aboutsummaryrefslogtreecommitdiff
path: root/aoc2023/src
diff options
context:
space:
mode:
authorHunky Jimpjorps <thechairman@thechairman.info>2023-12-18 16:10:25 -0500
committerHunky Jimpjorps <thechairman@thechairman.info>2023-12-18 16:10:25 -0500
commit6adea25685eb9668219e3f4ed9643ebe28b734c0 (patch)
tree33f0d23e2196424f16efafef715c5f177011a7a9 /aoc2023/src
parent662dc6d30da9325590a59eb506880d1d2e5ecfb2 (diff)
downloadgleam_aoc-6adea25685eb9668219e3f4ed9643ebe28b734c0.tar.gz
gleam_aoc-6adea25685eb9668219e3f4ed9643ebe28b734c0.zip
day 17 gleam incomplete
Diffstat (limited to 'aoc2023/src')
-rw-r--r--aoc2023/src/day17/solve.gleam53
-rw-r--r--aoc2023/src/utilities/prioqueue.gleam62
2 files changed, 95 insertions, 20 deletions
diff --git a/aoc2023/src/day17/solve.gleam b/aoc2023/src/day17/solve.gleam
index 200565a..7a01c4d 100644
--- a/aoc2023/src/day17/solve.gleam
+++ b/aoc2023/src/day17/solve.gleam
@@ -1,13 +1,13 @@
import adglent.{First, Second}
+import gleam/bool
+import gleam/dict.{type Dict}
import gleam/io
-import gleam/string
import gleam/list
import gleam/result
+import gleam/string
+import gleam/set.{type Set}
import utilities/array2d.{type Posn, Posn}
-import gleam/bool
-import gleam/dict
-import gleam/queue.{type Queue}
-import gleam/set
+import utilities/prioqueue.{type PriorityQueue}
type State {
State(posn: Posn, heatloss: Int, previous: Posn, history: List(Posn))
@@ -22,7 +22,9 @@ fn make_key(s: State) {
fn same_dir(s: State) {
case s.history {
[] -> []
- [first, ..] as deltas -> list.take_while(deltas, fn(d) { d == first })
+ [first, ..] as deltas ->
+ list.take_while(deltas, fn(d) { d == first })
+ |> list.take(10)
}
}
@@ -62,21 +64,32 @@ fn make_state(d: Posn, s: State, grid) {
)
}
-fn find_path(grid, goal, seen, queue: Queue(State), neighbor_fn, goal_fn) {
- let assert Ok(#(s, rest)) = queue.pop_front(queue)
- let key = make_key(s)
-
+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, goal, seen, rest, neighbor_fn, goal_fn)
+ True -> find_path(grid, rest, seen, get_neighbors, is_goal)
False -> {
- let seen = set.insert(seen, key)
- let neighbors: List(State) = neighbor_fn(s)
-
- case list.find(neighbors, goal_fn) {
+ let now_seen = set.insert(seen, key)
+ let neighbors = get_neighbors(state)
+ case list.find(neighbors, is_goal) {
Ok(final) -> final.heatloss
- Error(Nil) -> {
- let queue = list.fold(neighbors, queue, queue.push_back)
- find_path(grid, goal, seen, queue, neighbor_fn, goal_fn)
+ _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)
}
}
}
@@ -96,13 +109,13 @@ pub fn part1(input: String) {
|> list.first
|> result.map(list.length)
+ let start = State(Posn(0, 0), 0, Posn(0, 0), [])
let goal = Posn(rmax, cmax)
find_path(
grid,
- goal,
+ prioqueue.insert(prioqueue.new(), start, 0),
set.new(),
- queue.from_list([State(Posn(0, 0), 0, Posn(0, 0), [])]),
find_good_neighbors(0, 3, _, grid),
is_goal(_, 1, goal),
)
diff --git a/aoc2023/src/utilities/prioqueue.gleam b/aoc2023/src/utilities/prioqueue.gleam
new file mode 100644
index 0000000..640748b
--- /dev/null
+++ b/aoc2023/src/utilities/prioqueue.gleam
@@ -0,0 +1,62 @@
+//adapted from https://github.com/byronanderson/adventofcode2021/blob/main/gleam_advent/src/priority_queue.gleam
+
+import gleam/dict.{type Dict}
+
+type Ref
+
+@external(erlang, "erlang", "make_ref")
+fn make_ref() -> Ref
+
+type PQueue(a)
+
+pub opaque type PriorityQueue(a) {
+ PriorityQueue(queue: PQueue(#(a, Ref)), refs: Dict(a, Ref))
+}
+
+type OutResult(a) {
+ Empty
+ Value(a, Int)
+}
+
+@external(erlang, "pqueue2", "new")
+fn new_() -> PQueue(a)
+
+@external(erlang, "pqueue2", "in")
+fn insert_(item: a, prio: Int, queue: PQueue(a)) -> PQueue(a)
+
+@external(erlang, "pqueue2", "pout")
+fn pop_(queue: PQueue(a)) -> #(OutResult(a), PQueue(a))
+
+pub fn new() -> PriorityQueue(a) {
+ PriorityQueue(queue: new_(), refs: dict.new())
+}
+
+pub fn insert(
+ queue: PriorityQueue(a),
+ value: a,
+ priority: Int,
+) -> PriorityQueue(a) {
+ let ref = make_ref()
+
+ let refs =
+ queue.refs
+ |> dict.insert(value, ref)
+
+ PriorityQueue(refs: refs, queue: insert_(#(value, ref), priority, queue.queue),
+ )
+}
+
+pub fn pop(queue: PriorityQueue(a)) -> Result(#(a, PriorityQueue(a)), Nil) {
+ case pop_(queue.queue) {
+ #(Value(#(value, ref), _priority), pqueue) -> {
+ let assert Ok(recently_enqueued_ref) = dict.get(queue.refs, value)
+ case recently_enqueued_ref == ref {
+ True -> Ok(#(value, PriorityQueue(refs: queue.refs, queue: pqueue)))
+ False -> pop(PriorityQueue(refs: queue.refs, queue: pqueue))
+ }
+ }
+ #(Empty, _pqueue) -> {
+ Error(Nil)
+ }
+ }
+}