module Main where

import GHC.Exts
import Control.Monad
import Data.Set (Set)
import qualified Data.Set as Set

data Move   = L | R | U | D | F | A deriving Show
type Cursor = (Int, Int, Int)
type Trail  = Set Cursor
type State  = ([Move], Cursor, Trail)

size    = 3
count   = size * size * size - 1
choices = [L, U, A, D, R, F]
start   = (1, 1, 1)
finish  = (size, size, size)

move_cursor :: Cursor -> Move -> Cursor
move_cursor (x, y, z) L = (x+1, y, z)
move_cursor (x, y, z) R = (x-1, y, z)
move_cursor (x, y, z) U = (x, y+1, z)
move_cursor (x, y, z) D = (x, y-1, z)
move_cursor (x, y, z) F = (x, y, z+1)
move_cursor (x, y, z) A = (x, y, z-1)

test_in_range :: Cursor -> Bool
test_in_range (x, y, z) = bounded x && bounded y && bounded z
    where bounded n = n > 0 && n <= size

test_no_collision :: Cursor -> Trail -> Bool
test_no_collision = Set.notMember

single_step :: [State] -> [State]
single_step states =
    do (path, cursor, trail) <- states
       guard (cursor /= finish)
       next <- choices
       let new_path   = next:path
           new_cursor = move_cursor cursor next
           new_trail  = Set.insert new_cursor trail
       guard (test_in_range new_cursor)
       guard (test_no_collision new_cursor trail)
       return (new_path, new_cursor, new_trail)

solutions :: [[Move]]
solutions = map keep_path $ foldr ($) initial all_steps
    where initial = [([], start, Set.singleton start)]
          all_steps = replicate count single_step
          keep_path (path, _, _) = path

main :: IO ()
main = mapM_ print solutions