diff options
Diffstat (limited to 'aoc/2021')
31 files changed, 945 insertions, 0 deletions
diff --git a/aoc/2021/01/part-one.py b/aoc/2021/01/part-one.py new file mode 100644 index 0000000..db9a650 --- /dev/null +++ b/aoc/2021/01/part-one.py @@ -0,0 +1,6 @@ +from itertools import tee +from sys import stdin + +old, new = tee(map(int, stdin.read().strip().split())) +next(new) +print(sum(o < n for o, n in zip(old, new))) diff --git a/aoc/2021/01/part-two.py b/aoc/2021/01/part-two.py new file mode 100644 index 0000000..c8b0ac9 --- /dev/null +++ b/aoc/2021/01/part-two.py @@ -0,0 +1,8 @@ +from itertools import tee +from sys import stdin + +old, new = tee(map(int, stdin.read().strip().split())) +next(new) +next(new) +next(new) +print(sum(o < n for o, n in zip(old, new))) diff --git a/aoc/2021/02/part-one.zig b/aoc/2021/02/part-one.zig new file mode 100644 index 0000000..68335d7 --- /dev/null +++ b/aoc/2021/02/part-one.zig @@ -0,0 +1,25 @@ +const eql = std.mem.eql; +const parseUnsigned = std.fmt.parseUnsigned; +const print = std.debug.print; +const std = @import("std"); +const tokenize = std.mem.tokenize; + +pub fn main() !void { + var position = @as(usize, 0); + var depth = @as(usize, 0); + defer print("{}\n", .{ position * depth }); + + var input = tokenize(@embedFile("input"), "\n"); + while (input.next()) |line| { + var command = tokenize(line, " "); + const direction = command.next().?; + const x = try parseUnsigned(usize, command.next().?, 10); + if (eql(u8, direction, "forward")) + position += x + else if (eql(u8, direction, "down")) + depth += x + else if (eql(u8, direction, "up")) + depth -= x + else unreachable; + } +} diff --git a/aoc/2021/02/part-two.zig b/aoc/2021/02/part-two.zig new file mode 100644 index 0000000..f597db6 --- /dev/null +++ b/aoc/2021/02/part-two.zig @@ -0,0 +1,27 @@ +const eql = std.mem.eql; +const parseUnsigned = std.fmt.parseUnsigned; +const print = std.debug.print; +const std = @import("std"); +const tokenize = std.mem.tokenize; + +pub fn main() !void { + var position = @as(usize, 0); + var depth = @as(usize, 0); + defer print("{}\n", .{ position * depth }); + + var aim = @as(usize, 0); + var input = tokenize(@embedFile("input"), "\n"); + while (input.next()) |line| { + var command = tokenize(line, " "); + const direction = command.next().?; + const x = try parseUnsigned(usize, command.next().?, 10); + if (eql(u8, direction, "forward")) { + position += x; + depth += aim * x; + } else if (eql(u8, direction, "down")) { + aim += x; + } else if (eql(u8, direction, "up")) { + aim -= x; + } else unreachable; + } +} diff --git a/aoc/2021/03/part-one.zig b/aoc/2021/03/part-one.zig new file mode 100644 index 0000000..0366434 --- /dev/null +++ b/aoc/2021/03/part-one.zig @@ -0,0 +1,19 @@ +const print = @import("std").debug.print; + +const input = @embedFile("input"); +const mean = @splat(12, @as(u16, '0' * 1000 + 500)); +const pos = @Vector(12, u4){ 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0 }; + +pub fn main() void { + var sum = @splat(12, @as(u16, 0)); + var i = @as(usize, 0); + while (i < input.len) : (i += 13) { + var j = @as(usize, 0); + while (j < 12) : (j += 1) + sum[j] += input[i + j]; + } + + const common = @bitCast(@Vector(12, u1), sum > mean); + const gamma = @reduce(.Add, @as(@Vector(12, u12), common) << pos); + print("{}\n", .{ @as(usize, gamma) * ~gamma }); +} diff --git a/aoc/2021/03/part-two.raku b/aoc/2021/03/part-two.raku new file mode 100644 index 0000000..71464a2 --- /dev/null +++ b/aoc/2021/03/part-two.raku @@ -0,0 +1,8 @@ +sub filter(&op, @report, $column=0) { + return parse-base @report[0].join, 2 unless @report.elems > 1; + my $common = ([+] map *[$column], @report) > (@report.elems - 1) div 2; + filter &op, (grep { op $_[$column], $common }, @report), $column + 1 +} + +my $input = map *.comb, words slurp 'input'; +put [*] map { filter $_, $input }, (&infix:<==>, &infix:<!=>) diff --git a/aoc/2021/04/part-one.zig b/aoc/2021/04/part-one.zig new file mode 100644 index 0000000..67dc4e0 --- /dev/null +++ b/aoc/2021/04/part-one.zig @@ -0,0 +1,48 @@ +const parseUnsigned = std.fmt.parseUnsigned; +const print = std.debug.print; +const std = @import("std"); +const tokenize = std.mem.tokenize; + +pub fn main() !void { + var boards: [100][5]@Vector(5, u16) = undefined; + var input = tokenize(@embedFile("input"), "\n"); + var order = tokenize(input.next().?, ","); + var i = @as(usize, 0); + while (i < 100) : (i += 1) { + var j = @as(usize, 0); + while (j < 5) : (j += 1) { + var row = tokenize(input.next().?, " "); + var k = @as(usize, 0); + while (k < 5) : (k += 1) + boards[i][j][k] = 1 + try parseUnsigned(u16, row.next().?, 10); + } + } + + const result = loop: while (i > 0) : (i -= 1) { + const n = 1 + try parseUnsigned(u16, order.next().?, 10); + var j = @as(usize, 0); + while (j < 100) : (j += 1) { + var u = @as(usize, 0); + var k = @as(usize, 0); + while (k < 5) : (k += 1) { + var l = @as(usize, 0); + while (l < 5) : (l += 1) { + if (boards[j][k][l] == n) + boards[j][k][l] = 0 + else if (boards[j][k][l] > 0) + u += 1; + } + } + + const b = boards[j]; + const sum = b[0] + b[1] + b[2] + b[3] + b[4]; + const result = (@reduce(.Add, sum) - u) * (n - 1); + if (@reduce(.Min, sum) == 0) + break :loop result; + for (b) |v| + if (@reduce(.Max, v) == 0) + break :loop result; + } + } else unreachable; + print("{}\n", .{ result }); +} diff --git a/aoc/2021/04/part-two.zig b/aoc/2021/04/part-two.zig new file mode 100644 index 0000000..ffe2c05 --- /dev/null +++ b/aoc/2021/04/part-two.zig @@ -0,0 +1,48 @@ +const parseUnsigned = std.fmt.parseUnsigned; +const print = std.debug.print; +const std = @import("std"); +const tokenize = std.mem.tokenize; + +pub fn main() !void { + var boards: [100][5]@Vector(5, u16) = undefined; + var input = tokenize(@embedFile("input"), "\n"); + var order = tokenize(input.next().?, ","); + var i = @as(usize, 0); + while (i < 100) : (i += 1) { + var j = @as(usize, 0); + while (j < 5) : (j += 1) { + var row = tokenize(input.next().?, " "); + var k = @as(usize, 0); + while (k < 5) : (k += 1) + boards[i][j][k] = 1 + try parseUnsigned(u16, row.next().?, 10); + } + } + + var won = @splat(100, false); + while (i > 0) : (i -= 1) { + const n = 1 + try parseUnsigned(u16, order.next().?, 10); + var j = @as(usize, 0); + while (j < 100) : (j += 1) { + var u = @as(usize, 0); + var k = @as(usize, 0); + while (k < 5) : (k += 1) { + var l = @as(usize, 0); + while (l < 5) : (l += 1) { + if (boards[j][k][l] == n) + boards[j][k][l] = 0 + else if (boards[j][k][l] > 0) + u += 1; + } + } + + const b = boards[j]; + const sum = b[0] + b[1] + b[2] + b[3] + b[4]; + won[j] = for (b) |v| { + if (@reduce(.Max, v) == 0) + break true; + } else @reduce(.Min, sum) == 0; + if (@reduce(.And, won)) + return print("{}\n", .{ (@reduce(.Add, sum) - u) * (n - 1) }); + } + } +} diff --git a/aoc/2021/05/part-one.zig b/aoc/2021/05/part-one.zig new file mode 100644 index 0000000..95ad5a8 --- /dev/null +++ b/aoc/2021/05/part-one.zig @@ -0,0 +1,46 @@ +const allocator = std.heap.page_allocator; +const parseUnsigned = std.fmt.parseUnsigned; +const print = std.debug.print; +const set = std.mem.set; +const swap = std.mem.swap; +const std = @import("std"); +const tokenize = std.mem.tokenize; + +inline fn index(x: usize, y: usize) usize { + return x * 1000 + y; +} + +pub fn main() !void { + const diagram = try allocator.alloc(u16, 1_000_000); + defer allocator.free(diagram); + set(u16, diagram, 0); + + var input = tokenize(@embedFile("input"), "\n"); + while (input.next()) |line| { + var segment = tokenize(line, " -> "); + var point = tokenize(segment.next().?, ","); + var x1 = try parseUnsigned(usize, point.next().?, 10); + var y1 = try parseUnsigned(usize, point.next().?, 10); + point = tokenize(segment.next().?, ","); + var x2 = try parseUnsigned(usize, point.next().?, 10); + var y2 = try parseUnsigned(usize, point.next().?, 10); + + if (x1 > x2) + swap(usize, &x1, &x2); + if (y1 > y2) + swap(usize, &y1, &y2); + + if (x1 == x2) { + while (y1 <= y2) : (y1 += 1) + diagram[index(x1, y1)] += 1; + } else if (y1 == y2) { + while (x1 <= x2) : (x1 += 1) + diagram[index(x1, y1)] += 1; + } + } + + var result: usize = 0; + for (diagram) |point| + result += @boolToInt(point > 1); + print("{}\n", .{ result }); +} diff --git a/aoc/2021/05/part-two.zig b/aoc/2021/05/part-two.zig new file mode 100644 index 0000000..2c7ed83 --- /dev/null +++ b/aoc/2021/05/part-two.zig @@ -0,0 +1,48 @@ +const allocator = std.heap.page_allocator; +const parseUnsigned = std.fmt.parseUnsigned; +const print = std.debug.print; +const set = std.mem.set; +const swap = std.mem.swap; +const std = @import("std"); +const tokenize = std.mem.tokenize; + +inline fn index(x: usize, y: usize) usize { + return x * 1000 + y; +} + +pub fn main() !void { + const diagram = try allocator.alloc(u16, 1_000_000); + defer allocator.free(diagram); + set(u16, diagram, 0); + + var input = tokenize(@embedFile("input"), "\n"); + while (input.next()) |line| { + var segment = tokenize(line, " -> "); + var point = tokenize(segment.next().?, ","); + var x1 = try parseUnsigned(usize, point.next().?, 10); + var y1 = try parseUnsigned(usize, point.next().?, 10); + point = tokenize(segment.next().?, ","); + var x2 = try parseUnsigned(usize, point.next().?, 10); + var y2 = try parseUnsigned(usize, point.next().?, 10); + + if (x1 == x2) { + if (y1 > y2) swap(usize, &y1, &y2); + while (y1 <= y2) : (y1 += 1) + diagram[index(x1, y1)] += 1; + } else if (y1 == y2) { + if (x1 > x2) swap(usize, &x1, &x2); + while (x1 <= x2) : (x1 += 1) + diagram[index(x1, y1)] += 1; + } else while (true) { + diagram[index(x1, y1)] += 1; + if (x1 == x2 or y1 == y2) break; + if (x1 > x2) x1 -= 1 else x1 += 1; + if (y1 > y2) y1 -= 1 else y1 += 1; + } + } + + var result: usize = 0; + for (diagram) |point| + result += @boolToInt(point > 1); + print("{}\n", .{ result }); +} diff --git a/aoc/2021/06/part-one.py b/aoc/2021/06/part-one.py new file mode 100644 index 0000000..f1ad2fb --- /dev/null +++ b/aoc/2021/06/part-one.py @@ -0,0 +1,9 @@ +from collections import deque +from sys import stdin + +timer = deque([0] * 9) +for i in map(int, stdin.read().strip().split(',')): timer[i] += 1 +for i in range(80): + timer.rotate(-1) + timer[6] += timer[-1] +print(sum(timer)) diff --git a/aoc/2021/06/part-two.zig b/aoc/2021/06/part-two.zig new file mode 100644 index 0000000..72bf877 --- /dev/null +++ b/aoc/2021/06/part-two.zig @@ -0,0 +1,22 @@ +const parseUnsigned = std.fmt.parseUnsigned; +const print = std.debug.print; +const rotate = std.mem.rotate; +const std = @import("std"); +const tokenize = std.mem.tokenize; + +const input = @embedFile("input"); + +pub fn main() !void { + var timer = [_]usize{ 0 } ** 9; + defer print("{}\n", .{ @reduce(.Add, @as(@Vector(9, usize), timer)) }); + + var list = tokenize(input[0..input.len-1], ","); + while (list.next()) |i| + timer[try parseUnsigned(usize, i, 10)] += 1; + + var i: usize = 0; + while (i < 256) : (i += 1) { + rotate(usize, timer[0..], 1); + timer[6] += timer[8]; + } +} diff --git a/aoc/2021/07/part-one.raku b/aoc/2021/07/part-one.raku new file mode 100644 index 0000000..81cb7d4 --- /dev/null +++ b/aoc/2021/07/part-one.raku @@ -0,0 +1,3 @@ +my @input = map +*, split ',', trim slurp 'input'; +sub cost($align) { [+] map { abs $align - $_ }, @input } +put min (cost $_ for (min @input)...(max @input)) diff --git a/aoc/2021/07/part-two.raku b/aoc/2021/07/part-two.raku new file mode 100644 index 0000000..d4934d9 --- /dev/null +++ b/aoc/2021/07/part-two.raku @@ -0,0 +1,4 @@ +my &cum = { $_ * ($_ + 1) div 2 }; +my @input = map +*, split ',', trim slurp 'input'; +sub cost($align) { [+] map { cum abs $align - $_ }, @input } +put min (cost $_ for (min @input)...(max @input)) diff --git a/aoc/2021/08/part-one.zig b/aoc/2021/08/part-one.zig new file mode 100644 index 0000000..9f879e8 --- /dev/null +++ b/aoc/2021/08/part-one.zig @@ -0,0 +1,18 @@ +const print = std.debug.print; +const std = @import("std"); +const tokenize = std.mem.tokenize; + +pub fn main() void { + var count: usize = 0; + defer print("{}\n", .{ count }); + + var input = tokenize(@embedFile("input"), "\n"); + while (input.next()) |line| { + var output = tokenize(line[61..], " "); + while (output.next()) |digit| + switch (digit.len) { + 2, 3, 4, 7 => count += 1, + else => {}, + }; + } +} diff --git a/aoc/2021/08/part-two.zig b/aoc/2021/08/part-two.zig new file mode 100644 index 0000000..ae8bf09 --- /dev/null +++ b/aoc/2021/08/part-two.zig @@ -0,0 +1,57 @@ +const indexOfScalar = std.mem.indexOfScalar; +const print = std.debug.print; +const std = @import("std"); +const tokenize = std.mem.tokenize; + +const digits = [_]u7{ + 0b1110111, + 0b0010010, + 0b1011101, + 0b1011011, + 0b0111010, + 0b1101011, + 0b1101111, + 0b1010010, + 0b1111111, + 0b1111011, + //8687497 +}; + +pub fn main() void { + var sum: usize = 0; + defer print("{}\n", .{ sum }); + + var input = tokenize(@embedFile("input"), "\n"); + while (input.next()) |line| { + var freq = [_]u8{ 0 } ** 7; + for (line[0..58]) |c| + switch (c) { + 'a'...'g' => freq[c - 'a'] += 1, + else => {}, + }; + + var patterns = tokenize(line[0..58], " "); + while (patterns.next()) |p| + if (p.len == 4) + for (freq) |*f, i| { + if (indexOfScalar(u8, p, 'a' + @intCast(u8, i))) |_| + f.* -= 6; + }; // 8687497 to 8021437 + + var display: [7]u3 = undefined; + for (freq) |f, i| + display[i] = switch (f) { + 8 => 0, 0 => 1, 2 => 2, 1 => 3, 4 => 4, 3 => 5, 7 => 6, + else => unreachable, + }; + + var output = tokenize(line[61..], " "); + var pow: usize = 1000; + while (output.next()) |s| : (pow /= 10) { + var digit: u7 = 0; + for (s) |c| + digit |= @as(u7, 0b1000000) >> display[c - 'a']; + sum += pow * indexOfScalar(u7, digits[0..], digit).?; + } + } +} diff --git a/aoc/2021/09/part-one.zig b/aoc/2021/09/part-one.zig new file mode 100644 index 0000000..8e3ae15 --- /dev/null +++ b/aoc/2021/09/part-one.zig @@ -0,0 +1,33 @@ +const print = std.debug.print; +const std = @import("std"); + +const input = @embedFile("input"); + +inline fn get(x: i8, y: i8) u8 { + return switch (x) { + 0...99 => switch (y) { + 0...99 => input[@intCast(usize, x) + @intCast(usize, y) * 101], + else => ':', + }, + else => ':', + }; +} + +pub fn main() void { + var sum: usize = 0; + defer print("{}\n", .{ sum }); + + var row: i8 = 0; + while (row < 100) : (row += 1) { + var col: i8 = 0; + while (col < 100) : (col += 1) { + const height = get(col, row); + sum += @boolToInt(@reduce(.And, @Vector(4, u8){ + get(col + 1, row), + get(col, row + 1), + get(col - 1, row), + get(col, row - 1), + } > @splat(4, height))) * (height - '/'); + } + } +} diff --git a/aoc/2021/09/part-two.py b/aoc/2021/09/part-two.py new file mode 100644 index 0000000..99524c4 --- /dev/null +++ b/aoc/2021/09/part-two.py @@ -0,0 +1,20 @@ +from collections import deque +from functools import reduce +from operator import mul +from sys import stdin + +heightmap = [[int(c) for c in s] for s in stdin.read().strip().split()] +get = lambda y, x: 10 if min(x, y) < 0 or max(x, y) > 99 else heightmap[y][x] +adjacent = lambda y, x: ((y, x + 1), (y + 1, x), (y, x - 1), (y - 1, x)) +basins = {(i, j): 0 for i, row in enumerate(heightmap) + for j, height in enumerate(row) + if all(height < get(y, x) for y, x in adjacent(i, j))} +queue, visited = deque((key, key) for key in basins), set() +while queue: + key, pos = queue.popleft() + if pos in visited: continue + basins[key] += 1 + visited.add(pos) + for adj in adjacent(*pos): + if get(*adj) < 9 and adj not in visited: queue.append((key, adj)) +print(reduce(mul, sorted(basins.values(), reverse=True)[:3])) diff --git a/aoc/2021/10/Stack.zig b/aoc/2021/10/Stack.zig new file mode 100644 index 0000000..1aab8eb --- /dev/null +++ b/aoc/2021/10/Stack.zig @@ -0,0 +1,35 @@ +const Allocator = @import("std").mem.Allocator; +const Self = @This(); + +allocator: *Allocator, +memory: []u8, +len: usize, + +pub fn alloc(allocator: *Allocator, size: usize) !Self { + return Self{ + .allocator = allocator, + .memory = try allocator.alloc(u8, size), + .len = 0, + }; +} + +pub fn free(self: *Self) void { + self.allocator.free(self.memory); + self.* = undefined; +} + +pub fn push(self: *Self, node: u8) void { + self.memory[self.len] = node; + self.len += 1; +} + +pub fn pop(self: *Self) ?u8 { + if (self.len < 1) + return null; + self.len -= 1; + return self.memory[self.len]; +} + +pub fn reset(self: *Self) void { + self.len = 0; +} diff --git a/aoc/2021/10/part-one.zig b/aoc/2021/10/part-one.zig new file mode 100644 index 0000000..130fc4a --- /dev/null +++ b/aoc/2021/10/part-one.zig @@ -0,0 +1,32 @@ +const Stack = @import("Stack.zig"); +const page_allocator = std.heap.page_allocator; +const print = std.debug.print; +const std = @import("std"); +const tokenize = std.mem.tokenize; + +pub fn main() !void { + var input = tokenize(@embedFile("input"), "\n"); + var max_len: usize = 0; + while (input.next()) |line| { + if (line.len > max_len) + max_len = line.len; + } + var stack = try Stack.alloc(page_allocator, max_len); + defer stack.free(); + + var sum: usize = 0; + defer print("{}\n", .{ sum }); + input.reset(); + while (input.next()) |line| : (stack.reset()) + for (line) |c| + switch (c) { + '(', '[', '{', '<' => stack.push(c), + else => if (stack.pop().? ^ c > 6) { + sum += @as(usize, switch (c) { + ')' => 3, ']' => 57, '}' => 1197, '>' => 25137, + else => unreachable, + }); + break; + }, + }; +} diff --git a/aoc/2021/10/part-two.zig b/aoc/2021/10/part-two.zig new file mode 100644 index 0000000..4578272 --- /dev/null +++ b/aoc/2021/10/part-two.zig @@ -0,0 +1,44 @@ +const Stack = @import("Stack.zig"); +const desc = std.sort.desc(usize); +const indexOfScalar = std.mem.indexOfScalar; +const page_allocator = std.heap.page_allocator; +const print = std.debug.print; +const sort = std.sort.sort; +const std = @import("std"); +const tokenize = std.mem.tokenize; + +pub fn main() !void { + var input = tokenize(@embedFile("input"), "\n"); + var i: usize = 0; + var max_len: usize = 0; + while (input.next()) |line| : (i += 1) { + if (line.len > max_len) + max_len = line.len; + } + var stack = try Stack.alloc(page_allocator, max_len); + defer stack.free(); + + var scores = try page_allocator.alloc(usize, i); + defer page_allocator.free(scores); + input.reset(); + loop: while (input.next()) |line| : (stack.reset()) { + i -= 1; + scores[i] = 0; + for (line) |c| + switch (c) { + '(', '[', '{', '<' => stack.push(c), + else => if (stack.pop().? ^ c > 6) continue :loop, + }; + while (stack.pop()) |c| { + scores[i] *= 5; + scores[i] += @as(usize, switch (c) { + '(' => 1, '[' => 2, '{' => 3, '<' => 4, + else => unreachable, + }); + } + } + + sort(usize, scores, {}, desc); + i = indexOfScalar(usize, scores, 0).?; + print("{}\n", .{ scores[i / 2] }); +} diff --git a/aoc/2021/11/part-one.raku b/aoc/2021/11/part-one.raku new file mode 100644 index 0000000..88cf4eb --- /dev/null +++ b/aoc/2021/11/part-one.raku @@ -0,0 +1,12 @@ +sub adj($i, $k) { [&&] map -2 < * < 2, [«-»] map { polymod $_: 10 }, ($i, $k) } +sub flash(@level, $count) { + my $i = first * > 9, @level, :k; + return ({ max $_, 0 } for @level), $count without $i; + flash ({ $i == $^k ?? -8 !! $^v + adj $i, $^k } for @level.kv), $count + 1 +} +sub step($times, @level, $count=0) { + return $count unless $times > 0; + step $times - 1, |flash @level »+» 1, $count +} +my $input = lines slurp 'input'; +put step 100, $input.join.comb diff --git a/aoc/2021/11/part-two.raku b/aoc/2021/11/part-two.raku new file mode 100644 index 0000000..a362b16 --- /dev/null +++ b/aoc/2021/11/part-two.raku @@ -0,0 +1,9 @@ +sub adj($i, $k) { [&&] map -2 < * < 2, [«-»] map { polymod $_: 10 }, ($i, $k) } +sub flash(@level) { + my $i = first * > 9, @level, :k; + return map { max $_, 0 }, @level without $i; + flash map { $i == $^k ?? -8 !! $^v + adj $i, $^k }, @level.kv +} +sub step(@level) { (0 == all @level) ?? 0 !! 1 + step flash @level »+» 1 } +my $input = lines slurp 'input'; +put step $input.join.comb diff --git a/aoc/2021/12/part-one.py b/aoc/2021/12/part-one.py new file mode 100644 index 0000000..7ab0e56 --- /dev/null +++ b/aoc/2021/12/part-one.py @@ -0,0 +1,19 @@ +from collections import defaultdict, deque +from itertools import permutations +from sys import stdin + +edges = defaultdict(list) +for line in stdin.read().strip().split(): + for key, value in permutations(line.split('-')): + if key != 'end' and value != 'start': edges[key].append(value) +paths = set() +queue = deque([('start',)]) +while queue: + if (head := queue.popleft()) in paths: continue + paths.add(head) + if (chin := head[-1]) == 'end': continue + for neck in edges[chin]: + if neck.islower() and neck in head: continue + top = head + (neck,) + queue.append(top) +print(sum(path[-1] == 'end' for path in paths)) diff --git a/aoc/2021/12/part-two.py b/aoc/2021/12/part-two.py new file mode 100644 index 0000000..7d87da7 --- /dev/null +++ b/aoc/2021/12/part-two.py @@ -0,0 +1,20 @@ +from collections import defaultdict, deque +from itertools import groupby, permutations +from sys import stdin + +edges = defaultdict(list) +for line in stdin.read().strip().split(): + for key, value in permutations(line.split('-')): + if key != 'end' and value != 'start': edges[key].append(value) +paths = set() +queue = deque([('start',)]) +while queue: + if (head := queue.popleft()) in paths: continue + paths.add(head) + if (chin := head[-1]) == 'end': continue + for neck in edges[chin]: + top = head + (neck,) + if sum(len(tuple(group)) - 1 for cave, group in groupby(sorted(top)) + if cave.islower()) > 1: continue + queue.append(top) +print(sum(path[-1] == 'end' for path in paths)) diff --git a/aoc/2021/13/part-one.zig b/aoc/2021/13/part-one.zig new file mode 100644 index 0000000..bdd28eb --- /dev/null +++ b/aoc/2021/13/part-one.zig @@ -0,0 +1,36 @@ +const ArenaAllocator = std.heap.ArenaAllocator; +const AutoHashMap = std.AutoHashMap; +const min = std.math.min; +const page_allocator = std.heap.page_allocator; +const parseUnsigned = std.fmt.parseUnsigned; +const print = std.debug.print; +const split = std.mem.split; +const std = @import("std"); +const tokenize = std.mem.tokenize; + +const Dot = struct { x: u12, y: u12 }; +inline fn mirror(a: u12, m: u12) u12 { return min(a, m + m - a); } +fn foldX(d: Dot, m: u12) Dot { return .{ .x = mirror(d.x, m), .y = d.y }; } +fn foldY(d: Dot, m: u12) Dot { return .{ .x = d.x, .y = mirror(d.y, m) }; } + +pub fn main() !void { + var arena = ArenaAllocator.init(page_allocator); + defer arena.deinit(); + var map = AutoHashMap(Dot, void).init(&arena.allocator); + defer map.deinit(); + defer print("{}\n", .{ map.count() }); + + var input = split(@embedFile("input"), "\n\n"); + var dots = tokenize(input.next().?, "\n"); + var folds = tokenize(input.next().?, "\n"); + const instruction = folds.next().?; + while (dots.next()) |line| { + var coord = tokenize(line, ","); + const dot = Dot{ .x = try parseUnsigned(u12, coord.next().?, 10), + .y = try parseUnsigned(u12, coord.next().?, 10) }; + try map.put(switch (instruction[11]) { + 'x' => foldX, 'y' => foldY, + else => unreachable, + } (dot, try parseUnsigned(u12, instruction[13..], 10)), {}); + } +} diff --git a/aoc/2021/13/part-two.zig b/aoc/2021/13/part-two.zig new file mode 100644 index 0000000..f42ebff --- /dev/null +++ b/aoc/2021/13/part-two.zig @@ -0,0 +1,31 @@ +const min = std.math.min; +const parseUnsigned = std.fmt.parseUnsigned; +const print = std.debug.print; +const split = std.mem.split; +const std = @import("std"); +const tokenize = std.mem.tokenize; + +const Dot = struct { x: u12, y: u12 }; +inline fn mirror(a: u12, m: u12) u12 { return min(a, m + m - a); } +fn foldX(d: Dot, m: u12) Dot { return .{ .x = mirror(d.x, m), .y = d.y }; } +fn foldY(d: Dot, m: u12) Dot { return .{ .x = d.x, .y = mirror(d.y, m) }; } + +pub fn main() !void { + var input = split(@embedFile("input"), "\n\n"); + var dots = tokenize(input.next().?, "\n"); + var folds = tokenize(input.next().?, "\n"); + var code = @bitCast([6][40]u8, ([_]u8{ ' ' } ** 39 ++ [_]u8{ '\n' }) ** 6); + defer print("{s}", .{ @bitCast([240]u8, code) }); + + while (dots.next()) |line| : (folds.reset()) { + var coord = tokenize(line, ","); + var dot = Dot{ .x = try parseUnsigned(u12, coord.next().?, 10), + .y = try parseUnsigned(u12, coord.next().?, 10) }; + while (folds.next()) |instruction| + dot = switch (instruction[11]) { + 'x' => foldX, 'y' => foldY, + else => unreachable, + } (dot, try parseUnsigned(u12, instruction[13..], 10)); + code[dot.y][dot.x] = '|'; + } +} diff --git a/aoc/2021/14/part-one.zig b/aoc/2021/14/part-one.zig new file mode 100644 index 0000000..0f50c10 --- /dev/null +++ b/aoc/2021/14/part-one.zig @@ -0,0 +1,75 @@ +const AutoHashMap = std.AutoHashMap; +const FixedBufferAllocator = std.heap.FixedBufferAllocator; +const math = std.math; +const print = std.debug.print; +const split = std.mem.split; +const std = @import("std"); +const tokenize = std.mem.tokenize; + +const Children = packed struct { left: Pair, right: Pair }; +const Pair = packed struct { left: u8, right: u8 }; +const Rule = packed struct { adj: Pair, _: u32, ins: u8 }; + +fn KV(comptime M: type, comptime index: usize) type { + const type_info = @typeInfo(@typeInfo(M).Pointer.child.KV); + return type_info.Struct.fields[index].field_type; +} + +fn addOrPut(map: anytype, key: KV(@TypeOf(map), 0), + value: KV(@TypeOf(map), 1)) !void { + const result = try map.getOrPut(key); + if (result.found_existing) + result.value_ptr.* += value + else + result.value_ptr.* = value; +} + +pub fn main() !void { + var buffer: [0xdecaf]u8 = undefined; + var fba = FixedBufferAllocator.init(buffer[0..]); + var input = split(@embedFile("input"), "\n\n"); + var count = AutoHashMap(Pair, usize).init(&fba.allocator); + defer count.deinit(); + const template = input.next().?; + for (template[0..template.len-1]) |*c| + try addOrPut(&count, @ptrCast(*const Pair, c).*, 1); + + var rules = tokenize(input.next().?, "\n"); + var insertions = AutoHashMap(Pair, Children).init(&fba.allocator); + defer insertions.deinit(); + while (rules.next()) |rule| { + const unmasked = @ptrCast(*const Rule, rule.ptr); + try insertions.put(unmasked.adj, .{ + .left = .{ .left = unmasked.adj.left, .right = unmasked.ins }, + .right = .{ .left = unmasked.ins, .right = unmasked.adj.right }, + }); + } + + var result = AutoHashMap(u8, usize).init(&fba.allocator); + for (template) |c| + try addOrPut(&result, c, 1); + + var step: u8 = 0; + while (step < 10) : (step += 1) { + var tmp = AutoHashMap(Pair, usize).init(&fba.allocator); + var items = count.iterator(); + while (items.next()) |entry| { + const k = insertions.get(entry.key_ptr.*) orelse continue; + const v = entry.value_ptr.*; + try addOrPut(&tmp, k.left, v); + try addOrPut(&tmp, k.right, v); + try addOrPut(&result, k.left.right, v); + } + count.deinit(); + count = tmp; + } + + var values = result.valueIterator(); + var max = values.next().?.*; + var min = max; + while (values.next()) |value| { + max = math.max(value.*, max); + min = math.min(value.*, min); + } + print("{}\n", .{ max - min }); +} diff --git a/aoc/2021/14/part-two.zig b/aoc/2021/14/part-two.zig new file mode 100644 index 0000000..3f8bf1f --- /dev/null +++ b/aoc/2021/14/part-two.zig @@ -0,0 +1,75 @@ +const AutoHashMap = std.AutoHashMap; +const FixedBufferAllocator = std.heap.FixedBufferAllocator; +const math = std.math; +const print = std.debug.print; +const split = std.mem.split; +const std = @import("std"); +const tokenize = std.mem.tokenize; + +const Children = packed struct { left: Pair, right: Pair }; +const Pair = packed struct { left: u8, right: u8 }; +const Rule = packed struct { adj: Pair, _: u32, ins: u8 }; + +fn KV(comptime M: type, comptime index: usize) type { + const type_info = @typeInfo(@typeInfo(M).Pointer.child.KV); + return type_info.Struct.fields[index].field_type; +} + +fn addOrPut(map: anytype, key: KV(@TypeOf(map), 0), + value: KV(@TypeOf(map), 1)) !void { + const result = try map.getOrPut(key); + if (result.found_existing) + result.value_ptr.* += value + else + result.value_ptr.* = value; +} + +pub fn main() !void { + var buffer: [0xdecaf]u8 = undefined; + var fba = FixedBufferAllocator.init(buffer[0..]); + var input = split(@embedFile("input"), "\n\n"); + var count = AutoHashMap(Pair, usize).init(&fba.allocator); + defer count.deinit(); + const template = input.next().?; + for (template[0..template.len-1]) |*c| + try addOrPut(&count, @ptrCast(*const Pair, c).*, 1); + + var rules = tokenize(input.next().?, "\n"); + var insertions = AutoHashMap(Pair, Children).init(&fba.allocator); + defer insertions.deinit(); + while (rules.next()) |rule| { + const unmasked = @ptrCast(*const Rule, rule.ptr); + try insertions.put(unmasked.adj, .{ + .left = .{ .left = unmasked.adj.left, .right = unmasked.ins }, + .right = .{ .left = unmasked.ins, .right = unmasked.adj.right }, + }); + } + + var result = AutoHashMap(u8, usize).init(&fba.allocator); + for (template) |c| + try addOrPut(&result, c, 1); + + var step: u8 = 0; + while (step < 40) : (step += 1) { + var tmp = AutoHashMap(Pair, usize).init(&fba.allocator); + var items = count.iterator(); + while (items.next()) |entry| { + const k = insertions.get(entry.key_ptr.*) orelse continue; + const v = entry.value_ptr.*; + try addOrPut(&tmp, k.left, v); + try addOrPut(&tmp, k.right, v); + try addOrPut(&result, k.left.right, v); + } + count.deinit(); + count = tmp; + } + + var values = result.valueIterator(); + var max = values.next().?.*; + var min = max; + while (values.next()) |value| { + max = math.max(value.*, max); + min = math.min(value.*, min); + } + print("{}\n", .{ max - min }); +} diff --git a/aoc/2021/15/part-one.zig b/aoc/2021/15/part-one.zig new file mode 100644 index 0000000..700bcf4 --- /dev/null +++ b/aoc/2021/15/part-one.zig @@ -0,0 +1,53 @@ +const FixedBufferAllocator = std.heap.FixedBufferAllocator; +const Order = std.math.Order; +const PQ = std.PriorityQueue; +const input = @embedFile("input"); +const order = std.math.order; +const print = std.debug.print; +const std = @import("std"); + +const Risk = packed struct { + x: u7, + y: u7, + v: u18, + + pub fn lt(self: Risk, other: Risk) Order { + return order(self.v, other.v); + } + + pub fn move(self: Risk, queue: *PQ(Risk), dx: i8, dy: i8) !void { + switch (self.x + dx) { + 0...99 => |x| switch (self.y + dy) { + 0...99 => |y| try queue.add(.{ + .x = @intCast(u7, x), .y = @intCast(u7, y), + .v = self.v + input[@intCast(usize, x) + + @intCast(usize, y) * 101] - '0', + }), + else => {}, + }, + else => {}, + } + } +}; + +pub fn main() !void { + var visited = [_][100]bool{ [_]bool{ false } ** 100 } ** 100; + var buffer: [0xbeef]u8 = undefined; + var fba = FixedBufferAllocator.init(buffer[0..]); + var queue = PQ(Risk).init(&fba.allocator, Risk.lt); + try queue.add(.{ .x = 0, .y = 0, .v = 0 }); + const result = while (queue.count() > 0) { + const best = queue.remove(); + if (best.x == 99 and best.y == 99) + break best.v; + if (visited[best.x][best.y]) + continue + else + visited[best.x][best.y] = true; + try best.move(&queue, 1, 0); + try best.move(&queue, 0, 1); + try best.move(&queue, -1, 0); + try best.move(&queue, 0, -1); + } else unreachable; + print("{}\n", .{ result }); +} diff --git a/aoc/2021/15/part-two.zig b/aoc/2021/15/part-two.zig new file mode 100644 index 0000000..452a6c9 --- /dev/null +++ b/aoc/2021/15/part-two.zig @@ -0,0 +1,55 @@ +const FixedBufferAllocator = std.heap.FixedBufferAllocator; +const Order = std.math.Order; +const PQ = std.PriorityQueue; +const input = @embedFile("input"); +const order = std.math.order; +const print = std.debug.print; +const std = @import("std"); + +const Risk = packed struct { + x: u9, + y: u9, + v: u22, + + pub fn lt(self: Risk, other: Risk) Order { + return order(self.v, other.v); + } + + pub fn move(self: Risk, queue: *PQ(Risk), dx: i10, dy: i10) !void { + switch (self.x + dx) { + 0...499 => |x| switch (self.y + dy) { + 0...499 => |y| try queue.add(.{ + .v = self.v + @intCast(u22, + input[@intCast(usize, @rem(x, 100)) + + @intCast(usize, @rem(y, 100)) * 101] - '1' + + @divTrunc(x, 100) + @divTrunc(y, 100)) % 9 + 1, + .x = @intCast(u9, x), .y = @intCast(u9, y), + }), + else => {}, + }, + else => {}, + } + } +}; + +pub fn main() !void { + var visited = [_][500]bool{ [_]bool{ false } ** 500 } ** 500; + var buffer: [0xbeef]u8 = undefined; + var fba = FixedBufferAllocator.init(buffer[0..]); + var queue = PQ(Risk).init(&fba.allocator, Risk.lt); + try queue.add(.{ .x = 0, .y = 0, .v = 0 }); + const result = while (queue.count() > 0) { + const best = queue.remove(); + if (best.x == 499 and best.y == 499) + break best.v; + if (visited[best.x][best.y]) + continue + else + visited[best.x][best.y] = true; + try best.move(&queue, 1, 0); + try best.move(&queue, 0, 1); + try best.move(&queue, -1, 0); + try best.move(&queue, 0, -1); + } else unreachable; + print("{}\n", .{ result }); +} |