From 56b9e21f13ccbee0fe8cadaf1d69104e609d3200 Mon Sep 17 00:00:00 2001 From: Mathias Magnusson Date: Mon, 16 Dec 2024 01:00:57 +0100 Subject: aoc2024: day 13 part 2 attemped optimization, but idk how to --- aoc24/src/day13.zig | 64 +++++++++++++++++++++++++++++++++++------------------ 1 file changed, 43 insertions(+), 21 deletions(-) (limited to 'aoc24/src') diff --git a/aoc24/src/day13.zig b/aoc24/src/day13.zig index 2d3591f..e0d14b2 100644 --- a/aoc24/src/day13.zig +++ b/aoc24/src/day13.zig @@ -93,12 +93,11 @@ test "solveDiophantine" { inline for (.{ .{ .a = 69, .b = 42, .c = 100071, .solutions = 104 }, .{ .a = 2, .b = 4, .c = 7, .solutions = 0 }, - .{ .a = 2, .b = 4, .c = 6, .solutions = 2 }, }) |t| { var it = solveDiophantine(t.a, t.b, t.c); var solutions: usize = 0; while (it.next()) |sol| { - std.debug.print("{} * {} + {} * {} = {}\n", .{ t.a, sol[0], t.b, sol[1], t.c }); + // std.debug.print("{} * {} + {} * {} = {}\n", .{ t.a, sol[0], t.b, sol[1], t.c }); try std.testing.expectEqual(t.c, t.a * sol[0] + t.b * sol[1]); try std.testing.expect(sol[0] >= 0); try std.testing.expect(sol[1] >= 0); @@ -119,7 +118,8 @@ const DiophantineIterator = struct { } }; -fn solveDiophantine(a: u64, b: u64, c: u64) DiophantineIterator { +fn solveDiophantine(a: i64, b: i64, c: i64) DiophantineIterator { + // std.debug.print("solveDiophantine({}, {}, {})\n", .{ a, b, c }); const Vec = @Vector(2, i64); const cast = struct { fn f(x: u64) i64 { @@ -127,10 +127,10 @@ fn solveDiophantine(a: u64, b: u64, c: u64) DiophantineIterator { } }.f; - const d = std.math.gcd(a, b); - if (c % d != 0) return .{ .curr = .{ undefined, -1 }, .diff = undefined }; - const u = @divExact(a, d); - const v = @divExact(b, d); + const d = std.math.gcd(@abs(a), @abs(b)); + if (@rem(c, cast(d)) != 0) return .{ .curr = .{ undefined, -1 }, .diff = undefined }; + const u = @divExact(@abs(a), d); + const v = @divExact(@abs(b), d); var x = u; var y = v; var sub_x: Vec = .{ 1, 0 }; @@ -140,8 +140,8 @@ fn solveDiophantine(a: u64, b: u64, c: u64) DiophantineIterator { std.mem.swap(Vec, &sub_x, &sub_y); } while (y > 1) { - const rem = x % y; - const quot = x / y; + const rem = @rem(x, y); + const quot = @divTrunc(x, y); const sub: Vec = sub_x - @as(Vec, @splat(cast(quot))) * sub_y; // std.debug.print("{} = {} * {} + {}. {} = {} * {} + {} * {}\n", .{ x, y, quot, rem, rem, @divExact(a, d), sub[0], @divExact(b, d), sub[1] }); @@ -153,10 +153,13 @@ fn solveDiophantine(a: u64, b: u64, c: u64) DiophantineIterator { std.debug.assert(y == 1); const one = sub_y; - var solution = one * @as(Vec, @splat(cast(@divExact(c, d)))); + var solution = one * @as(Vec, @splat(cast(@divExact(@abs(c), d)))); const k: i64 = -@divFloor(solution[0], cast(v)); solution += .{ k * cast(v), -k * cast(u) }; - return .{ .curr = solution, .diff = .{ cast(v), -cast(u) } }; + const s = std.math.sign; + const sign_adjust: Vec = .{ s(a) * s(c), s(b) * s(c) }; + // std.debug.print("{} + k{}\n", .{ solution * sign_adjust, Vec{ cast(v), -cast(u) } * sign_adjust }); + return .{ .curr = solution * sign_adjust, .diff = Vec{ cast(v), -cast(u) } * sign_adjust }; } pub fn part2(_: std.mem.Allocator, input: Input) !u64 { @@ -164,16 +167,35 @@ pub fn part2(_: std.mem.Allocator, input: Input) !u64 { for (input) |machine| { std.debug.print("machine = {}\n", .{machine}); var fewest: u64 = std.math.maxInt(u64); - var x_sols = solveDiophantine(machine.a[0], machine.b[0], @as(u64, @intCast(machine.prize[0])) + 10000000000000); - const y_sols = solveDiophantine(machine.a[1], machine.b[1], @as(u64, @intCast(machine.prize[1])) + 10000000000000); - while (x_sols.next()) |sol_x| { - const ks = (sol_x - y_sols.curr) / y_sols.diff; - if (@reduce(.And, @rem(sol_x - y_sols.curr, y_sols.diff) == @Vector(2, i64){ 0, 0 }) and ks[0] == ks[1]) { - const tokens = @reduce(.Add, sol_x * @Vector(2, i64){ 3, 1 }); - fewest = @min(fewest, @as(u64, @intCast(tokens))); - std.debug.print(" possible solution {} for {} tokens\n", .{ sol_x, tokens }); - } - } + const x_sols = solveDiophantine(machine.a[0], machine.b[0], @as(i64, @intCast(machine.prize[0])) + 10000000000000); + const y_sols = solveDiophantine(machine.a[1], machine.b[1], @as(i64, @intCast(machine.prize[1])) + 10000000000000); + + const diff_a = x_sols.diff * y_sols.diff / @Vector(2, i64){ + @intCast(std.math.gcd(@abs(x_sols.diff[0]), @abs(y_sols.diff[0]))), + @intCast(std.math.gcd(@abs(x_sols.diff[1]), @abs(y_sols.diff[1]))), + }; + + // solveDiophantine(x_sols + + std.debug.print("{} & {} => {}\n", .{ x_sols.diff, y_sols.diff, diff_a }); + + // std.debug.print("{}, {}, {}\n", .{ x_sols.diff[0], y_sols.diff[0], y_sols.curr[0] - x_sols.curr[0] }); + // std.debug.print("{}, {}, {}\n", .{ x_sols.diff[1], y_sols.diff[1], y_sols.curr[1] - x_sols.curr[1] }); + // const kja = solveDiophantine(x_sols.diff[0], y_sols.diff[0], y_sols.curr[0] - x_sols.curr[0]); + // const kjb = solveDiophantine(x_sols.diff[1], y_sols.diff[1], y_sols.curr[1] - x_sols.curr[1]); + // std.debug.print("{}\n{}\n", .{ kja, kjb }); + + if (true) break; + + // while (x_sols.next()) |sol_x| { + // const ks = (sol_x - y_sols.curr) / y_sols.diff; + // if (@reduce(.And, @rem(sol_x - y_sols.curr, y_sols.diff) == @Vector(2, i64){ 0, 0 }) and ks[0] == ks[1]) { + // const tokens = @reduce(.Add, sol_x * @Vector(2, i64){ 3, 1 }); + // fewest = @min(fewest, @as(u64, @intCast(tokens))); + // std.debug.print(" possible solution {} for {} tokens\n", .{ sol_x, tokens }); + // } + // } + fewest = 0; if (fewest != std.math.maxInt(@TypeOf(fewest))) total_tokens += fewest; } -- cgit v1.2.3