Advent of Code 2023 Day 16

Day 16 of advent of code got me thinking a tiny bit more, until I started to think clearly :)

Day 16 of this year's Advent of Code wasn't that difficult, but it's leaving me thinking.

It involves tracing a light beam around a 2-dimensional grid. It can do one of three things, I suppose. It can continue in the direction it's moving, bounce off of a slanted mirror (/ or \) and change direction, or it can split.

In part 1 you start at {0, 0} and you need to find out how many points it touched. In part two, you need to find the maximum value of these points if you were to start at every point on the 4 edges.

I managed to get it from a runtime of about 8 seconds, down to 700 milliseconds by removing a large calculation I was doing every time it recursed. And I was thinking if I could make it even faster.

My idea may be wrong, and I'll think of it more. But if you ran a beam from a point, and it ended up on another point, could you eliminate that other point from the search space?

I'm thinking no, definitely not. But then I think maybe.

But definitely not. Mainly for two points. If you start at the end point and head out from the direction it came, does it travel the same path? And two, if it did, the light can be any number of light beams by that point.

If a light is heading east and comes into a | splitter, it then heads north and south. If the opposite beam was coming in to the same splitter from north or south, the rules of the puzzle says it just passes through. So no, definitely not.

I thought for a split second I had something profound but you definitely need to run through the entire search space :P  Oh well.

This year's problems have been more math based, but we did have to implement a hash map, and some problems involve recursion (like this one), so that's good. Last year's was a bunch of data structures and was fun as hell. Hopefully I can get through these but my math isn't nearly as strong!


blog comments powered by Disqus