Want to try solving this problem? You can submit your code online if you log in or register.

**Input File:** `clocks.in`

**Output File:** `clocks.out`

**Time Limit:** 0.5 seconds

There are nine clocks in a 3-by-3 array as shown in the diagram below.

|-------| |-------| |-------| | | | | | | | |---O | |---O | | O | | | | | | | |-------| |-------| |-------| A B C |-------| |-------| |-------| | | | | | | | O | | O | | O | | | | | | | | | | |-------| |-------| |-------| D E F |-------| |-------| |-------| | | | | | | | O | | O---| | O | | | | | | | | | |-------| |-------| |-------| G H I

The goal is to return all the dials to 12 o'clock with as few moves as possible.
There are nine different allowed ways to turn the dials on the clocks.
Each such way is called a *move*, and these moves are numbered 1,2,...,9.

Each move involves selecting a subset of clocks and turning the dials 90 degrees clockwise on each of those clocks. The clocks affected by each move are listed in the table below.

Move Affected clocks 1 ABDE 2 ABC 3 BCEF 4 ADG 5 BDEFH 6 CFI 7 DEGH 8 GHI 9 EFHI

The input file will contain three lines of three numbers each, representing the starting positions of the dials. Each number will be 0, 1, 2 or 3, representing 12 o'clock, 3 o'clock, 6 o'clock or 9 o'clock respectively. The three numbers on each line will be separated by spaces.

The output should consist of a shortest sequence of moves that returns all the dials to 12 o'clock. These moves should be output on a single line, with each move represented by an integer from 1 to 9 as explained above. The moves should be separated by spaces in the output file. If there are many possible solutions, you should output only one (any one will do).

3 3 0 2 2 2 2 1 2

5 8 4 9

The four moves `5 8 4 9` return all the dials to
12 o'clock as illustrated below.

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

Privacy
statement

© Australian Mathematics Trust 2001-2021

Page generated: 1 December 2021, 11:58am AEDT