aboutsummaryrefslogtreecommitdiff
path: root/2022/11-monkey-in-the-middle
diff options
context:
space:
mode:
Diffstat (limited to '2022/11-monkey-in-the-middle')
-rw-r--r--2022/11-monkey-in-the-middle/example27
-rw-r--r--2022/11-monkey-in-the-middle/first.zig126
-rw-r--r--2022/11-monkey-in-the-middle/input55
-rw-r--r--2022/11-monkey-in-the-middle/second.zig129
4 files changed, 337 insertions, 0 deletions
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;
+}
generated by cgit v1.2.3 (git 2.39.1) at 2024-11-22 04:21:15 +0000