Back into the mix with Advent of Code! I'm up to date so far in 2022, but I sorta cheated on one star, and I'm sure the remaining days will be brutal.

Hi, It's been a while. I've been doing Advent of Code starting December 1st, it is my 8th year, and accoring to the calendar, I've completed 5 of the 8. Sometimes I still try to work on the ones that I've missed.

Some of my favorite ones so far have been day 15 and todays, day 18, which prompted me to write up this little post about it.

Here are my solutions for day 15 and day 18. I wasn't quite able to solve day 17 yet, but my solution is fast and the idea is the right one, but the number just isn't correct. I found my solution by running some rust code someone else had written. That might become a thing in the future, me writing rust code. For right now, I can just read it and run it, like this kid I grew up with who could fluently understand his mother's Italian, but couldn't speak a word of it.

But I also do that sometimes to try to see how far away my answer is. The problem with day 17 was that of the 3 solutions I tried in rust, only one gave me the right answer for my input. It was the only one I've used to put in an answer that wasn't output by code that I wrote.

Day 15 Thoughts

Day 15 was fun. The main thing about it was finding the trick for part 2, which was to search a 4 million by 4 million size grid (hey google, what's 4 million times 4 million?) which is a 16 trillion search area. BUT you can cut down a ton of that with a little trick. There are better tricks than what I used, but mine is as follows:

Start at 0,0. Loop 16 trillion times :P  Just kidding. Start at 0,0. If you're within reach of a sensor, you know there's no sensor there. So you can figure out the current distance to the nearest sensor, and based on the distance (if it's less than the distance to its nearest beacon), you can just skip a bunch of steps. Basically, I wrote it up as this  ---

You're at point p1 (x1, y1) and the nearest sensor is at p2 (x2, y2). The nearest beacon is 12 away, and you determine that p1 distance is 5. If x1 is less than x2, you can definitely skip ahead to x2. But if you're at x2, your distance is only (y2-y1), so you can skip a whole bunch of steps after that. The number of steps you can skip is the distance minus abs(y2-y1). Distance is just abs(x1-x2) + abs(y1-y2). And if you're right above the point, you can just skip abs(x1-x2).

In the example, if you're 5 above the sensor and the distance to the nearest beacon is 12, you can skip right 7 and continue searching at x1+7,y1. These beacon radii were huge so you skip a ton of steps. My code searches the 16 trillion search area, and completes both parts, in 1.13 seconds. Not bad.

Day 18 Thoughts

I started out this one with the easy way for part 1, which was to get a list of the points, then loop through them and see how many points were directly beside it (distance == 1). The distance formula from part 2 works the same in 3D space, just use 3 points.  abs(x1-x2) + abs(y1-y2) + abs(z1-z2). If you have a point and determine it has 4 cubes directly beside it, then it has 2 sides that are exposed. Easy. But you always suspect part 2. Part 2 is sus and you're going to need to rewrite your code :)

Part 2 comes around and it's a doozy. I tried to remain lazy and see if I could solve it using the same kind of thing, if there's no square on a certain side, just see if that continues out into infinity. I wrote that and ran it on the sample imput, and it was wrong. It was close though, but there were some edge cases. Like a point on the outside that was directly across from a point also on the outside, but they were part of a V shape where they were both outside, but were across from each other.

Eventually, I decided to make a graph. A graph in computer science where you keep track of connecting nodes, and it makes it easy to determine paths to the next one. I rewrote part 1 using the new graph functionality, and it worked.

But then I tried to apply the same methodology that I was trying earlier, which was to see if there were any across from the current side. This was when I determined the edge cases above. I would print out the graph to see this. Ahhh, there's a V shape and both points are external, but my code reports them as internal. If this isn't making sense, basically you have 3D points to a ball type structure, where the inside is hollow, and you need to determine what points are internal and which are external.

At this point, I decided to the do the floodfill algorithm as seen in the code. But it's like an infinite space outside of the blob. So I decided to find the min and max points for all points, and decided that max+1   (max.x+1, max.y+1, max.z+1) is outside and is a good point to search for. The first time took a while to finish. It gave me the right answer, so I put it in and got my second star. However, I wanted to make it fast. At this point I change the parameter for the flood fill "find node" to a list of nodes, and any time I found a point, I would add the starting point to the list of points to find. This ran a little faster but it was using tons of memory. There's close to 3000 points, each point could add up to 6 points to the list to find. I finally decided to change the parameter to a map. I didn't try my method to update the map with points I found, instead I just built a box around the entire blob. It was a smallish box, the max dimension on any point was 22, so my list was like 10000 nodes, but it really sped it up to run around a second. Fun stuff!

I'm also going back and formatting old solutions with my AOC boilerplate, and I ran into one that isn't correct, it gives the wrong answer! So I have to fix it. It's a hard one, 2017 Day 21. I probably did the same thing and ran someone else's code. But that's unacceptable and I'll update it to work. And have been for a few days!