13 December 2019 Tagged in: advent of code | haskell

Advent of Code 2019 day 11

Langton's ant, and more Intcode

Advent of Code 2019 day 11

Day 11 was something akin to Langton's ant, a Turing-complete cellular automaton. It was an application of the Intcode interpreter from day 9 but with the interaction/scheduling handler similar to the one from day 7. As promised, no new features are needed in the Intcode interpreter.

It follows the pattern of day 7 closely, with an Ant data type instead of the EncapsulatedMachine from before. I also use a Map of Positions to Colours to keep track of the paint job.

The runAnt manager function follows very closely from before. The ant is run until it blocks, awaiting input. When it blocks, the manager handles any output generated by the ant (painting squares and moveing the ant) and then uses the camera to tell the ant what colour it's standing on. The manager then runs the ant again until it either blocks or terminates.

runAnt :: Ant -> Hull -> Hull
runAnt ant hull = hull''
    where ant' = runAntStep ant
          output = _machineOutput ant'
          hull' = if (null output) then hull else paint hull ant' (output!!0)
          ant'' = if (null output) then ant' else move ant' (output!!1)
          ant''' = camera ant'' hull
          hull'' =  if (_executionState ant' == Terminated)
                    then hull'
                    else runAnt ant''' hull'

The if (null output) ... statements are to catch the case where the ant looks at its current square before issuing any move commands. I assume that the ant always generates exactly two output elements before blocking for input; this is a generous reading of the problem spec, but it happens in practice. Because there are only ever two output items, I don't need to keep track of previous output.

The paint, move and camera functions do what you'd expect.

paint :: Hull -> Ant -> Integer -> Hull
paint hull ant 0 = M.insert (_currentPosition ant) Black hull
paint hull ant 1 = M.insert (_currentPosition ant) White hull

move :: Ant -> Integer -> Ant
move ant angle = ant { _currentDirection = direction', _currentPosition = position' }
    where direction' = turn (_currentDirection ant) angle
          delta = directionDelta direction'
          position' = sumPos delta $ _currentPosition ant

camera :: Ant -> Hull -> Ant
camera ant hull = ant { _currentInput = input' }
    where colour = M.findWithDefault Black (_currentPosition ant) hull
          input = _currentInput ant
          input' = input ++ [colourNum colour]

The only other notable part of the code is the turn procedure, which uses hand-rolled versions of pred and succ to handle turning in circles.

data Direction = North | East | South | West deriving (Show, Eq, Ord, Enum, Bounded)

succW :: (Bounded a, Enum a, Eq a) => a -> a 
succW dir | dir == maxBound = minBound
          | otherwise = succ dir

predW :: (Bounded a, Enum a, Eq a) => a -> a
predW dir | dir == minBound = maxBound
          | otherwise = pred dir

That's about it, really. There are some other utility functions in the code, but nothing terribly exciting.