diff options
Diffstat (limited to 'aoc24')
| -rw-r--r-- | aoc24/src/day13.zig | 63 |
1 files changed, 32 insertions, 31 deletions
diff --git a/aoc24/src/day13.zig b/aoc24/src/day13.zig index e0d14b2..583c7db 100644 --- a/aoc24/src/day13.zig +++ b/aoc24/src/day13.zig @@ -162,42 +162,43 @@ fn solveDiophantine(a: i64, b: i64, c: i64) DiophantineIterator { return .{ .curr = solution * sign_adjust, .diff = Vec{ cast(v), -cast(u) } * sign_adjust }; } -pub fn part2(_: std.mem.Allocator, input: Input) !u64 { - var total_tokens: u64 = 0; +pub fn part2(allocator: std.mem.Allocator, input: Input) !u64 { + var total_tokens = std.atomic.Value(u64).init(0); + var tpool: std.Thread.Pool = undefined; + try tpool.init(.{ .allocator = allocator }); + defer tpool.deinit(); + var wg = std.Thread.WaitGroup{}; for (input) |machine| { - std.debug.print("machine = {}\n", .{machine}); - var fewest: u64 = std.math.maxInt(u64); - 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]))), - }; + tpool.spawnWg(&wg, checkMachine, .{ machine, &total_tokens }); + } + wg.wait(); + return total_tokens.load(.monotonic); +} - // solveDiophantine(x_sols +fn checkMachine(machine: Machine, total_tokens: *std.atomic.Value(u64)) void { + // std.debug.print("machine[{} of {}] = {}\n", .{ i, input.len, machine }); + var fewest: u64 = std.math.maxInt(u64); - std.debug.print("{} & {} => {}\n", .{ x_sols.diff, y_sols.diff, diff_a }); + var comb_sols = solveDiophantine( + machine.a[0] + machine.a[1], + machine.b[0] + machine.b[1], + @as(i64, @intCast(machine.prize[0] + machine.prize[1])) + 20000000000000, + ); - // 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 }); + while (comb_sols.next()) |sol| { + const solves_x = machine.a[0] * sol[0] + machine.b[0] * sol[1] == @as(i64, @intCast(machine.prize[0])) + 10000000000000; + if (!solves_x) continue; + const solves_y = machine.a[1] * sol[0] + machine.b[1] * sol[1] == @as(i64, @intCast(machine.prize[1])) + 10000000000000; + std.debug.assert(solves_y); - if (true) break; + std.debug.print("found solution {}\n", .{sol}); - // 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; + const tokens = @reduce(.Add, sol * @Vector(2, i64){ 3, 1 }); + fewest = @min(fewest, @as(u64, @intCast(tokens))); } - return total_tokens; + + if (fewest != std.math.maxInt(@TypeOf(fewest))) { + _ = total_tokens.fetchAdd(fewest, .monotonic); // total_tokens += fewest; + } + // return total_tokens; } |