Help johnny to solve this Puzzle

Question

Scenario

Little Johnny wants to play with his friends today. But his babysitter won't let him go! After a lot of begging, the heartless nanny gives him her brand new electronic puzzle and says: "If you solve the puzzle then you are free to go". Not being aware of Little Johnny's IT skills, the nanny leaves the kid alone. Rapidly, Little Johnny sends you an e-mail asking for your help. The puzzle consists of three hexagons as shown in the figure. Each vertex is painted black or white. Some of them belong to just one hexagon and some of them belong to more than one. Exactly four of them are painted black, and the other nine are white. The goal is to make the shared vertexes black by means of allowed moves: rotating a hexagon 60 degrees clockwise or counter-clockwise. Can you help Little Johnny?

Input

Input starts with an integer T, the number of puzzles to solve (1<=T<=100). T lines follow, each one having 13 binary digits, corresponding to the top-down, left to right labeling of the vertexes in the puzzle. A '0' means the i-th vertex is painted white, while a '1' means it is painted black.

output

For each test case output M on a single line, the minimum number of moves required to solve the puzzle. Then print M lines, each one describing a move in the following manner: two space separated integers H and C, the rotated hexagon (upper left is 0, upper right is 1, lower one is 2) and the direction (0 for counter-clockwise, 1 for clockwise). If there is more than one solution, any will suffice.

Example

Input sample:

1 0000000101011

output sample:

3

2 0

2 0

1 1

source Limit

50000 Bytes

time limit

1 sec

Winning constrain

shortest code with specified time limit wins!

I leave the question for five days to decide winner future answers after five days too welcome

Answer 1

Python, 307 chars

S={'0001001011000':[]}
for i in[0]*7:
 for s in dict(S):
  for m in range(6):S.setdefault(''.join(s[int(x,16)]for x in['2150483769abc','3106428759abc','0326159487abc','0421753986abc','01234587a6c9b','012345976b8ca'][m]),[m]+S[s])
for j in[0]*input():
 L=S[raw_input()];print len(L)
 for m in L:print m/2,m%2

Computes S which is a mapping from a state (a string just like the input) to a list of move numbers which solve the state. Generates a complete S on startup (only 715 states), then looks up each input and prints the answer.

Moves are implemented using a string of hex digits indicating where each result vertex comes from.

Takes about 0.15 seconds regardless of how big the input is.

Answer 2

Mathematica 831

This was a very demanding challenge that took me several days to work out and streamline, far more than a typical challenge.

This graphs all the nodes, where each node corresponds to one arrangement of 4 black hexagon vertices. Then we find the shortest distance from an input vertex to the solution vertex, {4, 7, 9, 10}.

c = Complement; h = {{7, 9, 6, 3, 1, 4}, {7, 4, 2, 5, 8, 10}, {7, 10, 12, 13, 11, 9}}; i = {4, 7, 9, 10};l = RotateLeft; n = Module; q = Sort; r = RotateRight; s = Flatten;

p[v_, x_, r_] := Block[{d}, n[{d = v \[Intersection] x},If[d != {}, {v, (r[x][[Position[x, #][[1, 1]]]] & /@ d) \[Union] c[v, d], {x /. {h[[1]] -> 0, h[[2]] -> 1, h[[3]] -> 2}, r /. {r -> 0, l -> 1}}}, {}]] /. {{a_, b_, c_} :>   {q@a \[DirectedEdge] q@b, q@a \[DirectedEdge] q@b -> c}}]

o[e_, t_] := Cases[s[Outer[p, {#}, h, {l, r}, 1]~s~2 & /@ e, 1], {a_ \[DirectedEdge] w_, b_} /; \[Not] MemberQ[t, w] :> {a \[DirectedEdge] w, b} ]

m[{g_, j_, _, b_}] :=n[{e, k, u, z},{e, k} = Transpose[o[c @@ g, g[[2]]]];z = Graph[u = Union@Join[e, j], EdgeLabels -> k];{Prepend[g, c[VertexList[z], s[g, 1]]], u, z, Union@Join[k, b]}]

t[j_] :=n[{r, v, y, i = {4, 7, 9, 10}},z = Nest[m, {{{i}, {}}, {}, 1, {}}, 7];v = FindShortestPath[z[[3]], i, Flatten@Position[Characters@j, "1"]];y = Cases[z[[4]], Rule[DirectedEdge[a_, b_], k_] /; MemberQ[v, a] && MemberQ[v, b]];r = Reverse[y[[Cases[Flatten[Position[y, #] & /@ v, 1], {a_, _, 1} :> a]]]] /. (_ \[DirectedEdge] _ -> k_) :>  k ;Grid@Join[{{Length[r]}}, r]]

Usage

t["0100000100011"]

---

Timing

The search space loads at the when the code is read for the first time. A solution takes approximately .32 seconds, regardless of the distance from the solution node.

Note: [Intersection], [Union], and [DirectedEdge] are single, dedicated characters in Mathematica.