The Clocks
InterviewTime limit1sMemory limit256 MB
Given nine clock dials and nine moves that each rotate a fixed subset of dials by 90 degrees, find the shortest move sequence that sets every dial back to 12 o'clock.
- Level
Medium5 of 10
- Topics
- Brute force, Backtracking, Implementation, Math
- Solved
- No attempts yet
Problem
|-------| |-------| |-------|
| | | | | | |
|---O | |---O | | O |
| | | | | |
|-------| |-------| |-------|
A B C
|-------| |-------| |-------|
| | | | | |
| O | | O | | O |
| | | | | | | | |
|-------| |-------| |-------|
D E F
|-------| |-------| |-------|
| | | | | |
| O | | O---| | O |
| | | | | | | |
|-------| |-------| |-------| (Figure 1)
G H I
Nine clocks are arranged in a 3×3 grid (Figure 1). The goal is to return every dial to 12 o'clock using as few moves as possible. There are nine allowed ways to turn the dials; each way is called a move and is numbered from 1 to 9. Applying a move rotates the dials of the affected clocks 90 degrees clockwise, according to Figure 2 below.
Move Affected clocks
1 ABDE
2 ABC
3 BCEF
4 ADG
5 BDEFH
6 CFI
7 DEGH
8 GHI
9 EFHI (Figure 2)
Input
Nine integers describing the initial positions of the dials, listed clock by clock from A to I in the order shown in Figure 1 (top row A B C, middle row D E F, bottom row G H I). Each value is one of: 0 = 12 o'clock, 1 = 3 o'clock, 2 = 6 o'clock, 3 = 9 o'clock. The nine numbers may be split across several lines or separated by arbitrary whitespace.
Output
Print the shortest sequence of moves that returns every dial to 12 o'clock: the move numbers in non-decreasing order, separated by single spaces. If a move is used more than once, repeat its number that many times. Because the puzzle has exactly one shortest solution, this sequence is unique. If the dials are already all at 12 o'clock, print an empty line.
Hint
Each value corresponds to a clock position:
0 = 12 o'clock
1 = 3 o'clock
2 = 6 o'clock
3 = 9 o'clock
For the configuration in Figure 1, applying moves 5, 8, 4, and 9 returns every dial to 12 o'clock (the order does not matter):
3 3 0 3 0 0 3 0 0 0 0 0 0 0 0
2 2 2 5-> 3 3 3 8-> 3 3 3 4 -> 0 3 3 9-> 0 0 0
2 1 2 2 2 2 3 3 3 0 3 3 0 0 0