Essays/InsanityCube

The perlmonks node Challenge: "Insanity" Cube Puzzle presents an interesting puzzle game.

The puzzle consists of four cubes. Each cube has each six sides colored in one of four colors: green, purple, red, yellow. The patterns are the the following, listed for each cube in the order left, front, right, back, top, bottom.

   pgpygr
   rprrgy
   ppryyg
   rrygpy

The goal is to build a tower of four cubes rotating the four cubes in such a way that on any side of the tower you see four different colors.

The puzzle is easy to solve with a brute force solution in J, so here's what I (B Jonas) wrote (it is also posted in that thread).

NB. Insanity cube puzzle: http://www.perlmonks.com/?node_id=559228
NB. Solution by ambrus.
NB. Very inefficent wrt memory and somewhat inefficent wrt speed,
NB. but no need to optimize on a modern machine.

NB. a cube is a list of 6 sides (each atoms):
NB. left front right back top bottom.
NB. the first four of these sides are visible on the sides in a tower.
NB. a towers is a list of 4 cubes.

NB. colorings.
input =: >;: 'pgpygr rprrgy ppryyg rrygpy'

NB. all 24 rotations of a cube.
gens =: (i.6),'NSKTFL'i.'FSLTKN',:'SKTNFL'
rots =: ([:~.[:/:~[:,/{"1/)^:_~ gens

NB. all 24 rotations of each 4 cube.
posn =: rots {"_ 1 input

NB. stack a list of 4 lists of 24 cubes to a tower of 4 cubes in each 24^4 way,
NB. order of 4 cubes doesn't matter.
stack =: [:>[:>[:,[:{[:<"1<"1
towers =: stack posn

NB. check if a cube is good or bad -- rank 2, gives bool atom.
good =: [: (*./"1) 4 ({."1) 4 = [: (#@:~."1) |:"2
solns =: (good # ]) towers

NB. each solution gives 8 trivially equivalent solutions because you can
NB. rotate all cubes simultanously around the vertical axis or twice around
NB. the horizontal axis.  (this may be less than 8 for degenerate cubes.)
NB. rota y gives all 8 rotations of a tower y
rott =: (2{gens)&({"_ 1)
rotu =: ({~1{gens)&({"_ 1)
rota =: ([: ,/ [: rott^:(<4) rotu^:(<2))"2
NB. verify that each rotation of each solution is indeed among the solutions.
assert =: 3 :'assert. y'
assert *./ solns e.~ ,/ rota solns
NB. now normalize the solutions by changing a tower to the
NB. lexicographically first out of these eight variants,
NB. and weed out repetitions.
norml =: ([:{.[:/:~rota)"2
solns1 =: ~./:~ norml solns

NB. output the solutions. there's just one if you use the sample
NB. cube colorings in the post.
echo solns1
echo #solns1

NB. end

The output follows (there's just one solution for this pattern).

ggrypp
ypgrrr
ryppyg
prygyr
1

See also Doc/Articles/Play173

-- B Jonas <<DateTime(2008-08-06T19:57:49Z)>>

---