voroskoi/aoc2021-zig - Change 65A4T47IAWVWHN4E2NDGXVCI3SCMVNQQS3OM377US2ORTHJCWZKAC

Add solution for day16

Created by voroskoi on January 28, 2022

65A4T47IAWVWHN4E2NDGXVCI3SCMVNQQS3OM377US2ORTHJCWZKAC

Dependencies

In channels

main

Change contents

Insertion in src/main.zig at line 33 [4.50]

[2.76]

[3.561]

const day16a = @import("day16a.zig");
const day16b = @import("day16b.zig");

Insertion in src/main.zig at line 68 [4.50]

[2.134]

[3.1035]

    _ = try day16a.first();
    _ = try day16b.second();

File addition: day16b.zig (----------)

[4.15]

const std = @import("std");
const path = "../data/day16/input.txt";
const RetType = u44;
const Str = []const u8;
fn parseInput(a: std.mem.Allocator) ![]u8 {
    const input = @embedFile(path);
    var ret = std.ArrayList(u8).init(a);
    for (input) |ch| {
        switch (ch) {
            '0' => try ret.appendSlice("0000"),
            '1' => try ret.appendSlice("0001"),
            '2' => try ret.appendSlice("0010"),
            '3' => try ret.appendSlice("0011"),
            '4' => try ret.appendSlice("0100"),
            '5' => try ret.appendSlice("0101"),
            '6' => try ret.appendSlice("0110"),
            '7' => try ret.appendSlice("0111"),
            '8' => try ret.appendSlice("1000"),
            '9' => try ret.appendSlice("1001"),
            'A' => try ret.appendSlice("1010"),
            'B' => try ret.appendSlice("1011"),
            'C' => try ret.appendSlice("1100"),
            'D' => try ret.appendSlice("1101"),
            'E' => try ret.appendSlice("1110"),
            'F' => try ret.appendSlice("1111"),
            else => break,
        }
    }
    return ret.toOwnedSlice();
}
pub fn second() !RetType {
    // var gpa = std.heap.GeneralPurposeAllocator(.{}){};
    // const allocator = gpa.allocator();
    const allocator = std.testing.allocator;
    const input = try parseInput(allocator);
    defer allocator.free(input);
    var arena = std.heap.ArenaAllocator.init(allocator);
    defer arena.deinit();
    const p = try parsePacket(arena.allocator(), &input[0..]);
    return p.evaluate();
}
const LiteralType = u44;
const Packet = struct {
    version: u3,
    typeID: u3,
    literal: LiteralType,
    subs: std.ArrayList(Packet),
    fn sumVersion(self: @This()) RetType {
        var sum: RetType = self.version;
        for (self.subs.items) |sp| {
            sum += sp.sumVersion();
        }
        return sum;
    }
    fn parseOperator(self: *@This(), a: std.mem.Allocator, in: *Str) anyerror!void {
        in.* = in.*[6..];
        switch (in.*[0]) {
            '0' => {
                const total = try std.fmt.parseUnsigned(usize, in.*[1..16], 2);
                in.* = in.*[16..];
                const initial_length = in.len;
                var pivot: usize = 0;
                while (pivot < total) : (pivot = initial_length - in.len) {
                    var p = try parsePacket(a, in);
                    try self.subs.append(p);
                }
            },
            '1' => {
                const subpackets = try std.fmt.parseUnsigned(usize, in.*[1..12], 2);
                in.* = in.*[12..];
                var counter: usize = 0;
                while (counter < subpackets) : (counter += 1) {
                    var p = try parsePacket(a, in);
                    try self.subs.append(p);
                }
            },
            else => unreachable,
        }
    }
    fn evaluate(self: @This()) RetType {
        switch (self.typeID) {
            0 => {
                var sum: RetType = 0;
                for (self.subs.items) |s| {
                    sum += s.evaluate();
                }
                return sum;
            },
            1 => {
                var prod: RetType = 1;
                for (self.subs.items) |s| {
                    prod *= s.evaluate();
                }
                return prod;
            },
            2 => {
                var min: RetType = ~@as(RetType, 0);
                for (self.subs.items) |s| {
                    if (s.evaluate() < min) {
                        min = s.evaluate();
                    }
                }
                return min;
            },
            3 => {
                var max: RetType = 0;
                for (self.subs.items) |s| {
                    if (s.evaluate() > max) {
                        max = s.evaluate();
                    }
                }
                return max;
            },
            4 => {
                return self.literal;
            },
            5 => { // greater
                if (self.subs.items[0].evaluate() > self.subs.items[1].evaluate()) {
                    return 1;
                }
                return 0;
            },
            6 => { // less
                if (self.subs.items[0].evaluate() < self.subs.items[1].evaluate()) {
                    return 1;
                }
                return 0;
            },
            7 => { // equal
                if (self.subs.items[0].evaluate() == self.subs.items[1].evaluate()) {
                    return 1;
                }
                return 0;
            },
        }
        unreachable;
    }
};
fn parsePacket(a: std.mem.Allocator, in: *Str) !Packet {
    var p = Packet{ .version = undefined, .typeID = undefined, .literal = undefined, .subs = std.ArrayList(Packet).init(a) };
    p.version = try std.fmt.parseUnsigned(u3, in.*[0..3], 2);
    p.typeID = try std.fmt.parseUnsigned(u3, in.*[3..6], 2);
    if (p.typeID == 4) {
        p.literal = try parseLiteral(a, in);
    } else {
        try p.parseOperator(a, in);
    }
    return p;
}
fn parseLiteral(a: std.mem.Allocator, in: *Str) !LiteralType {
    in.* = in.*[6..];
    var ret = std.ArrayList(u8).init(a);
    var idx: usize = 0;
    while (idx < in.len) : (idx += 5) {
        try ret.appendSlice(in.*[idx + 1 .. idx + 5]);
        if (in.*[idx] == '0') {
            in.* = in.*[idx + 5 ..];
            break;
        }
    }
    return try std.fmt.parseUnsigned(LiteralType, ret.items, 2);
}
pub fn main() !void {
    var timer = try std.time.Timer.start();
    const ret = try second();
    const t = timer.lap() / 1000;
    try std.testing.expectEqual(@as(RetType, 12883091136209), ret);
    std.debug.print("Day 16b result: {d} \ttime: {d}µs\n", .{ ret, t });
}
test "day16a" {
    try std.testing.expectEqual(@as(RetType, 12883091136209), try second());
}

File addition: day16a.zig (----------)

[4.15]

const std = @import("std");
const path = "../data/day16/input.txt";
const RetType = u10;
const Str = []const u8;
fn parseInput(a: std.mem.Allocator) ![]u8 {
    const input = @embedFile(path);
    var ret = std.ArrayList(u8).init(a);
    for (input) |ch| {
        switch (ch) {
            '0' => try ret.appendSlice("0000"),
            '1' => try ret.appendSlice("0001"),
            '2' => try ret.appendSlice("0010"),
            '3' => try ret.appendSlice("0011"),
            '4' => try ret.appendSlice("0100"),
            '5' => try ret.appendSlice("0101"),
            '6' => try ret.appendSlice("0110"),
            '7' => try ret.appendSlice("0111"),
            '8' => try ret.appendSlice("1000"),
            '9' => try ret.appendSlice("1001"),
            'A' => try ret.appendSlice("1010"),
            'B' => try ret.appendSlice("1011"),
            'C' => try ret.appendSlice("1100"),
            'D' => try ret.appendSlice("1101"),
            'E' => try ret.appendSlice("1110"),
            'F' => try ret.appendSlice("1111"),
            else => break,
        }
    }
    return ret.toOwnedSlice();
}
pub fn first() !RetType {
    var gpa = std.heap.GeneralPurposeAllocator(.{}){};
    const allocator = gpa.allocator();
    const input = try parseInput(allocator);
    defer allocator.free(input);
    var arena = std.heap.ArenaAllocator.init(allocator);
    defer arena.deinit();
    const p = try parsePacket(arena.allocator(), &input[0..]);
    return p.sumVersion();
}
const LiteralType = u44;
const Packet = struct {
    version: u3,
    typeID: u3,
    literal: LiteralType,
    subs: std.ArrayList(Packet),
    fn sumVersion(self: @This()) RetType {
        var sum: RetType = self.version;
        for (self.subs.items) |sp| {
            sum += sp.sumVersion();
        }
        return sum;
    }
    fn parseOperator(self: *@This(), a: std.mem.Allocator, in: *Str) anyerror!void {
        in.* = in.*[6..];
        switch (in.*[0]) {
            '0' => {
                const total = try std.fmt.parseUnsigned(usize, in.*[1..16], 2);
                in.* = in.*[16..];
                const initial_length = in.len;
                var pivot: usize = 0;
                while (pivot < total) : (pivot = initial_length - in.len) {
                    var p = try parsePacket(a, in);
                    try self.subs.append(p);
                }
            },
            '1' => {
                const subpackets = try std.fmt.parseUnsigned(usize, in.*[1..12], 2);
                in.* = in.*[12..];
                var counter: usize = 0;
                while (counter < subpackets) : (counter += 1) {
                    var p = try parsePacket(a, in);
                    try self.subs.append(p);
                }
            },
            else => unreachable,
        }
    }
};
fn parsePacket(a: std.mem.Allocator, in: *Str) !Packet {
    var p = Packet{ .version = undefined, .typeID = undefined, .literal = undefined, .subs = std.ArrayList(Packet).init(a) };
    p.version = try std.fmt.parseUnsigned(u3, in.*[0..3], 2);
    p.typeID = try std.fmt.parseUnsigned(u3, in.*[3..6], 2);
    if (p.typeID == 4) {
        p.literal = try parseLiteral(a, in);
    } else {
        try p.parseOperator(a, in);
    }
    return p;
}
fn parseLiteral(a: std.mem.Allocator, in: *Str) !LiteralType {
    in.* = in.*[6..];
    var ret = std.ArrayList(u8).init(a);
    var idx: usize = 0;
    while (idx < in.len) : (idx += 5) {
        try ret.appendSlice(in.*[idx + 1 .. idx + 5]);
        if (in.*[idx] == '0') {
            in.* = in.*[idx + 5 ..];
            break;
        }
    }
    return try std.fmt.parseUnsigned(LiteralType, ret.items, 2);
}
pub fn main() !void {
    var timer = try std.time.Timer.start();
    const ret = try first();
    const t = timer.lap() / 1000;
    try std.testing.expectEqual(@as(RetType, 967), ret);
    std.debug.print("Day 16a result: {d} \t\ttime: {d}µs\n", .{ ret, t });
}
test "day16a" {
    try std.testing.expectEqual(@as(RetType, 967), try first());
}

File addition: day16 (d--x------)
[5.2349]

File addition: input.txt (----------)

[0.10175]

00569F4A0488043262D30B333FCE6938EC5E5228F2C78A017CD78C269921249F2C69256C559CC01083BA00A4C5730FF12A56B1C49A480283C0055A532CF2996197653005FC01093BC4CE6F5AE49E27A7532200AB25A653800A8CAE5DE572EC40080CD26CA01CAD578803CBB004E67C573F000958CAF5FC6D59BC8803D1967E0953C68401034A24CB3ACD934E311004C5A00A4AB9CAE99E52648401F5CC4E91B6C76801F59DA63C1F3B4C78298014F91BCA1BAA9CBA99006093BFF916802923D8CC7A7A09CA010CD62DF8C2439332A58BA1E495A5B8FA846C00814A511A0B9004C52F9EF41EC0128BF306E4021FD005CD23E8D7F393F48FA35FCE4F53191920096674F66D1215C98C49850803A600D4468790748010F8430A60E1002150B20C4273005F8012D95EC09E2A4E4AF7041004A7F2FB3FCDFA93E4578C0099C52201166C01600042E1444F8FA00087C178AF15E179802F377EC695C6B7213F005267E3D33F189ABD2B46B30042655F0035300042A0F47B87A200EC1E84306C801819B45917F9B29700AA66BDC7656A0C49DB7CAEF726C9CEC71EC5F8BB2F2F37C9C743A600A442B004A7D2279125B73127009218C97A73C4D1E6EF64A9EFDE5AF4241F3FA94278E0D9005A32D9C0DD002AB2B7C69B23CCF5B6C280094CE12CDD4D0803CF9F96D1F4012929DA895290FF6F5E2A9009F33D796063803551006E3941A8340008743B8D90ACC015C00DDC0010B873052320002130563A4359CF968000B10258024C8DF2783F9AD6356FB6280312EBB394AC6FE9014AF2F8C381008CB600880021B0AA28463100762FC1983122D2A005CBD11A4F7B9DADFD110805B2E012B1F4249129DA184768912D90B2013A4001098391661E8803D05612C731007216C768566007280126005101656E0062013D64049F10111E6006100E90E004100C1620048009900020E0006DA0015C000418000AF80015B3D938

Replacement in build.zig at line 4 [4.2055]
B:BD[4.2113] → [2.4214:4231]
```
const days = 15;
```
[4.2113]
[4.2129]
```
const days = 16;
```

Add solution for day16

Dependencies

In channels

Change contents

Insertion in src/main.zig at line 33 [4.50]

Insertion in src/main.zig at line 68 [4.50]

File addition: day16b.zig (----------)

File addition: day16a.zig (----------)

File addition: day16 (d--x------)

File addition: input.txt (----------)

Replacement in build.zig at line 4 [4.2055]