Hot Springs
Tags: adventofcode, algorithms, javascript, programming
Published: 2024-01-04 02:06:46

## [Advent of Code 2023 Day 12](https://adventofcode.com/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](https://regexr.com) to experiment with very specific `regex`s 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:
```js
let regex = '/^\.*';
```

Then, for each digit except the last, in order:
```js
regex += `#{digit}\.+`
```

Then, for the last digit:
```js
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:
```js
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:
```js
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 `regex`s that my function expects.

#### Turning input into arguments
Separating each part of the input:
```js
let [str, digits] = line.split(' ')
```

Turning the digits string into an ordered list of numbers:
```js
digits = digits.split(',').map(Number)
```

Extracting each index of each question mark:
```js
let questions = [...str.matchAll(/\?/g)].map(el => el.index)
```

Crafting the `regex` from three parts:
```js
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
```js
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:
```js
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:
```js
[...digits, ...digits, ...digits, ...digits, ...digits]
```

Next, the tougher one: the damaged springs.

I can do the same as above:
```js
str = [str, str, str, str, str]
```

Then, join them using a `?`:
```js
str = str.join('?')
```

And proceed with my question mark finder regex as normal:
```js
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!