Day 13 puts us just over halfway! Hopefully, you're sticking with it and able to keep up. If not, we've got a weekend coming up. 🎅
Today, we're predicting minecart crashes! You heard me right: the plants from yesterday have their own minecart infrastructure. And these minecarts are not well managed. We'll be parsing some pretty crazy ASCII art inputs and simulating these carts to figure out where they might run into issues.
There's a lot of moving pieces to this one. Good luck!
Top comments (15)
A solution in python in which I have represented the tracks as an array of transformation functions on carts.
Really interesting how yours is very much the same concept as mine but Pythonic rather than Kotlin-ic!
One idea I want to explore (I don't know when) is to substitute most of the functions with dictionaries and func calls by lookups. I think this way I can represent the movements in a way similar to a rule system.
I like the declarative section at the beginning (and used a similar one in my solution below).
Half way, and we have a puzzle that just needs cranked through. There's no trick that particularly helps - just read the input into a big 2D array, turn the cart symbols into little models of the carts that can maintain the necessary information about the next turn, etc., and run the ticks.
It can be done without a bunch of ugly and error-prone mutable state though. First a model:
Loading the input data
The input text lines are just mapped to
CharArrays. Then I use a pair of
foldIndexed()calls run over the input on both axes and find the locations of the carts. A starting model for each cart is built here.
Finally I replace the cart positions with track characters. I could have left them in place and given the original characters the same semantics, I guess. No big deal.
Cart movement is broken into a bunch of little functions, each of which should be pretty easy to understand.
The interesting one is
Plan.adjust()which takes the current track character at a cart's position and builds a new plan for the cart. On intersections it applies turning logic, on curves it changes direction, etc. In some cases the plan doesn't change.
Moving a cart is a matter of determining the new plan based on the current track character, then executing the plan.
Scanning for the order to move the carts makes use of a nice Kotlin library feature of chainable comparators:
Each tick is implemented by moving the carts in scan order and checking for collisions. One tricky part of this is that the carts move one at a time, giving a bunch of inter-tick mini-states. So the initial state of the fold is the previous state's carts, and on each iteration of the fold one cart is replaced by its updated version. This ensures the correct collision comparisons are made.
A whole new model is built each time.
Running the simulation makes use of an infinite sequence of states I call the timeline:
Just drop states from this sequence until a collision is detected, then find the crashed cart:
A proper part 2 today, which introduced a new tricky problem. Removing the carts the instant they crash introduces some more complexity to those inter-tick mini-states. We're folding over the carts in scan order, but our fold accumulator is the updated list of carts. These can become out of sync as a collision can happen before the scan order reaches a certain cart, removing it from the simulation. I solved this in a kind-of hacky way by skipping any cart in the fold that has been removed from the list.
The part 2 simulation is similar to part 1. Drop states until the end criteria is met, then extract the information required from the next state.
This is one of those problems that you just gotta grind through, I guess.
Surprisingly, this is the first one where, the first time it compiled, I got the right answer. Of course, getting it to compile took a few tries-- I'm using AoC to learn a new language --but once the syntax issues were ironed out, I just had the solution ready to go.
Only really interesting things are that on the beginning of each tick, I can do
which sorts the array of carts first by
y, then by
x. Then I can just iterate straight through that array and have the carts in correct order.
I implemented collision checking like so
and sadly have to call it once per cart, per tick. If I only called this at the beginning or end of each tick, then two carts like so:
would actually end up switching spots, and I'd never notice they overlapped.
For part 2, I replaced my
Essentially, instead of merely detecting if there is a collision, this method filters out any carts that have a position that is equal. (Now that I type that out, I realize I could have just called
I'm still calling this once per cart per tick, which is so poorly inefficient that it makes me wince, but there are so few carts in the input that it rarely matters.
Full code here: github.com/MustafaHaddara/advent-o... and github.com/MustafaHaddara/advent-o...
Oh, and last lesson learned: I wrote a
print_board()function that didn't actually print the carts! This is really really really stupid...it made that function almost entirely useless.
I had to do other things since Wednesday and couldn't focus on AoC until yesterday night but hopefully I will catch up soon!
I created a graph for all the map squares, and a list of carts that move around these squares.
Here's my solutions:
This one seemed like the hardest one so far on first reading, but I ended up grasping it better than a couple of the previous puzzles. I ended up using a
dequeto make the turning directions easier to muck with:
I remember something similar form last years AoC :)
Today most of my bugs were from me not knowing PHP (I'm using AoC to learn it). After JS I just keep forgetting that arrays are passed by value and you need to use pointer (
&) to pass variable by reference.
Perl solution. Most of the decisions are represented by the hash tables at the beginning of the code:
In part 2, I just replaced the code that printed the collision with a new one that removes the two carts involved.
Alright, now I'm making up ground on the ones I got behind on. I actually really enjoyed this one! It was fun tuning things to be readable and easy to follow.
I promise I'll post my code eventually, I spent too long working on this animation of part1: gfycat.com/EasygoingMassiveHog
Oof, I played with this too long.
Here's it all.