aoc-2020-zig

Advent of Code 2020 Solutions in Zig
git clone https://git.sinitax.com/sinitax/aoc-2020-zig
Log | Files | Refs | README | sfeed.txt

main.zig (3554B)

      1const std = @import("std");
      2const aoc = @import("aoc");
      3
      4fn part1(allocator: std.mem.Allocator, input: []u8, args: [][]u8) !?[]u8 {
      5    _ = args;
      6
      7    var target: u32 = 0;
      8
      9    var intlist = std.ArrayList(u32).init(allocator);
     10    defer intlist.deinit();
     11
     12    var lineit = std.mem.tokenize(u8, input, "\n");
     13    while (lineit.next()) |line| {
     14        var val = try std.fmt.parseInt(u32, line, 10);
     15        if (val > target) {
     16            target = val;
     17        }
     18        try intlist.append(val);
     19    }
     20
     21    target += 3;
     22    try intlist.append(target);
     23
     24    if (intlist.items.len == 0) return null;
     25
     26    std.sort.sort(u32, intlist.items, {}, comptime std.sort.asc(u32));
     27
     28    var diffs = [_]u32{ 0, 0, 0, 0 };
     29    var last: u32 = 0;
     30    for (intlist.items) |ov| {
     31        if (ov - last > 3 or ov == last) {
     32            aoc.debugfmt("Unable to find a suitable adapter for {} output jolts (next: {} jolts)\n", .{ last, ov });
     33            return aoc.Error.InvalidInput;
     34        }
     35        diffs[ov - last] += 1;
     36        last = ov;
     37    }
     38
     39    return try std.fmt.allocPrint(allocator, "{d}", .{diffs[1] * diffs[3]});
     40}
     41
     42fn countArrangements(arrangement: []u32, adapters: []const u32, adaptermask: []u1, target: u32, fillcount: u32, searchstart: u32, count: *u32) void {
     43    var last: u32 = 0;
     44    if (fillcount > 0) {
     45        last = arrangement[fillcount - 1];
     46    }
     47
     48    if (last == target) {
     49        count.* += 1;
     50        return;
     51    }
     52
     53    for (adapters[searchstart..]) |adap, i| {
     54        if (adaptermask[searchstart + i] == 1) continue;
     55        if (adap > last + 3) break;
     56
     57        adaptermask[searchstart + i] = 1;
     58        arrangement[fillcount] = adap;
     59        countArrangements(arrangement, adapters, adaptermask, target, fillcount + 1, searchstart + @intCast(u32, i) + 1, count);
     60        adaptermask[searchstart + i] = 0;
     61    }
     62}
     63
     64fn groupPermutations(adapters: []const u32) u64 {
     65    if (adapters.len == 1) return 1;
     66    var count: u64 = 0;
     67    for (adapters) |_, i| {
     68        if (i == 0) continue;
     69        if (adapters[i] <= adapters[0] + 3) {
     70            count += groupPermutations(adapters[i..]);
     71        }
     72    }
     73    return count;
     74}
     75
     76fn part2(allocator: std.mem.Allocator, input: []u8, args: [][]u8) !?[]u8 {
     77    _ = args;
     78
     79    var target: u32 = 0;
     80
     81    var intlist = std.ArrayList(u32).init(allocator);
     82    defer intlist.deinit();
     83
     84    try intlist.append(0);
     85
     86    var lineit = std.mem.tokenize(u8, input, "\n");
     87    while (lineit.next()) |line| {
     88        var val = try std.fmt.parseInt(u32, line, 10);
     89        if (val > target) {
     90            target = val;
     91        }
     92        try intlist.append(val);
     93    }
     94
     95    target += 3;
     96    try intlist.append(target);
     97
     98    if (intlist.items.len == 0) return aoc.Error.InvalidInput;
     99
    100    std.sort.sort(u32, intlist.items, {}, comptime std.sort.asc(u32));
    101
    102    var gapstart: u32 = 0;
    103    var multiplier: u128 = 1;
    104
    105    var i: u32 = 0;
    106    while (i < intlist.items.len - 1) : (i += 1) {
    107        // whenever we encounter a 3 jolt gap, we can calc permutations of group before
    108        if (i + 1 < intlist.items.len and intlist.items[i + 1] == intlist.items[i] + 3) {
    109            multiplier *= groupPermutations(intlist.items[gapstart .. i + 1]);
    110            aoc.debugfmt("gap from {} to {} => {}\n", .{ intlist.items[i], intlist.items[i + 1], multiplier });
    111            aoc.debugfmt("group size: {}\n", .{i + 1 - gapstart});
    112            gapstart = i + 1;
    113        }
    114    }
    115
    116    return try std.fmt.allocPrint(allocator, "{d}", .{multiplier});
    117}
    118
    119pub const main = aoc.main(part1, part2, .{ "1998", "347250213298688" });