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


    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.


    The full code is available, and on Github.

    Neil Smith

    Read more posts by this author.