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)
      1. Add 1 to index
      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[0]
      6. Set repeat = markerInput[1]
      7. set repeatedText = the string of characters found in input, numCharacters long, starting at position index
      8. For i = 0 to repeat
        1. Add repeatedText to expandedString
      9. End For
      10. Add numCharacters to index
    2. Else
      1. Add Input[index] to expandedString
      2. Add 1 to index
    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[0]
      5. Set repeat = markerInput[1]
      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)
      1. Add 1 to fileLength
    3. End If
  5. End For
  6. Return fileLength

Note that this function can also solve Part 1, and much more elegantly that I did. Given that only the number of characters is required, there’s no need for the extra overhead in actually generating the output string.

You can find the full solution on Github

Leave a Reply

Your email address will not be published. Required fields are marked *