commit 0d74166d177df1853679d83d11c45bfd0358a4a0
parent 9755ba3236266ea10d532d2de17f718b206fcaf5
Author: Louis Burda <quent.burda@gmail.com>
Date: Fri, 11 Dec 2020 16:28:10 +0100
added day 10, fixed scrape and added option to specify other input via env var in aoc lib
Diffstat:
7 files changed, 300 insertions(+), 9 deletions(-)
diff --git a/lib/aoc.zig b/lib/aoc.zig
@@ -18,8 +18,20 @@ pub fn gen_main(comptime part1: part_type, comptime part2: part_type) fn () anye
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 and std.mem.eql(u8, kv[0..sep], "AOCINPUT")) {
+ filename = kv[sep + 1 ..];
+ std.debug.print("Using input file: {}\n", .{filename});
+ break;
+ }
+ }
+ }
+
// read all input into mem (files are always small so no problem)
- const file = try std.fs.cwd().openFile("input", .{});
+ const file = try std.fs.cwd().openFile(filename, .{});
const text = try file.reader().readAllAlloc(heapalloc, std.math.maxInt(u32));
defer heapalloc.free(text);
diff --git a/scripts/scrape b/scripts/scrape
@@ -68,10 +68,12 @@ def scrape_text(day, part):
with open(path, "w+") as of:
text = extract_hltext(textobj)
- parts = text.split("\n\n")
+ parts = text.split("\n")
for i,p in enumerate(parts):
+ if p == "":
+ continue
newp = [list(),]
- words = p.split()
+ words = p.split(" ")
linelen = 0
for w in words:
if linelen + len(w) > 100:
@@ -80,7 +82,7 @@ def scrape_text(day, part):
newp[-1].append(w)
linelen += len(w) + 1
parts[i] = "\n".join([" ".join(words) for words in newp])
- of.write("{}\n".format("\n\n".join(parts)))
+ of.write("{}\n".format("\n".join(parts)))
def main():
if cmd == "input":
diff --git a/src/day10/main.zig b/src/day10/main.zig
@@ -2,15 +2,153 @@ const std = @import("std");
const aoc = @import("aoc");
fn part1(allocator: *std.mem.Allocator, input: []u8, args: [][]u8) !void {
- var answer: u32 = 0;
+ var target: u32 = 0;
- std.debug.print("{}\n", .{answer});
+ 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 part2(allocator: *std.mem.Allocator, input: []u8, args: [][]u8) !void {
- var answer: u32 = 0;
+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);
- std.debug.print("{}\n", .{answer});
+ 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/day10/out b/src/day10/out
@@ -0,0 +1,31 @@
+1
+2
+3
+4
+7
+8
+9
+10
+11
+14
+17
+18
+19
+20
+23
+24
+25
+28
+31
+32
+33
+34
+35
+38
+39
+42
+45
+46
+47
+48
+49
+\ No newline at end of file
diff --git a/src/day10/part2 b/src/day10/part2
@@ -0,0 +1,65 @@
+--- Part Two ---
+
+To completely determine whether you have enough adapters, you'll need to figure out how many
+different ways they can be arranged. Every arrangement needs to connect the charging outlet to your
+device. The previous rules about when adapters can successfully connect still apply.
+
+The first example above (the one that starts with 16, 10, 15) supports the following arrangements:
+
+(0), 1, 4, 5, 6, 7, 10, 11, 12, 15, 16, 19, (22)
+(0), 1, 4, 5, 6, 7, 10, 12, 15, 16, 19, (22)
+(0), 1, 4, 5, 7, 10, 11, 12, 15, 16, 19, (22)
+(0), 1, 4, 5, 7, 10, 12, 15, 16, 19, (22)
+(0), 1, 4, 6, 7, 10, 11, 12, 15, 16, 19, (22)
+(0), 1, 4, 6, 7, 10, 12, 15, 16, 19, (22)
+(0), 1, 4, 7, 10, 11, 12, 15, 16, 19, (22)
+(0), 1, 4, 7, 10, 12, 15, 16, 19, (22)
+
+(The charging outlet and your device's built-in adapter are shown in parentheses.) Given the
+adapters from the first example, the total number of arrangements that connect the charging outlet
+to your device is [1m[37m8[0m.
+
+The second example above (the one that starts with 28, 33, 18) has many arrangements. Here are a
+few:
+
+(0), 1, 2, 3, 4, 7, 8, 9, 10, 11, 14, 17, 18, 19, 20, 23, 24, 25, 28, 31,
+32, 33, 34, 35, 38, 39, 42, 45, 46, 47, 48, 49, (52)
+
+(0), 1, 2, 3, 4, 7, 8, 9, 10, 11, 14, 17, 18, 19, 20, 23, 24, 25, 28, 31,
+32, 33, 34, 35, 38, 39, 42, 45, 46, 47, 49, (52)
+
+(0), 1, 2, 3, 4, 7, 8, 9, 10, 11, 14, 17, 18, 19, 20, 23, 24, 25, 28, 31,
+32, 33, 34, 35, 38, 39, 42, 45, 46, 48, 49, (52)
+
+(0), 1, 2, 3, 4, 7, 8, 9, 10, 11, 14, 17, 18, 19, 20, 23, 24, 25, 28, 31,
+32, 33, 34, 35, 38, 39, 42, 45, 46, 49, (52)
+
+(0), 1, 2, 3, 4, 7, 8, 9, 10, 11, 14, 17, 18, 19, 20, 23, 24, 25, 28, 31,
+32, 33, 34, 35, 38, 39, 42, 45, 47, 48, 49, (52)
+
+(0), 3, 4, 7, 10, 11, 14, 17, 20, 23, 25, 28, 31, 34, 35, 38, 39, 42, 45,
+46, 48, 49, (52)
+
+(0), 3, 4, 7, 10, 11, 14, 17, 20, 23, 25, 28, 31, 34, 35, 38, 39, 42, 45,
+46, 49, (52)
+
+(0), 3, 4, 7, 10, 11, 14, 17, 20, 23, 25, 28, 31, 34, 35, 38, 39, 42, 45,
+47, 48, 49, (52)
+
+(0), 3, 4, 7, 10, 11, 14, 17, 20, 23, 25, 28, 31, 34, 35, 38, 39, 42, 45,
+47, 49, (52)
+
+(0), 3, 4, 7, 10, 11, 14, 17, 20, 23, 25, 28, 31, 34, 35, 38, 39, 42, 45,
+48, 49, (52)
+
+In total, this set of adapters can connect the charging outlet to your device in [1m[37m19208[0m
+distinct arrangements.
+
+You glance back down at your bag and try to remember why you brought so many adapters; there must be
+[1m[37mmore than a trillion[0m valid ways to arrange them! Surely, there must be an efficient way
+to count the arrangements.
+
+[1m[37mWhat is the total number of distinct ways you can arrange the adapters to connect the
+charging outlet to your device?[0m
+
+
diff --git a/src/day10/test-input b/src/day10/test-input
@@ -0,0 +1,31 @@
+28
+33
+18
+42
+31
+14
+46
+20
+48
+47
+24
+23
+49
+45
+19
+38
+39
+11
+1
+32
+25
+35
+8
+17
+7
+9
+4
+2
+34
+10
+3
diff --git a/src/day10/test-input2 b/src/day10/test-input2
@@ -0,0 +1,11 @@
+16
+10
+15
+5
+1
+11
+7
+19
+6
+12
+4
