DEV Community

Marco Servetto
Marco Servetto

Posted on

Advent of code Day 18

(Note: for more 42, go to:
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 []

Fs = Load:{reuse[]}

Unit = Load:{reuse[]}

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() = 

  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) = {
    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) = (
  mut method S take(S until) = (
    (string,index) = this
    i = string.indexOf(until from=index)
    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) = (
    left = this(t=S",")
    right = this(t=S"]")
SumAll = {class method Tree (Trees that) = {
  (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) = (
    0I.acc()(for e in exp, i in Range(exp.size()) (
  class method Trees expand(Trees that) = \()(
    for a in that for b in that if a.toS()!=b.toS() (
  input = Fs.Real.#$of().read(\"input")
  imm trees = Trees()(for line in input.split( \add(ParseTree(string=line)(t=S"")))
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]
 explode(k,[t1,t2]) = n1,[t1',sumLeft(n2,t2)],0
   n1,t1',n2 = explode(k+1,t1)
 explode(k,[t1,t2]) = 0,[sumRight(n1,t1),t2'],n2
   n1,t2',n2 = explode(k+1,t2)   

 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)