aoc2024: day 13 part 2 attemped optimization, but idk how to

1 files changed, 43 insertions, 21 deletions

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;
     }