From 1bec3f3b1b41230c5c4812024c56651e1fc24b7a Mon Sep 17 00:00:00 2001 From: Julien Dessaux Date: Sun, 11 Dec 2022 17:47:46 +0100 Subject: 2022-11 in zig --- 2022/11-monkey-in-the-middle/example | 27 +++++++ 2022/11-monkey-in-the-middle/first.zig | 126 +++++++++++++++++++++++++++++++ 2022/11-monkey-in-the-middle/input | 55 ++++++++++++++ 2022/11-monkey-in-the-middle/second.zig | 129 ++++++++++++++++++++++++++++++++ 4 files changed, 337 insertions(+) create mode 100644 2022/11-monkey-in-the-middle/example create mode 100644 2022/11-monkey-in-the-middle/first.zig create mode 100644 2022/11-monkey-in-the-middle/input create mode 100644 2022/11-monkey-in-the-middle/second.zig (limited to '2022') diff --git a/2022/11-monkey-in-the-middle/example b/2022/11-monkey-in-the-middle/example new file mode 100644 index 0000000..30e09e5 --- /dev/null +++ b/2022/11-monkey-in-the-middle/example @@ -0,0 +1,27 @@ +Monkey 0: + Starting items: 79, 98 + Operation: new = old * 19 + Test: divisible by 23 + If true: throw to monkey 2 + If false: throw to monkey 3 + +Monkey 1: + Starting items: 54, 65, 75, 74 + Operation: new = old + 6 + Test: divisible by 19 + If true: throw to monkey 2 + If false: throw to monkey 0 + +Monkey 2: + Starting items: 79, 60, 97 + Operation: new = old * old + Test: divisible by 13 + If true: throw to monkey 1 + If false: throw to monkey 3 + +Monkey 3: + Starting items: 74 + Operation: new = old + 3 + Test: divisible by 17 + If true: throw to monkey 0 + If false: throw to monkey 1 diff --git a/2022/11-monkey-in-the-middle/first.zig b/2022/11-monkey-in-the-middle/first.zig new file mode 100644 index 0000000..5ee8796 --- /dev/null +++ b/2022/11-monkey-in-the-middle/first.zig @@ -0,0 +1,126 @@ +const std = @import("std"); + +const example = @embedFile("example"); +const input = @embedFile("input"); + +pub fn main() anyerror!void { + var arena = std.heap.ArenaAllocator.init(std.heap.page_allocator); + defer arena.deinit(); + const allocator = arena.allocator(); + + try std.testing.expectEqual(try solve(example, allocator), 10605); + const result = try solve(input, allocator); + try std.io.getStdOut().writer().print("{}\n", .{result}); +} + +const Operation = struct { + first: ?u64, + operand: u8, + second: ?u64, + fn init(line: []const u8, allocator: std.mem.Allocator) !*Operation { + var o = try allocator.create(Operation); + var it = std.mem.tokenize(u8, line, " "); + _ = it.next() orelse unreachable; // Operation: + _ = it.next() orelse unreachable; // new + _ = it.next() orelse unreachable; // = + o.first = std.fmt.parseInt(u64, it.next() orelse unreachable, 10) catch null; + const tmp = it.next() orelse unreachable; + o.operand = tmp[0]; + o.second = std.fmt.parseInt(u64, it.next() orelse unreachable, 10) catch null; + return o; + } + fn run(o: Operation, v: u64) u64 { + const first = if (o.first) |f| f else v; + const second = if (o.second) |f| f else v; + switch (o.operand) { + '+' => return first + second, + '-' => return first - second, + '*' => return first * second, + '/' => return first / second, + else => unreachable, + } + } +}; + +const Monkey = struct { + inspections: u64, + items: std.ArrayList(u64), + operation: *Operation, + divisible: u64, // divisible by + testTrue: u64, + testFalse: u64, + fn init(it: *std.mem.TokenIterator(u8), allocator: std.mem.Allocator) !*Monkey { + var m = try allocator.create(Monkey); + m.inspections = 0; + m.items = std.ArrayList(u64).init(allocator); + var items = std.mem.tokenize(u8, it.next() orelse unreachable, " ,"); + _ = items.next() orelse unreachable; // starting + _ = items.next() orelse unreachable; // items: + while (items.next()) |item| { + try m.items.append(std.fmt.parseInt(u64, item, 10) catch unreachable); + } + m.operation = try Operation.init(it.next() orelse unreachable, allocator); + var divisible = std.mem.tokenize(u8, it.next() orelse unreachable, " "); + _ = divisible.next() orelse unreachable; // test: + _ = divisible.next() orelse unreachable; // divisible + _ = divisible.next() orelse unreachable; // by + m.divisible = std.fmt.parseInt(u64, divisible.next() orelse unreachable, 10) catch unreachable; + var testTrue = std.mem.tokenize(u8, it.next() orelse unreachable, " "); + _ = testTrue.next() orelse unreachable; // if + _ = testTrue.next() orelse unreachable; // true: + _ = testTrue.next() orelse unreachable; // throw + _ = testTrue.next() orelse unreachable; // to + _ = testTrue.next() orelse unreachable; // monkey + m.testTrue = std.fmt.parseInt(u64, testTrue.next() orelse unreachable, 10) catch unreachable; + var testFalse = std.mem.tokenize(u8, it.next() orelse unreachable, " "); + _ = testFalse.next() orelse unreachable; // if + _ = testFalse.next() orelse unreachable; // true: + _ = testFalse.next() orelse unreachable; // throw + _ = testFalse.next() orelse unreachable; // to + _ = testFalse.next() orelse unreachable; // monkey + m.testFalse = std.fmt.parseInt(u64, testFalse.next() orelse unreachable, 10) catch unreachable; + return m; + } + fn step(m: *Monkey, monkeys: []*Monkey) !void { + m.inspections += m.items.items.len; + for (m.items.items) |item| { + const v = m.operation.run(item) / 3; + if (@mod(v, m.divisible) == 0) { + try monkeys[m.testTrue].items.append(v); + } else { + try monkeys[m.testFalse].items.append(v); + } + } + m.items.items.len = 0; + } +}; + +fn solve(puzzle: []const u8, allocator: std.mem.Allocator) !u64 { + var it = std.mem.tokenize(u8, puzzle, "\n"); + var monkeys = std.ArrayList(*Monkey).init(allocator); + // process input + while (it.next()) |_| { + try monkeys.append(try Monkey.init(&it, allocator)); + } + // run 20 rounds + var rounds: usize = 0; + while (rounds < 20) : (rounds += 1) { + for (monkeys.items) |m| { + try m.step(monkeys.items); + } + } + // find answer + var m1: u64 = 0; + var m2: u64 = 0; + for (monkeys.items) |m| { + if (m.inspections > m1) { + m2 = m1; + m1 = m.inspections; + continue; + } + if (m.inspections > m2) { + m2 = m.inspections; + } + } + return m1 * m2; +} diff --git a/2022/11-monkey-in-the-middle/input b/2022/11-monkey-in-the-middle/input new file mode 100644 index 0000000..02baf95 --- /dev/null +++ b/2022/11-monkey-in-the-middle/input @@ -0,0 +1,55 @@ +Monkey 0: + Starting items: 99, 63, 76, 93, 54, 73 + Operation: new = old * 11 + Test: divisible by 2 + If true: throw to monkey 7 + If false: throw to monkey 1 + +Monkey 1: + Starting items: 91, 60, 97, 54 + Operation: new = old + 1 + Test: divisible by 17 + If true: throw to monkey 3 + If false: throw to monkey 2 + +Monkey 2: + Starting items: 65 + Operation: new = old + 7 + Test: divisible by 7 + If true: throw to monkey 6 + If false: throw to monkey 5 + +Monkey 3: + Starting items: 84, 55 + Operation: new = old + 3 + Test: divisible by 11 + If true: throw to monkey 2 + If false: throw to monkey 6 + +Monkey 4: + Starting items: 86, 63, 79, 54, 83 + Operation: new = old * old + Test: divisible by 19 + If true: throw to monkey 7 + If false: throw to monkey 0 + +Monkey 5: + Starting items: 96, 67, 56, 95, 64, 69, 96 + Operation: new = old + 4 + Test: divisible by 5 + If true: throw to monkey 4 + If false: throw to monkey 0 + +Monkey 6: + Starting items: 66, 94, 70, 93, 72, 67, 88, 51 + Operation: new = old * 5 + Test: divisible by 13 + If true: throw to monkey 4 + If false: throw to monkey 5 + +Monkey 7: + Starting items: 59, 59, 74 + Operation: new = old + 8 + Test: divisible by 3 + If true: throw to monkey 1 + If false: throw to monkey 3 diff --git a/2022/11-monkey-in-the-middle/second.zig b/2022/11-monkey-in-the-middle/second.zig new file mode 100644 index 0000000..86b74ff --- /dev/null +++ b/2022/11-monkey-in-the-middle/second.zig @@ -0,0 +1,129 @@ +const std = @import("std"); + +const example = @embedFile("example"); +const input = @embedFile("input"); + +pub fn main() anyerror!void { + var arena = std.heap.ArenaAllocator.init(std.heap.page_allocator); + defer arena.deinit(); + const allocator = arena.allocator(); + + try std.testing.expectEqual(try solve(example, allocator), 2713310158); + const result = try solve(input, allocator); + try std.io.getStdOut().writer().print("{}\n", .{result}); +} + +const Operation = struct { + first: ?u64, + operand: u8, + second: ?u64, + fn init(line: []const u8, allocator: std.mem.Allocator) !*Operation { + var o = try allocator.create(Operation); + var it = std.mem.tokenize(u8, line, " "); + _ = it.next() orelse unreachable; // Operation: + _ = it.next() orelse unreachable; // new + _ = it.next() orelse unreachable; // = + o.first = std.fmt.parseInt(u64, it.next() orelse unreachable, 10) catch null; + const tmp = it.next() orelse unreachable; + o.operand = tmp[0]; + o.second = std.fmt.parseInt(u64, it.next() orelse unreachable, 10) catch null; + return o; + } + fn run(o: Operation, v: u64) u64 { + const first = if (o.first) |f| f else v; + const second = if (o.second) |f| f else v; + switch (o.operand) { + '+' => return first + second, + '-' => return first - second, + '*' => return first * second, + '/' => return first / second, + else => unreachable, + } + } +}; + +const Monkey = struct { + inspections: u64, + items: std.ArrayList(u64), + operation: *Operation, + divisible: u64, // divisible by + testTrue: u64, + testFalse: u64, + fn init(it: *std.mem.TokenIterator(u8), allocator: std.mem.Allocator) !*Monkey { + var m = try allocator.create(Monkey); + m.inspections = 0; + m.items = std.ArrayList(u64).init(allocator); + var items = std.mem.tokenize(u8, it.next() orelse unreachable, " ,"); + _ = items.next() orelse unreachable; // starting + _ = items.next() orelse unreachable; // items: + while (items.next()) |item| { + try m.items.append(std.fmt.parseInt(u64, item, 10) catch unreachable); + } + m.operation = try Operation.init(it.next() orelse unreachable, allocator); + var divisible = std.mem.tokenize(u8, it.next() orelse unreachable, " "); + _ = divisible.next() orelse unreachable; // test: + _ = divisible.next() orelse unreachable; // divisible + _ = divisible.next() orelse unreachable; // by + m.divisible = std.fmt.parseInt(u64, divisible.next() orelse unreachable, 10) catch unreachable; + var testTrue = std.mem.tokenize(u8, it.next() orelse unreachable, " "); + _ = testTrue.next() orelse unreachable; // if + _ = testTrue.next() orelse unreachable; // true: + _ = testTrue.next() orelse unreachable; // throw + _ = testTrue.next() orelse unreachable; // to + _ = testTrue.next() orelse unreachable; // monkey + m.testTrue = std.fmt.parseInt(u64, testTrue.next() orelse unreachable, 10) catch unreachable; + var testFalse = std.mem.tokenize(u8, it.next() orelse unreachable, " "); + _ = testFalse.next() orelse unreachable; // if + _ = testFalse.next() orelse unreachable; // true: + _ = testFalse.next() orelse unreachable; // throw + _ = testFalse.next() orelse unreachable; // to + _ = testFalse.next() orelse unreachable; // monkey + m.testFalse = std.fmt.parseInt(u64, testFalse.next() orelse unreachable, 10) catch unreachable; + return m; + } + fn step(m: *Monkey, monkeys: []*Monkey, bigModulo: u64) !void { + m.inspections += m.items.items.len; + for (m.items.items) |item| { + const v = @mod(m.operation.run(item), bigModulo); + if (@mod(v, m.divisible) == 0) { + try monkeys[m.testTrue].items.append(v); + } else { + try monkeys[m.testFalse].items.append(v); + } + } + m.items.items.len = 0; + } +}; + +fn solve(puzzle: []const u8, allocator: std.mem.Allocator) !u64 { + var it = std.mem.tokenize(u8, puzzle, "\n"); + var monkeys = std.ArrayList(*Monkey).init(allocator); + var bigModulo: u64 = 1; + // process input + while (it.next()) |_| { + var m = try monkeys.addOne(); + m.* = try Monkey.init(&it, allocator); + bigModulo *= m.*.divisible; + } + // run 10k rounds + var rounds: usize = 0; + while (rounds < 10000) : (rounds += 1) { + for (monkeys.items) |m| { + try m.step(monkeys.items, bigModulo); + } + } + // find answer + var m1: u64 = 0; + var m2: u64 = 0; + for (monkeys.items) |m| { + if (m.inspections > m1) { + m2 = m1; + m1 = m.inspections; + continue; + } + if (m.inspections > m2) { + m2 = m.inspections; + } + } + return m1 * m2; +} -- cgit v1.2.3