Advent of Code 2023 Day 12 (BaseA Style)

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

Accepted answers

All comments

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.

CrawlerMacro.yxmc

Qiu

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

patrick_digan

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:

Macro:

Day12 part2.yxmc

Day 12 Part2 real.yxmd

CoG

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	Count	Remaining Characters
????.?##	1	6
????.##.	1	5

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):

ID	Prior Count
1	1	????.?	3
2	1	????.	3

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

ID	Prior Count			Remaining Characters
1	1	?###..	3	1
1	1	###..	3	0
2	1	?###.	3	1
2	1	###..	3	0

Combining by the remaining characters we have:

ID	Prior Count
1	2	?	-
2	2	-	-

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

Solution.yxzp

kelsey_kincaid

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:

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

Dynamic RegEx:
D12P1 Dynamic RegEx 1.png

AOC2023_Day12P1_KelseyKincaid.yxzp

AncientPandaman

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 "."

1	count
##.##?	1
##..##?	1
.##.##?	1

these three are same group, so group them to 1 to reduce records

1	count
##.##?	3

3. generate the code

2	new_2
1,1	#.#
1,4	#.####

4. verify with new_2 for text before ?

1 (trimmed ".")	new_2	text 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

Day 12.yxzp

Raj

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

mmontgomery

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.

2023_Day12.yxzp

ccanterman

@PangHC - 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

Gawa

Finally finished D12P2. As 2 days has already passed, I upload my WF this time.

Spoiler

My WF looks very simple, but needed uncountable attempts to make this....

Day12_gawa.yxzp

DaisukeTsuchiya

@Pang_Hee_Choy - Thank you so much for sharing super straightforward your solution.

I was stuck for so long time then I can get idea from your spoiler although I didn't download your WF.
Finally I can finished after repeating debugging so many times. WF runs in 15 sec.
I can sleep tonight.

Spoiler

Day12_Rev2.yxzp

AkimasaKajitani

I struggled with Day12P2 but I finally got the second star!!!

I did not notice that the RegEx Match expression in a macro gave up to run, so it took me for long time.

Spoiler

Part 1 macro : simple macro

Part 2 macro:

In part 2 macro, I made it according to following term.

1. I convert rom ? to . and #
2. Create a definitive pattern on my own & delete the left-most number if it is already definitive.
3. Re-create Num.
4. Discard those that don't fit in the pattern check
5. Reduce the number of records by grouping and summing counts

This workflow takes 1 minutes to finish.

SeanAdams

This is one of those days where it started out with brute force, and then Part 2 showed me the error of my ways.

It’s now running part 2 in ~17 sec – very happy with this solution!

Spoiler

Solution:

A few things that will help you as you think through this:

Alteryx works with spaces much easier than . characters
A double . does the same job as a single – but it’s much easier to work with singles (because you can do a simple text match vs. target)
Leading & trailing . characters don’t add value but they do add complexity

So here’s the recipe:

Parse the data

change . to spaces;
remove duplicate & leading / trailing spaces
Build a target string of what you’re looking for – e.g. 1,1,3 will be #.#.###

Figure out valid combinations:

Repeat until you run out of strings with ? characters:

For each incoming row, Create 2 rows – one that replaces the first ? with a space; and one that replaces it with #
Trim leading & trailing spaces
Trim duplicate spaces
Throw away any strings which are shorter than the target
Figure out where the next ? is – call this X
Match the first X of my working string vs. the target – if it fails, discard
Then check if any of our working strings are the same – if so, then keep a counter
1. E.g. instead of having 2 rows with ###??? – instead keep 1 row with a counter of 2
Loop

This works fast for a few reasons:

Your number of rows that you are iterating with is very small because you compress them into a summary (step 7 above) and you are throwing stuff away as you go along
You are using simple string matches each time (all the complexity of leading and duplicate spaces is gone)

2023_Day12-Part2b.yxzp

Tokimatsu

Just one summarize tool in one place made it dramatically faster. I can't tell you how long it took me to do that.

Spoiler