AoC 2024: Day 2

Challenge
1

Main thread for Day 2 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 2 Challenge

Templates:

Resources:

1910115-f465b6d3

Previous days discussions

Day 1: AoC 2024: Day 1

1 Like
2

It’s ugly but it works so it is what it is I guess :slight_smile:

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

pub fn isSafe(items: []i32) bool {
    var is_ascending = true;
    var is_descending = true;
    for (items[0 .. items.len - 1], items[1..]) |n0, n1| {
        const diff = @abs(n0 - n1);
        if (diff < 1 or diff > 3) return (false);

        if (n0 < n1) {
            is_descending = false;
        }

        if (n0 > n1) {
            is_ascending = false;
        }
    }

    if ((is_ascending and is_descending) or (!is_ascending and !is_descending)) {
        return (false);
    } else {
        return (true);
    }
}

pub fn main() !void {
    var gpa: std.heap.GeneralPurposeAllocator(.{}) = .{};
    defer _ = gpa.deinit();

    var arena: std.heap.ArenaAllocator = .init(gpa.allocator());
    defer arena.deinit();

    const allocator = gpa.allocator();
    const cwd = std.fs.cwd();

    const input_file = try cwd.openFile(opt.path, .{ .mode = .read_only });
    defer input_file.close();

    const input_text = try input_file.readToEndAlloc(allocator, std.math.maxInt(i32));
    defer allocator.free(input_text);

    var result: i32 = 0;
    var line_iter = std.mem.tokenizeScalar(u8, input_text, '\n');
    while (line_iter.next()) |input_line| {
        defer _ = arena.reset(.retain_capacity);
        var input_list: std.ArrayList(i32) = .init(arena.allocator());

        var input_iter = std.mem.tokenizeScalar(u8, input_line, ' ');
        while (input_iter.next()) |number| {
            try input_list.append(try std.fmt.parseInt(i32, number, 10));
        }

        const safety_report = try input_list.toOwnedSlice();
        result += @intFromBool(isSafe(safety_report));
    }
    std.debug.print("result1 = {d}\n", .{result});
}
Part 2 
const std = @import("std");
const opt = @import("build_options");

fn inspectFurther(subitems: []i32) bool {
    var is_ascending = true;
    var is_descending = true;

    for (subitems[0 .. subitems.len - 1], subitems[1..]) |n0, n1| {
        const diff = @abs(n0 - n1);
        if (diff < 1 or diff > 3) {
            return (false);
        }
        if (n0 < n1) {
            is_descending = (false);
        }
        if (n0 > n1) {
            is_ascending = (false);
        }
    }

    if ((is_ascending and is_descending) or (!is_ascending and !is_descending)) {
        return (false);
    } else {
        return (true);
    }
}

pub fn isSafe(items: []i32) bool {
    var buffer: [1024]i32 = undefined;
    const len = items.len;
    if (inspectFurther(items)) {
        return (true);
    }

    for (items, 0..) |_, i| {
        var new_items = buffer[0 .. len - 1];
        @memcpy(new_items[0..i], items[0..i]);
        @memcpy(new_items[i..], items[i + 1 ..]);
        if (inspectFurther(new_items)) {
            return (true);
        }
    }
    return (false);
}

pub fn main() !void {
    var gpa: std.heap.GeneralPurposeAllocator(.{}) = .{};
    defer _ = gpa.deinit();

    var arena: std.heap.ArenaAllocator = .init(gpa.allocator());
    defer arena.deinit();

    const allocator = gpa.allocator();
    const cwd = std.fs.cwd();

    const input_file = try cwd.openFile(opt.path, .{ .mode = .read_only });
    defer input_file.close();

    const input_text = try input_file.readToEndAlloc(allocator, std.math.maxInt(i32));
    defer allocator.free(input_text);

    var result: i32 = 0;
    var line_iter = std.mem.tokenizeScalar(u8, input_text, '\n');
    while (line_iter.next()) |input_line| {
        defer _ = arena.reset(.retain_capacity);
        var input_list: std.ArrayList(i32) = .init(arena.allocator());

        var input_iter = std.mem.tokenizeScalar(u8, input_line, ' ');
        while (input_iter.next()) |number| {
            try input_list.append(try std.fmt.parseInt(i32, number, 10));
        }

        const safety_report = try input_list.toOwnedSlice();
        result += @intFromBool(isSafe(safety_report));
    }
    std.debug.print("result2 = {d}\n", .{result});
}

If anyone has a better solution (which I’m sure everyone does because there’s probably a better approach than bruteforce lol) I’d be happy to see it :slight_smile:

1 Like
3

I was stuck on some edge case i could not find for part 2 for a very long time so i just ended up brute forcing it. If someone has an idea whats missing in the first approach let me know :smile:

Part 1 
fn part1() !i64 {
    var safe: i64 = 0;
    var lines = std.mem.tokenizeScalar(u8, data, '\n');

    outer: while (lines.next()) |line| {
        var toks = std.mem.tokenizeScalar(u8, line, ' ');
        var prev = try std.fmt.parseInt(i64, toks.next().?, 10);
        var current = try std.fmt.parseInt(i64, toks.next().?, 10);
        var increase = false;

        var diff = @abs(prev - current);
        if (diff == 0 or diff > 3) continue;

        if (prev < current) {
            increase = true;
        }

        prev = current;

        while (toks.next()) |tok| {
            current = try std.fmt.parseInt(i64, tok, 10);

            diff = @abs(prev - current);
            if (diff == 0 or diff > 3) continue :outer;

            if ((increase and prev > current) or (!increase and prev < current)) {
                continue :outer;
            }

            prev = current;
        }

        safe += 1;
    }

    return safe;
}
Part 2 
fn part2() !i64 {
    var safe: i64 = 0;
    var lines = std.mem.tokenizeScalar(u8, data, '\n');
    var idx: i64 = 0;

    while (lines.next()) |line| {
        var toks = std.mem.tokenizeScalar(u8, line, ' ');
        var nums = std.ArrayList(i64).init(gpa);
        while (toks.next()) |tok| {
            try nums.append(try std.fmt.parseInt(i64, tok, 10));
        }
        idx += 1;

        if (isValid(nums.items)) {
            safe += 1;
            continue;
        }

        for (0..nums.items.len) |i| {
            var nums_clone = try nums.clone();
            _ = nums_clone.orderedRemove(i);

            if (isValid(nums_clone.items)) {
                safe += 1;
                std.debug.print("{}\n", .{idx});
                break;
            }
        }
    }

    return safe;
}

fn isValid(nums: []i64) bool {
    var increase = false;
    if (nums[0] < nums[1]) increase = true;

    var prev = nums[0];

    for (nums[1..]) |current| {
        const diff = @abs(prev - current);

        if (diff == 0 or diff > 3) return false;

        if ((increase and prev > current) or (!increase and prev < current)) {
            return false;
        }

        prev = current;
    }

    return true;
}
Part 2 - first approach 
fn part2() !i64 {
    var safe: i64 = 0;
    var lines = std.mem.tokenizeScalar(u8, data, '\n');

    outer: while (lines.next()) |line| {
        var toks = std.mem.tokenizeScalar(u8, line, ' ');
        var prev = try std.fmt.parseInt(i64, toks.next().?, 10);
        var current = try std.fmt.parseInt(i64, toks.next().?, 10);
        var increase = false;
        var removed = false;

        var diff = @abs(prev - current);
        if (diff == 0 or diff > 3) {
            removed = true;
            const next = try std.fmt.parseInt(i64, toks.next().?, 10);

            diff = @abs(prev - next);
            if (diff == 0 or diff > 3) {
                diff = @abs(current - next);
                if (diff == 0 or diff > 3) continue;
                prev = current;
            }

            current = next;
        }

        if (prev < current) {
            increase = true;
        }

        prev = current;

        while (toks.next()) |tok| {
            current = try std.fmt.parseInt(i64, tok, 10);

            diff = @abs(prev - current);
            if (diff == 0 or diff > 3) {
                if (!removed) {
                    removed = true;
                    continue;
                }
                continue :outer;
            }

            if ((increase and prev > current) or (!increase and prev < current)) {
                if (!removed) {
                    removed = true;
                    continue;
                }
                continue :outer;
            }

            prev = current;
        }

        safe += 1;
    }

    return safe;
}
2 Likes
7

Like others, I couldn’t think of a good way to do part two in a single or bounded pass.

Code 
const std = @import("std");
const fmt = std.fmt;
const fs = std.fs;
const Allocator = std.mem.Allocator;

var arena = std.heap.ArenaAllocator.init(std.heap.page_allocator);
const global_alloc = arena.allocator();
const max_read = 20 * 1024;

pub fn main() !void {
    defer arena.deinit();

    const data = try loadData(global_alloc, "data/prod.txt");
    var iter = std.mem.tokenizeScalar(u8, data, '\n');
    var safe: usize = 0;
    var safe_with_dampner: usize = 0;
    while (iter.next()) |d| {
        const report = try parseReport(global_alloc, d);
        if (try analyzeReport(report)){
            safe +=1;
        } else if (try applyProblemDampner(report)){
            safe_with_dampner += 1;
        }
    }
    std.debug.print("# of Safe Reports is: {d}\n", .{safe}); 
    std.debug.print("# of Safe Reports (with dampner) is: {d}\n", .{safe + safe_with_dampner}); 
}

/// Load the Data from path
fn loadData(allocator: Allocator, path: []const u8) ![]u8 {
    const fd = try fs.cwd().openFile(path, .{});
    return try fd.readToEndAlloc(allocator, max_read);
}

fn applyProblemDampner(data:[] const isize) !bool {
    var i: usize = 0;
    var subArray = try global_alloc.alloc(isize, data.len - 1);
    while (i < data.len) : (i += 1) {
        if (i == 0) {
            @memcpy(subArray, data[1..]);

        } else if (i == data.len - 1) {
            @memcpy(subArray, data[0..data.len - 1]);
        } else {
            @memcpy(subArray[0..i], data[0..i]);
            @memcpy(subArray[i..], data[i + 1..]); 
        }
        if (try analyzeReport(subArray)) {
            return true;
        }

    }
    return false;
}

fn analyzeReport(report: []const isize) !bool {

    var window_iter = std.mem.window(isize, report, 2, 1);
    var increasing:?bool = null;
    while (window_iter.next()) | win | {
        const delta = win[0] - win[1];
        if(@abs(delta) < 1 or @abs(delta) > 3) {
            return false;
        }
        if (increasing == null) {
            increasing = delta > 0;
        } else if (increasing.? and delta < 0) {
            return false;
        } else if (!increasing.? and delta > 0) {
            return false;
        }
    }
    return true;
}

fn parseReport(allocator: Allocator, data: [] const u8) ![]isize {
    var list = std.ArrayList(isize).init(allocator);
    var iter = std.mem.tokenizeScalar(u8, data, ' ');
    while (iter.next()) |val|{
        try list.append(try fmt.parseInt(isize, val, 10));
    }
    return list.toOwnedSlice();
}
Explanation

I had a function to analyze each report according to the rules. That made adding the check in part 2 fairly straigntforward. If it failed our first pass we could check again with the modified requirements.

Inside that call I simply allocated 1 buffer and reused it each time to make the checks where
we skip one of the elements.

4
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();

    var safe_reports: u16 = 0;
    var report = std.ArrayList(u8).init(arena.allocator());

    var lines = std.mem.tokenizeAny(u8, input, &.{ '\r', '\n', '\x00' });
    while (lines.next()) |line| {
        var levels = std.mem.tokenizeScalar(u8, line, ' ');
        while (levels.next()) |level| {
            try report.append(try std.fmt.parseInt(u8, level, 10));
        }

        if (isSafeReport(report.items)) {
            safe_reports += 1;
        }

        report.clearRetainingCapacity();
    }

    std.debug.print("safe reports: {d}\n", .{safe_reports});
}

fn isSafeReport(levels: []const u8) bool {
    const order: std.math.Order = std.math.order(levels[0], levels[1]);

    for (levels[0 .. levels.len - 1], levels[1..]) |left, right| {
        const current_order = std.math.order(left, right);
        if (current_order != order or current_order == .eq) {
            return false;
        }
        const diff = if (order == .gt) left - right else right - left;
        if (diff > 3) return false;
    }

    return true;
}
Part 2 (naive) 
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();

    var safe_reports: u16 = 0;
    var report = std.ArrayList(u8).init(arena.allocator());

    var lines = std.mem.tokenizeAny(u8, input, &.{ '\r', '\n', '\x00' });
    while (lines.next()) |line| {
        var levels = std.mem.tokenizeScalar(u8, line, ' ');
        while (levels.next()) |level| {
            try report.append(try std.fmt.parseInt(u8, level, 10));
        }

        if (try isSafeReportSafetyDampened(report.items, arena.allocator())) {
            safe_reports += 1;
        }

        report.clearRetainingCapacity();
    }

    std.debug.print("safe reports: {d}\n", .{safe_reports});
}

fn isSafeReportSafetyDampened(levels: []const u8, gpa: std.mem.Allocator) !bool {
    for (0..levels.len) |skip_idx| {
        const new_levels = try gpa.alloc(u8, levels.len - 1);
        defer gpa.free(new_levels);

        @memcpy(new_levels[0..skip_idx], levels[0..skip_idx]);
        @memcpy(new_levels[skip_idx..], levels[skip_idx + 1 ..]);

        if (isSafeReport(new_levels)) {
            return true;
        }
    }

    return false;
}

fn isSafeReport(levels: []const u8) bool {
    const order: std.math.Order = std.math.order(levels[0], levels[1]);

    for (levels[0 .. levels.len - 1], levels[1..]) |left, right| {
        const current_order = std.math.order(left, right);
        if (current_order != order or current_order == .eq) {
            return false;
        }
        const diff = if (order == .gt) left - right else right - left;
        if (diff > 3) return false;
    }

    return true;
}

Reworking part two to not allocate a whole list for each item would be a good start…

2 Likes
5

This one made me use quite a lot of ArrayList, memory consumption must be ugly.

I guess this is the kind of situation where a sentinel terminated array of sufficient length would prove quite useful!

1 Like
6

I used BoundedArrays since my input seemed to have around 8 levels max. So only one allocation for reading input. Cleaned up a lot from last night.

https://zigbin.io/d8abdf

2 Likes
8

I tried to do it in one pass. But then needed to check again for the case where we can remove the first or second level… Not super clean but it worked.

Summary 

const std = @import("std");
const mem = std.mem;
const fmt = std.fmt;
const Allocator = std.mem.Allocator;
const List = std.ArrayList;
const print = std.debug.print;

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

const CheckResult = struct {
    has_removed_level: bool,
    result: bool,
};

fn checkReport(levels: []const i32) CheckResult {
    var maybe_increasing: ?bool = null;
    var maybe_prev_level: ?i32 = null;
    var safe = true;
    var have_removed_level = false;

    for (levels) |level| {
        var this_level_safe = true;

        if (maybe_prev_level) |prev_level| {
            const diff: i32 = level - prev_level;

            if (maybe_increasing) |increasing| {
                if (diff > 0 and !increasing) {
                    this_level_safe = false;
                } else if (diff < 0 and increasing) {
                    this_level_safe = false;
                }
            } else {
                if (diff > 0) {
                    maybe_increasing = true;
                } else {
                    maybe_increasing = false;
                }
            }

            if (@abs(diff) < 1 or @abs(diff) > 3) {
                this_level_safe = false;
            }
        }
        if (!have_removed_level and !this_level_safe) {
            have_removed_level = true;
            // if we remove this level, we don't update the prev level, we keep it where it is. We will need to deal with
            // the case where the first or second one could be removed at the end
        } else {
            if (!this_level_safe) {
                safe = false;
                break;
            }
            maybe_prev_level = level;
        }
    }
    print("{s}\n", .{if (safe) "safe" else "unsafe"});
    if (have_removed_level) {
        print("have removed level\n", .{});
    }
    return CheckResult{
        .has_removed_level = have_removed_level,
        .result = safe,
    };
}

pub fn main() !void {
    var gpa_impl = std.heap.GeneralPurposeAllocator(.{}){};
    const gpa = gpa_impl.allocator();

    var safe_count: usize = 0;
    var line_tok = mem.tokenizeAny(u8, data, "\r\n");
    while (line_tok.next()) |line| {
        print("line: {s} ", .{line});

        var levels = List(i32).init(gpa);
        defer levels.deinit();

        var levels_tok = mem.tokenizeScalar(u8, line, ' ');

        while (levels_tok.next()) |level_str| {
            const level: i32 = try fmt.parseInt(i32, level_str, 10);
            try levels.append(level);
        }
        const check_result = checkReport(levels.items);

        var safe = check_result.result;

        var initial_levels = List(i32).init(gpa);
        initial_levels.deinit();
        try initial_levels.insertSlice(0, levels.items);

        if (!safe) {
            // maybe it will be safe if we remove the first level. First weird case.
            _ = levels.orderedRemove(0);

            const new_check_result = checkReport(levels.items);

            if (new_check_result.result and !new_check_result.has_removed_level) {
                safe = true;
            }
        }

        if (!safe) {
            levels.clearRetainingCapacity();
            try levels.insertSlice(0, initial_levels.items);

            // maybe it will be safe if we remove the second level. Those were the two weird cases
            _ = levels.orderedRemove(1);

            const new_check_result = checkReport(levels.items);

            if (new_check_result.result and !new_check_result.has_removed_level) {
                safe = true;
            }
        }

        if (safe) {
            print("-> safe!\n", .{});
            safe_count += 1;
        } else {
            print("-> unsafe!\n", .{});
        }
    }
    print("answer part 2: {}\n", .{safe_count});
}
2 Likes
9

I managed to get a single pass solution to part 2! The MaskedIterator I defined lets me skip an index without having to mess with the underlying ArrayLists’s memory… I guess I meant something like ‘single allocation-pass’ - obviously I have to process that memory many times, but all the allocation happens once and is linear in the size of the input file.

1 Like
10

I am behind, but here is my solution :slight_smile: The Zig Pastebin