Code (runtime ~ 20min)
const std = @import("std");
const Present = struct {
pos: struct { x: usize, y: usize },
nblocks: usize,
shape: [3][3]bool,
const Self = @This();
pub fn init(block: []const u8) !Self {
var present = Self{
.pos = .{ .x = 0, .y = 0 },
.nblocks = 0,
.shape = undefined,
};
var lines = std.mem.tokenizeScalar(u8, block, '\n');
_ = lines.next().?;
for (0..3) |irow| {
const line = lines.next().?;
for (0..3) |icol| {
present.shape[irow][icol] = line[icol] == '#';
if (line[icol] == '#') {
present.nblocks += 1;
}
}
}
return present;
}
pub fn flipV(self: *Self) void {
for (0..3) |icol| {
const tmp = self.shape[0][icol];
self.shape[0][icol] = self.shape[2][icol];
self.shape[2][icol] = tmp;
}
}
pub fn flipH(self: *Self) void {
for (0..3) |irow| {
const tmp = self.shape[irow][0];
self.shape[irow][0] = self.shape[irow][2];
self.shape[irow][2] = tmp;
}
}
pub fn rotateL(self: *Self) void {
const tmp = self.*;
self.shape[0][0] = tmp.shape[0][2];
self.shape[0][1] = tmp.shape[1][2];
self.shape[0][2] = tmp.shape[2][2];
self.shape[1][0] = tmp.shape[0][1];
self.shape[1][2] = tmp.shape[2][1];
self.shape[2][0] = tmp.shape[0][0];
self.shape[2][1] = tmp.shape[1][0];
self.shape[2][2] = tmp.shape[2][0];
}
pub fn rotateR(self: *Self) void {
const tmp = self.*;
self.shape[0][0] = tmp.shape[2][0];
self.shape[0][1] = tmp.shape[1][0];
self.shape[0][2] = tmp.shape[0][0];
self.shape[1][0] = tmp.shape[2][1];
self.shape[1][2] = tmp.shape[0][1];
self.shape[2][0] = tmp.shape[2][2];
self.shape[2][1] = tmp.shape[1][2];
self.shape[2][2] = tmp.shape[0][2];
}
pub fn move(self: *Self, dx: i64, dy: i64, xmax: usize, ymax: usize) void {
if (dx < 0) {
if (self.pos.x > @abs(dx)) {
self.pos.x -= @abs(dx);
} else {
self.pos.x = 0;
}
} else {
if (self.pos.x + 2 + @abs(dx) < xmax) {
self.pos.x += @abs(dx);
} else {
self.pos.x = xmax - 3;
}
}
if (dy < 0) {
if (self.pos.y > @abs(dy)) {
self.pos.y -= @abs(dy);
} else {
self.pos.y = 0;
}
} else {
if (self.pos.y + 2 + @abs(dy) < ymax) {
self.pos.y += @abs(dy);
} else {
self.pos.y = ymax - 3;
}
}
}
pub fn overlapp(self: Self, other: Self) i64 {
var n: i64 = 0;
if (self.pos.x <= other.pos.x) {
//std.debug.print("s.x <= o.x\n", .{});
const dx = other.pos.x - self.pos.x;
if (dx >= 3) {
return 0;
}
if (self.pos.y <= other.pos.y) {
//std.debug.print("s.y <= o.y\n", .{});
const dy = other.pos.y - self.pos.y;
if (dy >= 3) {
return 0;
}
for (0 + dy..3, 0..3 - dy) |irow, jrow| {
for (0 + dx..3, 0..3 - dx) |icol, jcol| {
if (self.shape[irow][icol] and other.shape[jrow][jcol]) {
n += 1;
}
}
}
} else {
//std.debug.print("s.y > o.y\n", .{});
const dy = self.pos.y - other.pos.y;
if (dy >= 3) {
return 0;
}
for (0..3 - dy, 0 + dy..3) |irow, jrow| {
for (0 + dx..3, 0..3 - dx) |icol, jcol| {
if (self.shape[irow][icol] and other.shape[jrow][jcol]) {
n += 1;
}
}
}
}
} else {
const dx = self.pos.x - other.pos.x;
//std.debug.print("s.x > o.x\n", .{});
if (dx >= 3) {
return 0;
}
if (self.pos.y <= other.pos.y) {
//std.debug.print("s.y <= o.y\n", .{});
const dy = other.pos.y - self.pos.y;
if (dy >= 3) {
return 0;
}
for (0 + dy..3, 0..3 - dy) |irow, jrow| {
for (0..3 - dx, 0 + dx..3) |icol, jcol| {
if (self.shape[irow][icol] and other.shape[jrow][jcol]) {
n += 1;
}
}
}
} else {
const dy = self.pos.y - other.pos.y;
//std.debug.print("s.y > o.y\n", .{});
if (dy >= 3) {
return 0;
}
for (0..3 - dy, 0 + dy..3) |irow, jrow| {
for (0..3 - dx, 0 + dx..3) |icol, jcol| {
if (self.shape[irow][icol] and other.shape[jrow][jcol]) {
n += 1;
}
}
}
}
}
return n;
}
pub fn printDebug(self: Self) void {
for (0..3) |irow| {
for (0..3) |icol| {
const char: u8 = if (self.shape[irow][icol]) '#' else '.';
std.debug.print("{c}", .{char});
}
std.debug.print("\n", .{});
}
}
test "overlapp some" {
const p1str =
\\0:
\\##.
\\.#.
\\.##
;
var p1 = try Present.init(p1str);
const p2str =
\\0:
\\###
\\..#
\\###
;
var p2 = try Present.init(p2str);
try std.testing.expectEqual(5, p1.overlapp(p1));
try std.testing.expectEqual(7, p2.overlapp(p2));
p1.pos = .{ .x = 0, .y = 0 };
p2.pos = .{ .x = 0, .y = 0 };
try std.testing.expectEqual(4, p1.overlapp(p2));
try std.testing.expectEqual(4, p2.overlapp(p1));
p1.pos = .{ .x = 1, .y = 0 };
p2.pos = .{ .x = 0, .y = 0 };
try std.testing.expectEqual(4, p1.overlapp(p2));
try std.testing.expectEqual(4, p2.overlapp(p1));
p1.pos = .{ .x = 2, .y = 0 };
p2.pos = .{ .x = 0, .y = 0 };
try std.testing.expectEqual(1, p1.overlapp(p2));
try std.testing.expectEqual(1, p2.overlapp(p1));
p1.pos = .{ .x = 0, .y = 0 };
p2.pos = .{ .x = 1, .y = 0 };
try std.testing.expectEqual(3, p1.overlapp(p2));
try std.testing.expectEqual(3, p2.overlapp(p1));
p1.pos = .{ .x = 0, .y = 0 };
p2.pos = .{ .x = 2, .y = 0 };
try std.testing.expectEqual(1, p1.overlapp(p2));
try std.testing.expectEqual(1, p2.overlapp(p1));
p1.pos = .{ .x = 0, .y = 1 };
p2.pos = .{ .x = 0, .y = 0 };
try std.testing.expectEqual(1, p1.overlapp(p2));
try std.testing.expectEqual(1, p2.overlapp(p1));
p1.pos = .{ .x = 0, .y = 2 };
p2.pos = .{ .x = 0, .y = 0 };
try std.testing.expectEqual(2, p1.overlapp(p2));
try std.testing.expectEqual(2, p2.overlapp(p1));
p1.pos = .{ .x = 1, .y = 1 };
p2.pos = .{ .x = 0, .y = 0 };
try std.testing.expectEqual(2, p1.overlapp(p2));
try std.testing.expectEqual(2, p2.overlapp(p1));
p1.pos = .{ .x = 0, .y = 2 };
p2.pos = .{ .x = 1, .y = 1 };
try std.testing.expectEqual(1, p1.overlapp(p2));
try std.testing.expectEqual(1, p2.overlapp(p1));
p1.pos = .{ .x = 2, .y = 2 };
p2.pos = .{ .x = 0, .y = 0 };
try std.testing.expectEqual(1, p1.overlapp(p2));
try std.testing.expectEqual(1, p2.overlapp(p1));
p1.pos = .{ .x = 0, .y = 0 };
p2.pos = .{ .x = 2, .y = 2 };
try std.testing.expectEqual(1, p1.overlapp(p2));
try std.testing.expectEqual(1, p2.overlapp(p1));
p1.pos = .{ .x = 1, .y = 0 };
p2.pos = .{ .x = 0, .y = 1 };
try std.testing.expectEqual(2, p1.overlapp(p2));
try std.testing.expectEqual(2, p2.overlapp(p1));
p1.pos = .{ .x = 2, .y = 0 };
p2.pos = .{ .x = 0, .y = 2 };
try std.testing.expectEqual(0, p1.overlapp(p2));
try std.testing.expectEqual(0, p2.overlapp(p1));
p1.pos = .{ .x = 0, .y = 1 };
p2.pos = .{ .x = 1, .y = 0 };
try std.testing.expectEqual(1, p1.overlapp(p2));
try std.testing.expectEqual(1, p2.overlapp(p1));
p1.pos = .{ .x = 0, .y = 2 };
p2.pos = .{ .x = 2, .y = 0 };
try std.testing.expectEqual(0, p1.overlapp(p2));
try std.testing.expectEqual(0, p2.overlapp(p1));
}
test "overlapp none" {
const p1str =
\\0:
\\##.
\\.#.
\\.##
;
var p1 = try Present.init(p1str);
const p2str =
\\0:
\\###
\\..#
\\###
;
var p2 = try Present.init(p2str);
p1.pos = .{ .x = 3, .y = 0 };
p2.pos = .{ .x = 0, .y = 0 };
try std.testing.expectEqual(0, p1.overlapp(p2));
try std.testing.expectEqual(0, p2.overlapp(p1));
p1.pos = .{ .x = 0, .y = 3 };
p2.pos = .{ .x = 0, .y = 0 };
try std.testing.expectEqual(0, p1.overlapp(p2));
try std.testing.expectEqual(0, p2.overlapp(p1));
p1.pos = .{ .x = 0, .y = 0 };
p2.pos = .{ .x = 3, .y = 0 };
try std.testing.expectEqual(0, p1.overlapp(p2));
try std.testing.expectEqual(0, p2.overlapp(p1));
p1.pos = .{ .x = 0, .y = 0 };
p2.pos = .{ .x = 0, .y = 3 };
try std.testing.expectEqual(0, p1.overlapp(p2));
try std.testing.expectEqual(0, p2.overlapp(p1));
p1.pos = .{ .x = 3, .y = 3 };
p2.pos = .{ .x = 0, .y = 0 };
try std.testing.expectEqual(0, p1.overlapp(p2));
try std.testing.expectEqual(0, p2.overlapp(p1));
p1.pos = .{ .x = 3, .y = 3 };
p2.pos = .{ .x = 0, .y = 0 };
try std.testing.expectEqual(0, p1.overlapp(p2));
try std.testing.expectEqual(0, p2.overlapp(p1));
p1.pos = .{ .x = 3, .y = 0 };
p2.pos = .{ .x = 0, .y = 3 };
try std.testing.expectEqual(0, p1.overlapp(p2));
try std.testing.expectEqual(0, p2.overlapp(p1));
p1.pos = .{ .x = 3, .y = 3 };
p2.pos = .{ .x = 3, .y = 0 };
try std.testing.expectEqual(0, p1.overlapp(p2));
try std.testing.expectEqual(0, p2.overlapp(p1));
p1.pos = .{ .x = 3, .y = 3 };
p2.pos = .{ .x = 0, .y = 3 };
try std.testing.expectEqual(0, p1.overlapp(p2));
try std.testing.expectEqual(0, p2.overlapp(p1));
p1.pos = .{ .x = 3, .y = 0 };
p2.pos = .{ .x = 3, .y = 3 };
try std.testing.expectEqual(0, p1.overlapp(p2));
try std.testing.expectEqual(0, p2.overlapp(p1));
p1.pos = .{ .x = 0, .y = 3 };
p2.pos = .{ .x = 3, .y = 3 };
try std.testing.expectEqual(0, p1.overlapp(p2));
try std.testing.expectEqual(0, p2.overlapp(p1));
}
};
const Grid = struct {
nrows: usize,
ncols: usize,
presents: std.ArrayList(Present),
overlapp: i64,
beta: f64, // 1/(kB*T)
prng: std.Random.DefaultPrng,
allocator: std.mem.Allocator,
ntotal: usize,
naccept: usize,
solved: bool,
const Self = @This();
pub fn init(allocator: std.mem.Allocator, prng: std.Random.DefaultPrng) Self {
return Self{
.nrows = 0,
.ncols = 0,
.presents = std.ArrayList(Present).empty,
.overlapp = 0,
.prng = prng,
.beta = 0,
.allocator = allocator,
.ntotal = 0,
.naccept = 0,
.solved = false,
};
}
pub fn deinit(self: *Self) void {
self.presents.deinit(self.allocator);
}
pub fn resetState(self: *Self, line: []const u8, presents: std.ArrayList(Present)) !void {
self.presents.clearRetainingCapacity();
var blocks = std.mem.tokenizeSequence(u8, line, ": ");
const dims_str = blocks.next().?;
var dims = std.mem.tokenizeScalar(u8, dims_str, 'x');
self.ncols = try std.fmt.parseInt(usize, dims.next().?, 10);
self.nrows = try std.fmt.parseInt(usize, dims.next().?, 10);
const pcountlist_str = blocks.next().?;
var pcount_strs = std.mem.tokenizeScalar(u8, pcountlist_str, ' ');
var ip: usize = 0;
while (pcount_strs.next()) |pcount_str| : (ip += 1) {
const pcount = try std.fmt.parseInt(usize, pcount_str, 10);
try self.presents.appendNTimes(self.allocator, presents.items[ip], pcount);
}
const rng = self.prng.random();
for (self.presents.items) |*p| {
const x = rng.intRangeLessThan(usize, 0, self.ncols - 2);
const y = rng.intRangeLessThan(usize, 0, self.nrows - 2);
p.pos.x = x;
p.pos.y = y;
}
self.overlapp = self.totalOverlapp();
self.ntotal = 0;
self.naccept = 0;
self.solved = false;
}
pub fn totalOverlapp(self: Self) i64 {
var overlapp: i64 = 0;
for (self.presents.items[0 .. self.presents.items.len - 1], 0..) |p1, i| {
for (self.presents.items[i + 1 .. self.presents.items.len]) |p2| {
overlapp += p1.overlapp(p2);
}
}
return overlapp;
}
pub fn diffOverlapp(self: Self, pidx: usize, newP: Present) i64 {
var doverlapp: i64 = 0;
const present = self.presents.items[pidx];
for (0..pidx) |oidx| {
doverlapp -= present.overlapp(self.presents.items[oidx]);
doverlapp += newP.overlapp(self.presents.items[oidx]);
}
for (pidx + 1..self.presents.items.len) |oidx| {
doverlapp -= present.overlapp(self.presents.items[oidx]);
doverlapp += newP.overlapp(self.presents.items[oidx]);
}
return doverlapp;
}
pub fn mutate(self: *Self, pidx: usize) Present {
const rng = self.prng.random();
const opidx = std.Random.intRangeAtMost(
rng,
usize,
0,
200,
);
var present = self.presents.items[pidx];
switch (opidx) {
0...9 => {
present.flipH();
},
10...19 => {
present.flipV();
},
20...39 => {
present.rotateL();
},
40...59 => {
present.rotateR();
},
60...200 => {
const dx = std.Random.intRangeAtMost(
rng,
i64,
-3,
3,
);
const dy = std.Random.intRangeAtMost(
rng,
i64,
-3,
3,
);
present.move(dx, dy, self.ncols, self.nrows);
},
else => {
unreachable;
},
}
return present;
}
pub fn step(self: *Self) void {
self.ntotal += 1;
const rng = self.prng.random();
// 1. select present
const pidx = std.Random.intRangeLessThan(
rng,
usize,
0,
self.presents.items.len,
);
// 2. mutate present
const new_present = self.mutate(pidx);
// 3. compute change in overlapp
const d_overlapp = self.diffOverlapp(pidx, new_present);
// 4. accept directly
if (d_overlapp <= 0) {
self.presents.items[pidx] = new_present;
self.overlapp += d_overlapp;
self.naccept += 1;
} else {
// 5. compute acceptance
// random number [0:1)
const rn = std.Random.float(rng, f64);
const expo = -@as(f64, @floatFromInt(d_overlapp)) * self.beta;
if (expo > -100.0) {
if (std.math.exp(expo) >= rn) {
// 6. acceptance
self.presents.items[pidx] = new_present;
self.overlapp += d_overlapp;
self.naccept += 1;
}
}
// 7. Rejection
// nothing to do
}
}
pub fn run(self: *Self, nsteps_per_temp: usize, beta_start: f64, beta_end: f64, beta_scale: f64) void {
if (beta_scale <= 1.0) {
std.debug.print("beta_scale musst be larger than 1.0\n", .{});
return;
}
if (beta_start <= 0.0) {
std.debug.print("beta_start musst be larger than 0.0\n", .{});
return;
}
if (beta_end <= beta_start) {
std.debug.print("beta_end musst be larger than beta_start\n", .{});
return;
}
//std.debug.print(
// "# ntotal naccept temp overlapp\n",
// .{},
//);
self.beta = beta_start;
while (self.beta <= beta_end) : (self.beta *= beta_scale) {
for (0..nsteps_per_temp) |_| {
self.step();
//std.debug.print(
// " {d:>8} {d:>8} {d:>10.2} {d:>10}\n",
// .{
// self.ntotal,
// self.naccept,
// 1.0 / self.beta,
// self.overlapp,
// },
//);
if (self.overlapp == 0) {
self.solved = true;
return;
}
}
}
}
};
pub fn main() !void {
var dba = std.heap.DebugAllocator(.{}){};
defer _ = dba.deinit();
const allocator = dba.allocator();
var stdout_buffer: [1024]u8 = undefined;
var stdout_writer = std.fs.File.stdout().writer(&stdout_buffer);
const stdout = &stdout_writer.interface;
var stderr_buffer: [1024]u8 = undefined;
var stderr_writer = std.fs.File.stderr().writer(&stderr_buffer);
const stderr = &stderr_writer.interface;
const args = try std.process.argsAlloc(allocator);
defer std.process.argsFree(allocator, args);
if (args.len < 2) {
try stderr.print("Usage: {s} <filename>\n", .{args[0]});
try stderr.flush();
return error.InvalidArguments;
}
const filename = args[1];
const file = try std.fs.cwd().openFile(filename, .{});
defer file.close();
const file_size = try file.getEndPos();
const input = try allocator.alloc(u8, file_size);
defer allocator.free(input);
const bytes_read = try file.readAll(input);
if (bytes_read != file_size) {
try stderr.print("Warning: Read {d} bytes but expected {d}\n", .{ bytes_read, file_size });
try stderr.flush();
}
var presents = std.ArrayList(Present).empty;
defer presents.deinit(allocator);
var grid = Grid.init(allocator, std.Random.DefaultPrng.init(123456));
defer grid.deinit();
var npackable: usize = 0;
var blocks = std.mem.tokenizeSequence(u8, input, "\n\n");
while (blocks.next()) |block| {
if (block[1] == ':') {
try presents.append(allocator, try Present.init(block));
} else {
var lines = std.mem.tokenizeScalar(u8, block, '\n');
var npuzzles: usize = 0;
var n_really_packable: usize = 0;
while (lines.next()) |line| {
npuzzles += 1;
try grid.resetState(line, presents);
grid.run(1000, 1.0, 50.0, 1.005);
if (grid.solved) {
npackable += 1;
}
const gridsize = grid.nrows * grid.ncols;
var nblocks: usize = 0;
for (grid.presents.items) |p| {
nblocks += p.nblocks;
}
if (nblocks <= gridsize) {
n_really_packable += 1;
}
std.debug.print("Puzzle {d:>4}: Solved: {d:>3}({d:>3}), Unsolved: {d:>3}\n", .{ npuzzles, npackable, n_really_packable, npuzzles - npackable });
}
}
}
try stdout.print("Number of packable regions: {d}\n", .{npackable});
try stdout.flush();
}
test {
std.testing.refAllDecls(@This());
}