Advent of Code: Day 9 Solution

This year, I’m posting my solutions to the puzzles in the Advent of Code. Each post will consist of pseudocode, with a link to the actual code I used to solve the puzzle on Github.

And now, on with the solution:

Day 9, part 1

Simplified problem: You are given an input where strings in the pattern (0x1) where 0 and 1 are any number (there is no limit to the number).

Where this pattern is encountered, the number of characters represented in the 0 portion are repeated a number of times specified in the 1 portion. The first character repeated is directly after the closing bracket. Repeat markers in the repeating string are ignored. What is the length after the markers have been processed?

After processing the input, what is the length of the string?

Solution

1. Set input = (your input)
2. Remove all white space (spaces, tabs and newlines) from input
3. Set expandedString = nothing
4. Set index=0
5. While index is less than input length
1. If Input[index] = “(“ (start of repeat marker)
2. Set markerEndIndex = the first position of the matching “)”
3. Set markerInput = the text between index and markerEndIndex-1
4. Split markerInput on the ‘x’ character
5. Set numCharacters = markerInput
6. Set repeat = markerInput
7. set repeatedText = the string of characters found in input, numCharacters long, starting at position index
8. For i = 0 to repeat
9. End For
2. Else
3. End If
6. End While
7. Return length of expandedString

Day 9, part 2

Using the same rules and input as in Part 1, expand the string using all repeat markers, including those that fall within the repeated text.

If a repeat marker is found inside text to be repeated, that repeat marker is processed first, and the resulting string is then used for generating the expanded text.

Solution

I wracked my brain on this puzzle, but could not figure out the recursive nature. After half a day, I buckled and checked the Day 9 solutions thread on the AOC subreddit.

I found a solution that was very similar to the one I was working on by user LoupieG which I modified ever so slightly, and heavily commented to ensure I knew how it works. All credit to this solution should go to him/her.

1. Set input = (your input)
2. Remove all white space (spaces, tabs and newlines) from input
3. Set fileLength=0
4. For index=0 to input length
1. If Input[index] = “(“ (start of repeat marker)
1. Set markerEndIndex = the first position of the matching “)” after index
2. Set markerInput = the text between index and markerEndIndex-1
3. Split markerInput on the ‘x’ character
4. Set numCharacters = markerInput
5. Set repeat = markerInput
6. Set nextPosition=markerEndIndex + numCharacters
7. Set repeatCharacters=characters between markerEndIndex+1 and numCharacters
8. If repeatCharacters contains a “(”
1. Set input=repeatCharacters
2. Go to step 1 and follow these steps using repeatCharacters as the input (recursive call), then return here.
3. Add the result from Step 8.2 to fileLength
9. Else
1. Add (numCharacters * repeat) to fileLength
10. End If
11. Set index=nextPosition
2. Else (no repeat marker found at this position)