From 6adea25685eb9668219e3f4ed9643ebe28b734c0 Mon Sep 17 00:00:00 2001 From: Hunky Jimpjorps Date: Mon, 18 Dec 2023 16:10:25 -0500 Subject: day 17 gleam incomplete --- aoc2023/gleam.toml | 1 + aoc2023/manifest.toml | 10 +++--- aoc2023/src/day17/solve.gleam | 53 +++++++++++++++++++----------- aoc2023/src/utilities/prioqueue.gleam | 62 +++++++++++++++++++++++++++++++++++ 4 files changed, 102 insertions(+), 24 deletions(-) create mode 100644 aoc2023/src/utilities/prioqueue.gleam (limited to 'aoc2023') diff --git a/aoc2023/gleam.toml b/aoc2023/gleam.toml index 8e0eb9c..5b60622 100644 --- a/aoc2023/gleam.toml +++ b/aoc2023/gleam.toml @@ -16,6 +16,7 @@ simplifile = "~> 1.0" gleam_erlang = "~> 0.23" gleam_community_maths = "~> 1.0" gleam_otp = "~> 0.8" +pqueue = "~> 2.0" [dev-dependencies] gleeunit = "~> 1.0" diff --git a/aoc2023/manifest.toml b/aoc2023/manifest.toml index 2336490..a6f708a 100644 --- a/aoc2023/manifest.toml +++ b/aoc2023/manifest.toml @@ -2,18 +2,19 @@ # You typically do not need to edit this file packages = [ - { name = "adglent", version = "1.2.0", build_tools = ["gleam"], requirements = ["gap", "gleam_httpc", "gleam_community_ansi", "glint", "gleam_otp", "gleam_http", "gleam_erlang", "gleam_stdlib", "simplifile", "snag", "tom"], otp_app = "adglent", source = "hex", outer_checksum = "A20D35001061F8AD602E3B92FB3AC0E1E4EEC642AD2AAE0ACEAD3A85F37DA7F0" }, + { name = "adglent", version = "1.2.0", build_tools = ["gleam"], requirements = ["glint", "gleam_community_ansi", "snag", "gleam_erlang", "gleam_stdlib", "gleam_http", "gleam_otp", "tom", "gap", "simplifile", "gleam_httpc"], otp_app = "adglent", source = "hex", outer_checksum = "A20D35001061F8AD602E3B92FB3AC0E1E4EEC642AD2AAE0ACEAD3A85F37DA7F0" }, { name = "gap", version = "1.0.1", build_tools = ["gleam"], requirements = ["gleam_stdlib", "gleam_community_ansi"], otp_app = "gap", source = "hex", outer_checksum = "5E369751DB547BFBDA7735878DC04DA31FCA3112193D61D5D7566010C7C8BA98" }, - { name = "gleam_community_ansi", version = "1.2.0", build_tools = ["gleam"], requirements = ["gleam_community_colour", "gleam_stdlib"], otp_app = "gleam_community_ansi", source = "hex", outer_checksum = "8B5A9677BC5A2738712BBAF2BA289B1D8195FDF962BBC769569976AD5E9794E1" }, + { name = "gleam_community_ansi", version = "1.2.0", build_tools = ["gleam"], requirements = ["gleam_stdlib", "gleam_community_colour"], otp_app = "gleam_community_ansi", source = "hex", outer_checksum = "8B5A9677BC5A2738712BBAF2BA289B1D8195FDF962BBC769569976AD5E9794E1" }, { name = "gleam_community_colour", version = "1.2.0", build_tools = ["gleam"], requirements = ["gleam_stdlib"], otp_app = "gleam_community_colour", source = "hex", outer_checksum = "036C206886AFB9F153C552700A7A0B4D2864E3BC96A20C77E5F34A013C051BE3" }, { name = "gleam_community_maths", version = "1.0.1", build_tools = ["gleam"], requirements = ["gleam_stdlib"], otp_app = "gleam_community_maths", source = "hex", outer_checksum = "1B9DB313E94A0E4674CA84C5D29F45ECFE211BFB38ABBD8B23737395F47D08B3" }, { name = "gleam_erlang", version = "0.23.1", build_tools = ["gleam"], requirements = ["gleam_stdlib"], otp_app = "gleam_erlang", source = "hex", outer_checksum = "C21CFB816C114784E669FFF4BBF433535EEA9960FA2F216209B8691E87156B96" }, { name = "gleam_http", version = "3.5.2", build_tools = ["gleam"], requirements = ["gleam_stdlib"], otp_app = "gleam_http", source = "hex", outer_checksum = "AECDA43AFD523D07A8F09068598A6E271C505278A0CB6F9C7A2E4365EAE8D11E" }, - { name = "gleam_httpc", version = "2.1.1", build_tools = ["gleam"], requirements = ["gleam_stdlib", "gleam_http"], otp_app = "gleam_httpc", source = "hex", outer_checksum = "06AC1CA52C9BAA66C9D5C0303B2BF34E39AA1546BB96AEE496E4B06D513AB8C7" }, + { name = "gleam_httpc", version = "2.1.1", build_tools = ["gleam"], requirements = ["gleam_http", "gleam_stdlib"], otp_app = "gleam_httpc", source = "hex", outer_checksum = "06AC1CA52C9BAA66C9D5C0303B2BF34E39AA1546BB96AEE496E4B06D513AB8C7" }, { name = "gleam_otp", version = "0.8.0", build_tools = ["gleam"], requirements = ["gleam_erlang", "gleam_stdlib"], otp_app = "gleam_otp", source = "hex", outer_checksum = "18EF8242A5E54BA92F717C7222F03B3228AEE00D1F286D4C56C3E8C18AA2588E" }, { name = "gleam_stdlib", version = "0.33.0", build_tools = ["gleam"], requirements = [], otp_app = "gleam_stdlib", source = "hex", outer_checksum = "539E37A2AA5EBE8E75F4B74755E4CC604BD957C3000AC8D705A2024886A2738B" }, { name = "gleeunit", version = "1.0.0", build_tools = ["gleam"], requirements = ["gleam_stdlib"], otp_app = "gleeunit", source = "hex", outer_checksum = "D3682ED8C5F9CAE1C928F2506DE91625588CC752495988CBE0F5653A42A6F334" }, - { name = "glint", version = "0.13.0", build_tools = ["gleam"], requirements = ["gleam_community_ansi", "gleam_stdlib", "gleam_community_colour", "snag"], otp_app = "glint", source = "hex", outer_checksum = "46E56049CD370D61F720D319D0AB970408C9336EEB918F08B5DCB1DCE9845FA3" }, + { name = "glint", version = "0.13.0", build_tools = ["gleam"], requirements = ["gleam_community_colour", "gleam_community_ansi", "gleam_stdlib", "snag"], otp_app = "glint", source = "hex", outer_checksum = "46E56049CD370D61F720D319D0AB970408C9336EEB918F08B5DCB1DCE9845FA3" }, + { name = "pqueue", version = "2.0.7", build_tools = ["rebar3"], requirements = [], otp_app = "pqueue", source = "hex", outer_checksum = "8B0204BB202335890E4E7F9B99A8EC0B84DDB8513EE298EB180EE9B3BCB4C859" }, { name = "simplifile", version = "1.0.0", build_tools = ["gleam"], requirements = ["gleam_stdlib"], otp_app = "simplifile", source = "hex", outer_checksum = "0BD6F0E7DA1A7E11D18B8AD48453225CAFCA4C8CFB4513D217B372D2866C501C" }, { name = "snag", version = "0.2.1", build_tools = ["gleam"], requirements = ["gleam_stdlib"], otp_app = "snag", source = "hex", outer_checksum = "8FD70D8FB3728E08AC425283BB509BB0F012BE1AE218424A597CDE001B0EE589" }, { name = "tom", version = "0.2.1", build_tools = ["gleam"], requirements = ["gleam_stdlib"], otp_app = "tom", source = "hex", outer_checksum = "5C5A9B8586C547F1F39542B1A3BBD9FEE17AFEAB51CE53B32B13D0D46B421249" }, @@ -26,4 +27,5 @@ gleam_erlang = { version = "~> 0.23" } gleam_otp = { version = "~> 0.8" } gleam_stdlib = { version = "~> 0.32" } gleeunit = { version = "~> 1.0" } +pqueue = { version = "~> 2.0" } simplifile = { version = "~> 1.0" } 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) + } + } +} -- cgit v1.2.3