-
Notifications
You must be signed in to change notification settings - Fork 0
/
day23.jl
121 lines (109 loc) · 4.1 KB
/
day23.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
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
module Day23
using AdventOfCode2023
function day23(input::String = readInput(joinpath(@__DIR__, "..", "data", "day23.txt")))
data = map(x -> x[1], reduce(vcat, permutedims.(map(x -> split(x, ""), split(input)))))
start = CartesianIndex(1, findfirst(x -> x == '.', data[begin, :]))
goal = CartesianIndex(size(data, 1), findfirst(x -> x == '.', data[end, :]))
return [part1(data, start, goal), part2(data, start, goal)]
end
function part1(data::Matrix{Char}, start::CartesianIndex{2}, goal::CartesianIndex{2})
next = generate_next_p1(data)
graph = build_graph(start, goal, next)
return find_longest_path(start, goal, graph)
end
function part2(data::Matrix{Char}, start::CartesianIndex{2}, goal::CartesianIndex{2})
next = generate_next_p2(data)
graph = build_graph(start, goal, next)
return find_longest_path(start, goal, graph)
end
function generate_next_p1(data::Matrix{Char})
next = Dict{CartesianIndex{2}, Vector{CartesianIndex{2}}}()
dirs = CartesianIndex.((1, 0, -1, 0), (0, -1, 0, 1))
empty_idx = findall(x -> x == '.', data)
for ind ∈ empty_idx
v = CartesianIndex{2}[]
for d ∈ dirs
c = ind + d
if checkbounds(Bool, data, c) && data[c] != '#'
push!(v, c)
end
end
next[ind] = v
end
chars_dirs = (('v', CartesianIndex(1, 0)), ('^', CartesianIndex(-1, 0)), ('>', CartesianIndex(0, 1)), ('<', CartesianIndex(0, -1)))
for (c, d) ∈ chars_dirs
idx = findall(x -> x == c, data)
for ind ∈ idx
next[ind] = [ind + d]
end
end
return next
end
function generate_next_p2(data::Matrix{Char})
next = Dict{CartesianIndex{2}, Vector{CartesianIndex{2}}}()
dirs = CartesianIndex.((1, 0, -1, 0), (0, -1, 0, 1))
idx = findall(x -> x ∈ ('.', 'v', '^', '>', '<'), data)
for ind ∈ idx
v = CartesianIndex{2}[]
for d ∈ dirs
c = ind + d
if checkbounds(Bool, data, c) && data[c] != '#'
push!(v, c)
end
end
next[ind] = v
end
return next
end
function build_graph(start::CartesianIndex{2}, goal::CartesianIndex{2}, next::Dict{CartesianIndex{2}, Vector{CartesianIndex{2}}})
nodes = Set(findall(v -> length(v) > 2, next))
push!(nodes, start)
push!(nodes, goal)
graph = Dict{CartesianIndex{2},Dict{CartesianIndex{2},Int}}()
for node ∈ nodes
graph[node] = Dict{CartesianIndex{2},Int}()
for path_option ∈ next[node]
visited = Set([node])
last = path_option
while true
push!(visited, last)
if last ∈ nodes
graph[node][last] = length(visited) - 1
break
end
found = false
for l ∈ next[last]
if l ∉ visited
found = true
last = l
break
end
end
!found && break
end
end
end
return graph
end
function find_longest_path(start::CartesianIndex{2}, goal::CartesianIndex{2}, graph::Dict{CartesianIndex{2},Dict{CartesianIndex{2},Int}})
order = Dict{CartesianIndex{2},Int}()
for (i, elem) ∈ enumerate(keys(graph))
order[elem] = i
end
visited = Int64(1) << order[start]
max_length = Int[0]
longest_path!(max_length, visited, start, 0, goal, graph, order)
return max_length[1]
end
function longest_path!(max_length::Vector{Int}, visited::Int64, last::CartesianIndex{2}, current_length::Int, goal::CartesianIndex{2}, graph::Dict{CartesianIndex{2},Dict{CartesianIndex{2},Int}}, order::Dict{CartesianIndex{2}, Int})
if last == goal && current_length > max_length[begin]
max_length[begin] = current_length
return
end
for next_node ∈ keys(graph[last])
if visited >> order[next_node] & 1 != 1
longest_path!(max_length, visited + 1 << order[next_node], next_node, current_length + graph[last][next_node], goal, graph, order)
end
end
end
end # module