Advent of Code 2016 Day9: Explosives in Cyberspace

This is a series of programming challenges for beginners and experienced Caché programmers.

For an introduction : go to article

Today's challenge is about decompressing input that is compressed in an experimental format.
In the format, markers indicate how much time a number of characters need to be repeated.

For example :

A(1x5)BC repeats only the B a total of 5 times, becoming ABBBBBC for a decompressed length of 7.
(3x3)XYZ becomes XYZXYZXYZ for a decompressed length of 9.
A(2x2)BCD(2x2)EFG doubles the BC and EF, becoming ABCBCDEFEFG for a decompressed length of 11.
(6x1)(1x3)A simply becomes (1x3)A - the (1x3) looks like a marker, but because it's within a data section of another marker, it is not treated any differently from the A that comes after it. It has a decompressed length of 6.
X(8x2)(3x3)ABCY becomes X(3x3)ABC(3x3)ABCY (for a decompressed length of 18), because the decompressed data from the (8x2) marker (the (3x3)ABC) is skipped and not processed further.

For the complete explanation of the challenge, go to

Your input is found here :, you have to output the total length of the decompressed input.

Here is Bert's code as a routine :

Start() PUBLIC {
  #Dim objFileStream As %Stream.FileCharacter
objFileStream = ##Class(%Stream.FileCharacter).%New()

  while 'objFileStream.AtEnd {
result =$$decompressCount(line)
!,"part 1:",*9,result

decompressCount(Data) PUBLIC {
  for i=1:1:$LENGTH(Data) {
    if $EXTRACT(Data,i)="(" {
else {

The second part of the challenge is a next version of the compress format : if there are markers in the decompressed section, they have to be decompressed as well.

For example :

(3x3)XYZ still becomes XYZXYZXYZ, as the decompressed section contains no markers.
X(8x2)(3x3)ABCY becomes XABCABCABCABCABCABCY, because the decompressed data from the (8x2) marker is then further decompressed, thus triggering the (3x3) marker twice for a total of six ABC sequences.
(27x12)(20x12)(13x14)(7x10)(1x12)A decompresses into a string of A repeated 241920 times.
(25x3)(3x3)ABC(2x3)XY(5x2)PQRSTX(18x9)(3x2)TWO(5x7)SEVEN becomes 445 characters long.


What is length of the decompressed input using this decompression version 2 ?

Here is my code in a class that can decompress the two versions : by using recursion, we can reuse much of the code of the first part :

Class AOC2016.Day9 Extends AOC2016.Utils

  ClassMethod Part(file As %String = "day9.txt", version As %Integer = 1)
    #Dim input as %String
    #Dim iInput as %Integer
    #Dim totalLength as %Integer = 0
    Try {
      Do ..Input(file, .input)
      For iInput=1:1:input {
        Set totalLength=totalLength+..Decompress(input(iInput), version)
Catch {
      Write "Error : ",$ZError,!
    Write "Total length : ",totalLength,!

  ClassMethod Decompress(line, version As %Integer = 1) As %Integer
    #Dim totalLength as %Integer = 0
    #Dim marker as %String
    #Dim length, times, firstPos, lastPos as %Integer
    For  {
      If line="" Quit
      Set firstPos=$Locate(line,"\(\d*x\d*\)",,lastPos,marker)
      If firstPos>0 {
        set totalLength=totalLength+firstPos-1
        set length=+$E(marker,2,*)
        set times=+$Piece(marker,"x",2)
        Set line=$Extract(line,lastPos,*)
        Set totalLength=totalLength+(times*$Select(version=1:length,1:..Decompress($Extract(line,1,length),version)))
        Set line=$Extract(line,length+1,*)
else {
        set totalLength=totalLength+$length(line)
        set line = ""
    Quit totalLength



Look here for all our solutions so far : and

Here is the list of all Advent of Code 2016 articles  :

1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20  21  22  23  24  25 


Interesting, you decided to use a regex here. My code looks very similar to your, but in my case, I just replaced parens and 'x' to '|' and use $lb/$lfs to catch values.

  set fs = ##Class(%Stream.FileCharacter).%New()
  set sc=fs.LinkToFile("c:\development\day9.txt")
  set compressed = fs.Read(fs.Size)
  set compressed = $tr(compressed, "(x)", "|||")
  write !,"Length = ",$$uncompress(compressed)
  write !,"Full Length = ",$$uncompress(compressed, 1)
uncompress(str, deep = 0) public {
  set length = 0
  while $l(str) {
    if $e(str)="|" {
      set $lb(,count,times)=$lfs($p(str, "|", 1, 3), "|")
      set $e(str, 1, $l($p(str, "|", 1, 3)) + 1) = ""
      set tmp = $e(str, 1, count)
      set length = length + $s(deep:$$uncompress(tmp,1) * times, 1: count * times)
      set $e(str, 1, count) = ""
    else {
      set size = $l($p(str, "|"))
      if $i(length, size)
      set $e(str, 1, size) = ""
  quit length

Your use of Set $listbuild was unknown to me : i only used it on the right hand side (like Set var = $lb(...) ), but on the left-hand side, it is ideal to set a bunch of variables in the same instruction, cool !

and using $lb on a right side, can help, when you need to swap values without using the third variable.

set $lb(b,a)=$lb(a,b)