forward = (1, 0, 0)
left = (0, 0, 1)
right = (0, 0, -1)
(x, y, a) <+> (dx, dy, da) =
case a of
0 -> (x + dx, y + dy, a')
1 -> (x - dy, y + dx, a')
2 -> (x - dx, y - dy, a')
3 -> (x + dy, y - dx, a')
where a' = (a + da) `mod` 4
dragons n = reverse $ take (n + 1) $ iterate f (0, (0, 0, 0), (0, 0, 0))
where f (l, a, b) = (2 * l + 1,
(a <+> right <+> b <+> forward <+> right),
(left <+> forward <+> a <+> left <+> b))
position steps n = loop steps (0, 0, 1) "Fa" n (dragons n)
where loop 0 pos _ _ _ = pos
loop steps pos (x:xs) n ds@((l, a, b):ds') =
case x of
'F' -> loop (steps - 1) (pos <+> forward) xs n ds
'L' -> loop steps (pos <+> left) xs n ds
'R' -> loop steps (pos <+> right) xs n ds
_ | steps < l -> loop steps pos (expand x) (n - 1) ds'
| x == 'a' -> loop (steps - l) (pos <+> a) xs n ds
| x == 'b' -> loop (steps - l) (pos <+> b) xs n ds
expand 'a' = "aRbFR"
expand 'b' = "LFaLb"
answer = let (x, y, a) = position (10^12) 50 in (x, y)