AoC 2024: Day 5

Challenge
1

Main thread for Day 5 of the 2024 advent of code. Feel free to discuss the challenge and ask questions. If particular discussions become large, we can break them off into new threads.

Some Rules:

  1. Please try to keep spoilers within spoiler tags. This is done by typing [spoiler]text to be blurred[\spoiler]. If you have longer sections you can also use the [details=“Title”] tags.
  2. Have Fun

Day 5 Challenge

Templates:

Resources:

Previous days discussions

Day 1: AoC 2024: Day 1
Day 2: AoC 2024: Day 2
Day 3: AoC 2024: Day 3
Day 4: AoC 2024: Day 4

4

Part 2 was really boring on this one.

Part 1 & 2 
const std = @import("std");

const util = @import("util.zig");
const gpa = util.gpa;

const data = @embedFile("data/day05.txt");

var rules = [_][100]bool{[_]bool{false} ** 100} ** 100;

pub fn main() !void {
    var p1: i64 = 0;
    var p2: i64 = 0;

    var lines = std.mem.tokenizeScalar(u8, data, '\n');
    while (lines.next()) |line| {
        var split = std.mem.tokenizeScalar(u8, line, '|');
        const left = try std.fmt.parseInt(u8, split.next().?, 10);
        const right = try std.fmt.parseInt(u8, split.next().?, 10);

        rules[left - 1][right - 1] = true;

        if (lines.peek().?.len > 5) break;
    }

    var update = std.ArrayList(u8).init(gpa);
    outer: while (lines.next()) |line| {
        update.clearRetainingCapacity();

        var split = std.mem.tokenizeScalar(u8, line, ',');
        while (split.next()) |tok| {
            const val = try std.fmt.parseInt(u8, tok, 10);
            try update.append(val);
        }

        for (update.items[0 .. update.items.len - 1], 0..) |left, i| {
            for (update.items[i..]) |right| {
                const rule = rules[right - 1][left - 1];

                if (rule) {
                    std.mem.sort(u8, update.items, {}, cmp);
                    p2 += update.items[update.items.len / 2];
                    continue :outer;
                }
            }
        }

        p1 += update.items[update.items.len / 2];
    }

    std.debug.print("part1: {}\n", .{p1});
    std.debug.print("part2: {}\n", .{p2});
}

fn cmp(_: void, a: u8, b: u8) bool {
    return !rules[b - 1][a - 1];
}

cleaned it up a bit:

Part 1 & 2 
const std = @import("std");

const util = @import("util.zig");
const gpa = util.gpa;

const data = @embedFile("data/day05.txt");

var rules = [_][100]bool{[_]bool{false} ** 100} ** 100;

pub fn main() !void {
    var p1: i64 = 0;
    var p2: i64 = 0;

    var lines = std.mem.tokenizeScalar(u8, data, '\n');
    var update = std.ArrayList(u32).init(gpa);

    while (lines.next()) |line| {
        if (line.len < 6) {
            var split = std.mem.tokenizeScalar(u8, line, '|');
            const left = try std.fmt.parseInt(u32, split.next().?, 10);
            const right = try std.fmt.parseInt(u32, split.next().?, 10);
            rules[left][right] = true;

            continue;
        }

        defer update.clearRetainingCapacity();

        var split = std.mem.tokenizeScalar(u8, line, ',');
        while (split.next()) |tok| {
            const val = try std.fmt.parseInt(u32, tok, 10);
            try update.append(val);
        }

        var sorted = true;
        for (1..update.items.len) |i| {
            if (rules[update.items[i - 1]][update.items[i]]) continue;
            sorted = false;
        }

        if (sorted) {
            p1 += update.items[update.items.len / 2];
        } else {
            std.mem.sort(u32, update.items, {}, cmp);
            p2 += update.items[update.items.len / 2];
        }
    }

    std.debug.print("part1: {}\n", .{p1});
    std.debug.print("part2: {}\n", .{p2});
}

fn cmp(_: void, a: u32, b: u32) bool {
    return !rules[b][a];
}
9

this one uses only static memory and a simple custom parse(). rules are an array of bit sets. timing inside of main shows around 55us and poop reports total of 273us. a nice improvement from my original which took around 1ms.

$ zig build-exe 05.2.zig -OReleaseFast -femit-bin=/tmp/aoc-exe && /tmp/aoc-exe && poop -d 2000 '/tmp/aoc-exe'
took 54.939us
#...
Benchmark 1 (6652 runs): /tmp/aoc-exe
  measurement          mean ± σ            min … max           outliers
  wall_time           273us ± 36.1us     233us … 1.07ms         69 ( 1%)
#...

https://zigbin.io/eeb0dc

1 Like
11

I am a bit sad that I did not think about making a compare function and a big 100x100 table for fast checks.

I tried to keep the hot loop in cache with an array of sets of pages that need to be after. Then I had this idea of scoring pages by number of rules, which meh. So I kept in under one ms, but that turns out to not be particularly good…

https://zigbin.io/8b1e60

2

this is cleaned up quite a bit. my first part2 solution had a bunch of extra garbage.
https://zigbin.io/24c9f7

3

Parts 1 and 2 only differ in a single line, but I wanted them as separate functions.

Part 1 & 2 
const std = @import("std");

const Rule = struct {
    before: u16,
    after: u16,
};

pub fn part1(allocator: std.mem.Allocator, input: []const u8) !u32 {
    var rules = std.ArrayList(Rule).init(allocator);
    defer rules.deinit();
    var it = std.mem.splitScalar(u8, input, '\n');
    var isRules = true;
    var acc: u32 = 0;
    while (it.next()) |line| {
        if (line.len == 0) {
            isRules = false;
            continue;
        }
        if (isRules) {
            var rit = std.mem.tokenizeScalar(u8, line, '|');
            const rule = Rule{
                .before = try std.fmt.parseInt(u16, rit.next().?, 10),
                .after = try std.fmt.parseInt(u16, rit.next().?, 10),
            };
            try rules.append(rule);
        } else {
            var pages = std.ArrayList(u16).init(allocator);
            defer pages.deinit();
            var pit = std.mem.tokenizeScalar(u8, line, ',');
            while (pit.next()) |p| {
                try pages.append(try std.fmt.parseInt(u16, p, 10));
            }
            var tmp = try pages.clone();
            defer tmp.deinit();
            std.mem.sort(u16, pages.items, rules.items, lessByRules);
            if (std.mem.eql(u16, tmp.items, pages.items)) {
                acc += pages.items[pages.items.len / 2];
            }
        }
    }
    return acc;
}

pub fn part2(allocator: std.mem.Allocator, input: []const u8) !u32 {
    var rules = std.ArrayList(Rule).init(allocator);
    defer rules.deinit();
    var it = std.mem.splitScalar(u8, input, '\n');
    var isRules = true;
    var acc: u32 = 0;
    while (it.next()) |line| {
        if (line.len == 0) {
            isRules = false;
            continue;
        }
        if (isRules) {
            var rit = std.mem.tokenizeScalar(u8, line, '|');
            const rule = Rule{
                .before = try std.fmt.parseInt(u16, rit.next().?, 10),
                .after = try std.fmt.parseInt(u16, rit.next().?, 10),
            };
            try rules.append(rule);
        } else {
            var pages = std.ArrayList(u16).init(allocator);
            defer pages.deinit();
            var pit = std.mem.tokenizeScalar(u8, line, ',');
            while (pit.next()) |p| {
                try pages.append(try std.fmt.parseInt(u16, p, 10));
            }
            var tmp = try pages.clone();
            defer tmp.deinit();
            std.mem.sort(u16, pages.items, rules.items, lessByRules);
            if (!std.mem.eql(u16, tmp.items, pages.items)) {
                acc += pages.items[pages.items.len / 2];
            }
        }
    }
    return acc;
}

fn lessByRules(rules: []Rule, a: u16, b: u16) bool {
    for (rules) |r| {
        if (a == r.before and b == r.after) return true;
        if (a == r.after and b == r.before) return false;
    }
    return false;
}
5

Spent wayyyyy too much time stuggling with array to slice conversion. This is clearly overcomplicated.

const std = @import("std");
const u = @import("util.zig");

const data = @embedFile("data/day05.txt");

const Rule = struct {
    before: usize,
    after: usize,

    fn check(self: @This(), up: Update) bool {
        var last_before: ?usize = null;
        var first_after: ?usize = null;
        var i: usize = 0;
        var j: usize = up.len;
        while (i < up.len) : (i += 1) {
            j = up.len - i - 1;
            if (first_after == null and up[i] == self.after) {
                first_after = i;
            }
            if (last_before == null and up[j] == self.before) {
                last_before = j;
            }
            if (last_before != null and first_after != null and last_before.? > first_after.?) {
                return false;
            }
        }
        return true;
    }

    fn sort(self: @This(), up: Update) void {
        var last_before: ?usize = null;
        var first_after: ?usize = null;
        var i: usize = 0;
        var j: usize = up.len;
        while (i < up.len) : (i += 1) {
            j = up.len - i - 1;
            if (first_after == null and up[i] == self.after) {
                first_after = i;
            }
            if (last_before == null and up[j] == self.before) {
                last_before = j;
            }
            if (last_before != null and first_after != null and last_before.? > first_after.?) {
                std.mem.swap(usize, &up[last_before.?], &up[first_after.?]);
                break;
            }
        }
    }
};

const Update = []usize;

fn isValidUpdate(up: Update, rules: []Rule) bool {
    for (rules) |rule| {
        if (!rule.check(up)) {
            return false;
        }
    }
    return true;
}

fn level1(updates: []Update, rules: []Rule) !void {
    var sum_middle: usize = 0;
    for (updates) |up| {
        if (isValidUpdate(up, rules)) {
            const middle_index = @divFloor(up.len, 2);
            sum_middle += up[middle_index];
        }
    }
    u.print("{}\n", .{sum_middle});
}

fn level2(updates: []Update, rules: []Rule) !void {
    var sum_middle: usize = 0;
    for (updates) |up| {
        var count = false;
        while (!isValidUpdate(up, rules)) {
            count = true;
            for (rules) |rule| {
                rule.sort(up);
            }
        }
        if (count) {
            const middle_index = @divFloor(up.len, 2);
            sum_middle += up[middle_index];
        }
    }
    u.print("{}\n", .{sum_middle});
}

pub fn main() !void {
    var arena = std.heap.ArenaAllocator.init(u.gpa);
    defer arena.deinit();
    const alloc = arena.allocator();

    var rules = u.List(Rule).init(alloc);
    var updates = u.List(Update).init(alloc);

    // parsing
    var step: enum { rules, updates } = .rules;
    var it = std.mem.splitScalar(u8, data, '\n');
    while (it.next()) |line| {
        if (std.mem.eql(u8, line, "")) {
            u.print("skipping\n", .{});
            step = .updates;
            continue;
        }
        switch (step) {
            .rules => {
                var it_rule = std.mem.tokenizeScalar(u8, line, '|');
                const before = it_rule.next() orelse unreachable;
                const after = it_rule.next() orelse unreachable;
                const r = Rule{
                    .before = try u.parseInt(usize, before, 0),
                    .after = try u.parseInt(usize, after, 0),
                };
                try rules.append(r);
            },
            .updates => {
                var up = u.List(usize).init(alloc);
                var it_update = std.mem.tokenizeScalar(u8, line, ',');
                while (it_update.next()) |num| {
                    try up.append(try u.parseInt(usize, num, 0));
                }
                try updates.append(up.items);
            },
        }
    }

    try level1(updates.items, rules.items);
    try level2(updates.items, rules.items);
}

// Generated from template/template.zig.
// Run `zig build generate` to update.
// Only unmodified days will be updated.
6
Part 1 
const std = @import("std");

const data = @embedFile("data.txt");

pub fn main() !void {
    var arena = std.heap.ArenaAllocator.init(std.heap.page_allocator);
    defer arena.deinit();
    const allocator = arena.allocator();

    var ruleBook = std.AutoHashMap(u32, std.ArrayList(u32)).init(allocator);

    var lines = std.mem.tokenizeScalar(u8, data, '\n');
    var parseRule = true;
    var sum_of_middles: u32 = 0;
    outer: while (lines.next()) |line| {
        if (line.len != 5) parseRule = false;
        if (parseRule) {
            // l can't be seen after r
            const l = try std.fmt.parseInt(u32, line[0..2], 10);
            const r = try std.fmt.parseInt(u32, line[3..5], 10);
            var list = ruleBook.getPtr(r) orelse blk: {
                const new_list = std.ArrayList(u32).init(allocator);
                try ruleBook.put(r, new_list);
                break :blk ruleBook.getPtr(r).?;
            };
            try list.append(l);
            continue;
        }
        var nums = std.mem.tokenizeScalar(u8, line, ',');
        var updateList = std.ArrayList(u32).init(allocator);
        var cantSee = std.AutoHashMap(u32, void).init(allocator);
        while (nums.next()) |num_str| {
            const num = try std.fmt.parseInt(u32, num_str, 10);
            if (cantSee.contains(num)) continue :outer; // invalid update
            try updateList.append(num);
            // ruleBook.get(num) should return an ArrayList of every number that can't be seen after num
            const cantSeeNums = ruleBook.get(num) orelse continue;
            for (cantSeeNums.items) |n| {
                try cantSee.put(n, {});
            }
        }
        sum_of_middles += updateList.items[updateList.items.len / 2];
    }
    std.debug.print("Sum: {d}\n", .{sum_of_middles});
}
7
Part 1 and 2 
const std = @import("std");

const actual_data = @embedFile("./day05.txt");

// const data = test_data;
const data = actual_data;

pub fn main() !void {
    const allocator = std.heap.page_allocator;

    var parts = std.mem.splitSequence(u8, data, "\n\n");
    const rules_raw = parts.next() orelse unreachable;
    const pages = parts.next() orelse unreachable;

    var rules = std.ArrayList([2]u16).init(allocator);

    var rules_iter = std.mem.splitScalar(u8, rules_raw, '\n');
    while (rules_iter.next()) |line| {
        var rule = try rules.addOne();
        var rule_iter = std.mem.splitScalar(u8, line, '|');
        rule[0] = try std.fmt.parseInt(u16, rule_iter.next() orelse unreachable, 10);
        rule[1] = try std.fmt.parseInt(u16, rule_iter.next() orelse unreachable, 10);
    }

    const part1_result = try part1(rules.items, pages);
    const part2_result = try part2(rules.items, pages);

    const stdout = std.io.getStdOut().writer();
    try stdout.print("Part 1: {d}\n", .{part1_result});
    try stdout.print("Part 2: {d}\n", .{part2_result});
}

fn part1(rules: []const [2]u16, pages: []const u8) !usize {
    var section_iter = std.mem.splitScalar(u8, pages, '\n');
    var sum: usize = 0;

    var buf: [32]u16 = undefined;

    next_section: while (section_iter.next()) |section| {
        if (section.len == 0) {
            continue;
        }

        var page_iter = std.mem.splitScalar(u8, section, ',');
        var page_count: usize = 0;
        while (page_iter.next()) |page_num| {
            const page = try std.fmt.parseInt(u16, page_num, 10);
            buf[page_count] = page;
            page_count += 1;
        }

        for (rules) |rule| {
            const first = std.mem.indexOf(u16, buf[0..page_count], rule[0..1]);
            if (first) |f| {
                const second = std.mem.indexOf(u16, buf[0..page_count], rule[1..2]);
                if (second) |s| {
                    if (f > s) {
                        continue :next_section;
                    }
                }
            }
        }
        sum += buf[page_count / 2];
    }
    return sum;
}

fn fixPages(pages: []u16, rules: []const [2]u16) void {
    var passes: usize = 0;
    while (passes < 32) : (passes += 1) {
        log.debug("Pass {d}", .{passes});
        var is_fixed = true;
        for (rules) |rule| {
            const first = std.mem.indexOf(u16, pages, rule[0..1]);
            if (first) |f| {
                const second = std.mem.indexOf(u16, pages, rule[1..2]);
                if (second) |s| {
                    if (f > s) {
                        const temp = pages[f];
                        pages[f] = pages[s];
                        pages[s] = temp;
                        is_fixed = false;
                    }
                }
            }
        }
        if (is_fixed) {
            return;
        }
    }
    log.err("Failed to fix pages", .{});
    return;
}

fn part2(rules: []const [2]u16, pages: []const u8) !usize {
    var section_iter = std.mem.splitScalar(u8, pages, '\n');
    var sum: usize = 0;

    var buf: [32]u16 = undefined;

    while (section_iter.next()) |section| {
        if (section.len == 0) {
            continue;
        }

        var page_iter = std.mem.splitScalar(u8, section, ',');
        var page_count: usize = 0;
        while (page_iter.next()) |page_num| {
            const page = try std.fmt.parseInt(u16, page_num, 10);
            buf[page_count] = page;
            page_count += 1;
        }

        rules_check: for (rules) |rule| {
            const first = std.mem.indexOf(u16, buf[0..page_count], rule[0..1]);
            if (first) |f| {
                const second = std.mem.indexOf(u16, buf[0..page_count], rule[1..2]);
                if (second) |s| {
                    if (f > s) {
                        fixPages(buf[0..page_count], rules);
                        sum += buf[page_count / 2];
                        break :rules_check;
                    }
                }
            }
        }
    }
    return sum;
}
8

Definitely had to think about this one more. Not sure if what I ended up with was particularly efficient.

Part 1 
const std = @import("std");

const input = @embedFile("input.txt");

pub fn main() !void {
    var arena = std.heap.ArenaAllocator.init(std.heap.page_allocator);
    defer arena.deinit();

    // parse rules
    var rules = std.AutoHashMap(u8, std.ArrayListUnmanaged(u8)).init(arena.allocator());
    var update_section_start: usize = 0;
    var rule_iter = std.mem.splitScalar(u8, input, '\n');
    while (rule_iter.next()) |rule| {
        if (rule.len == 0) {
            // a blank line separates the rules and updates in the input.
            update_section_start = rule_iter.index.?;
            break;
        }
        const sep = std.mem.indexOfScalar(u8, rule, '|').?;
        const before_num = try std.fmt.parseInt(u8, rule[0..sep], 10);
        const after_num = try std.fmt.parseInt(u8, rule[sep + 1 ..], 10);
        const entry = try rules.getOrPutValue(after_num, .empty);
        try entry.value_ptr.append(arena.allocator(), before_num);
    }

    var result: u32 = 0;
    var update_iter = std.mem.tokenizeScalar(u8, input[update_section_start..], '\n');
    var update_nums = std.ArrayList(u8).init(arena.allocator());
    var banned_nums = std.AutoHashMap(u8, void).init(arena.allocator());

    next_update: while (update_iter.next()) |update| {
        update_nums.clearRetainingCapacity();
        banned_nums.clearRetainingCapacity();

        var num_iter = std.mem.tokenizeScalar(u8, update, ',');
        while (num_iter.next()) |num_string| {
            const num = try std.fmt.parseInt(u8, num_string, 10);
            if (banned_nums.contains(num)) continue :next_update;

            const rule = rules.get(num) orelse continue;

            for (rule.items) |rule_num| {
                try banned_nums.put(rule_num, {});
            }

            try update_nums.append(num);
        }

        result += update_nums.items[update_nums.items.len / 2];
    }

    std.debug.print("{d}\n", .{result});
}
Part 2 
const std = @import("std");

const input = @embedFile("input.txt");

pub fn main() !void {
    var arena = std.heap.ArenaAllocator.init(std.heap.page_allocator);
    defer arena.deinit();

    // parse rules
    var rules = std.AutoHashMap(u8, std.ArrayListUnmanaged(u8)).init(arena.allocator());
    var update_section_start: usize = 0;
    var rule_line_iter = std.mem.splitScalar(u8, input, '\n');
    while (rule_line_iter.next()) |rule| {
        if (rule.len == 0) {
            // a blank line separates the rules and updates in the input.
            update_section_start = rule_line_iter.index.?;
            break;
        }
        const sep = std.mem.indexOfScalar(u8, rule, '|').?;
        const before_num = try std.fmt.parseInt(u8, rule[0..sep], 10);
        const after_num = try std.fmt.parseInt(u8, rule[sep + 1 ..], 10);

        const entry = try rules.getOrPutValue(after_num, .empty);
        try entry.value_ptr.append(arena.allocator(), before_num);
    }

    var result: u32 = 0;
    var update_iter = std.mem.tokenizeScalar(u8, input[update_section_start..], '\n');
    var update_nums = std.ArrayList(u8).init(arena.allocator());
    var banned_nums = std.AutoHashMap(u8, void).init(arena.allocator());

    next_update: while (update_iter.next()) |update| {
        update_nums.clearRetainingCapacity();
        banned_nums.clearRetainingCapacity();

        var num_iter = std.mem.tokenizeScalar(u8, update, ',');
        while (num_iter.next()) |num_string| {
            const num = try std.fmt.parseInt(u8, num_string, 10);
            try update_nums.append(num);
        }

        for (update_nums.items) |num| {
            if (banned_nums.contains(num)) {
                std.mem.sort(u8, update_nums.items, rules, lessThan);
                result += update_nums.items[update_nums.items.len / 2];
                continue :next_update;
            }

            const rule = rules.get(num) orelse continue;
            for (rule.items) |rule_num| {
                try banned_nums.put(rule_num, {});
            }
        }
    }

    std.debug.print("{d}\n", .{result});
}

fn lessThan(rules: std.AutoHashMap(u8, std.ArrayListUnmanaged(u8)), left: u8, right: u8) bool {
    const rule_nums = rules.get(right) orelse return false;
    for (rule_nums.items) |num| {
        if (num == left) return true;
    }
    return false;
}
10

Decided to post the code on zigbin, as that seems pretty neet:

https://zigbin.io/05ccfe

I really misinterpreted the directions and thought that rules would be commutative (I.e if there was a rule 97 | 56, and 56 | 67, then we would have to also make sure 97 never appeared after 67.)

I started to build out a big graph structure and do some graph traversal stuff. Once I realized it I had gone too far and decided to just morph the code into what was needed.

Kind a bummed that it wasn’t needed.

12

I totally misunderstood today’s problem and wrote some topological sort routines – they worked for the test but not for the actual data. After a long while I realized I was not doing what was being requested… :frowning: Of course, I guess this is par for the course with AoC.