U 1
L 1
U 2
R 1
U 2
R 2
L 1
R 1
L 1
D 1
L 2
D 2
U 1
R 2
D 1
L 1
D 2
U 2
R 2
D 1
R 1
D 1
U 2
D 2
U 1
R 1
L 1
D 2
R 2
D 1
R 1
D 2
L 1
D 2
R 1
U 2
R 1
L 1
U 2
R 1
L 2
U 1
R 2
D 2
R 2
D 1
L 2
U 1
R 1
L 1
U 2
L 1
U 2
R 2
D 1
U 2
D 1
R 1
D 2
L 2
U 2
L 1
R 1
D 1
U 2
R 1
L 2
U 2
L 2
U 1
L 1
D 1
U 2
D 1
R 1
L 1
D 1
L 2
D 2
L 2
R 1
U 2
L 2
U 2
D 2
L 2
D 2
U 2
R 2
U 2
R 1
D 2
R 2
L 2
D 1
U 1
L 2
R 1
U 1
L 1
D 2
U 2
D 2
L 1
R 1
L 1
U 1
D 2
U 1
D 1
R 2
U 2
R 2
D 1
U 1
L 3
D 3
R 2
L 2
R 2
L 2
D 2
L 3
D 1
L 3
R 3
L 3
U 3
D 3
U 2
L 2
D 1
U 2
R 1
D 1
R 2
L 2
U 1
R 3
D 1
R 2
L 1
U 2
D 1
U 2
R 2
U 1
L 2
U 2
L 1
D 1
L 2
D 3
L 3
D 1
R 3
U 3
R 3
D 1
L 1
R 3
L 3
D 2
U 2
L 3
D 1
L 1
U 3
L 1
D 3
U 1
R 1
L 3
R 2
U 3
L 3
R 1
L 1
D 3
L 2
D 1
U 3
D 1
L 3
U 2
R 3
U 2
L 1
D 2
U 3
D 2
R 1
U 3
R 2
L 3
D 1
R 1
L 2
D 1
U 1
L 3
D 2
U 2
R 1
L 3
R 3
U 1
L 2
D 2
L 1
U 3
D 2
U 1
R 3
L 2
R 2
L 2
R 1
D 1
U 2
L 2
R 3
L 3
U 4
R 3
D 3
R 1
D 4
R 1
D 4
R 1
D 1
R 3
L 4
D 1
L 1
U 1
D 3
U 4
D 2
L 3
R 1
D 3
U 4
D 4
L 2
R 3
U 2
L 1
D 2
U 2
L 2
R 2
D 4
R 4
L 1
R 3
U 2
D 1
U 3
L 2
D 4
U 1
L 1
D 1
U 3
R 4
L 3
R 2
U 2
R 1
U 3
D 1
U 3
L 2
U 2
L 3
D 1
R 3
L 1
U 4
R 1
L 2
R 1
D 2
R 4
L 1
D 1
L 3
U 3
D 2
U 4
L 1
R 4
L 3
D 1
U 2
L 4
D 2
L 3
R 3
L 3
D 2
U 2
L 4
D 4
U 3
L 2
R 1
U 4
D 3
L 4
D 2
L 3
D 2
L 2
U 4
D 4
R 4
D 2
L 1
U 4
D 4
L 1
R 3
L 1
D 1
L 3
D 3
R 4
L 1
R 3
U 3
R 4
L 1
U 3
R 2
U 1
L 5
R 5
D 2
R 1
U 5
L 2
R 1
U 3
D 1
U 4
L 2
U 4
L 2
R 3
U 2
R 2
U 1
L 3
U 2
D 5
R 3
U 1
R 2
U 4
L 1
D 5
R 4
U 3
D 1
U 1
R 2
U 4
R 1
L 3
D 4
U 2
R 1
L 1
R 3
L 5
R 3
L 5
D 1
R 3
D 4
U 2
D 3
L 3
D 2
L 1
R 1
D 4
L 5
U 5
D 1
L 3
R 5
D 5
U 2
L 5
U 1
L 4
D 5
R 5
U 4
D 2
L 1
D 3
L 5
R 3
D 3
L 2
U 5
R 1
L 5
D 5
R 3
L 1
U 3
D 5
R 1
U 1
R 4
L 2
U 3
R 2
D 5
L 1
U 1
L 3
R 3
D 5
U 5
D 4
R 2
L 1
U 3
L 2
R 1
L 1
R 3
D 3
U 1
L 4
D 2
U 4
L 6
D 6
U 2
R 3
U 1
D 5
L 1
D 6
U 2
R 2
L 1
R 4
D 4
L 1
U 4
L 5
R 5
L 2
U 5
R 5
U 1
D 3
L 5
D 1
R 5
L 6
U 3
D 3
U 6
R 4
L 6
R 5
D 5
R 3
L 5
D 1
L 2
R 1
L 4
U 5
R 2
U 3
D 1
L 4
R 3
L 1
R 3
U 3
R 3
L 2
D 2
L 1
R 4
D 1
L 6
D 1
R 1
U 6
L 5
R 3
L 3
D 5
L 1
D 6
R 2
D 3
U 6
D 2
U 5
L 5
D 1
R 4
D 2
U 3
D 5
L 2
D 2
U 4
R 2
L 2
D 5
L 2
R 2
D 5
R 6
D 5
L 1
U 2
R 1
D 4
L 2
R 1
D 4
L 2
R 1
U 5
R 1
L 6
U 4
R 6
U 3
L 5
U 2
R 5
D 2
U 6
D 2
U 6
L 6
U 6
R 2
U 4
D 3
U 6
L 7
R 7
L 7
R 4
L 7
R 1
L 4
R 4
L 2
D 5
U 4
D 2
R 1
L 5
U 2
R 2
U 3
L 6
U 4
D 3
U 5
R 1
U 3
L 2
D 6
L 6
U 3
L 1
D 1
U 1
L 1
D 7
R 1
U 7
R 3
D 7
R 6
L 1
R 5
L 1
D 6
L 1
D 4
L 1
R 3
D 5
U 4
D 4
U 1
D 6
L 4
D 7
R 4
L 2
U 5
R 1
D 2
L 3
R 6
L 1
D 4
R 7
U 4
D 7
L 3
U 4
D 2
R 6
D 3
R 2
L 4
D 2
R 1
L 5
U 1
R 1
U 3
R 6
D 6
R 5
L 5
R 1
U 5
L 5
D 6
L 1
D 1
L 5
U 4
D 3
R 6
U 2
R 3
D 1
L 4
R 3
L 7
R 3
U 1
D 5
L 6
R 7
D 3
L 7
D 5
L 5
D 4
L 1
D 7
L 7
R 5
L 3
D 4
L 6
R 6
U 1
R 3
D 1
L 4
U 7
L 2
R 8
D 8
R 3
L 7
D 2
R 1
L 4
U 4
L 3
D 2
L 4
U 1
R 3
L 1
D 7
R 2
L 4
U 3
L 2
U 6
L 4
R 2
D 2
R 4
U 3
D 5
U 7
R 2
L 3
D 4
U 5
L 5
U 5
D 8
R 3
L 7
U 1
L 8
U 2
D 3
U 1
L 5
D 8
L 2
D 4
U 3
R 4
U 1
R 5
L 8
R 7
U 7
L 5
U 6
D 7
U 1
R 3
U 8
D 6
L 5
R 5
L 2
U 3
D 3
R 5
D 7
R 2
D 8
L 3
U 3
R 7
D 5
U 7
L 7
U 1
R 1
L 6
R 3
L 4
U 2
R 1
L 3
U 6
R 6
D 5
U 2
D 7
U 5
R 5
D 2
R 5
D 7
U 8
D 6
U 8
R 4
D 2
U 1
L 3
U 5
D 7
L 4
R 1
U 7
D 1
U 6
D 3
L 6
U 9
L 9
U 3
L 8
D 9
U 7
D 3
U 8
L 6
D 8
U 3
D 2
L 7
U 2
L 2
R 8
D 1
L 2
R 5
U 8
R 7
L 9
R 9
U 3
D 9
L 2
D 6
L 2
R 3
D 2
U 9
D 6
U 7
D 8
U 9
R 4
D 6
U 6
L 6
D 6
L 4
U 1
D 3
R 3
D 1
R 1
D 9
U 6
R 1
U 4
D 9
L 5
U 4
D 5
U 8
L 2
D 5
L 2
R 4
D 7
U 3
L 5
R 6
D 3
U 5
L 4
U 4
D 8
R 4
D 5
L 1
D 2
U 6
D 4
L 6
U 4
L 9
R 1
D 2
L 5
U 6
R 4
U 9
D 6
R 8
U 6
L 9
R 4
D 3
R 3
U 7
L 3
R 1
L 8
U 7
D 4
L 8
U 5
D 4
R 7
U 5
L 5
D 6
U 4
R 6
D 4
U 10
L 10
U 8
L 9
D 2
U 1
L 1
D 7
U 6
R 5
D 7
R 7
L 6
R 1
D 5
R 6
L 2
R 9
U 6
L 2
R 8
D 5
L 7
R 10
L 4
R 6
D 1
U 1
L 3
D 3
R 7
U 1
L 10
D 3
L 1
U 3
D 2
U 9
D 6
R 8
D 6
L 2
U 8
D 10
U 8
L 4
D 2
U 1
R 3
L 7
U 9
R 9
U 7
L 9
U 1
D 9
U 6
R 7
L 5
R 7
U 6
D 2
L 5
U 7
D 3
L 1
R 3
L 1
D 10
L 10
D 6
U 7
L 1
R 2
U 2
L 9
R 9
U 5
R 2
D 10
U 10
D 6
L 8
U 4
L 6
U 8
D 8
U 1
L 4
D 10
U 6
D 6
L 10
U 1
D 3
L 10
R 2
U 1
D 1
L 8
D 10
L 8
D 4
L 1
D 3
R 4
D 1
R 8
D 9
U 6
D 3
U 3
L 8
U 4
R 10
D 9
U 4
R 6
L 6
D 1
R 8
D 5
L 10
D 7
U 3
L 1
D 5
U 8
D 3
R 11
U 2
L 10
D 1
R 9
U 5
R 11
U 1
D 5
U 8
R 10
U 6
L 6
R 6
U 10
R 1
L 6
R 8
L 6
D 1
L 5
U 5
R 11
U 4
R 9
U 10
R 9
L 3
U 6
R 7
L 10
U 10
L 9
R 4
U 4
R 1
U 6
L 9
R 5
L 9
D 10
U 10
R 3
D 11
R 10
L 2
R 11
L 6
U 1
R 8
D 1
U 4
R 5
D 4
L 5
U 10
R 6
D 6
U 5
D 2
L 2
D 11
R 3
U 11
L 11
U 1
R 9
U 1
D 2
U 5
R 11
D 8
L 9
D 6
L 8
U 7
L 9
U 11
D 3
L 1
U 11
L 5
D 7
L 1
U 10
L 10
D 8
R 7
D 8
U 11
R 12
L 10
U 12
D 5
R 7
U 11
D 12
U 7
L 12
D 7
L 10
U 5
D 4
R 5
D 2
R 3
U 3
L 12
D 9
L 8
D 10
R 9
U 10
R 5
L 4
U 1
D 5
L 8
U 3
R 11
L 4
D 6
L 11
R 11
U 2
R 2
D 1
L 7
U 12
L 12
R 8
U 12
L 8
U 6
R 10
D 2
L 7
U 10
L 9
D 12
U 4
R 7
U 10
L 10
R 3
U 2
L 6
U 12
D 4
R 7
L 5
R 7
D 9
U 1
D 2
L 12
R 11
D 2
R 4
D 5
R 8
L 2
R 8
L 8
U 8
L 1
U 2
R 1
D 1
U 6
L 10
R 12
D 3
U 1
D 10
U 1
R 2
U 12
R 8
U 11
R 11
D 9
L 4
R 11
L 12
U 7
L 1
U 10
R 9
L 3
U 12
L 12
D 6
R 10
D 11
R 3
D 1
U 10
D 3
R 10
D 4
R 8
L 2
R 6
U 8
R 10
U 5
L 9
R 2
D 10
U 1
D 7
R 1
D 13
R 12
D 10
R 11
L 11
U 13
L 2
D 7
U 10
D 2
R 12
U 13
L 8
D 10
R 9
D 6
U 9
L 3
R 5
L 4
U 10
R 9
U 9
D 8
R 12
L 9
D 11
U 8
R 8
D 3
U 9
D 7
U 8
R 1
U 8
L 12
U 13
L 8
U 4
D 7
U 12
L 8
D 11
U 13
L 8
U 9
L 1
R 13
L 10
R 1
L 4
R 9
L 8
R 13
L 5
U 9
D 10
L 2
R 10
L 5
D 1
L 2
D 6
U 4
L 3
U 11
L 3
R 7
U 5
D 10
U 3
D 13
U 11
R 1
U 11
R 4
L 3
U 11
R 11
L 12
R 13
U 10
R 7
L 3
U 3
R 10
U 4
R 4
L 10
R 10
D 8
L 11
D 8
R 8
U 2
R 2
U 13
L 3
D 1
L 11
R 7
U 1
L 6
U 8
R 4
L 12
U 1
L 4
U 14
D 6
R 10
L 12
D 6
R 5
U 6
L 4
D 4
R 12
U 6
R 1
U 4
L 3
U 1
L 4
D 1
U 8
L 9
D 13
U 12
R 2
D 12
R 4
U 8
R 14
U 3
L 1
D 1
U 10
L 6
U 2
L 8
D 5
R 7
U 10
R 2
U 2
R 2
L 7
U 4
R 3
U 3
L 8
D 13
R 12
L 8
D 11
U 7
L 13
D 11
U 13
D 2
L 1
R 4
L 8
R 11
L 4
R 4
L 2
D 3
R 10
D 14
R 8
L 6
D 2
R 4
L 11
D 5
U 9
L 9
D 8
R 3
U 11
R 5
U 6
L 2
D 7
R 6
D 13
R 6
U 14
L 14
R 9
D 8
U 3
R 11
D 13
R 14
L 3
U 6
D 7
R 13
L 7
R 12
D 12
R 12
U 12
R 8
L 1
U 7
R 10
U 7
L 2
D 12
U 8
D 14
U 6
D 15
R 2
U 6
L 14
U 15
R 10
U 4
R 8
D 13
R 5
D 15
U 9
R 2
U 15
R 3
U 6
D 14
L 6
D 13
R 13
L 7
D 15
U 12
L 4
R 7
D 12
U 15
D 12
R 14
U 6
L 9
D 8
L 4
R 13
L 13
D 3
L 12
D 12
U 5
D 15
L 1
U 14
L 7
U 4
L 11
U 11
L 12
R 6
D 1
L 1
U 6
R 9
U 10
L 12
R 6
U 15
D 5
L 9
D 5
L 13
U 11
D 12
R 3
U 2
R 5
D 7
L 9
D 8
R 8
L 11
D 7
R 3
D 14
L 1
R 15
L 1
U 2
L 9
R 7
U 2
R 13
U 6
R 3
L 6
R 15
L 2
D 15
L 2
R 14
L 12
R 14
D 6
L 4
R 1
L 2
U 10
D 4
U 8
R 3
D 8
U 12
L 3
R 12
L 15
R 8
L 2
D 11
U 3
L 1
D 12
L 8
U 9
L 13
U 2
L 13
U 7
L 6
D 12
U 15
L 7
U 1
D 6
R 15
L 3
U 10
R 1
U 4
R 2
U 3
R 3
L 13
R 16
D 1
L 2
U 9
L 3
D 6
L 15
D 11
L 7
U 11
L 3
U 1
L 15
R 5
U 14
L 8
R 16
D 8
U 13
R 4
U 6
L 4
R 12
L 12
U 13
D 5
R 5
L 13
D 15
R 10
D 8
U 12
R 6
L 5
D 3
U 4
L 6
R 3
L 6
D 9
U 4
L 5
R 3
D 16
R 2
U 16
L 9
U 12
R 5
L 14
D 14
R 15
D 6
L 3
D 6
U 9
D 11
L 4
D 2
L 9
D 16
L 7
R 1
L 16
D 16
U 16
R 1
U 13
D 8
R 11
L 2
R 13
D 7
L 14
R 7
U 8
R 5
L 13
R 3
U 13
R 14
U 15
R 2
D 5
R 16
U 15
D 10
U 4
L 16
U 3
D 8
U 17
L 17
R 17
U 6
D 16
U 3
R 1
L 16
U 6
R 17
L 15
D 16
R 11
D 17
L 10
R 11
U 2
D 11
L 3
R 12
U 15
R 10
D 14
U 2
R 12
D 1
U 13
D 15
U 16
L 3
U 10
D 16
U 4
D 3
R 5
U 12
R 17
D 5
R 9
U 13
R 12
L 4
D 8
U 1
D 16
R 7
D 9
U 14
D 5
L 5
U 4
L 5
R 8
L 3
D 5
L 3
R 12
U 7
R 6
D 2
R 4
D 11
L 15
R 2
U 9
L 12
R 17
L 13
U 7
R 1
D 16
U 9
R 17
D 2
L 17
D 10
R 16
L 9
D 5
R 7
D 14
L 10
U 12
L 14
R 7
D 6
R 10
D 9
R 2
L 1
R 3
U 3
D 11
L 16
D 6
R 12
U 9
D 3
R 11
D 16
L 4
R 5
L 11
R 8
D 14
R 13
U 8
D 16
L 5
R 12
U 9
D 18
L 10
R 16
L 18
D 7
L 6
U 6
R 10
L 9
R 3
D 16
R 5
D 5
R 6
D 15
U 15
L 14
D 11
R 12
D 7
R 18
D 10
U 1
D 1
U 6
D 7
U 12
D 3
L 7
U 15
L 8
R 11
L 14
D 5
U 12
R 8
D 2
U 7
D 12
L 15
D 2
U 14
D 11
U 2
D 18
R 16
U 2
D 1
R 16
D 15
R 17
D 13
L 13
U 10
L 11
U 6
R 5
D 14
R 7
L 5
R 14
D 15
R 4
L 9
D 11
L 4
R 9
U 12
L 5
D 10
R 1
D 5
R 1
L 16
D 12
L 8
U 1
D 9
U 14
L 3
R 11
D 4
L 5
R 17
D 1
L 12
R 4
L 15
R 18
U 7
D 4
R 3
U 15
R 10
L 10
U 16
R 15
L 12
D 11
R 13
D 2
R 12
U 17
R 14
L 8
U 1
L 16
D 11
R 13
D 19
U 5
D 19
L 10
R 18
D 8
R 1
L 10
D 6
U 1
L 14
R 13
L 14
U 9
D 6
L 19
U 18
L 6
R 13
D 3
U 8
R 17
U 14
L 10
R 1
L 9
R 3
U 14
R 6
L 5
D 8
R 15
L 12
R 13
U 4
R 1
L 10
U 11
L 3
U 8
R 16
U 1
D 3
U 8
L 1
D 1
L 9
D 2
U 5
L 8
R 1
U 6
L 1
R 13
U 10
D 14
U 2
L 7
R 9
U 1
R 2
L 5
U 17
R 19
L 18
U 19
D 18
L 6
R 15
U 5
R 17
L 9
U 3
L 9
U 10
L 10
R 5
D 14
U 14
R 13
U 16
D 8
L 1
D 15
R 10
D 15
U 9
D 18
L 8
R 8
L 3
U 6
L 12
R 8
D 15
L 17
U 11
R 1
D 2
R 1
U 1
L 10
D 11
U 6
L 10
U 5
R 14

R 5
U 8
L 8
D 3
R 17
D 10
L 25
U 20

module Main where
import Data.Bifunctor (bimap, first, second)
import Data.List
import Data.Char
import Control.Monad.State
import Data.Functor.Identity
import Aoc
main :: IO ()
main = do
  content <- lines <$> input 9
  let moves = parse content
  print $ part1 moves
  print $ part2 moves
  where
    part1 f = length . nub . scanl addPos (0, 0) $ evalState (state headMoves f) Overlapped
    part2 f = length . nub . scanl addPos (0, 0) $ evalState (state headMoves2 f) (replicate 9 Overlapped)
    addPos (x, y) move = (x + (fst $ tailToPos move), y + (snd $ tailToPos move))
    state f = sequence . map f
data TailMovement = TailMove Direction
  | TailStill
  deriving Show
data RelativePosition = Relative Direction
  | Overlapped
  deriving Show
data Direction = NorthWest
  | North
  | NorthEast
  | East
  | SouthEast
  | South
  | SouthWest
  | West
  deriving (Show, Eq, Enum, Bounded)
type RelativeState = RelativePosition
tailToPos :: TailMovement -> (Int, Int)
tailToPos TailStill = (0, 0)
tailToPos (TailMove NorthWest) = (-1, 1)
tailToPos (TailMove North) = (0, 1)
tailToPos (TailMove NorthEast) = (1, 1)
tailToPos (TailMove East) = (1, 0)
tailToPos (TailMove SouthEast) = (1, -1)
tailToPos (TailMove South) = (0, -1)
tailToPos (TailMove SouthWest) = (-1, -1)
tailToPos (TailMove West) = (-1, 0)
compassU :: Direction -> [Direction]
compassU a = go 4 ((fromEnum a + 2) `mod` 8)
  where
    go :: Int -> Int -> [Direction]
    go 0 n = [toEnum n]
    go i n = toEnum n : go (i - 1) ((n + 1) `mod` 8)
compassOpposite :: Direction -> Direction
compassOpposite = toEnum . flip mod 8 . (+4) . fromEnum
side :: Direction -> [Direction]
side a = [toEnum ((fromEnum a - 1) `mod` 8), a, toEnum ((fromEnum a + 1) `mod` 8)]
tailMove :: RelativePosition -> Direction -> (TailMovement, RelativePosition)
tailMove Overlapped b = (TailStill, Relative b)
tailMove (Relative a) b
  | even $ fromEnum b = if a `elem` (compassU $ compassOpposite b)
                          then (TailMove . moveDiagLeft $ oppU b , dleft $ oppU b)
                          else (TailStill, diagRelLeft . side . compassOpposite $ b)
  | a `elem` compassSide = (TailMove a, Relative b)
  | otherwise = (TailStill, left $ compassU b)
  where
    oppU = compassU . compassOpposite
    moveDiagLeft (x:xs) = if x == a then toEnum ((fromEnum a + 1) `mod` 8) else moveDiagMid xs
    moveDiagMid (x:y:z:xs) = if a `elem` [x, y, z] then y else moveDiagRight xs
    moveDiagRight (x:[]) = toEnum ((fromEnum a - 1) `mod` 8)
    diagRelLeft (x:xs) = if x == a then Relative . toEnum $ ((fromEnum a - 2) `mod` 8) else diagRelMid xs
    diagRelMid (x:xs) = if x == a then Overlapped else diagRelRight xs
    diagRelRight (x:[]) = Relative . toEnum $ (fromEnum a + 2) `mod` 8
    compassSide = [toEnum (number - 1), b, toEnum ((number + 1) `mod` 8)]
    number = fromEnum b
    dleft (x:xs) = if x == a then Relative . toEnum $ (fromEnum a + 1) `mod` 8 else dmiddle xs
    dmiddle (x:y:z:xs) = if a `elem` [x, y, z] then Relative a else dright xs
    dright (x:[]) = Relative . toEnum $ (fromEnum a - 1) `mod` 8
    left (x:y:xs) = if x == a || y == a then Relative . toEnum $ (fromEnum a - 1) `mod` 8 else middle xs
    middle (x:xs) = if x == a then Overlapped else right xs
    right (x:y:[]) = Relative . toEnum $ (fromEnum a + 1) `mod` 8
headMoves :: Direction -> StateT RelativeState Identity TailMovement
headMoves dir = do
  rel <- get
  let (tail, newRel) = tailMove rel dir
  put newRel
  pure tail
headMoves2 :: Direction -> StateT [RelativeState] Identity TailMovement
headMoves2 dir = do
  rel <- get
  let hd = head rel
  let firstMove = tailMove hd dir
  let snake = scanl (\b a -> bwah (fst b) a) firstMove (tail rel)
  put . map snd $ snake
  pure . fst . last $ snake
  where
    bwah :: TailMovement -> RelativePosition -> (TailMovement, RelativePosition)
    bwah (TailMove b) a = tailMove a b
    bwah TailStill a = (TailStill, a)
parse :: [String] -> [Direction]
parse = concatMap (uncurry movement . bimap direction (read . drop 1) . break isSpace)
  where
    movement :: Direction -> Int -> [Direction]
    movement dir count = replicate count dir
    direction "R" = East
    direction "L" = West
    direction "U" = North
    direction "D" = South
    direction _ = error "Malformed input"