Statistics

Problem Statement for "FlipFlop"

Problem Statement

Flip-Flop is a puzzle played with a m by n grid of cells. Each cell has a colored peg, which can be one of three colors: Red, Green, or Blue. Here are some examples of what the grid may look like ('R' for Red, 'G' for Green, 'B' for Blue): 

  • RRGGB      RGBRGB      RRR
RRRGG      GBRGBR      GGG
GRRRR      BRGBRG      BBB
GGRRR                  
BGGRR

A color-switch is defined as changing the peg from one color to another. Red switches to Green. Green switches to Blue. Blue switches to Red.

A move is made by first choosing one of the pegs and doing a color-switch on it (the flip). Then, its (up to) four neighboring pegs are color-switched (the flop). Diagonal neighbors do not count, only vertical and horizontal neighbors do. Edges do not wrap around.

For example (the coordinates are represented as a (row, col) pair): 

  12345         12345         12345
1 BBBGG       1 BBBBB       1 BBBBB
2 BBBBG       2 BBBBB       2 BBBBB
3 BBBBB  -->  3 BBBBB  -->  3 BBBBB
4 GBBBB       4 GBBBB       4 BBBBB
5 GGBBB       5 GGBBB       5 BBBBB

Move 1     |  Move 2
-----------+------------
flip(1,5)  |  flip(5,1)
flop(1,4)  |  flop(4,1)
flop(2,5)  |  flop(5,2)

Another example: 

  12345         12345         12345         12345         12345
1 BRBBG       1 BGBBG       1 BBBBG       1 BBBBG       1 BBBBB
2 RRRGG       2 GGGGG       2 BBBGG       2 BBBGG       2 BBBBB
3 BRGBG  -->  3 BGGBG  -->  3 BBGBG  -->  3 BBBBG  -->  3 BBBBB
4 BGGGB       4 BGGGB       4 BGGGB       4 BBBBB       4 BBBBB
5 BBGBB       5 BBGBB       5 BBGBB       5 BBBBB       5 BBBBB
6 BBBBB       6 BBBBB       6 BBBBB       6 BBBBB       6 BBBBB

Move 1     |  Move 2     |  Move 3     |  Move 4
-----------+-------------+-------------+------------
flip(2,2)  |  flip(2,2)  |  flip(4,3)  |  flip(2,5)
flop(1,2)  |  flop(1,2)  |  flop(3,3)  |  flop(1,5)
flop(2,1)  |  flop(2,1)  |  flop(4,2)  |  flop(2,4)
flop(2,3)  |  flop(2,3)  |  flop(4,4)  |  flop(3,5)
flop(3,2)  |  flop(3,2)  |  flop(5,3)  |

The object of Flip-Flop is to start with some initial board position and reach the board with all Blue pegs by making a series of moves. Some initial positions are solvable. But for others, it is impossible. For each solvable initial position, there exists a minimum number of moves required to solve the puzzle.

You are given a String[], board, as the initial board position. Each element of board represents a row of the initial position by the colors of the pegs, with Element 0 as the first row, Element 1 as the second row, and so on. Your task is to write a function that returns the minimum number of moves to solve the puzzle. If the given initial position is unsolvable, return -1.

Definition

Class:
FlipFlop
Method:
minMoves
Parameters:
String[]
Returns:
int
Method signature:
int minMoves(String[] board)
(be sure your method is public)

Constraints

  • board contains between 2 and 10 elements, inclusive
  • board contains only the uppercase letters 'R', 'G', 'B'
  • Each element of board contains between 2 and 10 characters
  • All elements of board have the same length

Examples

  1. {"BBBGG", "BBBBG", "BBBBB", "GBBBB", "GGBBB"}

    Returns: 2

    This is the same as the first example. It requires a minimum of 2 moves.

  2. {"BRBBG", "RRRGG", "BRGBG", "BGGGB", "BBGBB", "BBBBB"}

    Returns: 4

    This is the same as the second example. It requires a minimum of 4 moves.

  3. {"RRG", "RGG"}

    Returns: 3

    Flip the top-left corner twice and the bottom-right corner once.

  4. {"RRRBRGGB", "BRBGGBGR", "RBGBBGRG"}

    Returns: -1

    This position is unsolvable.

  5. {"BBBBBB", "BGGGGB", "BGRRGB", "BGRRGB", "BGGGGB", "BBBBBB"}

    Returns: 32

  6. {"RRRGGGBBB", "RRRGGGBBB", "RRRGGGBBB", "BBBRRRGGG", "BBBRRRGGG", "BBBRRRGGG", "GGGBBBRRR", "GGGBBBRRR", "GGGBBBRRR"}

    Returns: 69

  7. {"BBBBBBBBBB", "BGGGGGGGGB", "BGBBBBBGBB", "BBBRBBGBBB", "BBBBRGBBBB", "BBBBGRBBBB", "BBBGBBRBBB", "BBGBBBBBGB", "BGGGGGGGGB", "BBBBBBBBBB"}

    Returns: 104

    Watch for timeout!

  8. {"GRRRRRRRRB", "RRRRRRRRRR", "RRRRRRRRRR", "RRRRRRRRRR", "RRRRGBRRRR", "RRRRBGRRRR", "RRRRRRRRRR", "RRRRRRRRRR", "RRRRRRRRRR", "BRRRRRRRRG"}

    Returns: 128

  9. {"GRRRB","GBRGB","RRBRG","BRBBB","RBGBB","RGBRG"}

    Returns: 29

  10. {"BGGRBRGR","BGRRBGBG","BRGRRBBB","RRGRGRBG","RRGRBBGB","BBRBBRBB","BRRRGGBG","RBGRGRBB"}

    Returns: -1

  11. {"BGRGGRB","RBRBGGG","RGGGGGB","RRRGGGR","GGGRRRR","BGRGGBR"}

    Returns: 40

  12. {"GGR","BGB","RBR","RRB","BBB","GBR","RRG"}

    Returns: 22

  13. {"RGRGBBGRG","GGBRGGBGB","GRBRGRRBB","GGRGBRGGB","GGRRBRBBB","RRRGBGBGR"}

    Returns: 50

  14. {"BRBRRGBR","RBBRBBRB","BBBBRRGB","GGBBGRBR","RGBBGRGB","GRRRBRBB","GGRBRRRR"}

    Returns: 50

  15. {"GBBGRG","BBGGGG","GGBBRG","BGGRGB","GBRBRB","BBBBBG","RRBGRB","GBBGRG"}

    Returns: 47

  16. {"RBBBBG","RBRGGR","GBGRRR","BRBGGB","RRRGBG","GRBBBB"}

    Returns: 26

  17. {"BBRBGGGRBR","GRBGRBGBRB","RRGRBGRRBR","BGBGRGGRBG"}

    Returns: 42

  18. {"GRBBRBRGRB","GGRGRGBGGR","BBGGGGGGGB","RRGGGBGBRG","BRBBGRBBRG","BGBBRBGRBG","GGBGRBRBGG","GRBBGRGGRB","GRRGBBGGGR"}

    Returns: 86

  19. {"RBBBB","BRRBR","RRGGR"}

    Returns: 12

  20. {"RBRRGRRR","GGGBRRBR","GRGGBBRG","BRBGGGRB"}

    Returns: 34

  21. {"RRGGRG","BGGGBG","BRGGBB","BBGGGB","BRBRRB","RRBRGR","BBRBBB","GGGBGR","RRBBGB"}

    Returns: 51

  22. {"GGBRRBBR","RRBRRBRB"}

    Returns: -1

  23. {"BGRB","BGRB","BBBB","RBGG","RRRR","RGGR"}

    Returns: 26

  24. {"BGGGBBRGR","GGRBBRGGB","GRBGBGBGB","RRBGBBRRG","RBBBRGRGG","BGGGRRRBG","BRBBBBGRB","BRRRGRGRR","GBRBGBBRB"}

    Returns: -1

  25. {"BB","RR","BR","BG","RR","GB","GR"}

    Returns: 12

  26. {"GGRBGG","GGBRGB","GBRRRB","BBRGGG","RRBGRR","GRRGGG","BGBGBB","GRBRGR"}

    Returns: 39

  27. {"GBBBGGGRB","BBBRBGRRB","GGGGGRBBB","RRGGBGBGG","GGBRBRGRB","GGGBBBGBR","RBBRRRRGG","GBRGGBBGG","BBBGGGBGG"}

    Returns: -1

  28. {"GGBG","BRGR","RRRB","RRGR","BRGG","GRBB"}

    Returns: 32

  29. {"BBGB","BBGB","BGBR","RRRG","BGGG","GGGR","BBGR","BRBB","BGGB"}

    Returns: -1

  30. {"RB","RG","BG"}

    Returns: 6

  31. {"GGGRRGGRGB","RBRBBRGRGR","RGGRGBRRBG"}

    Returns: 26

  32. {"RBRRG","RRBGR","RBBRG"}

    Returns: 19

  33. {"BRGRG","GRGBR","RGGRB","RBGRG","GGRGG","GBRRR","RGBGG","GGRGB","BBRGB","BRBGB"}

    Returns: 52

  34. {"BGG","RRB","GGR","RRG","GBR","GGB","BRB","RRR","GBR"}

    Returns: -1

  35. {"RRBGRBGRG","GGRGRGBRG","RBGBBBGRB"}

    Returns: -1

  36. {"RGRGRRBGR","BGBBGGBBB","BRGBBBRBR"}

    Returns: -1

  37. {"GBRR","BBBG","GBRR","GBGR","RGBG","RRBG","RGRR","RGRR","GRGR","RRRR"}

    Returns: 46

  38. {"GBGBGRBRB","RBBBGBRRG"}

    Returns: -1

  39. {"BBGRBBGR","BGGGRGGG","BRGRGGGR","BRBRGGRR","GBRRRRBR","GRBBRGRG","BGGBRGBR"}

    Returns: -1

  40. {"RBGG","BBBR","RBRR","GRGR","BGBB","BRGG","GRRR","BRGB","BBRB","BGBB"}

    Returns: 44

  41. {"RBBGRBBRBG","RBBBBGBRBR","RGBRGGBBBR","RBBBRBGGRR","GGGGGGGGBR","BGGRRGBGGB","GGBRGGBBGB","GGBBBGGBGR","GBRBBBBGRR","RGBBBBRRGB"}

    Returns: 102

  42. {"BBRBGR","BRRRRG","RRRBRB","RGGBRG","RBRRRR","BBBGGB","RRRBBB"}

    Returns: 40

  43. {"GRRGGGRBG","GGGGGBBRR","RBGGRGRRG","GBRGBBBRR","BBRGRBBBR","BRRRRRBGR","BGGGBRRGB","GGRBRGBGR","BBRBGBBBR","BGGBBRRRR"}

    Returns: 91

  44. {"BRGRGRR","RBRRGGG","BRBGBGB","GRBGBBB","BRRRGRG","GRGRRBR","BBRBGRG"}

    Returns: 50

  45. {"RBBRRBR","BGRBRGR"}

    Returns: -1

  46. {"RRGGR","GRGBG","GGGGR","BRRGG","BBRRG","GRRRG","BGGGG","RGRBR","RGRGB","RGBGG"}

    Returns: 54

  47. {"BBRGBGRRB","RGBBGGBRB","GGGBRBBGG","RGGGRBGBG","RBBBRGGRG","RBGRBRGGG"}

    Returns: 54

  48. {"GGGGGB","RRGBBR","RRGRRR","GGBRGR"}

    Returns: 31

  49. {"GRBRB","RRGGR","RBRBB","GGBBR","GBGGB","RBGRB","RBBGB","BRBRG","GBBGB"}

    Returns: 36

  50. {"RRBRRBGGGB","GRRGBGRRRR","RBBGRBRGBG","BBGRGBRBBG"}

    Returns: 35

  51. {"GGGRBGBRRB","RRGGRGRRRR","BBRRGRRBGR","GGGBRRBGRR","BBBBGGGGRB","GBBGGRBRGB","RRGBBBBRBB","GBRBGBBRRR","GRGRRRRGBG","GBGGBBBRGG"}

    Returns: 97

  52. {"BR","RR"}

    Returns: 2

  53. {"BGRRBRGBR","RGGRRBGGG","GRGRBBGGG","GGRGBRRGG","GRBGGRGGG","RRGBGGBGG","BRBBGGBRR","BRGRGGGRB","RGRRGGRGR","RRRBBRRBG"}

    Returns: 84

  54. {"RG","RG","RR","RR","RB","RR","RG","BG"}

    Returns: -1

  55. {"BBBGRRGR","GGGRGGGR","BGBGBBBB","BRRBBRRB","GRBBBBGG","GBGBRRRB","RGRRRRGG","GBBRRBBR"}

    Returns: -1

  56. {"BGBRG","GGGRB","BBGGG","RBBBB","GRGBR","GGBRG","GRRGB","GBRBR","GBRGR"}

    Returns: 46

  57. {"GRRBRRB","BRBBBRG","RBGRRRG","GBGRBBR"}

    Returns: 22

  58. {"RBBRGRGBGG","BBGBGGBGRR"}

    Returns: 27

  59. {"BBBBBBBB", "BBBBBBBB", "BBBBBBBB", "BBBBBBBB", "BBBBBBBB", "BBBBBBBB", "BBBBBBBB"}

    Returns: 0

  60. {"BB", "BB"}

    Returns: 0

  61. { "BBBBBBBBBB", "BGGGGGGGGB", "BGBBBBBGBB", "BBBRBBGBBB", "BBBBRGBBBB", "BBBBGRBBBB", "BBBGBBRBBB", "BBGBBBBBGB", "BGGGGGGGGR", "BBBBBBBBRR" }

    Returns: 106

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2024, TopCoder, Inc. All rights reserved.
This problem was used for: