-
Notifications
You must be signed in to change notification settings - Fork 1
/
day18.jl
106 lines (95 loc) · 2.6 KB
/
day18.jl
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
module Day18
using AdventOfCode2020
function day18(input::String = readInput(joinpath(@__DIR__, "..", "data", "day18.txt")))
sinput = split(rstrip(input), "\n")
tokens = tokenize.(sinput)
return [evaluate.(tokens) |> sum, evaluate.(tokens; plusfirst = true) |> sum]
end
function tokenize(inp::AbstractString)
tokens = Array{Union{Char,Int},1}()
i = 1
while i <= length(inp)
if isdigit(inp[i])
m = match(r"(\d+)", inp[i:end])
push!(tokens, parse(Int, m[1]))
i += length(m[1])
continue
elseif inp[i] in ('+', '*', '(', ')')
push!(tokens, inp[i])
end
i+= 1
end
return tokens
end
Base.isinteger(::Char) = false
function evaluate(token::Array{Union{Char,Int},1}; plusfirst = false)
stack = []
levels = Array{Int,1}()
level = 0
for t in token
if isinteger(t)
push!(stack, t)
push!(levels, level)
elseif t == '+'
push!(stack, +)
push!(levels, level)
elseif t == '*'
push!(stack, *)
push!(levels, level)
elseif t == '('
level += 1
elseif t == ')'
level -= 1
end
end
return evalstack!(stack, levels; plusfirst = plusfirst)
end
function evalstack!(stack::Array{Any,1}, levels::Array{Int,1}; plusfirst = false)
M = maximum(levels)
M == 0 && return evalstack!(stack; plusfirst = plusfirst)
ns = []
nl = Array{Int,1}()
i = j = 1
while i <= length(stack)
if levels[i] < M
push!(ns, stack[i])
push!(nl, levels[i])
i += 1
else
j = i
while j <= length(stack) && levels[j] == M
j += 1
end
res = evalstack!(stack[i:j-1]; plusfirst = plusfirst)
push!(ns, res)
push!(nl, M - 1)
i = j
end
end
return evalstack!(ns, nl; plusfirst = plusfirst)
end
function evalstack!(stack::Array{Any,1}; plusfirst = false)
isempty(stack) && return
if plusfirst
tmpstack = []
push!(tmpstack, popfirst!(stack))
while !isempty(stack)
n1 = pop!(tmpstack)
op = popfirst!(stack)
n2 = popfirst!(stack)
if op == +
push!(tmpstack, op(n1, n2))
else
push!(tmpstack, n1, op, n2)
end
end
stack = tmpstack
end
s = popfirst!(stack)
while !isempty(stack)
op = popfirst!(stack)
s = op(s, popfirst!(stack))
end
return s
end
end # module