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
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
|
import adglent.{First, Second}
import gleam/bool
import gleam/dict.{type Dict}
import gleam/io
import gleam/list
import gleam/result
import gleam/string
import gleam/set.{type Set}
import utilities/array2d.{type Posn, Posn}
import utilities/prioqueue.{type PriorityQueue}
type State {
State(posn: Posn, heatloss: Int, previous: Posn, history: List(Posn))
}
const deltas = [Posn(-1, 0), Posn(1, 0), Posn(0, -1), Posn(0, 1)]
fn make_key(s: State) {
#(s.posn, same_dir(s))
}
fn same_dir(s: State) {
case s.history {
[] -> []
[first, ..] as deltas ->
list.take_while(deltas, fn(d) { d == first })
|> list.take(10)
}
}
fn is_goal(s: State, min_run: Int, goal: Posn) {
goal == s.posn && list.length(same_dir(s)) >= min_run
}
fn find_good_neighbors(max: Int, min: Int, s: State, grid) {
deltas
|> list.filter(eliminate_bad_neighbors(_, s, max, min, grid))
|> list.map(make_state(_, s, grid))
}
fn eliminate_bad_neighbors(d: Posn, s: State, max, min, grid) {
let neighbor = array2d.add_posns(d, s.posn)
use <- bool.guard(
neighbor == s.previous || !dict.has_key(grid, neighbor),
False,
)
case same_dir(s), list.length(same_dir(s)) {
[prev, ..], l if l == max -> d != prev
_, 0 -> True
[prev, ..], l if l < min -> d == prev
_, _ -> True
}
}
fn make_state(d: Posn, s: State, grid) {
let neighbor = array2d.add_posns(d, s.posn)
let assert Ok(heat_lost) = dict.get(grid, neighbor)
State(
posn: neighbor,
heatloss: s.heatloss + heat_lost,
previous: s.posn,
history: [d, ..s.history],
)
}
fn find_path(
grid: Dict(Posn, Int),
queue: PriorityQueue(State),
seen: Set(#(Posn, List(Posn))),
get_neighbors: fn(State) -> List(State),
is_goal: fn(State) -> Bool,
) {
let assert Ok(#(state, rest)) = prioqueue.pop(queue)
let key =
make_key(
state
|> io.debug,
)
case set.contains(seen, key) {
True -> find_path(grid, rest, seen, get_neighbors, is_goal)
False -> {
let now_seen = set.insert(seen, key)
let neighbors = get_neighbors(state)
case list.find(neighbors, is_goal) {
Ok(final) -> final.heatloss
_err -> {
let now_queue =
list.fold(neighbors, rest, fn(acc, n) {
prioqueue.insert(acc, n, n.heatloss)
})
find_path(grid, now_queue, now_seen, get_neighbors, is_goal)
}
}
}
}
}
pub fn part1(input: String) {
let raw_grid =
input
|> array2d.to_list_of_lists
let grid = array2d.to_2d_intarray(raw_grid)
let rmax = list.length(raw_grid)
let assert Ok(cmax) =
raw_grid
|> list.first
|> result.map(list.length)
let start = State(Posn(0, 0), 0, Posn(0, 0), [])
let goal = Posn(rmax, cmax)
find_path(
grid,
prioqueue.insert(prioqueue.new(), start, 0),
set.new(),
find_good_neighbors(0, 3, _, grid),
is_goal(_, 1, goal),
)
|> string.inspect
}
pub fn part2(input: String) {
input
|> string.inspect
}
pub fn main() {
let assert Ok(part) = adglent.get_part()
let assert Ok(input) = adglent.get_input("17")
case part {
First ->
part1(input)
|> adglent.inspect
|> io.println
Second ->
part2(input)
|> adglent.inspect
|> io.println
}
}
|
