Skip to content

Commit 00a6053

Browse files
LiquidFunLiquidFun
committed
Add day 18
1 parent 0e369c6 commit 00a6053

File tree

5 files changed

+241
-0
lines changed

5 files changed

+241
-0
lines changed

‎2021/18/18.jl

Lines changed: 127 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,127 @@
1+
mutable struct Tree
2+
parent
3+
left
4+
right
5+
end
6+
7+
function Tree(parent)
8+
Tree(parent, nothing, nothing)
9+
end
10+
11+
function Base.show(io::IO, tree::Tree)
12+
tree isa Number && return print(tree)
13+
print("[")
14+
print(tree.left)
15+
print(",")
16+
print(tree.right)
17+
print("]")
18+
end
19+
20+
function make_tree(list, parent=nothing)
21+
list isa Number && return list
22+
curr = Tree(parent)
23+
curr.left = make_tree(list[1], curr)
24+
curr.right = make_tree(list[2], curr)
25+
return curr
26+
end
27+
28+
function explode(curr, left_leaf, right_leaf)
29+
if left_leaf != nothing
30+
left_leaf.right isa Number ? left_leaf.right += curr.left : left_leaf.left += curr.left
31+
end
32+
if right_leaf != nothing
33+
right_leaf.left isa Number ? right_leaf.left += curr.right : right_leaf.right += curr.right
34+
end
35+
if curr.parent.left === curr
36+
curr.parent.left = 0
37+
else
38+
curr.parent.right = 0
39+
end
40+
return true
41+
end
42+
43+
function find_leaves(curr, depth=0)
44+
curr isa Number && return []
45+
mid = curr.left isa Number || curr.right isa Number ? [(depth, curr)] : []
46+
vcat(find_leaves(curr.left, depth+1), mid, find_leaves(curr.right, depth+1))
47+
end
48+
49+
function find_next_explode(tree)
50+
leaves = vcat([(0, nothing)], find_leaves(tree), [(0, nothing)])
51+
for i in eachindex(leaves)
52+
if leaves[i][1] >= 4 && leaves[i][2].left isa Number && leaves[i][2].right isa Number
53+
return explode(leaves[i][2], leaves[i-1][2], leaves[i+1][2])
54+
end
55+
end
56+
return false
57+
end
58+
59+
function find_next_split(tree)
60+
found_split = false
61+
should_split(num) = num isa Number && num > 9
62+
function split_descend(curr)
63+
split_up(num) = Tree(curr, num ÷ 2, num - num ÷ 2)
64+
curr isa Number && return false
65+
found_split && return true
66+
should_split(curr.left) && (curr.left = split_up(curr.left)) != 1 && return found_split = true
67+
split_descend(curr.left) && return true
68+
should_split(curr.right) && (curr.right = split_up(curr.right)) != 1 && return found_split = true
69+
split_descend(curr.right) && return true
70+
return false
71+
end
72+
return split_descend(tree)
73+
end
74+
75+
function reduce_tree(tree)
76+
i = 0
77+
while true
78+
find_next_explode(tree) && continue
79+
find_next_split(tree) && continue
80+
return tree
81+
end
82+
end
83+
84+
function merge_trees(left_tree, right_tree)
85+
new_root = Tree(nothing)
86+
left_tree.parent = new_root
87+
right_tree.parent = new_root
88+
new_root.left = left_tree
89+
new_root.right = right_tree
90+
return new_root
91+
end
92+
93+
function add_trees(tree1, tree2)
94+
merge_trees(tree1, tree2) |> reduce_tree
95+
end
96+
97+
function magnitude(tree)
98+
tree isa Number && return tree
99+
return 3magnitude(tree.left) + 2magnitude(tree.right)
100+
end
101+
102+
function solve_part1(trees)
103+
curr = trees[1]
104+
for next in trees[2:end]
105+
merged = merge_trees(curr, next)
106+
curr = reduce_tree(merged)
107+
end
108+
println(magnitude(curr))
109+
end
110+
111+
function solve_part2(trees)
112+
best = 0
113+
for t1 in trees, t2 in trees
114+
if !(t1 == t2)
115+
best = max(best, add_trees(deepcopy(t1), deepcopy(t2)) |> magnitude)
116+
end
117+
end
118+
println(best)
119+
end
120+
121+
function main()
122+
trees = readlines() .|> Meta.parse .|> eval .|> make_tree
123+
solve_part1(deepcopy(trees))
124+
solve_part2(deepcopy(trees))
125+
end
126+
127+
main()

‎2021/18/example.ans

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,2 @@
1+
4140
2+
3993

‎2021/18/example.in

Lines changed: 10 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,10 @@
1+
[[[0,[5,8]],[[1,7],[9,6]]],[[4,[1,2]],[[1,4],2]]]
2+
[[[5,[2,8]],4],[5,[[9,9],0]]]
3+
[6,[[[6,2],[5,6]],[[7,6],[4,7]]]]
4+
[[[6,[0,7]],[0,9]],[4,[9,[9,0]]]]
5+
[[[7,[6,4]],[3,[1,3]]],[[[5,5],1],9]]
6+
[[6,[[7,3],[3,2]]],[[[3,8],[5,7]],4]]
7+
[[[[5,4],[7,7]],8],[[8,3],8]]
8+
[[9,3],[[9,9],[6,[4,9]]]]
9+
[[2,[[7,7],7]],[[5,8],[[9,3],[0,2]]]]
10+
[[[[5,2],5],[8,[3,7]]],[[5,[7,5]],[4,4]]]

‎2021/18/input.ans

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,2 @@
1+
3494
2+
4712

‎2021/18/input.in

Lines changed: 100 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,100 @@
1+
[[[[3,9],[0,5]],[4,6]],3]
2+
[[[8,[3,0]],[[8,4],[9,4]]],[[[0,9],4],[[3,8],2]]]
3+
[3,[3,[[2,8],[1,4]]]]
4+
[8,[[3,6],[[8,9],[4,1]]]]
5+
[[3,[[5,8],[3,3]]],[[[9,3],[6,3]],[[7,0],[8,8]]]]
6+
[[6,[[5,8],7]],[8,[[1,6],7]]]
7+
[[[[8,6],[9,3]],[3,[2,7]]],[[[6,7],[2,8]],[6,7]]]
8+
[[[9,[1,6]],0],[[7,3],[2,4]]]
9+
[[[[4,9],3],6],[[7,5],8]]
10+
[[[[8,3],8],[2,[6,5]]],[[6,[1,9]],[0,2]]]
11+
[[[9,9],[[9,8],1]],[[[7,4],[1,4]],[[1,1],4]]]
12+
[[5,[[8,2],[8,6]]],[9,[7,[8,9]]]]
13+
[[4,6],[8,[3,[1,2]]]]
14+
[[[2,[7,9]],7],[[2,0],[9,2]]]
15+
[[4,9],[[[3,4],[2,9]],5]]
16+
[[[[0,0],[3,7]],[[6,1],8]],[[[4,0],4],8]]
17+
[[4,[[8,9],[2,2]]],[[[1,8],[2,7]],[[6,8],0]]]
18+
[[7,5],[[7,0],1]]
19+
[[[5,[1,0]],1],[[[7,7],[2,2]],[[4,2],8]]]
20+
[[[7,1],[7,3]],[2,0]]
21+
[[[[6,2],3],[3,[5,2]]],[[7,2],[[9,5],[0,1]]]]
22+
[[[[0,3],2],6],9]
23+
[[[9,8],[[7,8],[5,9]]],[[[4,8],[0,2]],[[6,8],[2,3]]]]
24+
[2,[[3,7],9]]
25+
[[[9,9],1],[7,[7,[5,8]]]]
26+
[[8,[1,1]],[8,8]]
27+
[[[[3,3],[1,4]],[[5,3],4]],[5,2]]
28+
[[[[0,9],1],[[3,8],8]],[9,[[8,8],[0,7]]]]
29+
[[[9,4],1],[[9,7],[[6,1],[9,5]]]]
30+
[[[1,[4,0]],9],[[3,7],2]]
31+
[[[5,[0,5]],[5,[9,2]]],[[[2,2],[8,0]],[3,[7,8]]]]
32+
[[[[8,2],3],3],[[[5,4],[0,5]],9]]
33+
[[[3,[6,2]],0],[[[7,3],[6,3]],[[6,3],2]]]
34+
[[6,1],[[[1,2],2],[9,4]]]
35+
[[[1,[9,0]],[[8,2],[4,9]]],[[0,[9,6]],[[0,4],[4,0]]]]
36+
[9,[4,[7,0]]]
37+
[[7,2],[[9,5],8]]
38+
[[6,[[0,6],0]],[[[2,0],[4,1]],[[9,5],4]]]
39+
[[[6,[0,0]],5],[[[5,2],[7,3]],[[2,8],[3,2]]]]
40+
[[[2,7],[[8,2],2]],[[5,[0,6]],[[9,8],[0,4]]]]
41+
[[[8,9],[[4,1],2]],[[[3,4],[4,5]],[[7,4],0]]]
42+
[[5,[2,[2,1]]],[[5,6],[[6,2],[3,0]]]]
43+
[[8,[0,0]],[[6,1],[9,[1,3]]]]
44+
[[[9,[5,8]],5],[[8,[6,6]],[7,5]]]
45+
[3,2]
46+
[[8,[[6,3],[8,4]]],[[2,7],[8,[9,5]]]]
47+
[[[4,[9,1]],[[3,6],[8,8]]],[[[9,0],6],[[3,7],6]]]
48+
[[9,[[4,9],6]],[[8,2],[1,3]]]
49+
[[[2,[4,3]],[[5,6],[7,3]]],7]
50+
[[[[0,1],7],[[9,1],9]],[[[0,1],[6,5]],1]]
51+
[[[7,[5,3]],[[6,6],6]],[[2,7],3]]
52+
[[1,[[5,8],[1,7]]],[[[5,0],[4,7]],[[3,3],[3,7]]]]
53+
[[[[8,8],[2,6]],[1,2]],[[[2,6],4],[1,[1,8]]]]
54+
[5,[[8,[8,2]],0]]
55+
[[6,[[5,9],[8,4]]],[7,[5,9]]]
56+
[[7,3],[[[2,5],4],[[1,1],8]]]
57+
[[[0,1],7],[0,8]]
58+
[[7,[6,6]],[2,9]]
59+
[[[[1,9],1],[[4,8],5]],[[0,[8,3]],[[0,9],[1,5]]]]
60+
[[[0,9],[[6,7],5]],[4,[[1,1],[0,6]]]]
61+
[[[6,1],7],[[[1,4],8],[[9,0],4]]]
62+
[5,[3,[[0,7],[4,9]]]]
63+
[[[[6,0],[1,5]],[[1,5],1]],[[1,[7,1]],[[6,2],7]]]
64+
[[[9,0],8],[[[4,1],[5,4]],[4,[5,1]]]]
65+
[3,[5,9]]
66+
[6,[6,5]]
67+
[[1,[8,0]],[9,0]]
68+
[[[[1,8],3],0],[7,[[0,8],6]]]
69+
[[[[4,2],2],3],[[2,5],[[9,2],4]]]
70+
[[1,[[1,1],[8,4]]],[[[8,1],0],[0,2]]]
71+
[[[[0,7],[8,7]],[9,6]],0]
72+
[[3,7],[[1,[0,9]],[1,[7,6]]]]
73+
[[[[3,5],[4,6]],[[7,1],[8,0]]],6]
74+
[[7,[5,[7,7]]],[4,[5,3]]]
75+
[1,[[[0,0],[4,6]],[7,[1,9]]]]
76+
[[[3,7],[7,[0,6]]],[7,[5,3]]]
77+
[[[[5,3],0],2],[[[2,7],[7,9]],[[1,4],3]]]
78+
[[[[8,3],9],[[8,3],[7,4]]],[[4,[6,0]],[7,[3,7]]]]
79+
[[[6,[5,0]],8],[[[4,5],3],[1,[5,9]]]]
80+
[[7,8],[[6,8],[[8,4],[3,1]]]]
81+
[[[2,7],[6,3]],[[0,0],4]]
82+
[[1,[[6,5],[4,8]]],[[8,[2,7]],[[7,8],[6,8]]]]
83+
[[[2,3],[7,7]],[0,[3,3]]]
84+
[5,[[2,8],[2,[6,9]]]]
85+
[[[[6,3],2],[[2,8],9]],[[[5,6],[8,0]],[[9,3],[5,0]]]]
86+
[[[[6,2],7],[6,1]],[[[5,9],4],4]]
87+
[[[[7,2],[0,4]],[[6,7],7]],[6,[[8,5],[9,0]]]]
88+
[[[[9,6],8],[2,[3,7]]],6]
89+
[[0,[[1,0],4]],[5,[[7,4],[2,4]]]]
90+
[[[[4,4],[4,7]],[[7,4],3]],5]
91+
[[[[8,2],[0,3]],[[7,2],1]],[[7,[1,2]],6]]
92+
[[[3,8],[3,1]],[7,7]]
93+
[[[6,5],[[8,7],4]],3]
94+
[[7,[2,[2,5]]],[9,1]]
95+
[9,2]
96+
[[4,[2,9]],[[4,[2,9]],0]]
97+
[[[0,2],[[2,1],[9,2]]],[[6,[8,2]],[4,[3,8]]]]
98+
[1,[[[2,2],6],[[3,5],6]]]
99+
[[[9,[4,8]],[1,4]],[4,[1,[9,1]]]]
100+
[[[8,0],[[8,4],3]],9]

0 commit comments

Comments
 (0)