Advent of Code 2024 Day 17 (BaseA Style)

[AlteryxCommunityTeam]

Discussion thread for day 17 of the Advent of Code - https://adventofcode.com/2024/day/17

[CoG]

This problem looks like a nightmare to work out, but it's actually quite simple once you type out all of the cases (Part 2 comes with a lovely trick):

Spoiler

All instructions for a single step of the program fit into a single Formula Tool. If you take the time to read and plot out what the code is doing, it is essentially a simple for loop, iterating on the value of Register [A]:

3 Bit Computer (Iterative macro that handles programs):


Running the macro above for the provided problem data gives the answer for Part 1. For Part 2 I broke out the pen and paper and ran some simple test cases to identify how this program really worked. It turns out the code is a lot simple than I anticipated. For every iteration's output (remember the program is a for loop), the value of [A] is reduced by a factor of 8. This immediately gave me an understanding of what the solution would look like. Since the program is 16 values long, we need to run 16 iterations, which means [A] needs to start at a minimum of 8^15, which is huge, and immediately ruled out the brute force approach. I looked at the small cases again and had an epiphany: Part 2 expects the minimum [A] that outputs the program (as the programs output). Considering the modularity/periodicity of the problem, I can thus work backwards to identify what the value of [A] should be to generate the last characters of the program as output.

Example
Code: 2,4,1,1,7,5,1,5,4,0,0,3,5,5,3,0 
Start with [A] = 0,
increase [A] by 1 until the output of the program matches the last character of the code ("0"). Once I found that value, I can multiply by 8 (the reverse of the programs iteration) and start the cycle now looking for the computer to output the last 2 characters of the code ("3,0"). The key insight comes from recognizing that even though I will be checking larger and larger numbers (int64 for all fields), *I will only need to check a maximum of 8 values per program character to find a match. Once a complete match is identified terminate the search and you will have your answer!

*Note: This is not technically guaranteed (since each input range is not guaranteed to cover all potential values (mod 8), but it is a reasonable assumption for AoC and, in the case of D17, this assumption is valid.

**EDIT: The assumption above is still required since not all programs can be generated as output, but we do need an extra bit of logic to account for these collisions. My input was perfect and never hits a digit that is not part of the output, but this is not true of all participants inputs (See next spoiler for how to handle this more generalized approach).

Search for Copy (Iterative Macro):

Main Workflow:

V2 (Solves All Inputs; I over-wrote my original file to ensure that nobody else gets the same bug, so see Main.yxzp for solution):

Spoiler

Thanks to those that pointed out my solution only worked for some inputs, and special thanks to @Hub119 for sending me his input program!

We can generalize my workflow by incorporating another powerful process, recursion. If we ever leave the 8-value window that we expect a result in, then know that we made a mistake earlier in the selection process. We can simply reset the value of [A] back to the previous value then progressing as before (i.e. Floor([A]/8). This process functions like a Depth First Search, and I believe this resolves the issue some had with my approach before, and runs quite quickly.

[Goddenra]

Very similar for P1. A far less elegant approach to P2. Ran for a first set of records (100k), spotted the pattern, then worked out a starting point. Still needed a bit of brute force at the end, but the number was at least manageable!

[mmontgomery]

Day17. More in spoiler

Spoiler

P1: Took me forever to setup, but once I did it was straight forward to run/debug
P2: H/t to @CoG for approach and then I built it based on how my data was structured.

Run time: 2:56

[Qiu]

@CoG 
I was only thinking that the output for  A as 4 or 5 will be the same (divided by Nth power of 2 and truncated to integer), but did not think there is more.

thanks for the hint.

[Tokimatsu]

My part2 solution works for only attached input data.

Spoiler

 

 

 

[gawa]

Thanks to hint from @CoG , I finally get out of the labyrinth just now.

It reminds me of my tough experience of 2023D20(at that time, @CoG helped me out)

Spoiler

First, I thought about Batch Macro for brute force approach but once I input my answer having 15 digits integer, they said "too low". I gave up brute force.
Next, I tried to start calculate backward based on part1 result because XOR can be inversible operation. But at some points, I realized value of register "C" is not predictable(not 100% sure about it but I guess so).
Lastly, I checked spoiler of CoG, and got a great hint. Thanks!
 

[Hub119]

This one got a bit crazy... part 1 was easy enough once I just slowed down and "coded" the problem statement step by step as I read it.  Part 2 on the other hand required me to put my part 1 iterative macro, inside a batch macro, inside ANOTHER iterative macro... but once that was finally set, got everything to run in a little over 10 minutes.  I'll take it.

Spoiler

Workflow

Spoiler

P2 Outer Iterative Macro

Spoiler

Part 2 Batch Macro

Spoiler

P1 Computer Macro

[DaisukeTsuchiya]

It took me quite a while to fully understand the problem statement.

Spoiler

For P1, I struggled with how to manage data within the iterative macro. In the end, a single line of data summarizing the parameters is used for iterative macro.

For P2, brute force was completely unfeasible due to the enormous volume (8^15). I initially tried calculating all possible values for Registers A, B, and C, but it seemed overly complex. Instead, I followed the spoiler from @CoG  and focused only on calculating Register A. Thanks,  @CoG - I always find your insights helpful.

Register A would be calculated by multiplying Register A by 8, adding 0–7 then tested whether the results matches the program's final output. These process is repeated 15times. 

[AkimasaKajitani]

Solved!

Spoiler

Finally, I got the answer. For Part 1, it took me a while to understand the logic of the quiz. I made a table of what each program would do, then put that into Designer.
For Part 2, I could see that there was a pattern from the results of Part 1, and by tinkering with the numbers, I was able to get the answer. I guess the key is 8 bits...To be honest, I haven't quite sorted out the workflow for Part 2 yet.



Part 1 macro


Part2 iterative macro (messy one)


Part 2 batch macro : This macro has Part 1 macro inside.