AoC 2025: Day 5

Challenge
1

Main thread for Day 5 of the 2025 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.

Notice that Advent of Code has changed it’s schedule and there will only be 12 days of puzzles this year.

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. If you use the new WYSIWYG editor, remember to close the details section, as it is opened by default. This is an issue (feature?) of the newest discourse updates. If you use markdown, then you can remove the “open" parameter (not in by default unless you use the WYSIWYG editor)
  2. Have Fun

Day 5 Challenge

Templates:

Resources:

2

Happy with the terseness of my solution today! A bit of funky wrapping math at the end to avoid removing items from an ArrayList …but otherwise the code smells OK lol.

1 Like
3

Used BST to solve both parts, but 300 lines :melting_face:

2 Likes
4

I think today’s problem is quite practical. NonConsecutiveRange is a structure that is often used when dealing with actual problems, so I have encapsulated it.

const std = @import("std");

const ConsecutiveRange = packed struct {
    end: usize,
    start: usize,
    const Backing = std.meta.Int(.unsigned, @bitSizeOf(ConsecutiveRange));
    pub fn packStartEnd(start: usize, end: usize) ConsecutiveRange {
        return .{ .start = start, .end = end };
    }
    pub fn asc(_: void, a: ConsecutiveRange, b: ConsecutiveRange) bool {
        return @as(Backing, @bitCast(a)) < @as(Backing, @bitCast(b));
    }
};
const NonConsecutiveRange = struct {
    consecutive_ranges: []ConsecutiveRange,
    const Builder = struct {
        raw: std.ArrayList(ConsecutiveRange) = .empty,
        to_merge: ConsecutiveRange = undefined,
        merged: std.ArrayList(ConsecutiveRange) = .empty,
        pub const init: Builder = .{};
        pub fn append(self: *Builder, allocator: std.mem.Allocator, new_consecutive_range: ConsecutiveRange) !void {
            try self.raw.append(allocator, new_consecutive_range);
        }
        pub fn toOwnedNonConsecutiveRange(self: *Builder, allocator: std.mem.Allocator) !NonConsecutiveRange {
            defer {
                self.raw.deinit(allocator);
                self.* = undefined;
            }
            if (self.raw.items.len == 0) return .{ .consecutive_ranges = &[0]ConsecutiveRange{} };
            std.mem.sortUnstable(ConsecutiveRange, self.raw.items, {}, ConsecutiveRange.asc);
            self.to_merge = self.raw.items[0];
            for (self.raw.items[1..]) |r| {
                if (r.start > self.to_merge.end + 1) {
                    try self.merged.append(allocator, self.to_merge);
                    self.to_merge = r;
                    continue;
                }
                if (r.end <= self.to_merge.end) continue;
                self.to_merge = .packStartEnd(self.to_merge.start, r.end);
            }
            try self.merged.append(allocator, self.to_merge);
            return .{ .consecutive_ranges = try self.merged.toOwnedSlice(allocator) };
        }
    };
    pub fn contain(self: NonConsecutiveRange, value: usize) bool {
        var bound_low: usize = 0;
        var bound_high: usize = self.consecutive_ranges.len;
        while (bound_low < bound_high) {
            const mid = bound_low + (bound_high - bound_low) / 2;
            const cr = self.consecutive_ranges[mid];
            if (value < cr.start) bound_high = mid else if (value > cr.end) bound_low = mid + 1 else return true;
        }
        return false;
    }
};

pub fn part1(input: []const u8) !usize {
    var gpa: std.heap.DebugAllocator(.{}) = .init;
    const allocator = gpa.allocator();
    var line_it = std.mem.splitScalar(u8, input, '\n');
    var sum: usize = 0;
    const ncrs = read_ranges: {
        var ncrbuilder: NonConsecutiveRange.Builder = .init;
        while (line_it.next()) |line| {
            if (line.len == 0) break :read_ranges try ncrbuilder.toOwnedNonConsecutiveRange(allocator);
            var it = std.mem.splitScalar(u8, line, '-');
            const start_str = it.next().?;
            const end_str = it.next().?;
            const start = try std.fmt.parseUnsigned(usize, start_str, 10);
            const end = try std.fmt.parseUnsigned(usize, end_str, 10);
            const cr: ConsecutiveRange = .packStartEnd(start, end);
            try ncrbuilder.append(allocator, cr);
        }
        unreachable;
    };
    scan_food: while (line_it.next()) |line| {
        if (line.len == 0) break :scan_food;
        const food = try std.fmt.parseUnsigned(usize, line, 10);
        if (ncrs.contain(food)) sum += 1;
    }
    return sum;
}

pub fn part2(input: []const u8) !usize {
    var gpa: std.heap.DebugAllocator(.{}) = .init;
    const allocator = gpa.allocator();
    var line_it = std.mem.splitScalar(u8, input, '\n');
    var sum: usize = 0;
    const ncrs = read_ranges: {
        var ncrbuilder: NonConsecutiveRange.Builder = .init;
        while (line_it.next()) |line| {
            if (line.len == 0) break :read_ranges try ncrbuilder.toOwnedNonConsecutiveRange(allocator);
            var it = std.mem.splitScalar(u8, line, '-');
            const start_str = it.next().?;
            const end_str = it.next().?;
            const start = try std.fmt.parseUnsigned(usize, start_str, 10);
            const end = try std.fmt.parseUnsigned(usize, end_str, 10);
            const cr: ConsecutiveRange = .packStartEnd(start, end);
            try ncrbuilder.append(allocator, cr);
        }
        unreachable;
    };
    for (ncrs.consecutive_ranges) |cr| {
        sum += cr.end - cr.start + 1;
    }
    return sum;
}
1 Like
5

Nothing too complicated. It is actually slightly quicker to just sort the ranges after loading, instead of inserting into position and moving elements around, since the std sort is a lot better than my pseudo insertion sort.

const std = @import("std");

pub fn main() !void {
    const input = @embedFile("05.txt");

    var part1: usize = 0;
    var part2: usize = 0;

    const Range = struct { lo: usize, hi: usize };
    var ranges_storage: [256]Range = undefined;
    var ranges: std.ArrayList(Range) = .initBuffer(&ranges_storage);

    var it = std.mem.tokenizeScalar(u8, input, '\n');
    while (it.next()) |line| {
        const index = std.mem.findScalar(u8, line, '-') orelse break;
        const lo = try std.fmt.parseUnsigned(usize, line[0..index], 10);
        const hi = try std.fmt.parseUnsigned(usize, line[index + 1 ..], 10);

        // preserve order in ranges
        var l: usize = 0;
        var r = ranges.items.len;

        while (l < r) {
            const mid = l + (r - l) / 2;
            if (ranges.items[mid].lo < lo) l = mid + 1 else r = mid;
        }

        try ranges.insertBounded(l, .{ .lo = lo, .hi = hi });
    }

    // merge overlapping ranges in place
    {
        var i: usize = 0;
        var r = ranges.items[0];
        for (ranges.items[1..]) |n| {
            if (r.hi >= n.hi) {
                continue;
            }

            if (r.hi >= n.lo) {
                r.hi = n.hi;
                continue;
            }

            part2 += r.hi - r.lo + 1;
            ranges.items[i] = r;
            i += 1;
            r = n;
        }

        part2 += r.hi - r.lo + 1;
        ranges.items[i] = r;
        i += 1;
        ranges.items.len = i;
    }

    while (it.next()) |line| {
        const n = try std.fmt.parseUnsigned(usize, line, 10);

        for (ranges.items) |r| {
            if (n > r.hi) {
                continue;
            }

            if (r.lo <= n and n <= r.hi) {
                part1 += 1;
                break;
            }
        }
    }

    std.debug.print("1: {}\n2: {}\n", .{ part1, part2 });
}
6

Part 2:

const std = @import(“std”);
const data = @embedFile(“data.txt”);
const Range = struct { lo: usize, hi: usize };

pub fn main() !void {
var debug_allocator = std.heap.DebugAllocator(.{}){};
defer _ = debug_allocator.deinit();
const gpa = debug_allocator.allocator();

var ranges: std.ArrayList(Range) = .{};
defer ranges.deinit(gpa);

var iter = std.mem.splitScalar(u8, data, '\n');
outer_loop: while (iter.next()) |line| {
    if (line.len == 0) break;
    var split = std.mem.splitScalar(u8, line, '-');
    var lo = try std.fmt.parseInt(usize, split.next().?, 10);
    var hi = try std.fmt.parseInt(usize, split.next().?, 10);
    for (ranges.items, 0..) |r, i| {
        if (lo >= r.lo and hi <= r.hi) continue :outer_loop; // complete overlap - inside existing range
        if (lo >= r.lo and lo <= r.hi and hi > r.hi) lo = r.hi + 1;
        if (hi >= r.lo and hi <= r.hi and lo < r.lo) hi = r.lo -| 1;
        if (lo < r.lo and hi > r.hi) _ = ranges.orderedRemove(i); // complete overlap - outside existing range
    }
    try ranges.append(gpa, .{ .lo = lo, .hi = hi });
}

var total: usize = 0;
for (ranges.items) |rg| {
    total += (rg.hi - rg.lo + 1);
}
std.debug.print("total: {d}\n", .{total});

}
1 Like
7

okayish code

the idea:

  1. collect all ranges
  2. solve part1 by checking if the numbers are contained in any range
  3. sort ranges by start value ascending
  4. if the end value of n-th range is bigger than n+1–th value, the ranges overlap
  5. solve all overlaps, when they occur, set n to 0,0, so we dont need to do any memcpying etc,
  6. part2 solution is the sum of all the ranges
const std = @import("std");
const data = @embedFile("data");

pub fn main() !void {
    // create a ranges slice
    var it = std.mem.tokenizeAny(u8, data, "\n");

    var ranges_buf: [1024][2]usize = undefined;
    var ranges_count: usize = 0;
    r: while (it.next()) |range| {
        const delimiter: usize = blk: {
            for (range, 0..) |c, i| {
                if (c == '-') break :blk i;
            }
            break :r;
        };

        const start = try std.fmt.parseInt(usize, range[0..delimiter], 10);
        const end = try std.fmt.parseInt(usize, range[delimiter + 1 .. range.len], 10);

        ranges_buf[ranges_count][0] = start;
        ranges_buf[ranges_count][1] = end;

        ranges_count += 1;
    }

    var ranges = ranges_buf[0..ranges_count];

    var result: usize = 0;

    // part 1

    // start parsing actual numbers
    it = std.mem.tokenizeAny(u8, data, "\n");
    for (0..ranges_count) |_| _ = it.next();

    while (it.next()) |num| {
        const n = try std.fmt.parseInt(usize, num, 10);

        for (0..ranges_count) |i| {
            if (n >= ranges[i][0] and n <= ranges[i][1]) {
                result += 1;
                break;
            }
        }
    }

    // part 2

    var result2: usize = 0;

    std.mem.sort([2]usize, ranges, {}, lessThanFn);

    for (0..ranges.len - 1) |r| {
        const first = ranges_buf[r];
        const second = ranges_buf[r + 1];

        if (first[1] >= second[0]) {
            ranges_buf[r + 1][0] = first[0];
            if (first[1] > second[1]) {
                ranges_buf[r + 1][1] = first[1];
            }

            // flag exluded ranges with zeros
            ranges_buf[r][0] = 0;
            ranges_buf[r][1] = 0;
        }
    }

    // count non exluded ranges
    for (ranges) |r| if (r[0] != 0 and r[1] != 0) {
        result2 += r[1] - r[0] + 1;
    };

    std.debug.print("Result is {}\n", .{result});
    std.debug.print("Result2 is {}\n", .{result2});
}

fn lessThanFn(ctx: void, lhs: [2]usize, rhs: [2]usize) bool {
    _ = ctx;

    if (lhs[0] < rhs[0])
        return true
    else if (lhs[0] == rhs[0])
        return lhs[1] < rhs[1]
    else
        return false;
}
1 Like
8

Switching a bit between the days this year, just finished day 5:

Part 1

fn part1(allocator: Allocator) anyerror!void {
    var fresh_ingredients: usize = 0;

    const input_embed = @embedFile("puzzle-05");
    const split_at = std.mem.indexOf(u8, input_embed, "\n\n").?;
    const ranges = std.mem.trim(u8, input_embed[0..split_at], "\n");
    const ingredients_ids = std.mem.trim(u8, input_embed[split_at..], "\n");

    var ranges_list: std.array_list.Managed(@Vector(2, usize)) = .init(allocator);
    defer ranges_list.deinit();
    var ranges_reader: std.Io.Reader = .fixed(ranges);
    while (try ranges_reader.takeDelimiter('\n')) |range| {
        const sep = std.mem.indexOf(u8, range, "-").?;
        try ranges_list.append(.{
            try std.fmt.parseInt(usize, range[0..sep], 10),
            try std.fmt.parseInt(usize, range[sep + 1 ..], 10),
        });
    }

    var instructions_reader: std.Io.Reader = .fixed(ingredients_ids);
    while (try instructions_reader.takeDelimiter('\n')) |line| {
        const num = try std.fmt.parseInt(usize, line, 10);
        var is_fresh = false;
        for (ranges_list.items) |range| {
            is_fresh = (num >= range[0] and num <= range[1]);
            if (is_fresh) break;
        }
        if (is_fresh) fresh_ingredients += 1;
    }

    std.debug.print("Result: {d}\n", .{fresh_ingredients});
}

Part 2

fn part2(allocator: Allocator) anyerror!void {
    const input_embed = @embedFile("puzzle-05");
    const split_at = std.mem.indexOf(u8, input_embed, "\n\n").?;
    const ranges = std.mem.trim(u8, input_embed[0..split_at], "\n");

    var ranges_list: std.array_list.Managed(@Vector(2, usize)) = .init(allocator);
    defer ranges_list.deinit();

    var ranges_reader: std.Io.Reader = .fixed(ranges);
    while (try ranges_reader.takeDelimiter('\n')) |range| {
        const sep = std.mem.indexOf(u8, range, "-").?;
        const lower = try std.fmt.parseInt(usize, range[0..sep], 10);
        const upper = try std.fmt.parseInt(usize, range[sep + 1 ..], 10);

        try ranges_list.append(.{ lower, upper });
    }

    std.mem.sort(@Vector(2, usize), ranges_list.items, {}, comptime struct {
        pub fn f(_: void, a: @Vector(2, usize), b: @Vector(2, usize)) bool {
            return a[0] < b[0];
        }
    }.f);

    for (0..ranges_list.items.len - 1) |r| {
        const curr = ranges_list.items[r];
        const next = ranges_list.items[r + 1];

        // Current range overlaps next range on lower bound of next
        if (curr[1] >= next[0]) {

            // Extend next range on lower end
            ranges_list.items[r + 1][0] = curr[0];

            // Current range overlaps next range on upper bound of next
            if (curr[1] > next[1]) {
                // Extend next range on upper end
                ranges_list.items[r + 1][1] = curr[1];
            }

            // Dismiss current range
            // (as the next range has been expanded and ids shouldn't be
            // counted twice)
            ranges_list.items[r] = .{ 0, 0 };
        }
    }

    var sum: usize = 0;
    for (ranges_list.items) |r| {
        if (r[0] == 0 or r[1] == 0) continue;
        sum += r[1] - r[0] + 1;
    }

    std.debug.print("Result: {d}\n", .{sum});
}