From 3efd4e62966998a88d7ef37d281c11cb450343c0 Mon Sep 17 00:00:00 2001 From: Brendan Hansen Date: Thu, 16 Dec 2021 09:23:42 -0600 Subject: [PATCH] day 16 of aoc-2021; even better overload resolution --- include/utils.h | 1 + src/checker.c | 6 + src/polymorph.h | 5 + src/types.c | 1 + tests/aoc-2021/day16 | 2 + tests/aoc-2021/day16.onyx | 212 +++++++++++++++++++++++++++++++++ tests/aoc-2021/input/day16.txt | 1 + 7 files changed, 228 insertions(+) create mode 100644 tests/aoc-2021/day16 create mode 100644 tests/aoc-2021/day16.onyx create mode 100644 tests/aoc-2021/input/day16.txt diff --git a/include/utils.h b/include/utils.h index 626e8a2e..edba6c78 100644 --- a/include/utils.h +++ b/include/utils.h @@ -37,3 +37,4 @@ u32 levenshtein_distance(const char *str1, const char *str2); char *find_closest_symbol_in_node(AstNode *node, char *sym); extern AstTyped node_that_signals_a_yield; +extern AstTyped node_that_signals_failure; diff --git a/src/checker.c b/src/checker.c index 73c3fe3d..cd2b9a5f 100644 --- a/src/checker.c +++ b/src/checker.c @@ -2074,6 +2074,8 @@ CheckStatus check_struct(AstStructType* s_node) { CheckStatus check_struct_defaults(AstStructType* s_node) { if (s_node->entity_type && s_node->entity_type->state < Entity_State_Code_Gen) YIELD(s_node->token->pos, "Waiting for struct type to be constructed before checking defaulted members."); + if (s_node->entity_type && s_node->entity_type->state == Entity_State_Failed) + return Check_Failed; if (s_node->meta_tags) { bh_arr_each(AstTyped *, meta, s_node->meta_tags) { @@ -2191,6 +2193,10 @@ CheckStatus check_function_header(AstFunction* func) { YIELD(local->token->pos, "Waiting for parameter type to be known."); } + if (local->type == (Type *) &node_that_signals_failure) { + return Check_Failed; + } + if (local->type->kind == Type_Kind_Compound) { ERROR(param->local->token->pos, "Compound types are not allowed as parameter types. Try splitting this into multiple parameters."); } diff --git a/src/polymorph.h b/src/polymorph.h index b1b5c6c3..2cbfa349 100644 --- a/src/polymorph.h +++ b/src/polymorph.h @@ -18,6 +18,7 @@ static b32 doing_nested_polymorph_lookup = 0; // like polymorphic_proc_lookup when it is determined that everything works so far, but // the caller must yield in order to finish checking this polymorphic procedure. AstTyped node_that_signals_a_yield = { Ast_Kind_Function, 0 }; +AstTyped node_that_signals_failure = { Ast_Kind_Error, 0 }; static void ensure_polyproc_cache_is_created(AstPolyProc* pp) { if (pp->concrete_funcs == NULL) sh_new_arena(pp->concrete_funcs); @@ -961,6 +962,10 @@ Type* polymorphic_struct_lookup(AstPolyStructType* ps_type, bh_arr(AstPolySoluti return NULL; } + if (concrete_struct->entity_type->state == Entity_State_Failed) { + return (Type *) &node_that_signals_failure; + } + Type* cs_type = type_build_from_ast(context.ast_alloc, (AstType *) concrete_struct); if (!cs_type) return NULL; diff --git a/src/types.c b/src/types.c index ca2bb4d5..bc2a42f9 100644 --- a/src/types.c +++ b/src/types.c @@ -596,6 +596,7 @@ Type* type_build_from_ast(bh_allocator alloc, AstType* type_node) { bh_arr_free(slns); if (!concrete) return NULL; + if (concrete == (Type *) &node_that_signals_failure) return concrete; concrete->Struct.constructed_from = (AstType *) ps_type; return concrete; } diff --git a/tests/aoc-2021/day16 b/tests/aoc-2021/day16 new file mode 100644 index 00000000..d39ac5c7 --- /dev/null +++ b/tests/aoc-2021/day16 @@ -0,0 +1,2 @@ +Part 1: 940 +Part 2: 13476220616073 diff --git a/tests/aoc-2021/day16.onyx b/tests/aoc-2021/day16.onyx new file mode 100644 index 00000000..30bef44a --- /dev/null +++ b/tests/aoc-2021/day16.onyx @@ -0,0 +1,212 @@ +#load "core/std" + +use package core + +base16_to_hex :: (s: str) -> u32 { + res := 0; + for s { + res *= 16; + switch it { + case #char "0" .. #char "9" do res += ~~(it - #char "0"); + case #char "a" .. #char "f" do res += ~~(it - #char "a" + 10); + case #char "A" .. #char "F" do res += ~~(it - #char "A" + 10); + case #default do break break; + } + } + + return res; +} + +BitIterator :: struct { + iter: Iterator(u32); + bits_read: u32; + + values: [] u8; + value_idx: u32; + bit_idx: i32; + + next :: (b: ^BitIterator) -> u32 { + v, _ := iter.take_one(b.iter, no_close=true); + return v; + } +} + +bit_iterator :: (values: [] u8) -> ^BitIterator { + c := new(BitIterator); + c.iter = .{ c, next, cfree }; + c.values = values; + c.value_idx = 0; + c.bit_idx = 7; + + next :: (use c: ^BitIterator) -> (u32, bool) { + if value_idx >= values.count do return 0, false; + + defer { + bits_read += 1; + bit_idx -= 1; + if bit_idx < 0 { + value_idx += 1; + bit_idx = 7; + } + } + + ret := 0; + if (values[value_idx] & ~~(1 << bit_idx)) != 0 do ret = 1; + return ret, true; + } + + return c; +} + +read_bits :: (bit_provider: ^BitIterator, count: u32) -> u32 { + res := 0; + for count { + res *= 2; + if bit := bit_provider->next(); bit == 1 { + res += 1; + } + } + + return res; +} + + +Packet :: struct { + version: u32; + type: u32; +} + +Packet_Literal :: struct { + use base: Packet; + value: u64; +} + +Packet_Operator :: struct { + use base: Packet; + subpackets: [] ^Packet; +} + +parse_packet :: (bit_provider: ^BitIterator) -> ^Packet { + version := read_bits(bit_provider, 3); + type := read_bits(bit_provider, 3); + + switch type { + case 4 { + value: u64; + while true { + cont := read_bits(bit_provider, 1); + value *= 16; + value += ~~read_bits(bit_provider, 4); + + if cont == 0 do break; + } + + p := new(Packet_Literal); + p.version = version; + p.type = type; + p.value = value; + return p; + } + + case #default { + packets: [..] ^Packet; + + l_type := read_bits(bit_provider, 1); + if l_type == 0 { + // Length encoded + bits_to_read := read_bits(bit_provider, 15); + curr_bits := bit_provider.bits_read; + while bit_provider.bits_read < curr_bits + bits_to_read { + packets << parse_packet(bit_provider); + } + + } else { + // Count encoded + count := read_bits(bit_provider, 11); + for count { + packets << parse_packet(bit_provider); + } + } + + p := new(Packet_Operator); + p.version = version; + p.type = type; + p.subpackets = packets; + return p; + } + } +} + +packet_sum_version :: (p: ^Packet) -> u64 { + switch p.type { + case 4 do return ~~p.version; + + case #default { + sum: u64; + for (cast (^Packet_Operator) p).subpackets { + sum += packet_sum_version(it); + } + + return sum + ~~p.version; + } + } +} + +packet_reduce :: (p: ^Packet) -> u64 { + op := cast(^Packet_Operator) p; + switch p.type { + case 0 { + return array.fold(op.subpackets, cast(u64) 0, (x, y) => y + packet_reduce(x)); + } + + case 1 { + return array.fold(op.subpackets, cast(u64) 1, (x, y) => y * packet_reduce(x)); + } + + case 2 { + return array.fold(op.subpackets, cast(u64) -1, (x, y) => math.min(y, packet_reduce(x))); + } + + case 3 { + return array.fold(op.subpackets, cast(u64) 0, (x, y) => math.max(y, packet_reduce(x))); + } + + case 4 { + return (cast(^Packet_Literal) p).value; + } + + case 5 { + return ~~(1 if packet_reduce(op.subpackets[0]) > packet_reduce(op.subpackets[1]) else 0); + } + + case 6 { + return ~~(1 if packet_reduce(op.subpackets[0]) < packet_reduce(op.subpackets[1]) else 0); + } + + case 7 { + return ~~(1 if packet_reduce(op.subpackets[0]) == packet_reduce(op.subpackets[1]) else 0); + } + } +} + + +main :: (args) => { + for file: os.with_file("./tests/aoc-2021/input/day16.txt") { + reader := io.reader_make(file); + line := io.read_line(^reader, consume_newline=false, inplace=true); + + transmission: [..] u8; + for i: range.{ 0, line.count, 2 } { + transmission << ~~(base16_to_hex(line[i .. i + 2])); + } + + bit_provider := bit_iterator(transmission); + packet := parse_packet(bit_provider); + + result := packet_sum_version(packet); + printf("Part 1: {}\n", result); + + result = packet_reduce(packet); + printf("Part 2: {}\n", result); + } +} diff --git a/tests/aoc-2021/input/day16.txt b/tests/aoc-2021/input/day16.txt new file mode 100644 index 00000000..eb9ff961 --- /dev/null +++ b/tests/aoc-2021/input/day16.txt @@ -0,0 +1 @@ +E0525D9802FA00B80021B13E2D4260004321DC648D729DD67B2412009966D76C0159ED274F6921402E9FD4AC1B0F652CD339D7B82240083C9A54E819802B369DC0082CF90CF9280081727DAF41E6A5C1B9B8E41A4F31A4EF67E2009834015986F9ABE41E7D6080213931CB004270DE5DD4C010E00D50401B8A708E3F80021F0BE0A43D9E460007E62ACEE7F9FB4491BC2260090A573A876B1BC4D679BA7A642401434937C911CD984910490CCFC27CC7EE686009CFC57EC0149CEFE4D135A0C200C0F401298BCF265377F79C279F540279ACCE5A820CB044B62299291C0198025401AA00021D1822BC5C100763A4698FB350E6184C00A9820200FAF00244998F67D59998F67D5A93ECB0D6E0164D709A47F5AEB6612D1B1AC788846008780252555097F51F263A1CA00C4D0946B92669EE47315060081206C96208B0B2610E7B389737F3E2006D66C1A1D4ABEC3E1003A3B0805D337C2F4FA5CD83CE7DA67A304E9BEEF32DCEF08A400020B1967FC2660084BC77BAC3F847B004E6CA26CA140095003900BAA3002140087003D40080022E8C00870039400E1002D400F10038C00D100218038F400B6100229500226699FEB9F9B098021A00800021507627C321006E24C5784B160C014A0054A64E64BB5459DE821803324093AEB3254600B4BF75C50D0046562F72B1793004667B6E78EFC0139FD534733409232D7742E402850803F1FA3143D00042226C4A8B800084C528FD1527E98D5EB45C6003FE7F7FCBA000A1E600FC5A8311F08010983F0BA0890021F1B61CC4620140EC010100762DC4C8720008641E89F0866259AF460C015D00564F71ED2935993A539C0F9AA6B0786008D80233514594F43CDD31F585005A25C3430047401194EA649E87E0CA801D320D2971C95CAA380393AF131F94F9E0499A775460 -- 2.25.1