15 December 2019 ; tagged in: advent of code , haskell

Advent of Code 2019 day 13

Remembering things when the game engine doesn't remind you

Advent of Code 2019 day 13

Day 13 was a day of fiddly detail more than grand challenges.

Part 1

Part 1 was a relatively simple warm-up: run a Intcode machine, read its output, and process it to produce an image of the screen.

The screen was a Map taking Position to Cell:

type Position = (Integer, Integer) -- x, y
data Cell  = Empty | Wall | Block | Paddle | Ball deriving (Show, Eq, Ord)
type Screen = M.Map Position Cell

Building the screen was just splitting the machine's output into chunksOf 3 and folding the chunks into the Screen.

buildScreen :: [Integer] -> Screen
buildScreen output = foldl' addCell M.empty $ chunksOf 3 output

addCell :: Screen -> [Integer] -> Screen
addCell screen [x, y, c] = M.insert (x, y) (cellOf c) screen

cellOf :: Integer -> Cell
cellOf 0 = Empty
cellOf 1 = Wall
cellOf 2 = Block
cellOf 3 = Paddle
cellOf 4 = Ball

Finding the number of blocks was just a combination of M.filter and M.size:

part1 mem = M.size $ M.filter (== Block) screen
    where (_halted, _machine, output) = runProgram [] mem
          (screen, _score) = buildScreen output

Part 2

This was initially daunting. Get a machine to play Breakout? But a little bit of thought resulted in the realisation that all I had to do was keep the one-space paddle below the one-space ball, and the game would play itself. All I had to do was keep track of the the x positions of both the paddle and the ball, and all would be fine.

The tricky part was keeping track of all the detail, especially in light of how the Intcode program only produced output of things that had changed from the previous game step. I was responsible for keeping track of whatever else I needed.

Much like day 7 and day 11, I encapsulated the Intcode machine, and used that to track the machine's state, input and output, and whatever else I wanted.

data Game = Game 
    { _machine :: Machine
    , _executionState :: ExecutionState
    , _currentInput :: [Integer]
    , _machineOutput :: [Integer]
    , _currentScore :: Integer
    , _paddleX :: Integer
    , _ballX :: Integer
    } deriving (Eq)

The game was run with three functions: runGame did the termination detection and loop control. runGameStep does all the processing of the machine output and deciding on the input. runGameMachine runs the Intcode machine.

runGame :: Game -> Game
runGame game0 = game
    where game1 = runGameStep game0
          game = if (_executionState game1 == Terminated)
                 then game1
                 else runGame game1

runGameStep :: Game -> Game
runGameStep game0 = game
    where game1 = runGameMachine game0
          output = _machineOutput game1
          (screen, score) = buildScreen output
          cs = _currentScore game0
          score' = if score > cs then score else cs
          game2 = game1 { _currentScore = score' }
          game = joystick game2 screen

runGameMachine :: Game -> Game
runGameMachine g = g { _machine = machine'
                     , _executionState = halted
                     , _machineOutput = output
                     }
    where   machine = _machine g
            input = _currentInput g
            (halted, machine', output) = runMachine input machine

Note that buildScreen has been modified to return a pair of both the screen updates and any score it finds in the machine's output; runGameStep only update's the Game state's copy of the score if it's higher than the previous one.

joystick picks the joystick direction based on the screen. Again, the Intcode machine only returns the ball and paddle positions when they've changed from the last frame. That means I need to use the last-cached values if new ones aren't present in the Intcode output. This function sets the _executionState from Blocked to Runnable. Finally, it moves the paddle towards the ball and appends this new command to the machine's input.

joystick :: Game -> Screen -> Game
joystick game screen = game {_currentInput = ci ++ [direction], 
                              _paddleX = px, _ballX = bx,
                              _executionState = termination}
  where knownBall = M.filter (== Ball) screen
        bx = if M.null knownBall
             then _ballX game
             else fst $ fst $ M.findMin knownBall
        knownPaddle = M.filter (== Paddle) screen
        px = if M.null knownPaddle
             then _paddleX game
             else fst $ fst $ M.findMin knownPaddle
        termination = if _executionState game == Blocked
                      then Runnable
                      else _executionState game
        ci = _currentInput game
        direction = if bx > px 
                    then 1
                    else if bx < px
                         then -1
                         else 0

I put all this together in the main part2 function, which modifies the Intcode machine, runs it until its Terminated, then returns the last-recorded _currentScore.

part2 mem = _currentScore game
    where mem' = [2] ++ (tail mem)
          game0 = buildGame mem'
          game = runGame game0

Debugging

If you look in the code, you'll see a few other functions: showScreen shows what's happening on the screen, and ghcisetupsets up a game from the input file. These were useful when I was developing, mainly to understand what the Intcode machine was actually returning at each frame.

Code

The full code is available, and on Github.