From 3866493332c2aa0a834a65b4a6425d646b763005 Mon Sep 17 00:00:00 2001 From: Brendan Hansen Date: Sun, 12 Dec 2021 13:22:44 -0600 Subject: [PATCH] added day 12 of aoc-2021 --- core/container/iter.onyx | 44 ++++++++++++++ core/hash.onyx | 4 ++ src/wasm_runtime.c | 2 +- tests/aoc-2021/day12 | 1 + tests/aoc-2021/day12.onyx | 103 +++++++++++++++++++++++++++++++++ tests/aoc-2021/input/day12.txt | 20 +++++++ 6 files changed, 173 insertions(+), 1 deletion(-) create mode 100644 tests/aoc-2021/day12 create mode 100644 tests/aoc-2021/day12.onyx create mode 100644 tests/aoc-2021/input/day12.txt diff --git a/core/container/iter.onyx b/core/container/iter.onyx index 9b806683..7f493037 100644 --- a/core/container/iter.onyx +++ b/core/container/iter.onyx @@ -1,6 +1,7 @@ package core.iter use package core.intrinsics.onyx { __zero_value } +#local memory :: package core.memory as_iterator :: #match {} @@ -229,6 +230,49 @@ zip :: (left_iterator: Iterator($T), right_iterator: Iterator($R)) -> Iterator(Z }; } +concat :: (iters: ..Iterator($T)) -> Iterator(T) { + Context :: struct (T: type_expr) { + iters: [] Iterator(T); + idx: u32; + } + + c := new(Context(T)); + c.iters = memory.copy_slice(iters); + c.idx = 0; + + next :: (use c: ^Context($T)) -> (T, bool) { + while true { + if idx >= iters.count do return __zero_value(T), false; + + curr_iter := ^iters[idx]; + value, valid := curr_iter.next(curr_iter.data); + if valid { + return value, true; + } + + idx += 1; + } + } + + close :: (use c: ^Context($T)) { + // I don't feel like this should always close ALL the iterators... + // But I don't know what the semantics should be for specifying which + // if any iterators to close. + for^ iters { + it.close(it.data); + } + + memory.free_slice(^iters); + cfree(c); + } + + return .{ + c, + #solidify next {T=T}, + #solidify close {T=T} + }; +} + const :: (value: $T) -> Iterator(T) { next :: (data: ^$T) -> (T, bool) { return *(cast(^T) data), true; diff --git a/core/hash.onyx b/core/hash.onyx index d6d89deb..6e1d6331 100644 --- a/core/hash.onyx +++ b/core/hash.onyx @@ -11,3 +11,7 @@ to_u32 :: #match { return hash; }, } + +Hashable :: interface (T: type_expr) { + to_u32(T); +} \ No newline at end of file diff --git a/src/wasm_runtime.c b/src/wasm_runtime.c index 7416edfa..e88dc936 100644 --- a/src/wasm_runtime.c +++ b/src/wasm_runtime.c @@ -293,7 +293,7 @@ b32 onyx_run_wasm(bh_buffer wasm_bytes, int argc, char *argv[]) { run_trap = wasm_func_call(start_func, &args, &results); -#if 0 +#if 1 if (run_trap != NULL) { wasm_message_t msg; wasm_trap_message(run_trap, &msg); diff --git a/tests/aoc-2021/day12 b/tests/aoc-2021/day12 new file mode 100644 index 00000000..322abade --- /dev/null +++ b/tests/aoc-2021/day12 @@ -0,0 +1 @@ +Part 2: 149385 diff --git a/tests/aoc-2021/day12.onyx b/tests/aoc-2021/day12.onyx new file mode 100644 index 00000000..a47c7329 --- /dev/null +++ b/tests/aoc-2021/day12.onyx @@ -0,0 +1,103 @@ +#load "core/std" + +use package core + +Communative_Pair :: struct (T: type_expr) where hash.Hashable(T) { + a, b: T; +} + +#match hash.to_u32 (p: Communative_Pair($T)) => { + return hash.to_u32(p.a) * 13 + hash.to_u32(p.b) * 17; +} + +#operator == (p1, p2: Communative_Pair($T)) => { + if p1.a == p2.a && p1.b == p2.b do return true; + if p1.a == p2.b && p1.b == p2.a do return true; + return false; +} + +main :: (args) => { + for file: os.with_file("./tests/aoc-2021/input/day12.txt") { + reader := io.reader_make(file); + + verticies: Set(str); + edges: Set(Communative_Pair(str)); + while !io.reader_empty(^reader) { + line := io.read_line(^reader, consume_newline=true); + + left, right := do { + parts := string.split(line, #char "-"); + defer memory.free_slice(^parts); + return string.strip_whitespace(parts[0]), string.strip_whitespace(parts[1]); + }; + + edges << .{ left, right }; + verticies << left; + verticies << right; + } + + Node :: struct { name: str; child_idx: u32; second_visit: bool; } + node_stack: [..] Node; + node_stack << .{ "start", 0, false }; + + children_of :: (edges: ^$T, name: str) -> Iterator(str) { + #persist NAME_HACK: str; + NAME_HACK = name; + + return iter.concat( + iter.as_iterator(edges) + |> iter.filter((x) => x.a == NAME_HACK) + |> iter.map((x) => x.b), + + iter.as_iterator(edges) + |> iter.filter((x) => x.b == NAME_HACK) + |> iter.map((x) => x.a) + ); + } + + cannot_visit_multiple :: (name) => { + c := name[0]; + return c >= #char "a" && c <= #char "z"; + } + + edge_map: Map(str, [] str); + for v: iter.as_iterator(^verticies) { + edge_map[v] = children_of(^edges, v) |> iter.to_array(); + } + + paths_count := 0; + while node_stack.count != 0 { + node_idx := node_stack.count - 1; + defer node_stack[node_idx].child_idx += 1; + + children := edge_map[node_stack[node_idx].name]; + valid := node_stack[node_idx].child_idx < children.count; + + if valid { + child := children[node_stack[node_idx].child_idx]; + second_visit := node_stack[node_idx].second_visit; + + if cannot_visit_multiple(child) { + visit_count := 0; + for^ node_stack { + if it.name == child do visit_count += 1; + } + + if visit_count >= 1 { + if second_visit || child == "start" do continue; + + second_visit = true; + } + } + + if child == "end" do paths_count += 1; + else do node_stack << .{ child, 0, second_visit }; + + } else { + array.pop(^node_stack); + } + } + + printf("Part 2: {}\n", paths_count); + } +} \ No newline at end of file diff --git a/tests/aoc-2021/input/day12.txt b/tests/aoc-2021/input/day12.txt new file mode 100644 index 00000000..c0147c63 --- /dev/null +++ b/tests/aoc-2021/input/day12.txt @@ -0,0 +1,20 @@ +VJ-nx +start-sv +nx-UL +FN-nx +FN-zl +end-VJ +sv-hi +em-VJ +start-hi +sv-em +end-zl +zl-em +hi-VJ +FN-em +start-VJ +jx-FN +zl-sv +FN-sv +FN-hi +nx-end \ No newline at end of file -- 2.25.1