[aoc] Add first five/fifth

11 files changed, 291 insertions, 6 deletions

diff --git a/README.md b/README.md
index 4ba11ad..5fd359d 100644
--- a/README.md
+++ b/README.md
@@ -7,6 +7,7 @@ this README as well as commit messages are duolingo (anglais et vietnamien).
 |    Thư mục   |                      Nguồn đề bài                      |
 | ------------ | ------------------------------------------------------ |
 | `2ndary`     | Secondary school competitions                          |
+| `aoc`        | [Advent of Code][5]                                    |
 | `coci`       | [Giải Tin học Croatia mở rộng][0]                      |
 | `codechef`   | [Codechef][2]                                          |
 | `codeforces` | [Codeforces][3]                                        |
@@ -19,11 +20,12 @@ this README as well as commit messages are duolingo (anglais et vietnamien).
 | `toys`       | Programs that don't deserve their own repo             |
 | `usth`       | L'Université des Sciences et des Technologies de Hanoï |
 
-[0]: http://www.hsin.hr/coci/
-[1]: http://laptrinh.ntu.edu.vn/
-[2]: http://codechef.com/
-[3]: http://codeforces.com/
-[4]: https://www.reddit.com/r/dailyprogrammer
+[0]: https://hsin.hr/coci
+[1]: http://laptrinh.ntu.edu.vn
+[2]: https://codechef.com
+[3]: https://codeforces.com
+[4]: https://reddit.com/r/dailyprogrammer
+[5]: https://adventofcode.com
 
 Ở mỗi thư mục con sẽ có tệp `README.md` ghi lại đề bài. Riêng `coci`, `ntu` và
 `codeforces` sẽ chỉ có danh sách đường dẫn tới các đề bài. Đề bài sẽ được cập
@@ -44,7 +46,7 @@ Phiên bản các trình dịch sử dụng test:
 | Raku        | Rakudo 2018.12+    |
 | Rust        | Rust 2018+         |
 | Scheme      | GNU Guile 2.0.11+  |
-| Zig         | Zig 0.7.1+         |
+| Zig         | Zig 0.8.1+         |
 
 SICP không chỉ dùng Guile để chạy Scheme mà còn sử dụng Racket (`#lang sicp`)
 trong các chương 1, 2 và 3.
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..6088925
--- /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 });
+}