Advent of Code 2016, Day 9: Explosives in Cyberspace

Part A

On Day 9 we need to implement decompression algorithm. Compressed strings can look like this:

ADVENT
A(1x5)BC
(3x3)XYZ
(6x1)(1x3)A

If you see repetition marker like this (3x4), you need to take 3 subsequent characters and repeat them 4 times. So A(1x5)BC becomes ABBBBBC. If one marker covers another one, the nested one is not decompressed. For example, (6x1)(1x3)A will be decompressed to (1x3)A.

Here is my solution:

compressed = File.read("9.txt").strip
uncompressed = ""

while compressed.size > 0
  if compressed[0] =~ /[A-Z]/
    uncompressed += compressed[0]
    compressed = compressed[1..]
  elsif match = compressed.match(/\((\d+)x(\d+)\)/)
    length, times = match.captures.map(&:to_i)
    match_begin = match.begin(0)
    match_end = match.end(0)

    part = compressed[match_end, length] * times

    uncompressed += part
    compressed = compressed[(match_end + length)..]
  end
end

puts uncompressed
puts uncompressed.size

Here we extract leading characters from the string. If it is A-Z character we add it just like that to the decompressed string. If it is a repetition marker, we extract subsequent characters and add them to the decompressed string multiplied given amount of times.

It is not the most efficient solution. I just hacked it quickly to get the answer. It would be better not to modify the compressed string, just advance the pointer to the current position.

Part B

In the second part, the “nested” markers should also be decompressed. This can significantly increase the size of decompressed string. We need to pass the length of decompressed string, but decompressing it is not feasible.

Here is my solution:

compressed = File.read("9.txt").strip

def parse(string)
  nodes = []

  while string.size > 0
    if string =~ /^[A-Z]+/
      match = Regexp.last_match
      match_begin = match.begin(0)
      match_end = match.end(0)

      nodes.push([:plain, match_end - match_begin, string[match_begin...match_end]])

      string = string[match_end..]
    elsif string =~ /^\((\d+)x(\d+)\)/
      match = Regexp.last_match
      length, times = match.captures.map(&:to_i)
      match_begin = match.begin(0)
      match_end = match.end(0)

      nodes.push([:multiply, times, parse(string[match_end, length])])

      string = string[(match_end + length)..]
    end
  end

  nodes
end

def traverse(nodes)
  nodes.map do |node|
    if node[0] == :plain
      node[1]
    else
      node[1] * traverse(node[2])
    end
  end.sum
end

nodes = parse(compressed)
size = traverse(nodes)
puts size

Our parse method is scanning the string recursively and returning a list of nodes that can be nested. For plain strings it returns plain nodes. In case of repetition markers it is trying to parse them recursively and returns nested lists of nodes. For string X(8x2)(3x3)ABCY it will return [[:plain, 1, "X"], [:multiply, 2, [[:multiply, 3, [[:plain, 3, "ABC"]]]]], [:plain, 1, "Y"]]. You can see that there are is nested node with :multiply, :multiply and :plain.

Then traverse method is iterating over list of nodes and calculating the actual length. In case of :multiply nodes it is recursively multiplying them together.