AoC 2024: Day 7

Challenge
1

Main thread for Day 7 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 7 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
Day 5: AoC 2024: Day 5
Day 6: AoC 2024: Day 6

2

That one was really easy to solve with recursion.

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

var alloc: std.mem.Allocator = undefined;

const test_data =
    \\190: 10 19
    \\3267: 81 40 27
    \\83: 17 5
    \\156: 15 6
    \\7290: 6 8 6 15
    \\161011: 16 10 13
    \\192: 17 8 14
    \\21037: 9 7 18 13
    \\292: 11 6 16 20
;

const Equation = struct {
    result: usize,
    terms: []usize,
};

var equations: []Equation = undefined;

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

fn solveRec(target: usize, temp: usize, terms: []usize) bool {
    return switch (terms.len) {
        0 => target == temp,
        else => solveRec(target, temp + terms[0], terms[1..]) or
            solveRec(target, temp * terms[0], terms[1..]),
    };
}

fn concat(a: usize, b: usize) usize {
    const len_b: usize = std.math.log10_int(b) + 1;
    const exp = std.math.powi(usize, 10, len_b) catch unreachable;
    return a * exp + b;
}

fn solveRec2(target: usize, temp: usize, terms: []usize) bool {
    return switch (terms.len) {
        0 => target == temp,
        else => solveRec2(target, temp + terms[0], terms[1..]) or
            solveRec2(target, temp * terms[0], terms[1..]) or
            solveRec2(target, concat(temp, terms[0]), terms[1..]),
    };
}

fn parse(d: []const u8) !void {
    var eqList = u.List(Equation).init(alloc);
    var lines = std.mem.tokenizeScalar(u8, d, '\n');
    while (lines.next()) |line| {
        var parts = std.mem.tokenizeScalar(u8, line, ':');
        const left = parts.next() orelse unreachable;
        const right = parts.next() orelse unreachable;
        var terms = std.mem.tokenizeScalar(u8, right, ' ');
        var list = u.List(usize).init(alloc);
        while (terms.next()) |term| {
            try list.append(try u.parseInt(usize, term, 0));
        }
        try eqList.append(Equation{
            .result = try u.parseInt(usize, left, 0),
            .terms = list.items,
        });
    }
    equations = eqList.items;
}

fn part1() !void {
    var total: usize = 0;
    for (equations) |eq| {
        if (solveRec(eq.result, 0, eq.terms)) {
            total += eq.result;
        }
    }
    u.print("{any}\n", .{total});
}

fn part2() !void {
    var total: usize = 0;
    for (equations) |eq| {
        if (solveRec2(eq.result, 0, eq.terms)) {
            total += eq.result;
        }
    }
    u.print("{any}\n", .{total});
}

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

    try parse(data);
    try part1();
    try part2();
}

// Generated from template/template.zig.
// Run `zig build generate` to update.
// Only unmodified days will be updated.
3

In hindsight, I probably should have just gone with recursion, but oh well.

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

pub fn part1(input: []const u8) !usize {
    var acc: usize = 0;
    var numbers: [20]usize = undefined;
    var it = std.mem.tokenizeScalar(u8, input, '\n');
    outer: while (it.next()) |line| {
        var parts = std.mem.tokenizeScalar(u8, line, ' ');
        const rstr = parts.next().?;
        const result = try std.fmt.parseInt(usize, rstr[0 .. rstr.len - 1], 10);
        var max: u6 = 0;
        while (parts.next()) |n| : (max += 1) {
            if (max > 19) return error.TooManyNumbers;
            numbers[max] = try std.fmt.parseInt(usize, n, 10);
        }
        // number of permutations is 2 ^ (numbers.len - 1)
        // have a for loop from 0 to number of permutations and use the bits of
        // the number to get the operator
        // 0 -> +
        // 1 -> *
        const perms: u64 = @as(u64, 2) << (max - 1);
        mutations: for (0..perms) |i| {
            var intermediate: usize = numbers[0];
            var ii: u6 = 1;
            while (ii < max) : (ii += 1) {
                if (intermediate > result) continue :mutations;
                const bit = i >> (ii - 1) & 0b1;
                intermediate = switch (bit) {
                    0 => intermediate + numbers[ii],
                    1 => intermediate * numbers[ii],
                    else => unreachable,
                };
            }
            if (result == intermediate) {
                acc += result;
                continue :outer;
            }
        }
    }
    return acc;
}

fn concat(a: usize, b: usize) usize {
    var tmp = b;
    var d: usize = 1;
    while (tmp > 0) {
        tmp /= 10;
        d *= 10;
    }
    return a * d + b;
}

pub fn part2(input: []const u8) !usize {
    var acc: usize = 0;
    var numbers: [20]usize = undefined;
    var it = std.mem.tokenizeScalar(u8, input, '\n');
    outer: while (it.next()) |line| {
        var parts = std.mem.tokenizeScalar(u8, line, ' ');
        const rstr = parts.next().?;
        const result = try std.fmt.parseInt(usize, rstr[0 .. rstr.len - 1], 10);
        var max: u6 = 0;
        while (parts.next()) |n| : (max += 1) {
            if (max > 19) return error.TooManyNumbers;
            numbers[max] = try std.fmt.parseInt(usize, n, 10);
        }
        // number of permutations is 3 ^ (numbers.len - 1)
        // 0 -> +
        // 1 -> *
        // 2 -> ||
        const perms: u64 = std.math.pow(u64, 3, max - 1);
        mutations: for (0..perms) |i| {
            var intermediate: usize = numbers[0];
            var ii: u6 = 1;
            while (ii < max) : (ii += 1) {
                if (intermediate > result) continue :mutations;
                const op = i / std.math.pow(u64, 3, ii - 1) % 3;
                intermediate = switch (op) {
                    0 => intermediate + numbers[ii],
                    1 => intermediate * numbers[ii],
                    2 => concat(intermediate, numbers[ii]),
                    else => unreachable,
                };
            }
            if (result == intermediate) {
                acc += result;
                continue :outer;
            }
        }
    }
    return acc;
}
4

Pretty easy day overall, but i was stuck on a edge case on p1 for some time.

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

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

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

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

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

    while (lines.next()) |line| {
        defer numbers.clearRetainingCapacity();
        var numbers_it = std.mem.tokenizeAny(u8, line, ": ");
        const value = try std.fmt.parseInt(u64, numbers_it.next().?, 10);

        while (numbers_it.next()) |num_str| {
            const number = try std.fmt.parseInt(u64, num_str, 10);
            try numbers.append(number);
        }

        if (solve(value, numbers.items[0], numbers.items[1..])) p1 += value;

        if (solve2(value, numbers.items[0], numbers.items[1..])) p2 += value;
    }

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

fn solve(value: u64, current: u64, terms: []u64) bool {
    if (terms.len == 0) return value == current;

    return (solve(value, current + terms[0], terms[1..]) or solve(value, current * terms[0], terms[1..]));
}

fn concat(a: u64, b: u64) u64 {
    const digits_b: usize = std.math.log10_int(b) + 1;
    const e = std.math.powi(u64, 10, digits_b) catch unreachable;

    return a * e + b;
}

fn solve2(value: u64, current: u64, terms: []u64) bool {
    if (terms.len == 0) return value == current;

    return (solve2(value, current + terms[0], terms[1..]) or
        solve2(value, current * terms[0], terms[1..])) or
        solve2(value, concat(current, terms[0]), terms[1..]);
}
5

Very straightforward with recursion. Part 2 saw some noticeable slowdown, but I haven’t tried to optimize anything.

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 inputs = std.ArrayList(u64).init(arena.allocator());

    var result: u64 = 0;

    var line_iter = std.mem.tokenizeScalar(u8, input, '\n');
    while (line_iter.next()) |line| {
        inputs.clearRetainingCapacity();

        const colon = std.mem.indexOfScalar(u8, line, ':').?;
        const target = try std.fmt.parseInt(u64, line[0..colon], 10);

        var input_iter = std.mem.tokenizeScalar(u8, line[colon + 1 ..], ' ');
        while (input_iter.next()) |n| {
            try inputs.append(try std.fmt.parseInt(u64, n, 10));
        }

        if (canMakeTarget(target, inputs.items[0], inputs.items[1..])) {
            result += target;
        }
    }

    std.log.info("{d}", .{result});
}

fn canMakeTarget(target: u64, acc: u64, inputs: []const u64) bool {
    if (inputs.len == 0) {
        return acc == target;
    }

    return canMakeTarget(target, acc + inputs[0], inputs[1..]) or
        canMakeTarget(target, acc * inputs[0], inputs[1..]);
}
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();

    var inputs = std.ArrayList(u64).init(arena.allocator());

    var result: u64 = 0;

    var line_iter = std.mem.tokenizeScalar(u8, input, '\n');
    while (line_iter.next()) |line| {
        inputs.clearRetainingCapacity();

        const colon = std.mem.indexOfScalar(u8, line, ':').?;
        const target = try std.fmt.parseInt(u64, line[0..colon], 10);

        var input_iter = std.mem.tokenizeScalar(u8, line[colon + 1 ..], ' ');
        while (input_iter.next()) |n| {
            try inputs.append(try std.fmt.parseInt(u64, n, 10));
        }

        if (canMakeTarget(target, inputs.items[0], inputs.items[1..], arena.allocator())) {
            result += target;
        }
    }

    std.log.info("{d}", .{result});
}

fn canMakeTarget(target: u64, acc: u64, inputs: []const u64, allocator: std.mem.Allocator) bool {
    if (inputs.len == 0) {
        return acc == target;
    }

    if (canMakeTarget(target, acc + inputs[0], inputs[1..], allocator) or
        canMakeTarget(target, acc * inputs[0], inputs[1..], allocator))
    {
        return true;
    }

    const concat = std.fmt.allocPrint(allocator, "{d}{d}", .{ acc, inputs[0] }) catch unreachable;
    const concat_num = std.fmt.parseInt(u64, concat, 10) catch unreachable;

    return canMakeTarget(target, concat_num, inputs[1..], allocator);
}
6
Parts 1 & 2 
const std = @import("std");

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

pub fn main() !void {
    var lines = std.mem.tokenizeScalar(u8, data, '\n');
    var total: u64 = 0;
    var total2: u64 = 0;

    while (lines.next()) |line| {
        var numsIter = std.mem.tokenizeAny(u8, line, ": ");
        const target = try std.fmt.parseInt(u64, numsIter.next().?, 10);

        var nums = try std.BoundedArray(u64, 20).init(0);
        while (numsIter.next()) |num_str| {
            const num = try std.fmt.parseInt(u64, num_str, 10);
            try nums.append(num);
        }

        if (doCheckSum(&nums.buffer, nums.len, 0, nums.buffer[0], target)) {
            // std.debug.print("{s}\n", .{line});
            total += target;
        }

        if (doCheckSum2(&nums.buffer, nums.len, 0, nums.buffer[0], target)) {
            //std.debug.print("{s}\n", .{line});
            total2 += target;
        }
    }
    std.debug.print("Total: {d}\n", .{total});
    std.debug.print("Total2: {d}\n", .{total2});
}

pub fn doCheckSum(nums: []u64, len: usize, i: usize, acc: u64, target: u64) bool {
    if (acc > target) return false;
    if ((i == len - 1) and acc == target) return true;
    if ((i == len - 1) and acc != target) return false;
    return doCheckSum(nums, len, i + 1, acc + nums[i + 1], target) or
        doCheckSum(nums, len, i + 1, acc * nums[i + 1], target);
}

pub fn doCheckSum2(nums: []u64, len: usize, i: usize, acc: u64, target: u64) bool {
    if (acc > target) return false;
    if ((i == len - 1) and acc == target) return true;
    if ((i == len - 1) and acc != target) return false;
    return doCheckSum2(nums, len, i + 1, acc + nums[i + 1], target) or
        doCheckSum2(nums, len, i + 1, acc * nums[i + 1], target) or
        doCheckSum2(nums, len, i + 1, concat(acc, nums[i + 1]), target);
}

// from maxsch solution
pub fn concat(a: u64, b: u64) u64 {
    const digits_b: usize = std.math.log10_int(b) + 1;
    const e = std.math.powi(u64, 10, digits_b) catch unreachable;
    return a * e + b;
}
7

cleaned up day 7 non-recursive solution. runs in 344ms release fast on my machine https://zigbin.io/f84238

this recursive solution is like 6x faster - around 57ms https://zigbin.io/c9fd9d

8

I made some experiments to see if going backwards helped. My thinking was that aborting when the multiplication if the modulo was not zero could save some time. Turns out it did nothing. I tried a bunch of other early out ideas, and got it down to around 15ms on my i9 laptop cpu.

https://zigbin.io/134b2c