Problem D
Rubik's Revenge in ... 2D!? 3D?
You are given a puzzle that can be represented as a $4 \times 4$ grid of colored cells. The solved puzzle contains 4 monochromatic rows, in this order: red, green, blue, yellow. Although we will analyze this puzzle using its 2D representation, it is actually a 3D puzzle! Imagine that the grid is stretched over a torus (in other words, top edge is connected to the bottom one and left edge is connected to the right one). If you are not familiar with the word “torus” or what it is supposed to represent, just replace it with the word(s) “donut (with the hole in the middle)”.
Given a description of a state of this puzzle, what is the minimum number of moves you need to solve it? Note that all possible puzzle configurations are solvable in less than 13 moves.
Input
Input file contains exactly $4$ lines, containing $4$ characters each, each character being either “R”, “G”, “B” or “Y’. The input will describe a valid state of the puzzle.
Output
Output the minimum number of moves needed to solve the given puzzle.
Sample Input 1 | Sample Output 1 |
---|---|
RGGR GBGB BYBY YRYR |
3 |
Sample Input 2 | Sample Output 2 |
---|---|
RRRR GBGG GYBB BYYY |
4 |