commit 60db11460b039b567509d09eade2cb55e85ddded
parent 1a3b342d54a6883f768a0f93b8c317840136c9cb
Author: Louis Burda <quent.burda@gmail.com>
Date: Fri, 25 Dec 2020 16:50:19 +0100
added day 23 part 2 and day 25, added debug lvl to aoc helper lib
Diffstat:
7 files changed, 197 insertions(+), 19 deletions(-)
diff --git a/lib/aoc.zig b/lib/aoc.zig
@@ -4,6 +4,7 @@ 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 {
@@ -31,6 +32,7 @@ pub fn gen_main(comptime part1: part_type, comptime part2: part_type) fn () anye
break;
} else if (std.mem.eql(u8, kv[0..sep], "AOCDEBUG")) {
debug = true;
+ debuglvl = try std.fmt.parseInt(u32, kv[sep + 1 ..], 10);
}
}
}
diff --git a/src/day23/main.zig b/src/day23/main.zig
@@ -38,6 +38,15 @@ const RingLink = struct {
}
};
+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;
@@ -58,23 +67,6 @@ fn parseInput(input: []const u8, lookup: []RingLink, list: *?*RingLink) !u32 {
}
fn doRound(list: *RingLink, len: u32, lookup: []RingLink, current: **RingLink, max: u32, round: usize) !void {
- if (aoc.debug) {
- std.debug.print("\n-- move {} --\ncups:", .{round});
-
- 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", .{});
- }
-
var target = (current.*.data + max - 2) % max + 1;
var k: usize = 0;
var check = current.*.next;
@@ -84,8 +76,34 @@ fn doRound(list: *RingLink, len: u32, lookup: []RingLink, current: **RingLink, m
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();
@@ -151,7 +169,7 @@ fn part2(allocator: *std.mem.Allocator, input: []u8, args: [][]u8) !void {
var current = list.?;
while (round < 10000000) : (round += 1) {
if (round % 1000000 == 0) std.debug.print(".", .{});
- try doRound(list.?, 1000000, lookup, ¤t, max, round + 1);
+ try doRound(list.?, 1000000, lookup, ¤t, 1000000, round + 1);
}
std.debug.print("\n", .{});
diff --git a/src/day25/input b/src/day25/input
@@ -0,0 +1,2 @@
+8987316
+14681524
diff --git a/src/day25/input-test b/src/day25/input-test
@@ -0,0 +1,2 @@
+5764801
+17807724
diff --git a/src/day25/main.zig b/src/day25/main.zig
@@ -0,0 +1,56 @@
+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/day25/part1 b/src/day25/part1
@@ -0,0 +1,77 @@
+--- Day 25: Combo Breaker ---
+
+You finally reach the check-in desk. Unfortunately, their registration systems are currently
+offline, and they cannot check you in. Noticing the look on your face, they quickly add that tech
+support is already on the way! They even created all the room keys this morning; you can take yours
+now and give them your room deposit once the registration system comes back online.
+
+The room key is a small RFID card. Your room is on the 25th floor and the elevators are also
+temporarily out of service, so it takes what little energy you have left to even climb the stairs
+and navigate the halls. You finally reach the door to your room, swipe your card, and -
+[1m[37mbeep[0m - the light turns red.
+
+Examining the card more closely, you discover a phone number for tech support.
+
+"Hello! How can we help you today?" You explain the situation.
+
+"Well, it sounds like the card isn't sending the right command to unlock the door. If you go back to
+the check-in desk, surely someone there can reset it for you." Still catching your breath, you
+describe the status of the elevator and the exact number of stairs you just had to climb.
+
+"I see! Well, your only other option would be to reverse-engineer the cryptographic handshake the
+card does with the door and then inject your own commands into the data stream, but that's
+definitely impossible." You thank them for their time.
+
+Unfortunately for the door, you know a thing or two about cryptographic handshakes.
+
+The handshake used by the card and the door involves an operation that [1m[37mtransforms[0m a
+[1m[37msubject number[0m. To transform a subject number, start with the value 1. Then, a number
+of times called the [1m[37mloop size[0m, perform the following steps:
+
+
+ - Set the value to itself multiplied by the [1m[37msubject number[0m.
+ - Set the value to the remainder after dividing the value by [1m[37m20201227[0m.
+
+
+The card always uses a specific, secret [1m[37mloop size[0m when it transforms a subject number.
+The door always uses a different, secret loop size.
+
+The cryptographic handshake works like this:
+
+
+ - The [1m[37mcard[0m transforms the subject number of [1m[37m7[0m according to the
+[1m[37mcard's[0m secret loop size. The result is called the [1m[37mcard's public key[0m.
+ - The [1m[37mdoor[0m transforms the subject number of [1m[37m7[0m according to the
+[1m[37mdoor's[0m secret loop size. The result is called the [1m[37mdoor's public key[0m.
+ - The card and door use the wireless RFID signal to transmit the two public keys (your puzzle
+input) to the other device. Now, the [1m[37mcard[0m has the [1m[37mdoor's[0m public key, and
+the [1m[37mdoor[0m has the [1m[37mcard's[0m public key. Because you can eavesdrop on the
+signal, you have both public keys, but neither device's loop size.
+ - The [1m[37mcard[0m transforms the subject number of [1m[37mthe door's public key[0m
+according to the [1m[37mcard's[0m loop size. The result is the [1m[37mencryption key[0m.
+ - The [1m[37mdoor[0m transforms the subject number of [1m[37mthe card's public key[0m
+according to the [1m[37mdoor's[0m loop size. The result is the same [1m[37mencryption key[0m
+as the [1m[37mcard[0m calculated.
+
+
+If you can use the two public keys to determine each device's loop size, you will have enough
+information to calculate the secret [1m[37mencryption key[0m that the card and door use to
+communicate; this would let you send the unlock command directly to the door!
+
+For example, suppose you know that the card's public key is 5764801. With a little trial and error,
+you can work out that the card's loop size must be [1m[37m8[0m, because transforming the initial
+subject number of 7 with a loop size of 8 produces 5764801.
+
+Then, suppose you know that the door's public key is 17807724. By the same process, you can
+determine that the door's loop size is [1m[37m11[0m, because transforming the initial subject
+number of 7 with a loop size of 11 produces 17807724.
+
+At this point, you can use either device's loop size with the other device's public key to calculate
+the [1m[37mencryption key[0m. Transforming the subject number of 17807724 (the door's public key)
+with a loop size of 8 (the card's loop size) produces the encryption key, [1m[37m14897079[0m.
+(Transforming the subject number of 5764801 (the card's public key) with a loop size of 11 (the
+door's loop size) produces the same encryption key: [1m[37m14897079[0m.)
+
+[1m[37mWhat encryption key is the handshake trying to establish?[0m
+
+
diff --git a/src/day25/part2 b/src/day25/part2
@@ -0,0 +1,21 @@
+--- Part Two ---
+
+The light turns green and the door unlocks. As you collapse onto the bed in your room, your pager
+goes off!
+
+"It's an emergency!" the Elf calling you explains. "The soft serve machine in the cafeteria on
+sub-basement 7 just failed and you're the only one that knows how to fix it! We've already
+dispatched a reindeer to your location to pick you up."
+
+You hear the sound of hooves landing on your balcony.
+
+The reindeer carefully explores the contents of your room while you figure out how you're going to
+pay the [1m[33m50 stars[0m you owe the resort before you leave. Noticing that you look concerned,
+the reindeer wanders over to you; you see that it's carrying a small pouch.
+
+"Sorry for the trouble," a note in the pouch reads. Sitting at the bottom of the pouch is a gold
+coin with a little picture of a starfish on it.
+
+Looks like you only needed [1m[33m49 stars[0m after all.
+
+
