General Discussions

Discuss any topics that are not product-specific here.

Advent of Code 2023 Day 12 (BaseA Style)

AlteryxCommunityTeam
Alteryx Community Team
Alteryx Community Team

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

14 REPLIES 14
ScottLewis
8 - Asteroid

Macro for part 1. Faster of the two ways I was able to solve part 1 (the other being constructing all possible sets of operational springs up to len(springs-damaged). Runs in about 3 seconds on my Part 1 data. Bursts in to flame if I feed it 10 lines of part 2. Working on that. Probably something to do with partial search or excluding cases but I haven't cracked it yet.

 

Qiu
20 - Arcturus
20 - Arcturus

@ScottLewis 
3 seconds? that is supper fast. mine spends 3 minutes... 😂
Part2 is disaster..

patrick_digan
17 - Castor
17 - Castor

Phew, Finally got part 2. I solved part 1 with a much different mehtod, but it didn't scale for part 2. So now this method solves either part. "Only" 28 seconds for part 2!

Spoiler
I basically build the string character by character in an iterative macro. The key is the filter to make sure it's on the rights track and that my record count doesn't blow up. Also important that the summarize tool is in the macro to combine converging paths.
Workflow:
image.png

Macro:
image.png
AndrewDMerrill
13 - Pulsar

This took me so long, and I'm honestly a little bitter about how simple the workflow looks, now that I've tidied it up. It was so satisfying watching the journey from basically crashing my computer, to running part 2 in ~6 seconds. I'll post my workflow when 10 people have finished the D12P2.

 

Edit: Posted my Workflow

 

Spoiler
Explanation of Solution:
Spoiler
This problem is best solved via a technique known as Dynamic Programming, in which problems are broken down into smaller sub-problems that can more quickly computed, the results saved, and then used in the next iteration. For this problem I matched the rightmost matches to the rightmost cluster of contiguous broken springs. For example if we have:
????.?#?3,2
Then we know that the '2' broken springs (from right input), can only be in two places:
Configuration
CountRemaining Characters
????.?##16
????.##.15

We now have the basis for the DP algorithm. If we store this as our Iterative Macro Input and Output, then we can progressively count all the possibilities since we are effectively now solving two new problems (with saved info):
IDPrior Count  
11????.?3
21????.3

 
We repeat the process from step 1 (hence the dynamic part of DP algorithm), to get:

IDPrior Count  Remaining Characters
11?###..31
11###..30
21?###.3
1
21###..3
0

Combining by the remaining characters we have:
IDPrior Count  
12?-
22--

But since we have no more broken springs to account for, we can break out of our iterative macro and aggregate the final output (in this case - Sum of [Prior Count]) revealing a final answer of 4.


Main Workflow:
Main Workflow.png

Data Prep (Standard Macro):

Data Prep.png

Iterative Macro:

Iterative Macro.png

 

 

kelsey_kincaid
12 - Quasar

I haven't gotten Part 2 yet, but I don't know that I will today so I'll go ahead and post my Part 1. It isn't the most efficient solution, but there are components of it that I'm proud of. Just need to optimize!

 

Spoiler
One thing I realized after pondering this and dreaming about it is that Base2 could be really helpful. There is a defined number of permutations of the missing values (denoted by ?) and that is 2^(# of question marks). Then, by converting each number from 0 to that maximum value to a binary string, you suddenly have a list of every possible permutation of # (which I replaced with 1) and . (which I replaced with 0) in your string. The answer on my production data was too low, which I finally figured out was because some rows are already valid and so every unknown value needs to be a working gear. All I had to do was start my iterations at 0 instead of 1 and it all worked out... just took time to troubleshoot! I also had to recombine the ? values back with the known values before testing.

The next puzzle was to figure out how to check that the pattern generated was a valid one. I split my pattern list into rows, and used a formula to generate what RegEx pattern I should be looking for. If there were 4 #s in a row, then I'd be looking for 1{4}. Then I used a Summarize to concatenate those back together with a 0+ as my delimiter, which ensured that every string of 1s was separated by at least one zero. I later added a prefix and suffix to the pattern, which I could have done in the Summarize tool itself (a clean up task after I figure out part 2 perhaps).

I wrapped all of that logic in a batch macro and let it fly. It takes several minutes to run, but nothing tooooo crazy. I know there are more efficient solutions out there.... especially after looking at Part 2 😰. I'll keep fiddling with it!

Workflow:
D12P1 Workflow.png

Macro:
Day12P1 Macro.png

A look at the different combinations of ?s recombined with the known values for testing:
D12BinaryRegExExample.png

Dynamic RegEx:
D12P1 Dynamic RegEx 1.png
D12P1 Workflow.png

Pang_Hee_Choy
12 - Quasar

struggle a lot...

thanks AMP to speed up the time spend.

Spoiler
part1: skips, just do it. and verify in the end

part2: few methods to reduce the records. 
1. create "count" column and group them
2. trim the "." for ease for grouping
3. generate "#.#" for text 1,1 
4. verify by text before ?, with step 3 in same text length

explain for point 2, 3, and 4
Spoiler
2. trim the "."
1count
##.##?1
##..##?1
.##.##?1
 
these three are same group, so group them to 1 to reduce records
  
1count
##.##?3

3. generate the code
2new_2
1,1#.#
1,4#.####

4. verify with new_2 for text before ?
1 (trimmed ".")new_2text before ?new_2 (same text length with text before ?)result
##.##??##.##.###.####.##pass
##.##.?##.####.##.##.##pass
##.#.?##.####.#.##.##fail
i takes lot of time to find out, it required to trim the verify text (step 4) as well.

workflow:
Screenshot 2023-12-13 110534.png 
part2 macro:
Screenshot 2023-12-13 110540.png

 

Raj
13 - Pulsar

@Pang_Hee_Choy  Great thinking man
spent a huge time on this Challange but never thought this way.

mmontgomery
10 - Fireball

P1 solved with no macro. P2, well, probably will need some help.

Spoiler
P1 took me a long time to figure out the logic and once I did, I fixed a small bug, and team brute force worked!

I used 20(!) generate rows fields to create 01 combinations on top of each other to create the possible value list.

From there, I split the puzzle into three categories:
1. ?
2. #
3. '.'

I then created a sequenceID per row to identify which final column they belong in.

To make life easier to consolidate all '....' to '.' since they didn't change the outcome.

From there I figured out the max combo of rows needed from generate rows using a regex match of the key symbol above to filter to only the necessary rows needed for blending to give each row its own tabular dataset.

From there, I made the values into 1 or 0 string then did a multirow to calculate running sums then took the max of the running sum ends and concatenated it to match it against the instructions.




Day12P1.png

  

Carolyn
8 - Asteroid

@Pang_Hee_Choy - Thanks for sharing! I was stuck on how to come up with all the diff possible combos for Part 1 and your solution was super straightforward. I was trying to do it all at once but duh, do it one at a time :) 

Labels