{--
Universal Turing machine implementation, released under ISC/BSD license:
Copyright (c) 2009, Alex Stangl <alex@stangl.us>

Permission to use, copy, modify, and/or distribute this software for any
purpose with or without fee is hereby granted, provided that the above
copyright notice and this permission notice appear in all copies.

THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.

This implementation, written on 01/18/2009 is an attempt to write a Haskell
implementation of a Universal Turing machine, which takes 5n command-line integer arguments,
each 5-tuple consists of (input state, input symbol, output state, output symbol, direction)
see http://www.mathrix.org/experimentalAIT/TuringMachine.html for full rules and other details.
This is a straightforward implementation; no attempt has been made to make this source code short.
Consistent with the C++ version, though, no error handling is added, to cope with invalid arguments.
--}

import Data.List
import System

-- lTape is tape left of curr position, rTape is tape right of curr position; head of both lists is adjacent to curr position
-- symbol contains input symbol at curr position
-- si, so are input/output state; ci, co input/output symbol; d is tape direction
tm step state symbol lTape rTape (si:ci:so:co:d:xs) rules
    | state == 0                  = [concat $ map show $ reverse lTape ++ (symbol:rTape), show step]
    | si /= state || ci /= symbol = tm step state symbol lTape rTape xs rules
    | d == 1                      = tm (step+1) so (safeHead rTape) (co:lTape) (drop 1 rTape) rules rules
    | d == -1                     = tm (step+1) so (safeHead lTape) (drop 1 lTape) (co:rTape) rules rules
    | d == 0                      = tm (step+1) so co lTape rTape rules rules
    where safeHead [] = 0
          safeHead (x:xs) = x

main = do args <- getArgs
          putStrLn $ unlines $ tm 0 1 0 [] [] (map read args) (map read args)