openpgp4fpr:2a420f2982e589326ca49d1b0644b87ed144c988

  • 0 Posts
  • 8 Comments
Joined 2 years ago
cake
Cake day: June 30th, 2023

help-circle


  • Zig

    const std = @import("std");
    const List = std.ArrayList;
    const Map = std.AutoHashMap;
    
    const tokenizeScalar = std.mem.tokenizeScalar;
    const splitScalar = std.mem.splitScalar;
    const parseInt = std.fmt.parseInt;
    const print = std.debug.print;
    const contains = std.mem.containsAtLeast;
    const eql = std.mem.eql;
    
    var gpa = std.heap.GeneralPurposeAllocator(.{}){};
    const alloc = gpa.allocator();
    
    const Answer = struct {
        middle_sum: i32,
        reordered_sum: i32,
    };
    
    pub fn solve(input: []const u8) !Answer {
        var rows = splitScalar(u8, input, '\n');
    
        // key is a page number and value is a
        // list of pages to be printed before it
        var rules = Map(i32, List(i32)).init(alloc);
        var pages = List([]i32).init(alloc);
        defer {
            var iter = rules.iterator();
            while (iter.next()) |rule| {
                rule.value_ptr.deinit();
            }
            rules.deinit();
            pages.deinit();
        }
    
        var parse_rules = true;
        while (rows.next()) |row| {
            if (eql(u8, row, "")) {
                parse_rules = false;
                continue;
            }
    
            if (parse_rules) {
                var rule_pair = tokenizeScalar(u8, row, '|');
                const rule = try rules.getOrPut(try parseInt(i32, rule_pair.next().?, 10));
                if (!rule.found_existing) {
                    rule.value_ptr.* = List(i32).init(alloc);
                }
                try rule.value_ptr.*.append(try parseInt(i32, rule_pair.next().?, 10));
            } else {
                var page = List(i32).init(alloc);
                var page_list = tokenizeScalar(u8, row, ',');
                while (page_list.next()) |list| {
                    try page.append(try parseInt(i32, list, 10));
                }
                try pages.append(try page.toOwnedSlice());
            }
        }
    
        var middle_sum: i32 = 0;
        var reordered_sum: i32 = 0;
    
        var wrong_order = false;
        for (pages.items) |page| {
            var index: usize = page.len - 1;
            while (index > 0) : (index -= 1) {
                var page_rule = rules.get(page[index]) orelse continue;
    
                // check the rest of the pages
                var remaining: usize = 0;
                while (remaining < page[0..index].len) {
                    if (contains(i32, page_rule.items, 1, &[_]i32{page[remaining]})) {
                        // re-order the wrong page
                        const element = page[remaining];
                        page[remaining] = page[index];
                        page[index] = element;
                        wrong_order = true;
    
                        if (rules.get(element)) |next_rule| {
                            page_rule = next_rule;
                        }
    
                        continue;
                    }
                    remaining += 1;
                }
            }
            if (wrong_order) {
                reordered_sum += page[(page.len - 1) / 2];
                wrong_order = false;
            } else {
                // middle page number
                middle_sum += page[(page.len - 1) / 2];
            }
        }
        return Answer{ .middle_sum = middle_sum, .reordered_sum = reordered_sum };
    }
    
    pub fn main() !void {
        const answer = try solve(@embedFile("input.txt"));
        print("Part 1: {d}\n", .{answer.middle_sum});
        print("Part 2: {d}\n", .{answer.reordered_sum});
    }
    
    test "test input" {
        const answer = try solve(@embedFile("test.txt"));
        try std.testing.expectEqual(143, answer.middle_sum);
        try std.testing.expectEqual(123, answer.reordered_sum);
    }
    
    

  • Zig

    const std = @import("std");
    const List = std.ArrayList;
    
    const tokenizeScalar = std.mem.tokenizeScalar;
    const parseInt = std.fmt.parseInt;
    const print = std.debug.print;
    const eql = std.mem.eql;
    
    var gpa = std.heap.GeneralPurposeAllocator(.{}){};
    const alloc = gpa.allocator();
    
    const Point = struct {
        x: isize,
        y: isize,
        fn add(self: *const Point, point: *const Point) Point {
            return Point{ .x = self.x + point.x, .y = self.y + point.y };
        }
    };
    
    // note: i have no idea how to use this or if it's even possible
    // const DirectionType = enum(u8) { Up, Down, Left, Right, UpLeft, UpRight, DownLeft, DownRight };
    // const Direction = union(DirectionType) {
    //     up: Point = .{ .x = 0, .y = 0 },
    // };
    
    const AllDirections = [_]Point{
        .{ .x = 0, .y = -1 }, // up
        .{ .x = 0, .y = 1 }, // down
        .{ .x = -1, .y = 0 }, // left
        .{ .x = 1, .y = 0 }, // right
        .{ .x = -1, .y = -1 }, // up left
        .{ .x = 1, .y = -1 }, // up right
        .{ .x = -1, .y = 1 }, // down left
        .{ .x = 1, .y = 1 }, // down right
    };
    
    const Answer = struct {
        xmas: u32,
        mas: u32,
    };
    
    pub fn searchXmas(letters: List([]const u8), search_char: u8, position: Point, direction: Point) u32 {
        const current_char = getChar(letters, position);
        if (current_char == search_char) {
            const next = position.add(&direction);
            if (current_char == 'M') {
                return searchXmas(letters, 'A', next, direction);
            } else if (current_char == 'A') {
                return searchXmas(letters, 'S', next, direction);
            } else if (current_char == 'S') {
                return 1; // found all letters
            }
        }
        return 0;
    }
    
    pub fn countXmas(letters: List([]const u8), starts: List(Point)) u32 {
        var counter: u32 = 0;
        for (starts.items) |start| {
            for (AllDirections) |direction| {
                const next = start.add(&direction);
                counter += searchXmas(letters, 'M', next, direction);
            }
        }
        return counter;
    }
    
    pub fn countMas(letters: List([]const u8), starts: List(Point)) u32 {
        var counter: u32 = 0;
        for (starts.items) |start| {
            const a_char = getChar(letters, start) orelse continue;
            const top_left_char = getChar(letters, start.add(&AllDirections[4])) orelse continue;
            const down_right_char = getChar(letters, start.add(&AllDirections[7])) orelse continue;
            const top_right_char = getChar(letters, start.add(&AllDirections[5])) orelse continue;
            const down_left_char = getChar(letters, start.add(&AllDirections[6])) orelse continue;
    
            const tldr = [3]u8{ top_left_char, a_char, down_right_char };
            const trdl = [3]u8{ top_right_char, a_char, down_left_char };
            if ((eql(u8, &tldr, "MAS") or eql(u8, &tldr, "SAM")) and (eql(u8, &trdl, "MAS") or eql(u8, &trdl, "SAM"))) {
                counter += 1;
            }
        }
        return counter;
    }
    
    pub fn getChar(letters: List([]const u8), point: Point) ?u8 {
        if (0 > point.x or point.x >= letters.items.len) {
            return null;
        }
        const row = @as(usize, @intCast(point.x));
    
        if (0 > point.y or point.y >= letters.items[row].len) {
            return null;
        }
        const col = @as(usize, @intCast(point.y));
        return letters.items[row][col];
    }
    
    pub fn solve(input: []const u8) !Answer {
        var rows = tokenizeScalar(u8, input, '\n');
    
        var letters = List([]const u8).init(alloc);
        defer letters.deinit();
        var x_starts = List(Point).init(alloc);
        defer x_starts.deinit();
        var a_starts = List(Point).init(alloc);
        defer a_starts.deinit();
    
        var x: usize = 0;
        while (rows.next()) |row| {
            try letters.append(row);
            for (row, 0..) |letter, y| {
                if (letter == 'X') {
                    try x_starts.append(.{ .x = @intCast(x), .y = @intCast(y) });
                } else if (letter == 'A') {
                    try a_starts.append(.{ .x = @intCast(x), .y = @intCast(y) });
                }
            }
            x += 1;
        }
    
        // PART 1
        const xmas = countXmas(letters, x_starts);
    
        // PART 2
        const mas = countMas(letters, a_starts);
    
        return Answer{ .xmas = xmas, .mas = mas };
    }
    
    pub fn main() !void {
        const answer = try solve(@embedFile("input.txt"));
        print("Part 1: {d}\n", .{answer.xmas});
        print("Part 2: {d}\n", .{answer.mas});
    }
    
    test "test input" {
        const answer = try solve(@embedFile("test.txt"));
        try std.testing.expectEqual(18, answer.xmas);
    }
    
    

  • #Zig

    const std = @import("std");
    const List = std.ArrayList;
    
    const splitScalar = std.mem.splitScalar;
    const parseInt = std.fmt.parseInt;
    const print = std.debug.print;
    const concat = std.mem.concat;
    
    var gpa = std.heap.GeneralPurposeAllocator(.{}){};
    const alloc = gpa.allocator();
    
    const Answer = struct {
        safe: u32,
        tolerated: u32,
    };
    
    pub fn isSafe(levels: []i32) bool {
        if (levels.len == 0) {
            return false;
        }
        // slide window in pairs, advancing by one
        var it = std.mem.window(i32, levels, 2, 1);
        const first = it.first();
        const decreasing = first[0] - first[1] > 0;
        it.reset(); // rewind the iterator
    
        while (it.next()) |slice| {
            const lhs: i32 = slice[0];
            const rhs: i32 = slice[1];
            if (decreasing) {
                if (lhs <= rhs) return false;
                if (lhs - rhs < 1 or lhs - rhs > 3) return false;
            } else {
                if (rhs <= lhs) return false;
                if (rhs - lhs < 1 or rhs - lhs > 3) return false;
            }
        }
        return true;
    }
    
    pub fn solve(input: []const u8) !Answer {
        var rows = splitScalar(u8, input, '\n');
    
        // PART 1
    
        // determine how many reports are safe
        var safe_reports: u32 = 0;
        var tolerated_reports: u32 = 0;
        var unsafe_reports = List([]i32).init(alloc);
        defer unsafe_reports.deinit();
    
        while (rows.next()) |row| {
            var levels = splitScalar(u8, row, ' ');
    
            var report = List(i32).init(alloc);
            defer report.deinit();
    
            while (levels.next()) |level| {
                const value = parseInt(i32, level, 10) catch continue;
                report.append(value) catch continue;
            }
    
            if (isSafe(report.items)) {
                safe_reports += 1;
            } else {
                try unsafe_reports.append(try alloc.dupe(i32, report.items));
            }
        }
    
        // PART 2
    
        // determine how many unsafe reports can be tolerated
        for (unsafe_reports.items) |report| {
            var index: usize = 0;
            while (index < report.len) : (index += 1) {
                // mutate report by removing one level
                const mutated_report = concat(
                    alloc,
                    i32,
                    &[_][]const i32{ report[0..index], report[index + 1 ..] },
                ) catch report;
                defer alloc.free(mutated_report);
    
                if (isSafe(mutated_report)) {
                    tolerated_reports += 1;
                    break;
                }
            }
        }
    
        return Answer{ .safe = safe_reports, .tolerated = safe_reports + tolerated_reports };
    }
    
    pub fn main() !void {
        const answer = try solve(@embedFile("input.txt"));
        print("Part 1: {d}\n", .{answer.safe});
        print("Part 2: {d}\n", .{answer.tolerated});
    }
    
    test "test input" {
        const answer = try solve(@embedFile("test.txt"));
        try std.testing.expectEqual(2, answer.safe);
        try std.testing.expectEqual(4, answer.tolerated);
    

  • Zig

    const std = @import("std");
    const List = std.ArrayList;
    const Map = std.AutoHashMap;
    
    const splitSeq = std.mem.splitSequence;
    const splitScalar = std.mem.splitScalar;
    const parseInt = std.fmt.parseInt;
    const print = std.debug.print;
    const sort = std.sort.block;
    
    var gpa = std.heap.GeneralPurposeAllocator(.{}){};
    const alloc = gpa.allocator();
    
    const Answer = struct {
        distance: u32,
        similarity: u32,
    };
    
    fn lessThan(_: void, lhs: []const u8, rhs: []const u8) bool {
        return std.mem.lessThan(u8, lhs, rhs);
    }
    
    pub fn solve(input: []const u8) !Answer {
        var rows = splitScalar(u8, input, '\n');
        var left_list = List([]const u8).init(alloc);
        defer left_list.deinit();
        var right_list = List([]const u8).init(alloc);
        defer right_list.deinit();
    
        // PART 1
    
        // split the rows into two lists
        while (rows.next()) |row| {
            var sides = splitSeq(u8, row, "   ");
            try left_list.append(sides.next() orelse break);
            try right_list.append(sides.next() orelse break);
        }
        _ = left_list.pop(); // last null
    
        // sort both lists
        sort([]const u8, left_list.items, {}, lessThan);
        sort([]const u8, right_list.items, {}, lessThan);
    
        var distance: u32 = 0;
        for (left_list.items, right_list.items) |left, right| {
            distance += @abs(try parseInt(i32, left, 10) - try parseInt(i32, right, 10));
        }
    
        // PART 2
        var right_scores = Map(i32, u32).init(alloc);
        defer right_scores.deinit();
    
        // count number of item appearances in the right list
        for (right_list.items) |item| {
            const value = try parseInt(i32, item, 10);
            const result = try right_scores.getOrPut(value);
            if (!result.found_existing) {
                result.value_ptr.* = 1;
            } else {
                result.value_ptr.* += 1;
            }
        }
    
        // sum up similarity between items in left list and right list scores
        var similarity: u32 = 0;
        for (left_list.items) |item| {
            const value = try parseInt(i32, item, 10);
            const result = right_scores.get(value) orelse 0;
            similarity += @as(u32, @intCast(value)) * result;
        }
        return Answer{ .distance = distance, .similarity = similarity };
    }
    
    pub fn main() !void {
        const answer = try solve(@embedFile("input.txt"));
        print("Part 1: {d}\n", .{answer.distance});
        print("Part 2: {d}\n", .{answer.similarity});
    }
    
    test "test input" {
        const answer = try solve(@embedFile("test.txt"));
        try std.testing.expectEqual(answer.distance, 11);
        try std.testing.expectEqual(answer.similarity, 31);
    }