commit 9282e95e8844afe856ba76ceb6d2c3010df8bb1a
parent 2b5d4232879dc74491dabf54a0ddc958d66ebcec
Author: Louis Burda <quent.burda@gmail.com>
Date: Sat, 8 Apr 2023 12:40:30 -0400
Restructure repo and update solutions to zig 0.10.1
Diffstat:
169 files changed, 3532 insertions(+), 3452 deletions(-)
diff --git a/.gitignore b/.gitignore
@@ -1,3 +0,0 @@
-main
-cache
-zig-cache
diff --git a/.gitmodules b/.gitmodules
@@ -1,3 +0,0 @@
-[submodule "helper"]
- path = helper
- url = git@github.com:Sinitax/aoc-helper.git
diff --git a/README.md b/README.md
@@ -0,0 +1,5 @@
+## Advent Of Code 2020
+
+Solutions to the annual [coding advent calendar](https://adventofcode.com) written in [Zig](https://ziglang.org/).
+
+The version of zig used to compile the code is: `0.10.1`
diff --git a/data/helper/config b/data/helper/config
@@ -1,13 +0,0 @@
-#!/bin/bash
-
-# year you are solving problems for
-export AOCYEAR=2020
-
-# directory you want day directories to be prepared in (format: src/dayN/..)
-export SRCDIR="src"
-
-# specify what files to copy to your day directory on prepare
-export TEMPLATE_DIR="data/helper/template"
-export TEMPLATE_FILES="
-main.zig:main.zig
-"
diff --git a/data/helper/init.sh b/data/helper/init.sh
@@ -1,12 +0,0 @@
-#!/bin/bash
-
-REPOROOT=$(git rev-parse --show-toplevel)
-
-set -e
-
-ln -sf "$REPOROOT/data/helper/config" "$REPOROOT/helper/data/config"
-for f in "$REPOROOT/data/helper/scripts"/*; do
- ln -sf "$f" "$REPOROOT/helper/scripts"
-done
-
-echo "done"
diff --git a/data/helper/scripts/build b/data/helper/scripts/build
@@ -1,7 +0,0 @@
-#!/bin/bash
-
-[ ! -e "$SOLUTIONS_ROOT/cache" ] && mkdir "$SOLUTIONS_ROOT/cache"
-zig build-exe --cache-dir "$SOLUTIONS_ROOT/cache" \
- --pkg-begin "console8" "$SOLUTIONS_ROOT/lib/console8.zig" --pkg-end \
- --pkg-begin "aoc" "$SOLUTIONS_ROOT/lib/aoc.zig" --pkg-end \
- main.zig
diff --git a/data/helper/scripts/run b/data/helper/scripts/run
@@ -1,4 +0,0 @@
-#!/bin/bash
-
-[ ! -e "main" ] && $HELPER_ROOT/scripts/build
-$PWD/main $@
diff --git a/data/helper/scripts/test b/data/helper/scripts/test
@@ -1,7 +0,0 @@
-#!/bin/bash
-
-[ ! -e "$SOLUTIONS_ROOT/cache" ] && mkdir "$SOLUTIONS_ROOT/cache"
-zig test --cache-dir "$SOLUTIONS_ROOT/cache" \
- --pkg-begin "console8" "$SOLUTIONS_ROOT/lib/console8.zig" --pkg-end \
- --pkg-begin "aoc" "$SOLUTIONS_ROOT/lib/aoc.zig" --pkg-end \
- main.zig
diff --git a/data/helper/template/main.zig b/data/helper/template/main.zig
@@ -1,16 +0,0 @@
-const std = @import("std");
-const aoc = @import("aoc");
-
-fn part1(allocator: *std.mem.Allocator, input: []u8, args: [][]u8) !void {
- var answer: u32 = 0;
-
- std.debug.print("{}\n", .{answer});
-}
-
-fn part2(allocator: *std.mem.Allocator, input: []u8, args: [][]u8) !void {
- var answer: u32 = 0;
-
- std.debug.print("{}\n", .{answer});
-}
-
-pub const main = aoc.gen_main(part1, part2);
diff --git a/docs/README.md b/docs/README.md
@@ -1,5 +0,0 @@
-## Advent Of Code 2020
-
-Solutions to the annual [coding advent calendar](https://adventofcode.com) written in [Zig](https://ziglang.org/).
-
-The version of zig used to compile to code is: `0.7.0+d4c167f3c`
diff --git a/helper b/helper
@@ -1 +0,0 @@
-Subproject commit 6417aa3043784125bd6630152d34ce48617ea852
diff --git a/lib/aoc.zig b/lib/aoc.zig
@@ -1,122 +0,0 @@
-const std = @import("std");
-pub const input = @import("input.zig");
-
-pub const Error = error{InvalidInput};
-
-pub var debug = false;
-pub var debuglvl: u32 = 0;
-
-const part_type = fn (alloc: *std.mem.Allocator, input: []u8, args: [][]u8) anyerror!void;
-pub fn gen_main(comptime part1: part_type, comptime part2: part_type) fn () anyerror!void {
- const impl = struct {
- fn main() !void {
- // create a default allocator
- var gpa = std.heap.GeneralPurposeAllocator(.{}){};
- defer _ = gpa.deinit();
- var heapalloc = &gpa.allocator;
-
- // parse args
- const args = try std.process.argsAlloc(heapalloc);
- defer heapalloc.free(args);
- if (args.len < 2) return;
- const part = try std.fmt.parseInt(u8, args[1], 10);
-
- var filename: []const u8 = std.mem.spanZ("input");
- for (std.os.environ) |v| {
- const kv = std.mem.spanZ(v);
- if (std.mem.indexOfScalar(u8, kv, '=')) |sep| {
- if (sep == kv.len - 1) continue;
- if (std.mem.eql(u8, kv[0..sep], "AOCINPUT")) {
- filename = kv[sep + 1 ..];
- std.debug.print("Using input file: {}\n", .{filename});
- break;
- } else if (std.mem.eql(u8, kv[0..sep], "AOCDEBUG")) {
- debug = true;
- debuglvl = try std.fmt.parseInt(u32, kv[sep + 1 ..], 10);
- }
- }
- }
-
- // read all input into mem (files are always small so no problem)
- const file = try std.fs.cwd().openFile(filename, .{});
- const text = try file.reader().readAllAlloc(heapalloc, std.math.maxInt(u32));
- defer heapalloc.free(text);
-
- // exec part
- try switch (part) {
- 1 => part1(heapalloc, text, args[2..]),
- 2 => part2(heapalloc, text, args[2..]),
- else => std.debug.print("Invalid part number!\n", .{}),
- };
- }
- };
- return impl.main;
-}
-
-pub const Pos = struct {
- x: i64,
- y: i64,
- const Self = @This();
-
- pub fn add(self: Self, other: Self) Self {
- return Self{ .x = self.x + other.x, .y = self.y + other.y };
- }
-
- pub fn mult(self: Self, val: i64) Self {
- return Self{ .x = self.x * val, .y = self.y * val };
- }
-};
-
-pub const Dir = struct {
- pub const East = Pos{ .x = 1, .y = 0 };
- pub const West = Pos{ .x = -1, .y = 0 };
- pub const South = Pos{ .x = 0, .y = -1 };
- pub const North = Pos{ .x = 0, .y = 1 };
-
- pub const Name = enum {
- NORTH = 0, EAST = 1, SOUTH = 2, WEST = 3
- };
- pub const dirs = [_]Pos{ North, East, South, West };
-
- pub fn get(name: Name) Pos {
- return dirs[@enumToInt(name)];
- }
-
- pub fn nextCW(dir: usize, offset: usize) usize {
- return (dir + @intCast(u32, offset)) % @intCast(u32, dirs.len);
- }
-
- pub fn nextCCW(dir: usize, offset: usize) usize {
- const constrained = offset % dirs.len;
- if (dir >= constrained) {
- return dir - constrained;
- } else {
- return dirs.len - (constrained - dir);
- }
- }
-
- const cos90vs = [_]i32{ 1, 0, -1, 0 };
- const sin90vs = [_]i32{ 0, 1, 0, -1 };
-
- pub fn rotCW(pos: Pos, offset: usize) Pos {
- const constrained = (4 - offset % 4) % 4;
- return Pos{
- .x = cos90vs[constrained] * pos.x - sin90vs[constrained] * pos.y,
- .y = sin90vs[constrained] * pos.x + cos90vs[constrained] * pos.y,
- };
- }
-
- pub fn rotCCW(pos: Pos, offset: usize) Pos {
- const constrained = offset % 4;
- std.debug.print("{}\n", .{constrained});
- return Pos{
- .x = cos90vs[constrained] * pos.x - sin90vs[constrained] * pos.y,
- .y = sin90vs[constrained] * pos.x + cos90vs[constrained] * pos.y,
- };
- }
-};
-
-pub fn assertV(v: anytype) !@TypeOf(v.?) {
- if (v == null) return Error.InvalidInput;
- return v.?;
-}
diff --git a/lib/console8.zig b/lib/console8.zig
@@ -1,91 +0,0 @@
-const std = @import("std");
-
-pub const OpError = error{ InstructionPointerOOB, InvalidFormat, InstructionUnknown };
-pub const OpFuncSig = fn (ctx: *Console, arg: i64) OpError!void;
-pub const Instruction = struct {
- opcode: []const u8, opfunc: OpFuncSig, argval: i64
-};
-
-pub const Console = struct {
- accumulator: i64 = 0,
- instructptr: u64 = 0,
-
- jumpAddr: i65 = 0,
-
- code: []const u8,
- instlist: [][]const u8,
- allocator: *std.mem.Allocator,
- const Self = @This();
-
- pub fn init(code: []const u8, allocator: *std.mem.Allocator) !Self {
- var instvec = std.ArrayList([]const u8).init(allocator);
- errdefer instvec.deinit();
-
- var instit = std.mem.tokenize(code, "\n");
- while (instit.next()) |inst| {
- try instvec.append(inst);
- }
- return Console{
- .code = code,
- .instlist = instvec.toOwnedSlice(),
- .allocator = allocator,
- };
- }
-
- pub fn deinit(self: *Self) void {
- self.allocator.free(self.instlist);
- }
-
- pub fn reset(self: *Self) void {
- self.accumulator = 0;
- self.instructptr = 0;
- }
-
- const instructionMap = std.ComptimeStringMap(OpFuncSig, .{
- .{ "jmp", jumpInstruction },
- .{ "acc", accInstruction },
- .{ "nop", nopInstruction },
- });
-
- pub fn jumpInstruction(self: *Self, arg: i64) OpError!void {
- self.jumpAddr = @intCast(i65, self.instructptr) + @intCast(i65, arg);
- if (self.jumpAddr < 0 or self.jumpAddr >= self.instlist.len)
- return error.InstructionPointerOOB;
- self.instructptr = @intCast(u64, self.jumpAddr);
- }
-
- pub fn accInstruction(self: *Self, arg: i64) OpError!void {
- self.accumulator += arg;
- self.instructptr += 1;
- }
-
- pub fn nopInstruction(self: *Self, arg: i64) OpError!void {
- self.instructptr += 1;
- }
-
- pub fn parseNext(self: *Self) !?Instruction {
- if (self.instructptr >= self.instlist.len)
- return null;
-
- const inststr = self.instlist[self.instructptr];
- const sep = std.mem.indexOfScalar(u8, inststr, ' ');
- if (sep == null) return OpError.InvalidFormat;
-
- const opcode = inststr[0..sep.?];
- if (instructionMap.get(opcode)) |opfunc| {
- const arg = inststr[sep.? + 1 ..];
- const val = std.fmt.parseInt(i64, arg, 10) catch |err| {
- std.debug.print("Failed to parse arg value: {}\n", .{arg});
- return OpError.InvalidFormat;
- };
- return Instruction{ .opcode = opcode, .opfunc = opfunc, .argval = val };
- } else {
- std.debug.print("Unknown instruction: {}\n", .{inststr});
- return OpError.InstructionUnknown;
- }
- }
-
- pub fn exec(self: *Self, inst: *Instruction) !void {
- try inst.opfunc(self, inst.argval);
- }
-};
diff --git a/lib/input.zig b/lib/input.zig
@@ -1 +0,0 @@
-const std = @import("std");
diff --git a/src/.gitignore b/src/.gitignore
@@ -0,0 +1,3 @@
+main
+main.o
+.cache
diff --git a/src/day1/input b/src/01/input
diff --git a/src/01/main.zig b/src/01/main.zig
@@ -0,0 +1,72 @@
+const std = @import("std");
+const aoc = @import("aoc");
+
+const Parts = struct { a: u32, b: u32 };
+
+fn findparts(intlist: *const std.ArrayList(u32), sum: u32) ?Parts {
+ var start: usize = 0;
+ const items = intlist.items;
+ var end: usize = items.len - 1;
+ while (start != end) {
+ const csum = items[start] + items[end];
+ if (csum == sum) {
+ return Parts{ .a = items[start], .b = items[end] };
+ } else if (csum > sum) {
+ end -= 1;
+ } else {
+ start += 1;
+ }
+ }
+ return null;
+}
+
+fn parse(allocator: std.mem.Allocator, input: []u8) !std.ArrayList(u32) {
+ var intlist = std.ArrayList(u32).init(allocator);
+ errdefer intlist.deinit();
+
+ var it = std.mem.tokenize(u8, input, "\n");
+ while (it.next()) |line| {
+ try intlist.append(try std.fmt.parseInt(u32, line, 10));
+ }
+
+ return intlist;
+}
+
+fn part1(allocator: std.mem.Allocator, input: []u8, args: [][]u8) !?[]u8 {
+ _ = args;
+
+ const intlist = try parse(allocator, input);
+ defer intlist.deinit();
+
+ std.sort.sort(u32, intlist.items, {}, comptime std.sort.asc(u32));
+
+ if (findparts(&intlist, 2020)) |parts| {
+ return try std.fmt.allocPrint(allocator, "{d}", .{parts.a * parts.b});
+ }
+
+ return null;
+}
+
+fn part2(allocator: std.mem.Allocator, input: []u8, args: [][]u8) !?[]u8 {
+ _ = args;
+
+ const intlist = try parse(allocator, input);
+ defer intlist.deinit();
+
+ std.sort.sort(u32, intlist.items, {}, comptime std.sort.asc(u32));
+
+ const target: u16 = 2020;
+ var third: u32 = 0;
+ while (third < intlist.items.len) : (third += 1) {
+ const tmp = intlist.items[third];
+ intlist.items[third] = target + 1;
+ if (findparts(&intlist, target - tmp)) |parts| {
+ return try std.fmt.allocPrint(allocator, "{d}", .{parts.a * parts.b * tmp});
+ }
+ intlist.items[third] = tmp;
+ }
+
+ return null;
+}
+
+pub const main = aoc.main(part1, part2, .{ "658899", "155806250" });
diff --git a/src/day1/part1 b/src/01/part1
diff --git a/src/day1/part2 b/src/01/part2
diff --git a/src/day2/input b/src/02/input
diff --git a/src/02/main.zig b/src/02/main.zig
@@ -0,0 +1,61 @@
+const std = @import("std");
+const aoc = @import("aoc");
+
+const Entry = struct { a: u16, b: u16, char: u8, pass: []u8 };
+
+fn freeEntries(allocator: std.mem.Allocator, entries: *const std.ArrayList(Entry)) void {
+ for (entries.items) |item|
+ allocator.free(item.pass);
+ entries.deinit();
+}
+
+fn parse(allocator: std.mem.Allocator, input: []u8) !std.ArrayList(Entry) {
+ var entries = std.ArrayList(Entry).init(allocator);
+ errdefer freeEntries(allocator, &entries);
+
+ var lineit = std.mem.tokenize(u8, input, "\n");
+ while (lineit.next()) |line| {
+ var entry: Entry = undefined;
+ var it = std.mem.tokenize(u8, line, " -");
+ entry.a = try std.fmt.parseInt(u16, it.next().?, 10);
+ entry.b = try std.fmt.parseInt(u16, it.next().?, 10);
+ entry.char = it.next().?[0];
+ entry.pass = try allocator.dupe(u8, it.next().?);
+ try entries.append(entry);
+ }
+
+ return entries;
+}
+
+fn part1(allocator: std.mem.Allocator, input: []u8, args: [][]u8) !?[]u8 {
+ _ = args;
+
+ const entries = try parse(allocator, input);
+ defer freeEntries(allocator, &entries);
+
+ var valid: u32 = 0;
+ for (entries.items) |entry| {
+ var count: u16 = 0;
+ for (entry.pass) |c| count += @boolToInt(c == entry.char);
+ valid += @boolToInt(count >= entry.a and count <= entry.b);
+ }
+
+ return try std.fmt.allocPrint(allocator, "{d}", .{valid});
+}
+
+fn part2(allocator: std.mem.Allocator, input: []u8, args: [][]u8) !?[]u8 {
+ _ = args;
+
+ const entries = try parse(allocator, input);
+ defer freeEntries(allocator, &entries);
+
+ var valid: u32 = 0;
+ for (entries.items) |entry| {
+ valid += @boolToInt((entry.pass[entry.a - 1] == entry.char) !=
+ (entry.pass[entry.b - 1] == entry.char));
+ }
+
+ return try std.fmt.allocPrint(allocator, "{d}", .{valid});
+}
+
+pub const main = aoc.main(part1, part2, .{ "603", "404" });
diff --git a/src/day2/part1 b/src/02/part1
diff --git a/src/day2/part2 b/src/02/part2
diff --git a/src/day3/input b/src/03/input
diff --git a/src/03/main.zig b/src/03/main.zig
@@ -0,0 +1,77 @@
+const std = @import("std");
+const aoc = @import("aoc");
+
+const Entry = []u1;
+const Vector = struct { x: u16, y: u16 };
+
+fn freeEntries(allocator: std.mem.Allocator, entries: *const std.ArrayList(Entry)) void {
+ for (entries.items) |entry| {
+ allocator.free(entry);
+ }
+ entries.deinit();
+}
+
+fn parse(allocator: std.mem.Allocator, input: []u8) !std.ArrayList(Entry) {
+ var entries = std.ArrayList(Entry).init(allocator);
+ errdefer freeEntries(allocator, &entries);
+
+ var lineit = std.mem.tokenize(u8, input, "\n");
+ while (lineit.next()) |line| {
+ var linemap: []u1 = try allocator.alloc(u1, line.len);
+ errdefer allocator.free(linemap);
+
+ for (line) |c, i| {
+ linemap[i] = @boolToInt(c == '#');
+ }
+ try entries.append(linemap);
+ }
+
+ return entries;
+}
+
+fn treesHit(map: std.ArrayList(Entry), slope: Vector) u16 {
+ var count: u16 = 0;
+ var pos = Vector{ .x = 0, .y = 0 };
+ while (pos.y < map.items.len - 1) {
+ pos.x += slope.x;
+ pos.y += slope.y;
+
+ count += map.items[pos.y][pos.x % map.items[0].len];
+ }
+ return count;
+}
+
+fn part1(allocator: std.mem.Allocator, input: []u8, args: [][]u8) !?[]u8 {
+ _ = args;
+
+ const map = try parse(allocator, input);
+ defer freeEntries(allocator, &map);
+
+ const answer = treesHit(map, Vector{ .x = 3, .y = 1 });
+
+ return try std.fmt.allocPrint(allocator, "{d}", .{answer});
+}
+
+fn part2(allocator: std.mem.Allocator, input: []u8, args: [][]u8) !?[]u8 {
+ _ = args;
+
+ const map = try parse(allocator, input);
+ defer freeEntries(allocator, &map);
+
+ const slopes = [_]Vector{
+ Vector{ .x = 1, .y = 1 },
+ Vector{ .x = 3, .y = 1 },
+ Vector{ .x = 5, .y = 1 },
+ Vector{ .x = 7, .y = 1 },
+ Vector{ .x = 1, .y = 2 },
+ };
+
+ var answer: u32 = 1;
+ for (slopes) |slope| {
+ answer *= treesHit(map, slope);
+ }
+
+ return try std.fmt.allocPrint(allocator, "{d}", .{answer});
+}
+
+pub const main = aoc.main(part1, part2, .{ "282", "958815792" });
diff --git a/src/day3/part1 b/src/03/part1
diff --git a/src/day3/part2 b/src/03/part2
diff --git a/src/day4/input b/src/04/input
diff --git a/src/04/main.zig b/src/04/main.zig
@@ -0,0 +1,108 @@
+const std = @import("std");
+const aoc = @import("aoc");
+
+fn intChecker(
+ comptime min: u32,
+ comptime max: u32,
+ comptime len: ?u32,
+ comptime suffix: ?[]const u8,
+) fn ([]const u8) bool {
+ const impl = struct {
+ fn check(input: []const u8) bool {
+ var parsed = input;
+ if (suffix) |suf| {
+ if (!std.mem.eql(u8, suf, input[(input.len - suf.len)..]))
+ return false;
+ parsed = input[0..(input.len - suf.len)];
+ }
+ if (len != null and parsed.len != len.?)
+ return false;
+ const val = std.fmt.parseInt(u32, parsed, 10) catch {
+ return false;
+ };
+ return (val >= min and val <= max);
+ }
+ };
+ return impl.check;
+}
+
+fn combineOr(
+ comptime f1: fn ([]const u8) bool,
+ comptime f2: fn ([]const u8) bool,
+) fn ([]const u8) bool {
+ const impl = struct {
+ fn check(input: []const u8) bool {
+ return f1(input) or f2(input);
+ }
+ };
+ return impl.check;
+}
+
+fn isColorStr(input: []const u8) bool {
+ if (input.len != 7) return false;
+ _ = std.fmt.parseInt(u32, input[1..], 16) catch {
+ return false;
+ };
+ return input[0] == '#';
+}
+
+fn isEyeColor(input: []const u8) bool {
+ const valids = "amb blu brn gry grn hzl oth";
+ return std.mem.indexOf(u8, valids[0..], input) != null;
+}
+
+fn countValids(input: []u8, validate: bool) !u16 {
+ var entryit = std.mem.split(u8, input, "\n\n");
+ const required_keys = [_][]const u8{ "byr", "iyr", "eyr", "hgt", "hcl", "ecl", "pid", "cid" };
+ const validation_funcs = [required_keys.len]?*const fn ([]const u8) bool{
+ intChecker(1920, 2002, 4, null),
+ intChecker(2010, 2020, 4, null),
+ intChecker(2020, 2030, 4, null),
+ combineOr(intChecker(150, 193, 3, "cm"), intChecker(59, 76, 2, "in")),
+ isColorStr,
+ isEyeColor,
+ intChecker(0, 999999999, 9, null),
+ null,
+ };
+ var count: u16 = 0;
+ entryloop: while (entryit.next()) |entry| {
+ const key_mask = [required_keys.len]u8{ 1, 1, 1, 1, 1, 1, 1, 'X' };
+ var present = [required_keys.len]u1{ 0, 0, 0, 0, 0, 0, 0, 0 };
+ var partit = std.mem.tokenize(u8, entry, ": \n");
+ while (partit.next()) |key| {
+ const value = partit.next().?;
+ for (required_keys) |ckey, i| {
+ if (std.mem.eql(u8, key, ckey)) {
+ if (validate and validation_funcs[i] != null) {
+ if (!validation_funcs[i].?(value)) continue :entryloop;
+ }
+ present[i] = 1;
+ }
+ }
+ }
+ for (key_mask) |k, i| {
+ if (k != 'X' and present[i] != k)
+ continue :entryloop;
+ }
+ count += 1;
+ }
+ return count;
+}
+
+fn part1(allocator: std.mem.Allocator, input: []u8, args: [][]u8) !?[]u8 {
+ _ = args;
+
+ const answer = try countValids(input, false);
+
+ return try std.fmt.allocPrint(allocator, "{d}", .{answer});
+}
+
+fn part2(allocator: std.mem.Allocator, input: []u8, args: [][]u8) !?[]u8 {
+ _ = args;
+
+ const answer = try countValids(input, true);
+
+ return try std.fmt.allocPrint(allocator, "{d}", .{answer});
+}
+
+pub const main = aoc.main(part1, part2, .{ "226", "160" });
diff --git a/src/day4/part1 b/src/04/part1
diff --git a/src/day4/part2 b/src/04/part2
diff --git a/src/day5/input b/src/05/input
diff --git a/src/05/main.zig b/src/05/main.zig
@@ -0,0 +1,52 @@
+const std = @import("std");
+const aoc = @import("aoc");
+
+const row_count = 128;
+const col_count = 8;
+
+// Input is coded in a way that we can do an implicit binary search by replacing
+// identifiers for the lower half with "0" and for the upper half with "1"
+// See commit <f1b717029cf3262c1fa2760124af258924d668da> for actual binary search
+
+fn code2Id(input: []const u8) !u32 {
+ var value: u32 = 0;
+ for (input) |c|
+ value = value * 2 + @boolToInt(c == 'B' or c == 'R');
+ return value;
+}
+
+fn part1(allocator: std.mem.Allocator, input: []u8, args: [][]u8) !?[]u8 {
+ _ = args;
+
+ var lineit = std.mem.tokenize(u8, input, "\n");
+ var answer: u32 = 0;
+ while (lineit.next()) |line| {
+ const id = try code2Id(line[0..10]);
+ answer = std.math.max(answer, id);
+ }
+
+ return try std.fmt.allocPrint(allocator, "{d}", .{answer});
+}
+
+fn part2(allocator: std.mem.Allocator, input: []u8, args: [][]u8) !?[]u8 {
+ _ = args;
+
+ var lineit = std.mem.tokenize(u8, input, "\n");
+ var seats = [_]u1{0} ** (row_count * col_count);
+ var min: u32 = std.math.inf_u32;
+ while (lineit.next()) |line| {
+ const id = try code2Id(line);
+ min = std.math.min(min, id);
+ seats[id] = 1;
+ }
+
+ for (seats[min..]) |_, i| {
+ if (seats[min + i] == 0) {
+ return try std.fmt.allocPrint(allocator, "{d}", .{min + i});
+ }
+ }
+
+ return null;
+}
+
+pub const main = aoc.main(part1, part2, .{ "850", "599" });
diff --git a/src/day5/part1 b/src/05/part1
diff --git a/src/day5/part2 b/src/05/part2
diff --git a/src/day6/input b/src/06/input
diff --git a/src/06/main.zig b/src/06/main.zig
@@ -0,0 +1,39 @@
+const std = @import("std");
+const aoc = @import("aoc");
+
+fn part1(allocator: std.mem.Allocator, input: []u8, args: [][]u8) !?[]u8 {
+ _ = args;
+
+ var entryit = std.mem.split(u8, input, "\n\n");
+ var answer: u32 = 0;
+ while (entryit.next()) |group| {
+ var seen = [_]u1{0} ** 256;
+ for (group) |c| {
+ if (c == ' ' or c == '\n') continue;
+ answer += @boolToInt(seen[c] == 0);
+ seen[c] = 1;
+ }
+ }
+
+ return try std.fmt.allocPrint(allocator, "{d}", .{answer});
+}
+
+fn part2(allocator: std.mem.Allocator, input: []u8, args: [][]u8) !?[]u8 {
+ _ = args;
+
+ var entryit = std.mem.split(u8, input, "\n\n");
+ var answer: u32 = 0;
+ while (entryit.next()) |group| {
+ var count = [_]u16{0} ** 256;
+ var members: u16 = 0;
+ var memberit = std.mem.tokenize(u8, group, "\n ");
+ while (memberit.next()) |member| : (members += 1) {
+ for (member) |c| count[c] += 1;
+ }
+ for (count) |v| answer += @boolToInt(v == members);
+ }
+
+ return try std.fmt.allocPrint(allocator, "{d}", .{answer});
+}
+
+pub const main = aoc.main(part1, part2, .{ "6748", "3445" });
diff --git a/src/day6/part1 b/src/06/part1
diff --git a/src/day6/part2 b/src/06/part2
diff --git a/src/day7/input b/src/07/input
diff --git a/src/07/main.zig b/src/07/main.zig
@@ -0,0 +1,108 @@
+const std = @import("std");
+const aoc = @import("aoc");
+
+const BagCount = struct { id: u64, count: u32 };
+
+const BagRule = struct {
+ outer: u64,
+ innerit: std.mem.SplitIterator(u8),
+
+ fn from(line: []const u8) BagRule {
+ var partit = std.mem.split(u8, line, " bags contain ");
+ const outer = std.hash.CityHash64.hash(partit.next().?);
+ var innerit = std.mem.split(u8, partit.next().?, ", ");
+ return BagRule{ .outer = outer, .innerit = innerit };
+ }
+
+ fn nextInner(self: *BagRule) !?BagCount {
+ if (self.innerit.next()) |bagstr| {
+ if (std.mem.eql(u8, bagstr[0..2], "no")) return null;
+ const lastsep = std.mem.lastIndexOfScalar(u8, bagstr, ' ').?;
+ const firstsep = std.mem.indexOfScalar(u8, bagstr, ' ').?;
+ const count = try std.fmt.parseInt(u32, bagstr[0..firstsep], 10);
+ const id = std.hash.CityHash64.hash(bagstr[firstsep + 1 .. lastsep]);
+ return BagCount{ .id = id, .count = count };
+ } else {
+ return null;
+ }
+ }
+};
+
+fn countBagsTotal(map: *std.AutoHashMap(u64, std.ArrayList(BagCount)), outer: u64) u64 {
+ var sum: u64 = 0;
+ if (map.get(outer)) |inner| {
+ for (inner.items) |bag|
+ sum += bag.count * (1 + countBagsTotal(map, bag.id));
+ }
+ return sum;
+}
+
+fn countParentTypes(map: *std.AutoHashMap(u64, std.ArrayList(u64)), inner: u64, seen: *std.ArrayList(u64)) anyerror!u64 {
+ var sum: u64 = 0;
+ if (map.get(inner)) |outer| {
+ for (outer.items) |bagid| {
+ if (std.mem.indexOfScalar(u64, seen.items, bagid) == null) {
+ try seen.append(bagid);
+ sum += 1 + try countParentTypes(map, bagid, seen);
+ }
+ }
+ }
+ return sum;
+}
+
+fn part1(allocator: std.mem.Allocator, input: []u8, args: [][]u8) !?[]u8 {
+ _ = args;
+
+ var lineit = std.mem.tokenize(u8, input, "\n");
+ var map = std.AutoHashMap(u64, std.ArrayList(u64)).init(allocator);
+ defer {
+ var mapit = map.iterator();
+ while (mapit.next()) |kv| kv.value_ptr.deinit();
+ map.deinit();
+ }
+
+ while (lineit.next()) |line| {
+ var rule = BagRule.from(line);
+ while (try rule.nextInner()) |inner| {
+ if (map.get(inner.id) == null)
+ try map.put(inner.id, std.ArrayList(u64).init(allocator));
+ try map.getEntry(inner.id).?.value_ptr.append(rule.outer);
+ }
+ }
+
+ const target = std.hash.CityHash64.hash("shiny gold");
+ var seen = std.ArrayList(u64).init(allocator);
+ defer seen.deinit();
+
+ const answer = try countParentTypes(&map, target, &seen);
+
+ return try std.fmt.allocPrint(allocator, "{d}", .{answer});
+}
+
+fn part2(allocator: std.mem.Allocator, input: []u8, args: [][]u8) !?[]u8 {
+ _ = args;
+
+ var lineit = std.mem.tokenize(u8, input, "\n");
+ var map = std.AutoHashMap(u64, std.ArrayList(BagCount)).init(allocator);
+ defer {
+ var mapit = map.iterator();
+ while (mapit.next()) |kv| kv.value_ptr.deinit();
+ map.deinit();
+ }
+
+ const target = std.hash.CityHash64.hash("shiny gold");
+ while (lineit.next()) |line| {
+ var rule = BagRule.from(line);
+ if (map.get(rule.outer) == null)
+ try map.put(rule.outer, std.ArrayList(BagCount).init(allocator));
+ while (try rule.nextInner()) |bag| {
+ try map.getEntry(rule.outer).?.value_ptr.append(bag);
+ }
+ }
+
+ const answer = countBagsTotal(&map, target);
+
+ return try std.fmt.allocPrint(allocator, "{d}", .{answer});
+}
+
+pub const main = aoc.main(part1, part2, .{ "161", "30899" });
diff --git a/src/day7/part1 b/src/07/part1
diff --git a/src/day7/part2 b/src/07/part2
diff --git a/src/day8/input b/src/08/input
diff --git a/src/08/main.zig b/src/08/main.zig
@@ -0,0 +1,67 @@
+const std = @import("std");
+const aoc = @import("aoc");
+const Console = @import("console8").Console;
+
+fn runTillRepeat(console: *Console, instlist: *std.ArrayList(u64), swapon: ?u64) !void {
+ while (try console.parseNext()) |_inst| {
+ var inst = _inst;
+ aoc.debugfmt("{:<5}: {s} {d}\n", .{ console.instructptr, inst.opcode, inst.argval });
+ if (std.mem.indexOfScalar(u64, instlist.items, console.instructptr) != null) {
+ return;
+ }
+ if (swapon != null and swapon.? == console.instructptr) {
+ inst.opfunc = switch (inst.opfunc) {
+ Console.jumpInstruction => Console.nopInstruction,
+ Console.nopInstruction => Console.jumpInstruction,
+ else => unreachable,
+ };
+ }
+ try instlist.append(console.instructptr);
+ try console.exec(&inst);
+ }
+}
+
+fn part1(allocator: std.mem.Allocator, input: []u8, args: [][]u8) !?[]u8 {
+ _ = args;
+
+ var console = try Console.init(input, allocator);
+ defer console.deinit();
+
+ var instlist = std.ArrayList(u64).init(allocator);
+ defer instlist.deinit();
+
+ try runTillRepeat(&console, &instlist, null);
+
+ return try std.fmt.allocPrint(allocator, "{d}", .{console.accumulator});
+}
+
+fn part2(allocator: std.mem.Allocator, input: []u8, args: [][]u8) !?[]u8 {
+ _ = args;
+
+ var console = try Console.init(input, allocator);
+ defer console.deinit();
+
+ var instlist = std.ArrayList(u64).init(allocator);
+ defer instlist.deinit();
+
+ try runTillRepeat(&console, &instlist, null);
+
+ for (instlist.items) |inst| {
+ if (std.mem.eql(u8, "acc"[0..3], console.instlist[inst][0..3]))
+ continue;
+
+ var sim_seen = std.ArrayList(u64).init(allocator);
+ defer sim_seen.deinit();
+
+ console.reset();
+ //std.debug.print("Swapping instruction: {:<5}: {}\n", .{ inst, console.instlist[inst] });
+ runTillRepeat(&console, &sim_seen, inst) catch {};
+ if (console.jumpAddr == console.instlist.len or console.instructptr == console.instlist.len) {
+ return try std.fmt.allocPrint(allocator, "{d}", .{console.accumulator});
+ }
+ }
+
+ return null;
+}
+
+pub const main = aoc.main(part1, part2, .{ "1766", "1639" });
diff --git a/src/day8/part1 b/src/08/part1
diff --git a/src/day8/part2 b/src/08/part2
diff --git a/src/day9/input b/src/09/input
diff --git a/src/09/main.zig b/src/09/main.zig
@@ -0,0 +1,83 @@
+const std = @import("std");
+const aoc = @import("aoc");
+
+const preamble_size = 25;
+
+fn preambleHasSum(preamble: []u64, target: u64) bool {
+ for (preamble) |v1| {
+ for (preamble) |v2| {
+ if (v1 != v2 and v1 + v2 == target)
+ return true;
+ }
+ }
+ return false;
+}
+
+fn getInvalid(allocator: std.mem.Allocator, input: []u8) !u64 {
+ var preamble = std.ArrayList(u64).init(allocator);
+ defer preamble.deinit();
+
+ var i: u64 = 0;
+ var numit = std.mem.tokenize(u8, input, "\n");
+ while (numit.next()) |numstr| : (i += 1) {
+ const num = try std.fmt.parseInt(u64, numstr, 10);
+ if (i > preamble_size) {
+ if (!preambleHasSum(preamble.items, num)) {
+ return num;
+ }
+ preamble.items[(i - 1) % preamble_size] = num;
+ } else {
+ try preamble.append(num);
+ }
+ }
+
+ return aoc.Error.InvalidInput;
+}
+
+fn listSum(items: []u64) u64 {
+ var sum: u64 = 0;
+ for (items) |i|
+ sum += i;
+ return sum;
+}
+
+fn part1(allocator: std.mem.Allocator, input: []u8, args: [][]u8) !?[]u8 {
+ _ = args;
+
+ const answer = try getInvalid(allocator, input);
+
+ return try std.fmt.allocPrint(allocator, "{d}", .{answer});
+}
+
+fn part2(allocator: std.mem.Allocator, input: []u8, args: [][]u8) !?[]u8 {
+ _ = args;
+
+ const invalid = try getInvalid(allocator, input);
+
+ var numset = std.ArrayList(u64).init(allocator);
+ defer numset.deinit();
+
+ var numit = std.mem.tokenize(u8, input, "\n");
+ while (true) {
+ const sum = listSum(numset.items);
+ if (sum < invalid) {
+ const numstr = numit.next();
+ if (numstr == null) break;
+ const num = try std.fmt.parseInt(u64, numstr.?, 10);
+ try numset.append(num);
+ } else if (sum > invalid) {
+ _ = numset.orderedRemove(0);
+ } else {
+ break;
+ }
+ }
+
+ if (numset.items.len > 0) {
+ const answer = std.mem.min(u64, numset.items) + std.mem.max(u64, numset.items);
+ return try std.fmt.allocPrint(allocator, "{d}", .{answer});
+ }
+
+ return null;
+}
+
+pub const main = aoc.main(part1, part2, .{ "466456641", "55732936" });
diff --git a/src/day9/part1 b/src/09/part1
diff --git a/src/day9/part2 b/src/09/part2
diff --git a/src/day10/input b/src/10/input
diff --git a/src/10/main.zig b/src/10/main.zig
@@ -0,0 +1,119 @@
+const std = @import("std");
+const aoc = @import("aoc");
+
+fn part1(allocator: std.mem.Allocator, input: []u8, args: [][]u8) !?[]u8 {
+ _ = args;
+
+ var target: u32 = 0;
+
+ var intlist = std.ArrayList(u32).init(allocator);
+ defer intlist.deinit();
+
+ var lineit = std.mem.tokenize(u8, input, "\n");
+ while (lineit.next()) |line| {
+ var val = try std.fmt.parseInt(u32, line, 10);
+ if (val > target) {
+ target = val;
+ }
+ try intlist.append(val);
+ }
+
+ target += 3;
+ try intlist.append(target);
+
+ if (intlist.items.len == 0) return null;
+
+ std.sort.sort(u32, intlist.items, {}, comptime std.sort.asc(u32));
+
+ var diffs = [_]u32{ 0, 0, 0, 0 };
+ var last: u32 = 0;
+ for (intlist.items) |ov| {
+ if (ov - last > 3 or ov == last) {
+ aoc.debugfmt("Unable to find a suitable adapter for {} output jolts (next: {} jolts)\n", .{ last, ov });
+ return aoc.Error.InvalidInput;
+ }
+ diffs[ov - last] += 1;
+ last = ov;
+ }
+
+ return try std.fmt.allocPrint(allocator, "{d}", .{diffs[1] * diffs[3]});
+}
+
+fn countArrangements(arrangement: []u32, adapters: []const u32, adaptermask: []u1, target: u32, fillcount: u32, searchstart: u32, count: *u32) void {
+ var last: u32 = 0;
+ if (fillcount > 0) {
+ last = arrangement[fillcount - 1];
+ }
+
+ if (last == target) {
+ count.* += 1;
+ return;
+ }
+
+ for (adapters[searchstart..]) |adap, i| {
+ if (adaptermask[searchstart + i] == 1) continue;
+ if (adap > last + 3) break;
+
+ adaptermask[searchstart + i] = 1;
+ arrangement[fillcount] = adap;
+ countArrangements(arrangement, adapters, adaptermask, target, fillcount + 1, searchstart + @intCast(u32, i) + 1, count);
+ adaptermask[searchstart + i] = 0;
+ }
+}
+
+fn groupPermutations(adapters: []const u32) u64 {
+ if (adapters.len == 1) return 1;
+ var count: u64 = 0;
+ for (adapters) |_, i| {
+ if (i == 0) continue;
+ if (adapters[i] <= adapters[0] + 3) {
+ count += groupPermutations(adapters[i..]);
+ }
+ }
+ return count;
+}
+
+fn part2(allocator: std.mem.Allocator, input: []u8, args: [][]u8) !?[]u8 {
+ _ = args;
+
+ var target: u32 = 0;
+
+ var intlist = std.ArrayList(u32).init(allocator);
+ defer intlist.deinit();
+
+ try intlist.append(0);
+
+ var lineit = std.mem.tokenize(u8, input, "\n");
+ while (lineit.next()) |line| {
+ var val = try std.fmt.parseInt(u32, line, 10);
+ if (val > target) {
+ target = val;
+ }
+ try intlist.append(val);
+ }
+
+ target += 3;
+ try intlist.append(target);
+
+ if (intlist.items.len == 0) return aoc.Error.InvalidInput;
+
+ std.sort.sort(u32, intlist.items, {}, comptime std.sort.asc(u32));
+
+ var gapstart: u32 = 0;
+ var multiplier: u128 = 1;
+
+ var i: u32 = 0;
+ while (i < intlist.items.len - 1) : (i += 1) {
+ // whenever we encounter a 3 jolt gap, we can calc permutations of group before
+ if (i + 1 < intlist.items.len and intlist.items[i + 1] == intlist.items[i] + 3) {
+ multiplier *= groupPermutations(intlist.items[gapstart .. i + 1]);
+ aoc.debugfmt("gap from {} to {} => {}\n", .{ intlist.items[i], intlist.items[i + 1], multiplier });
+ aoc.debugfmt("group size: {}\n", .{i + 1 - gapstart});
+ gapstart = i + 1;
+ }
+ }
+
+ return try std.fmt.allocPrint(allocator, "{d}", .{multiplier});
+}
+
+pub const main = aoc.main(part1, part2, .{ "1998", "347250213298688" });
diff --git a/src/day10/out b/src/10/out
diff --git a/src/day10/part1 b/src/10/part1
diff --git a/src/day10/part2 b/src/10/part2
diff --git a/src/day10/test-input b/src/10/test-input
diff --git a/src/day10/test-input2 b/src/10/test-input2
diff --git a/src/day11/input b/src/11/input
diff --git a/src/11/main.zig b/src/11/main.zig
@@ -0,0 +1,169 @@
+const std = @import("std");
+const aoc = @import("aoc");
+
+const SeatState = enum { EMPTY, FLOOR, TAKEN };
+const MapDims = struct { width: usize, height: usize };
+const Dir = struct { x: i8, y: i8 };
+const Pos = struct { x: i128, y: i128 };
+
+const adjacent = [_]Dir{
+ Dir{ .x = -1, .y = -1 },
+ Dir{ .x = -0, .y = -1 },
+ Dir{ .x = 1, .y = -1 },
+ Dir{ .x = -1, .y = 0 },
+ Dir{ .x = 1, .y = 0 },
+ Dir{ .x = -1, .y = 1 },
+ Dir{ .x = 0, .y = 1 },
+ Dir{ .x = 1, .y = 1 },
+};
+
+fn parseMap(mapitems: *[]SeatState, dims: *MapDims, input: []const u8, allocator: std.mem.Allocator) !void {
+ var lineit = std.mem.tokenize(u8, input, "\n");
+ var map = std.ArrayList(SeatState).init(allocator);
+ errdefer map.deinit();
+ while (lineit.next()) |line| {
+ if (dims.width == 0) {
+ dims.width = line.len;
+ } else if (dims.width != line.len) {
+ return aoc.Error.InvalidInput;
+ }
+ for (line) |c| {
+ try map.append(switch (c) {
+ '#' => SeatState.TAKEN,
+ 'L' => SeatState.EMPTY,
+ '.' => SeatState.FLOOR,
+ else => {
+ return aoc.Error.InvalidInput;
+ },
+ });
+ }
+ dims.height += 1;
+ }
+ mapitems.* = map.toOwnedSlice();
+}
+
+fn printMap(mapitems: []SeatState, dims: MapDims) void {
+ for (mapitems) |state, i| {
+ const c: u8 = switch (state) {
+ SeatState.EMPTY => 'L',
+ SeatState.TAKEN => '#',
+ SeatState.FLOOR => '.',
+ };
+ if (i % dims.width == 0) {
+ aoc.debugfmt("\n", .{});
+ }
+ aoc.debugfmt("{c}", .{c});
+ }
+}
+
+fn simulateStrategyOne(before: []SeatState, after: []SeatState, dims: MapDims) u32 {
+ var seat_changes: u32 = 0;
+ for (before) |state, i| {
+ const p = Pos{ .x = i % dims.width, .y = i / dims.width };
+ var count: u32 = 0;
+ for (adjacent) |ap| {
+ if (p.x + ap.x >= dims.width or p.x + ap.x < 0 or p.y + ap.y >= dims.height or p.y + ap.y < 0) continue;
+ const ni = @intCast(u64, @intCast(i64, i) + ap.x + ap.y * @intCast(i64, dims.width));
+ count += @boolToInt(before[ni] == SeatState.TAKEN);
+ }
+ if (state == SeatState.EMPTY and count == 0) {
+ after[i] = SeatState.TAKEN;
+ seat_changes += 1;
+ } else if (state == SeatState.TAKEN and count >= 4) {
+ after[i] = SeatState.EMPTY;
+ seat_changes += 1;
+ } else {
+ after[i] = before[i];
+ }
+ }
+ return seat_changes;
+}
+
+fn simulateStrategyTwo(before: []SeatState, after: []SeatState, dims: MapDims) u32 {
+ var seat_changes: u32 = 0;
+ for (before) |state, i| {
+ const p = Pos{ .x = i % dims.width, .y = i / dims.width };
+ var count: u32 = 0;
+ for (adjacent) |ap| {
+ var iterp = Pos{ .x = p.x + ap.x, .y = p.y + ap.y };
+ while (iterp.x < dims.width and iterp.x >= 0 and iterp.y < dims.height and iterp.y >= 0) {
+ const ni = @intCast(u64, iterp.x + iterp.y * @intCast(i64, dims.width));
+ if (before[ni] == SeatState.TAKEN) {
+ count += 1;
+ break;
+ } else if (before[ni] == SeatState.EMPTY) {
+ break;
+ } else {
+ iterp.x += ap.x;
+ iterp.y += ap.y;
+ }
+ }
+ }
+ if (state == SeatState.EMPTY and count == 0) {
+ after[i] = SeatState.TAKEN;
+ seat_changes += 1;
+ } else if (state == SeatState.TAKEN and count >= 5) {
+ after[i] = SeatState.EMPTY;
+ seat_changes += 1;
+ } else {
+ after[i] = before[i];
+ }
+ }
+ return seat_changes;
+}
+
+fn part1(allocator: std.mem.Allocator, input: []u8, args: [][]u8) !?[]u8 {
+ _ = args;
+
+ var mapdims = MapDims{ .width = 0, .height = 0 };
+ var mapitems: []SeatState = undefined;
+ try parseMap(&mapitems, &mapdims, input, allocator);
+ defer allocator.free(mapitems);
+
+ var mapresult = try allocator.alloc(SeatState, mapitems.len);
+ defer allocator.free(mapresult);
+
+ var round: u32 = 0;
+ while (simulateStrategyOne(mapitems, mapresult, mapdims) > 0) : (round += 1) {
+ aoc.debugfmt("\rRound: {}", .{round});
+ std.mem.copy(SeatState, mapitems, mapresult);
+ }
+
+ var taken_count: u64 = 0;
+ for (mapresult) |state| {
+ taken_count += @boolToInt(state == SeatState.TAKEN);
+ }
+
+ aoc.debugfmt("\nSeats Occupied: {}\n", .{taken_count});
+
+ return try std.fmt.allocPrint(allocator, "{d}", .{taken_count});
+}
+
+fn part2(allocator: std.mem.Allocator, input: []u8, args: [][]u8) !?[]u8 {
+ _ = args;
+
+ var mapdims = MapDims{ .width = 0, .height = 0 };
+ var mapitems: []SeatState = undefined;
+ try parseMap(&mapitems, &mapdims, input, allocator);
+ defer allocator.free(mapitems);
+
+ var mapresult = try allocator.alloc(SeatState, mapitems.len);
+ defer allocator.free(mapresult);
+
+ var round: u32 = 0;
+ while (simulateStrategyTwo(mapitems, mapresult, mapdims) > 0) : (round += 1) {
+ aoc.debugfmt("\rRound: {}", .{round});
+ std.mem.copy(SeatState, mapitems, mapresult);
+ }
+
+ var taken_count: u64 = 0;
+ for (mapresult) |state| {
+ taken_count += @boolToInt(state == SeatState.TAKEN);
+ }
+
+ aoc.debugfmt("\nSeats Occupied: {}\n", .{taken_count});
+
+ return try std.fmt.allocPrint(allocator, "{d}", .{taken_count});
+}
+
+pub const main = aoc.main(part1, part2, .{ "2126", "1914" });
diff --git a/src/day11/part1 b/src/11/part1
diff --git a/src/day11/part2 b/src/11/part2
diff --git a/src/day12/input b/src/12/input
diff --git a/src/day12/input-test b/src/12/input-test
diff --git a/src/12/main.zig b/src/12/main.zig
@@ -0,0 +1,67 @@
+const std = @import("std");
+const aoc = @import("aoc");
+const Pos = aoc.Pos;
+const Dir = aoc.Dir;
+
+const Ship = struct { pos: Pos, waypoint: Pos, dir: usize };
+
+fn part1(allocator: std.mem.Allocator, input: []u8, args: [][]u8) !?[]u8 {
+ _ = args;
+
+ var ship = Ship{ .pos = Pos{ .x = 0, .y = 0 }, .waypoint = Pos{ .x = 0, .y = 0 }, .dir = 0 };
+ var lineit = std.mem.tokenize(u8, input, "\n");
+ while (lineit.next()) |line| {
+ const val = try std.fmt.parseInt(u32, line[1..], 10);
+ switch (line[0]) {
+ 'N' => ship.pos = ship.pos.add(Dir.North.mult(val)),
+ 'S' => ship.pos = ship.pos.add(Dir.South.mult(val)),
+ 'E' => ship.pos = ship.pos.add(Dir.East.mult(val)),
+ 'W' => ship.pos = ship.pos.add(Dir.West.mult(val)),
+ 'L' => ship.dir = Dir.nextCCW(ship.dir, @divExact(val, 90)),
+ 'R' => ship.dir = Dir.nextCW(ship.dir, @divExact(val, 90)),
+ 'F' => ship.pos = ship.pos.add(Dir.dirs[ship.dir].mult(val)),
+ else => {
+ return aoc.Error.InvalidInput;
+ },
+ }
+ }
+
+ const answer = std.math.absCast(ship.pos.x) + std.math.absCast(ship.pos.y);
+
+ return try std.fmt.allocPrint(allocator, "{d}", .{answer});
+}
+
+fn part2(allocator: std.mem.Allocator, input: []u8, args: [][]u8) !?[]u8 {
+ _ = args;
+
+ var ship = Ship{ .pos = Pos{ .x = 0, .y = 0 }, .waypoint = Pos{ .x = 10, .y = 1 }, .dir = 0 };
+ var lineit = std.mem.tokenize(u8, input, "\n");
+ while (lineit.next()) |line| {
+ const val = try std.fmt.parseInt(u32, line[1..], 10);
+ switch (line[0]) {
+ 'N' => ship.waypoint = ship.waypoint.add(Dir.North.mult(val)),
+ 'S' => ship.waypoint = ship.waypoint.add(Dir.South.mult(val)),
+ 'E' => ship.waypoint = ship.waypoint.add(Dir.East.mult(val)),
+ 'W' => ship.waypoint = ship.waypoint.add(Dir.West.mult(val)),
+ 'L' => {
+ var new = Dir.rotCCW(ship.waypoint, @divExact(val, 90));
+ ship.waypoint = new;
+ },
+ 'R' => {
+ var new = Dir.rotCW(ship.waypoint, @divExact(val, 90));
+ ship.waypoint = new;
+ },
+ 'F' => ship.pos = ship.pos.add(ship.waypoint.mult(val)),
+ else => {
+ return aoc.Error.InvalidInput;
+ },
+ }
+ aoc.debugfmt("{s} {} {} {} {}\n", .{ line, ship.waypoint.x, ship.waypoint.y, ship.pos.x, ship.pos.y });
+ }
+
+ const answer = std.math.absCast(ship.pos.x) + std.math.absCast(ship.pos.y);
+
+ return try std.fmt.allocPrint(allocator, "{d}", .{answer});
+}
+
+pub const main = aoc.main(part1, part2, .{ "1191", "61053" });
diff --git a/src/day12/part1 b/src/12/part1
diff --git a/src/day12/part2 b/src/12/part2
diff --git a/src/day13/input b/src/13/input
diff --git a/src/day13/input-test b/src/13/input-test
diff --git a/src/13/main.zig b/src/13/main.zig
@@ -0,0 +1,112 @@
+const std = @import("std");
+const aoc = @import("aoc");
+
+fn gcd(a: u64, b: u64) u64 {
+ var ac = a;
+ var bc = b;
+ while (true) {
+ if (ac > bc) {
+ ac = ac % bc;
+ if (ac == 0) return bc;
+ } else {
+ bc = bc % ac;
+ if (bc == 0) return ac;
+ }
+ }
+}
+
+fn lcm(a: u64, b: u64) u64 {
+ return @divExact(a * b, gcd(a, b));
+}
+
+fn waittime(start: u32, busid: u32) u32 {
+ return (busid - (start % busid)) % busid;
+}
+
+fn printRegion(buses: []u32, start: u64, end: u64) void {
+ aoc.debugfmt(" ", .{});
+ for (buses) |bus| {
+ aoc.debugfmt(" {:^5}", .{bus});
+ }
+ aoc.debugfmt("\n", .{});
+
+ var i = start;
+ while (i < end) : (i += 1) {
+ aoc.debugfmt("{:<10}", .{i});
+ for (buses) |bus| {
+ var c: u8 = '.';
+ if (bus > 0 and i % bus == 0) c = 'D';
+ aoc.debugfmt(" {c} ", .{c});
+ }
+ aoc.debugfmt("\n", .{});
+ }
+ aoc.debugfmt("\n", .{});
+}
+
+fn part1(allocator: std.mem.Allocator, input: []u8, args: [][]u8) !?[]u8 {
+ _ = args;
+
+ var lineit = std.mem.tokenize(u8, input, "\n");
+ var start = try std.fmt.parseInt(u32, lineit.next().?, 10);
+
+ var bestbus: ?u32 = null;
+ var busit = std.mem.tokenize(u8, lineit.next().?, ",");
+ while (busit.next()) |bus| {
+ if (bus[0] == 'x') continue;
+ const val = try std.fmt.parseInt(u32, bus, 10);
+ if (bestbus == null or waittime(start, val) < waittime(start, bestbus.?)) {
+ bestbus = val;
+ }
+ }
+
+ const answer = bestbus.? * waittime(start, bestbus.?);
+
+ return try std.fmt.allocPrint(allocator, "{d}", .{answer});
+}
+
+fn part2(allocator: std.mem.Allocator, input: []u8, args: [][]u8) !?[]u8 {
+ _ = args;
+
+ var lineit = std.mem.tokenize(u8, input, "\n");
+ _ = try std.fmt.parseInt(u32, lineit.next().?, 10);
+
+ var busses = std.ArrayList(u32).init(allocator);
+ defer busses.deinit();
+
+ var busit = std.mem.tokenize(u8, lineit.next().?, ",");
+
+ const first = try std.fmt.parseInt(u32, busit.next().?, 10);
+ try busses.append(first);
+
+ var offset: u64 = 0;
+ var cycle: u64 = first;
+ var delay: u32 = 1;
+ while (busit.next()) |bus| : (delay += 1) {
+ if (bus[0] == 'x') {
+ try busses.append(0);
+ continue;
+ }
+ const val = try std.fmt.parseInt(u32, bus, 10);
+ try busses.append(val);
+
+ var mult: u64 = @divFloor(offset + delay, val);
+ if ((offset + delay) % val != 0) mult += 1;
+ while ((mult * val - offset - delay) % cycle != 0) {
+ mult += std.math.max(1, @divFloor(cycle - (mult * val - offset - delay) % cycle, val));
+ }
+ offset = mult * val - delay;
+
+ cycle = lcm(cycle, val);
+ if (aoc.debug) {
+ printRegion(busses.items, offset, offset + delay + 1);
+ printRegion(busses.items, offset + cycle, offset + cycle + delay + 1);
+ aoc.debugfmt("{}\n", .{offset});
+ }
+ }
+
+ printRegion(busses.items, offset, offset + busses.items.len);
+
+ return try std.fmt.allocPrint(allocator, "{}", .{offset});
+}
+
+pub const main = aoc.main(part1, part2, .{ "6568", "554865447501099" });
diff --git a/src/day13/notes b/src/13/notes
diff --git a/src/day13/part1 b/src/13/part1
diff --git a/src/day13/part2 b/src/13/part2
diff --git a/src/day14/input b/src/14/input
diff --git a/src/day14/input-test b/src/14/input-test
diff --git a/src/day14/input-test2 b/src/14/input-test2
diff --git a/src/day14/input-test3 b/src/14/input-test3
diff --git a/src/14/main.zig b/src/14/main.zig
@@ -0,0 +1,122 @@
+const std = @import("std");
+const aoc = @import("aoc");
+
+fn getBit(v: u36, i: u6) bool {
+ return ((v >> i) & 1) > 0;
+}
+
+fn clearBit(v: u36, i: u6) u36 {
+ return v & ~(@as(u36, 1) << i);
+}
+
+fn setBit(v: u36, i: u6) u36 {
+ return v | (@as(u36, 1) << i);
+}
+
+fn getValStr(line: []const u8) ![]const u8 {
+ const sep = std.mem.indexOf(u8, line, " = ");
+ if (sep == null) return aoc.Error.InvalidInput;
+ return line[sep.? + 3 ..];
+}
+
+fn getAddrStr(line: []const u8) ![]const u8 {
+ const sep = std.mem.indexOfScalar(u8, line, ']');
+ if (sep == null) return aoc.Error.InvalidInput;
+ return line[4..sep.?];
+}
+
+fn part1(allocator: std.mem.Allocator, input: []u8, args: [][]u8) !?[]u8 {
+ _ = args;
+
+ var answer: u64 = 0;
+
+ var memmap = std.AutoHashMap(u36, u64).init(allocator);
+ defer memmap.deinit();
+
+ var ormask: u36 = 0;
+ var andmask: u36 = ~@as(u36, 0);
+
+ var lineit = std.mem.tokenize(u8, input, "\n");
+ while (lineit.next()) |line| {
+ if (std.mem.eql(u8, line[0..4], "mask")) {
+ andmask = ~@as(u36, 0);
+ ormask = 0;
+ for (try getValStr(line)) |c, i| {
+ if (c == '0') {
+ andmask = clearBit(andmask, @intCast(u6, 35 - i));
+ } else if (c == '1') {
+ ormask = setBit(ormask, @intCast(u6, 35 - i));
+ }
+ }
+ } else {
+ const val = try std.fmt.parseInt(u36, try getValStr(line), 10);
+ const addr = try std.fmt.parseInt(u36, try getAddrStr(line), 10);
+ try memmap.put(addr, (val & andmask) | ormask);
+ }
+ }
+
+ var mapit = memmap.iterator();
+ while (mapit.next()) |kv| {
+ answer += kv.value_ptr.*;
+ }
+
+ return try std.fmt.allocPrint(allocator, "{}", .{answer});
+}
+
+fn bitRecurse(map: *std.AutoHashMap(u36, u64), addr: *u36, val: u64, mask: u36, index: u6) anyerror!void {
+ if (index == 36) {
+ aoc.debugfmt("SET: {b} {}\n", .{ addr.*, val });
+ try map.put(addr.*, val);
+ } else {
+ if (getBit(mask, index)) {
+ addr.* = setBit(addr.*, index);
+ try bitRecurse(map, addr, val, mask, index + 1);
+ addr.* = clearBit(addr.*, index);
+ try bitRecurse(map, addr, val, mask, index + 1);
+ } else {
+ try bitRecurse(map, addr, val, mask, index + 1);
+ }
+ }
+}
+
+fn part2(allocator: std.mem.Allocator, input: []u8, args: [][]u8) !?[]u8 {
+ _ = args;
+
+ var answer: u64 = 0;
+
+ var memmap = std.AutoHashMap(u36, u64).init(allocator);
+ defer memmap.deinit();
+
+ var ormask: u36 = 0;
+ var flipmask: u36 = 0;
+
+ var lineit = std.mem.tokenize(u8, input, "\n");
+ while (lineit.next()) |line| {
+ if (std.mem.eql(u8, line[0..4], "mask")) {
+ ormask = 0;
+ flipmask = 0;
+ for (try getValStr(line)) |c, i| {
+ if (c == '1') {
+ ormask = setBit(ormask, @intCast(u6, 35 - i));
+ } else if (c == 'X') {
+ flipmask = setBit(flipmask, @intCast(u6, 35 - i));
+ }
+ }
+ } else {
+ var addr = try std.fmt.parseInt(u36, try getAddrStr(line), 10);
+ const val = try std.fmt.parseInt(u36, try getValStr(line), 10);
+ addr = addr | ormask;
+ aoc.debugfmt("{b} {b} {} {}\n", .{ flipmask, ormask, addr, val });
+ try bitRecurse(&memmap, &addr, val, flipmask, 0);
+ }
+ }
+
+ var mapit = memmap.iterator();
+ while (mapit.next()) |kv| {
+ answer += kv.value_ptr.*;
+ }
+
+ return try std.fmt.allocPrint(allocator, "{}", .{answer});
+}
+
+pub const main = aoc.main(part1, part2, .{ "4886706177792", "3348493585827" });
diff --git a/src/day14/part1 b/src/14/part1
diff --git a/src/day14/part2 b/src/14/part2
diff --git a/src/day15/input b/src/15/input
diff --git a/src/15/main.zig b/src/15/main.zig
@@ -0,0 +1,63 @@
+const std = @import("std");
+const aoc = @import("aoc");
+
+const Occurance = struct { last: u32, beforelast: u32 };
+
+fn getNthSpoken(allocator: std.mem.Allocator, input: []u8, spoken: u32) !u32 {
+ var occurances = std.AutoHashMap(u32, Occurance).init(allocator);
+ defer occurances.deinit();
+
+ var intlist = std.ArrayList(u32).init(allocator);
+ defer intlist.deinit();
+
+ var numit = std.mem.tokenize(u8, input, "\n,");
+ var i: u32 = 0;
+ while (numit.next()) |numstr| : (i += 1) {
+ const num = try std.fmt.parseInt(u32, numstr, 10);
+ try intlist.append(num);
+ try occurances.put(num, Occurance{ .last = i, .beforelast = i });
+ }
+
+ while (i < spoken) : (i += 1) {
+ if (aoc.debug and i % 100000 == 0)
+ aoc.debugfmt("\r{}", .{i});
+
+ const num = intlist.items[i - 1];
+ var entry = occurances.getEntry(num);
+ var diff: u32 = 0;
+ if (entry) |occ_entry| {
+ diff = occ_entry.value_ptr.last - occ_entry.value_ptr.beforelast;
+ }
+ entry = occurances.getEntry(diff);
+ if (entry) |occ_entry| {
+ occ_entry.value_ptr.beforelast = occ_entry.value_ptr.last;
+ occ_entry.value_ptr.last = i;
+ } else {
+ try occurances.put(diff, Occurance{ .last = i, .beforelast = i });
+ }
+ try intlist.append(diff);
+ }
+
+ if (aoc.debug)
+ aoc.debugfmt("\r \r", .{});
+
+ return intlist.items[spoken - 1];
+}
+
+fn part1(allocator: std.mem.Allocator, input: []u8, args: [][]u8) !?[]u8 {
+ _ = args;
+
+ const answer = try getNthSpoken(allocator, input, 2020);
+
+ return try std.fmt.allocPrint(allocator, "{}", .{answer});
+}
+
+fn part2(allocator: std.mem.Allocator, input: []u8, args: [][]u8) !?[]u8 {
+ _ = args;
+
+ const answer = try getNthSpoken(allocator, input, 30000000);
+
+ return try std.fmt.allocPrint(allocator, "{}", .{answer});
+}
+
+pub const main = aoc.main(part1, part2, .{ "1259", "689" });
diff --git a/src/day15/part1 b/src/15/part1
diff --git a/src/day15/part2 b/src/15/part2
diff --git a/src/day16/input b/src/16/input
diff --git a/src/day16/input-test b/src/16/input-test
diff --git a/src/16/main.zig b/src/16/main.zig
@@ -0,0 +1,179 @@
+const std = @import("std");
+const aoc = @import("aoc");
+
+const Range = struct { min: u32, max: u32 };
+const FieldRule = struct { name: []const u8, r1: Range, r2: Range };
+
+fn assert(comptime T: type, part: ?T) !T {
+ if (part == null) return aoc.Error.InvalidInput;
+ return part.?;
+}
+
+fn parseRange(str: []const u8) !Range {
+ const sep = try assert(usize, std.mem.indexOfScalar(u8, str, '-'));
+ if (sep == str.len - 1) return aoc.Error.InvalidInput;
+ return Range{
+ .min = try std.fmt.parseInt(u32, str[0..sep], 10),
+ .max = try std.fmt.parseInt(u32, str[sep + 1 ..], 10),
+ };
+}
+
+fn parseRules(rules: *std.ArrayList(FieldRule), str: []const u8) !void {
+ var lineit = std.mem.tokenize(u8, str, "\n");
+ while (lineit.next()) |line| {
+ const sep = try assert(usize, std.mem.indexOf(u8, line, ": "));
+ if (sep == line.len - 1) return aoc.Error.InvalidInput;
+ const name = line[0..sep];
+ var rangepart = line[sep + 2 ..];
+ var spaceit = std.mem.tokenize(u8, rangepart, " ");
+ const r1 = try parseRange(try assert([]const u8, spaceit.next()));
+ _ = spaceit.next();
+ const r2 = try parseRange(try assert([]const u8, spaceit.next()));
+ try rules.append(FieldRule{ .name = name, .r1 = r1, .r2 = r2 });
+ }
+}
+
+fn parseVals(vals: *std.ArrayList(u32), str: []const u8) !void {
+ var lineit = std.mem.tokenize(u8, str, "\n");
+ while (lineit.next()) |line| {
+ var partit = std.mem.tokenize(u8, line, ",");
+ while (partit.next()) |part| {
+ try vals.append(try std.fmt.parseInt(u32, part, 10));
+ }
+ }
+}
+
+fn matchesRule(rule: FieldRule, v: u32) bool {
+ return (v >= rule.r1.min and v <= rule.r1.max or v >= rule.r2.min and v <= rule.r2.max);
+}
+
+fn hasRule(rules: []FieldRule, v: u32) bool {
+ for (rules) |r| {
+ if (matchesRule(r, v)) return true;
+ }
+ return false;
+}
+
+fn printCandidates(candidates: []u1, rulecount: usize, remove: usize) void {
+ var i: u32 = 0;
+ while (i < rulecount) : (i += 1) {
+ for (candidates[i * rulecount .. (i + 1) * rulecount]) |c| {
+ aoc.debugfmt("{} ", .{c});
+ }
+ if (i == remove) aoc.debugfmt(" <<<", .{});
+ aoc.debugfmt("\n", .{});
+ }
+}
+
+fn part1(allocator: std.mem.Allocator, input: []u8, args: [][]u8) !?[]u8 {
+ _ = args;
+
+ var answer: u32 = 0;
+
+ var rules = std.ArrayList(FieldRule).init(allocator);
+ defer rules.deinit();
+
+ var othervals = std.ArrayList(u32).init(allocator);
+ defer othervals.deinit();
+
+ var secit = std.mem.split(u8, input, "\n\n");
+ try parseRules(&rules, try assert([]const u8, secit.next()));
+ _ = secit.next();
+ try parseVals(&othervals, (try assert([]const u8, secit.next()))[16..]);
+
+ for (othervals.items) |v| {
+ if (!hasRule(rules.items, v)) answer += v;
+ }
+
+ return try std.fmt.allocPrint(allocator, "{}", .{answer});
+}
+
+fn part2(allocator: std.mem.Allocator, input: []u8, args: [][]u8) !?[]u8 {
+ _ = args;
+
+ var rules = std.ArrayList(FieldRule).init(allocator);
+ defer rules.deinit();
+
+ var ownvals = std.ArrayList(u32).init(allocator);
+ defer ownvals.deinit();
+
+ var othervals = std.ArrayList(u32).init(allocator);
+ defer othervals.deinit();
+
+ var secit = std.mem.split(u8, input, "\n\n");
+ try parseRules(&rules, try assert([]const u8, secit.next()));
+ try parseVals(&ownvals, (try assert([]const u8, secit.next()))[13..]);
+ try parseVals(&othervals, (try assert([]const u8, secit.next()))[16..]);
+
+ const rulecount = rules.items.len;
+
+ {
+ var index: u32 = 0;
+ while (index < othervals.items.len) {
+ var i: u32 = 0;
+ while (i < rulecount) : (i += 1) {
+ if (!hasRule(rules.items, othervals.items[index + i]))
+ break;
+ }
+
+ if (i == rulecount) {
+ index += @intCast(u32, rulecount);
+ } else {
+ if (aoc.debug)
+ aoc.debugfmt("REMOVE: ", .{});
+ i = 0;
+ while (i < rulecount) : (i += 1) {
+ if (aoc.debug)
+ aoc.debugfmt("{} ", .{othervals.items[index]});
+ _ = othervals.orderedRemove(index);
+ }
+ if (aoc.debug)
+ aoc.debugfmt("\n", .{});
+ }
+ }
+ }
+
+ var candidates = try allocator.alloc(u1, rulecount * rulecount);
+ defer allocator.free(candidates);
+ std.mem.set(u1, candidates, 1);
+
+ if (aoc.debug)
+ aoc.debugfmt("{}\n", .{othervals.items.len});
+ {
+ var index: u32 = 0;
+ while (index < othervals.items.len) : (index += 1) {
+ const ri = index % rulecount;
+ const v = othervals.items[index];
+ for (rules.items) |r, rri| {
+ if (!matchesRule(r, v)) {
+ candidates[ri * rulecount + rri] = 0;
+ }
+ }
+ }
+ }
+
+ var answer: u64 = 1;
+ {
+ var index: u32 = 0;
+ while (index < rulecount * rulecount) : (index += 1) {
+ var ri = index % rulecount;
+ const cc = candidates[ri * rulecount .. (ri + 1) * rulecount];
+ if (std.mem.count(u1, cc, ([_]u1{1})[0..]) == 1) {
+ const field = std.mem.indexOfScalar(u1, cc, 1).?;
+ if (std.mem.indexOf(u8, rules.items[field].name, "departure") != null)
+ answer *= ownvals.items[ri];
+ for (ownvals.items) |_, ii| {
+ candidates[ii * rulecount + field] = 0;
+ }
+ if (aoc.debug) {
+ printCandidates(candidates, rulecount, ri);
+ aoc.debugfmt("\n", .{});
+ }
+ }
+ }
+ }
+
+ return try std.fmt.allocPrint(allocator, "{}", .{answer});
+}
+
+pub const main = aoc.main(part1, part2, .{ "25972", "622670335901" });
diff --git a/src/day16/part1 b/src/16/part1
diff --git a/src/day16/part2 b/src/16/part2
diff --git a/src/day17/input b/src/17/input
diff --git a/src/day17/input-test b/src/17/input-test
diff --git a/src/17/main.zig b/src/17/main.zig
@@ -0,0 +1,195 @@
+const std = @import("std");
+const aoc = @import("aoc");
+
+fn PosVec(comptime N: u32) type {
+ return struct { data: [N]i64 };
+}
+
+const Active = bool;
+
+fn forNeighbors(comptime dims: u32, map: *std.AutoHashMap(PosVec(dims), Active), p: PosVec(dims), data: anytype, func: fn (map: *std.AutoHashMap(PosVec(dims), Active), p: PosVec(dims), d: @TypeOf(data)) anyerror!void) !void {
+ var i: u32 = 0;
+ while (i < comptime std.math.pow(u32, 3, dims)) : (i += 1) {
+ var np: PosVec(dims) = undefined;
+ var d: u32 = 0;
+ var skip = true;
+ while (d < dims) : (d += 1) {
+ const offset = (i / std.math.pow(u32, 3, d)) % 3;
+ np.data[d] = p.data[d] + @intCast(i64, offset) - 1;
+ if (skip and offset != 1) skip = false;
+ }
+ if (skip) continue;
+ try func(map, np, data);
+ }
+}
+
+fn posStr(comptime dims: u32, p: PosVec(dims)) void {
+ var d: u32 = 0;
+ while (d < dims) : (d += 1) {
+ aoc.debugfmt("{} ", .{p.data[d]});
+ }
+}
+
+fn countActive(comptime dims: u32) fn (map: *std.AutoHashMap(PosVec(dims), Active), p: PosVec(dims), d: *u32) anyerror!void {
+ const impl = struct {
+ fn func(map: *std.AutoHashMap(PosVec(dims), Active), p: PosVec(dims), d: *u32) anyerror!void {
+ d.* += @boolToInt(map.get(p) != null);
+ }
+ };
+ return impl.func;
+}
+
+fn addNew(comptime dims: u32) fn (oldmap: *std.AutoHashMap(PosVec(dims), Active), p: PosVec(dims), newmap: *std.AutoHashMap(PosVec(dims), Active)) anyerror!void {
+ const impl = struct {
+ fn func(oldmap: *std.AutoHashMap(PosVec(dims), Active), p: PosVec(dims), newmap: *std.AutoHashMap(PosVec(dims), Active)) anyerror!void {
+ if (newmap.get(p) != null) return;
+
+ var v = oldmap.get(p);
+ var state = (v != null);
+
+ var count: u32 = 0;
+ try forNeighbors(dims, oldmap, p, &count, countActive(dims));
+ if (state and count >= 2 and count <= 3 or !state and count == 3) {
+ try newmap.put(p, true);
+ }
+ }
+ };
+ return impl.func;
+}
+
+fn simulateRound(comptime dims: u32, map: *std.AutoHashMap(PosVec(dims), Active), allocator: std.mem.Allocator) !void {
+ var newmap = std.AutoHashMap(PosVec(dims), Active).init(allocator);
+ errdefer newmap.deinit();
+
+ var mapit = map.iterator();
+ while (mapit.next()) |kv| {
+ try forNeighbors(dims, map, kv.key_ptr.*, &newmap, addNew(dims));
+ try addNew(dims)(map, kv.key_ptr.*, &newmap);
+ }
+
+ std.mem.swap(std.AutoHashMap(PosVec(dims), Active), map, &newmap);
+ newmap.deinit();
+}
+
+fn sliceProduct(data: []i64) i64 {
+ var product: i64 = 1;
+ for (data) |v| {
+ product *= v;
+ }
+ return product;
+}
+
+fn printMap(comptime dims: u32, map: *std.AutoHashMap(PosVec(dims), Active)) void {
+ var min: ?PosVec(dims) = null;
+ var max: ?PosVec(dims) = null;
+
+ var mapit = map.iterator();
+ while (mapit.next()) |kv| {
+ if (min == null) min = kv.key_ptr.*;
+ if (max == null) max = kv.key_ptr.*;
+
+ var d: u32 = 0;
+ while (d < dims) : (d += 1) {
+ if (min.?.data[d] > kv.key_ptr.data[d]) min.?.data[d] = kv.key_ptr.data[d];
+ if (max.?.data[d] < kv.key_ptr.data[d]) max.?.data[d] = kv.key_ptr.data[d];
+ }
+ }
+
+ if (min == null or max == null) return;
+
+ var space: PosVec(dims) = undefined;
+ {
+ var d: u32 = 0;
+ while (d < dims) : (d += 1) {
+ space.data[d] = max.?.data[d] - min.?.data[d];
+ }
+ }
+
+ var i: usize = 0;
+ while (i < sliceProduct(space.data[0..])) : (i += @intCast(usize, space.data[0] * space.data[1])) {
+ var np: PosVec(dims) = undefined;
+ var d: u32 = 0;
+ while (d < dims) : (d += 1) {
+ np.data[d] = min.?.data[d] + @mod(@divFloor(@intCast(i64, i), sliceProduct(space.data[0..d])), space.data[d]);
+ }
+
+ d = 2;
+ aoc.debugfmt("Slice at: ", .{});
+ while (d < dims) : (d += 1) {
+ if (d > 2) aoc.debugfmt(",", .{});
+ aoc.debugfmt("{}.Dim = {} ", .{ d + 1, np.data[d] });
+ }
+ aoc.debugfmt("\n", .{});
+
+ var y = min.?.data[1];
+ while (y <= max.?.data[1]) : (y += 1) {
+ var x = min.?.data[0];
+ while (x <= max.?.data[0]) : (x += 1) {
+ var v = np;
+ v.data[0] = x;
+ v.data[1] = y;
+ var c: u8 = '.';
+ if (map.get(v) != null) c = '#';
+ aoc.debugfmt("{c}", .{c});
+ }
+ aoc.debugfmt("\n", .{});
+ }
+ aoc.debugfmt("\n", .{});
+ }
+}
+
+fn part1(allocator: std.mem.Allocator, input: []u8, args: [][]u8) !?[]u8 {
+ _ = args;
+
+ var map = std.AutoHashMap(PosVec(3), Active).init(allocator);
+ defer map.deinit();
+
+ var lineit = std.mem.tokenize(u8, input, "\n");
+ var y: i64 = 0;
+ while (lineit.next()) |line| : (y += 1) {
+ for (line) |c, x| {
+ if (c != '#') continue;
+ try map.put(PosVec(3){ .data = [_]i64{ @intCast(i64, x), y, 0 } }, true);
+ }
+ }
+
+ var i: usize = 0;
+ while (i < 6) : (i += 1) {
+ try simulateRound(3, &map, allocator);
+ if (aoc.debug) {
+ aoc.debugfmt("AFTER ROUND {}:\n", .{i + 1});
+ printMap(3, &map);
+ }
+ }
+
+ return try std.fmt.allocPrint(allocator, "{}", .{map.count()});
+}
+
+fn part2(allocator: std.mem.Allocator, input: []u8, args: [][]u8) !?[]u8 {
+ _ = args;
+
+ var map = std.AutoHashMap(PosVec(4), Active).init(allocator);
+ defer map.deinit();
+
+ var lineit = std.mem.tokenize(u8, input, "\n");
+ var y: i64 = 0;
+ while (lineit.next()) |line| : (y += 1) {
+ for (line) |c, x| {
+ if (c != '#') continue;
+ try map.put(PosVec(4){ .data = [_]i64{ @intCast(i64, x), y, 0, 0 } }, true);
+ }
+ }
+
+ var i: usize = 0;
+ while (i < 6) : (i += 1) {
+ try simulateRound(4, &map, allocator);
+ if (aoc.debug) {
+ aoc.debugfmt("AFTER ROUND {}:\n", .{i + 1});
+ printMap(4, &map);
+ }
+ }
+
+ return try std.fmt.allocPrint(allocator, "{}", .{map.count()});
+}
+
+pub const main = aoc.main(part1, part2, .{ "304", "1868" });
diff --git a/src/day17/part1 b/src/17/part1
diff --git a/src/day17/part2 b/src/17/part2
diff --git a/src/day18/input b/src/18/input
diff --git a/src/day18/input-test b/src/18/input-test
diff --git a/src/day18/input-test2 b/src/18/input-test2
diff --git a/src/18/main.zig b/src/18/main.zig
@@ -0,0 +1,177 @@
+// Own twist on https://en.wikipedia.org/wiki/Shunting-yard_algorithm
+
+const std = @import("std");
+const aoc = @import("aoc");
+
+const OpType = enum { ADD, MULT, COUNT };
+const Op = struct { prio: u32, optype: OpType };
+const Item = union(enum) { num: i64, op: OpType };
+
+const op_names = [_][]const u8{ "ADD", "MULT" };
+
+fn printStack(stack: []Item) void {
+ for (stack) |item| {
+ switch (item) {
+ .op => aoc.debugfmt("{s} ", .{op_names[@enumToInt(item.op)]}),
+ .num => aoc.debugfmt("{} ", .{item.num}),
+ }
+ }
+ aoc.debugfmt("\n", .{});
+}
+
+fn parseToken(line: []const u8, i: *usize, depth: *u32, op_prio: []const u32, mathstack: *std.ArrayList(Item), opstack: *std.ArrayList(Op)) !bool {
+ if (i.* > line.len) {
+ return false;
+ } else if (i.* == line.len) {
+ while (opstack.items.len > 0)
+ try mathstack.append(Item{ .op = opstack.pop().optype });
+ } else {
+ const c = line[i.*];
+ switch (c) {
+ '+', '*' => {
+ const optype = switch (c) {
+ '+' => OpType.ADD,
+ '*' => OpType.MULT,
+ else => unreachable,
+ };
+ const prio = depth.* * @enumToInt(OpType.COUNT) + op_prio[@enumToInt(optype)];
+ while (opstack.items.len > 0 and
+ opstack.items[opstack.items.len - 1].prio >= prio)
+ {
+ try mathstack.append(Item{ .op = opstack.pop().optype });
+ }
+ try opstack.append(Op{ .optype = optype, .prio = prio });
+ },
+ '(' => depth.* += 1,
+ ')' => depth.* -= 1,
+ ' ' => {},
+ else => {
+ // in this case we know that every number is one digit..
+ // crappy zig parseInt requires span of exact int size
+ // before we even know the format >:(((
+ const val = try std.fmt.parseInt(i64, line[i.* .. i.* + 1], 10);
+ try mathstack.append(Item{ .num = val });
+ },
+ }
+ }
+ i.* += 1;
+ return true;
+}
+
+fn reduceStack(mathstack: *std.ArrayList(Item), opstack: *std.ArrayList(Op), tmpstack: *std.ArrayList(Item)) !void {
+ _ = opstack;
+
+ while (mathstack.items.len > 0) {
+ while (mathstack.items[mathstack.items.len - 1] != .op and
+ tmpstack.items.len > 0)
+ {
+ try mathstack.append(tmpstack.pop());
+ }
+ if (mathstack.items.len < 3 or mathstack.items[mathstack.items.len - 1] != .op)
+ break;
+ const op = mathstack.pop();
+
+ // get first arg
+ if (mathstack.items[mathstack.items.len - 1] != .num) {
+ try tmpstack.append(op);
+ continue;
+ }
+ const a = mathstack.pop();
+
+ // get second arg
+ if (mathstack.items[mathstack.items.len - 1] != .num) {
+ try tmpstack.append(op);
+ try tmpstack.append(a);
+ continue;
+ }
+ const b = mathstack.pop();
+
+ const result: i64 = switch (op.op) {
+ OpType.ADD => a.num + b.num,
+ OpType.MULT => a.num * b.num,
+ else => unreachable,
+ };
+ try mathstack.append(Item{ .num = result });
+ }
+}
+
+fn printRPN(allocator: std.mem.Allocator, input: []u8, prios: []const u32) !void {
+ var mathstack = std.ArrayList(Item).init(allocator);
+ defer mathstack.deinit();
+
+ var opstack = std.ArrayList(Op).init(allocator);
+ defer opstack.deinit();
+
+ var lineit = std.mem.tokenize(u8, input, "\n");
+ while (lineit.next()) |line| {
+ var depth: u32 = 0;
+ var i: usize = 0;
+ while (try parseToken(line, &i, &depth, prios, &mathstack, &opstack)) {}
+ }
+
+ printStack(mathstack.items);
+}
+
+fn partProto(allocator: std.mem.Allocator, input: []u8, prios: []const u32) !?[]u8 {
+ var answer: i64 = 0;
+
+ if (aoc.debug) {
+ aoc.debugfmt("Reverse Polish Notation:\n", .{});
+ try printRPN(allocator, input, prios);
+ }
+
+ var mathstack = std.ArrayList(Item).init(allocator);
+ defer mathstack.deinit();
+
+ var opstack = std.ArrayList(Op).init(allocator);
+ defer opstack.deinit();
+
+ var tmpstack = std.ArrayList(Item).init(allocator);
+ defer tmpstack.deinit();
+
+ var lineit = std.mem.tokenize(u8, input, "\n");
+ while (lineit.next()) |line| {
+ var depth: u32 = 0;
+ var i: usize = 0;
+ while (try parseToken(line, &i, &depth, prios, &mathstack, &opstack)) {
+ try reduceStack(&mathstack, &opstack, &tmpstack);
+ }
+
+ if (mathstack.items.len != 1) return aoc.Error.InvalidInput;
+ const last = mathstack.items[mathstack.items.len - 1];
+ if (last != .num) return aoc.Error.InvalidInput;
+ answer += last.num;
+
+ try mathstack.resize(0);
+ try opstack.resize(0);
+ try tmpstack.resize(0);
+ }
+
+ return try std.fmt.allocPrint(allocator, "{}", .{answer});
+}
+
+fn part1(allocator: std.mem.Allocator, input: []u8, args: [][]u8) !?[]u8 {
+ _ = args;
+
+ const prios = [_]u32{ 1, 1 };
+
+ return try partProto(allocator, input, prios[0..]);
+}
+
+fn part2(allocator: std.mem.Allocator, input: []u8, args: [][]u8) !?[]u8 {
+ _ = args;
+
+ const prios = [_]u32{ 2, 1 };
+
+ return try partProto(allocator, input, prios[0..]);
+}
+
+test "unions" {
+ const item1 = Item{ .op = OpType.MULT };
+ const item2 = Item{ .num = 1000 };
+ const expect = std.testing.expect;
+ expect(item1 == .op);
+ expect(item2 == .num);
+}
+
+pub const main = aoc.main(part1, part2, .{ "5783053349377", "74821486966872" });
diff --git a/src/day18/part1 b/src/18/part1
diff --git a/src/day18/part2 b/src/18/part2
diff --git a/src/day19/input b/src/19/input
diff --git a/src/day19/input-test b/src/19/input-test
diff --git a/src/day19/input-test2 b/src/19/input-test2
diff --git a/src/day19/input-test3 b/src/19/input-test3
diff --git a/src/19/main.zig b/src/19/main.zig
@@ -0,0 +1,181 @@
+const std = @import("std");
+const aoc = @import("aoc");
+
+const Rule = union(enum) {
+ c: u8,
+ combos: []const []const usize,
+};
+
+fn printSlice(slice: []const usize) void {
+ for (slice) |v, i| {
+ if (i > 0) {
+ aoc.debugfmt(" ", .{});
+ }
+ aoc.debugfmt("{}", .{v});
+ }
+}
+
+var stacktrace: std.ArrayList(usize) = undefined;
+
+fn checkRule(rules: *std.AutoHashMap(usize, Rule), rid: usize, msg: []const u8, nextstack: *std.ArrayList(usize)) anyerror!bool {
+ if (msg.len == 0) return true;
+ const rule = rules.get(rid) orelse return aoc.Error.InvalidInput;
+
+ if (rule == .c) {
+ if (msg[0] != rule.c) return false;
+ if (msg.len == 1) return (nextstack.items.len == 0);
+ if (nextstack.items.len == 0) return false;
+
+ const next = nextstack.pop();
+
+ const valid = try checkRule(rules, next, msg[1..], nextstack);
+ if (valid) try stacktrace.append(next);
+ if (valid) return true;
+
+ try nextstack.append(next);
+ } else {
+ for (rule.combos) |ruleseq| {
+ try nextstack.appendSlice(ruleseq[1..]);
+ std.mem.reverse(usize, nextstack.items[nextstack.items.len - (ruleseq.len - 1) ..]);
+
+ const valid = try checkRule(rules, ruleseq[0], msg, nextstack);
+ if (valid) try stacktrace.append(ruleseq[0]);
+ if (valid) return true;
+
+ try nextstack.resize(nextstack.items.len - (ruleseq.len - 1));
+ }
+ }
+ return false;
+}
+
+fn freeRules(allocator: std.mem.Allocator, rules: *std.AutoHashMap(usize, Rule), ignore: ?[]const usize) void {
+ var mapit = rules.iterator();
+ while (mapit.next()) |kv| {
+ if (ignore != null and std.mem.indexOfScalar(usize, ignore.?, kv.key_ptr.*) != null) continue;
+ if (kv.value_ptr.* == .combos) {
+ for (kv.value_ptr.combos) |rs| {
+ allocator.free(rs);
+ }
+ allocator.free(kv.value_ptr.combos);
+ }
+ }
+ rules.deinit();
+}
+
+fn parseRule(allocator: std.mem.Allocator, rules: *std.AutoHashMap(usize, Rule), line: []const u8) !void {
+ const indexsep = try aoc.unwrap(std.mem.indexOf(u8, line, ": "));
+ const index = try std.fmt.parseInt(usize, line[0..indexsep], 10);
+
+ var chrsep = std.mem.indexOf(u8, line, "\"");
+ if (chrsep != null) {
+ if (chrsep.? == line.len - 1) return aoc.Error.InvalidInput;
+ try rules.put(index, Rule{ .c = line[chrsep.? + 1] });
+ } else {
+ var vals = std.ArrayList([]usize).init(allocator);
+ errdefer vals.deinit();
+
+ var ruleit = std.mem.split(u8, line[indexsep + 2 ..], " | ");
+ while (ruleit.next()) |r| {
+ var ruleids = std.ArrayList(usize).init(allocator);
+ errdefer ruleids.deinit();
+
+ var spaceit = std.mem.tokenize(u8, r, " ");
+ while (spaceit.next()) |word| {
+ try ruleids.append(try std.fmt.parseInt(usize, word, 10));
+ }
+
+ if (ruleids.items.len == 0) return aoc.Error.InvalidInput;
+
+ try vals.append(ruleids.items);
+ }
+
+ try rules.put(index, Rule{ .combos = vals.items });
+ }
+}
+
+fn part1(allocator: std.mem.Allocator, input: []u8, args: [][]u8) !?[]u8 {
+ _ = args;
+
+ var rules = std.AutoHashMap(usize, Rule).init(allocator);
+ defer freeRules(allocator, &rules, null);
+
+ var partit = std.mem.split(u8, input, "\n\n");
+
+ var lineit = std.mem.tokenize(u8, try aoc.unwrap(partit.next()), "\n");
+ while (lineit.next()) |line| {
+ try parseRule(allocator, &rules, line);
+ }
+
+ var answer: u32 = 0;
+ var nextstack = std.ArrayList(usize).init(allocator);
+ defer nextstack.deinit();
+
+ stacktrace = std.ArrayList(usize).init(allocator);
+ defer stacktrace.deinit();
+
+ lineit = std.mem.tokenize(u8, try aoc.unwrap(partit.next()), "\n");
+ var count: usize = 0;
+ while (lineit.next()) |line| {
+ count += 1;
+ if (try checkRule(&rules, 0, line, &nextstack))
+ answer += 1;
+ try nextstack.resize(0);
+ }
+
+ return try std.fmt.allocPrint(allocator, "{}", .{answer});
+}
+
+fn part2(allocator: std.mem.Allocator, input: []u8, args: [][]u8) !?[]u8 {
+ _ = args;
+
+ var rules = std.AutoHashMap(usize, Rule).init(allocator);
+ defer freeRules(allocator, &rules, ([_]usize{ 8, 11 })[0..]);
+
+ var partit = std.mem.split(u8, input, "\n\n");
+
+ var lineit = std.mem.tokenize(u8, try aoc.unwrap(partit.next()), "\n");
+ while (lineit.next()) |line| {
+ if (std.mem.eql(u8, line[0..2], "8:")) {
+ const p1: []const usize = ([_]usize{42})[0..];
+ const p2: []const usize = ([_]usize{ 42, 8 })[0..];
+ try rules.put(8, Rule{ .combos = ([_][]const usize{ p1, p2 })[0..] });
+ } else if (std.mem.eql(u8, line[0..3], "11:")) {
+ const p1: []const usize = ([_]usize{ 42, 31 })[0..];
+ const p2: []const usize = ([_]usize{ 42, 11, 31 })[0..];
+ try rules.put(11, Rule{ .combos = ([_][]const usize{ p1, p2 })[0..] });
+ } else {
+ try parseRule(allocator, &rules, line);
+ }
+ }
+
+ var answer: u32 = 0;
+ var nextstack = std.ArrayList(usize).init(allocator);
+ defer nextstack.deinit();
+
+ stacktrace = std.ArrayList(usize).init(allocator);
+ defer stacktrace.deinit();
+
+ var count: usize = 0;
+ lineit = std.mem.tokenize(u8, try aoc.unwrap(partit.next()), "\n");
+ while (lineit.next()) |line| {
+ count += 1;
+ const valid = try checkRule(&rules, 0, line, &nextstack);
+ answer += @boolToInt(valid);
+ if (aoc.debug) {
+ aoc.debugfmt("TRACE: [", .{});
+ std.mem.reverse(usize, stacktrace.items);
+ printSlice(stacktrace.items);
+ aoc.debugfmt("]\n", .{});
+ if (valid) {
+ aoc.debugfmt("MATCH {s}\n\n", .{line});
+ } else {
+ aoc.debugfmt("NO MATCH {s}\n\n", .{line});
+ }
+ }
+ try nextstack.resize(0);
+ }
+
+ return try std.fmt.allocPrint(allocator, "{}", .{answer});
+}
+
+pub const main = aoc.main(part1, part2, .{ "134", "377" });
diff --git a/src/day19/part1 b/src/19/part1
diff --git a/src/day19/part2 b/src/19/part2
diff --git a/src/day19/trace b/src/19/trace
diff --git a/src/day20/input b/src/20/input
diff --git a/src/day20/input-test b/src/20/input-test
diff --git a/src/day20/input-test2 b/src/20/input-test2
diff --git a/src/20/main.zig b/src/20/main.zig
@@ -0,0 +1,470 @@
+const std = @import("std");
+const aoc = @import("aoc");
+
+const tile_width: u32 = 10;
+const Tile = struct {
+ id: u32,
+ data: [tile_width * tile_width]u1,
+ sides: [4][tile_width]u1, // NOTE: update these values when placed accordingly
+ adj: [4]?usize,
+ pos: aoc.Pos,
+};
+const Flip = enum { NONE, HOR, VERT };
+const flips = [_]Flip{ Flip.NONE, Flip.HOR, Flip.VERT };
+
+const seamonster = [_][]const u8{
+ " # ",
+ "# ## ## ###",
+ " # # # # # # ",
+};
+
+const dirs = [4]aoc.Pos{
+ aoc.Pos{ .x = 0, .y = -1 },
+ aoc.Pos{ .x = 1, .y = 0 },
+ aoc.Pos{ .x = 0, .y = 1 },
+ aoc.Pos{ .x = -1, .y = 0 },
+};
+
+fn printGrid(tiles: []Tile, grid: []?usize, grid_width: u32) void {
+ var y: u32 = 0;
+ while (y < grid_width * tile_width) : (y += 1) {
+ var x: u32 = 0;
+ if (y > 0 and y % tile_width == 0) aoc.debugfmt("\n", .{});
+ while (x < grid_width * tile_width) : (x += 1) {
+ if (x > 0 and x % tile_width == 0) aoc.debugfmt(" ", .{});
+ var tile_index: ?usize = grid[@divFloor(y, tile_width) * grid_width + @divFloor(x, tile_width)];
+ if (tile_index != null) {
+ var tile = tiles[tile_index.?];
+ var c: u8 = if (tile.data[(y % tile_width) * tile_width + (x % tile_width)] == 1) '#' else '.';
+ aoc.debugfmt("{c}", .{c});
+ } else {
+ aoc.debugfmt("?", .{});
+ }
+ }
+ aoc.debugfmt("\n", .{});
+ }
+ aoc.debugfmt("\n\n", .{});
+}
+
+fn printTile(data: []u1, width: u32) void {
+ var y: u32 = 0;
+ while (y < width) : (y += 1) {
+ printTileSlice(data[y * width .. (y + 1) * width]);
+ aoc.debugfmt("\n", .{});
+ }
+}
+
+fn printTileSlice(slice: []const u1) void {
+ var i: u32 = 0;
+ while (i < slice.len) : (i += 1) {
+ var c: u8 = if (slice[i] == 1) '#' else '.';
+ aoc.debugfmt("{c}", .{c});
+ }
+}
+
+fn couldMatch(side1: [tile_width]u1, side2: [tile_width]u1) bool {
+ var side1_cpy = side1;
+ if (std.mem.eql(u1, side1_cpy[0..], side2[0..])) return true;
+ std.mem.reverse(u1, side1_cpy[0..]);
+ if (std.mem.eql(u1, side1_cpy[0..], side2[0..])) return true;
+ return false;
+}
+
+fn parseTiles(tiles: *std.ArrayList(Tile), input: []u8) !void {
+ var tileit = std.mem.split(u8, input, "\n\n");
+ while (tileit.next()) |tilestr| {
+ if (tilestr.len <= 1) continue;
+ var tile: Tile = undefined;
+ var lineit = std.mem.tokenize(u8, tilestr, "\n");
+
+ // read tile id
+ var numstr = (try aoc.unwrap(lineit.next()))[5..9];
+ tile.id = try std.fmt.parseInt(u32, numstr, 10);
+
+ // read tile data
+ var i: u32 = 0;
+ var line: []const u8 = undefined;
+ while (i < tile_width * tile_width) : (i += 1) {
+ if (i % tile_width == 0) line = try aoc.unwrap(lineit.next());
+ tile.data[i] = @boolToInt(line[i % tile_width] == '#');
+ }
+
+ // read side bits
+ i = 0;
+ while (i < 4) : (i += 1) {
+ var sidebits: [tile_width]u1 = undefined;
+ for (sidebits) |_, k| {
+ sidebits[k] = switch (i) {
+ @enumToInt(aoc.Dir.Name.NORTH) => tile.data[k],
+ @enumToInt(aoc.Dir.Name.WEST) => tile.data[(tile_width - 1 - k) * tile_width],
+ @enumToInt(aoc.Dir.Name.EAST) => tile.data[tile_width - 1 + k * tile_width],
+ @enumToInt(aoc.Dir.Name.SOUTH) => tile.data[tile_width * tile_width - 1 - k],
+ else => unreachable,
+ };
+ }
+ tile.sides[i] = sidebits;
+ }
+
+ // init misc data
+ tile.adj = [_]?usize{ null, null, null, null };
+
+ try tiles.append(tile);
+ }
+}
+
+fn matchTiles(tiles: *std.ArrayList(Tile)) void {
+ // for each items's side, look for another item with a matching side
+ for (tiles.items) |*tile, tile_index| {
+ sides_loop: for (tile.sides) |_, i| {
+ for (tiles.items) |*otile, otile_index| {
+ if (tile_index == otile_index) continue;
+
+ for (otile.sides) |_, oi| {
+ if (tile.adj[i] == null and otile.adj[oi] == null and couldMatch(tile.sides[i], otile.sides[oi])) {
+ tile.adj[i] = otile_index;
+ otile.adj[oi] = tile_index;
+ continue :sides_loop;
+ }
+ }
+ }
+ }
+
+ if (aoc.debug) {
+ aoc.debugfmt("{}:\nSIDES ", .{tile.id});
+ for (tile.sides) |side| {
+ for (side) |b| {
+ var c: u8 = if (b == 1) '#' else '.';
+ aoc.debugfmt("{c}", .{c});
+ }
+ aoc.debugfmt(" ", .{});
+ }
+ aoc.debugfmt("\n", .{});
+ for (tile.adj) |adj, i| {
+ if (tile.adj[i] == null) {
+ aoc.debugfmt("null ", .{});
+ } else {
+ var adjtile = tiles.items[adj.?];
+ aoc.debugfmt("{} ", .{adjtile.id});
+ }
+ }
+ aoc.debugfmt("\n\n", .{});
+ }
+ }
+}
+
+fn checkSides(tiles: []Tile, grid: []?usize, grid_width: u32, p: aoc.Pos, adj: [4]?usize, sides: [4][10]u1) bool {
+ var rot: u32 = 0;
+ while (rot < 4) : (rot += 1) {
+ const np = p.add(dirs[rot]);
+ aoc.debugfmt("{}\n", .{@intToEnum(aoc.Dir.Name, @intCast(u2, rot))});
+ aoc.debugfmt("{} {}\n", .{ np.x, np.y });
+
+ if (np.x < 0 or np.x >= grid_width or np.y < 0 or np.y >= grid_width) {
+ aoc.debugfmt("Side is null\n", .{});
+ if (adj[rot] == null) {
+ continue;
+ } else {
+ aoc.debugfmt("Side {} should be NULL!\n", .{@intToEnum(aoc.Dir.Name, @intCast(u2, rot))});
+ return false;
+ }
+ }
+
+ var ti: ?usize = grid[@intCast(u32, np.y * @intCast(i64, grid_width) + np.x)];
+ if (ti == null) continue;
+
+ var otherside = tiles[ti.?].sides[aoc.Dir.nextCW(rot, 2)];
+ std.mem.reverse(u1, otherside[0..]);
+ printTileSlice(otherside[0..]);
+ aoc.debugfmt(" vs ", .{});
+ printTileSlice(sides[rot][0..]);
+ aoc.debugfmt("\n", .{});
+
+ if (!std.mem.eql(u1, otherside[0..], sides[rot][0..])) return false;
+ }
+ return true;
+}
+
+fn rotateData(newdata: *[]u1, olddata: []u1, width: u32, rot: usize) void {
+ for (olddata) |v, di| {
+ const dy = @divFloor(di, width);
+ const dx = di % width;
+ var nx = dx;
+ var ny = dy;
+ switch (rot) {
+ @enumToInt(aoc.Dir.Name.NORTH) => {},
+ @enumToInt(aoc.Dir.Name.EAST) => {
+ nx = width - 1 - dy;
+ ny = dx;
+ },
+ @enumToInt(aoc.Dir.Name.SOUTH) => {
+ nx = width - 1 - dx;
+ ny = width - 1 - dy;
+ },
+ @enumToInt(aoc.Dir.Name.WEST) => {
+ nx = dy;
+ ny = width - 1 - dx;
+ },
+ else => {},
+ }
+ newdata.*[ny * width + nx] = v;
+ }
+}
+
+fn flipData(data: []u1, width: u32, flip: Flip) void {
+ switch (flip) {
+ Flip.HOR => {
+ var y: u32 = 0;
+ while (y < width) : (y += 1) {
+ std.mem.reverse(u1, data[y * width .. (y + 1) * width]);
+ }
+ },
+ Flip.VERT => {
+ var x: u32 = 0;
+ while (x < width) : (x += 1) {
+ var y: u32 = 0;
+ while (y < width / 2) : (y += 1) {
+ std.mem.swap(u1, &data[x + y * width], &data[x + (width - 1 - y) * width]);
+ }
+ }
+ },
+ else => {},
+ }
+}
+
+fn manipulateAndPlace(allocator: std.mem.Allocator, tiles: []Tile, grid: []?usize, grid_width: u32, p: aoc.Pos, tile_index: usize) !void {
+ var tile = &tiles[tile_index];
+
+ for (dirs) |_, rot| {
+ for (flips) |flip| {
+ // apply manipulation to only sides first for checking
+ var sides = tile.sides;
+ var tmp_sides = tile.sides;
+ var adj = tile.adj;
+ var tmp_adj = tile.adj;
+ switch (flip) {
+ Flip.HOR => {
+ std.mem.reverse(u1, tmp_sides[@enumToInt(aoc.Dir.Name.NORTH)][0..]);
+ std.mem.reverse(u1, tmp_sides[@enumToInt(aoc.Dir.Name.SOUTH)][0..]);
+ tmp_sides[@enumToInt(aoc.Dir.Name.WEST)] = sides[@enumToInt(aoc.Dir.Name.EAST)];
+ tmp_sides[@enumToInt(aoc.Dir.Name.EAST)] = sides[@enumToInt(aoc.Dir.Name.WEST)];
+ std.mem.reverse(u1, tmp_sides[@enumToInt(aoc.Dir.Name.EAST)][0..]);
+ std.mem.reverse(u1, tmp_sides[@enumToInt(aoc.Dir.Name.WEST)][0..]);
+ std.mem.swap(?usize, &adj[@enumToInt(aoc.Dir.Name.EAST)], &adj[@enumToInt(aoc.Dir.Name.WEST)]);
+ },
+ Flip.VERT => {
+ std.mem.reverse(u1, tmp_sides[@enumToInt(aoc.Dir.Name.WEST)][0..]);
+ std.mem.reverse(u1, tmp_sides[@enumToInt(aoc.Dir.Name.EAST)][0..]);
+ tmp_sides[@enumToInt(aoc.Dir.Name.NORTH)] = sides[@enumToInt(aoc.Dir.Name.SOUTH)];
+ tmp_sides[@enumToInt(aoc.Dir.Name.SOUTH)] = sides[@enumToInt(aoc.Dir.Name.NORTH)];
+ std.mem.reverse(u1, tmp_sides[@enumToInt(aoc.Dir.Name.NORTH)][0..]);
+ std.mem.reverse(u1, tmp_sides[@enumToInt(aoc.Dir.Name.SOUTH)][0..]);
+ std.mem.swap(?usize, &adj[@enumToInt(aoc.Dir.Name.NORTH)], &adj[@enumToInt(aoc.Dir.Name.SOUTH)]);
+ },
+ else => {},
+ }
+ sides = tmp_sides;
+
+ for (dirs) |_, i| {
+ tmp_sides[i] = sides[aoc.Dir.nextCCW(i, rot)];
+ tmp_adj[i] = adj[aoc.Dir.nextCCW(i, rot)];
+ }
+
+ aoc.debugfmt("\nROT: {}\n", .{rot});
+ aoc.debugfmt("FLIP: {}\n", .{flip});
+ aoc.debugfmt("SIDES: \n", .{});
+ for (tmp_sides) |side| {
+ printTileSlice(side[0..]);
+ aoc.debugfmt("\n", .{});
+ }
+ const valid = checkSides(tiles, grid, grid_width, p, tmp_adj, tmp_sides);
+
+ // now apply manipulations to image data
+ if (valid) {
+ // for (tile.sides) |side| {
+ // printTileSlice(side[0..]);
+ // aoc.debugfmt("\n", .{});
+ // }
+ aoc.debugfmt("{} {} {}\n", .{ tile.id, flip, rot });
+ printTile(tile.data[0..], tile_width);
+ aoc.debugfmt("\n", .{});
+ tile.sides = tmp_sides;
+ tile.pos = p;
+ tile.adj = tmp_adj;
+ grid[@intCast(u32, p.y * @intCast(i64, grid_width) + p.x)] = tile_index;
+
+ flipData(tile.data[0..], tile_width, flip);
+
+ var newdata = try allocator.alloc(u1, tile_width * tile_width);
+ defer allocator.free(newdata);
+
+ rotateData(&newdata, tile.data[0..], tile_width, rot);
+ std.mem.copy(u1, tile.data[0..], newdata);
+ return;
+ }
+ }
+ }
+ return aoc.Error.InvalidInput;
+}
+
+fn part1(allocator: std.mem.Allocator, input: []u8, args: [][]u8) !?[]u8 {
+ _ = args;
+
+ var tiles = std.ArrayList(Tile).init(allocator);
+ defer tiles.deinit();
+
+ try parseTiles(&tiles, input);
+
+ matchTiles(&tiles);
+
+ var answer: u64 = 1;
+ for (tiles.items) |tile| {
+ var unknown: u32 = 0;
+ for (tile.adj) |v| {
+ unknown += @boolToInt(v == null);
+ }
+ if (unknown == 2) answer *= tile.id;
+ }
+
+ return try std.fmt.allocPrint(allocator, "{}", .{answer});
+}
+
+fn part2(allocator: std.mem.Allocator, input: []u8, args: [][]u8) !?[]u8 {
+ _ = args;
+
+ var tiles = std.ArrayList(Tile).init(allocator);
+ defer tiles.deinit();
+
+ try parseTiles(&tiles, input);
+
+ matchTiles(&tiles);
+
+ var grid = try allocator.alloc(?usize, tiles.items.len);
+ std.mem.set(?usize, grid, null);
+ defer allocator.free(grid);
+ var grid_width = @intCast(u32, std.math.sqrt(tiles.items.len));
+
+ var left = std.ArrayList(usize).init(allocator);
+ defer left.deinit();
+
+ for (tiles.items) |_, tile_index| {
+ try left.append(tile_index);
+ }
+
+ // add a corner as first item to add onto
+ for (tiles.items) |tile, tile_index| {
+ var unknown: u32 = 0;
+ for (tile.adj) |v| {
+ unknown += @boolToInt(v == null);
+ }
+ if (unknown == 2) {
+ try manipulateAndPlace(allocator, tiles.items, grid, grid_width, aoc.Pos{ .x = 0, .y = 0 }, tile_index);
+ _ = left.swapRemove(tile_index);
+ break;
+ }
+ }
+
+ // find adjacents and manipulate until they fit
+ next_tile: while (left.items.len > 0) {
+ if (aoc.debug) printGrid(tiles.items, grid, grid_width);
+
+ for (grid) |_, gi| {
+ aoc.debugfmt("POS {}\n", .{gi});
+ const tile_index: ?usize = grid[gi] orelse continue;
+ aoc.debugfmt("POS {} YES\n", .{gi});
+
+ var placed = &tiles.items[tile_index.?];
+ for (placed.adj) |want, dir| {
+ if (want == null) continue;
+ // aoc.debugfmt("LOOKING FOR {}\n", .{want.?});
+ // for (left.items) |item| {
+ // aoc.debugfmt("> {}\n", .{item});
+ // }
+ if (std.mem.indexOfScalar(usize, left.items, want.?)) |left_index| {
+ const new_index = left.items[left_index];
+ const new_tile = tiles.items[new_index];
+ var npos = placed.pos.add(dirs[dir]);
+ aoc.debugfmt("TRYING TO PLACE {} NEW AT: {} {}\n", .{ new_tile.id, npos.x, npos.y });
+
+ try manipulateAndPlace(allocator, tiles.items, grid, grid_width, npos, new_index);
+
+ _ = left.swapRemove(left_index);
+ continue :next_tile;
+ }
+ }
+ }
+ return aoc.Error.InvalidInput;
+ }
+
+ if (aoc.debug) printGrid(tiles.items, grid, grid_width);
+
+ // convert grid to image
+ var image = try allocator.alloc(u1, grid.len * (tile_width - 2) * (tile_width - 2));
+ defer allocator.free(image);
+
+ const image_width = grid_width * (tile_width - 2);
+ var y: u32 = 0;
+ while (y < grid_width) : (y += 1) {
+ var x: u32 = 0;
+ while (x < grid_width) : (x += 1) {
+ var tile = tiles.items[grid[y * grid_width + x].?];
+ var doff = (y * grid_width * (tile_width - 2) + x) * (tile_width - 2);
+ var dy: u32 = 1;
+ while (dy < tile_width - 1) : (dy += 1) {
+ var dx: u32 = 1;
+ while (dx < tile_width - 1) : (dx += 1) {
+ image[doff + (dy - 1) * image_width + (dx - 1)] = tile.data[dy * tile_width + dx];
+ }
+ }
+ }
+ }
+
+ y = 0;
+ while (y < grid_width * (tile_width - 2)) : (y += 1) {
+ printTileSlice(image[y * grid_width * (tile_width - 2) .. (y + 1) * grid_width * (tile_width - 2)]);
+ aoc.debugfmt("\n", .{});
+ }
+
+ // rotate image till we find a sea monster
+ var image_copy = try allocator.dupe(u1, image);
+ defer allocator.free(image_copy);
+
+ var rot: usize = 0;
+ while (rot < 4) : (rot += 1) {
+ for (flips) |flip| {
+ flipData(image, image_width, flip);
+ rotateData(&image_copy, image, image_width, rot);
+
+ y = 0;
+ var count: u32 = 0;
+ while (y < image_width - seamonster.len) : (y += 1) {
+ var x: u32 = 0;
+ check_next: while (x < image_width - seamonster[0].len) : (x += 1) {
+ var sy: u32 = 0;
+ while (sy < seamonster.len) : (sy += 1) {
+ var sx: u32 = 0;
+ while (sx < seamonster[0].len) : (sx += 1) {
+ if (seamonster[sy][sx] == '#' and image_copy[(y + sy) * image_width + (x + sx)] != 1)
+ continue :check_next;
+ }
+ }
+ count += 1;
+ }
+ }
+
+ if (count > 0) {
+ var image_count = std.mem.count(u1, image_copy, ([_]u1{1})[0..]);
+ var seamonster_count: usize = 0;
+ var sy: u32 = 0;
+ while (sy < seamonster.len) : (sy += 1) {
+ seamonster_count += std.mem.count(u8, seamonster[sy], "#");
+ }
+ const answer = image_count - count * seamonster_count;
+ return try std.fmt.allocPrint(allocator, "{}", .{answer});
+ }
+ }
+ }
+
+ return null;
+}
+
+pub const main = aoc.main(part1, part2, .{ "54755174472007", "1692" });
diff --git a/src/day20/part1 b/src/20/part1
diff --git a/src/day20/part2 b/src/20/part2
diff --git a/src/day21/input b/src/21/input
diff --git a/src/day21/input-test b/src/21/input-test
diff --git a/src/21/main.zig b/src/21/main.zig
@@ -0,0 +1,188 @@
+const std = @import("std");
+const aoc = @import("aoc");
+
+const hasher = std.hash.CityHash32;
+const IngredientInfo = struct {
+ count: u32,
+};
+const Pair = struct { ingredient: []const u8, allergen: []const u8 };
+
+fn freeListmap(listmap: *std.AutoHashMap(u32, std.ArrayList(u32))) void {
+ var mapit = listmap.iterator();
+ while (mapit.next()) |kv| {
+ kv.value_ptr.deinit();
+ }
+ listmap.deinit();
+}
+
+fn getAllergen(allergens: *std.AutoHashMap(u32, std.ArrayList(u32)), ingredient: u32) ?u32 {
+ var allergenit = allergens.iterator();
+ while (allergenit.next()) |alg| {
+ if (alg.value_ptr.items.len == 1 and alg.value_ptr.items[0] == ingredient)
+ return alg.key_ptr.*;
+ }
+ return null;
+}
+
+fn updateAllergens(allocator: std.mem.Allocator, allergens: *std.AutoHashMap(u32, std.ArrayList(u32)), allergen: u32) !void {
+ var next = std.ArrayList(u32).init(allocator);
+ defer next.deinit();
+
+ try next.append(allergen);
+
+ while (next.items.len > 0) {
+ const key = next.items[0];
+ var ingredient = allergens.getEntry(key).?.value_ptr.items[0];
+ var mapit = allergens.iterator();
+ while (mapit.next()) |alg| {
+ if (alg.key_ptr.* == key) continue;
+ const ind = std.mem.indexOfScalar(u32, alg.value_ptr.items, ingredient);
+ if (ind != null) {
+ _ = alg.value_ptr.swapRemove(ind.?);
+ if (alg.value_ptr.items.len == 1) {
+ try next.append(alg.key_ptr.*);
+ }
+ }
+ }
+ _ = next.swapRemove(0);
+ }
+}
+
+fn parseAllergens(allocator: std.mem.Allocator, allergens: *std.AutoHashMap(u32, std.ArrayList(u32)), unhash: *std.AutoHashMap(u32, []const u8), ingredient_counts: *std.AutoHashMap(u32, u32), input: []const u8) !void {
+ var ingredients = std.ArrayList(u32).init(allocator);
+ defer ingredients.deinit();
+
+ var lineit = std.mem.tokenize(u8, input, "\n");
+ while (lineit.next()) |line| {
+ var allergen = false;
+
+ try ingredients.resize(0);
+
+ var spaceit = std.mem.tokenize(u8, line, " ");
+ while (spaceit.next()) |word| {
+ if (std.mem.eql(u8, word, "(contains")) {
+ allergen = true;
+ continue;
+ }
+
+ if (allergen) {
+ const allergen_name = if (word[word.len - 1] == ')' or word[word.len - 1] == ',') word[0 .. word.len - 1] else word;
+ const allergen_hash = hasher.hash(allergen_name);
+ try unhash.put(allergen_hash, allergen_name);
+ var algentry = allergens.getEntry(allergen_hash);
+ if (algentry) |algent| {
+ var i: u32 = 0;
+ while (i < algent.value_ptr.items.len) {
+ if (std.mem.indexOfScalar(u32, ingredients.items, algent.value_ptr.items[i]) == null) {
+ _ = algent.value_ptr.swapRemove(i);
+ } else {
+ i += 1;
+ }
+ }
+
+ if (algent.value_ptr.items.len == 1) {
+ try updateAllergens(allocator, allergens, algent.key_ptr.*);
+ }
+ } else {
+ var copy = std.ArrayList(u32).init(allocator);
+ errdefer copy.deinit();
+ for (ingredients.items) |ing| {
+ if (getAllergen(allergens, ing) == null) {
+ try copy.append(ing);
+ }
+ }
+ try allergens.put(allergen_hash, copy);
+ }
+ } else {
+ const ingredient_hash = hasher.hash(word);
+ try unhash.put(ingredient_hash, word);
+ try ingredients.append(ingredient_hash);
+ const entry = ingredient_counts.getEntry(ingredient_hash);
+ if (entry == null) {
+ try ingredient_counts.put(ingredient_hash, 1);
+ } else {
+ entry.?.value_ptr.* += 1;
+ }
+ }
+ }
+ }
+}
+
+fn ascendingAllergen(ctx: void, p1: Pair, p2: Pair) bool {
+ _ = ctx;
+ var i: u32 = 0;
+ while (i < std.math.min(p1.allergen.len, p2.allergen.len) and p1.allergen[i] == p2.allergen[i]) : (i += 1) {}
+ return p1.allergen[i] < p2.allergen[i];
+}
+
+fn part1(allocator: std.mem.Allocator, input: []u8, args: [][]u8) !?[]u8 {
+ _ = args;
+
+ var allergens = std.AutoHashMap(u32, std.ArrayList(u32)).init(allocator);
+ defer freeListmap(&allergens);
+
+ var ingredient_counts = std.AutoHashMap(u32, u32).init(allocator);
+ defer ingredient_counts.deinit();
+
+ var unhash = std.AutoHashMap(u32, []const u8).init(allocator);
+ defer unhash.deinit();
+
+ try parseAllergens(allocator, &allergens, &unhash, &ingredient_counts, input);
+
+ var answer: u32 = 0;
+
+ var algit = allergens.iterator();
+ while (algit.next()) |alg| {
+ aoc.debugfmt("{} - ", .{alg.key_ptr.*});
+ for (alg.value_ptr.items) |v| {
+ aoc.debugfmt("{} ", .{v});
+ }
+ aoc.debugfmt("\n", .{});
+ }
+
+ var mapit = ingredient_counts.iterator();
+ while (mapit.next()) |kv| {
+ if (getAllergen(&allergens, kv.key_ptr.*) == null) answer += kv.value_ptr.*;
+ }
+
+ return try std.fmt.allocPrint(allocator, "{}", .{answer});
+}
+
+fn part2(allocator: std.mem.Allocator, input: []u8, args: [][]u8) !?[]u8 {
+ _ = args;
+
+ var allergens = std.AutoHashMap(u32, std.ArrayList(u32)).init(allocator);
+ defer freeListmap(&allergens);
+
+ var ingredient_counts = std.AutoHashMap(u32, u32).init(allocator);
+ defer ingredient_counts.deinit();
+
+ var unhash = std.AutoHashMap(u32, []const u8).init(allocator);
+ defer unhash.deinit();
+
+ try parseAllergens(allocator, &allergens, &unhash, &ingredient_counts, input);
+
+ var pairs = std.ArrayList(Pair).init(allocator);
+ defer pairs.deinit();
+
+ var mapit = ingredient_counts.iterator();
+ while (mapit.next()) |kv| {
+ const alg = getAllergen(&allergens, kv.key_ptr.*);
+ if (alg != null) {
+ try pairs.append(Pair{ .ingredient = unhash.get(kv.key_ptr.*).?, .allergen = unhash.get(alg.?).? });
+ }
+ }
+
+ std.sort.sort(Pair, pairs.items, {}, ascendingAllergen);
+
+ var parts = std.ArrayList([]const u8).init(allocator);
+ defer parts.deinit();
+ for (pairs.items) |p, i| {
+ if (i > 0) try parts.append(",");
+ try parts.append(p.ingredient);
+ }
+ return try std.mem.join(allocator, "", parts.items);
+}
+
+const sol2 = "fqhpsl,zxncg,clzpsl,zbbnj,jkgbvlxh,dzqc,ppj,glzb";
+pub const main = aoc.main(part1, part2, .{ "2584", sol2 });
diff --git a/src/day21/part1 b/src/21/part1
diff --git a/src/day21/part2 b/src/21/part2
diff --git a/src/day22/input b/src/22/input
diff --git a/src/day22/input-test b/src/22/input-test
diff --git a/src/day22/input-test2 b/src/22/input-test2
diff --git a/src/22/main.zig b/src/22/main.zig
@@ -0,0 +1,181 @@
+const std = @import("std");
+const aoc = @import("aoc");
+
+const Player = enum { P1, P2 };
+const GameResult = struct { score: u64, winner: Player };
+
+fn parseInput(input: []u8, decks: [2]*std.ArrayList(u32)) !void {
+ var partit = std.mem.split(u8, input, "\n\n");
+ var decknum: u32 = 0;
+ while (partit.next()) |part| : (decknum += 1) {
+ if (decknum == 2) break;
+ var lineit = std.mem.tokenize(u8, part, "\n");
+ _ = lineit.next();
+ while (lineit.next()) |line| {
+ try decks[decknum].append(try std.fmt.parseInt(u32, line, 10));
+ }
+ }
+ if (decknum < 2) return aoc.Error.InvalidInput;
+}
+
+fn printDeck(deck: *std.ArrayList(u32)) void {
+ for (deck.items) |v, i| {
+ if (i > 0) aoc.debugfmt(", ", .{});
+ aoc.debugfmt("{}", .{v});
+ }
+}
+
+fn printRoundInfo(roundnum: u32, decks: [2]*std.ArrayList(u32)) void {
+ aoc.debugfmt("\n-- ROUND {} --\n", .{roundnum});
+ aoc.debugfmt("Player 1's deck: ", .{});
+ printDeck(decks[0]);
+ aoc.debugfmt("\nPlayer 2's deck: ", .{});
+ printDeck(decks[1]);
+ aoc.debugfmt("\n", .{});
+}
+
+fn printPickedCards(card1: u32, card2: u32) void {
+ aoc.debugfmt("Player 1 plays: {}\n", .{card1});
+ aoc.debugfmt("Player 2 plays: {}\n", .{card2});
+}
+
+fn calcScore(deck: *std.ArrayList(u32)) u64 {
+ var score: u64 = 0;
+ for (deck.items) |v, i| {
+ score += v * (deck.items.len - i);
+ }
+ return score;
+}
+
+fn copyList(allocator: std.mem.Allocator, list: []u32) !std.ArrayList(u32) {
+ var newlist = std.ArrayList(u32).init(allocator);
+ errdefer newlist.deinit();
+
+ for (list) |v| {
+ try newlist.append(v);
+ }
+
+ return newlist;
+}
+
+fn part1Round(allocator: std.mem.Allocator, roundnum: u32, decks: [2]*std.ArrayList(u32)) anyerror!void {
+ _ = allocator;
+ if (aoc.debug) printRoundInfo(roundnum, decks);
+ const card1: u32 = decks[0].orderedRemove(0);
+ const card2: u32 = decks[1].orderedRemove(0);
+ if (aoc.debug) printPickedCards(card1, card2);
+ if (card1 > card2) {
+ if (aoc.debug) aoc.debugfmt("Player1 wins\n", .{});
+ try decks[0].append(card1);
+ try decks[0].append(card2);
+ } else if (card2 > card1) {
+ if (aoc.debug) aoc.debugfmt("Player2 wins\n", .{});
+ try decks[1].append(card2);
+ try decks[1].append(card1);
+ } else return aoc.Error.InvalidInput;
+}
+
+fn part2Round(
+ allocator: std.mem.Allocator,
+ roundnum: u32,
+ decks: [2]*std.ArrayList(u32),
+) anyerror!void {
+ if (aoc.debug) printRoundInfo(roundnum, decks);
+ const card1: u32 = decks[0].orderedRemove(0);
+ const card2: u32 = decks[1].orderedRemove(0);
+ if (aoc.debug) printPickedCards(card1, card2);
+
+ var winner = @intToEnum(Player, @boolToInt(card2 > card1));
+ if (card1 <= decks[0].items.len and card2 <= decks[1].items.len) {
+ if (aoc.debug) aoc.debugfmt("\nStarting subgame..\n", .{});
+ var tmp_deck1 = try copyList(allocator, decks[0].items[0..card1]);
+ defer tmp_deck1.deinit();
+
+ var tmp_deck2 = try copyList(allocator, decks[1].items[0..card2]);
+ defer tmp_deck2.deinit();
+
+ const result = try playGame(allocator, [2]*std.ArrayList(u32){ &tmp_deck1, &tmp_deck2 }, part2Round);
+ winner = result.winner;
+ if (aoc.debug) {
+ const wp: u32 = if (winner == Player.P1) 1 else 2;
+ aoc.debugfmt("Player{} wins the subgame\n...anyway, back to previous game\n\n", .{wp});
+ }
+ }
+
+ if (winner == Player.P1) {
+ if (aoc.debug) aoc.debugfmt("Player1 wins the round\n", .{});
+ try decks[0].append(card1);
+ try decks[0].append(card2);
+ } else if (winner == Player.P2) {
+ if (aoc.debug) aoc.debugfmt("Player2 wins the round\n", .{});
+ try decks[1].append(card2);
+ try decks[1].append(card1);
+ } else return aoc.Error.InvalidInput;
+}
+
+fn playGame(
+ allocator: std.mem.Allocator,
+ decks: [2]*std.ArrayList(u32),
+ roundFunc: *const fn (
+ alloc: std.mem.Allocator,
+ num: u32,
+ decks: [2]*std.ArrayList(u32),
+ ) anyerror!void,
+) !GameResult {
+ var ctxstack = std.ArrayList(u64).init(allocator);
+ defer ctxstack.deinit();
+
+ var roundnum: u32 = 1;
+ while (decks[0].items.len > 0 and decks[1].items.len > 0) : (roundnum += 1) {
+ try roundFunc(allocator, roundnum, decks);
+
+ var hash: u64 = calcScore(decks[0]) + 100000 * calcScore(decks[1]);
+ if (std.mem.indexOfScalar(u64, ctxstack.items, hash) != null) {
+ return GameResult{ .score = calcScore(decks[0]), .winner = Player.P1 };
+ }
+
+ try ctxstack.append(hash);
+ }
+
+ var nonempty = if (decks[0].items.len != 0) decks[0] else decks[1];
+ return GameResult{
+ .score = calcScore(nonempty),
+ .winner = if (nonempty == decks[0]) Player.P1 else Player.P2,
+ };
+}
+
+fn part1(allocator: std.mem.Allocator, input: []u8, args: [][]u8) !?[]u8 {
+ _ = args;
+
+ var deck1 = std.ArrayList(u32).init(allocator);
+ defer deck1.deinit();
+
+ var deck2 = std.ArrayList(u32).init(allocator);
+ defer deck2.deinit();
+
+ const decks = [2]*std.ArrayList(u32){ &deck1, &deck2 };
+ try parseInput(input, decks);
+
+ const result = try playGame(allocator, decks, part1Round);
+
+ return try std.fmt.allocPrint(allocator, "{}", .{result.score});
+}
+
+fn part2(allocator: std.mem.Allocator, input: []u8, args: [][]u8) !?[]u8 {
+ _ = args;
+
+ var deck1 = std.ArrayList(u32).init(allocator);
+ defer deck1.deinit();
+
+ var deck2 = std.ArrayList(u32).init(allocator);
+ defer deck2.deinit();
+
+ const decks = [2]*std.ArrayList(u32){ &deck1, &deck2 };
+ try parseInput(input, decks);
+
+ const result = try playGame(allocator, decks, part2Round);
+
+ return try std.fmt.allocPrint(allocator, "{}", .{result.score});
+}
+
+pub const main = aoc.main(part1, part2, .{ "32272", "33206" });
diff --git a/src/day22/part1 b/src/22/part1
diff --git a/src/day22/part2 b/src/22/part2
diff --git a/src/day23/input b/src/23/input
diff --git a/src/day23/input-test b/src/23/input-test
diff --git a/src/23/main.zig b/src/23/main.zig
@@ -0,0 +1,194 @@
+const std = @import("std");
+const aoc = @import("aoc");
+
+// Links in this list are arranges in a circle
+const RingLink = struct {
+ data: u32,
+ next: *RingLink,
+ const Self = @This();
+
+ pub fn insertNext(self: *Self, link: *RingLink) void {
+ link.next = self.next;
+ self.next = link;
+ }
+
+ pub fn popNext(self: *Self) !*Self {
+ const nlink = self.next;
+ if (nlink == self) return error.EmptyRingList;
+ self.next = nlink.next;
+ return nlink;
+ }
+
+ pub fn length(self: *Self) usize {
+ var count: usize = 1;
+ var link = self.next;
+ while (link != self) : (link = link.next) {
+ count += 1;
+ }
+ return count;
+ }
+
+ pub fn advance(self: *Self, count: usize) *RingLink {
+ var link = self;
+ var counter: usize = 0;
+ while (counter < count) : (link = link.next) {
+ counter += 1;
+ }
+ return link;
+ }
+};
+
+fn printLinks(start: *RingLink, end: *RingLink, skipfirst: bool) void {
+ var link = start;
+ var b = skipfirst;
+ while (b or link != end) : (link = link.next) {
+ b = false;
+ aoc.debugfmt("{} ", .{link.data});
+ }
+}
+
+fn parseInput(input: []const u8, lookup: []RingLink, list: *?*RingLink) !u32 {
+ var max: u32 = 0;
+ var link: *RingLink = undefined;
+ for (input) |c, i| {
+ if (c == '\n') break;
+ const v = try std.fmt.parseInt(u32, input[i .. i + 1], 10);
+ if (v > max) max = v;
+ if (list.* == null) {
+ list.* = &lookup[v];
+ link = list.*.?;
+ link.next = link;
+ } else {
+ link.insertNext(&lookup[v]);
+ link = link.next;
+ }
+ }
+ return max;
+}
+
+fn doRound(list: *RingLink, len: u32, lookup: []RingLink, current: **RingLink, max: u32, round: usize) !void {
+ _ = list;
+ var target = (current.*.data + max - 2) % max + 1;
+ var k: usize = 0;
+ var check = current.*.next;
+ while (k < 9) : (k += 1) {
+ if (check.data == target)
+ target = (target + max - 2) % max + 1;
+
+ check = if (k % 3 == 0) current.*.next else check.next;
+ }
+ var closest = &lookup[target];
+
+ if (aoc.debug) {
+ aoc.debugfmt("\n-- move {} --\ncups:", .{round});
+
+ if (aoc.debuglvl == 1) {
+ var start = current.*.advance(len - ((round - 1) % len));
+ var link = start;
+ while (true) {
+ if (link == current.*) {
+ aoc.debugfmt(" ({})", .{link.data});
+ } else {
+ aoc.debugfmt(" {} ", .{link.data});
+ }
+ link = link.next;
+ if (link == start) break;
+ }
+ aoc.debugfmt("\n", .{});
+ } else {
+ aoc.debugfmt("\n{} {} {}\n", .{ current.*.data, target, closest.data });
+ aoc.debugfmt(".. ", .{});
+ printLinks(current.*, current.*.next.next.next.next, false);
+ aoc.debugfmt("..\n.. ", .{});
+ printLinks(closest, closest.next.next.next.next, false);
+ aoc.debugfmt("..\n", .{});
+ }
+ }
+
+ var i: usize = 0;
+ while (i < 3) : (i += 1) {
+ const poplink = try current.*.popNext();
+ closest.insertNext(poplink);
+ closest = poplink;
+ }
+
+ current.* = current.*.next;
+}
+
+fn createLookup(allocator: std.mem.Allocator, len: usize) ![]RingLink {
+ var lookup = try allocator.alloc(RingLink, len + 1);
+ errdefer allocator.free(lookup);
+
+ var i: usize = 1;
+ while (i <= len) : (i += 1) {
+ lookup[i] = RingLink{ .data = @intCast(u32, i), .next = undefined };
+ }
+
+ return lookup;
+}
+
+fn part1(allocator: std.mem.Allocator, input: []u8, args: [][]u8) !?[]u8 {
+ _ = args;
+
+ var lookup = try createLookup(allocator, 9);
+ defer allocator.free(lookup);
+
+ var list: ?*RingLink = null;
+ const max = try parseInput(input, lookup, &list);
+ if (list == null) return aoc.Error.InvalidInput;
+ const real_len = @intCast(u32, list.?.length());
+
+ var round: usize = 0;
+ var current = list.?;
+ while (round < 100) : (round += 1) {
+ try doRound(list.?, real_len, lookup, ¤t, max, round + 1);
+ }
+
+ var start = &lookup[1];
+ var link = start.next;
+
+ var parts = std.ArrayList(u8).init(allocator);
+ defer parts.deinit();
+ while (link != start) : (link = link.next) {
+ try parts.append('0' + @intCast(u8, link.data));
+ }
+
+ return try std.fmt.allocPrint(allocator, "{s}", .{parts.items});
+}
+
+fn part2(allocator: std.mem.Allocator, input: []u8, args: [][]u8) !?[]u8 {
+ _ = args;
+
+ var lookup = try createLookup(allocator, 1000000);
+ defer allocator.free(lookup);
+
+ var list: ?*RingLink = null;
+ _ = try parseInput(input, lookup, &list);
+ if (list == null) return aoc.Error.InvalidInput;
+ const real_len = list.?.length();
+
+ var end = list.?.advance(real_len - 1);
+ var i = real_len + 1;
+ while (i <= 1000000) : (i += 1) {
+ end.insertNext(&lookup[i]);
+ end = end.next;
+ }
+
+ var round: usize = 0;
+ var current = list.?;
+ while (round < 10000000) : (round += 1) {
+ if (round % 1000000 == 0) aoc.debugfmt(".", .{});
+ try doRound(list.?, 1000000, lookup, ¤t, 1000000, round + 1);
+ }
+ aoc.debugfmt("\n", .{});
+
+ var link = (&lookup[1]).next;
+
+ const a = @intCast(u64, link.data);
+ const b = @intCast(u64, link.next.data);
+ aoc.debugfmt("{} * {} = {}\n", .{ a, b, a * b });
+
+ return try std.fmt.allocPrint(allocator, "{}", .{a * b});
+}
+
+pub const main = aoc.main(part1, part2, .{ "97245386", "156180332979" });
diff --git a/src/day23/notes b/src/23/notes
diff --git a/src/day23/part1 b/src/23/part1
diff --git a/src/day23/part2 b/src/23/part2
diff --git a/src/day24/input b/src/24/input
diff --git a/src/day24/input-test b/src/24/input-test
diff --git a/src/24/main.zig b/src/24/main.zig
@@ -0,0 +1,125 @@
+const std = @import("std");
+const aoc = @import("aoc");
+
+const Color = enum { BLACK, WHITE };
+const Dir = enum { E, SE, SW, W, NW, NE };
+const dirs = [_]aoc.Pos{
+ aoc.Pos{ .x = 2, .y = 0 },
+ aoc.Pos{ .x = 1, .y = -1 },
+ aoc.Pos{ .x = -1, .y = -1 },
+ aoc.Pos{ .x = -2, .y = 0 },
+ aoc.Pos{ .x = -1, .y = 1 },
+ aoc.Pos{ .x = 1, .y = 1 },
+};
+const tokens = [_][]const u8{
+ "e",
+ "se",
+ "sw",
+ "w",
+ "nw",
+ "ne",
+};
+const Tile = struct {
+ color: Color,
+};
+
+fn parseInput(tiles: *std.AutoHashMap(aoc.Pos, Tile), input: []const u8) !void {
+ var lineit = std.mem.tokenize(u8, input, "\n");
+ while (lineit.next()) |line| {
+ var pos = aoc.Pos{ .x = 0, .y = 0 };
+
+ var i: usize = 0;
+ while (i < line.len) {
+ var dir = for (tokens) |tok, ti| {
+ if (i + tok.len > line.len) continue;
+ if (std.mem.eql(u8, tok, line[i .. i + tok.len])) {
+ i += tok.len;
+ break @intToEnum(Dir, @intCast(u3, ti));
+ }
+ } else return aoc.Error.InvalidInput;
+ if (aoc.debug) std.debug.print("{} ", .{dir});
+ pos = pos.add(dirs[@enumToInt(dir)]);
+ }
+ if (aoc.debug) std.debug.print("=> {} {}\n", .{ pos.x, pos.y });
+
+ var tile = tiles.getEntry(pos);
+ if (tile != null) {
+ tile.?.value_ptr.color = if (tile.?.value_ptr.color == Color.WHITE) Color.BLACK else Color.WHITE;
+ } else {
+ try tiles.put(pos, Tile{ .color = Color.BLACK });
+ }
+ }
+}
+
+fn applyRule(pos: aoc.Pos, before: *std.AutoHashMap(aoc.Pos, Tile), after: *std.AutoHashMap(aoc.Pos, Tile)) !void {
+ if (after.contains(pos)) return;
+ const old_tile = before.get(pos);
+ const old_color = if (old_tile == null) Color.WHITE else old_tile.?.color;
+
+ var adj: u32 = 0;
+ for (dirs) |d| {
+ const tile = before.get(pos.add(d));
+ if (tile != null and tile.?.color == Color.BLACK) adj += 1;
+ }
+
+ if (adj == 2 and old_color == Color.WHITE) {
+ try after.put(pos, Tile{ .color = Color.BLACK });
+ } else if ((adj == 0 or adj > 2) and old_color == Color.BLACK) {
+ try after.put(pos, Tile{ .color = Color.WHITE });
+ } else {
+ try after.put(pos, Tile{ .color = old_color });
+ }
+}
+
+fn doRound(allocator: std.mem.Allocator, tiles: *std.AutoHashMap(aoc.Pos, Tile)) !void {
+ var result = std.AutoHashMap(aoc.Pos, Tile).init(allocator);
+ defer result.deinit();
+
+ var mapit = tiles.iterator();
+ while (mapit.next()) |kv| {
+ for (dirs) |d| {
+ try applyRule(kv.key_ptr.add(d), tiles, &result);
+ }
+ try applyRule(kv.key_ptr.*, tiles, &result);
+ }
+
+ std.mem.swap(std.AutoHashMap(aoc.Pos, Tile), &result, tiles);
+}
+
+fn countBlack(tiles: *std.AutoHashMap(aoc.Pos, Tile)) u32 {
+ var count: u32 = 0;
+ var mapit = tiles.iterator();
+ while (mapit.next()) |kv| {
+ if (kv.value_ptr.color == Color.BLACK) count += 1;
+ }
+ return count;
+}
+
+fn part1(allocator: std.mem.Allocator, input: []u8, args: [][]u8) !?[]u8 {
+ _ = args;
+
+ var tiles = std.AutoHashMap(aoc.Pos, Tile).init(allocator);
+ defer tiles.deinit();
+
+ try parseInput(&tiles, input);
+
+ return try std.fmt.allocPrint(allocator, "{}", .{countBlack(&tiles)});
+}
+
+fn part2(allocator: std.mem.Allocator, input: []u8, args: [][]u8) !?[]u8 {
+ _ = args;
+
+ var tiles = std.AutoHashMap(aoc.Pos, Tile).init(allocator);
+ defer tiles.deinit();
+
+ try parseInput(&tiles, input);
+
+ var round: usize = 0;
+ while (round < 100) : (round += 1) {
+ try doRound(allocator, &tiles);
+ }
+
+ return try std.fmt.allocPrint(allocator, "{}", .{countBlack(&tiles)});
+}
+
+pub const main = aoc.main(part1, part2, .{ "317", "3804" });
diff --git a/src/day24/part1 b/src/24/part1
diff --git a/src/day24/part2 b/src/24/part2
diff --git a/src/day25/input b/src/25/input
diff --git a/src/day25/input-test b/src/25/input-test
diff --git a/src/25/main.zig b/src/25/main.zig
@@ -0,0 +1,58 @@
+const std = @import("std");
+const aoc = @import("aoc");
+
+fn transform(subject_num: u64, loops: u64) u64 {
+ var num: u64 = 1;
+ var i: u64 = 0;
+ while (i < loops) : (i += 1) {
+ num *= subject_num;
+ num %= 20201227;
+ }
+ return num;
+}
+
+fn bfLoops(subject_num: u64, pubkey: u64) ?u64 {
+ var i: u64 = 0;
+ var tmp: u64 = 1;
+ while (i < ~@as(u64, 0)) : (i += 1) {
+ if (tmp == pubkey) return i;
+ tmp *= subject_num;
+ tmp %= 20201227;
+ }
+ return null;
+}
+
+fn parseInput(door_pubkey: *u64, card_pubkey: *u64, input: []const u8) !void {
+ var lineit = std.mem.tokenize(u8, input, "\n");
+ door_pubkey.* = try std.fmt.parseInt(u64, try aoc.unwrap(lineit.next()), 10);
+ card_pubkey.* = try std.fmt.parseInt(u64, try aoc.unwrap(lineit.next()), 10);
+}
+
+fn part1(allocator: std.mem.Allocator, input: []u8, args: [][]u8) !?[]u8 {
+ var door_pubkey: u64 = undefined;
+ var card_pubkey: u64 = undefined;
+
+ try parseInput(&door_pubkey, &card_pubkey, input);
+
+ if (args.len == 0 or std.mem.eql(u8, args[0], "bf_door")) {
+ if (bfLoops(7, door_pubkey)) |door_loops| {
+ std.debug.print("{}\n", .{transform(card_pubkey, door_loops)});
+ return null;
+ }
+ } else if (args.len > 0 and std.mem.eql(u8, args[0], "bf_card")) {
+ if (bfLoops(7, card_pubkey)) |card_loops| {
+ const answer = transform(door_pubkey, card_loops);
+ return try std.fmt.allocPrint(allocator, "{}", .{answer});
+ }
+ }
+ return null;
+}
+
+fn part2(allocator: std.mem.Allocator, input: []u8, args: [][]u8) !?[]u8 {
+ _ = input;
+ _ = args;
+
+ return try std.fmt.allocPrint(allocator, "", .{});
+}
+
+pub const main = aoc.main(part1, part2, .{ "15217943", "" });
diff --git a/src/day25/part1 b/src/25/part1
diff --git a/src/day25/part2 b/src/25/part2
diff --git a/src/Makefile b/src/Makefile
@@ -0,0 +1,21 @@
+DAYS = $(shell seq 1 25 | xargs printf "%02i\n")
+
+.PHONY: all
+all::
+
+define make-day
+all:: $1/run
+.PHONY: $1/run
+$1/main: $1/main.zig
+ zig build-exe \
+ --pkg-begin "aoc" "common/aoc.zig" --pkg-end \
+ --pkg-begin "console8" "common/console8.zig" --pkg-end \
+ --cache-dir .cache/zig -femit-bin=$1/main -freference-trace \
+ $1/main.zig
+$1/run: $1/main
+ @echo "== day $1 =="
+ @echo -en "\npart 1: " && cd $1 && time ./main 1
+ @echo -en "\npart 2: " && cd $1 && time ./main 2
+ @echo ""
+endef
+$(foreach day,$(DAYS),$(eval $(call make-day,$(day))))
diff --git a/src/common/aoc.zig b/src/common/aoc.zig
@@ -0,0 +1,145 @@
+const std = @import("std");
+
+pub const Error = error{InvalidInput};
+
+pub var debug = false;
+pub var debuglvl: u32 = 0;
+
+pub fn debugfmt(comptime fmt: []const u8, args: anytype) void {
+ if (debug)
+ std.debug.print(fmt, args);
+}
+
+const part_type = fn (alloc: std.mem.Allocator, input: []u8, args: [][]u8) anyerror!?[]u8;
+pub fn main(comptime part1: part_type, comptime part2: part_type, comptime sols: [2]?[]const u8) fn () anyerror!void {
+ const impl = struct {
+ fn main() !void {
+ const envvar = std.os.getenv("AOC_DEBUG");
+ if (envvar != null) {
+ debuglvl = try std.fmt.parseInt(u32, envvar.?, 10);
+ debug = debuglvl != 0;
+ }
+
+ var gpa = std.heap.GeneralPurposeAllocator(.{}){};
+ defer _ = gpa.deinit();
+ var heapalloc = gpa.allocator();
+
+ const args = try std.process.argsAlloc(heapalloc);
+ defer heapalloc.free(args);
+ if (args.len < 2) return;
+
+ var filename: []const u8 = std.mem.span("input");
+ for (std.os.environ) |v| {
+ const kv = std.mem.span(v);
+ if (std.mem.indexOfScalar(u8, kv, '=')) |sep| {
+ if (sep == kv.len - 1) continue;
+ if (std.mem.eql(u8, kv[0..sep], "AOC_INPUT")) {
+ filename = kv[sep + 1 ..];
+ std.debug.print("Using input file: {s}\n", .{filename});
+ break;
+ } else if (std.mem.eql(u8, kv[0..sep], "AOCDEBUG")) {
+ debug = true;
+ debuglvl = try std.fmt.parseInt(u32, kv[sep + 1 ..], 10);
+ }
+ }
+ }
+
+ const file = try std.fs.cwd().openFile(filename, .{});
+ const text = try file.reader().readAllAlloc(heapalloc, std.math.maxInt(u32));
+ defer heapalloc.free(text);
+
+ var part = try std.fmt.parseInt(u8, args[1], 10);
+ var answer: ?[]u8 = null;
+ switch (part) {
+ 1 => answer = try part1(heapalloc, text, args[2..]),
+ 2 => answer = try part2(heapalloc, text, args[2..]),
+ else => {
+ std.debug.print("Invalid part number!\n", .{});
+ std.os.exit(1);
+ },
+ }
+ part = part - 1;
+
+ if (answer != null) {
+ const stdout = std.io.getStdOut().writer();
+ try std.fmt.format(stdout, "{s}\n", .{answer.?});
+ if (sols[part] != null and !std.mem.eql(u8, answer.?, sols[part].?)) {
+ std.debug.print("Invalid answer\n", .{});
+ std.os.exit(1);
+ }
+ heapalloc.free(answer.?);
+ }
+
+ if (sols[part] == null) {
+ std.debug.print("Missing solution\n", .{});
+ std.os.exit(1);
+ }
+ }
+ };
+ return impl.main;
+}
+
+pub const Pos = struct {
+ x: i64,
+ y: i64,
+ const Self = @This();
+
+ pub fn add(self: Self, other: Self) Self {
+ return Self{ .x = self.x + other.x, .y = self.y + other.y };
+ }
+
+ pub fn mult(self: Self, val: i64) Self {
+ return Self{ .x = self.x * val, .y = self.y * val };
+ }
+};
+
+pub const Dir = struct {
+ pub const East = Pos{ .x = 1, .y = 0 };
+ pub const West = Pos{ .x = -1, .y = 0 };
+ pub const South = Pos{ .x = 0, .y = -1 };
+ pub const North = Pos{ .x = 0, .y = 1 };
+
+ pub const Name = enum(u8) { NORTH = 0, EAST = 1, SOUTH = 2, WEST = 3 };
+ pub const dirs = [_]Pos{ North, East, South, West };
+
+ pub fn get(name: Name) Pos {
+ return dirs[@enumToInt(name)];
+ }
+
+ pub fn nextCW(dir: usize, offset: usize) usize {
+ return (dir + @intCast(u32, offset)) % @intCast(u32, dirs.len);
+ }
+
+ pub fn nextCCW(dir: usize, offset: usize) usize {
+ const constrained = offset % dirs.len;
+ if (dir >= constrained) {
+ return dir - constrained;
+ } else {
+ return dirs.len - (constrained - dir);
+ }
+ }
+
+ const cos90vs = [_]i32{ 1, 0, -1, 0 };
+ const sin90vs = [_]i32{ 0, 1, 0, -1 };
+
+ pub fn rotCW(pos: Pos, offset: usize) Pos {
+ const constrained = (4 - offset % 4) % 4;
+ return Pos{
+ .x = cos90vs[constrained] * pos.x - sin90vs[constrained] * pos.y,
+ .y = sin90vs[constrained] * pos.x + cos90vs[constrained] * pos.y,
+ };
+ }
+
+ pub fn rotCCW(pos: Pos, offset: usize) Pos {
+ const constrained = offset % 4;
+ return Pos{
+ .x = cos90vs[constrained] * pos.x - sin90vs[constrained] * pos.y,
+ .y = sin90vs[constrained] * pos.x + cos90vs[constrained] * pos.y,
+ };
+ }
+};
+
+pub fn unwrap(v: anytype) !@TypeOf(v.?) {
+ if (v == null) return Error.InvalidInput;
+ return v.?;
+}
diff --git a/src/common/console8.zig b/src/common/console8.zig
@@ -0,0 +1,91 @@
+const std = @import("std");
+const aoc = @import("aoc.zig");
+
+pub const OpError = error{ InstructionPointerOOB, InvalidFormat, InstructionUnknown };
+pub const OpFuncSig = fn (ctx: *Console, arg: i64) OpError!void;
+pub const Instruction = struct { opcode: []const u8, opfunc: *const OpFuncSig, argval: i64 };
+
+pub const Console = struct {
+ accumulator: i64 = 0,
+ instructptr: u64 = 0,
+
+ jumpAddr: i65 = 0,
+
+ code: []const u8,
+ instlist: [][]const u8,
+ allocator: std.mem.Allocator,
+ const Self = @This();
+
+ pub fn init(code: []const u8, allocator: std.mem.Allocator) !Self {
+ var instvec = std.ArrayList([]const u8).init(allocator);
+ errdefer instvec.deinit();
+
+ var instit = std.mem.tokenize(u8, code, "\n");
+ while (instit.next()) |inst| {
+ try instvec.append(inst);
+ }
+ return Console{
+ .code = code,
+ .instlist = instvec.toOwnedSlice(),
+ .allocator = allocator,
+ };
+ }
+
+ pub fn deinit(self: *Self) void {
+ self.allocator.free(self.instlist);
+ }
+
+ pub fn reset(self: *Self) void {
+ self.accumulator = 0;
+ self.instructptr = 0;
+ }
+
+ const instructionMap = std.ComptimeStringMap(*const OpFuncSig, .{
+ .{ "jmp", jumpInstruction },
+ .{ "acc", accInstruction },
+ .{ "nop", nopInstruction },
+ });
+
+ pub fn jumpInstruction(self: *Self, arg: i64) OpError!void {
+ self.jumpAddr = @intCast(i65, self.instructptr) + @intCast(i65, arg);
+ if (self.jumpAddr < 0 or self.jumpAddr >= self.instlist.len)
+ return error.InstructionPointerOOB;
+ self.instructptr = @intCast(u64, self.jumpAddr);
+ }
+
+ pub fn accInstruction(self: *Self, arg: i64) OpError!void {
+ self.accumulator += arg;
+ self.instructptr += 1;
+ }
+
+ pub fn nopInstruction(self: *Self, arg: i64) OpError!void {
+ _ = arg;
+ self.instructptr += 1;
+ }
+
+ pub fn parseNext(self: *Self) !?Instruction {
+ if (self.instructptr >= self.instlist.len)
+ return null;
+
+ const inststr = self.instlist[self.instructptr];
+ const sep = std.mem.indexOfScalar(u8, inststr, ' ');
+ if (sep == null) return OpError.InvalidFormat;
+
+ const opcode = inststr[0..sep.?];
+ if (instructionMap.get(opcode)) |opfunc| {
+ const arg = inststr[sep.? + 1 ..];
+ const val = std.fmt.parseInt(i64, arg, 10) catch {
+ aoc.debugfmt("Failed to parse arg value: {s}\n", .{arg});
+ return OpError.InvalidFormat;
+ };
+ return Instruction{ .opcode = opcode, .opfunc = opfunc, .argval = val };
+ } else {
+ aoc.debugfmt("Unknown instruction: {s}\n", .{inststr});
+ return OpError.InstructionUnknown;
+ }
+ }
+
+ pub fn exec(self: *Self, inst: *Instruction) !void {
+ try inst.opfunc(self, inst.argval);
+ }
+};
diff --git a/src/day1/main.zig b/src/day1/main.zig
@@ -1,67 +0,0 @@
-const std = @import("std");
-const aoc = @import("aoc");
-
-const Parts = struct {
- a: u32, b: u32
-};
-
-fn findparts(intlist: *const std.ArrayList(u32), sum: u32) ?Parts {
- var start: usize = 0;
- const items = intlist.items;
- var end: usize = items.len - 1;
- while (start != end) {
- const csum = items[start] + items[end];
- if (csum == sum) {
- return Parts{ .a = items[start], .b = items[end] };
- } else if (csum > sum) {
- end -= 1;
- } else {
- start += 1;
- }
- }
- return null;
-}
-
-fn parse(allocator: *std.mem.Allocator, input: []u8) !std.ArrayList(u32) {
- var intlist = std.ArrayList(u32).init(allocator);
- errdefer intlist.deinit();
-
- var it = std.mem.tokenize(input, "\n");
- while (it.next()) |line| {
- try intlist.append(try std.fmt.parseInt(u32, line, 10));
- }
-
- return intlist;
-}
-
-fn part1(allocator: *std.mem.Allocator, input: []u8, args: [][]u8) !void {
- const intlist = try parse(allocator, input);
- defer intlist.deinit();
-
- std.sort.sort(u32, intlist.items, {}, comptime std.sort.asc(u32));
-
- if (findparts(&intlist, 2020)) |parts| {
- std.debug.print("{}\n", .{parts.a * parts.b});
- }
-}
-
-fn part2(allocator: *std.mem.Allocator, input: []u8, args: [][]u8) !void {
- const intlist = try parse(allocator, input);
- defer intlist.deinit();
-
- std.sort.sort(u32, intlist.items, {}, comptime std.sort.asc(u32));
-
- const target: u16 = 2020;
- var third: u32 = 0;
- while (third < intlist.items.len) : (third += 1) {
- const tmp = intlist.items[third];
- intlist.items[third] = target + 1;
- if (findparts(&intlist, target - tmp)) |parts| {
- std.debug.print("{}\n", .{parts.a * parts.b * tmp});
- return;
- }
- intlist.items[third] = tmp;
- }
-}
-
-pub const main = aoc.gen_main(part1, part2);
diff --git a/src/day10/main.zig b/src/day10/main.zig
@@ -1,154 +0,0 @@
-const std = @import("std");
-const aoc = @import("aoc");
-
-fn part1(allocator: *std.mem.Allocator, input: []u8, args: [][]u8) !void {
- var target: u32 = 0;
-
- var intlist = std.ArrayList(u32).init(allocator);
- defer intlist.deinit();
-
- var lineit = std.mem.tokenize(input, "\n");
- while (lineit.next()) |line| {
- var val = try std.fmt.parseInt(u32, line, 10);
- if (val > target) {
- target = val;
- }
- try intlist.append(val);
- }
-
- target += 3;
- try intlist.append(target);
-
- if (intlist.items.len == 0) return;
-
- std.sort.sort(u32, intlist.items, {}, comptime std.sort.asc(u32));
-
- var diffs = [_]u32{ 0, 0, 0, 0 };
- var last: u32 = 0;
- for (intlist.items) |ov| {
- if (ov - last > 3 or ov == last) {
- std.debug.print("Unable to find a suitable adapter for {} output jolts (next: {} jolts)\n", .{ last, ov });
- return aoc.Error.InvalidInput;
- }
- diffs[ov - last] += 1;
- last = ov;
- }
-
- std.debug.print("{}\n", .{diffs[1] * diffs[3]});
-}
-
-fn countArrangements(arrangement: []u32, adapters: []const u32, adaptermask: []u1, target: u32, fillcount: u32, searchstart: u32, count: *u32) void {
- var last: u32 = 0;
- if (fillcount > 0) {
- last = arrangement[fillcount - 1];
- }
-
- if (last == target) {
- count.* += 1;
- return;
- }
-
- for (adapters[searchstart..]) |adap, i| {
- if (adaptermask[searchstart + i] == 1) continue;
- if (adap > last + 3) break;
-
- adaptermask[searchstart + i] = 1;
- arrangement[fillcount] = adap;
- countArrangements(arrangement, adapters, adaptermask, target, fillcount + 1, searchstart + @intCast(u32, i) + 1, count);
- adaptermask[searchstart + i] = 0;
- }
-}
-
-fn part2Recursive(allocator: *std.mem.Allocator, input: []u8, args: [][]u8) !void {
- var target: u32 = 0;
-
- var intlist = std.ArrayList(u32).init(allocator);
- defer intlist.deinit();
-
- var lineit = std.mem.tokenize(input, "\n");
- while (lineit.next()) |line| {
- var val = try std.fmt.parseInt(u32, line, 10);
- if (val > target) {
- target = val;
- }
- try intlist.append(val);
- }
-
- target += 3;
- try intlist.append(target);
-
- if (intlist.items.len == 0) return;
-
- std.sort.sort(u32, intlist.items, {}, comptime std.sort.asc(u32));
-
- var count: u32 = 0;
-
- var arrangements = try allocator.alloc(u32, intlist.items.len);
- defer allocator.free(arrangements);
-
- var adaptermask = try allocator.alloc(u1, intlist.items.len);
- defer allocator.free(adaptermask);
-
- countArrangements(arrangements, intlist.items, adaptermask, target, 0, 0, &count);
-
- std.debug.print("{}\n", .{count});
-}
-
-fn groupPermutations(adapters: []const u32) u64 {
- if (adapters.len == 1) return 1;
- var count: u64 = 0;
- for (adapters) |v, i| {
- if (i == 0) continue;
- if (adapters[i] <= adapters[0] + 3) {
- count += groupPermutations(adapters[i..]);
- }
- }
- return count;
-}
-
-fn part2Iterative(allocator: *std.mem.Allocator, input: []u8, args: [][]u8) !void {
- var target: u32 = 0;
-
- var intlist = std.ArrayList(u32).init(allocator);
- defer intlist.deinit();
-
- try intlist.append(0);
-
- var lineit = std.mem.tokenize(input, "\n");
- while (lineit.next()) |line| {
- var val = try std.fmt.parseInt(u32, line, 10);
- if (val > target) {
- target = val;
- }
- try intlist.append(val);
- }
-
- target += 3;
- try intlist.append(target);
-
- if (intlist.items.len == 0) return aoc.Error.InvalidInput;
-
- std.sort.sort(u32, intlist.items, {}, comptime std.sort.asc(u32));
-
- var gapstart: u32 = 0;
- var multiplier: u128 = 1;
-
- var i: u32 = 0;
- while (i < intlist.items.len - 1) : (i += 1) {
- // whenever we encounter a 3 jolt gap, we can calc permutations of group before
- if (i + 1 < intlist.items.len and intlist.items[i + 1] == intlist.items[i] + 3) {
- multiplier *= groupPermutations(intlist.items[gapstart .. i + 1]);
- std.debug.print("gap from {} to {} => {}\n", .{ intlist.items[i], intlist.items[i + 1], multiplier });
- std.debug.print("group size: {}\n", .{i + 1 - gapstart});
- gapstart = i + 1;
- }
- }
-
- std.debug.print("{}\n", .{multiplier});
-}
-
-fn part2(allocator: *std.mem.Allocator, input: []u8, args: [][]u8) !void {
- try part2Iterative(allocator, input, args);
-}
-
-pub const main = aoc.gen_main(part1, part2);
diff --git a/src/day11/main.zig b/src/day11/main.zig
@@ -1,161 +0,0 @@
-const std = @import("std");
-const aoc = @import("aoc");
-
-const SeatState = enum { EMPTY, FLOOR, TAKEN };
-const MapDims = struct { width: usize, height: usize };
-const Dir = struct { x: i8, y: i8 };
-const Pos = struct { x: i128, y: i128 };
-
-const adjacent = [_]Dir{
- Dir{ .x = -1, .y = -1 },
- Dir{ .x = -0, .y = -1 },
- Dir{ .x = 1, .y = -1 },
- Dir{ .x = -1, .y = 0 },
- Dir{ .x = 1, .y = 0 },
- Dir{ .x = -1, .y = 1 },
- Dir{ .x = 0, .y = 1 },
- Dir{ .x = 1, .y = 1 },
-};
-
-fn parseMap(mapitems: *[]SeatState, dims: *MapDims, input: []const u8, allocator: *std.mem.Allocator) !void {
- var lineit = std.mem.tokenize(input, "\n");
- var map = std.ArrayList(SeatState).init(allocator);
- errdefer map.deinit();
- while (lineit.next()) |line| {
- if (dims.width == 0) {
- dims.width = line.len;
- } else if (dims.width != line.len) {
- return aoc.Error.InvalidInput;
- }
- for (line) |c, i| {
- try map.append(switch (c) {
- '#' => SeatState.TAKEN,
- 'L' => SeatState.EMPTY,
- '.' => SeatState.FLOOR,
- else => {
- return aoc.Error.InvalidInput;
- },
- });
- }
- dims.height += 1;
- }
- mapitems.* = map.toOwnedSlice();
-}
-
-fn printMap(mapitems: []SeatState, dims: MapDims) void {
- for (mapitems) |state, i| {
- const c: u8 = switch (state) {
- SeatState.EMPTY => 'L',
- SeatState.TAKEN => '#',
- SeatState.FLOOR => '.',
- };
- if (i % dims.width == 0) {
- std.debug.print("\n", .{});
- }
- std.debug.print("{c}", .{c});
- }
-}
-
-fn simulateStrategyOne(before: []SeatState, after: []SeatState, dims: MapDims) u32 {
- var seat_changes: u32 = 0;
- for (before) |state, i| {
- const p = Pos{ .x = i % dims.width, .y = i / dims.width };
- var count: u32 = 0;
- for (adjacent) |ap| {
- if (p.x + ap.x >= dims.width or p.x + ap.x < 0 or p.y + ap.y >= dims.height or p.y + ap.y < 0) continue;
- const ni = @intCast(u64, @intCast(i64, i) + ap.x + ap.y * @intCast(i64, dims.width));
- count += @boolToInt(before[ni] == SeatState.TAKEN);
- }
- if (state == SeatState.EMPTY and count == 0) {
- after[i] = SeatState.TAKEN;
- seat_changes += 1;
- } else if (state == SeatState.TAKEN and count >= 4) {
- after[i] = SeatState.EMPTY;
- seat_changes += 1;
- } else {
- after[i] = before[i];
- }
- }
- return seat_changes;
-}
-
-fn simulateStrategyTwo(before: []SeatState, after: []SeatState, dims: MapDims) u32 {
- var seat_changes: u32 = 0;
- for (before) |state, i| {
- const p = Pos{ .x = i % dims.width, .y = i / dims.width };
- var count: u32 = 0;
- for (adjacent) |ap| {
- var iterp = Pos{ .x = p.x + ap.x, .y = p.y + ap.y };
- while (iterp.x < dims.width and iterp.x >= 0 and iterp.y < dims.height and iterp.y >= 0) {
- const ni = @intCast(u64, iterp.x + iterp.y * @intCast(i64, dims.width));
- if (before[ni] == SeatState.TAKEN) {
- count += 1;
- break;
- } else if (before[ni] == SeatState.EMPTY) {
- break;
- } else {
- iterp.x += ap.x;
- iterp.y += ap.y;
- }
- }
- }
- if (state == SeatState.EMPTY and count == 0) {
- after[i] = SeatState.TAKEN;
- seat_changes += 1;
- } else if (state == SeatState.TAKEN and count >= 5) {
- after[i] = SeatState.EMPTY;
- seat_changes += 1;
- } else {
- after[i] = before[i];
- }
- }
- return seat_changes;
-}
-
-fn part1(allocator: *std.mem.Allocator, input: []u8, args: [][]u8) !void {
- var mapdims = MapDims{ .width = 0, .height = 0 };
- var mapitems: []SeatState = undefined;
- try parseMap(&mapitems, &mapdims, input, allocator);
- defer allocator.free(mapitems);
-
- var mapresult = try allocator.alloc(SeatState, mapitems.len);
- defer allocator.free(mapresult);
-
- var round: u32 = 0;
- while (simulateStrategyOne(mapitems, mapresult, mapdims) > 0) : (round += 1) {
- std.debug.print("\rRound: {}", .{round});
- std.mem.copy(SeatState, mapitems, mapresult);
- }
-
- var taken_count: u64 = 0;
- for (mapresult) |state| {
- taken_count += @boolToInt(state == SeatState.TAKEN);
- }
-
- std.debug.print("\nSeats Occupied: {}\n", .{taken_count});
-}
-
-fn part2(allocator: *std.mem.Allocator, input: []u8, args: [][]u8) !void {
- var mapdims = MapDims{ .width = 0, .height = 0 };
- var mapitems: []SeatState = undefined;
- try parseMap(&mapitems, &mapdims, input, allocator);
- defer allocator.free(mapitems);
-
- var mapresult = try allocator.alloc(SeatState, mapitems.len);
- defer allocator.free(mapresult);
-
- var round: u32 = 0;
- while (simulateStrategyTwo(mapitems, mapresult, mapdims) > 0) : (round += 1) {
- std.debug.print("\rRound: {}", .{round});
- std.mem.copy(SeatState, mapitems, mapresult);
- }
-
- var taken_count: u64 = 0;
- for (mapresult) |state| {
- taken_count += @boolToInt(state == SeatState.TAKEN);
- }
-
- std.debug.print("\nSeats Occupied: {}\n", .{taken_count});
-}
-
-pub const main = aoc.gen_main(part1, part2);
diff --git a/src/day12/main.zig b/src/day12/main.zig
@@ -1,60 +0,0 @@
-const std = @import("std");
-const aoc = @import("aoc");
-const Pos = aoc.Pos;
-const Dir = aoc.Dir;
-
-const Ship = struct { pos: Pos, waypoint: Pos, dir: usize };
-
-fn part1(allocator: *std.mem.Allocator, input: []u8, args: [][]u8) !void {
- var ship = Ship{ .pos = Pos{ .x = 0, .y = 0 }, .waypoint = Pos{ .x = 0, .y = 0 }, .dir = 0 };
- var lineit = std.mem.tokenize(input, "\n");
- while (lineit.next()) |line| {
- const val = try std.fmt.parseInt(u32, line[1..], 10);
- switch (line[0]) {
- 'N' => ship.pos = ship.pos.add(Dir.North.mult(val)),
- 'S' => ship.pos = ship.pos.add(Dir.South.mult(val)),
- 'E' => ship.pos = ship.pos.add(Dir.East.mult(val)),
- 'W' => ship.pos = ship.pos.add(Dir.West.mult(val)),
- 'L' => ship.dir = Dir.nextCCW(ship.dir, @divExact(val, 90)),
- 'R' => ship.dir = Dir.nextCW(ship.dir, @divExact(val, 90)),
- 'F' => ship.pos = ship.pos.add(Dir.dirs[ship.dir].mult(val)),
- else => {
- return aoc.Error.InvalidInput;
- },
- }
- }
-
- std.debug.print("{}\n", .{std.math.absCast(ship.pos.x) + std.math.absCast(ship.pos.y)});
-}
-
-fn part2(allocator: *std.mem.Allocator, input: []u8, args: [][]u8) !void {
- var ship = Ship{ .pos = Pos{ .x = 0, .y = 0 }, .waypoint = Pos{ .x = 10, .y = 1 }, .dir = 0 };
- var lineit = std.mem.tokenize(input, "\n");
- while (lineit.next()) |line| {
- const val = try std.fmt.parseInt(u32, line[1..], 10);
- switch (line[0]) {
- 'N' => ship.waypoint = ship.waypoint.add(Dir.North.mult(val)),
- 'S' => ship.waypoint = ship.waypoint.add(Dir.South.mult(val)),
- 'E' => ship.waypoint = ship.waypoint.add(Dir.East.mult(val)),
- 'W' => ship.waypoint = ship.waypoint.add(Dir.West.mult(val)),
- // WORKAROUND for language bug (parameter is implicitly passed as reference and assignment order)
- 'L' => {
- var new = Dir.rotCCW(ship.waypoint, @divExact(val, 90));
- ship.waypoint = new;
- },
- 'R' => {
- var new = Dir.rotCW(ship.waypoint, @divExact(val, 90));
- ship.waypoint = new;
- },
- 'F' => ship.pos = ship.pos.add(ship.waypoint.mult(val)),
- else => {
- return aoc.Error.InvalidInput;
- },
- }
- std.debug.print("{} {} {} {} {}\n", .{ line, ship.waypoint.x, ship.waypoint.y, ship.pos.x, ship.pos.y });
- }
-
- std.debug.print("{}\n", .{std.math.absCast(ship.pos.x) + std.math.absCast(ship.pos.y)});
-}
-
-pub const main = aoc.gen_main(part1, part2);
diff --git a/src/day13/main.zig b/src/day13/main.zig
@@ -1,105 +0,0 @@
-const std = @import("std");
-const aoc = @import("aoc");
-
-fn gcd(a: u64, b: u64) u64 {
- var ac = a;
- var bc = b;
- while (true) {
- if (ac > bc) {
- ac = ac % bc;
- if (ac == 0) return bc;
- } else {
- bc = bc % ac;
- if (bc == 0) return ac;
- }
- }
-}
-
-fn lcm(a: u64, b: u64) u64 {
- return @divExact(a * b, gcd(a, b));
-}
-
-fn waittime(start: u32, busid: u32) u32 {
- return (busid - (start % busid)) % busid;
-}
-
-fn printRegion(buses: []u32, start: u64, end: u64) void {
- std.debug.print(" ", .{});
- for (buses) |bus| {
- std.debug.print(" {:^5}", .{bus});
- }
- std.debug.print("\n", .{});
-
- var i = start;
- while (i < end) : (i += 1) {
- std.debug.print("{:<10}", .{i});
- for (buses) |bus| {
- var c: u8 = '.';
- if (bus > 0 and i % bus == 0) c = 'D';
- std.debug.print(" {c} ", .{c});
- }
- std.debug.print("\n", .{});
- }
- std.debug.print("\n", .{});
-}
-
-fn part1(allocator: *std.mem.Allocator, input: []u8, args: [][]u8) !void {
- var lineit = std.mem.tokenize(input, "\n");
- var start = try std.fmt.parseInt(u32, lineit.next().?, 10);
-
- var bestbus: ?u32 = null;
- var busit = std.mem.tokenize(lineit.next().?, ",");
- while (busit.next()) |bus| {
- if (bus[0] == 'x') continue;
- const val = try std.fmt.parseInt(u32, bus, 10);
- if (bestbus == null or waittime(start, val) < waittime(start, bestbus.?)) {
- bestbus = val;
- }
- }
-
- std.debug.print("{} {}\n", .{ bestbus.?, bestbus.? * waittime(start, bestbus.?) });
-}
-
-fn part2(allocator: *std.mem.Allocator, input: []u8, args: [][]u8) !void {
- var lineit = std.mem.tokenize(input, "\n");
- _ = try std.fmt.parseInt(u32, lineit.next().?, 10);
-
- var busses = std.ArrayList(u32).init(allocator);
- defer busses.deinit();
-
- var busit = std.mem.tokenize(lineit.next().?, ",");
-
- const first = try std.fmt.parseInt(u32, busit.next().?, 10);
- try busses.append(first);
-
- var offset: u64 = 0;
- var cycle: u64 = first;
- var delay: u32 = 1;
- while (busit.next()) |bus| : (delay += 1) {
- if (bus[0] == 'x') {
- try busses.append(0);
- continue;
- }
- const val = try std.fmt.parseInt(u32, bus, 10);
- try busses.append(val);
-
- var mult: u64 = @divFloor(offset + delay, val);
- if ((offset + delay) % val != 0) mult += 1;
- while ((mult * val - offset - delay) % cycle != 0) {
- mult += std.math.max(1, @divFloor(cycle - (mult * val - offset - delay) % cycle, val));
- }
- offset = mult * val - delay;
-
- cycle = lcm(cycle, val);
- if (aoc.debug) {
- printRegion(busses.items, offset, offset + delay + 1);
- printRegion(busses.items, offset + cycle, offset + cycle + delay + 1);
- std.debug.print("{}\n", .{offset});
- }
- }
-
- printRegion(busses.items, offset, offset + busses.items.len);
- std.debug.print("{}\n", .{offset});
-}
-
-pub const main = aoc.gen_main(part1, part2);
diff --git a/src/day14/main.zig b/src/day14/main.zig
@@ -1,118 +0,0 @@
-const std = @import("std");
-const aoc = @import("aoc");
-
-fn getBit(v: u36, i: u6) bool {
- return ((v >> i) & 1) > 0;
-}
-
-fn clearBit(v: u36, i: u6) u36 {
- return v & ~(@as(u36, 1) << i);
-}
-
-fn setBit(v: u36, i: u6) u36 {
- return v | (@as(u36, 1) << i);
-}
-
-fn getValStr(line: []const u8) ![]const u8 {
- const sep = std.mem.indexOf(u8, line, " = ");
- if (sep == null) return aoc.Error.InvalidInput;
- return line[sep.? + 3 ..];
-}
-
-fn getAddrStr(line: []const u8) ![]const u8 {
- const sep = std.mem.indexOfScalar(u8, line, ']');
- if (sep == null) return aoc.Error.InvalidInput;
- return line[4..sep.?];
-}
-
-fn part1(allocator: *std.mem.Allocator, input: []u8, args: [][]u8) !void {
- var answer: u64 = 0;
-
- var memmap = std.AutoHashMap(u36, u64).init(allocator);
- defer memmap.deinit();
-
- var ormask: u36 = 0;
- var andmask: u36 = ~@as(u36, 0);
-
- var lineit = std.mem.tokenize(input, "\n");
- while (lineit.next()) |line| {
- if (std.mem.eql(u8, line[0..4], "mask")) {
- andmask = ~@as(u36, 0);
- ormask = 0;
- for (try getValStr(line)) |c, i| {
- if (c == '0') {
- andmask = clearBit(andmask, @intCast(u6, 35 - i));
- } else if (c == '1') {
- ormask = setBit(ormask, @intCast(u6, 35 - i));
- }
- }
- } else {
- const val = try std.fmt.parseInt(u36, try getValStr(line), 10);
- const addr = try std.fmt.parseInt(u36, try getAddrStr(line), 10);
- try memmap.put(addr, (val & andmask) | ormask);
- }
- }
-
- var mapit = memmap.iterator();
- while (mapit.next()) |kv| {
- answer += kv.value;
- }
-
- std.debug.print("{}\n", .{answer});
-}
-
-fn bitRecurse(map: *std.AutoHashMap(u36, u64), addr: *u36, val: u64, mask: u36, index: u6) anyerror!void {
- if (index == 36) {
- std.debug.print("SET: {b} {}\n", .{ addr.*, val });
- try map.put(addr.*, val);
- } else {
- if (getBit(mask, index)) {
- addr.* = setBit(addr.*, index);
- try bitRecurse(map, addr, val, mask, index + 1);
- addr.* = clearBit(addr.*, index);
- try bitRecurse(map, addr, val, mask, index + 1);
- } else {
- try bitRecurse(map, addr, val, mask, index + 1);
- }
- }
-}
-
-fn part2(allocator: *std.mem.Allocator, input: []u8, args: [][]u8) !void {
- var answer: u64 = 0;
-
- var memmap = std.AutoHashMap(u36, u64).init(allocator);
- defer memmap.deinit();
-
- var ormask: u36 = 0;
- var flipmask: u36 = 0;
-
- var lineit = std.mem.tokenize(input, "\n");
- while (lineit.next()) |line| {
- if (std.mem.eql(u8, line[0..4], "mask")) {
- ormask = 0;
- flipmask = 0;
- for (try getValStr(line)) |c, i| {
- if (c == '1') {
- ormask = setBit(ormask, @intCast(u6, 35 - i));
- } else if (c == 'X') {
- flipmask = setBit(flipmask, @intCast(u6, 35 - i));
- }
- }
- } else {
- var addr = try std.fmt.parseInt(u36, try getAddrStr(line), 10);
- const val = try std.fmt.parseInt(u36, try getValStr(line), 10);
- addr = addr | ormask;
- std.debug.print("{b} {b} {} {}\n", .{ flipmask, ormask, addr, val });
- try bitRecurse(&memmap, &addr, val, flipmask, 0);
- }
- }
-
- var mapit = memmap.iterator();
- while (mapit.next()) |kv| {
- answer += kv.value;
- }
-
- std.debug.print("{}\n", .{answer});
-}
-
-pub const main = aoc.gen_main(part1, part2);
diff --git a/src/day15/main.zig b/src/day15/main.zig
@@ -1,55 +0,0 @@
-const std = @import("std");
-const aoc = @import("aoc");
-
-const Occurance = struct { last: u32, beforelast: u32 };
-
-fn getNthSpoken(allocator: *std.mem.Allocator, input: []u8, spoken: u32) !u32 {
- var occurances = std.AutoHashMap(u32, Occurance).init(allocator);
- defer occurances.deinit();
-
- var intlist = std.ArrayList(u32).init(allocator);
- defer intlist.deinit();
-
- var numit = std.mem.tokenize(input, "\n,");
- var i: u32 = 0;
- while (numit.next()) |numstr| : (i += 1) {
- const num = try std.fmt.parseInt(u32, numstr, 10);
- try intlist.append(num);
- try occurances.put(num, Occurance{ .last = i, .beforelast = i });
- }
-
- while (i < spoken) : (i += 1) {
- if (aoc.debug and i % 100000 == 0)
- std.debug.print("\r{}", .{i});
-
- const num = intlist.items[i - 1];
- var entry = occurances.getEntry(num);
- var diff: u32 = 0;
- if (entry) |occ_entry| {
- diff = occ_entry.value.last - occ_entry.value.beforelast;
- }
- entry = occurances.getEntry(diff);
- if (entry) |occ_entry| {
- occ_entry.value.beforelast = occ_entry.value.last;
- occ_entry.value.last = i;
- } else {
- try occurances.put(diff, Occurance{ .last = i, .beforelast = i });
- }
- try intlist.append(diff);
- }
-
- if (aoc.debug)
- std.debug.print("\r \r", .{});
-
- return intlist.items[spoken - 1];
-}
-
-fn part1(allocator: *std.mem.Allocator, input: []u8, args: [][]u8) !void {
- std.debug.print("{}\n", .{try getNthSpoken(allocator, input, 2020)});
-}
-
-fn part2(allocator: *std.mem.Allocator, input: []u8, args: [][]u8) !void {
- std.debug.print("{}\n", .{try getNthSpoken(allocator, input, 30000000)});
-}
-
-pub const main = aoc.gen_main(part1, part2);
diff --git a/src/day16/main.zig b/src/day16/main.zig
@@ -1,176 +0,0 @@
-const std = @import("std");
-const aoc = @import("aoc");
-
-const Range = struct { min: u32, max: u32 };
-const FieldRule = struct { name: []const u8, r1: Range, r2: Range };
-
-fn assert(comptime T: type, part: ?T) !T {
- if (part == null) return aoc.Error.InvalidInput;
- return part.?;
-}
-
-fn parseRange(str: []const u8) !Range {
- const sep = try assert(usize, std.mem.indexOfScalar(u8, str, '-'));
- if (sep == str.len - 1) return aoc.Error.InvalidInput;
- return Range{
- .min = try std.fmt.parseInt(u32, str[0..sep], 10),
- .max = try std.fmt.parseInt(u32, str[sep + 1 ..], 10),
- };
-}
-
-fn parseRules(rules: *std.ArrayList(FieldRule), str: []const u8) !void {
- var lineit = std.mem.tokenize(str, "\n");
- while (lineit.next()) |line| {
- const sep = try assert(usize, std.mem.indexOf(u8, line, ": "));
- if (sep == line.len - 1) return aoc.Error.InvalidInput;
- const name = line[0..sep];
- var rangepart = line[sep + 2 ..];
- var spaceit = std.mem.tokenize(rangepart, " ");
- const r1 = try parseRange(try assert([]const u8, spaceit.next()));
- _ = spaceit.next();
- const r2 = try parseRange(try assert([]const u8, spaceit.next()));
- try rules.append(FieldRule{ .name = name, .r1 = r1, .r2 = r2 });
- }
-}
-
-fn parseVals(vals: *std.ArrayList(u32), str: []const u8) !void {
- var lineit = std.mem.tokenize(str, "\n");
- while (lineit.next()) |line| {
- var partit = std.mem.tokenize(line, ",");
- while (partit.next()) |part| {
- try vals.append(try std.fmt.parseInt(u32, part, 10));
- }
- }
-}
-
-fn matchesRule(rule: FieldRule, v: u32) bool {
- return (v >= rule.r1.min and v <= rule.r1.max or v >= rule.r2.min and v <= rule.r2.max);
-}
-
-fn hasRule(rules: []FieldRule, v: u32) bool {
- for (rules) |r, i| {
- if (matchesRule(r, v)) return true;
- }
- return false;
-}
-
-fn printCandidates(candidates: []u1, rulecount: usize, remove: usize) void {
- var i: u32 = 0;
- while (i < rulecount) : (i += 1) {
- for (candidates[i * rulecount .. (i + 1) * rulecount]) |c| {
- std.debug.print("{} ", .{c});
- }
- if (i == remove) std.debug.print(" <<<", .{});
- std.debug.print("\n", .{});
- }
-}
-
-fn part1(allocator: *std.mem.Allocator, input: []u8, args: [][]u8) !void {
- var answer: u32 = 0;
-
- var rules = std.ArrayList(FieldRule).init(allocator);
- defer rules.deinit();
-
- var othervals = std.ArrayList(u32).init(allocator);
- defer othervals.deinit();
-
- var secit = std.mem.split(input, "\n\n");
- try parseRules(&rules, try assert([]const u8, secit.next()));
- _ = secit.next();
- try parseVals(&othervals, (try assert([]const u8, secit.next()))[16..]);
-
- for (othervals.items) |v| {
- if (!hasRule(rules.items, v)) answer += v;
- }
-
- std.debug.print("{}\n", .{answer});
-}
-
-fn part2(allocator: *std.mem.Allocator, input: []u8, args: [][]u8) !void {
- var rules = std.ArrayList(FieldRule).init(allocator);
- defer rules.deinit();
-
- var ownvals = std.ArrayList(u32).init(allocator);
- defer ownvals.deinit();
-
- var othervals = std.ArrayList(u32).init(allocator);
- defer othervals.deinit();
-
- var secit = std.mem.split(input, "\n\n");
- try parseRules(&rules, try assert([]const u8, secit.next()));
- try parseVals(&ownvals, (try assert([]const u8, secit.next()))[13..]);
- try parseVals(&othervals, (try assert([]const u8, secit.next()))[16..]);
-
- const rulecount = rules.items.len;
-
- {
- var index: u32 = 0;
- while (index < othervals.items.len) {
- const ri = index % rulecount;
- var i: u32 = 0;
- while (i < rulecount) : (i += 1) {
- if (!hasRule(rules.items, othervals.items[index + i]))
- break;
- }
-
- if (i == rulecount) {
- index += @intCast(u32, rulecount);
- } else {
- if (aoc.debug)
- std.debug.print("REMOVE: ", .{});
- i = 0;
- while (i < rulecount) : (i += 1) {
- if (aoc.debug)
- std.debug.print("{} ", .{othervals.items[index]});
- _ = othervals.orderedRemove(index);
- }
- if (aoc.debug)
- std.debug.print("\n", .{});
- }
- }
- }
-
- var candidates = try allocator.alloc(u1, rulecount * rulecount);
- defer allocator.free(candidates);
- std.mem.set(u1, candidates, 1);
-
- if (aoc.debug)
- std.debug.print("{}\n", .{othervals.items.len});
- {
- var index: u32 = 0;
- while (index < othervals.items.len) : (index += 1) {
- const ri = index % rulecount;
- const v = othervals.items[index];
- for (rules.items) |r, rri| {
- if (!matchesRule(r, v)) {
- candidates[ri * rulecount + rri] = 0;
- }
- }
- }
- }
-
- var answer: u64 = 1;
- {
- var index: u32 = 0;
- while (index < rulecount * rulecount) : (index += 1) {
- var ri = index % rulecount;
- const cc = candidates[ri * rulecount .. (ri + 1) * rulecount];
- if (std.mem.count(u1, cc, ([_]u1{1})[0..]) == 1) {
- const field = std.mem.indexOfScalar(u1, cc, 1).?;
- if (std.mem.indexOf(u8, rules.items[field].name, "departure") != null)
- answer *= ownvals.items[ri];
- for (ownvals.items) |_, ii| {
- candidates[ii * rulecount + field] = 0;
- }
- if (aoc.debug) {
- printCandidates(candidates, rulecount, ri);
- std.debug.print("\n", .{});
- }
- }
- }
- }
-
- std.debug.print("{}\n", .{answer});
-}
-
-pub const main = aoc.gen_main(part1, part2);
diff --git a/src/day17/main.zig b/src/day17/main.zig
@@ -1,193 +0,0 @@
-const std = @import("std");
-const aoc = @import("aoc");
-
-fn PosVec(comptime N: u32) type {
- return struct { data: [N]i64 };
-}
-
-const Active = bool;
-
-fn forNeighbors(comptime dims: u32, map: *std.AutoHashMap(PosVec(dims), Active), p: PosVec(dims), data: anytype, func: fn (map: *std.AutoHashMap(PosVec(dims), Active), p: PosVec(dims), d: @TypeOf(data)) anyerror!void) !void {
- var i: u32 = 0;
- while (i < comptime std.math.pow(u32, 3, dims)) : (i += 1) {
- var np: PosVec(dims) = undefined;
- var d: u32 = 0;
- var skip = true;
- while (d < dims) : (d += 1) {
- const offset = (i / std.math.pow(u32, 3, d)) % 3;
- np.data[d] = p.data[d] + @intCast(i64, offset) - 1;
- if (skip and offset != 1) skip = false;
- }
- if (skip) continue;
- try func(map, np, data);
- }
-}
-
-fn posStr(comptime dims: u32, p: PosVec(dims)) void {
- var d: u32 = 0;
- while (d < dims) : (d += 1) {
- std.debug.print("{} ", .{p.data[d]});
- }
-}
-
-fn countActive(comptime dims: u32) fn (map: *std.AutoHashMap(PosVec(dims), Active), p: PosVec(dims), d: *u32) anyerror!void {
- const impl = struct {
- fn func(map: *std.AutoHashMap(PosVec(dims), Active), p: PosVec(dims), d: *u32) anyerror!void {
- d.* += @boolToInt(map.get(p) != null);
- }
- };
- return impl.func;
-}
-
-fn addNew(comptime dims: u32) fn (oldmap: *std.AutoHashMap(PosVec(dims), Active), p: PosVec(dims), newmap: *std.AutoHashMap(PosVec(dims), Active)) anyerror!void {
- const impl = struct {
- fn func(oldmap: *std.AutoHashMap(PosVec(dims), Active), p: PosVec(dims), newmap: *std.AutoHashMap(PosVec(dims), Active)) anyerror!void {
- if (newmap.get(p) != null) return;
-
- var v = oldmap.get(p);
- var state = (v != null);
-
- var count: u32 = 0;
- try forNeighbors(dims, oldmap, p, &count, countActive(dims));
- if (state and count >= 2 and count <= 3 or !state and count == 3) {
- try newmap.put(p, true);
- }
- }
- };
- return impl.func;
-}
-
-fn simulateRound(comptime dims: u32, map: *std.AutoHashMap(PosVec(dims), Active), allocator: *std.mem.Allocator) !void {
- var newmap = std.AutoHashMap(PosVec(dims), Active).init(allocator);
- errdefer newmap.deinit();
-
- var mapit = map.iterator();
- while (mapit.next()) |kv| {
- try forNeighbors(dims, map, kv.key, &newmap, addNew(dims));
- try addNew(dims)(map, kv.key, &newmap);
- }
-
- std.mem.swap(std.AutoHashMap(PosVec(dims), Active), map, &newmap);
- newmap.deinit();
-}
-
-fn sliceProduct(data: []i64) i64 {
- var product: i64 = 1;
- for (data) |v| {
- product *= v;
- }
- return product;
-}
-
-fn printMap(comptime dims: u32, map: *std.AutoHashMap(PosVec(dims), Active)) void {
- var min: ?PosVec(dims) = null;
- var max: ?PosVec(dims) = null;
-
- var mapit = map.iterator();
- while (mapit.next()) |kv| {
- if (min == null) min = kv.key;
- if (max == null) max = kv.key;
-
- var d: u32 = 0;
- while (d < dims) : (d += 1) {
- if (min.?.data[d] > kv.key.data[d]) min.?.data[d] = kv.key.data[d];
- if (max.?.data[d] < kv.key.data[d]) max.?.data[d] = kv.key.data[d];
- }
- }
-
- if (min == null or max == null) return;
-
- var space: PosVec(dims) = undefined;
- {
- var d: u32 = 0;
- while (d < dims) : (d += 1) {
- space.data[d] = max.?.data[d] - min.?.data[d];
- }
- }
-
- var i: usize = 0;
- while (i < sliceProduct(space.data[0..])) : (i += @intCast(usize, space.data[0] * space.data[1])) {
- var np: PosVec(dims) = undefined;
- var d: u32 = 0;
- while (d < dims) : (d += 1) {
- np.data[d] = min.?.data[d] + @mod(@divFloor(@intCast(i64, i), sliceProduct(space.data[0..d])), space.data[d]);
- }
-
- d = 2;
- std.debug.print("Slice at: ", .{});
- while (d < dims) : (d += 1) {
- if (d > 2) std.debug.print(",", .{});
- std.debug.print("{}.Dim = {} ", .{ d + 1, np.data[d] });
- }
- std.debug.print("\n", .{});
-
- var y = min.?.data[1];
- while (y <= max.?.data[1]) : (y += 1) {
- var x = min.?.data[0];
- while (x <= max.?.data[0]) : (x += 1) {
- var v = np;
- v.data[0] = x;
- v.data[1] = y;
- var c: u8 = '.';
- if (map.get(v) != null) c = '#';
- std.debug.print("{c}", .{c});
- }
- std.debug.print("\n", .{});
- }
- std.debug.print("\n", .{});
- }
-}
-
-fn part1(allocator: *std.mem.Allocator, input: []u8, args: [][]u8) !void {
- var map = std.AutoHashMap(PosVec(3), Active).init(allocator);
- defer map.deinit();
-
- var lineit = std.mem.tokenize(input, "\n");
- var y: i64 = 0;
- while (lineit.next()) |line| : (y += 1) {
- for (line) |c, x| {
- if (c != '#') continue;
- try map.put(PosVec(3){ .data = [_]i64{ @intCast(i64, x), y, 0 } }, true);
- }
- }
-
- var i: usize = 0;
- while (i < 6) : (i += 1) {
- try simulateRound(3, &map, allocator);
- if (aoc.debug) {
- std.debug.print("AFTER ROUND {}:\n", .{i + 1});
- printMap(3, &map);
- }
- }
-
- var answer: u32 = map.count();
- std.debug.print("{}\n", .{answer});
-}
-
-fn part2(allocator: *std.mem.Allocator, input: []u8, args: [][]u8) !void {
- var map = std.AutoHashMap(PosVec(4), Active).init(allocator);
- defer map.deinit();
-
- var lineit = std.mem.tokenize(input, "\n");
- var y: i64 = 0;
- while (lineit.next()) |line| : (y += 1) {
- for (line) |c, x| {
- if (c != '#') continue;
- try map.put(PosVec(4){ .data = [_]i64{ @intCast(i64, x), y, 0, 0 } }, true);
- }
- }
-
- var i: usize = 0;
- while (i < 6) : (i += 1) {
- try simulateRound(4, &map, allocator);
- if (aoc.debug) {
- std.debug.print("AFTER ROUND {}:\n", .{i + 1});
- printMap(4, &map);
- }
- }
-
- var answer: u32 = map.count();
- std.debug.print("{}\n", .{answer});
-}
-
-pub const main = aoc.gen_main(part1, part2);
diff --git a/src/day18/main.zig b/src/day18/main.zig
@@ -1,173 +0,0 @@
-// Own twist on https://en.wikipedia.org/wiki/Shunting-yard_algorithm
-
-const std = @import("std");
-const aoc = @import("aoc");
-
-const OpType = enum { ADD, MULT, COUNT };
-const Op = struct {
- prio: u32, optype: OpType
-};
-const Item = union(enum) {
- num: i64, op: OpType
-};
-
-const op_names = [_][]const u8{ "ADD", "MULT" };
-
-fn printStack(stack: []Item) void {
- for (stack) |item| {
- switch (item) {
- .op => std.debug.print("{} ", .{op_names[@enumToInt(item.op)]}),
- .num => std.debug.print("{} ", .{item.num}),
- }
- }
- std.debug.print("\n", .{});
-}
-
-fn parseToken(line: []const u8, i: *usize, depth: *u32, op_prio: []const u32, mathstack: *std.ArrayList(Item), opstack: *std.ArrayList(Op)) !bool {
- if (i.* > line.len) {
- return false;
- } else if (i.* == line.len) {
- while (opstack.items.len > 0)
- try mathstack.append(Item{ .op = opstack.pop().optype });
- } else {
- const c = line[i.*];
- switch (c) {
- '+', '*' => {
- const optype = switch (c) {
- '+' => OpType.ADD,
- '*' => OpType.MULT,
- else => unreachable,
- };
- const prio = depth.* * @enumToInt(OpType.COUNT) + op_prio[@enumToInt(optype)];
- while (opstack.items.len > 0 and
- opstack.items[opstack.items.len - 1].prio >= prio)
- {
- try mathstack.append(Item{ .op = opstack.pop().optype });
- }
- try opstack.append(Op{ .optype = optype, .prio = prio });
- },
- '(' => depth.* += 1,
- ')' => depth.* -= 1,
- ' ' => {},
- else => {
- // in this case we know that every number is one digit..
- // crappy zig parseInt requires span of exact int size
- // before we even know the format >:(((
- const val = try std.fmt.parseInt(i64, line[i.* .. i.* + 1], 10);
- try mathstack.append(Item{ .num = val });
- },
- }
- }
- i.* += 1;
- return true;
-}
-
-fn reduceStack(mathstack: *std.ArrayList(Item), opstack: *std.ArrayList(Op), tmpstack: *std.ArrayList(Item)) !void {
- while (mathstack.items.len > 0) {
- while (mathstack.items[mathstack.items.len - 1] != .op and
- tmpstack.items.len > 0)
- {
- try mathstack.append(tmpstack.pop());
- }
- if (mathstack.items.len < 3 or mathstack.items[mathstack.items.len - 1] != .op)
- break;
- const op = mathstack.pop();
-
- // get first arg
- if (mathstack.items[mathstack.items.len - 1] != .num) {
- try tmpstack.append(op);
- continue;
- }
- const a = mathstack.pop();
-
- // get second arg
- if (mathstack.items[mathstack.items.len - 1] != .num) {
- try tmpstack.append(op);
- try tmpstack.append(a);
- continue;
- }
- const b = mathstack.pop();
-
- const result: i64 = switch (op.op) {
- OpType.ADD => a.num + b.num,
- OpType.MULT => a.num * b.num,
- else => unreachable,
- };
- try mathstack.append(Item{ .num = result });
- }
-}
-
-fn printRPN(allocator: *std.mem.Allocator, input: []u8, prios: []const u32) !void {
- var mathstack = std.ArrayList(Item).init(allocator);
- defer mathstack.deinit();
-
- var opstack = std.ArrayList(Op).init(allocator);
- defer opstack.deinit();
-
- var lineit = std.mem.tokenize(input, "\n");
- while (lineit.next()) |line| {
- var depth: u32 = 0;
- var i: usize = 0;
- while (try parseToken(line, &i, &depth, prios, &mathstack, &opstack)) {}
- }
-
- printStack(mathstack.items);
-}
-
-fn partProto(allocator: *std.mem.Allocator, input: []u8, prios: []const u32) !void {
- var answer: i64 = 0;
-
- if (aoc.debug) {
- std.debug.print("Reverse Polish Notation:\n", .{});
- try printRPN(allocator, input, prios);
- }
-
- var mathstack = std.ArrayList(Item).init(allocator);
- defer mathstack.deinit();
-
- var opstack = std.ArrayList(Op).init(allocator);
- defer opstack.deinit();
-
- var tmpstack = std.ArrayList(Item).init(allocator);
- defer tmpstack.deinit();
-
- var lineit = std.mem.tokenize(input, "\n");
- while (lineit.next()) |line| {
- var depth: u32 = 0;
- var i: usize = 0;
- while (try parseToken(line, &i, &depth, prios, &mathstack, &opstack)) {
- try reduceStack(&mathstack, &opstack, &tmpstack);
- }
-
- if (mathstack.items.len != 1) return aoc.Error.InvalidInput;
- const last = mathstack.items[mathstack.items.len - 1];
- if (last != .num) return aoc.Error.InvalidInput;
- answer += last.num;
-
- try mathstack.resize(0);
- try opstack.resize(0);
- try tmpstack.resize(0);
- }
-
- std.debug.print("{}\n", .{answer});
-}
-
-fn part1(allocator: *std.mem.Allocator, input: []u8, args: [][]u8) !void {
- const prios = [_]u32{ 1, 1 };
- try partProto(allocator, input, prios[0..]);
-}
-
-fn part2(allocator: *std.mem.Allocator, input: []u8, args: [][]u8) !void {
- const prios = [_]u32{ 2, 1 };
- try partProto(allocator, input, prios[0..]);
-}
-
-test "unions" {
- const item1 = Item{ .op = OpType.MULT };
- const item2 = Item{ .num = 1000 };
- const expect = std.testing.expect;
- expect(item1 == .op);
- expect(item2 == .num);
-}
-
-pub const main = aoc.gen_main(part1, part2);
diff --git a/src/day19/main.zig b/src/day19/main.zig
@@ -1,177 +0,0 @@
-const std = @import("std");
-const aoc = @import("aoc");
-
-const Rule = union(enum) {
- c: u8,
- combos: []const []const usize,
-};
-
-fn printSlice(slice: []const usize) void {
- for (slice) |v, i| {
- if (i > 0) {
- std.debug.print(" ", .{});
- }
- std.debug.print("{}", .{v});
- }
-}
-
-var stacktrace: std.ArrayList(usize) = undefined;
-
-fn checkRule(rules: *std.AutoHashMap(usize, Rule), rid: usize, msg: []const u8, nextstack: *std.ArrayList(usize)) anyerror!bool {
- if (msg.len == 0) return true;
- const rule = rules.get(rid) orelse return aoc.Error.InvalidInput;
-
- if (rule == .c) {
- if (msg[0] != rule.c) return false;
- if (msg.len == 1) return (nextstack.items.len == 0);
- if (nextstack.items.len == 0) return false;
-
- const next = nextstack.pop();
-
- const valid = try checkRule(rules, next, msg[1..], nextstack);
- if (valid) try stacktrace.append(next);
- if (valid) return true;
-
- try nextstack.append(next);
- } else {
- for (rule.combos) |ruleseq| {
- try nextstack.appendSlice(ruleseq[1..]);
- std.mem.reverse(usize, nextstack.items[nextstack.items.len - (ruleseq.len - 1) ..]);
-
- const valid = try checkRule(rules, ruleseq[0], msg, nextstack);
- if (valid) try stacktrace.append(ruleseq[0]);
- if (valid) return true;
-
- try nextstack.resize(nextstack.items.len - (ruleseq.len - 1));
- }
- }
- return false;
-}
-
-fn freeRules(allocator: *std.mem.Allocator, rules: *std.AutoHashMap(usize, Rule), ignore: ?[]const usize) void {
- var mapit = rules.iterator();
- while (mapit.next()) |kv| {
- if (ignore != null and std.mem.indexOfScalar(usize, ignore.?, kv.key) != null) continue;
- if (kv.value == .combos) {
- for (kv.value.combos) |rs| {
- allocator.free(rs);
- }
- allocator.free(kv.value.combos);
- }
- }
- rules.deinit();
-}
-
-fn parseRule(allocator: *std.mem.Allocator, rules: *std.AutoHashMap(usize, Rule), line: []const u8) !void {
- const indexsep = try aoc.assertV(std.mem.indexOf(u8, line, ": "));
- const index = try std.fmt.parseInt(usize, line[0..indexsep], 10);
-
- var chrsep = std.mem.indexOf(u8, line, "\"");
- if (chrsep != null) {
- if (chrsep.? == line.len - 1) return aoc.Error.InvalidInput;
- try rules.put(index, Rule{ .c = line[chrsep.? + 1] });
- } else {
- var vals = std.ArrayList([]usize).init(allocator);
- errdefer vals.deinit();
-
- var ruleit = std.mem.split(line[indexsep + 2 ..], " | ");
- while (ruleit.next()) |r| {
- var ruleids = std.ArrayList(usize).init(allocator);
- errdefer ruleids.deinit();
-
- var spaceit = std.mem.tokenize(r, " ");
- while (spaceit.next()) |word| {
- try ruleids.append(try std.fmt.parseInt(usize, word, 10));
- }
-
- if (ruleids.items.len == 0) return aoc.Error.InvalidInput;
-
- try vals.append(ruleids.items);
- }
-
- try rules.put(index, Rule{ .combos = vals.items });
- }
-}
-
-fn part1(allocator: *std.mem.Allocator, input: []u8, args: [][]u8) !void {
- var rules = std.AutoHashMap(usize, Rule).init(allocator);
- defer freeRules(allocator, &rules, null);
-
- var partit = std.mem.split(input, "\n\n");
-
- var lineit = std.mem.tokenize(try aoc.assertV(partit.next()), "\n");
- while (lineit.next()) |line| {
- try parseRule(allocator, &rules, line);
- }
-
- var answer: u32 = 0;
- var nextstack = std.ArrayList(usize).init(allocator);
- defer nextstack.deinit();
-
- stacktrace = std.ArrayList(usize).init(allocator);
- defer stacktrace.deinit();
-
- lineit = std.mem.tokenize(try aoc.assertV(partit.next()), "\n");
- var count: usize = 0;
- while (lineit.next()) |line| {
- count += 1;
- if (try checkRule(&rules, 0, line, &nextstack))
- answer += 1;
- try nextstack.resize(0);
- }
-
- std.debug.print("{} / {} matching\n", .{ answer, count });
-}
-
-fn part2(allocator: *std.mem.Allocator, input: []u8, args: [][]u8) !void {
- var rules = std.AutoHashMap(usize, Rule).init(allocator);
- defer freeRules(allocator, &rules, ([_]usize{ 8, 11 })[0..]);
-
- var partit = std.mem.split(input, "\n\n");
-
- var lineit = std.mem.tokenize(try aoc.assertV(partit.next()), "\n");
- while (lineit.next()) |line| {
- if (std.mem.eql(u8, line[0..2], "8:")) {
- const p1: []const usize = ([_]usize{42})[0..];
- const p2: []const usize = ([_]usize{ 42, 8 })[0..];
- try rules.put(8, Rule{ .combos = ([_][]const usize{ p1, p2 })[0..] });
- } else if (std.mem.eql(u8, line[0..3], "11:")) {
- const p1: []const usize = ([_]usize{ 42, 31 })[0..];
- const p2: []const usize = ([_]usize{ 42, 11, 31 })[0..];
- try rules.put(11, Rule{ .combos = ([_][]const usize{ p1, p2 })[0..] });
- } else {
- try parseRule(allocator, &rules, line);
- }
- }
-
- var answer: u32 = 0;
- var nextstack = std.ArrayList(usize).init(allocator);
- defer nextstack.deinit();
-
- stacktrace = std.ArrayList(usize).init(allocator);
- defer stacktrace.deinit();
-
- var count: usize = 0;
- lineit = std.mem.tokenize(try aoc.assertV(partit.next()), "\n");
- while (lineit.next()) |line| {
- count += 1;
- const valid = try checkRule(&rules, 0, line, &nextstack);
- answer += @boolToInt(valid);
- if (aoc.debug) {
- std.debug.print("TRACE: [", .{});
- std.mem.reverse(usize, stacktrace.items);
- printSlice(stacktrace.items);
- std.debug.print("]\n", .{});
- if (valid) {
- std.debug.print("MATCH {}\n\n", .{line});
- } else {
- std.debug.print("NO MATCH {}\n\n", .{line});
- }
- }
- try nextstack.resize(0);
- }
-
- std.debug.print("{} / {} matching\n", .{ answer, count });
-}
-
-pub const main = aoc.gen_main(part1, part2);
diff --git a/src/day2/main.zig b/src/day2/main.zig
@@ -1,57 +0,0 @@
-const std = @import("std");
-const aoc = @import("aoc");
-
-const Entry = struct {
- a: u16, b: u16, char: u8, pass: []u8
-};
-
-fn freeEntries(allocator: *std.mem.Allocator, entries: *const std.ArrayList(Entry)) void {
- for (entries.items) |item|
- allocator.free(item.pass);
- entries.deinit();
-}
-
-fn parse(allocator: *std.mem.Allocator, input: []u8) !std.ArrayList(Entry) {
- var entries = std.ArrayList(Entry).init(allocator);
- errdefer freeEntries(allocator, &entries);
-
- var lineit = std.mem.tokenize(input, "\n");
- while (lineit.next()) |line| {
- var entry: Entry = undefined;
- var it = std.mem.tokenize(line, " -");
- entry.a = try std.fmt.parseInt(u16, it.next().?, 10);
- entry.b = try std.fmt.parseInt(u16, it.next().?, 10);
- entry.char = it.next().?[0];
- entry.pass = try allocator.dupe(u8, it.next().?);
- try entries.append(entry);
- }
-
- return entries;
-}
-
-fn part1(allocator: *std.mem.Allocator, input: []u8, args: [][]u8) !void {
- const entries = try parse(allocator, input);
- defer freeEntries(allocator, &entries);
-
- var valid: u32 = 0;
- for (entries.items) |entry| {
- var count: u16 = 0;
- for (entry.pass) |c| count += @boolToInt(c == entry.char);
- valid += @boolToInt(count >= entry.a and count <= entry.b);
- }
- std.debug.print("{}\n", .{valid});
-}
-
-fn part2(allocator: *std.mem.Allocator, input: []u8, args: [][]u8) !void {
- const entries = try parse(allocator, input);
- defer freeEntries(allocator, &entries);
-
- var valid: u32 = 0;
- for (entries.items) |entry| {
- valid += @boolToInt((entry.pass[entry.a - 1] == entry.char) !=
- (entry.pass[entry.b - 1] == entry.char));
- }
- std.debug.print("{}\n", .{valid});
-}
-
-pub const main = aoc.gen_main(part1, part2);
diff --git a/src/day20/main.zig b/src/day20/main.zig
@@ -1,463 +0,0 @@
-const std = @import("std");
-const aoc = @import("aoc");
-
-const tile_width: u32 = 10;
-const Tile = struct {
- id: u32,
- data: [tile_width * tile_width]u1,
- sides: [4][tile_width]u1, // NOTE: update these values when placed accordingly
- adj: [4]?usize,
- pos: aoc.Pos,
-};
-const Flip = enum { NONE, HOR, VERT };
-const flips = [_]Flip{ Flip.NONE, Flip.HOR, Flip.VERT };
-
-const seamonster = [_][]const u8{
- " # ",
- "# ## ## ###",
- " # # # # # # ",
-};
-
-const dirs = [4]aoc.Pos{
- aoc.Pos{ .x = 0, .y = -1 },
- aoc.Pos{ .x = 1, .y = 0 },
- aoc.Pos{ .x = 0, .y = 1 },
- aoc.Pos{ .x = -1, .y = 0 },
-};
-
-fn printGrid(tiles: []Tile, grid: []?usize, grid_width: u32) void {
- var y: u32 = 0;
- while (y < grid_width * tile_width) : (y += 1) {
- var x: u32 = 0;
- if (y > 0 and y % tile_width == 0) std.debug.print("\n", .{});
- while (x < grid_width * tile_width) : (x += 1) {
- if (x > 0 and x % tile_width == 0) std.debug.print(" ", .{});
- var tile_index: ?usize = grid[@divFloor(y, tile_width) * grid_width + @divFloor(x, tile_width)];
- if (tile_index) |ti| {
- var tile = tiles[tile_index.?];
- var c: u8 = if (tile.data[(y % tile_width) * tile_width + (x % tile_width)] == 1) '#' else '.';
- std.debug.print("{c}", .{c});
- } else {
- std.debug.print("?", .{});
- }
- }
- std.debug.print("\n", .{});
- }
- std.debug.print("\n\n", .{});
-}
-
-fn printTile(data: []u1, width: u32) void {
- var y: u32 = 0;
- while (y < width) : (y += 1) {
- printTileSlice(data[y * width .. (y + 1) * width]);
- std.debug.print("\n", .{});
- }
-}
-
-fn printTileSlice(slice: []const u1) void {
- var i: u32 = 0;
- while (i < slice.len) : (i += 1) {
- var c: u8 = if (slice[i] == 1) '#' else '.';
- std.debug.print("{c}", .{c});
- }
-}
-
-fn couldMatch(side1: [tile_width]u1, side2: [tile_width]u1) bool {
- var side1_cpy = side1;
- if (std.mem.eql(u1, side1_cpy[0..], side2[0..])) return true;
- std.mem.reverse(u1, side1_cpy[0..]);
- if (std.mem.eql(u1, side1_cpy[0..], side2[0..])) return true;
- return false;
-}
-
-fn parseTiles(tiles: *std.ArrayList(Tile), input: []u8) !void {
- var tileit = std.mem.split(input, "\n\n");
- while (tileit.next()) |tilestr| {
- if (tilestr.len <= 1) continue;
- var tile: Tile = undefined;
- var lineit = std.mem.tokenize(tilestr, "\n");
-
- // read tile id
- var numstr = (try aoc.assertV(lineit.next()))[5..9];
- tile.id = try std.fmt.parseInt(u32, numstr, 10);
-
- // read tile data
- var i: u32 = 0;
- var line: []const u8 = undefined;
- while (i < tile_width * tile_width) : (i += 1) {
- if (i % tile_width == 0) line = try aoc.assertV(lineit.next());
- tile.data[i] = @boolToInt(line[i % tile_width] == '#');
- }
-
- // read side bits
- i = 0;
- while (i < 4) : (i += 1) {
- var sidebits: [tile_width]u1 = undefined;
- for (sidebits) |_, k| {
- sidebits[k] = switch (i) {
- @enumToInt(aoc.Dir.Name.NORTH) => tile.data[k],
- @enumToInt(aoc.Dir.Name.WEST) => tile.data[(tile_width - 1 - k) * tile_width],
- @enumToInt(aoc.Dir.Name.EAST) => tile.data[tile_width - 1 + k * tile_width],
- @enumToInt(aoc.Dir.Name.SOUTH) => tile.data[tile_width * tile_width - 1 - k],
- else => unreachable,
- };
- }
- tile.sides[i] = sidebits;
- }
-
- // init misc data
- tile.adj = [_]?usize{ null, null, null, null };
-
- try tiles.append(tile);
- }
-}
-
-fn matchTiles(tiles: *std.ArrayList(Tile)) void {
- // for each items's side, look for another item with a matching side
- for (tiles.items) |*tile, tile_index| {
- sides_loop: for (tile.sides) |_, i| {
- for (tiles.items) |*otile, otile_index| {
- if (tile_index == otile_index) continue;
-
- for (otile.sides) |_, oi| {
- if (tile.adj[i] == null and otile.adj[oi] == null and couldMatch(tile.sides[i], otile.sides[oi])) {
- tile.adj[i] = otile_index;
- otile.adj[oi] = tile_index;
- continue :sides_loop;
- }
- }
- }
- }
-
- if (aoc.debug) {
- std.debug.print("{}:\nSIDES ", .{tile.id});
- for (tile.sides) |side| {
- for (side) |b| {
- var c: u8 = if (b == 1) '#' else '.';
- std.debug.print("{c}", .{c});
- }
- std.debug.print(" ", .{});
- }
- std.debug.print("\n", .{});
- for (tile.adj) |adj, i| {
- if (tile.adj[i] == null) {
- std.debug.print("null ", .{});
- } else {
- var adjtile = tiles.items[adj.?];
- std.debug.print("{} ", .{adjtile.id});
- }
- }
- std.debug.print("\n\n", .{});
- }
- }
-}
-
-fn checkSides(tiles: []Tile, grid: []?usize, grid_width: u32, p: aoc.Pos, adj: [4]?usize, sides: [4][10]u1) bool {
- var rot: u32 = 0;
- while (rot < 4) : (rot += 1) {
- const np = p.add(dirs[rot]);
- std.debug.print("{}\n", .{@intToEnum(aoc.Dir.Name, @intCast(u2, rot))});
- std.debug.print("{} {}\n", .{ np.x, np.y });
-
- var side: ?[tile_width]u1 = undefined;
- if (np.x < 0 or np.x >= grid_width or np.y < 0 or np.y >= grid_width) {
- std.debug.print("Side is null\n", .{});
- if (adj[rot] == null) {
- continue;
- } else {
- std.debug.print("Side {} should be NULL!\n", .{@intToEnum(aoc.Dir.Name, @intCast(u2, rot))});
- return false;
- }
- }
-
- var ti: ?usize = grid[@intCast(u32, np.y * @intCast(i64, grid_width) + np.x)] orelse continue;
-
- var otherside = tiles[ti.?].sides[aoc.Dir.nextCW(rot, 2)];
- std.mem.reverse(u1, otherside[0..]);
- printTileSlice(otherside[0..]);
- std.debug.print(" vs ", .{});
- printTileSlice(sides[rot][0..]);
- std.debug.print("\n", .{});
-
- if (!std.mem.eql(u1, otherside[0..], sides[rot][0..])) return false;
- }
- return true;
-}
-
-fn rotateData(newdata: *[]u1, olddata: []u1, width: u32, rot: usize) void {
- for (olddata) |v, di| {
- const dy = @divFloor(di, width);
- const dx = di % width;
- var nx = dx;
- var ny = dy;
- switch (rot) {
- @enumToInt(aoc.Dir.Name.NORTH) => {},
- @enumToInt(aoc.Dir.Name.EAST) => {
- nx = width - 1 - dy;
- ny = dx;
- },
- @enumToInt(aoc.Dir.Name.SOUTH) => {
- nx = width - 1 - dx;
- ny = width - 1 - dy;
- },
- @enumToInt(aoc.Dir.Name.WEST) => {
- nx = dy;
- ny = width - 1 - dx;
- },
- else => {},
- }
- newdata.*[ny * width + nx] = v;
- }
-}
-
-fn flipData(data: []u1, width: u32, flip: Flip) void {
- switch (flip) {
- Flip.HOR => {
- var y: u32 = 0;
- while (y < width) : (y += 1) {
- std.mem.reverse(u1, data[y * width .. (y + 1) * width]);
- }
- },
- Flip.VERT => {
- var x: u32 = 0;
- while (x < width) : (x += 1) {
- var y: u32 = 0;
- while (y < width / 2) : (y += 1) {
- std.mem.swap(u1, &data[x + y * width], &data[x + (width - 1 - y) * width]);
- }
- }
- },
- else => {},
- }
-}
-
-fn manipulateAndPlace(allocator: *std.mem.Allocator, tiles: []Tile, grid: []?usize, grid_width: u32, p: aoc.Pos, tile_index: usize) !void {
- var tile = &tiles[tile_index];
-
- for (dirs) |_, rot| {
- for (flips) |flip| {
- // apply manipulation to only sides first for checking
- var sides = tile.sides;
- var tmp_sides = tile.sides;
- var adj = tile.adj;
- var tmp_adj = tile.adj;
- switch (flip) {
- Flip.HOR => {
- std.mem.reverse(u1, tmp_sides[@enumToInt(aoc.Dir.Name.NORTH)][0..]);
- std.mem.reverse(u1, tmp_sides[@enumToInt(aoc.Dir.Name.SOUTH)][0..]);
- tmp_sides[@enumToInt(aoc.Dir.Name.WEST)] = sides[@enumToInt(aoc.Dir.Name.EAST)];
- tmp_sides[@enumToInt(aoc.Dir.Name.EAST)] = sides[@enumToInt(aoc.Dir.Name.WEST)];
- std.mem.reverse(u1, tmp_sides[@enumToInt(aoc.Dir.Name.EAST)][0..]);
- std.mem.reverse(u1, tmp_sides[@enumToInt(aoc.Dir.Name.WEST)][0..]);
- std.mem.swap(?usize, &adj[@enumToInt(aoc.Dir.Name.EAST)], &adj[@enumToInt(aoc.Dir.Name.WEST)]);
- },
- Flip.VERT => {
- std.mem.reverse(u1, tmp_sides[@enumToInt(aoc.Dir.Name.WEST)][0..]);
- std.mem.reverse(u1, tmp_sides[@enumToInt(aoc.Dir.Name.EAST)][0..]);
- tmp_sides[@enumToInt(aoc.Dir.Name.NORTH)] = sides[@enumToInt(aoc.Dir.Name.SOUTH)];
- tmp_sides[@enumToInt(aoc.Dir.Name.SOUTH)] = sides[@enumToInt(aoc.Dir.Name.NORTH)];
- std.mem.reverse(u1, tmp_sides[@enumToInt(aoc.Dir.Name.NORTH)][0..]);
- std.mem.reverse(u1, tmp_sides[@enumToInt(aoc.Dir.Name.SOUTH)][0..]);
- std.mem.swap(?usize, &adj[@enumToInt(aoc.Dir.Name.NORTH)], &adj[@enumToInt(aoc.Dir.Name.SOUTH)]);
- },
- else => {},
- }
- sides = tmp_sides;
-
- for (dirs) |_, i| {
- tmp_sides[i] = sides[aoc.Dir.nextCCW(i, rot)];
- tmp_adj[i] = adj[aoc.Dir.nextCCW(i, rot)];
- }
-
- std.debug.print("\nROT: {}\n", .{rot});
- std.debug.print("FLIP: {}\n", .{flip});
- std.debug.print("SIDES: \n", .{});
- for (tmp_sides) |side| {
- printTileSlice(side[0..]);
- std.debug.print("\n", .{});
- }
- const valid = checkSides(tiles, grid, grid_width, p, tmp_adj, tmp_sides);
-
- // now apply manipulations to image data
- if (valid) {
- // for (tile.sides) |side| {
- // printTileSlice(side[0..]);
- // std.debug.print("\n", .{});
- // }
- std.debug.print("{} {} {}\n", .{ tile.id, flip, rot });
- printTile(tile.data[0..], tile_width);
- std.debug.print("\n", .{});
- tile.sides = tmp_sides;
- tile.pos = p;
- tile.adj = tmp_adj;
- grid[@intCast(u32, p.y * @intCast(i64, grid_width) + p.x)] = tile_index;
-
- flipData(tile.data[0..], tile_width, flip);
-
- var newdata = try allocator.alloc(u1, tile_width * tile_width);
- defer allocator.free(newdata);
-
- rotateData(&newdata, tile.data[0..], tile_width, rot);
- std.mem.copy(u1, tile.data[0..], newdata);
- return;
- }
- }
- }
- return aoc.Error.InvalidInput;
-}
-
-fn part1(allocator: *std.mem.Allocator, input: []u8, args: [][]u8) !void {
- var tiles = std.ArrayList(Tile).init(allocator);
- defer tiles.deinit();
-
- try parseTiles(&tiles, input);
-
- matchTiles(&tiles);
-
- var answer: u64 = 1;
- for (tiles.items) |tile| {
- var unknown: u32 = 0;
- for (tile.adj) |v| {
- unknown += @boolToInt(v == null);
- }
- if (unknown == 2) answer *= tile.id;
- }
-
- std.debug.print("{}\n", .{answer});
-}
-
-fn part2(allocator: *std.mem.Allocator, input: []u8, args: [][]u8) !void {
- var tiles = std.ArrayList(Tile).init(allocator);
- defer tiles.deinit();
-
- try parseTiles(&tiles, input);
-
- matchTiles(&tiles);
-
- var grid = try allocator.alloc(?usize, tiles.items.len);
- defer allocator.free(grid);
- var grid_width = @intCast(u32, std.math.sqrt(tiles.items.len));
-
- var left = std.ArrayList(usize).init(allocator);
- defer left.deinit();
-
- for (tiles.items) |_, tile_index| {
- try left.append(tile_index);
- }
-
- // add a corner as first item to add onto
- for (tiles.items) |tile, tile_index| {
- var unknown: u32 = 0;
- for (tile.adj) |v| {
- unknown += @boolToInt(v == null);
- }
- if (unknown == 2) {
- try manipulateAndPlace(allocator, tiles.items, grid, grid_width, aoc.Pos{ .x = 0, .y = 0 }, tile_index);
- _ = left.swapRemove(tile_index);
- break;
- }
- }
-
- // find adjacents and manipulate until they fit
- next_tile: while (left.items.len > 0) {
- if (aoc.debug) printGrid(tiles.items, grid, grid_width);
-
- for (grid) |_, gi| {
- std.debug.print("POS {}\n", .{gi});
- const tile_index: ?usize = grid[gi] orelse continue;
- std.debug.print("POS {} YES\n", .{gi});
-
- var placed = &tiles.items[tile_index.?];
- for (placed.adj) |want, dir| {
- if (want == null) continue;
- // std.debug.print("LOOKING FOR {}\n", .{want.?});
- // for (left.items) |item| {
- // std.debug.print("> {}\n", .{item});
- // }
- if (std.mem.indexOfScalar(usize, left.items, want.?)) |left_index| {
- const new_index = left.items[left_index];
- const new_tile = tiles.items[new_index];
- var npos = placed.pos.add(dirs[dir]);
- std.debug.print("TRYING TO PLACE {} NEW AT: {} {}\n", .{ new_tile.id, npos.x, npos.y });
-
- try manipulateAndPlace(allocator, tiles.items, grid, grid_width, npos, new_index);
-
- _ = left.swapRemove(left_index);
- continue :next_tile;
- }
- }
- }
- return aoc.Error.InvalidInput;
- }
-
- if (aoc.debug) printGrid(tiles.items, grid, grid_width);
-
- // convert grid to image
- var image = try allocator.alloc(u1, grid.len * (tile_width - 2) * (tile_width - 2));
- defer allocator.free(image);
-
- const image_width = grid_width * (tile_width - 2);
- var y: u32 = 0;
- while (y < grid_width) : (y += 1) {
- var x: u32 = 0;
- while (x < grid_width) : (x += 1) {
- var tile = tiles.items[grid[y * grid_width + x].?];
- var doff = (y * grid_width * (tile_width - 2) + x) * (tile_width - 2);
- var dy: u32 = 1;
- while (dy < tile_width - 1) : (dy += 1) {
- var dx: u32 = 1;
- while (dx < tile_width - 1) : (dx += 1) {
- image[doff + (dy - 1) * image_width + (dx - 1)] = tile.data[dy * tile_width + dx];
- }
- }
- }
- }
-
- y = 0;
- while (y < grid_width * (tile_width - 2)) : (y += 1) {
- printTileSlice(image[y * grid_width * (tile_width - 2) .. (y + 1) * grid_width * (tile_width - 2)]);
- std.debug.print("\n", .{});
- }
-
- // rotate image till we find a sea monster
- var image_copy = try allocator.dupe(u1, image);
- defer allocator.free(image_copy);
-
- var rot: usize = 0;
- while (rot < 4) : (rot += 1) {
- for (flips) |flip| {
- flipData(image, image_width, flip);
- rotateData(&image_copy, image, image_width, rot);
-
- y = 0;
- var count: u32 = 0;
- while (y < image_width - seamonster.len) : (y += 1) {
- var x: u32 = 0;
- check_next: while (x < image_width - seamonster[0].len) : (x += 1) {
- var sy: u32 = 0;
- while (sy < seamonster.len) : (sy += 1) {
- var sx: u32 = 0;
- while (sx < seamonster[0].len) : (sx += 1) {
- if (seamonster[sy][sx] == '#' and image_copy[(y + sy) * image_width + (x + sx)] != 1)
- continue :check_next;
- }
- }
- count += 1;
- }
- }
-
- if (count > 0) {
- var image_count = std.mem.count(u1, image_copy, ([_]u1{1})[0..]);
- var seamonster_count: usize = 0;
- var sy: u32 = 0;
- while (sy < seamonster.len) : (sy += 1) {
- seamonster_count += std.mem.count(u8, seamonster[sy], "#");
- }
- std.debug.print("{}\n", .{image_count - count * seamonster_count});
- return;
- }
- }
- }
-}
-
-pub const main = aoc.gen_main(part1, part2);
diff --git a/src/day21/main.zig b/src/day21/main.zig
@@ -1,180 +0,0 @@
-const std = @import("std");
-const aoc = @import("aoc");
-
-const hasher = std.hash.CityHash32;
-const IngredientInfo = struct {
- count: u32,
-};
-const Pair = struct { ingredient: []const u8, allergen: []const u8 };
-
-fn freeListmap(listmap: *std.AutoHashMap(u32, std.ArrayList(u32))) void {
- var mapit = listmap.iterator();
- while (mapit.next()) |kv| {
- kv.value.deinit();
- }
- listmap.deinit();
-}
-
-fn getAllergen(allergens: *std.AutoHashMap(u32, std.ArrayList(u32)), ingredient: u32) ?u32 {
- var allergenit = allergens.iterator();
- while (allergenit.next()) |alg| {
- if (alg.value.items.len == 1 and alg.value.items[0] == ingredient)
- return alg.key;
- }
- return null;
-}
-
-fn updateAllergens(allocator: *std.mem.Allocator, allergens: *std.AutoHashMap(u32, std.ArrayList(u32)), allergen: u32) !void {
- var next = std.ArrayList(u32).init(allocator);
- defer next.deinit();
-
- try next.append(allergen);
-
- while (next.items.len > 0) {
- const key = next.items[0];
- var ingredient = allergens.getEntry(key).?.value.items[0];
- var mapit = allergens.iterator();
- while (mapit.next()) |alg| {
- if (alg.key == key) continue;
- const ind = std.mem.indexOfScalar(u32, alg.value.items, ingredient);
- if (ind != null) {
- _ = alg.value.swapRemove(ind.?);
- if (alg.value.items.len == 1) {
- try next.append(alg.key);
- }
- }
- }
- _ = next.swapRemove(0);
- }
-}
-
-fn parseAllergens(allocator: *std.mem.Allocator, allergens: *std.AutoHashMap(u32, std.ArrayList(u32)), unhash: *std.AutoHashMap(u32, []const u8), ingredient_counts: *std.AutoHashMap(u32, u32), input: []const u8) !void {
- var ingredients = std.ArrayList(u32).init(allocator);
- defer ingredients.deinit();
-
- var lineit = std.mem.tokenize(input, "\n");
- while (lineit.next()) |line| {
- var allergen = false;
-
- try ingredients.resize(0);
-
- var spaceit = std.mem.tokenize(line, " ");
- while (spaceit.next()) |word| {
- if (std.mem.eql(u8, word, "(contains")) {
- allergen = true;
- continue;
- }
-
- if (allergen) {
- const allergen_name = if (word[word.len - 1] == ')' or word[word.len - 1] == ',') word[0 .. word.len - 1] else word;
- const allergen_hash = hasher.hash(allergen_name);
- try unhash.put(allergen_hash, allergen_name);
- var algentry = allergens.getEntry(allergen_hash);
- if (algentry) |algent| {
- var i: u32 = 0;
- while (i < algent.value.items.len) {
- if (std.mem.indexOfScalar(u32, ingredients.items, algent.value.items[i]) == null) {
- _ = algent.value.swapRemove(i);
- } else {
- i += 1;
- }
- }
-
- if (algent.value.items.len == 1) {
- try updateAllergens(allocator, allergens, algent.key);
- }
- } else {
- var copy = std.ArrayList(u32).init(allocator);
- errdefer copy.deinit();
- for (ingredients.items) |ing| {
- if (getAllergen(allergens, ing) == null) {
- try copy.append(ing);
- }
- }
- try allergens.put(allergen_hash, copy);
- }
- } else {
- const ingredient_hash = hasher.hash(word);
- try unhash.put(ingredient_hash, word);
- try ingredients.append(ingredient_hash);
- const entry = ingredient_counts.getEntry(ingredient_hash);
- if (entry == null) {
- try ingredient_counts.put(ingredient_hash, 1);
- } else {
- entry.?.value += 1;
- }
- }
- }
- }
-}
-
-fn ascendingAllergen(ctx: void, p1: Pair, p2: Pair) bool {
- var i: u32 = 0;
- while (i < std.math.min(p1.allergen.len, p2.allergen.len) and p1.allergen[i] == p2.allergen[i]) : (i += 1) {}
- return p1.allergen[i] < p2.allergen[i];
-}
-
-fn part1(allocator: *std.mem.Allocator, input: []u8, args: [][]u8) !void {
- var allergens = std.AutoHashMap(u32, std.ArrayList(u32)).init(allocator);
- defer freeListmap(&allergens);
-
- var ingredient_counts = std.AutoHashMap(u32, u32).init(allocator);
- defer ingredient_counts.deinit();
-
- var unhash = std.AutoHashMap(u32, []const u8).init(allocator);
- defer unhash.deinit();
-
- try parseAllergens(allocator, &allergens, &unhash, &ingredient_counts, input);
-
- var answer: u32 = 0;
-
- var algit = allergens.iterator();
- while (algit.next()) |alg| {
- std.debug.print("{} - ", .{alg.key});
- for (alg.value.items) |v| {
- std.debug.print("{} ", .{v});
- }
- std.debug.print("\n", .{});
- }
-
- var mapit = ingredient_counts.iterator();
- while (mapit.next()) |kv| {
- if (getAllergen(&allergens, kv.key) == null) answer += kv.value;
- }
-
- std.debug.print("{}\n", .{answer});
-}
-
-fn part2(allocator: *std.mem.Allocator, input: []u8, args: [][]u8) !void {
- var allergens = std.AutoHashMap(u32, std.ArrayList(u32)).init(allocator);
- defer freeListmap(&allergens);
-
- var ingredient_counts = std.AutoHashMap(u32, u32).init(allocator);
- defer ingredient_counts.deinit();
-
- var unhash = std.AutoHashMap(u32, []const u8).init(allocator);
- defer unhash.deinit();
-
- try parseAllergens(allocator, &allergens, &unhash, &ingredient_counts, input);
-
- var pairs = std.ArrayList(Pair).init(allocator);
- defer pairs.deinit();
-
- var mapit = ingredient_counts.iterator();
- while (mapit.next()) |kv| {
- const alg = getAllergen(&allergens, kv.key);
- if (alg != null) {
- try pairs.append(Pair{ .ingredient = unhash.get(kv.key).?, .allergen = unhash.get(alg.?).? });
- }
- }
-
- std.sort.sort(Pair, pairs.items, {}, ascendingAllergen);
-
- for (pairs.items) |p, i| {
- if (i > 0) std.debug.print(",", .{});
- std.debug.print("{}", .{p.ingredient});
- }
- std.debug.print("\n", .{});
-}
-
-pub const main = aoc.gen_main(part1, part2);
diff --git a/src/day22/main.zig b/src/day22/main.zig
@@ -1,180 +0,0 @@
-const std = @import("std");
-const aoc = @import("aoc");
-
-const Player = enum { P1, P2 };
-const GameResult = struct {
- score: u64, winner: Player
-};
-
-fn parseInput(input: []u8, decks: [2]*std.ArrayList(u32)) !void {
- var partit = std.mem.split(input, "\n\n");
- var decknum: u32 = 0;
- while (partit.next()) |part| : (decknum += 1) {
- if (decknum == 2) break;
- var lineit = std.mem.tokenize(part, "\n");
- _ = lineit.next();
- while (lineit.next()) |line| {
- try decks[decknum].append(try std.fmt.parseInt(u32, line, 10));
- }
- }
- if (decknum < 2) return aoc.Error.InvalidInput;
-}
-
-fn printDeck(deck: *std.ArrayList(u32)) void {
- for (deck.items) |v, i| {
- if (i > 0) std.debug.print(", ", .{});
- std.debug.print("{}", .{v});
- }
-}
-
-fn printRoundInfo(roundnum: u32, decks: [2]*std.ArrayList(u32)) void {
- std.debug.print("\n-- ROUND {} --\n", .{roundnum});
- std.debug.print("Player 1's deck: ", .{});
- printDeck(decks[0]);
- std.debug.print("\nPlayer 2's deck: ", .{});
- printDeck(decks[1]);
- std.debug.print("\n", .{});
-}
-
-fn printPickedCards(card1: u32, card2: u32) void {
- std.debug.print("Player 1 plays: {}\n", .{card1});
- std.debug.print("Player 2 plays: {}\n", .{card2});
-}
-
-fn calcScore(deck: *std.ArrayList(u32)) u64 {
- var score: u64 = 0;
- for (deck.items) |v, i| {
- score += v * (deck.items.len - i);
- }
- return score;
-}
-
-fn copyList(allocator: *std.mem.Allocator, list: []u32) !std.ArrayList(u32) {
- var newlist = std.ArrayList(u32).init(allocator);
- errdefer newlist.deinit();
-
- for (list) |v| {
- try newlist.append(v);
- }
-
- return newlist;
-}
-
-fn part1Round(
- allocator: *std.mem.Allocator,
- roundnum: u32,
- decks: [2]*std.ArrayList(u32),
-) anyerror!void {
- if (aoc.debug) printRoundInfo(roundnum, decks);
- const card1: u32 = decks[0].orderedRemove(0);
- const card2: u32 = decks[1].orderedRemove(0);
- if (aoc.debug) printPickedCards(card1, card2);
- if (card1 > card2) {
- if (aoc.debug) std.debug.print("Player1 wins\n", .{});
- try decks[0].append(card1);
- try decks[0].append(card2);
- } else if (card2 > card1) {
- if (aoc.debug) std.debug.print("Player2 wins\n", .{});
- try decks[1].append(card2);
- try decks[1].append(card1);
- } else return aoc.Error.InvalidInput;
-}
-
-fn part2Round(
- allocator: *std.mem.Allocator,
- roundnum: u32,
- decks: [2]*std.ArrayList(u32),
-) anyerror!void {
- if (aoc.debug) printRoundInfo(roundnum, decks);
- const card1: u32 = decks[0].orderedRemove(0);
- const card2: u32 = decks[1].orderedRemove(0);
- if (aoc.debug) printPickedCards(card1, card2);
-
- var winner = @intToEnum(Player, @boolToInt(card2 > card1));
- if (card1 <= decks[0].items.len and card2 <= decks[1].items.len) {
- if (aoc.debug) std.debug.print("\nStarting subgame..\n", .{});
- var tmp_deck1 = try copyList(allocator, decks[0].items[0..card1]);
- defer tmp_deck1.deinit();
-
- var tmp_deck2 = try copyList(allocator, decks[1].items[0..card2]);
- defer tmp_deck2.deinit();
-
- const result = try playGame(allocator, [2]*std.ArrayList(u32){ &tmp_deck1, &tmp_deck2 }, part2Round);
- winner = result.winner;
- if (aoc.debug) {
- const wp: u32 = if (winner == Player.P1) 1 else 2;
- std.debug.print("Player{} wins the subgame\n...anyway, back to previous game\n\n", .{wp});
- }
- }
-
- if (winner == Player.P1) {
- if (aoc.debug) std.debug.print("Player1 wins the round\n", .{});
- try decks[0].append(card1);
- try decks[0].append(card2);
- } else if (winner == Player.P2) {
- if (aoc.debug) std.debug.print("Player2 wins the round\n", .{});
- try decks[1].append(card2);
- try decks[1].append(card1);
- } else return aoc.Error.InvalidInput;
-}
-
-fn playGame(
- allocator: *std.mem.Allocator,
- decks: [2]*std.ArrayList(u32),
- roundFunc: fn (
- alloc: *std.mem.Allocator,
- num: u32,
- decks: [2]*std.ArrayList(u32),
- ) anyerror!void,
-) !GameResult {
- var ctxstack = std.ArrayList(u64).init(allocator);
- defer ctxstack.deinit();
-
- var roundnum: u32 = 1;
- while (decks[0].items.len > 0 and decks[1].items.len > 0) : (roundnum += 1) {
- try roundFunc(allocator, roundnum, decks);
-
- var hash: u64 = calcScore(decks[0]) + 100000 * calcScore(decks[1]);
- if (std.mem.indexOfScalar(u64, ctxstack.items, hash) != null) {
- return GameResult{ .score = calcScore(decks[0]), .winner = Player.P1 };
- }
-
- try ctxstack.append(hash);
- }
-
- var nonempty = if (decks[0].items.len != 0) decks[0] else decks[1];
- return GameResult{
- .score = calcScore(nonempty),
- .winner = if (nonempty == decks[0]) Player.P1 else Player.P2,
- };
-}
-
-fn part1(allocator: *std.mem.Allocator, input: []u8, args: [][]u8) !void {
- var deck1 = std.ArrayList(u32).init(allocator);
- defer deck1.deinit();
-
- var deck2 = std.ArrayList(u32).init(allocator);
- defer deck2.deinit();
-
- const decks = [2]*std.ArrayList(u32){ &deck1, &deck2 };
- try parseInput(input, decks);
-
- const result = try playGame(allocator, decks, part1Round);
- std.debug.print("{}\n", .{result.score});
-}
-
-fn part2(allocator: *std.mem.Allocator, input: []u8, args: [][]u8) !void {
- var deck1 = std.ArrayList(u32).init(allocator);
- defer deck1.deinit();
-
- var deck2 = std.ArrayList(u32).init(allocator);
- defer deck2.deinit();
-
- const decks = [2]*std.ArrayList(u32){ &deck1, &deck2 };
- try parseInput(input, decks);
-
- const result = try playGame(allocator, decks, part2Round);
- std.debug.print("{}\n", .{result.score});
-}
-
-pub const main = aoc.gen_main(part1, part2);
diff --git a/src/day23/main.zig b/src/day23/main.zig
@@ -1,180 +0,0 @@
-const std = @import("std");
-const aoc = @import("aoc");
-
-// Links in this list are arranges in a circle
-const RingLink = struct {
- data: u32,
- next: *RingLink,
- const Self = @This();
-
- pub fn insertNext(self: *Self, link: *RingLink) void {
- link.next = self.next;
- self.next = link;
- }
-
- pub fn popNext(self: *Self) !*Self {
- const nlink = self.next;
- if (nlink == self) return error.EmptyRingList;
- self.next = nlink.next;
- return nlink;
- }
-
- pub fn length(self: *Self) usize {
- var count: usize = 1;
- var link = self.next;
- while (link != self) : (link = link.next) {
- count += 1;
- }
- return count;
- }
-
- pub fn advance(self: *Self, count: usize) *RingLink {
- var link = self;
- var counter: usize = 0;
- while (counter < count) : (link = link.next) {
- counter += 1;
- }
- return link;
- }
-};
-
-fn printLinks(start: *RingLink, end: *RingLink, skipfirst: bool) void {
- var link = start;
- var b = skipfirst;
- while (b or link != end) : (link = link.next) {
- b = false;
- std.debug.print("{} ", .{link.data});
- }
-}
-
-fn parseInput(input: []const u8, lookup: []RingLink, list: *?*RingLink) !u32 {
- var max: u32 = 0;
- var link: *RingLink = undefined;
- for (input) |c, i| {
- if (c == '\n') break;
- const v = try std.fmt.parseInt(u32, input[i .. i + 1], 10);
- if (v > max) max = v;
- if (list.* == null) {
- list.* = &lookup[v];
- link = list.*.?;
- link.next = link;
- } else {
- link.insertNext(&lookup[v]);
- link = link.next;
- }
- }
- return max;
-}
-
-fn doRound(list: *RingLink, len: u32, lookup: []RingLink, current: **RingLink, max: u32, round: usize) !void {
- var target = (current.*.data + max - 2) % max + 1;
- var k: usize = 0;
- var check = current.*.next;
- while (k < 9) : (k += 1) {
- if (check.data == target)
- target = (target + max - 2) % max + 1;
-
- check = if (k % 3 == 0) current.*.next else check.next;
- }
- var closest = &lookup[target];
-
- if (aoc.debug) {
- std.debug.print("\n-- move {} --\ncups:", .{round});
-
- if (aoc.debuglvl == 1) {
- var start = current.*.advance(len - ((round - 1) % len));
- var link = start;
- while (true) {
- if (link == current.*) {
- std.debug.print(" ({})", .{link.data});
- } else {
- std.debug.print(" {} ", .{link.data});
- }
- link = link.next;
- if (link == start) break;
- }
- std.debug.print("\n", .{});
- } else {
- std.debug.print("\n{} {} {}\n", .{ current.*.data, target, closest.data });
- std.debug.print(".. ", .{});
- printLinks(current.*, current.*.next.next.next.next, false);
- std.debug.print("..\n.. ", .{});
- printLinks(closest, closest.next.next.next.next, false);
- std.debug.print("..\n", .{});
- }
- }
-
- var i: usize = 0;
- while (i < 3) : (i += 1) {
- const poplink = try current.*.popNext();
- closest.insertNext(poplink);
- closest = poplink;
- }
-
- current.* = current.*.next;
-}
-
-fn createLookup(allocator: *std.mem.Allocator, len: usize) ![]RingLink {
- var lookup = try allocator.alloc(RingLink, len + 1);
- errdefer allocator.free(lookup);
-
- var i: usize = 1;
- while (i <= len) : (i += 1) {
- lookup[i] = RingLink{ .data = @intCast(u32, i), .next = undefined };
- }
-
- return lookup;
-}
-
-fn part1(allocator: *std.mem.Allocator, input: []u8, args: [][]u8) !void {
- var lookup = try createLookup(allocator, 9);
- defer allocator.free(lookup);
-
- var list: ?*RingLink = null;
- const max = try parseInput(input, lookup, &list);
- if (list == null) return aoc.Error.InvalidInput;
- const real_len = @intCast(u32, list.?.length());
-
- var round: usize = 0;
- var current = list.?;
- while (round < 100) : (round += 1) {
- try doRound(list.?, real_len, lookup, ¤t, max, round + 1);
- }
-
- var start = &lookup[1];
- var link = start.next;
- while (link != start) : (link = link.next) {
- std.debug.print("{}", .{link.data});
- }
- std.debug.print("\n", .{});
-}
-
-fn part2(allocator: *std.mem.Allocator, input: []u8, args: [][]u8) !void {
- var lookup = try createLookup(allocator, 1000000);
- defer allocator.free(lookup);
-
- var list: ?*RingLink = null;
- const max = try parseInput(input, lookup, &list);
- if (list == null) return aoc.Error.InvalidInput;
- const real_len = list.?.length();
-
- var end = list.?.advance(real_len - 1);
- var i = real_len + 1;
- while (i <= 1000000) : (i += 1) {
- end.insertNext(&lookup[i]);
- end = end.next;
- }
-
- var round: usize = 0;
- var current = list.?;
- while (round < 10000000) : (round += 1) {
- if (round % 1000000 == 0) std.debug.print(".", .{});
- try doRound(list.?, 1000000, lookup, ¤t, 1000000, round + 1);
- }
- std.debug.print("\n", .{});
-
- var link = (&lookup[1]).next;
- std.debug.print("{} * {} = {}\n", .{ @intCast(u64, link.data), @intCast(u64, link.next.data), @intCast(u64, link.data) * @intCast(u64, link.next.data) });
-}
-
-pub const main = aoc.gen_main(part1, part2);
diff --git a/src/day24/main.zig b/src/day24/main.zig
@@ -1,121 +0,0 @@
-const std = @import("std");
-const aoc = @import("aoc");
-
-const Color = enum { BLACK, WHITE };
-const Dir = enum { E, SE, SW, W, NW, NE };
-const dirs = [_]aoc.Pos{
- aoc.Pos{ .x = 2, .y = 0 },
- aoc.Pos{ .x = 1, .y = -1 },
- aoc.Pos{ .x = -1, .y = -1 },
- aoc.Pos{ .x = -2, .y = 0 },
- aoc.Pos{ .x = -1, .y = 1 },
- aoc.Pos{ .x = 1, .y = 1 },
-};
-const tokens = [_][]const u8{
- "e",
- "se",
- "sw",
- "w",
- "nw",
- "ne",
-};
-const Tile = struct {
- color: Color,
-};
-
-fn parseInput(tiles: *std.AutoHashMap(aoc.Pos, Tile), input: []const u8) !void {
- var lineit = std.mem.tokenize(input, "\n");
- while (lineit.next()) |line| {
- var pos = aoc.Pos{ .x = 0, .y = 0 };
-
- var i: usize = 0;
- while (i < line.len) {
- var dir = for (tokens) |tok, ti| {
- if (i + tok.len > line.len) continue;
- if (std.mem.eql(u8, tok, line[i .. i + tok.len])) {
- i += tok.len;
- break @intToEnum(Dir, @intCast(u3, ti));
- }
- } else return aoc.Error.InvalidInput;
- if (aoc.debug) std.debug.print("{} ", .{dir});
- pos = pos.add(dirs[@enumToInt(dir)]);
- }
- if (aoc.debug) std.debug.print("=> {} {}\n", .{ pos.x, pos.y });
-
- var tile = tiles.getEntry(pos);
- if (tile != null) {
- tile.?.value.color = if (tile.?.value.color == Color.WHITE) Color.BLACK else Color.WHITE;
- } else {
- try tiles.put(pos, Tile{ .color = Color.BLACK });
- }
- }
-}
-
-fn applyRule(pos: aoc.Pos, before: *std.AutoHashMap(aoc.Pos, Tile), after: *std.AutoHashMap(aoc.Pos, Tile)) !void {
- if (after.contains(pos)) return;
- const old_tile = before.get(pos);
- const old_color = if (old_tile == null) Color.WHITE else old_tile.?.color;
-
- var adj: u32 = 0;
- for (dirs) |d| {
- const tile = before.get(pos.add(d));
- if (tile != null and tile.?.color == Color.BLACK) adj += 1;
- }
-
- if (adj == 2 and old_color == Color.WHITE) {
- try after.put(pos, Tile{ .color = Color.BLACK });
- } else if ((adj == 0 or adj > 2) and old_color == Color.BLACK) {
- try after.put(pos, Tile{ .color = Color.WHITE });
- } else {
- try after.put(pos, Tile{ .color = old_color });
- }
-}
-
-fn doRound(allocator: *std.mem.Allocator, tiles: *std.AutoHashMap(aoc.Pos, Tile)) !void {
- var result = std.AutoHashMap(aoc.Pos, Tile).init(allocator);
- defer result.deinit();
-
- var mapit = tiles.iterator();
- while (mapit.next()) |kv| {
- for (dirs) |d| {
- try applyRule(kv.key.add(d), tiles, &result);
- }
- try applyRule(kv.key, tiles, &result);
- }
-
- std.mem.swap(std.AutoHashMap(aoc.Pos, Tile), &result, tiles);
-}
-
-fn countBlack(tiles: *std.AutoHashMap(aoc.Pos, Tile)) u32 {
- var count: u32 = 0;
- var mapit = tiles.iterator();
- while (mapit.next()) |kv| {
- if (kv.value.color == Color.BLACK) count += 1;
- }
- return count;
-}
-
-fn part1(allocator: *std.mem.Allocator, input: []u8, args: [][]u8) !void {
- var tiles = std.AutoHashMap(aoc.Pos, Tile).init(allocator);
- defer tiles.deinit();
-
- try parseInput(&tiles, input);
-
- std.debug.print("{}\n", .{countBlack(&tiles)});
-}
-
-fn part2(allocator: *std.mem.Allocator, input: []u8, args: [][]u8) !void {
- var tiles = std.AutoHashMap(aoc.Pos, Tile).init(allocator);
- defer tiles.deinit();
-
- try parseInput(&tiles, input);
-
- var round: usize = 0;
- while (round < 100) : (round += 1) {
- try doRound(allocator, &tiles);
- }
-
- std.debug.print("{}\n", .{countBlack(&tiles)});
-}
-
-pub const main = aoc.gen_main(part1, part2);
diff --git a/src/day25/main.zig b/src/day25/main.zig
@@ -1,56 +0,0 @@
-const std = @import("std");
-const aoc = @import("aoc");
-
-fn transform(subject_num: u64, loops: u64) u64 {
- var num: u64 = 1;
- var i: u64 = 0;
- while (i < loops) : (i += 1) {
- num *= subject_num;
- num %= 20201227;
- }
- return num;
-}
-
-fn bfLoops(subject_num: u64, pubkey: u64) ?u64 {
- var i: u64 = 0;
- var tmp: u64 = 1;
- while (i < ~@as(u64, 0)) : (i += 1) {
- if (tmp == pubkey) return i;
- tmp *= subject_num;
- tmp %= 20201227;
- }
- return null;
-}
-
-fn parseInput(door_pubkey: *u64, card_pubkey: *u64, input: []const u8) !void {
- var lineit = std.mem.tokenize(input, "\n");
- door_pubkey.* = try std.fmt.parseInt(u64, try aoc.assertV(lineit.next()), 10);
- card_pubkey.* = try std.fmt.parseInt(u64, try aoc.assertV(lineit.next()), 10);
-}
-
-fn part1(allocator: *std.mem.Allocator, input: []u8, args: [][]u8) !void {
- var door_pubkey: u64 = undefined;
- var card_pubkey: u64 = undefined;
-
- try parseInput(&door_pubkey, &card_pubkey, input);
-
- if (args.len == 0 or std.mem.eql(u8, args[0], "bf_door")) {
- if (bfLoops(7, door_pubkey)) |door_loops| {
- std.debug.print("{}\n", .{transform(card_pubkey, door_loops)});
- return;
- }
- } else if (args.len > 0 and std.mem.eql(u8, args[0], "bf_card")) {
- if (bfLoops(7, card_pubkey)) |card_loops| {
- std.debug.print("{}\n", .{transform(door_pubkey, card_loops)});
- return;
- }
- }
-}
-
-fn part2(allocator: *std.mem.Allocator, input: []u8, args: [][]u8) !void {
- var answer: u32 = 0;
-
- std.debug.print("{}\n", .{answer});
-}
-
-pub const main = aoc.gen_main(part1, part2);
diff --git a/src/day3/main.zig b/src/day3/main.zig
@@ -1,73 +0,0 @@
-const std = @import("std");
-const aoc = @import("aoc");
-
-const Entry = []u1;
-const Vector = struct {
- x: u16, y: u16
-};
-
-fn freeEntries(allocator: *std.mem.Allocator, entries: *const std.ArrayList(Entry)) void {
- for (entries.items) |entry| {
- allocator.free(entry);
- }
- entries.deinit();
-}
-
-fn parse(allocator: *std.mem.Allocator, input: []u8) !std.ArrayList(Entry) {
- var entries = std.ArrayList(Entry).init(allocator);
- errdefer freeEntries(allocator, &entries);
-
- var lineit = std.mem.tokenize(input, "\n");
- while (lineit.next()) |line| {
- var linemap: []u1 = try allocator.alloc(u1, line.len);
- errdefer allocator.free(linemap);
-
- for (line) |c, i| {
- linemap[i] = @boolToInt(c == '#');
- }
- try entries.append(linemap);
- }
-
- return entries;
-}
-
-fn treesHit(map: std.ArrayList(Entry), slope: Vector) u16 {
- var count: u16 = 0;
- var pos = Vector{ .x = 0, .y = 0 };
- while (pos.y < map.items.len - 1) {
- pos.x += slope.x;
- pos.y += slope.y;
-
- count += map.items[pos.y][pos.x % map.items[0].len];
- }
- return count;
-}
-
-fn part1(allocator: *std.mem.Allocator, input: []u8, args: [][]u8) !void {
- const map = try parse(allocator, input);
- defer freeEntries(allocator, &map);
-
- const answer = treesHit(map, Vector{ .x = 3, .y = 1 });
- std.debug.print("{}\n", .{answer});
-}
-
-fn part2(allocator: *std.mem.Allocator, input: []u8, args: [][]u8) !void {
- const map = try parse(allocator, input);
- defer freeEntries(allocator, &map);
-
- var answer: u32 = 1;
- const slopes = [_]Vector{
- Vector{ .x = 1, .y = 1 },
- Vector{ .x = 3, .y = 1 },
- Vector{ .x = 5, .y = 1 },
- Vector{ .x = 7, .y = 1 },
- Vector{ .x = 1, .y = 2 },
- };
- for (slopes) |slope| {
- answer *= treesHit(map, slope);
- }
-
- std.debug.print("{}\n", .{answer});
-}
-
-pub const main = aoc.gen_main(part1, part2);
diff --git a/src/day4/main.zig b/src/day4/main.zig
@@ -1,100 +0,0 @@
-const std = @import("std");
-const aoc = @import("aoc");
-
-fn intChecker(
- comptime min: u32,
- comptime max: u32,
- comptime len: ?u32,
- comptime suffix: ?[]const u8,
-) fn ([]const u8) bool {
- const impl = struct {
- fn check(input: []const u8) bool {
- var parsed = input;
- if (suffix) |suf| {
- if (!std.mem.eql(u8, suf, input[(input.len - suf.len)..]))
- return false;
- parsed = input[0..(input.len - suf.len)];
- }
- if (len != null and parsed.len != len.?)
- return false;
- const val = std.fmt.parseInt(u32, parsed, 10) catch |x| {
- return false;
- };
- return (val >= min and val <= max);
- }
- };
- return impl.check;
-}
-
-fn combineOr(
- comptime f1: fn ([]const u8) bool,
- comptime f2: fn ([]const u8) bool,
-) fn ([]const u8) bool {
- const impl = struct {
- fn check(input: []const u8) bool {
- return f1(input) or f2(input);
- }
- };
- return impl.check;
-}
-
-fn isColorStr(input: []const u8) bool {
- if (input.len != 7) return false;
- _ = std.fmt.parseInt(u32, input[1..], 16) catch |x| {
- return false;
- };
- return input[0] == '#';
-}
-
-fn isEyeColor(input: []const u8) bool {
- const valids = "amb blu brn gry grn hzl oth";
- return std.mem.indexOf(u8, valids[0..], input) != null;
-}
-
-fn countValids(allocator: *std.mem.Allocator, input: []u8, validate: bool) !u16 {
- var entryit = std.mem.split(input, "\n\n");
- const required_keys = [_][]const u8{ "byr", "iyr", "eyr", "hgt", "hcl", "ecl", "pid", "cid" };
- const validation_funcs = [required_keys.len]?fn ([]const u8) bool{
- intChecker(1920, 2002, 4, null),
- intChecker(2010, 2020, 4, null),
- intChecker(2020, 2030, 4, null),
- combineOr(comptime intChecker(150, 193, 3, "cm"), comptime intChecker(59, 76, 2, "in")),
- isColorStr,
- isEyeColor,
- intChecker(0, 999999999, 9, null),
- null,
- };
- var count: u16 = 0;
- entryloop: while (entryit.next()) |entry| {
- const key_mask = [required_keys.len]u8{ 1, 1, 1, 1, 1, 1, 1, 'X' };
- var present = [required_keys.len]u1{ 0, 0, 0, 0, 0, 0, 0, 0 };
- var partit = std.mem.tokenize(entry, ": \n");
- while (partit.next()) |key| {
- const value = partit.next().?;
- for (required_keys) |ckey, i| {
- if (std.mem.eql(u8, key, ckey)) {
- if (validate and validation_funcs[i] != null) {
- if (!validation_funcs[i].?(value)) continue :entryloop;
- }
- present[i] = 1;
- }
- }
- }
- for (key_mask) |k, i| {
- if (key_mask[i] != 'X' and present[i] != key_mask[i])
- continue :entryloop;
- }
- count += 1;
- }
- return count;
-}
-
-fn part1(allocator: *std.mem.Allocator, input: []u8, args: [][]u8) !void {
- std.debug.print("{}\n", .{try countValids(allocator, input, false)});
-}
-
-fn part2(allocator: *std.mem.Allocator, input: []u8, args: [][]u8) !void {
- std.debug.print("{}\n", .{try countValids(allocator, input, true)});
-}
-
-pub const main = aoc.gen_main(part1, part2);
diff --git a/src/day5/main.zig b/src/day5/main.zig
@@ -1,46 +0,0 @@
-const std = @import("std");
-const aoc = @import("aoc");
-
-const row_count = 128;
-const col_count = 8;
-
-// Input is coded in a way that we can do an implicit binary search by replacing
-// identifiers for the lower half with "0" and for the upper halb with "1"
-// See commit <f1b717029cf3262c1fa2760124af258924d668da> for actual binary search
-
-fn code2Id(input: []const u8) !u32 {
- var value: u32 = 0;
- for (input) |c|
- value = value * 2 + @boolToInt(c == 'B' or c == 'R');
- return value;
-}
-
-fn part1(allocator: *std.mem.Allocator, input: []u8, args: [][]u8) !void {
- var lineit = std.mem.tokenize(input, "\n");
- var answer: u32 = 0;
- while (lineit.next()) |line| {
- const id = try code2Id(line[0..10]);
- answer = std.math.max(answer, id);
- }
- std.debug.print("{}\n", .{answer});
-}
-
-fn part2(allocator: *std.mem.Allocator, input: []u8, args: [][]u8) !void {
- var lineit = std.mem.tokenize(input, "\n");
- var seats = [_]u1{0} ** (row_count * col_count);
- var min: u32 = std.math.inf_u32;
- while (lineit.next()) |line| {
- const id = try code2Id(line);
- min = std.math.min(min, id);
- seats[id] = 1;
- }
-
- for (seats[min..]) |b, i| {
- if (seats[min + i] == 0) {
- std.debug.print("{}\n", .{min + i});
- break;
- }
- }
-}
-
-pub const main = aoc.gen_main(part1, part2);
diff --git a/src/day6/main.zig b/src/day6/main.zig
@@ -1,33 +0,0 @@
-const std = @import("std");
-const aoc = @import("aoc");
-
-fn part1(allocator: *std.mem.Allocator, input: []u8, args: [][]u8) !void {
- var entryit = std.mem.split(input, "\n\n");
- var answer: u32 = 0;
- while (entryit.next()) |group| {
- var seen = [_]u1{0} ** 256;
- for (group) |c| {
- if (c == ' ' or c == '\n') continue;
- answer += @boolToInt(seen[c] == 0);
- seen[c] = 1;
- }
- }
- std.debug.print("{}\n", .{answer});
-}
-
-fn part2(allocator: *std.mem.Allocator, input: []u8, args: [][]u8) !void {
- var entryit = std.mem.split(input, "\n\n");
- var answer: u32 = 0;
- while (entryit.next()) |group| {
- var count = [_]u16{0} ** 256;
- var members: u16 = 0;
- var memberit = std.mem.tokenize(group, "\n ");
- while (memberit.next()) |member| : (members += 1) {
- for (member) |c| count[c] += 1;
- }
- for (count) |v| answer += @boolToInt(v == members);
- }
- std.debug.print("{}\n", .{answer});
-}
-
-pub const main = aoc.gen_main(part1, part2);
diff --git a/src/day7/main.zig b/src/day7/main.zig
@@ -1,105 +0,0 @@
-const std = @import("std");
-const aoc = @import("aoc");
-
-const testv = @ptrToInt(&target);
-const BagCount = struct {
- id: u64, count: u32
-};
-
-// null for 'not available' and errors for 'parsing failed'
-
-const BagRule = struct {
- outer: u64,
- inner_striter: std.mem.SplitIterator,
- const Self = @This();
-
- fn from(line: []const u8) !Self {
- var partit = std.mem.split(line[0 .. line.len - 1], " bags contain ");
- var outer = std.hash.CityHash64.hash(partit.next().?);
- var innerit = std.mem.split(partit.next().?, ", ");
- return Self{ .outer = outer, .inner_striter = innerit };
- }
-
- fn nextInner(self: *Self) !?BagCount {
- if (self.inner_striter.next()) |bagstr| {
- if (std.mem.eql(u8, bagstr[0..2], "no")) return null;
- const lastsep = std.mem.lastIndexOfScalar(u8, bagstr, ' ').?;
- const firstsep = std.mem.indexOfScalar(u8, bagstr, ' ').?;
- const count = try std.fmt.parseInt(u32, bagstr[0..firstsep], 10);
- const id = std.hash.CityHash64.hash(bagstr[firstsep + 1 .. lastsep]);
- return BagCount{ .id = id, .count = count };
- } else {
- return null;
- }
- }
-};
-
-fn countBagsTotal(map: *std.AutoHashMap(u64, std.ArrayList(BagCount)), outer: u64) u64 {
- var sum: u64 = 0;
- if (map.get(outer)) |inner| {
- for (inner.items) |bag|
- sum += bag.count * (1 + countBagsTotal(map, bag.id));
- }
- return sum;
-}
-
-fn countParentTypes(map: *std.AutoHashMap(u64, std.ArrayList(u64)), inner: u64, seen: *std.ArrayList(u64)) anyerror!u64 {
- var sum: u64 = 0;
- if (map.get(inner)) |outer| {
- for (outer.items) |bagid| {
- if (std.mem.indexOfScalar(u64, seen.items, bagid) == null) {
- try seen.append(bagid);
- sum += 1 + try countParentTypes(map, bagid, seen);
- }
- }
- }
- return sum;
-}
-
-fn part1(allocator: *std.mem.Allocator, input: []u8, args: [][]u8) !void {
- var lineit = std.mem.tokenize(input, "\n");
- var map = std.AutoHashMap(u64, std.ArrayList(u64)).init(allocator);
- defer {
- var mapit = map.iterator();
- while (mapit.next()) |kv| kv.value.deinit();
- map.deinit();
- }
-
- while (lineit.next()) |line| {
- var rule = try BagRule.from(line);
- while (try rule.nextInner()) |inner| {
- if (map.get(inner.id) == null)
- try map.put(inner.id, std.ArrayList(u64).init(allocator));
- try map.getEntry(inner.id).?.*.value.append(rule.outer);
- }
- }
-
- const target = std.hash.CityHash64.hash("shiny gold");
- var seen = std.ArrayList(u64).init(allocator);
- defer seen.deinit();
- std.debug.print("{}\n", .{countParentTypes(&map, target, &seen)});
-}
-
-fn part2(allocator: *std.mem.Allocator, input: []u8, args: [][]u8) !void {
- var lineit = std.mem.tokenize(input, "\n");
- var map = std.AutoHashMap(u64, std.ArrayList(BagCount)).init(allocator);
- defer {
- var mapit = map.iterator();
- while (mapit.next()) |kv| kv.value.deinit();
- map.deinit();
- }
-
- const target = std.hash.CityHash64.hash("shiny gold");
- while (lineit.next()) |line| {
- var rule = try BagRule.from(line);
- if (map.get(rule.outer) == null)
- try map.put(rule.outer, std.ArrayList(BagCount).init(allocator));
- while (try rule.nextInner()) |bag| {
- try map.getEntry(rule.outer).?.*.value.append(bag);
- }
- }
-
- std.debug.print("{}\n", .{countBagsTotal(&map, target)});
-}
-
-pub const main = aoc.gen_main(part1, part2);
diff --git a/src/day8/main.zig b/src/day8/main.zig
@@ -1,60 +0,0 @@
-const std = @import("std");
-const aoc = @import("aoc");
-const Console = @import("console8").Console;
-
-fn runTillRepeat(console: *Console, instlist: *std.ArrayList(u64), swapon: ?u64) !void {
- while (try console.parseNext()) |*inst| {
- // std.debug.print("{:<5}: {} {}\n", .{ console.instructptr, inst.opcode, inst.argval });
- if (std.mem.indexOfScalar(u64, instlist.items, console.instructptr) != null) {
- return;
- }
- if (swapon != null and swapon.? == console.instructptr) {
- inst.opfunc = switch (inst.opfunc) {
- Console.jumpInstruction => Console.nopInstruction,
- Console.nopInstruction => Console.jumpInstruction,
- else => unreachable,
- };
- }
- try instlist.append(console.instructptr);
- try console.exec(inst);
- }
-}
-
-fn part1(allocator: *std.mem.Allocator, input: []u8, args: [][]u8) !void {
- var console = try Console.init(input, allocator);
- defer console.deinit();
-
- var instlist = std.ArrayList(u64).init(allocator);
- defer instlist.deinit();
-
- try runTillRepeat(&console, &instlist, null);
- std.debug.print("{}\n", .{console.accumulator});
-}
-
-fn part2(allocator: *std.mem.Allocator, input: []u8, args: [][]u8) !void {
- var console = try Console.init(input, allocator);
- defer console.deinit();
-
- var instlist = std.ArrayList(u64).init(allocator);
- defer instlist.deinit();
-
- try runTillRepeat(&console, &instlist, null);
-
- for (instlist.items) |inst| {
- if (std.mem.eql(u8, "acc"[0..3], console.instlist[inst][0..3]))
- continue;
-
- var sim_seen = std.ArrayList(u64).init(allocator);
- defer sim_seen.deinit();
-
- console.reset();
- //std.debug.print("Swapping instruction: {:<5}: {}\n", .{ inst, console.instlist[inst] });
- runTillRepeat(&console, &sim_seen, inst) catch {};
- if (console.jumpAddr == console.instlist.len or console.instructptr == console.instlist.len) {
- std.debug.print("{}\n", .{console.accumulator});
- break;
- }
- }
-}
-
-pub const main = aoc.gen_main(part1, part2);
diff --git a/src/day9/main.zig b/src/day9/main.zig
@@ -1,74 +0,0 @@
-const std = @import("std");
-const aoc = @import("aoc");
-
-const preamble_size = 25;
-
-fn preambleHasSum(preamble: []u64, target: u64) bool {
- for (preamble) |v1| {
- for (preamble) |v2| {
- if (v1 != v2 and v1 + v2 == target)
- return true;
- }
- }
- return false;
-}
-
-fn getInvalid(allocator: *std.mem.Allocator, input: []u8) !u64 {
- var preamble = std.ArrayList(u64).init(allocator);
- defer preamble.deinit();
-
- var i: u64 = 0;
- var numit = std.mem.tokenize(input, "\n");
- while (numit.next()) |numstr| : (i += 1) {
- const num = try std.fmt.parseInt(u64, numstr, 10);
- if (i > preamble_size) {
- if (!preambleHasSum(preamble.items, num)) {
- return num;
- }
- preamble.items[(i - 1) % preamble_size] = num;
- } else {
- try preamble.append(num);
- }
- }
-
- return aoc.Error.InvalidInput;
-}
-
-fn listSum(items: []u64) u64 {
- var sum: u64 = 0;
- for (items) |i|
- sum += i;
- return sum;
-}
-
-fn part1(allocator: *std.mem.Allocator, input: []u8, args: [][]u8) !void {
- std.debug.print("{}\n", .{try getInvalid(allocator, input)});
-}
-
-fn part2(allocator: *std.mem.Allocator, input: []u8, args: [][]u8) !void {
- const invalid = try getInvalid(allocator, input);
-
- var numset = std.ArrayList(u64).init(allocator);
- defer numset.deinit();
-
- var numit = std.mem.tokenize(input, "\n");
- while (true) {
- const sum = listSum(numset.items);
- if (sum < invalid) {
- const numstr = numit.next();
- if (numstr == null) break;
- const num = try std.fmt.parseInt(u64, numstr.?, 10);
- try numset.append(num);
- } else if (sum > invalid) {
- _ = numset.orderedRemove(0);
- } else {
- break;
- }
- }
-
- if (numset.items.len > 0) {
- std.debug.print("{}\n", .{std.mem.min(u64, numset.items) + std.mem.max(u64, numset.items)});
- }
-}
-
-pub const main = aoc.gen_main(part1, part2);
