diff options
Diffstat (limited to 'aoc')
61 files changed, 1592 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 }); +} diff --git a/aoc/2022/01/part-one.sh b/aoc/2022/01/part-one.sh new file mode 100755 index 0000000..a0e0095 --- /dev/null +++ b/aoc/2022/01/part-one.sh @@ -0,0 +1,2 @@ +#!/bin/sh +sed 's/$/+/' | { echo 0; sed 's/^+$/p0/'; echo p; } | dc | sort -n | tail -1 diff --git a/aoc/2022/01/part-two.sh b/aoc/2022/01/part-two.sh new file mode 100755 index 0000000..a5a4d77 --- /dev/null +++ b/aoc/2022/01/part-two.sh @@ -0,0 +1,3 @@ +#!/bin/sh +sed 's/$/+/' | { echo 0; sed 's/^+$/p0/'; echo p; } | dc | + sort -n | tail -n 3 | { echo 0; sed 's/$/+/'; echo p; } | dc diff --git a/aoc/2022/02/part-one.ha b/aoc/2022/02/part-one.ha new file mode 100644 index 0000000..7a49de0 --- /dev/null +++ b/aoc/2022/02/part-one.ha @@ -0,0 +1,30 @@ +use bufio; +use fmt; +use io; +use os; + +fn scanbyte(file: io::handle) u8 = { + match (bufio::scanbyte(os::stdin)!) { + case let byte: u8 => + return byte; + case io::EOF => + fmt::fatal("Unexpected EOF"); + }; +}; + +export fn main() void = { + let score: u16 = 0; + for (true) { + const them = 'D' - (match (bufio::scanbyte(os::stdin)!) { + case let byte: u8 => + yield byte; + case io::EOF => + break; + }); + scanbyte(os::stdin); + const us = scanbyte(os::stdin) - 'W'; + scanbyte(os::stdin); + score += us + (us + them) % 3 * 3; + }; + fmt::println(score)!; +}; diff --git a/aoc/2022/02/part-two.ha b/aoc/2022/02/part-two.ha new file mode 100644 index 0000000..da7ab52 --- /dev/null +++ b/aoc/2022/02/part-two.ha @@ -0,0 +1,30 @@ +use bufio; +use fmt; +use io; +use os; + +fn scanbyte(file: io::handle) u8 = { + match (bufio::scanbyte(os::stdin)!) { + case let byte: u8 => + return byte; + case io::EOF => + fmt::fatal("Unexpected EOF"); + }; +}; + +export fn main() void = { + let score: u16 = 0; + for (true) { + const opponent = match (bufio::scanbyte(os::stdin)!) { + case let byte: u8 => + yield byte; + case io::EOF => + break; + } - '?'; + scanbyte(os::stdin); + const outcome = scanbyte(os::stdin) - 'X'; + scanbyte(os::stdin); + score += (opponent + outcome) % 3 + 1 + outcome * 3; + }; + fmt::println(score)!; +}; diff --git a/aoc/2022/03/part-one.nim b/aoc/2022/03/part-one.nim new file mode 100644 index 0000000..0f16754 --- /dev/null +++ b/aoc/2022/03/part-one.nim @@ -0,0 +1,19 @@ +import math +import sequtils +import sets +import strutils + +func priority(item: int): int = + result = item - 96 + if result < 0: + result += 58 + +func examine(sack: string): int = + let + size = sack.len div 2 + other = to_hash_set sack[0 ..< size] + for c in sack[size .. ^1]: + if c in other: + return priority ord c + +echo sum stdin.read_all.strip.split_lines.map examine diff --git a/aoc/2022/03/part-two.nim b/aoc/2022/03/part-two.nim new file mode 100644 index 0000000..ef27011 --- /dev/null +++ b/aoc/2022/03/part-two.nim @@ -0,0 +1,16 @@ +import math +import sequtils +import sets +import strutils + +func priority(group: seq[string]): int = + let sets = group.map_it it.to_hash_set + var common = sets.foldl a * b + result = common.pop.ord - 96 + if result < 0: + result += 58 + +let + elves = split_lines strip read_all stdin + groups = elves.distribute elves.len div 3 +echo sum groups.map priority diff --git a/aoc/2022/04/part-one.jl b/aoc/2022/04/part-one.jl new file mode 100755 index 0000000..3f409ea --- /dev/null +++ b/aoc/2022/04/part-one.jl @@ -0,0 +1,8 @@ +#!/usr/bin/env julia +function containing(line) + (a, b), (c, d) = map(r -> map(i -> parse(Int16, i), + split(r, '-')), + split(line, ',')) + (c - a) * (d - b) <= 0 +end +println(sum(map(containing, readlines(stdin)))) diff --git a/aoc/2022/04/part-two.jl b/aoc/2022/04/part-two.jl new file mode 100755 index 0000000..9f4dbaf --- /dev/null +++ b/aoc/2022/04/part-two.jl @@ -0,0 +1,8 @@ +#!/usr/bin/env julia +function overlapping(line) + (a, b), (c, d) = map(r -> map(i -> parse(Int16, i), + split(r, '-')), + split(line, ',')) + !(b < c || d < a) +end +println(sum(map(overlapping, readlines(stdin)))) diff --git a/aoc/2022/05/part-one.rb b/aoc/2022/05/part-one.rb new file mode 100755 index 0000000..4e11ce9 --- /dev/null +++ b/aoc/2022/05/part-one.rb @@ -0,0 +1,10 @@ +#!/usr/bin/env ruby +drawing, procedure = ARGF.read.split /\n.*\n\n/ +first, *rest = (drawing.split "\n").map { |line| (line.scan /.(.). ?/) } +stacks = (first.zip *rest).map { |stack| stack.join.strip.reverse } +for line in procedure.split "\n" + n, from, to = (line.scan /\d+/).map &:to_i + stacks[to - 1] << stacks[from - 1][-n..].reverse + stacks[from - 1].slice! -n.. +end +puts (stacks.map { |stack| stack[-1] }).join diff --git a/aoc/2022/05/part-two.rb b/aoc/2022/05/part-two.rb new file mode 100755 index 0000000..1cabf1b --- /dev/null +++ b/aoc/2022/05/part-two.rb @@ -0,0 +1,10 @@ +#!/usr/bin/env ruby +drawing, procedure = ARGF.read.split /\n.*\n\n/ +first, *rest = (drawing.split "\n").map { |line| (line.scan /.(.). ?/) } +stacks = (first.zip *rest).map { |stack| stack.join.strip.reverse } +for line in procedure.split "\n" + n, from, to = (line.scan /\d+/).map &:to_i + stacks[to - 1] << stacks[from - 1][-n..] + stacks[from - 1].slice! -n.. +end +puts (stacks.map { |stack| stack[-1] }).join diff --git a/aoc/2022/06/part-one.d b/aoc/2022/06/part-one.d new file mode 100644 index 0000000..c914704 --- /dev/null +++ b/aoc/2022/06/part-one.d @@ -0,0 +1,24 @@ +import core.stdc.stdio : getchar, printf; + +extern(C) void main() +{ + slide: for (auto q = 0u, i = 1u; q & 0xffu ^ '\n'; ++i) + { + q <<= 8u; + q |= getchar(); + if (i < 4) + continue; + + auto p = cast(ubyte*) &q; + for (auto s = 0u, j = 0u; j < 4u; ++j) + { + auto b = 1u << (p[j] & 0x1fu); + if (s & b) + continue slide; + s |= b; + } + + printf("%d\n", i); + break; + } +} diff --git a/aoc/2022/06/part-two.d b/aoc/2022/06/part-two.d new file mode 100644 index 0000000..4465e38 --- /dev/null +++ b/aoc/2022/06/part-two.d @@ -0,0 +1,26 @@ +import core.int128 : Cent, and, or, shl, tst, xor; +import core.stdc.stdio : getchar, printf; + +extern(C) void main() +{ + slide: for (auto q = cast(Cent) 0u, i = 1u; + tst(xor(and(q, cast(Cent) 0xff), cast(Cent) '\n')); + ++i) + { + q = or(shl(q, 8u), cast(Cent) getchar()); + if (i < 14) + continue; + + auto p = cast(ubyte*) &q; + for (auto s = 0u, j = 0u; j < 14u; ++j) + { + auto b = 1u << (p[j] & 0x1fu); + if (s & b) + continue slide; + s |= b; + } + + printf("%d\n", i); + break; + } +} diff --git a/aoc/2022/07/part-one.janet b/aoc/2022/07/part-one.janet new file mode 100755 index 0000000..fba92e5 --- /dev/null +++ b/aoc/2022/07/part-one.janet @@ -0,0 +1,58 @@ +#!/usr/bin/env janet +(def grammar + ~{:filename (<- (some :S)) + :dirname (+ (/ "/" :root) + (/ ".." :parent) + :filename) + :cd (* "$ cd " (constant :cd) + :dirname + "\n") + :file (* (<- :d+) + " " + (constant :name) + :filename) + :dir (* (constant :dir) + "dir " + (constant :name) + :dirname) + :ls (* "$ ls\n" (constant :ls) + (group (any (/ (* (constant :stat) + (+ :file :dir) + "\n") + ,struct)))) + :main (some (/ (+ :cd :ls) + ,tuple))}) + +(defn du [fs] + (if (number? fs) + [fs] + (reduce (fn [[parent & children] [child & grandchildren]] + [(+ parent child) + (splice children) + (if (empty? grandchildren) + [] + [child (splice grandchildren)])]) + [0] + (map du (values fs))))) + +(var path nil) +(let [fs (table)] + (each [cmd rest] + (peg/match grammar (:read stdin :all)) + (cond (= cmd :ls) (each {:name name :stat stat} + rest + (set ((array/peek path) + name) + (if (= stat :dir) + (table) + (scan-number stat)))) + (= rest :root) (set path (array fs)) + (= rest :parent) (array/pop path) + (let [last (array/peek path)] + (unless (last rest) + (set (last rest) + (table))) + (array/push path (last rest))))) + (print (+ (splice (filter (fn [n] + (<= n 100_000)) + (flatten (du fs))))))) diff --git a/aoc/2022/07/part-two.janet b/aoc/2022/07/part-two.janet new file mode 100755 index 0000000..36c25f1 --- /dev/null +++ b/aoc/2022/07/part-two.janet @@ -0,0 +1,60 @@ +#!/usr/bin/env janet +(def grammar + ~{:filename (<- (some :S)) + :dirname (+ (/ "/" :root) + (/ ".." :parent) + :filename) + :cd (* "$ cd " (constant :cd) + :dirname + "\n") + :file (* (<- :d+) + " " + (constant :name) + :filename) + :dir (* (constant :dir) + "dir " + (constant :name) + :dirname) + :ls (* "$ ls\n" (constant :ls) + (group (any (/ (* (constant :stat) + (+ :file :dir) + "\n") + ,struct)))) + :main (some (/ (+ :cd :ls) + ,tuple))}) + +(defn du [fs] + (if (number? fs) + [fs] + (reduce (fn [[parent & children] [child & grandchildren]] + [(+ parent child) + (splice children) + (if (empty? grandchildren) + [] + [child (splice grandchildren)])]) + [0] + (map du (values fs))))) + +(var path nil) +(let [fs (table)] + (each [cmd rest] + (peg/match grammar (:read stdin :all)) + (cond (= cmd :ls) (each {:name name :stat stat} + rest + (set ((array/peek path) + name) + (if (= stat :dir) + (table) + (scan-number stat)))) + (= rest :root) (set path (array fs)) + (= rest :parent) (array/pop path) + (let [last (array/peek path)] + (unless (last rest) + (set (last rest) + (table))) + (array/push path (last rest))))) + (let [usages (flatten (du fs))] + (print (min (splice (filter (fn [n] + (>= (+ n 40_000_000) + (first usages))) + usages)))))) diff --git a/aoc/2022/08/part-one.f90 b/aoc/2022/08/part-one.f90 new file mode 100644 index 0000000..a339f48 --- /dev/null +++ b/aoc/2022/08/part-one.f90 @@ -0,0 +1,47 @@ +PROGRAM one + implicit none + integer, parameter :: WIDTH = 99, HEIGHT = 99 + character(WIDTH), dimension(HEIGHT) :: lines + integer :: i, j + integer, dimension(HEIGHT, WIDTH) :: grid, tmp + logical, dimension(HEIGHT, WIDTH) :: visible + + read (*, *) lines + do i = 1, HEIGHT + do j = 1, WIDTH + read (lines(i)(j:j), '(I1)') grid(i, j) + end do + end do + + visible(:, :) = .false. + visible(1, :) = .true. + visible(HEIGHT, :) = .true. + visible(:, 1) = .true. + visible(:, WIDTH) = .true. + + tmp = grid + do i = 2, HEIGHT-1 + visible(i, :) = visible(i, :) .or. tmp(i-1, :) < grid(i, :) + tmp(i, :) = max(tmp(i-1, :), grid(i, :)) + end do + + tmp = grid + do i = HEIGHT-1, 2, -1 + visible(i, :) = visible(i, :) .or. tmp(i+1, :) < grid(i, :) + tmp(i, :) = max(tmp(i+1, :), grid(i, :)) + end do + + tmp = grid + do i = 2, WIDTH-1 + visible(:, i) = visible(:, i) .or. tmp(:, i-1) < grid(:, i) + tmp(:, i) = max(tmp(:, i-1), grid(:, i)) + end do + + tmp = grid + do i = WIDTH-1, 2, -1 + visible(:, i) = visible(:, i) .or. tmp(:, i+1) < grid(:, i) + tmp(:, i) = max(tmp(:, i+1), grid(:, i)) + end do + + print *, sum(merge(1, 0, visible)) +end program one diff --git a/aoc/2022/08/part-two.f90 b/aoc/2022/08/part-two.f90 new file mode 100644 index 0000000..a313638 --- /dev/null +++ b/aoc/2022/08/part-two.f90 @@ -0,0 +1,53 @@ +PROGRAM two + implicit none + integer, parameter :: WIDTH = 99, HEIGHT = 99 + integer, parameter :: ID(0:9) = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] + integer, parameter :: COL(HEIGHT, 0:9) = spread(ID, 1, HEIGHT) + integer, parameter :: ROW(WIDTH, 0:9) = spread(ID, 1, WIDTH) + character(WIDTH) :: lines(HEIGHT) + integer :: i, j + integer, dimension(HEIGHT, WIDTH) :: grid, score + integer, dimension(HEIGHT, WIDTH, 0:9) :: tmp + + read (*, *) lines + do i = 1, HEIGHT + do j = 1, WIDTH + read (lines(i)(j:j), '(I1)') grid(i, j) + end do + end do + + score = 0 + tmp = 0 + do i = 2, HEIGHT-1 + tmp(i, :, :) = merge(tmp(i-1, :, :)+1, 1, spread(grid(i-1, :), 2, 10) < ROW) + do j = 2, WIDTH-1 + score(i, j) = tmp(i, j, grid(i, j)) + end do + end do + + tmp = 0 + do i = 2, WIDTH-1 + tmp(:, i, :) = merge(tmp(:, i-1, :)+1, 1, spread(grid(:, i-1), 2, 10) < COL) + do j = 2, WIDTH-1 + score(j, i) = score(j, i) * tmp(j, i, grid(j, i)) + end do + end do + + tmp = 0 + do i = HEIGHT-1, 2, -1 + tmp(i, :, :) = merge(tmp(i+1, :, :)+1, 1, spread(grid(i+1, :), 2, 10) < ROW) + do j = 2, WIDTH-1 + score(i, j) = score(i, j) * tmp(i, j, grid(i, j)) + end do + end do + + tmp = 0 + do i = WIDTH-1, 2, -1 + tmp(:, i, :) = merge(tmp(:, i+1, :)+1, 1, spread(grid(:, i+1), 2, 10) < COL) + do j = 2, WIDTH-1 + score(j, i) = score(j, i) * tmp(j, i, grid(j, i)) + end do + end do + + print *, maxval(score) +end program two diff --git a/aoc/2022/09/part-one.tcl b/aoc/2022/09/part-one.tcl new file mode 100755 index 0000000..3e7716a --- /dev/null +++ b/aoc/2022/09/part-one.tcl @@ -0,0 +1,25 @@ +#!/usr/bin/env tclsh +proc vec x {list [expr {abs($x)}] [expr {($x>0)-($x<0)}]} +set tx [set hx 0] +set ty [set hy 0] +while {1} { + set line [gets stdin] + if {[eof stdin] || $line == ""} then break + lassign [split $line] d n + for {set i 0} {$i < $n} {incr i} { + switch $d { + R {incr hx 1} + U {incr hy 1} + L {incr hx -1} + D {incr hy -1} + } + lassign [vec [expr {$hx-$tx}]] mx dx + lassign [vec [expr {$hy-$ty}]] my dy + if {$mx == 2 || $my == 2} { + incr tx $dx + incr ty $dy + } + set v($tx,$ty) 1 + } +} +puts [array size v] diff --git a/aoc/2022/09/part-two.tcl b/aoc/2022/09/part-two.tcl new file mode 100755 index 0000000..e3d539f --- /dev/null +++ b/aoc/2022/09/part-two.tcl @@ -0,0 +1,30 @@ +#!/usr/bin/env tclsh +proc vec x {list [expr {abs($x)}] [expr {($x>0)-($x<0)}]} +for {set i 0} {$i < 10} {incr i} { + set kx($i) 0 + set ky($i) 0 +} +while {1} { + set line [gets stdin] + if {[eof stdin] || $line == ""} then break + lassign [split $line] d n + for {set i 0} {$i < $n} {incr i} { + switch $d { + R {incr kx(0) 1} + U {incr ky(0) 1} + L {incr kx(0) -1} + D {incr ky(0) -1} + } + for {set j 1} {$j < 10} {incr j} { + set p [expr {$j-1}] + lassign [vec [expr {$kx($p)-$kx($j)}]] mx dx + lassign [vec [expr {$ky($p)-$ky($j)}]] my dy + if {$mx == 2 || $my == 2} { + incr kx($j) $dx + incr ky($j) $dy + } + } + set v($kx(9),$ky(9)) 1 + } +} +puts [array size v] diff --git a/aoc/2022/10/part-one.awk b/aoc/2022/10/part-one.awk new file mode 100755 index 0000000..756464e --- /dev/null +++ b/aoc/2022/10/part-one.awk @@ -0,0 +1,8 @@ +#!/usr/bin/env -S awk -f +BEGIN { cycle = x = 1 } +{ cycle++ } +cycle % 40 == 20 { strength += cycle * x } +{ x += $2 } +/^addx/ { cycle++ } +/^addx/ && cycle % 40 == 20 { strength += cycle * x } +END { print strength } diff --git a/aoc/2022/10/part-two.awk b/aoc/2022/10/part-two.awk new file mode 100755 index 0000000..9126306 --- /dev/null +++ b/aoc/2022/10/part-two.awk @@ -0,0 +1,10 @@ +#!/usr/bin/env -S awk -f +function cycle (c, x) { + printf x - 2 < c && c < x + 2 ? "#" : "." + printf c == 39 ? "\n" : "" + return (c + 1) % 40 +} +BEGIN { x = 1 } +{ c = cycle(c, x) } +/^addx/ { c = cycle(c, x) } +{ x += $2 } diff --git a/aoc/2024/01/part-one.py b/aoc/2024/01/part-one.py new file mode 100644 index 0000000..2a2421e --- /dev/null +++ b/aoc/2024/01/part-one.py @@ -0,0 +1,4 @@ +from sys import stdin + +left, right = zip(*((int(a), int(b)) for a, b in map(str.split, stdin))) +print(sum(map(abs, map(int.__sub__, sorted(left), sorted(right))))) diff --git a/aoc/2024/01/part-two.py b/aoc/2024/01/part-two.py new file mode 100644 index 0000000..5000c9c --- /dev/null +++ b/aoc/2024/01/part-two.py @@ -0,0 +1,6 @@ +from sys import stdin +from collections import Counter + +left, right = zip(*((int(a), int(b)) for a, b in map(str.split, stdin))) +counter = Counter(right) +print(sum(counter[n]*n for n in left)) diff --git a/aoc/2024/02/part-one.py b/aoc/2024/02/part-one.py new file mode 100644 index 0000000..e0d74db --- /dev/null +++ b/aoc/2024/02/part-one.py @@ -0,0 +1,6 @@ +from sys import stdin + +print(sum(all(0 < d < 4 for d in diffs) or all(-4 < d < 0 for d in diffs) + for diffs in (tuple(map(int.__sub__, levels, levels[1:])) + for levels in (tuple(map(int, line)) + for line in map(str.split, stdin))))) diff --git a/aoc/2024/02/part-two.py b/aoc/2024/02/part-two.py new file mode 100644 index 0000000..ad5f5a6 --- /dev/null +++ b/aoc/2024/02/part-two.py @@ -0,0 +1,21 @@ +from collections import Counter +from itertools import chain, count +from sys import stdin + + +def safe(levels, dampened=False): + head = levels[0 if 0 < levels[1] - levels[0] < 4 else 1] - 1, + tail = levels[-1 if 0 < levels[-1] - levels[-2] < 4 else -2] + 1, + dampenable = tuple((not dampened and 0 < a - c < 4 + and safe(levels[:i]+levels[i+1:], True)) + for i, a, b, c in zip(count(), + chain(levels[1:], tail), + levels, + chain(head, levels)) + if not (0 < a - b < 4 and 0 < b - c < 4)) + return not dampenable or any(dampenable) + + +print(sum(safe(levels) or safe(tuple(map(int.__neg__, levels))) + for levels in (tuple(map(int, line)) + for line in map(str.split, stdin)))) diff --git a/aoc/2024/03/part-one.c b/aoc/2024/03/part-one.c new file mode 100644 index 0000000..0438304 --- /dev/null +++ b/aoc/2024/03/part-one.c @@ -0,0 +1,11 @@ +#include <stdio.h> + +int main() +{ + size_t x, y, s = 0; + while (scanf("%*[^m]") != EOF) + if (scanf("mul(%3zu,%3zu", &x, &y) == 2 && getchar() == ')') + s += x * y; + printf("%zu\n", s); + return 0; +} diff --git a/aoc/2024/03/part-two.c b/aoc/2024/03/part-two.c new file mode 100644 index 0000000..4ae337f --- /dev/null +++ b/aoc/2024/03/part-two.c @@ -0,0 +1,27 @@ +#include <stdbool.h> +#include <stdio.h> + +int main() +{ + bool d = true; + size_t x, y, s = 0; + while (scanf("%*[^dm]") != EOF) { + if (getchar() == 'd') { + int c; +#define unless(i) if ((c = getchar()) != i && ungetc(c, stdin) == c) + unless ('o') continue; + unless ('(') { + if (scanf("n't()") != EOF) + d = false; + continue; + } + unless (')') continue; +#undef unless + d = true; + } + if (scanf("ul(%3zu,%3zu", &x, &y) == 2 && getchar() == ')' && d) + s += x * y; + } + printf("%zu\n", s); + return 0; +} diff --git a/aoc/2024/04/part-one.py b/aoc/2024/04/part-one.py new file mode 100644 index 0000000..ba25336 --- /dev/null +++ b/aoc/2024/04/part-one.py @@ -0,0 +1,23 @@ +from sys import stdin + + +def index(m, n, i, j, c): + return (m[i][j], m[n-j-1][i], m[n-i-1][n-j-1], m[j][n-i-1])[c] + + +def rot(m, c): + n = len(m) + if n != len(m[0]): raise ValueError + for i in range(n): + yield ''.join(index(m, n, i-j, j, c) for j in range(i+1)) + for i in range(1, n): + yield ''.join(index(m, n, n-j-1, i+j, c) for j in range(n-i)) + + +reverse_all = lambda strings: (s[::-1] for s in strings) +count = lambda strings: sum(s.count('XMAS') for s in strings) +lines = tuple(map(str.strip, stdin.readlines())) +columns = tuple(''.join(column) for column in zip(*lines)) +print((count(lines) + count(reverse_all(lines)) + + count(columns) + count(reverse_all(columns)) + + sum(count(rot(lines, c)) for c in range(4)))) diff --git a/aoc/2024/04/part-two.py b/aoc/2024/04/part-two.py new file mode 100644 index 0000000..a3e7c4a --- /dev/null +++ b/aoc/2024/04/part-two.py @@ -0,0 +1,10 @@ +from itertools import islice +from sys import stdin + +mat = tuple(map(str.strip, stdin.readlines())) +m = len(mat) +n = len(mat[0]) +print(sum(c == 'A' and ({mat[i-1][j-1], mat[i+1][j+1]} + == {mat[i-1][j+1], mat[i+1][j-1]} == {'M', 'S'}) + for i, line in islice(enumerate(mat), 1, m-1) + for j, c in islice(enumerate(line), 1, n-1))) diff --git a/aoc/2024/05/part-one.c b/aoc/2024/05/part-one.c new file mode 100644 index 0000000..4d2b560 --- /dev/null +++ b/aoc/2024/05/part-one.c @@ -0,0 +1,27 @@ +#include <stdbool.h> +#include <stdio.h> +#include <stdlib.h> + +int main() +{ + bool after[100][100] = {false}; + unsigned char x, y; + while (scanf("%hhu|%hhu\n", &x, &y) == 2) + after[y][x] = true; + + unsigned char line[90]; + unsigned sum = y = 0; + do { + bool right = true; + do { + line[y] = x; + for (unsigned char i = 0; right && i < y; ++i) + if (after[line[i]][line[y]]) + right = false; + } while (scanf(",%hhu", &x) == 1 && ++y); + if (right) + sum += line[y + 1 >> 1]; + } while (y = 0, scanf("%hhu", &x) == 1); + printf("%u\n", sum); + return 0; +} diff --git a/aoc/2024/05/part-two.c b/aoc/2024/05/part-two.c new file mode 100644 index 0000000..443e8b0 --- /dev/null +++ b/aoc/2024/05/part-two.c @@ -0,0 +1,35 @@ +#include <stdbool.h> +#include <stdio.h> +#include <stdlib.h> + +static bool after[100][100]; + +int compare(const void *x, const void *y) +{ + return after[*(const unsigned char *) x][*(const unsigned char *) y]; +} + +int main() +{ + unsigned char x, y; + while (scanf("%hhu|%hhu\n", &x, &y) == 2) + after[y][x] = true; + + unsigned char line[90]; + unsigned sum = y = 0; + do { + bool right = true; + do { + line[y] = x; + for (unsigned char i = 0; right && i < y; ++i) + if (after[line[i]][line[y]]) + right = false; + } while (scanf(",%hhu", &x) == 1 && ++y); + if (right) + continue; + qsort(line, ++y, 1, compare); + sum += line[y >> 1]; + } while (y = 0, scanf("%hhu", &x) == 1); + printf("%u\n", sum); + return 0; +} |