Here’s my take for day 18. I spent some time refactoring the code to extract common parts. I have a “core” machine which contains only the features needed in both parts. Then on top of that I build specific machines for each part. Finally, I have the common executor which runs the machine until it’s done, and spits out its output. It would likely be cleaner if I had turned the core machine into a behaviour, and moved the execute function there, but I already spent too much time on the refactoring, so I left it in this shape.
Although the 2nd part tempts to be solved with two processes, I decided to go for just one. I don’t see any particular benefit of using two of them, while I think that cross-process deadlock detection can only bring problems.
Here’s my day 18. The code in its current state only works for part 2. The gist of part 1 is commented out.
I frustratingly spent hours debugging infinite loops in part 2 that were ultimately caused by treating my receive list as a stack instead of a queue. Ugh…
I also considered two processes, especially since I could use some additional experience with using processes. But in the end I just went with what felt a straight forward solution since I really don’t have that much time these days…
I stared at my code for hours, literally… I checked everything in my logic. I found hints in the net, that jgz needs to be able to handle integers as first argument… I checked and repaired my code, it still didn’t work… I stared another hour at my code, before I accidentally realized during a rewrite from nearly scratch, that I missed to convert the integer to an integer during parsing, but made it an atom, such that I checked for the value of register :"1"…
Now everything is fine, and I will submit my code to the repository as is, perhaps I will revisit it later though and clean it up…
However, for part 2 it’s quite involved (and not very fast). On the upside, I think I cover all the edge cases, and the correct solution is determined in finite time. I also had to reach for some long forgotten maths to solve it.
Basically, I went for a brute force approach. For each pair of particles, I calculate their collision points. Then I group, so I get a list [collision_2, [p1, p2, p3, ...], [collision_2, [...], ...] sorted by the collision point. After that calculating survivors is pretty trivial.
I wonder if there is a better approach, but couldn’t really think of any. I though about simulating the universe by moving particles one step at a time, and removing the collided ones in each step. However, it wasn’t clear to me when to terminate the loop. When should I stop and decide that there are no collisions?
A friend of mine picked a magical number (I think it was 10000), and stopped if no collision happened in that time. I don’t really like such approach, since it’s trivial to construct an input where the collision happens after the magical number.
Good job! I tried to solve part 2 using kinematic equations, but I got hung up conceptually trying to complete the square with vectors for a, b, and c.
I eventually just gave up, and ran through each step of the equation, filtering out colliding particles, stopping after I ran the simulation “long enough” (an arbitrary number of iterations that gave me the right answer). I’m not proud.
Such is life I’m still not proud with my solution for day 16 (the dance), which detects a cycle. Once I find the time, I’ll recode it.
Regarding today, I feel that, from the performance point of view, a hybrid solution might work best. First, a simulation which would flesh out early collisions. Then, when there has not been collisions for some time, the final checkup through a hopefully much smaller set of survivors. But I don’t think I’ll have the time for that
This is my day 20 solution. I did go for simulating the particles and finding a stopping position.
My logic for the stopping condition is this:
First I check that all the particles are going in the direction in which they will ultimately end up going. I do this by checking that velocity and acceleration are in the same direction and also that the current position is in the same direction as the velocity. If this is true then the particle is moving away from the origin.
At this point the particles are moving away from the origin and will never come back. I sort all the particles by the total distance from the origin. If the accelerations of these sorted particles are all descending then they cannot meet each anymore. This because the one with the largest distance also has the largest acceleration and it escaping the others. The second farthest away cannot catch the first one, since it has smaller acceleration, but it’s acceleration is bigger that acceleration of all the rest so it is escaping them as well,…
I might need to check the velocity in the same way, but at least from all my tests this becomes unnecessary by the time the first check passes. I’m not sure if particle A that is closer to origin than particle B, but has a higher velocity and lower acceleration can catch up particle A. Probably
Here’s my day 22 solution. Day 21 was giving me lots of trouble yesterday. I haven’t come up with a working solution yet. Hopefully I’ll have time to get back to it later today.
On 21, I lost a lot of time debugging my decompose/recompose functions. In the end, the solution was quite simple, and I was able to flesh it out with the help of custom build inspect_grid and inspect_cells which printed things visually.
Learning from those mistakes, today I immediately wrote such functions, and visually verifying that I’m moving forward properly. My solution for 22 is here (debug statements are removed). After finishing the second part, I replaced stream with recursion, and did a few other minor cleanups to reduce the time from 15 to 8 seconds.
I’m still not proud with my solution for day 16 (the dance), which detects a cycle. Once I find the time, I’ll recode it.
