## DEV Community 👩‍💻👨‍💻 is a community of 963,673 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

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]

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


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)]


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.