Day 13: Mine Cart Madness

For Day 13 we get to crash mine carts until there is only one remaining. As part of the original solution, if the terminal size is able to contain all the tracks, the progress of the mine are displayed. While it would be possible to pipe that output into the excellent asciinema Terminal Session Recorder it seemed like more fun to write an asciinema Nim library that can ‘record’ and output asciicast v2 files. The result is below, a small, and short animation!

Test Input

If you found that exciting, scroll down the page to find the puzzle input, which plays for roughly 17 exhilarating minutes.

Lookup Tables

The most interesting aspect of the approach to the solution for Day 10 is that it is almost entirely lookup table driven. That is, it does not consist of a series of if statements, e.g. for finding the tile a cart would move to:

  if cart = '^':
    new_tile = map[y - 1][x]
  elif cart = '>':
    new_tile = map[y][x + 1]
  ...

Instead the following const block defines various rules that are used in the main move loop to move the cart depending on the conditions of the cart and the track it is on:

const
  carts = "<^>v"
  crashed_cart = 'X'
  cart_directions = [(x: -1, y: 0), (x: 0, y: -1), (x: 1, y: 0), (x: 0, y: 1)]
  cart_tracks = "-|-|"
  cart_turn_multiplier = [1, -1, 1, -1]
  track_turn_multiplier = [-1, 1]
  directions = "LSR"
  directions_turn = [-1, 0, 1]
  straight_tracks = "|-"
  intersection_tracks = "+"
  turning_tracks = "/\\"
  empty = char(0)

Using the above lookup ‘tables’, finding the new tile a cart moves to becomes:

  let movement = cart_directions[carts.find(tile.cart)]
  let new_tile = map[y + movement.y][x + movement.x]

Size Matters

It turns out that naively outputting the animation for the test input is fine, it results in a file that is 3345 bytes… and it turns out that this is not fine for the actual puzzle input, which results in a file that is just shy of 240MB.

The naive approach in this case, is, for each frame: clear the screen then render the entire screen. This approach generates a lot of data (over 23k bytes) for each frame when animating the puzzle input, which is 150x150 characters; and with over 10000 frames before there is only one cart remaining we get a file size that the web asciinema player struggles to handle. While it obviously takes a long time to load the file, seeking (since there are no key-frames in asciiicasts) is a painful affair.

Optimising

I used a couple of strategies to optimise the output, compared to the naive approach (-d:inefficient):

1. Only render the tracks once and make all subsequent frames render only the individual characters that changed
2. As the output is colourised, output each colour as a separate pass instead of all positions sorted left-to-right, top-to-bottom (-d:sorted)
3. Use shorter cursor movement sequences where possible (turned off using -d:not_optimised)

Moving away from the naive approach predictably had a large effect. The gain from the other optimisations is fairly marginal.

Puzzle Input

Did you find the remaining cart? ;)