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
- I'm so excited to simulate this puzzle!
- Lots of details. Lots of state to manage.
- Considering all the symbols a cart could encounter on it's turn
- Parsing the input to create the track map and determine cart positions
- The data structure and attributes for each orientation
- Re-ordering the carts and placing on a copy of the tracks
- 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
- New example input
- This reminds me of Giant Squid
- 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!
Top comments (0)