commit 2106b6e00af2e0d9203b2aeb66b841bc761185f1
parent 0f0e042ff46d956bcd06d885859518ba5dbe2662
Author: Louis Burda <quent.burda@gmail.com>
Date: Sun, 13 Dec 2020 16:41:14 +0100
added debug var to aoc lib and day13
Diffstat:
8 files changed, 258 insertions(+), 18 deletions(-)
diff --git a/lib/aoc.zig b/lib/aoc.zig
@@ -3,6 +3,8 @@ pub const input = @import("input.zig");
pub const Error = error{InvalidInput};
+pub var debug = false;
+
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 {
@@ -22,10 +24,13 @@ pub fn gen_main(comptime part1: part_type, comptime part2: part_type) fn () anye
for (std.os.environ) |v| {
const kv = std.mem.spanZ(v);
if (std.mem.indexOfScalar(u8, kv, '=')) |sep| {
- if (sep < kv.len - 1 and std.mem.eql(u8, kv[0..sep], "AOCINPUT")) {
+ 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;
}
}
}
diff --git a/scripts/prepare b/scripts/prepare
@@ -24,19 +24,11 @@ fi
daynum="$1"
folder="$REPOROOT/src/day$daynum"
-if [ -e "$folder" ]; then
- echo "Directory for problem already exists"
- exit 1
-fi
-
-echo "Initializing folder"
-
-mkdir "$folder"
-echo "Copying template"
-cp "$REPOROOT/data/template.zig" "$folder/main.zig"
+[ ! -e "$folder" ] && ( echo "Initializing folder"; mkdir "$folder" )
+[ ! -e "$folder/main.zig" ] && ( echo "Copying template"; cp "$REPOROOT/data/template.zig" "$folder/main.zig" )
-load "Loading problem input" $daynum input
-load "Loading first problem text" $daynum part 1
-load "Loading second problem text" $daynum part 2
+[ ! -e "$folder/input" ] && load "Loading problem input" $daynum input
+[ ! -e "$folder/part1" ] && load "Loading first problem text" $daynum part 1
+[ ! -e "$folder/part2" ] && load "Loading second problem text" $daynum part 2
diff --git a/src/day13/input b/src/day13/input
@@ -0,0 +1,2 @@
+1001612
+19,x,x,x,x,x,x,x,x,41,x,x,x,37,x,x,x,x,x,821,x,x,x,x,x,x,x,x,x,x,x,x,13,x,x,x,17,x,x,x,x,x,x,x,x,x,x,x,29,x,463,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,23
diff --git a/src/day13/input-test b/src/day13/input-test
@@ -0,0 +1,2 @@
+939
+7,13,x,x,59,x,31,19
diff --git a/src/day13/main.zig b/src/day13/main.zig
@@ -1,16 +1,105 @@
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 answer: u32 = 0;
+ 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", .{answer});
+ std.debug.print("{} {}\n", .{ bestbus.?, bestbus.? * waittime(start, bestbus.?) });
}
fn part2(allocator: *std.mem.Allocator, input: []u8, args: [][]u8) !void {
- var answer: u32 = 0;
+ 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});
+ }
+ }
- std.debug.print("{}\n", .{answer});
+ 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/day13/notes b/src/day13/notes
@@ -0,0 +1,6 @@
+3 x 4
+
+ 1 (4)
+ 2 (8)
+ 3 (12)
+ 8
diff --git a/src/day13/part1 b/src/day13/part1
@@ -0,0 +1,65 @@
+--- Day 13: Shuttle Search ---
+
+Your ferry can make it safely to a nearby port, but it won't get much further. When you call to book
+another ship, you discover that no ships embark from that port to your vacation island. You'll need
+to get from the port to the nearest airport.
+
+Fortunately, a shuttle bus service is available to bring you from the sea port to the airport! Each
+bus has an ID number that also indicates [1m[37mhow often the bus leaves for the airport[0m.
+
+Bus schedules are defined based on a [1m[37mtimestamp[0m that measures the [1m[37mnumber of
+minutes[0m since some fixed reference point in the past. At timestamp 0, every bus simultaneously
+departed from the sea port. After that, each bus travels to the airport, then various other
+locations, and finally returns to the sea port to repeat its journey forever.
+
+The time this loop takes a particular bus is also its ID number: the bus with ID 5 departs from the
+sea port at timestamps 0, 5, 10, 15, and so on. The bus with ID 11 departs at 0, 11, 22, 33, and so
+on. If you are there when the bus departs, you can ride that bus to the airport!
+
+Your notes (your puzzle input) consist of two lines. The first line is your estimate of the
+[1m[37mearliest timestamp you could depart on a bus[0m. The second line lists the bus IDs that
+are in service according to the shuttle company; entries that show x must be out of service, so you
+decide to ignore them.
+
+To save time once you arrive, your goal is to figure out [1m[37mthe earliest bus you can take to
+the airport[0m. (There will be exactly one such bus.)
+
+For example, suppose you have the following notes:
+
+939
+7,13,x,x,59,x,31,19
+
+Here, the earliest timestamp you could depart is 939, and the bus IDs in service are 7, 13, 59, 31,
+and 19. Near timestamp 939, these bus IDs depart at the times marked D:
+
+time bus 7 bus 13 bus 59 bus 31 bus 19
+929 . . . . .
+930 . . . D .
+931 D . . . D
+932 . . . . .
+933 . . . . .
+934 . . . . .
+935 . . . . .
+936 . D . . .
+937 . . . . .
+938 D . . . .
+[1m[37m939 . . . . .[0m
+940 . . . . .
+941 . . . . .
+942 . . . . .
+943 . . . . .
+[1m[37m944 . . D . .[0m
+945 D . . . .
+946 . . . . .
+947 . . . . .
+948 . . . . .
+949 . D . . .
+
+The earliest bus you could take is bus ID 59. It doesn't depart until timestamp 944, so you would
+need to wait 944 - 939 = 5 minutes before it departs. Multiplying the bus ID by the number of
+minutes you'd need to wait gives [1m[37m295[0m.
+
+[1m[37mWhat is the ID of the earliest bus you can take to the airport multiplied by the number of
+minutes you'll need to wait for that bus?[0m
+
+
diff --git a/src/day13/part2 b/src/day13/part2
@@ -0,0 +1,79 @@
+--- Part Two ---
+
+The shuttle company is running a contest: one gold coin for anyone that can find the earliest
+timestamp such that the first bus ID departs at that time and each subsequent listed bus ID departs
+at that subsequent minute. (The first line in your input is no longer relevant.)
+
+For example, suppose you have the same list of bus IDs as above:
+
+7,13,x,x,59,x,31,19
+An x in the schedule means there are no constraints on what bus IDs must depart at that time.
+
+This means you are looking for the earliest timestamp (called t) such that:
+
+
+ - Bus ID 7 departs at timestamp t.
+ - Bus ID 13 departs one minute after timestamp t.
+ - There are no requirements or restrictions on departures at two or three minutes after timestamp
+t.
+ - Bus ID 59 departs four minutes after timestamp t.
+ - There are no requirements or restrictions on departures at five minutes after timestamp t.
+ - Bus ID 31 departs six minutes after timestamp t.
+ - Bus ID 19 departs seven minutes after timestamp t.
+
+
+The only bus departures that matter are the listed bus IDs at their specific offsets from t. Those
+bus IDs can depart at other times, and other bus IDs can depart at those times. For example, in the
+list above, because bus ID 19 must depart seven minutes after the timestamp at which bus ID 7
+departs, bus ID 7 will always [1m[37malso[0m be departing with bus ID 19 at seven minutes after
+timestamp t.
+
+In this example, the earliest timestamp at which this occurs is [1m[37m1068781[0m:
+
+time bus 7 bus 13 bus 59 bus 31 bus 19
+1068773 . . . . .
+1068774 D . . . .
+1068775 . . . . .
+1068776 . . . . .
+1068777 . . . . .
+1068778 . . . . .
+1068779 . . . . .
+1068780 . . . . .
+[1m[37m1068781[0m [1m[37mD[0m . . . .
+[1m[37m1068782[0m . [1m[37mD[0m . . .
+[1m[37m1068783[0m . . . . .
+[1m[37m1068784[0m . . . . .
+[1m[37m1068785[0m . . [1m[37mD[0m . .
+[1m[37m1068786[0m . . . . .
+[1m[37m1068787[0m . . . [1m[37mD[0m .
+[1m[37m1068788[0m D . . . [1m[37mD[0m
+1068789 . . . . .
+1068790 . . . . .
+1068791 . . . . .
+1068792 . . . . .
+1068793 . . . . .
+1068794 . . . . .
+1068795 D D . . .
+1068796 . . . . .
+1068797 . . . . .
+
+In the above example, bus ID 7 departs at timestamp 1068788 (seven minutes after t). This is fine;
+the only requirement on that minute is that bus ID 19 departs then, and it does.
+
+Here are some other examples:
+
+
+ - The earliest timestamp that matches the list 17,x,13,19 is [1m[37m3417[0m.
+ - 67,7,59,61 first occurs at timestamp [1m[37m754018[0m.
+ - 67,x,7,59,61 first occurs at timestamp [1m[37m779210[0m.
+ - 67,7,x,59,61 first occurs at timestamp [1m[37m1261476[0m.
+ - 1789,37,47,1889 first occurs at timestamp [1m[37m1202161486[0m.
+
+
+However, with so many bus IDs in your list, surely the actual earliest timestamp will be larger than
+100000000000000!
+
+[1m[37mWhat is the earliest timestamp such that all of the listed bus IDs depart at offsets
+matching their positions in the list?[0m
+
+
