Advent of Code 2023 Day 16 (BaseA Style)

[AlteryxCommunityTeam]

Discussion thread for day 16 of the Advent of Code - https://adventofcode.com/2023/day/16

[gawa]

The longest execution time ever in AoC2023, 37 minutes. I want to know any smarter logic.

Révélation

My iteration number was 

Révélation

around 1,000-1,100 times. 

If you wish brute force attack, please refer to this value. 

[AndrewDMerrill]

I lucked out on my first run (I had a bug that could have resulted in miscounting, but everything worked out okay thankfully; I think I had about a 25% chance of success). Similar approach to @gawa except I added a bit of extra logic that allowed for my workflow to take half the time! only 18 minutes XD

Clever Brute Force Strategy (for part 2):

Révélation

Instead of pure brute force, add logic that adds in part 1's results. Any laser beam that ends up in the same tile/cell going the same direction as a beam from part 1, will, by necessity, trace out the entirety of Part 1's trajectory allowing us to terminate the search early. This also implies that for every termination (i.e. where the laser hits the wall), the corresponding beam that enters from the same spot in the reverse direction will also no longer need to be considered.

Workflows:

Révélation

Main Workflow:


Iterative 1 ( for Part 2 runs all cases):

Iterative 2 (Ray Tracing):

[AkimasaKajitani]

Team Brute Force

Révélation

It takes me 1 hour 20 minutes to get the results for Part 2. It needs long time to finish, but the logic is simple.

 

Part 1 macro
I mistook the record point of history, so I wasted a lot of time. It was too hard to find.

Part 2 Batch Macro
This batch macro run Part 1 macro 440 times.

 

[DaisukeTsuchiya]

I also use brute force.

Révélation

It take 1.5min to run P1 for 2800 loop so I wonder same macro can be used for P2. @gawa advise that batch macro would be slower so I generate all direction input outside of macro then input into P1 macro at one time. Luckly it completed in 45 min.

Rev.1 WF is uploaded on Dec 17


<Common Macro for P1 & P2>

 

[kelsey_kincaid]

I am also solidly on team Brute Force. There has got to be a better way. This is on my list to cleanup and optimize as I have time, but for now my focus is on getting D12P2 done!

Révélation

Part 1: I really like using tables instead of building out complex formulas. I built a mapping of the different directions a light beam could be heading, the symbol it would encounter, and what would need to happen next. My iterative macro took the starting location (in P1, row 1 column 1) and then found the next non-blank cell it would encounter. From there it figures out which blank cells were energized along the path and returns those in the output, while taking that non-blank cell and feeding it back through the macro to find the next step in the path. I realized that the light beam never necessarily "breaks out" of the grid and can loop infinitely. There is surely a good way of breaking out of the macro once it starts looping like that, but instead I just set a reasonable max iteration count for the macro and de-duped on the back end. I'm eager to see how everyone else handled this.

Part 2: To create a list of potential starting cells, I first found every row and column that had a single non-blank value in it. I realized we didn't need to spend time evaluating columns or rows that would break out of the grid quickly because of fully blank values. Then I calculated the directions they could be going and fed that into a batch macro which ran the iterative macro from P1 for each possible starting point. Took about 35 minutes to run :\ but it got me the right answer. The early stopping I am missing from P1 would probably speed P2 up a lot, too.

Workflow:

Iterative Macro:


Mapping:


Batch Macro for P2:

 

[mmontgomery]

P1 and P2 had the same macro logic but different setups. More in spoiler

Révélation

In the macro, I decided to break out each filter combination into a different step to make it easier to debug.

For P2, it took me a bit to build the entry point logic. I ended up doing manual list creation by generating rows. I ran the main macro about 1k times to get a sense of top leaders then ran the top 3 after at 2500 times to get the final count.

I had a bug to fix in my final sum. The iteration macro started on step 2 but I forgot to include step 1 in afterward sum. Once I did that, it ran in a few minutes overall

[Pang_Hee_Choy]

team brute force+1

1 hours+ run time

[Tokimatsu]

Done, but later I will try to create more faster workflow.

Révélation

 P1 macro

 

P2 macro, calls M1 macro.