Advent of Code 2016 Day 9
Part 1
- Same day, different year
- Writing the spec for a loop
- Running each unit test, then my puzzle input
Same day, different year
2017 Day 9 offered a similar-themed challenge: processing a stream of characters.
This time, the unique aspects are:
- Based on the existence of certain characters, the stream length will grow substantially once it's been processed
- All that Part 1 asks for is a length, not the contents of the processed stream - that may make my algorithm less complicated and more performant...since I just have to accumulate a sum instead of a string
Writing the spec for a loop
Set answer to 0
Set pointer to 0
Do as long as pointer is not beyond the length of the input string
Increment answer and pointer depending on the value at pointer:
1. Value is (
Create marker as an empty string
Append to marker one character at a time for all characters after the ( and before the next )
Split the resulting string at the x into an array of two strings
Coerce each string to a number
Increment answer by the product of both numbers
Increment pointer by the sum of the length of marker, the first of the two numbers, and 2
2. Value is anything else
Increment answer by 1
Increment pointer by 1
Return answer
The equation I struggled most to figure out:
Increment pointer by the sum of the length of marker, the first of the two numbers, and 2
After some tinkering in the code, then a break from the code, I discovered the winning ingredients, given how my algorithm works.
Running each unit test, then my puzzle input
- This puzzle graciously offers six unit tests
- I passed the first couple
- But failed a middle one
- Then passed the middle one
- But failed some early ones
- Then fixed my algorithm to become what is shown above
- And passed every unit test
Then, running it on my puzzle input:
- Generated the correct answer!
My core loop in JavaScript:
let answer = 0, pointer = 0
while (pointer < input.length) {
switch (input[pointer]) {
case "(":
let marker = ""
for (let j = pointer + 1; input[j] !== ')'; j++) {
marker += input[j]
}
let [chars, times] = marker.split('x').map(Number)
answer += chars * times
pointer += marker.length + 2 + chars
break;
default:
answer++
pointer++
}
}
return answer
Part 2
- Still just the length, but now...recursion?
- Updating my algorithm to use recursion
- Running each unit test, then my puzzle input
Still just the length, but now...recursion?
So...I guess that's good and bad news.
I've got to study the second example closer:
X(8x2)(3x3)ABCY
-
X
is normal: add1
to sum -
(8x2)
targets(3x3)ABC
- Instead of adding
16
to my sum and moving toY
- I need to
decompress
that bit -
(3x3)
targetsABC
- Attempting to
decompress
it just results in3
- So,
(3x3)ABC
decompressed has length 9 - Instead of
8x2
I now have9x2
=18
- Add
18
to sum then move toY
-
Y
is normal: add1
to sum - Final sum:
1 + 18 + 1 = 20
Hmm. That seems complicated.
But I have a hunch I only have to make a few adjustments to my Part 1 algorithm to get this to work.
Updating my algorithm to use recursion
- My entire algorithm must now become a function
- Instead of incrementing
answer
by the product ofchars
andtimes
, I'll incrementanswer
by the number returned from calling the function, but with the number of characters referenced in the parentheses sliced from the string just afterpointer
I think that's it!
Running each unit test, then on my puzzle input
- This part graciously offers four more unit tests
- I passed them all!
Then, running it on my puzzle input:
- Generated the correct answer!
My new core loop in JavaScript:
function decompress(stream) {
let answer = 0, pointer = 0
while (pointer < input.length) {
switch (input[pointer]) {
case "(":
let marker = ""
for (let j = pointer + 1; input[j] !== ')'; j++) {
marker += input[j]
}
let [chars, times] = marker.split('x').map(Number)
answer += times * decompress(
stream.slice(
pointer + marker.length + 2,
pointer + marker.length + 2 + chars
)
)
pointer += marker.length + 2 + chars
break;
default:
answer++
pointer++
}
}
return answer
}
An animation of how my recursive algorithm works:
I did it!!
- I solved both parts!
- I solved another recursion algorithm puzzle!
- I smartly recognized I should focus on incrementing a sum equivalent to a length, avoiding the trap of accumulating some massive string!
- That strategy saved me from having to re-think my entire algorithm for Part 2!
Top comments (0)