DEV Community

Marco Servetto
Marco Servetto

Posted on

Advent of code Day 18

(Note: for more 42, go to: https://www.youtube.com/MarcoServetto)
Ok, finally I have a solution for day 18.
Those tasks are getting more complex day after day.
This time part 2 was trivial after doing part1.

reuse [L42.is/AdamsTowel]

Fs = Load:{reuse[L42.is/FileSystem]}

Unit = Load:{reuse[L42.is/Unit]}

Tree = {interface [HasToS]
  method I magnitude()
  method Tree reduce()
  }  
Trees = Collection.list(Tree)

Leaf = Class:Trait(Unit(I)):{[Tree]
  method magnitude()=\#inner

  method reduce()={
    if \#inner<10I return this
    half1 = \#inner/2I
    half2 = if half1+half1==\#inner half1 else half1+1I
    return Node(left=This(half1),right=This(half2))
    }
  }  
Node = Data:{[Tree,HasToS]
  Tree left, Tree right

  method toS()=S"[%this.left(),%this.right()]"

  method I magnitude() = 
    (\left.magnitude()*3I)+(\right.magnitude()*2I)

  method reduce()={
    Explode(Tree tree) = Explode(k=0I,t=this)
    if tree.toS()!=this.toS() return tree.reduce()
    Tree split = Split(this)
    if split.toS()!=this.toS() return split.reduce()
    return this
    }
  }
Split = {class method Tree(Tree that)={
  if Node(left,right)=that (
    l = This(left)
    if l.toS()!=left.toS() return Node(left=l,right=right)
    return Node(left=l,right=This(right))
    )
  return that.reduce()
  }}
Explode = Data:{
  I left,Tree tree, I right 
  class method This(I k, Tree t) = {
    if t<:Leaf return This(left=0I,tree=t,right=0I)
    if t<:Node (
      return \node(k=k,t=t)
      )
    error X"exaustive Leaf+Node"
    }
  class method This node4(Node t) = {
    if (Leaf left,Leaf right) = t return This(left=left.#inner(),tree=Leaf"0",right=right.#inner())
    error X"exaustive %t"
    }
  class method This node(I k,Node t) = {
    (left,right)=t
    sLeft  = \stable(k=k+1I,t=left)
    sRight = \stable(k=k+1I,t=right) 
    if sLeft && sRight return This(left=0I,tree=t,right=0I)
    (left1,tree,right2)=This(k=k+1I t=if !sLeft left else right)
    if !sLeft return This(left=left1
    ,,tree=Node(left=tree,right=This.sumLeft(n=right2,t=right)) right=0I)
    return This(left=0I
    ,,tree=Node(left=This.sumRight(n=left1,t=left),right=tree) right=right2)
    }
  class method Bool stable(I k, Tree t) = {
    if Node(left,right)=t return k!=4I && \stable(k=k+1I,t=left) && \stable(k=k+1I, t=right)
    return Bool.true()
    }
   class method Tree sumLeft(I n,Tree t) = {
     if t<:Leaf return t+Leaf(n)
     if Node(left,right)=t return Node(left=this.sumLeft(n=n,t=left),right=right)
     error X"exaustive"
     }
   class method Tree sumRight(I n,Tree t) = {
     if t<:Leaf return t+Leaf(n)
     if Node(left,right)=t return Node(left=left, right=this.sumRight(n=n,t=right))
     error X"exaustive"
     }
  }
ParseTree = Data:{
  S string
  var I index = 0I
  mut method Bool check(S that) = 
    \string.startsWith(that leftOffSet=this.index())
  mut method Void pop(S that) = (
     X[this.check(that)]
     \index(\index+that.size())
     )
  mut method S take(S until) = (
    (string,index) = this
    i = string.indexOf(until from=index)
    \index(i)
    string.subString(index to=i)
    )
  mut method Tree(S t) = 
    if !\check(S"[") \leaf(t=t) else \node(t=t)

  mut method Leaf leaf(S t) = \(string=this.take(until=t))

  mut method Node node(S t) = (
    \pop(S"[")
    left = this(t=S",")
    \pop(S",")
    right = this(t=S"]")
    \pop(S"]")
    Node(left=left,right=right)
    )
  }
SumAll = {class method Tree (Trees that) = {
  X[!that.isEmpty()]
  (size,left,withoutLeft) = that
  if size==1I return left
  res  = Node(left=left,right=withoutLeft.left()).reduce()
  return This(withoutLeft.with(left=res))
  }}
SumMax = {
  class method I (Trees that) = (
    exp=This.expand(that)
    0I.acc()(for e in exp, i in Range(exp.size()) (
      \val(\val.max(e.reduce().magnitude()))
      ))
    )
  class method Trees expand(Trees that) = \()(
    for a in that for b in that if a.toS()!=b.toS() (
      \add(Node(left=a,right=b))
      ))
  }
Main=(
  input = Fs.Real.#$of().read(\"input")
  imm trees = Trees()(for line in input.split(S.nl()) \add(ParseTree(string=line)(t=S"")))
  all=SumAll(trees)
  Debug(all.magnitude())//3647
  max=SumMax(trees)
  Debug(max)//4600
  )
Enter fullscreen mode Exit fullscreen mode

Now, figuring out the explosion algorithm was quite challenging, and I had to switch using the 'formal language' that is commonly used for designing programming languages.
If you are curious, here is explode in formalism:

 #define explode(k,t) = n1 t n2 //0 if none
 explode(k,n) = empty,n,empty
 explode(4,[n1,n2]) = n1,0,n2
 explode(k,[t1,t2]) = [t1,t2]
   k!=4
   stable(k,t1)
   stable(k,t2)
 explode(k,[t1,t2]) = n1,[t1',sumLeft(n2,t2)],0
   k!=4
   !stable(k,t1)
   n1,t1',n2 = explode(k+1,t1)
 explode(k,[t1,t2]) = 0,[sumRight(n1,t1),t2'],n2
   k!=4
   stable(k,t1)
   !stable(k,t2)
   n1,t2',n2 = explode(k+1,t2)   

 stable(k,n)
 stable(k,[t1,t2]) = k!=4 && stable(k+1,t1) && stable(k+1,t2)

 sumLeft(n0,n) = n+n0
 sumLeft(n0,[t1,t2]) = [sumLeft(n0,t1),t2]
 sumRight(n0,n) = n+n0
 sumRight(n0,[t1,t2]) = [t1,sumRight(n0,t2)]
Enter fullscreen mode Exit fullscreen mode

As you can see, I'm using a functional approach to do the reduction.
I'm not sure if a 'mutation' based approach would have been easier.

Top comments (0)