Rubik's Cube Daily Programmer Challenges

rubiks-cube.hs

{-# LANGUAGE NoMonomorphismRestriction #-}
{-# LANGUAGE ViewPatterns #-}

import Control.Monad
import Data.Array.IO
import Data.List.Split (chunksOf)

type Point = (Int,Int,Int)

-- basic rotations
xtoy (x,y,z) = (-y,x,z) -- rotate x-axis onto the z-axis
xtoz (x,y,z) = (-z,y,x)
ytoz (x,y,z) = (x,-z,y)
ytox (x,y,z) = (y,-x,z)
ztoy (x,y,z) = (x,z,-y)
ztox (x,y,z) = (z,y,-x)

rotF p@(_,y,_) | y <= -1 = ztox p
rotF p = p

-- define the other moves in terms of rotF
rotR = xtoy . rotF . ytox
rotL = ytox . rotF . xtoy
rotB = ytox . ytox . rotF . xtoy . xtoy
rotU = ztoy . rotF . ytoz
rotD = ytoz . rotF . ztoy

-- the faces
faceF = (,,) <$> [-1,0,1] <*> [-2] <*> [1,0,-1]
(_ : faceR : faceB : faceL : _ ) = iterate (map xtoy) faceF
faceU = map ztoy faceF
faceD = map ytoz faceF

allfaces = faceF ++ faceR ++ faceB ++ faceL ++ faceU ++ faceD

face (2,_,_)  = 'R'
face (-2,_,_) = 'L'
face (_,2,_)  = 'B'
face (_,-2,_) = 'F'
face (_,_,2)  = 'U'
face (_,_,-2) = 'D'

-- parser
moves = [ ('F', rotF), ('B', rotB), ('L', rotL), ('R', rotR), ('U', rotU), ('D', rotD) ]

tmove :: Char -> Maybe (Point -> Point)
tmove c = lookup c moves

chmove c = case lookup c moves of
            Just _ -> Just c
            _      -> Nothing

mult :: String -> (Int, String)
mult ('\'':cs) = (3,cs)
mult ('2':cs) = (2,cs)
mult cs = (1,cs)

parseMoves p [] = []
parseMoves p ((p -> Just t) : (mult -> (n,cs))) = parseMoves p cs ++ (replicate n t)
parseMoves p (_:cs) = parseMoves p cs

orbit :: Eq a => (a -> a) -> a -> [a]
orbit p a = a : takeWhile (/= a) (iterate p (p a))

inverse :: Eq a => (a -> a) -> (a -> a)
inverse p a = last (orbit p a)

parse s = chain (parseMoves tmove s)

chain = foldr (.) id

-- Challenge 92 -- 2012-08-27

blt grid letters start delta = do
  let mv (x,y) (dx,dy) = (x+dx,y+dy)
  let xs = zip letters (iterate (mv delta) start)
  forM_ xs $ \(ch, rc) -> writeArray grid rc ch

blt33 grid letters start dr dc = do
  let mv (x,y) (dx,dy) = (x+dx,y+dy)
      rows = zip (chunksOf 3 letters) (iterate (mv dc) start)
  forM_ rows $ \(chs, rstart) -> do blt grid chs rstart dr

solve92 :: String -> IO ()
solve92 s =
  do let t = inverse (parse s)
     grid <- newArray ((0,0),(5,11)) ' ' :: IO (IOUArray (Int,Int) Char)
     blt33 grid (map (face . t) faceF) (3,0) (1,0) (0,2)
     blt33 grid (map (face . t) faceR) (3,6) (1,0) (-1,2)
     blt33 grid (map (face . t) faceU) (0,4) (1,-2) (0,2)
     blt grid "///" (0,10) (1,-2)
     blt grid "|||" (3,5) (1,0)
     chs <- getElems grid
     forM_ (chunksOf 12 chs) $ putStrLn
     putStrLn ""
     return ()

main92 = do
  solve92 "R U B' R B R2 U' R' F R F'"
  solve92 "F' B L R' U' D F' B"

-- Challenge 157 -- 2014-04-09

solve157 s =
  do let t = inverse (parse s)
     putStrLn $ s ++ " -> "
     putStrLn $ fmt $ map (face . t) faceF
     putStrLn ""
  where fmt [a,b,c,d,e,f,g,h,i] = unlines [ [a,d,g], [b,e,h], [c,f,i] ]

cycleDecomposition :: (Eq a, Ord a) =>  (a -> a) -> [a] -> [ [a] ]
cycleDecomposition p xs = go xs []
  where go [] cycles = cycles
        go (a:as) cycles
          | any (elem a) cycles = go as cycles
          | otherwise           = go as (orbit p a: cycles)

cycles p = map length $ cycleDecomposition p allfaces

main157 = do
  solve157 "U2 R' D2 R F L' U2 R"
  solve157 "R U2 F2 D' F' U L' D2 U2 B' L R2 U2 D"

-- Challenge 336 - 2017-10-18

solve336 s = do let t = parse s
                    o = foldl1 lcm (cycles t)
                putStrLn $ s ++ " -> " ++ show o ++ "\n"

main336 = do
  solve336 "R"
  solve336 "R F2 L' U D B2"
  solve336 "R' F2 B F B F2 L' U F2 D R2 L R' B L B2 R U"
  solve336 "R D"

main = do { main92; main157; main336 }

rubiks-cube.js

// basic rotations
function xtoy ([x,y,z]) { return [-y,x,z] } // rotate the x-axis onto the y-axis
function xtoz ([x,y,z]) { return [-z,y,x] }
function ytoz ([x,y,z]) { return [x,-z,y] }
function ytox ([x,y,z]) { return [y,-x,z] }
function ztoy ([x,y,z]) { return [x,z,-y] }
function ztox ([x,y,z]) { return [z,y,-x] }

// the F move
function rotF(p) {
  return (p[1] <= -1) ? ztox(p) : p
}

function conj(t, r)  { return (p) => r(r(r(t(r(p))))) }
function conj2(t, r) { return (p) => r(t(r(p))) }
function comp(f, g)  { return (p) => f(g(p)) }

// the other basic moves
let rotR = conj(rotF, ytox)
let rotL = conj(rotF, xtoy)
let rotB = conj2(rotF, comp(xtoy, xtoy))
let rotU = conj(rotF, ytoz)
let rotD = conj(rotF, ztoy)

// the faces
// we don't have array comprehensions in node8.5
let faceF = []
for (let x of [-1,0,1]) { 
  for (let z of [1,0,-1]) {
    faceF.push([x,-2,z])
  }
}
let faceR = faceF.map(xtoy)
let faceB = faceR.map(xtoy)
let faceL = faceB.map(xtoy)
let faceU = faceF.map(ztoy)
let faceD = faceF.map(ytoz)

let allfaces = [].concat(faceF, faceB, faceL, faceR, faceU, faceD)

function face([x,y,z]) {
  if (x == 2)  return 'R'
  if (x == -2) return 'L'
  if (y == 2)  return 'B'
  if (y == -2) return 'F'
  if (z == 2)  return 'U'
  if (z == -2) return 'D'
  throw "oops!"
}

function ptequal(p,q) {
  return (p[0] == q[0]) && (p[1] == q[1]) && (p[2] == q[2])
}

function orbit(t, p) {
  let ps = [p]
  while (1) {
    p = t(p)
    if (ptequal(p, ps[0])) break
    ps.push(p)
  }
  return ps
}

function inverse(t) {
  return (p) => {
    let ps = orbit(t, p)
    return ps[ps.length-1]
  }
}

function cycleDecomposition(t, pts, equal) {
  let orbits = []
  for (let p of pts) {
    if (!orbits.some( (o) => o.some( (q) => equal(p,q) ))) {
      orbits.push( orbit(t, p) )
    }
  }
  return orbits
}

function gcd(a,b) {
  while (a) {
    let t = a; a = b % a; b = t;
  }
  return b
}

function lcm(a,b) {
  return a*b/gcd(a,b)
}

function order(t) {
  let orbits = cycleDecomposition(t, allfaces, ptequal)
  return orbits.map( (x) => x.length ).reduce( lcm, 1 )
}

// parser
let moves = { 'F': rotF, 'B': rotB, 'L': rotL, 'R': rotR, 'U': rotU, 'D': rotD }

function parseMove(face, mult) {
  let m = 1
  if (mult == "'") m = 3
  if (mult == "2") m = 2
  return Array(m).fill( moves[face] )
}

function parseMoves(s) {
  let re = /([FBLRUD])(['2]?)/g
  let ts = []
  s.replace(re, (m,g,h)  => ts.push( ...parseMove(g, h) ) )
  return ts
}

function parse(s) {
  let ts = parseMoves(s)
  return (p) => {
    for (let t of ts) { p = t(p) }
    return p
  }
}

// #92 display routines
function blt33(grid, letters, [gsr, gsc], [drr,drc], [dcr,dcc]) {
  for (let r = 0; r <= 2; ++r) {
    for (let c = 0; c <= 2; ++c) {
      let ch = letters[ r+3*c ]
      let gr = gsr + r*drr+c*dcr
      let gc = gsc + r*drc+c*dcc
      grid[gr][gc] = ch
    }
  }
}

function blt(grid, letters, [gsr, gsc], [dr,dc]) {
  for (let i = 0; i < letters.length; ++i) {
    grid[ gsr + i*dr ][ gsc + i*dc ] = letters[i]
  }
}

//       W W W /
//     W W W / R
//   W W W / R R
//   G G G|R R R
//   G G G|R R
//   G G G|R 

function solve92(s) { // Solve Challenge 92 -- 2012-08-27
  let grid = Array(6).fill(0).map( (x) => Array(12).fill(' ') )
  let t = inverse( parse(s) )
  let row = (n) => n*11
  blt33(grid, faceF.map(t).map(face), [3,0], [1,0], [0,2])
  blt33(grid, faceR.map(t).map(face), [3,6], [1,0], [-1,2])
  blt33(grid, faceU.map(t).map(face), [0,4], [1,-2], [0,2])
  blt(grid, "///", [0,10], [1,-2])
  blt(grid, "|||", [3,5], [1,0])
  console.log(s, "->")
  for (let g of grid) { console.log(g.join('')) }
  console.log("")
}

function solve157(s) { // Solve Challenge 157 -- 2014-04-09
  let t = inverse( parse(s) )
  let [a,b,c,d,e,f,g,h,i] = faceF.map( t ).map( face )
  console.log(` ${s} -> `)
  console.log(`${a}${d}${g}\n${b}${e}${h}\n${c}${f}${i}\n`)
}

function solve336(s) { // Solve Challenge 337 -- 2017-10-18
  let t = parse(s)
  console.log(s, "->", order(t), "\n")
}

function main92() {
  solve92("R U B' R B R2 U' R' F R F'")
  solve92("F' B L R' U' D F' B")
}


function main157() {
  solve157("U2 R' D2 R F L' U2 R")
  solve157("R U2 F2 D' F' U L' D2 U2 B' L R2 U2 D")
}

function main336() {
  let exprs = ["R F2 L' U D B2",
               "R' F2 B F B F2 L' U F2 D R2 L R' B L B2 R U" ,
               "R D"
              ]
  for (let s of exprs) { solve336(s) }
}

main92()
main157()
main336()

z-small-word-orders.txt

    1 -> D D'
    1 -> D F B F' B' D'
    1 -> D U D U' D2
    1 -> D U D' U'
    2 -> D D
    2 -> D F B F B D'
    2 -> D F B2 F D'
    2 -> D F2 B2 D'
    2 -> D F2 D'
    3 -> D F2 B2 U' B2 F2
    3 -> D F2 D2 F2 D
    4 -> D F B F B' F2
    4 -> D F B F' B'
    4 -> D F D'
    4 -> D F2 B2 U
    4 -> D U
    5 -> D F B F' D B'
    5 -> D F D F D2
    5 -> D F D F'
    6 -> D F B F2 B2 U
    6 -> D F B F2 U'
    6 -> D F B U
    6 -> D F2 D
    7 -> D F B F' D' L
    7 -> D F D L D2
    7 -> D F D' R
    8 -> D F B D
    8 -> D F B F B' U
    8 -> D F B2 F' U
    8 -> D F2 U
    9 -> D F B F' B L
    9 -> D F B F' L2
    9 -> D F R2
    9 -> D F2 L' D2
   10 -> D F B F' D' L2
   10 -> D F D' L
   10 -> D F2 U F L2
   12 -> D F B F B2 U2
   12 -> D F B F2 U
   12 -> D F B U'
   12 -> D F2 L2
   14 -> D F2 B U' B2 U
   15 -> D F B2 F' U' L2
   15 -> D F2 U F2 U2
   15 -> D F2 U' L2
   16 -> D F B D' L
   16 -> D F B F2 D' L'
   18 -> D F B2 F2 U2 F
   18 -> D F2 B U2 B2
   20 -> D F B F' U2 B'
   20 -> D F U2 F'
   20 -> D F2 B2 D L2
   21 -> D F B' D2 B'
   21 -> D F B2 F' U B2
   21 -> D F2 U F2
   22 -> D F B2 F2 L' U'
   22 -> D F B2 L U'
   24 -> D F B F B
   24 -> D F B F2 B F'
   24 -> D F B2 F
   24 -> D F2 B2
   28 -> D F B F' U B'
   28 -> D F U F'
   28 -> D F' B' D L2
   30 -> D F B F B F2
   30 -> D F B F B'
   30 -> D F B2 F'
   30 -> D F D
   30 -> D F2
   33 -> D F B F2 L'
   33 -> D F B2 F2 B' L'
   33 -> D F' B L'
   35 -> D F B2 F' U' B2
   35 -> D F B2 U L'
   35 -> D F2 U' F2
   36 -> D F B F U2
   36 -> D F B2 F B' U2
   36 -> D F B2 U2
   36 -> D F L2
   40 -> D F B D2 B2
   40 -> D F B F' U B2
   40 -> D F U F2
   42 -> D F B F2 U2 F2
   42 -> D F B U2 B2
   42 -> D F2 D2 F'
   44 -> D F B' L'
   44 -> D F2 B F' B2 L'
   44 -> D F2 B' F' L'
   45 -> D F B F' U B
   45 -> D F B' L2 B
   45 -> D F U F
   48 -> D F B2 F2 D2 L
   48 -> D F D2 L
   48 -> D F' B2 D2 L
   55 -> D F B2 U L' R2
   56 -> D F B F B L2
   56 -> D F B2 F L2
   56 -> D F B2 L'
   60 -> D F B F L'
   60 -> D F B F2 B L'
   60 -> D F L'
   60 -> D F2 B L'
   63 -> D F B F B2 F2
   63 -> D F B F2 B'
   63 -> D F B' F'
   63 -> D F D2
   63 -> D F'
   66 -> D F B F2 D2 L'
   66 -> D F' B D2 L'
   70 -> D F2 B' U' B2 U'
   70 -> D F2 U F2 L
   72 -> D F B F2 B2 L
   72 -> D F B' F2 L
   72 -> D F' B' L
   77 -> D F B F' U R'
   77 -> D F U L'
   77 -> D F2 B D2 L2
   80 -> D F B F' R
   80 -> D F L
   80 -> D F' R' D2
   80 -> D F2 B F' B' L
   84 -> D F B F' L
   84 -> D F B L2
   84 -> D F B2 F' B' L
   84 -> D F R
   90 -> D F B
   90 -> D F B F B2 F
   90 -> D F B F2 B2
   90 -> D F B' F2
   99 -> D F B2 F' L F2
   99 -> D F U2 F L
   99 -> D F2 L B2
  105 -> D F
  105 -> D F B F B' F'
  105 -> D F B F'
  105 -> D F B2 F' B'
  105 -> D F' D2
  112 -> D F2 B U' B2 R'
  120 -> D F U2 F
  120 -> D F2 B U2 B
  120 -> D F2 B2 F' U2 F
  126 -> D F B F U' L'
  126 -> D F U' L
  126 -> D F2 B U' L'
  132 -> D F B F B L'
  132 -> D F B2 F L'
  132 -> D F2 B2 L'
  140 -> D F B' F' D L'
  140 -> D F U2 B2 L2
  140 -> D F' D L'
  144 -> D F B F2 B L
  144 -> D F B2 F2 L
  144 -> D F' B2 L
  154 -> D F B U' B L
  165 -> D F B U' B' L'
  165 -> D F2 U' F L
  168 -> D F B F
  168 -> D F B F B F'
  168 -> D F B2
  168 -> D F B2 F B'
  180 -> D F B F B2 F'
  180 -> D F B F2
  180 -> D F B'
  180 -> D F B2 F2 B'
  198 -> D F B F B L
  198 -> D F B2 F L
  198 -> D F2 B2 L
  210 -> D F B F2 U2 F'
  210 -> D F B U2 B
  210 -> D F' U B'
  231 -> D F B F L2
  231 -> D F B F2 B2 L'
  231 -> D F B L'
  240 -> D F B' F' U2 L'
  240 -> D F U2 F2 L
  240 -> D F' U2 R'
  252 -> D F B F' U L
  252 -> D F U R
  252 -> D F' B' U2 L2
  280 -> D F U F L'
  280 -> D F2 B2 L' B L'
  315 -> D F B F U F'
  315 -> D F B2 U B'
  315 -> D F U B
  330 -> D F U2 B' L
  330 -> D F2 B U2 L B
  336 -> D F B' U2 L'
  336 -> D F2 B' F' U2 L'
  360 -> D F B F B F
  360 -> D F B F B2
  360 -> D F B2 F2
  360 -> D F2 B'
  420 -> D F B F' U F'
  420 -> D F B2 U2 L
  420 -> D F U B'
  462 -> D F B' U2 L
  462 -> D F2 B' F' U2 L
  495 -> D F B2 F D2 L'
  495 -> D F2 B2 D2 L'
  504 -> D F B' F' U2 R'
  504 -> D F' U2 L'
  504 -> D F2 B' D2 L
  630 -> D F B' F U F
  630 -> D F' B2 U B
  720 -> D F B' F U' L
  720 -> D F B2 U' L'
  840 -> D F B F B2 L
  840 -> D F B' F L
  840 -> D F2 B' L
  990 -> D F B' U2 B2 L
 1260 -> D F B2 F2 L F'
 1260 -> D F' B2 L F'