Robert Mion

Posted on

# Medicine for Rudolph

## Part 1

1. Can this be solved with just `matchAll()`?
2. How about with `reduce()`, `matchAll()`, `slice()`, `Set()`?
3. Writing a working algorithm

### Can this be solved with just `matchAll()`?

• I could use `matchAll()` to count the number of occurrences in my puzzle's input string of each string to be replaced
• I could run that on each replacement rule
• Then sum each count up
• But that assumes that no two replacements would have created the same modified string
• And the prompts throughout this puzzle's instructions make it seem highly unlikely that there are no two identical modified strings

### How about with `reduce()`, `matchAll()`, `slice()`, `Set()`?

• `reduce()` will accumulate a unique set of values
• `matchAll()` will find each occurrence of the string to be replaced, along with the index where that string starts
• `slice()` will let me concatenate together the parts of the original molecule string before and after the string to be replaced, with the replacement string sandwiched in-between
• I will attempt to add each modified molecule string to a `Set()`, trusting that it won't add duplicates
• Then I'll return the size of the set

Let's see how this goes!

### Writing a working algorithm

In pseudocode:

``````For each rule, accumulate a set of unique strings
Store each index of each match of the targeted substring rule in the molecule string
For each index
Add to the set - if not a duplicate:
the string resulting from stitching together the parts before and after the replaced string, with the replacement string sandwiched in-between

Return the size of the unique set of modified strings
``````

In JavaScript:

``````rules.reduce((distincts, rule) => {
let matches = [...molecule.matchAll(rule[0])]
.map(el => el.index)
matches.forEach(
match => {
molecule.slice(0, match) +
rule[1] +
molecule.slice(match + rule[0].length)
)
}
)
return distincts
}, new Set()).size
}
``````

## Part 2

1. Highly unlikely
2. But maybe a simulator?
3. `HOHOHO` in 6 steps
4. The first steps of my molecule
5. I've gotta try, right?
6. I tried. I succeeded. And failed.

### Highly unlikely

I sense a need for:

• Recursion
• Shortest Path (via Depth-First Search, perhaps?)

I doubt I'll be able to solve this part algorithmically.

### But maybe a simulator?

• It may be fun to morph the string in real-time
• But before I do, I need to gain a better understanding of how a user would interact with the parts of the string

### `HOHOHO` in 6 steps

• If I have even the slightest chance at building a simulator, I need to feel confident at solving the non-illustrated example

### The first steps of my molecule

That escalates quickly:

### I've gotta try, right?

Not making a simulator. Solving algorithmically!

I've got an idea:

``````Set steps as Infinity
Recursive function
Expects as parameters:
1. String (gradually increasing in length)
2. Step (number incrementing by 1)
If Step is greater than steps
Make no further recursive calls, because even if it becomes the medicine molecule, it's not the shortest path
Else, if the string is larger than the medicine molecule
Make no further recursive calls
Else, if the string is identical to the medicine molecule
Set steps to the smaller number between steps and Step
Make no further recursive calls
Else - Step is smaller than steps and String is not identical to the medicine molecule
Generate a list of matches for each of the replaceable strings in the String
For each match
Call the recursive function, passing as arguments
1. String with the match replaced
2. Step + 1
``````
• Could this work?
• How many times would the recursive function get called?
• I'm excited to attempt writing it to find out!

### I tried. I succeeded. And failed.

• I wrote the recursive algorithm described above
• It generated the correct answer for Part 2's example, `HOHOHO`: `6` steps!
• Sadly, it never finished running on my puzzle input

Why not?

Because of rules like these:

``````Ca => CaCa
Ti => TiTi
``````

These rules cause my depth-first search algorithm to never get past some cases where the string keeps growing by `CaCaCaCa...`

I tried naively accounting for each case that popped up, but it got to be too much.

At least I tried!

## I did it!

• I solved Part 1!
• I wrote a recursive algorithm that worked on Part 2's example!
• I made some GIFs that helped me understand how successful algorithms might work!

I didn't anticipate attempting - let alone solving - Part 2.

I'm glad I stuck with this puzzle long enough to at least attempt Part 2.

I'm also glad I didn't spend time trying to build a simulator.

I don't think it would have been much fun to use.