Hot Springs

Advent of Code 2023 Day 12

Part 1

Full understanding. Full intimidation.

I read today's entire description.

I feel I understand the task well.

I took the day to repeatedly strategize how I might solve it.

And the best strategy I could think of involves recursion and checking all possible arrangements...even ones that will clearly not pan out to winning arrangements.

So, I'm not feeling great about earning this star.

One interesting win: a regular expression

When thinking about how I might compare an arrangement to the contiguous group of damaged springs, I used regexr.com to experiment with very specific regexs that used the numbers.

For example, checking the first sample string #.#.### for a match against 1,1,3, can be accomplished with this regex:

/^\.*#{1}\.+#{1}\.+#{3}\.*$/

That looks pretty cryptic, so let me break it down:

• ^ is the start of a string
• \.* is 0 or more .s
• #{N} is exactly N #
• \.+ is 1 or more .s
• $ is the end of a string

Repurposing it for use on this string .#.###.#.###### for a match against 1,3,1,6 can be accomplished with this regex:

/^\.*#{1}\.+#{3}\.+#{1}\.+#{6}\.*$/

How would I programmatically construct that regex for each line's digits?

Start with:

let regex = '/^\.*';

Then, for each digit except the last, in order:

regex += `#{digit}\.+`

Then, for the last digit:

regex += `#{digit}\.*$/`

And viola! I should have a regex that can test any string for a match against the contiguous damaged springs.

Now...how am I going to generate all possible arrangements?

Thinking out loud...a lot!

I'll start with the first sample string again:

???.### 1,1,3

Three question marks, at indices 0, 1, and 2.

Each question mark is binary: it could either be a . or a #.

A bifurcating fork at each ?.

The potential arrangements are:

2 to the power of [number of question marks]

In this case:

2 ^ 3

Or 8:

...
..#
.#.
.##
#..
#.#
##.
###

It is a pair of sideways binary trees:

    .        #
  .   #    .   #
 . # . #  . # . #

Could I construct this using recursion?

What would be my base case?

Let me work through this.

Building a binary tree with recursion

My recursive function may need:

• The damaged condition records
• The contiguous groups as a list of digits - or the regex I wrote above
• A decreasing list of remaining indices to bifurcate on

No better way to see where my logic is wrong than to simulate calling this function.

Here's a rough outline of this function:

function findArrangements(qMarks, arrangement, regex) {
  if (qMarks.length == 0) {
    return arrangement.join('').test(regex) == true ? 1 : 0
  } else {
    return findArrangements(qMarks.slice(1), arrangement.splice(qMarks[0], 1, '.'), regex) + findArrangements(qMarks.slice(1), arrangement.splice(qMarks[0], 1, '#'), regex)
  }
}

What's my thinking here?

• The base case is an empty list of indices of the positions of question marks
• The function continually chops off the next index of question mark, starting from the front of the string
• It treats the arrangement string as an array and replaces the question mark with a . and a # in two separate function calls, thereby adding two nodes to the current branch of the binary tree
• Those subsequent function calls will get one-element-smaller question mark location arrays, one-character-modified arrangement arrays, and the same regex to test in the base case
• What's returned from each base case is whether the transformed string matches the regex
• If it does, return 1 to add to the sum of matching arrangements
• If not, return 0
• Each higher level will sum up the tallies from both nodes' leaves
• The original function call will then sum up tallies from all branches

At least, that's the hope.

Odds are I got something wrong.

Time to write this and debug!

The fun part: programming

After some troubleshooting of the splice() method, my recursive algorithm is generating the correct answers for several sample lines.

This is my working JavaScript algorithm:

function findArrangements(qMarks, arrangement, regex) {
  if (qMarks.length == 0) {
    return regex.test(arrangement.join('')) == true ? 1 : 0
  } else {
    return findArrangements(
      qMarks.slice(1), 
      arrangement.toSpliced(qMarks[0], 1, '.'), 
      regex) + findArrangements(
      qMarks.slice(1), 
      arrangement.toSpliced(qMarks[0], 1, '#'), 
      regex)
  }
}

I omitted the console.log() statements which helped me see what was going wrong - and then right once I fixed it.

Right now I'm manually calling the function with pre-parsed arguments.

I need to do the other fun part: parse each input line into the correctly structured and formatted arrays and regexs that my function expects.

Turning input into arguments

Separating each part of the input:

let [str, digits] = line.split(' ')

Turning the digits string into an ordered list of numbers:

digits = digits.split(',').map(Number)

Extracting each index of each question mark:

let questions = [...str.matchAll(/\?/g)].map(el => el.index)

Crafting the regex from three parts:

let regex = '^\\.*';
for (let i = 0; i < digits.length - 1; i++) {
  regex += `#{${digits[i]}}\\.+`
}
regex += `#{${digits[digits.length - 1]}}\\.*$`

My working algorithm for Part 1

input.reduce((sum, line) => {
  let [str, digits] = line.split(' ')
  digits = digits.split(',').map(Number)
  let questions = [...str.matchAll(/\?/g)].map(el => el.index)
  let regex = '^\\.*';
  for (let i = 0; i < digits.length - 1; i++) {
    regex += `#{${digits[i]}}\\.+`
  }
  regex += `#{${digits[digits.length - 1]}}\\.*$`
  return sum += findArrangements(questions, str.split(''), new RegExp(regex))
}, 0)

And here again is the working recursive function:

function findArrangements(qMarks, arrangement, regex) {
  if (qMarks.length == 0) {
    let test = regex.test(arrangement.join(''))
    return test ? 1 : 0
  } else {
    return findArrangements(
      qMarks.slice(1), 
      arrangement.toSpliced(qMarks[0], 1, '.'), 
      regex) + findArrangements(
      qMarks.slice(1), 
      arrangement.toSpliced(qMarks[0], 1, '#'), 
      regex)
  }
}

It generates the correct answer instantly for the examples.

And after about 20 seconds, it generates the correct answer for my puzzle input!

I wonder how many factors of 2 it had to run in those 20 seconds. Probably several million. Tens? Hundreds?

On to Part 2...

Part 2

Everything is five times as long???!!

I doubt recursion is gonna get me through this.

I foresee a stack overflow on my input's first line.

But, I'm confident I can at least augment my Part 1 algorithm to generate the correct answer using the example input.

So, I'll at least try to do that.

Unfolding everything five times

First the easy one: the contiguous digit groups.

Once I have the list of numbers, I just need a list containing that list five times:

[...digits, ...digits, ...digits, ...digits, ...digits]

Next, the tougher one: the damaged springs.

I can do the same as above:

str = [str, str, str, str, str]

Then, join them using a ?:

str = str.join('?')

And proceed with my question mark finder regex as normal:

let questions = [...str.matchAll(/\?/g)].map(el => el.index)

That should be it. Right?

Time to find out.

Running and waiting...

I saw 1 for the first line. Correct!

Then nothing. For minutes.

So I rearranged the lines.

Saw 1 again.

Waited a few minutes.

Then saw 17. It should have been 16.

Bummer.

Given how long a line with only 4 ?s took, this thing will take days - maybe years! - to finish.

So, that's as far as I can get here.

I wonder how smarter programmers did this without recursion.

All I know is...on to Day 13!