Mine Cart Madness

Advent of Code 2018 Day 13

Try the simulator using your puzzle input!

Task: Solve for X where...

Part 1

X = the location of the first crash as format X,Y

Part 2

X = the location of the last cart (as format X,Y) at the end of the first tick where it is the only cart left

Example input

/->-\        
|   |  /----\
| /-+--+-\  |
| | |  | v  |
\-+-/  \-+--/
  \------/   

It represents:

• Carts being pushed on rudimentary tracks
• - and | are straight paths
• / and \ are curves
• + are intersections of two perpendicular paths
• >,<,^,v are carts with the point end indicating the direction they face

Part 1

1. I'm so excited to simulate this puzzle!
2. Lots of details. Lots of state to manage.
3. Considering all the symbols a cart could encounter on it's turn
4. Parsing the input to create the track map and determine cart positions
5. The data structure and attributes for each orientation
6. Re-ordering the carts and placing on a copy of the tracks
7. A written description of my main cart-moving loop

I'm so excited to simulate this puzzle!

• Carts moving along a track? That's fun to watch!
• I hope I can figure this one out, unlike Day 24
• I won't make a simulator unless I can get it to work on at least my puzzle input

Lots of details. Lots of state to manage.

Details from the initial map

• The positions and orientations of all carts on the tracks
• The straight paths, curves and intersections on the tracks
• The track under each cart is a straight path matching the direction the cart is facing

Details from the instructions

• The cycle of turns carts follow when encountering an intersection is: 1. left, 2. straight, 3. right, go to 1
• The cycle of moves the carts adhere to is called a tick and follows a top-left to bottom-right z-shape pattern, as depicted below:

Start->
------>
------>
--->End

State to manage

The map of the tracks:

• The coordinates and types of all valid track tiles

Each cart:

• Orientation
• Moved queued for next intersection
• Position as X,Y

How to re-orient at curves:

• For each curve type: the next orientation for each current orientation

How to move:

• For each orientation: a relative position one step away in the appropriate direction

How to re-orient at intersections:

• For each orientation: the next orientation for each of the three possible new orientations: left, straight or right

Considering all the symbols a cart could encounter on it's turn

When a cart's turn in a tick begins, it must assess the state of the track one step ahead.

The symbols could be any of the following:

• —: Move left or right and don't re-orient
• |: Move up or down and don't re-orient
• \: Move one step in the current direction and re-orient
• /: Move one step in the current direction and re-orient
• +: Move one step in the current direction and re-orient
• ^v<>: Report first collision since cart is about to hit another cart

Parsing the input to create the track map and determine cart positions

Split the input at each newline character into an array of strings
  Split each string at each character into an array of characters
Create an empty array, carts

For each array of characters
  For each character
    If the character is one of the four cart symbols
      Add to carts a new cart object with three key-value pairs:
        1. Orientation - the character
        2. Position - the cell's columns and row as a two-element array
        3. Next rotation - 0 (indicating the first of three possible moves)
      Update the cell's value in carts with the appropriate track symbol, '-' or '|'

Using the example input, I generate this list of carts:

[
  { 
    orientation: '>', 
    position: [ 2, 0 ], 
    next_rotation: 0 
  },
  { 
    orientation: 'v', 
    position: [ 9, 3 ], 
    next_rotation: 0
  }
]

The data structure and attributes for each orientation

For each orientation:

• The relative coordinates of the next move
• The three orientations mapped to the cycle at each intersection
• The symbol to change to at each curve type

let legend = {
  '^': {
    move: [0,-1],
    plus: ['<','^','>'],
    curves: {
      '/': '>',
      '\\': '<'
    }
  },
  'v': {
    move: [0, 1],
    plus: ['>','v','<'],
    curves: {
      '/': '<',
      '\\': '>'
    }
  },
  '<': {
    move: [-1,0],
    plus: ['v','<','^'],
    curves: {
      '/': 'v',
      '\\': '^'
    }
  },
  '>': {
    move: [ 1,0],
    plus: ['^','>','v'],
    curves: {
      '/': '^',
      '\\': 'v'
    }
  }
}

The next big question: will this hold up as I build out the algorithm for each cart's turn in the tick?

I'm anxious to find out. Time for more programming!

Re-ordering the carts and placing on a copy of the tracks

At the start of each tick:

• I must determine the order in which the carts will take their turns
• I must create a copy of the map so I can temporarily place carts on it, preserving a version of the map with no carts on it for use in each tick

Ordering the carts:

• Sort the carts in ascending order by row
• If in the same row, sort in ascending order by column
• Such that carts in the upper (smaller value) rows come before lower (larger value) rows
• And carts in the left-most columns come before right-most columns

With this as a cart object:

{ 
    orientation: '>', 
    position: [ 2, 0 ] // X,Y , 
    next_rotation: 0 
  },

carts.sort((a,b) => a.position[1] - b.position[1] || a.position[0] - b.position[0])

Copying the map:

clone = tracks.map(track => track.slice())

A written description of my main cart-moving loop

Function tick():
Sort the carts into the proper turn-taking order
For each cart
  Determine the position and symbol of the track one step away
  Determine whether that position matches the position of any other carts
    If the position is a match
      Add a property to the current cart that stores the position of the collision as X,Y
      Set a variable, bang, as the same position
  Depending on the symbol of the track one step away:
    Update some variation of the following properties of the current cart:
      - Position (all cases)
      - Orientation ('+', '\', '/')
      - Next Rotation ('+')
  Return the updated object for the current cart

Run tick() as long as no carts have a collision property

As soon as one does:
  Return that cart's collision property's associated value

The results:

• I ran it on the example input. It generated the correct answer!
• I ran it on my puzzle input. It generated the correct answer, again!

Now, I had to see it in action.

Building the simulator

• This was a pretty simple one to build since my algorithm was already set up to render the tracks after each iteration
• Once a few oversights in my copy-pasting, misnaming and character escaping were worked out, I got to watch!

The animation below only shows the portion of the track where the first collision occurs.

Try the simulator for Part 1 using your puzzle input!

Part 2

1. New example input
2. This reminds me of Giant Squid
3. Modifying my algorithm from Part 1

New example input

/>-<\  
|   |  
| /<+-\
| | | v
\>+</ |
  |   ^
  \<->/  

This reminds me of Giant Squid

• 2021 Day 4's puzzle featured several Bingo! boards
• Part 1 asked for the first completed Bingo! board
• Part 2 asked for the last completed Bingo! board
• In this case, I'm searching for collisions

Modifying my algorithm from Part 1

• Since I'll need to remove carts, I need to give each one an ID. I'll assign one when each cart is created by using the length of the carts array at that moment
• I should no longer permanently modify the tracks with an X to mark collisions
• When I sense a collision, I must mark both carts as about to collide, so that I can later find them and delete them from the array of carts
• My main loop should run only as long as the carts array contains more than one cart
• After each tick, I must check for carts marked as collided and remove them from the array of carts
• Lastly, I must return the position of the only remaining cart

The results:

• It worked on the new example puzzle input!
• It worked on my puzzle input!

Updating the simulator

• It took some troubleshooting due to copy-paste oversights
• But I eventually got it to work
• It was fun to watch the carts move around and disappear when colliding

Try the simulator using your puzzle input!

I did it!!

• I solved both parts!
• I made a simulator that accounts for both parts!

I'm so glad I took the time to fully think through the data structure and logic for this puzzle.

I earned both gold stars.

And I got to celebrate by watching my simulator in action!