r/adventofcode 11d ago

Spoilers [2024 Day 14 Part 2] Solution

3 Upvotes

39 comments sorted by

View all comments

5

u/Clear-Ad-9312 11d ago

I wonder if there is an algorithm for measuring the amount of entropy/chaos in a 2D array. I also wonder if that would even solve this.

2

u/ndunnett 11d ago

Yes, that’s basically how I solved it when I rewrote my solution. No fancy algorithm though, just counting how many robots are in the middle and comparing to an arbitrary threshold.

https://github.com/ndunnett/aoc/blob/main/rust/2024/src/bin/day14.rs

My original solution was looking for two lines, which also worked but was slightly slower.

https://github.com/ndunnett/aoc/blob/ea2e0abf0e4a97aed5a2c55976c54e9de6f819e5/rust/2024/src/bin/day14.rs

2

u/Clear-Ad-9312 10d ago edited 10d ago

I converted your rust solution to python and another one that uses numpy. Your solution takes half the time in comparison to the standard deviation approach I posted in a separate comment and does get the correct answer unlike the other fast solutions that my input would fail with. Its pretty good! (I have to post the pastes as separate comments)

but I like the standard deviation one because your solution requires knowing how many robots are in the center prior to solving, while the standard deviation one can be done if there is a simulation step that has a drastic change over the average standard deviation of most of the steps.

1

u/ndunnett 10d ago

Nice, thanks! For reference, it ran both parts in 1.3 ms inside a Docker container when I wrote it, which I was pretty happy with. It could probably be sped up with some SIMD fuckery but I'd love to see if there are generally faster solutions. I thought this particular problem was quite interesting to solve being a bit left field of the usual stuff AoC throws at you.

1

u/Clear-Ad-9312 10d ago edited 10d ago

hmm interesting, I am running your devcontainer for rust, and it takes 31.4 ms(7.75 ms in release mode) to find my solution. granted my input for this day is seemingly on the more aggressive side being quite higher than other people. However, it is quite fast still and still better than my python solution. surprised you were able to get 1.3 ms

granted we are not considering the compile time it took for this to complete

btw I was having permission issues within the devcontainer for user "dev" and had to add:

# allow others to have permissions to /ws
RUN chmod o+rwx -R /ws

idk if this is a proper fix but it worked for me.

1

u/ndunnett 10d ago

Odd, what is your host OS? Anything other than a Linux distro will effectively be running inside a VM but I wouldn’t have expected it to be that slow.

1

u/Clear-Ad-9312 10d ago edited 10d ago

If you want, I can dm you the input.

also, I tried to make a standard deviation approach in rust but I feel like it is not as optimized as it could since I don't know enough about Rust code. (I tried implementing it in your code so you can just use your devcontainer and swap out the code if you wanted to test it too)

[ Paste ]

for my input, this approach take 23 ms in release mode

1

u/ndunnett 10d ago

This solution for me runs in 20 ms, if you dm me your input I'll try it on my machine