General Discussions
Discuss any topics that are not product-specific here.
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:
Workflow:
Macro:
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:
Main Workflow:
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:
Then we know that the '2' broken springs (from right input), can only be in two places:
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):
Combining by the remaining characters we have:
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.
| ????.?#? | 3,2 |
| 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:
Data Prep (Standard Macro):
Iterative Macro:
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:
Macro:
A look at the different combinations of ?s recombined with the known values for testing:
Dynamic RegEx:
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:
Macro:
A look at the different combinations of ?s recombined with the known values for testing:
Dynamic RegEx:
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
workflow:
part2 macro:
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
i takes lot of time to find out, it required to trim the verify text (step 4) as well.2. trim the "."
these three are same group, so group them to 1 to reduce records
3. generate the code
4. verify with new_2 for text before ?
| 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 |
workflow:
part2 macro:
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.
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.
