Medicine for Rudolph

Advent of Code 2015 Day 19

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()?

Sadly, I don't think so.

• 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 => {
        distincts.add(
          molecule.slice(0, match) + 
          rule[1] + 
          molecule.slice(match + rule[0].length)
        )
      }
    )
    return distincts
  }, new Set()).size
}

It generated the correct answer!

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.