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 example diagramtic representation(for clarification)

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

• Gareth: Source. I'm not sure what the general feeling is about posting puzzles from other sites here, but at the very least you should give credit to the originator.
• Paul R: Is this a code-golf or a code-challenge ? It's currently tagged as both. As for attribution, it's just common courtesy to cite the source of something that you have copied, even if it's in the public domain
• Gareth: @DavidCarraher Possibly, but the solutions there are not required to be golfed whereas this is marked as [code-golf]. Also, if someone is waiting for a way to solve the puzzle they only need to wait for the first answer to arrive here.
• Peter Taylor: Similar to codegolf.stackexchange.com/questions/586, codegolf.stackexchange.com/questions/693 , codegolf.stackexchange.com/questions/2478 , codegolf.stackexchange.com/questions/3474 , codegolf.stackexchange.com/questions/3524 , codegolf.stackexchange.com/questions/4084 , codegolf.stackexchange.com/questions/4619
• acolyte: Wait, if he's emailing people, then he has access to the internet. which means that there's absolutely 0 reason to go outside. ever.

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.

• DavidC: 715 states seems like such a small number given there are 13 positions and four fillers. Even with symmetry taken into account. I'll have to give this more thought.
• Keith Randall: (13 choose 4) = 715 en.wikipedia.org/wiki/Combination.
• DavidC: Yes. I didn't do the math. Just assumed it was much larger.
• DavidC: I cannot figure out how you managed to tackle such a big problem with so little code!

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"]

out

grid

---

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.