# 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 =~ /[A-Z]/
uncompressed += compressed
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 == :plain
node
else
node * traverse(node)
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.