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
ABBBBBC. If one marker covers another one, the nested one is not decompressed. For example,
(6x1)(1x3)A will be decompressed to
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.
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
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.
traverse method is iterating over list of nodes and calculating the actual length. In case of :multiply nodes it is recursively multiplying them together.