Advent of Code 2024 Day 7 (BaseA Style)

[AlteryxCommunityTeam]

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

[gawa]

A bit relaxing day😁

Part1

Spoiler

How to create all combination of operand:
Use the Generate Row tool to create binary strings from 0 to 2^n-1. n is number of slots of operand.
Let 0=+ and 1=*, and calculate by Multi Row Formula.

Find the record that matches requirement *Don't forget deduplication.

Part2

Spoiler

As one more operand is added, binary does not work: tertiary(0/1/2) will do. Unlike binary data, tertiary string cannot be directly created from Generate Row tool. I went with Iterative Macro to create tertiary strings. And, let 2= ||
*If data is not big, we can create Hex-decimal by Generate Row tool and filter the data having character only 0,1,2. But it took long time in this case, and I didn't take it.

Basically,  logic is almost same as part1, but I reduced no. of record to be examined for the following case:
1) part1 result can be ignored because we already know they are surely match without using new operator.
2) If target value is N digits, we can ignore combo of operand having more than N times of new operand.
for example:
Target 123, list 1 2 3 4
1 || 2 =12             2 digits
12 || 3=123          3 digits
123 || 4=1234      4 digits=>NG immediately
This is because as other operands are only + and *, calculation result for each operand will never decrease. Once it's over target value, no chance of match.
I wrote this filter condition, and it actually drops 2-3% of total records.

REGEX_CountMatches([Bin_String],"2")<Length([Target])

And, sum up the result of part1 and part2!

[ScottLewis]

That was a nice morale boost after Day 6.
I'm not normally in the do it all in a formula tool camp but this one very much lent itself to that.

Assorted hints and observations

Spoiler

Two (or three) cases means 2^n (or 3^n) possibilities.

You can use modulus on row number to make all the combinations. First column uses the row number mod N, each successive column uses Rownumber mod N^Column Number. So 1,2,4,8 or 1,3,8,27.

3^12 is a lot bigger than 2^12. Was a little concerned about execution time but I came in at 8 minutes.

Now that I'm typing this, I think it's actually N-1, which would cut execution time by nearly a third.

You can concatenate numbers by nesting ToStrings inside a ToNumber.

In cases like this where you're applying the same operation several times, I find it easier to write multiple formulas on the same variable rather than nesting IF statements. I wrote some monster conditionals last year and troubleshooting them cost me time I could have been using on the problem.

 

[kelsey_kincaid]

This one took me a bit to think through, but I'm happy with where I ended up. It was one of those rare days for me where Part 2 came easily after Part 1.

Spoiler

Workflow: Used two separate macros for part 1 and part 2, but would like to add some interface tools to allow a multi-select of what operators are permitted

Macro: 

Formula in Macro: The GetPart() function comes in handy again!

[clmc9601]

I continue to be SO THANKFUL for dark mode!! You're the best, @NicoleJ!

Channeling @grossal energy today for a formula-style macro-free solution.

Spoiler

When I write lengthy formulas, I prefer to generate them in the repetitive sections. I used Alteryx to generate the expressions for part 1 and part 2 after I wrote the first iteration. It's not truly dynamic like @gawa 's solution, as mine only tests the first 500 permutations. Mathematically, with 12 operands, there could be upwards of 2000 permutations possible.

The magic in solving this way comes from reversing the order. Rather than adding up to the total, I start with the total and subtract and divide to check the answer.

 
Here are the basic building blocks of the expression:

Spoiler

First, make sure there's an additional valid number to check.
If that condition is met, then evaluate whether the cumulative result is divisible by the current operand or ends with (||) the current operand. Regardless of whether either of those cases are met, I also add an option to subtract the current operand. 

This expression turns a single number input into 1-3 output numbers: row-1 divided by current operand, row-1 chopped off current operand, and row-1 subtracted out current operand.

IF regex_countmatches([Row-1:Cum result], ',')>1 and tonumber(getpart([Row-1:Cum result],',',1))>=0
THEN

IF Mod(IIF(isempty([Row-1:Order]),[1],tonumber(getpart([Row-1:Cum result],',',1))),[2])=0 and EndsWith(tostring(IIF(isempty([Row-1:Order]),[1],tonumber(getpart([Row-1:Cum result],',',1)))),tostring([2]))
THEN tostring(IIF(isempty([Row-1:Order]),[1],tonumber(getpart([Row-1:Cum result],',',1)))/[2])+','
+ tostring(IIF(isempty([Row-1:Order]),[1],tonumber(getpart([Row-1:Cum result],',',1)))-[2])+','
+ left(tostring(IIF(isempty([Row-1:Order]),[1],tonumber(getpart([Row-1:Cum result],',',1)))),length(tostring(IIF(isempty([Row-1:Order]),[1],tonumber(getpart([Row-1:Cum result],',',1)))))-length(tostring([2])))+','

ELSEIF Mod(IIF(isempty([Row-1:Order]),[1],tonumber(getpart([Row-1:Cum result],',',1))),[2])=0
THEN tostring(IIF(isempty([Row-1:Order]),[1],tonumber(getpart([Row-1:Cum result],',',1)))/[2])+','
+ tostring(IIF(isempty([Row-1:Order]),[1],tonumber(getpart([Row-1:Cum result],',',1)))-[2])+','

ELSEIF EndsWith(tostring(IIF(isempty([Row-1:Order]),[1],tonumber(getpart([Row-1:Cum result],',',1)))),tostring([2]))
THEN left(tostring(IIF(isempty([Row-1:Order]),[1],tonumber(getpart([Row-1:Cum result],',',1)))),length(tostring(IIF(isempty([Row-1:Order]),[1],tonumber(getpart([Row-1:Cum result],',',1)))))-length(tostring([2])))+','
+ tostring(IIF(isempty([Row-1:Order]),[1],tonumber(getpart([Row-1:Cum result],',',1)))-[2])+','

ELSE tostring(IIF(isempty([Row-1:Order]),[1],tonumber(getpart([Row-1:Cum result],',',1)))-[2])+','
ENDIF

[clmc9601]

Also, Visual Studio Code is by far my favorite IDE that can also be dumbed down and used as a great text editor. It has handy dandy color coding by language and powerful find/replace features. Using it makes writing complex formulas like this significantly easier!

[AkimasaKajitani]

Solved!

My approach is simple iterative macro solution.

Spoiler

All I did was look for something that met the conditions by taking the right hand side vertically and executing each operator simultaneously for each record. Both Part 1 and Part 2 were completed in about 12 seconds. Since the number of records wasn't that huge, no special ingenuity was required.

However, I wandered around for an hour without realizing that the maching should be made on the last record on the right hand side...

 
Part1 macro:

 

Part2 macro:

[CoG]

This problem is an excellent exercise in algorithms:

Spoiler

The key to this problem is pruning your search domain (mainly for part 2). I built a macro to do just that. The way it works is that since we evaluate left to right, if an interim calculation is already larger than the target, then it doesn't matter what operators we use later on, we will fail. We can thus stop calculating, and drop all further investigation of that branch. (As @gawa mentioned, you can also immediately filter out all successful records from Part 1 for additional efficiency). The iterative macro evaluates all records, one step at a time for each operator, throws out any operator chains that have gone over and keeps the rest for the next iteration:



The main workflow looks like this:

[DaisukeTsuchiya]

Done. WF run in 17 sec for P1 and P2. I need to go back to Day6P2.

Spoiler

[leozhang2work]

Spoiler

Took awhile to find my issue mistake (Tip: Use regex to be more restrict on what to replace, be careful replacing more than intended)

Part 2 is easy for me, adding one more case in IF ELSE solved it.