Turing Machine

anarchy golf - Turing Machine にハマりました。
最終的に通したコードはこんな感じ。空白を削って 168B です。

main = interact $ f "" 0 2 . map words . lines
f s i j m
  | j<2 = s
  | 0<1 = f (take i s ++ a : drop(i+1)s) (max i 0 + b%61) (c%63) m
  where
  [a,b,c] = m!!k!!j
  k
    | i<0 = 1
    | 0<1 = (s++"0")!!i%47
n%i = fromEnum n - i

このコードは、簡単に短くすることができます。
7 行目以降、k を求めるところで、リストの範囲を超えたインデックスが渡されるのを防ぐために場合分けをしてますが、リストの前にも要素を足してしまえば、場合分けは不要。
こんな感じで、160B まで縮みます。

main = interact $ f "" 1 2 . map words . lines
f s i j m
  | j<2 = s
  | 0<1 = f (take(i-1)s ++ a : drop i s) (max i 1 + b%61) (c%63) m
  where
  [a,b,c] = m!!(('0':s++"0")!!i%47)!!j
n%i = fromEnum n - i

ただ残念ながらこのコードは通りません。test #3 で timeout。
プロファイルもとって調べてみたら、(++) のコストがとにかく高くて、(:) で駄目押ししてる感じ。
ぎりぎり 1 秒くらいなので、運がよければ通るかもと 100 回くらい submit（ごめんなさい、ごめんなさい）してみたけど、やっぱり駄目。
あんまり悔しいので、ここにＵＰしときます。
Haskell の time limit を 1.5 秒くらいに‥‥。