From 85bd7ec1bd9cdc7ec53692fce5cae3118b7357a0 Mon Sep 17 00:00:00 2001 From: Nguyễn Gia Phong Date: Sun, 5 Dec 2021 15:18:59 +0700 Subject: [aoc] Add first five/fifth --- README.md | 14 ++++++++------ aoc/2021/01/part-one.py | 6 ++++++ aoc/2021/01/part-two.py | 8 ++++++++ aoc/2021/02/part-one.zig | 25 ++++++++++++++++++++++++ aoc/2021/02/part-two.zig | 27 ++++++++++++++++++++++++++ aoc/2021/03/part-one.zig | 19 +++++++++++++++++++ aoc/2021/03/part-two.raku | 8 ++++++++ aoc/2021/04/part-one.zig | 48 +++++++++++++++++++++++++++++++++++++++++++++++ aoc/2021/04/part-two.zig | 48 +++++++++++++++++++++++++++++++++++++++++++++++ aoc/2021/05/part-one.zig | 46 +++++++++++++++++++++++++++++++++++++++++++++ aoc/2021/05/part-two.zig | 48 +++++++++++++++++++++++++++++++++++++++++++++++ 11 files changed, 291 insertions(+), 6 deletions(-) create mode 100644 aoc/2021/01/part-one.py create mode 100644 aoc/2021/01/part-two.py create mode 100644 aoc/2021/02/part-one.zig create mode 100644 aoc/2021/02/part-two.zig create mode 100644 aoc/2021/03/part-one.zig create mode 100644 aoc/2021/03/part-two.raku create mode 100644 aoc/2021/04/part-one.zig create mode 100644 aoc/2021/04/part-two.zig create mode 100644 aoc/2021/05/part-one.zig create mode 100644 aoc/2021/05/part-two.zig 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 }); +} -- cgit 1.4.1