Advent of Code 2015 Day 19
Part 1
- Can this be solved with just
matchAll()
? - How about with
reduce()
,matchAll()
,slice()
,Set()
? - 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
- Highly unlikely
- But maybe a simulator?
-
HOHOHO
in 6 steps - The first steps of my molecule
- I've gotta try, right?
- 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
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.
Top comments (1)
In today's world, health care is becoming increasingly important, and treatment can play a key role in ensuring that it is maintained. It is important to have access to quality healthcare services, such as those provided by curaveindoctors.com/ , that help maintain and improve our physical and mental well-being. Support from professional specialists can be an important step in managing your health and improving your quality of life.