diff options
| -rw-r--r-- | day_11.zig | 160 | ||||
| -rw-r--r-- | inputs/day_11 | 55 | ||||
| -rw-r--r-- | main.zig | 1 | ||||
| -rw-r--r-- | util/aoc.zig | 2 |
4 files changed, 217 insertions, 1 deletions
diff --git a/day_11.zig b/day_11.zig new file mode 100644 index 0000000..dc68190 --- /dev/null +++ b/day_11.zig @@ -0,0 +1,160 @@ +const std = @import("std"); +const Result = @import("util/aoc.zig").Result; + +const Operation = struct { + symbol: u8, + fixed: bool = false, + fixed_number: u8 = 0, + + fn exe(self: Operation, b: u64) u64 { + if (self.symbol == '*') { + switch (self.fixed) { + true => return self.fixed_number * b, + false => return b * b, + } + } + + switch (self.fixed) { + true => return self.fixed_number + b, + false => return b + b, + } + } +}; + +const Monkey = struct { + const Throw_rules = struct { + multiple_of: u8, + true: u8, + false: u8, + }; + + id: u8, + inspect_count: usize = 0, + items: std.ArrayList(u64), + operation: Operation, + throw_rules: Throw_rules, + + fn throws_to(self: Monkey, worry_level: u64) usize { + if (worry_level % self.throw_rules.multiple_of == 0) return self.throw_rules.true; + return self.throw_rules.false; + } + + fn inspect(self: *Monkey) u64 { + self.inspect_count += 1; + return self.operation.exe(self.items.orderedRemove(0)); + } +}; + +fn answer(monkeys: []Monkey) u64 { + var max: [2]u64 = std.mem.zeroes([2]u64); + for (monkeys) |*monkey| { + if (monkey.inspect_count > max[0] and monkey.inspect_count > max[1]) { + max[1] = max[0]; + max[0] = monkey.inspect_count; + } else if (monkey.inspect_count > max[1]) { + max[1] = monkey.inspect_count; + } + + monkey.items.deinit(); + } + return max[0] * max[1]; +} + +fn parse(allocator: std.mem.Allocator, input: []const u8) []Monkey { + var monkeys = std.ArrayList(Monkey).init(allocator); + + var monkey_iter = std.mem.split(u8, input, "\n\n"); + while (monkey_iter.next()) |monkey_data| { + var monkey = std.mem.split(u8, monkey_data, "\n"); + + var line = monkey.next().?; + var id = std.fmt.parseInt(u8, line[7 .. line.len - 1], 0) catch unreachable; + + var items = std.ArrayList(u64).init(allocator); + line = monkey.next().?; + var items_iter = std.mem.split(u8, line[18..], ", "); + while (items_iter.next()) |item| { + items.append(std.fmt.parseInt(u64, item, 0) catch unreachable) catch unreachable; + } + + const operation = blk: { + line = monkey.next().?; + var op = Operation{ .symbol = line[23] }; + + if (line[25] != 'o') { + op.fixed = true; + op.fixed_number = std.fmt.parseInt(u8, line[25..], 0) catch unreachable; + } + + break :blk op; + }; + + const throw_rules = blk: { + line = monkey.next().?; + const multiple_of = std.fmt.parseInt(u8, line[21..], 0) catch unreachable; + + line = monkey.next().?; + const iftrue = std.fmt.parseInt(u8, line[29..], 0) catch unreachable; + + line = monkey.next().?; + const iffalse = std.fmt.parseInt(u8, line[30..], 0) catch unreachable; + + break :blk Monkey.Throw_rules{ + .multiple_of = multiple_of, + .true = iftrue, + .false = iffalse, + }; + }; + + monkeys.append(Monkey{ + .id = id, + .items = items, + .operation = operation, + .throw_rules = throw_rules, + }) catch unreachable; + } + + return monkeys.toOwnedSlice() catch unreachable; +} + +pub fn puzzle_1(allocator: std.mem.Allocator, input: []const u8) Result { + var monkeys = parse(allocator, input); + defer allocator.free(monkeys); + + var i: usize = 0; + while (i < 20) : (i += 1) { + for (monkeys) |*monkey| { + while (monkey.items.items.len > 0) { + const new_worry_level = monkey.inspect(); + const throw_to = monkey.throws_to(new_worry_level / 3); + monkeys[throw_to].items.append(new_worry_level / 3) catch unreachable; + } + } + } + + return .{ .int = @intCast(i32, answer(monkeys)) }; +} + +pub fn puzzle_2(allocator: std.mem.Allocator, input: []const u8) Result { + var monkeys = parse(allocator, input); + defer allocator.free(monkeys); + + const mod = blk: { + var r: u64 = 1; + for (monkeys) |monkey| r *= monkey.throw_rules.multiple_of; + break :blk r; + }; + + var i: usize = 0; + while (i < 10000) : (i += 1) { + for (monkeys) |*monkey| { + while (monkey.items.items.len > 0) { + const new_worry_level = monkey.inspect(); + const throw_to = monkey.throws_to(new_worry_level % mod); + monkeys[throw_to].items.append(new_worry_level % mod) catch unreachable; + } + } + } + + return .{ .int = @intCast(i64, answer(monkeys)) }; +} diff --git a/inputs/day_11 b/inputs/day_11 new file mode 100644 index 0000000..f505c2e --- /dev/null +++ b/inputs/day_11 @@ -0,0 +1,55 @@ +Monkey 0: + Starting items: 83, 97, 95, 67 + Operation: new = old * 19 + Test: divisible by 17 + If true: throw to monkey 2 + If false: throw to monkey 7 + +Monkey 1: + Starting items: 71, 70, 79, 88, 56, 70 + Operation: new = old + 2 + Test: divisible by 19 + If true: throw to monkey 7 + If false: throw to monkey 0 + +Monkey 2: + Starting items: 98, 51, 51, 63, 80, 85, 84, 95 + Operation: new = old + 7 + Test: divisible by 7 + If true: throw to monkey 4 + If false: throw to monkey 3 + +Monkey 3: + Starting items: 77, 90, 82, 80, 79 + Operation: new = old + 1 + Test: divisible by 11 + If true: throw to monkey 6 + If false: throw to monkey 4 + +Monkey 4: + Starting items: 68 + Operation: new = old * 5 + Test: divisible by 13 + If true: throw to monkey 6 + If false: throw to monkey 5 + +Monkey 5: + Starting items: 60, 94 + Operation: new = old + 5 + Test: divisible by 3 + If true: throw to monkey 1 + If false: throw to monkey 0 + +Monkey 6: + Starting items: 81, 51, 85 + Operation: new = old * old + Test: divisible by 5 + If true: throw to monkey 5 + If false: throw to monkey 1 + +Monkey 7: + Starting items: 98, 81, 63, 65, 84, 71, 84 + Operation: new = old + 3 + Test: divisible by 2 + If true: throw to monkey 2 + If false: throw to monkey 3 @@ -16,6 +16,7 @@ const t = [_]struct { .{ .day = @import("day_08.zig"), .input = @embedFile("inputs/day_08"), .expect = &[_]Result{ .{ .int = 1859 }, .{ .int = 332640 } } }, .{ .day = @import("day_09.zig"), .input = @embedFile("inputs/day_09"), .expect = &[_]Result{ .{ .int = 6087 }, .{ .int = 2493 } } }, .{ .day = @import("day_10.zig"), .input = @embedFile("inputs/day_10"), .expect = &[_]Result{ .{ .int = 14620 }, .{ .int = 4210 } } }, + .{ .day = @import("day_11.zig"), .input = @embedFile("inputs/day_11"), .expect = &[_]Result{ .{ .int = 108240 }, .{ .int = 25712998901 } } }, }; pub fn main() !void { diff --git a/util/aoc.zig b/util/aoc.zig index 0c3e668..0f32c54 100644 --- a/util/aoc.zig +++ b/util/aoc.zig @@ -1,7 +1,7 @@ const std = @import("std"); pub const Result = union(enum) { - int: i32, + int: i64, string: []const u8, pub fn cmp(self: Result, result: Result) bool { |