The Clocks - USACO 1.4.2

theclocks - codetrick
Consider nine clocks arranged in a 3x3 array thusly:

|-------|    |-------|    |-------|    
|       |    |       |    |   |   |    
|---O   |    |---O   |    |   O   |          
|       |    |       |    |       |           
|-------|    |-------|    |-------|    
    A            B            C

|-------|    |-------|    |-------|
|       |    |       |    |       |
|   O   |    |   O   |    |   O   |
|   |   |    |   |   |    |   |   |
|-------|    |-------|    |-------|
    D            E            F

|-------|    |-------|    |-------|
|       |    |       |    |       |
|   O   |    |   O---|    |   O   |
|   |   |    |       |    |   |   |
|-------|    |-------|    |-------|
    G            H            I

The goal is to find a minimal sequence of moves to return all the dials to 12 o'clock. Nine different ways to turn the dials on the clocks are supplied via a table below; each way is called a move. Select for each move a number 1 through 9 which will cause the dials of the affected clocks (see next table) to be turned 90 degrees clockwise.

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

Example

Each number represents a time accoring to following table:

9 9 12       9 12 12       9 12 12        12 12 12      12 12 12 
6 6 6  5 ->  9  9  9  8->  9  9  9  4 ->  12  9  9  9-> 12 12 12 
6 3 6        6  6  6       9  9  9        12  9  9      12 12 12 

[But this might or might not be the `correct' answer; see below.]

PROGRAM NAME: clocks

INPUT FORMAT

Lines 1-3:

Three lines of three space-separated numbers; each number represents the start time of one clock, 3, 6, 9, or 12. The ordering of the numbers corresponds to the first example above.

SAMPLE INPUT (file clocks.in)

9 9 12
6 6 6
6 3 6

OUTPUT FORMAT

A single line that contains a space separated list of the shortest sequence of moves (designated by numbers) which returns all the clocks to 12:00. If there is more than one solution, print the one which gives the lowest number when the moves are concatenated (e.g., 5 2 4 6 < 9 3 1 1).

SAMPLE OUTPUT (file clocks.out)

4 5 8 9

X. http://leonlu.iteye.com/blog/1125347
某一种转动方式若使用4次即没使用。因此1-9每一种转动方式至多使用4次，因此9种转动方式最多产生4(enum 0...3)^9=262144个序列，使用dfs完全遍历也不会超时。保存每次产生的有效序列结果，全部遍历完成后，按序列长度和数字大小排序，输出第一个结果。 
https://github.com/leonlu/USACOJavaSolution/blob/master/USACOSection1/src/clocks.java

	// O(n) = 4^9 = 262144 public class clocks {
	private static int[] clock;
	private static int[][] moves;
	private static List<int[]> validSequences;
	public static void main(String[] args) throws Exception {
	BufferedReader in = new BufferedReader(new FileReader("clocks.in"));
	PrintWriter out = new PrintWriter(new BufferedWriter(new FileWriter(
	"clocks.out")), true);
	// read in
	StringTokenizer st = new StringTokenizer(in.readLine());
	clock = new int[9];
	for (int i = 0; i < clock.length; i++) {
	if (!st.hasMoreTokens())
	st = new StringTokenizer(in.readLine());
	clock[i] = Integer.parseInt(st.nextToken());
	}
	// use char-'A' to generate the moves
	moves = new int[][] { { 'A', 'B', 'D', 'E' }, { 'A', 'B', 'C' },
	{ 'B', 'C', 'E', 'F' }, { 'A', 'D', 'G' },
	{ 'B', 'D', 'E', 'F', 'H' }, { 'C', 'F', 'I' },
	{ 'D', 'E', 'G', 'H' }, { 'G', 'H', 'I' },
	{ 'E', 'F', 'H', 'I' } };
	for (int i = 0; i < moves.length; i++)
	for (int j = 0; j < moves[i].length; j++)
	moves[i][j] -= 'A';
	// dfs
	validSequences = new ArrayList<int[]>();
	int[] moveSequence = new int[9];
	dfs(0, moveSequence);
	// sort by length and first number
	Collections.sort(validSequences, new Comparator<int[]>() {
	public int compare(int[] arg0, int[] arg1) {
	int sum0 = 0, sum1 = 0;
	for (int i = 0; i < arg0.length; i++) {
	sum0 += arg0[i];
	sum1 += arg1[i];
	}
	if (sum0 < sum1)
	return -1;
	else if (sum0 > sum1)
	return 1;
	for (int i = 0; i < arg0.length; i++) {
	if (arg0[i] < arg1[i])
	return -1;
	if (arg0[i] > arg1[i])
	return 1;
	}
	return 0;
	}
	});
	// output
	int[] res = validSequences.get(0);
	StringBuilder sb = new StringBuilder();
	for (int i = 0; i < res.length; i++) {
	int times = res[i];
	for (int j = 0; j < times; j++) {
	sb.append(i + 1);
	sb.append(" ");
	}
	}
	sb.deleteCharAt(sb.length() - 1);
	out.println(sb);
	System.exit(0);
	}
	private static void dfs(int t, int[] moveSequence) {
	if (t == moveSequence.length) {
	if (moveClocks(clock, moves, moveSequence))
	validSequences.add(moveSequence.clone());
	} else
	for (int i = 0; i < 4; i++) {
	moveSequence[t] = i;
	dfs(t + 1, moveSequence);
	}
	}
	private static int clockwise(int n) {
	n += 3;
	if (n == 15)
	return 3;
	else
	return n;
	}
	private static void moveClock(int[] clock, int[] move) {
	for (int i : move)
	clock[i] = clockwise(clock[i]);
	}
	private static boolean moveClocks(int[] clock, int[][] moves,
	int[] ms) {
	clock = clock.clone();
	for (int i = 0; i < ms.length; i++) {
	int[] move = moves[i];
	int cnt = ms[i];
	while (cnt-- != 0)
	moveClock(clock, move);
	}
	return successful(clock);
	}
	private static boolean successful(int[] clock) {
	for (int i : clock) {
	if (i != 12)
	return false;
	}
	return true;
	}
	}

1）产生序列时，可先尽量多得产生标号小的。每次标号产生完毕后，检查序列长度以及有效性，若序列较短则替换原有的长度及序列。 
2）时钟的状态不需要每次重新算，可以作为搜索的状态跟着跑。 
https://github.com/leonlu/USACOJavaSolution/blob/master/USACOSection1/src/clocks_refined.java
// 1. apply smaller moves first by repeating 3..0 instead of 0...3
// 2. when t == 9, just validate it and check the length. If a sequence of smaller length found, replace foundSequence with it.
// 3. make the moved clocks a state with dfs, rather than calculate it every time

X. Bit mask
http://cornered-code.blogspot.com/2013/03/usaco-clocks.html

TODO: http://olympiads.win.tue.nl/ioi/ioi94/contest/day2prb1/solution.html
http://blog.tomtung.com/2007/02/usaco-p58-the-clocks/
Read full article from theclocks - codetrick