Unable to load image

rDrama Advent of Code Day 16: Energized Edition

Summary for those just joining us:

Advent of Code is an annual Christmas themed coding challenge that runs from December 1st until christmas. Each day the coding problems get progressively harder. We have a leaderboard and pretty good turnout, so feel free to hop in at any time and show your stuff!

Whether you have a single line monstrosity or a beautiful phone book sized stack of OOP code, you can export it in a nice little image for sharing at https://carbon.vercel.app

What did you think about today's problem?

https://adventofcode.com/2023

Our Code is 2416137-393b284c (No need to share your profile, you have the option to join anonymously if you don't want us to see your github)

15
Jump in the discussion.

No email address required.

https://i.rdrama.net/images/17027207341610188.webp

For part2 is just part 1, but for every possible starting value. It runs in ~600ms. I then tried to add some logic that says if I already passed through a starting point with the same movement vector, I can just skip checking that starting point. That increased my time needed by 50% to 900ms.

using boost::unordered_flat_set instead of std::set to prevent looping, improves this to 160ms.

So anyone has a non brute force solution?

Jump in the discussion.

No email address required.

A recursive/DP solution where you cache the set of cells which get energized when you hit a deflector with certain direction should be fast. If you use 1 bit per cell there might be a clever way to bitwise OR the 2 sets of energized cells together.

Jump in the discussion.

No email address required.

I'm surprised he didn't force people to do that given it's day 16.

Jump in the discussion.

No email address required.

Link copied to clipboard
Action successful!
Error, please refresh the page and try again.