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)

πŸ‘‹ Hey, my name is Noah and I’m the one who set up this ad. My job is to get you to join DEV, so if you fancy doing me a favor, I’d love for you to create an account.

If you found DEV from searching around, here are a couple of our most popular articles on DEV: