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 (3218B)

      1const std = @import("std");
      2const aoc = @import("aoc");
      3
      4fn gcd(a: u64, b: u64) u64 {
      5    var ac = a;
      6    var bc = b;
      7    while (true) {
      8        if (ac > bc) {
      9            ac = ac % bc;
     10            if (ac == 0) return bc;
     11        } else {
     12            bc = bc % ac;
     13            if (bc == 0) return ac;
     14        }
     15    }
     16}
     17
     18fn lcm(a: u64, b: u64) u64 {
     19    return @divExact(a * b, gcd(a, b));
     20}
     21
     22fn waittime(start: u32, busid: u32) u32 {
     23    return (busid - (start % busid)) % busid;
     24}
     25
     26fn printRegion(buses: []u32, start: u64, end: u64) void {
     27    aoc.debugfmt("          ", .{});
     28    for (buses) |bus| {
     29        aoc.debugfmt(" {:^5}", .{bus});
     30    }
     31    aoc.debugfmt("\n", .{});
     32
     33    var i = start;
     34    while (i < end) : (i += 1) {
     35        aoc.debugfmt("{:<10}", .{i});
     36        for (buses) |bus| {
     37            var c: u8 = '.';
     38            if (bus > 0 and i % bus == 0) c = 'D';
     39            aoc.debugfmt("   {c}  ", .{c});
     40        }
     41        aoc.debugfmt("\n", .{});
     42    }
     43    aoc.debugfmt("\n", .{});
     44}
     45
     46fn part1(allocator: std.mem.Allocator, input: []u8, args: [][]u8) !?[]u8 {
     47    _ = args;
     48
     49    var lineit = std.mem.tokenize(u8, input, "\n");
     50    var start = try std.fmt.parseInt(u32, lineit.next().?, 10);
     51
     52    var bestbus: ?u32 = null;
     53    var busit = std.mem.tokenize(u8, lineit.next().?, ",");
     54    while (busit.next()) |bus| {
     55        if (bus[0] == 'x') continue;
     56        const val = try std.fmt.parseInt(u32, bus, 10);
     57        if (bestbus == null or waittime(start, val) < waittime(start, bestbus.?)) {
     58            bestbus = val;
     59        }
     60    }
     61
     62    const answer = bestbus.? * waittime(start, bestbus.?);
     63
     64    return try std.fmt.allocPrint(allocator, "{d}", .{answer});
     65}
     66
     67fn part2(allocator: std.mem.Allocator, input: []u8, args: [][]u8) !?[]u8 {
     68    _ = args;
     69
     70    var lineit = std.mem.tokenize(u8, input, "\n");
     71    _ = try std.fmt.parseInt(u32, lineit.next().?, 10);
     72
     73    var busses = std.ArrayList(u32).init(allocator);
     74    defer busses.deinit();
     75
     76    var busit = std.mem.tokenize(u8, lineit.next().?, ",");
     77
     78    const first = try std.fmt.parseInt(u32, busit.next().?, 10);
     79    try busses.append(first);
     80
     81    var offset: u64 = 0;
     82    var cycle: u64 = first;
     83    var delay: u32 = 1;
     84    while (busit.next()) |bus| : (delay += 1) {
     85        if (bus[0] == 'x') {
     86            try busses.append(0);
     87            continue;
     88        }
     89        const val = try std.fmt.parseInt(u32, bus, 10);
     90        try busses.append(val);
     91
     92        var mult: u64 = @divFloor(offset + delay, val);
     93        if ((offset + delay) % val != 0) mult += 1;
     94        while ((mult * val - offset - delay) % cycle != 0) {
     95            mult += std.math.max(1, @divFloor(cycle - (mult * val - offset - delay) % cycle, val));
     96        }
     97        offset = mult * val - delay;
     98
     99        cycle = lcm(cycle, val);
    100        if (aoc.debug) {
    101            printRegion(busses.items, offset, offset + delay + 1);
    102            printRegion(busses.items, offset + cycle, offset + cycle + delay + 1);
    103            aoc.debugfmt("{}\n", .{offset});
    104        }
    105    }
    106
    107    printRegion(busses.items, offset, offset + busses.items.len);
    108
    109    return try std.fmt.allocPrint(allocator, "{}", .{offset});
    110}
    111
    112pub const main = aoc.main(part1, part2, .{ "6568", "554865447501099" });