commit 92c6da10e190dcb5a176ac67991df6d4ea78e555
parent 2fa13abd916e5592b8583d8f3fa336bc3c036b55
Author: amin <dev@aminmesbah.com>
Date: Thu, 13 Dec 2018 07:17:45 +0000
Add actual solution to 11-2
Using the summed-area table [1], a wonderfully clever algorithm.
[1]: https://en.wikipedia.org/wiki/Summed-area_table
FossilOrigin-Name: d9b8f2c7346fa6c32e09a40231d6353956ef47f069533b843ca4d90d32a6be22
Diffstat:
| M | day_11.zig | | | 109 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++------------------ |
1 file changed, 84 insertions(+), 25 deletions(-)
diff --git a/day_11.zig b/day_11.zig
@@ -6,53 +6,92 @@ const grid_serial_number: u32 = 5791;
const grid_side_len = 300;
pub fn main() void {
- const result = regionOfHighestTotalPower(grid_serial_number);
- debug.warn("11-1: {}\n", result);
-
- // Horrible brute-force algorithm. Uncomment at your own risk.
- //debug.warn("11-2: ");
- //regionOfHighestTotalPowerUltimateSupremeExtremeBruteForceImSoTiredExtravaganza(grid_serial_number);
+ const result1 = regionOfHighestTotalPower(grid_serial_number);
+ debug.assert(V2.eq(V2.init(20, 68), result1));
+ debug.warn("11-1: {}\n", result1);
+
+ const result2 = regionOfHighestTotalPowerOfAnySize(grid_serial_number);
+ debug.assert(V2.eq(V2.init(231, 273), result2.region));
+ debug.assert(16 == result2.square_side_len);
+ debug.warn("11-2: {},{}\n", result2.region, result2.square_side_len);
}
-fn regionOfHighestTotalPowerUltimateSupremeExtremeBruteForceImSoTiredExtravaganza(gsn: u32) void {
+fn regionOfHighestTotalPowerOfAnySize(gsn: u32) RegionInfo {
var grid = []i32{0} ** (grid_side_len * grid_side_len);
for (grid) |*cell, i| {
var coord = point_from_index(i, grid_side_len);
// grid is 1 based, though array is 0 based
- coord.x += 1;
- coord.y += 1;
+ cell.* = getFuelCellPower(coord.x + 1, coord.y + 1, gsn);
+ }
+ // https://en.wikipedia.org/wiki/Summed-area_table
+ var sat = []i32{0} ** grid.len;
+ for (grid) |cell, i| {
+ const c = point_from_index(i, grid_side_len);
- cell.* = getFuelCellPower(coord.x, coord.y, gsn);
+ sat[i] = grid[index_from_point(c.x, c.y, grid_side_len)];
+
+ if (c.x > 0) {
+ sat[i] += sat[index_from_point(c.x - 1, c.y, grid_side_len)];
+ }
+ if (c.y > 0) {
+ sat[i] += sat[index_from_point(c.x, c.y - 1, grid_side_len)];
+ }
+ if (c.x > 0 and c.y > 0) {
+ sat[i] -= sat[index_from_point(c.x - 1, c.y - 1, grid_side_len)];
+ }
}
- var highest_highest_power: i32 = 0;
- var highest_highest_power_region = V2.init(1, 1);
+ var highest_highest_power: i32 = grid[0];
+ var highest_highest_power_region = V2.init(0, 0);
var highest_square_side_len: u32 = 1;
var square_side_len: u32 = 1;
- while (square_side_len <= 300) : (square_side_len += 1) {
- debug.warn("{}\n", square_side_len);
- var highest_power: i32 = 0;
+ while (square_side_len <= grid_side_len) : (square_side_len += 1) {
+ var highest_power: i32 = @minValue(i32);
var highest_power_region = V2.init(1, 1);
for (grid) |cell, i| {
const array_coord = point_from_index(i, grid_side_len);
+
+ // cells start at (1, 1)
const cell_coord = V2.init(array_coord.x + 1, array_coord.y + 1);
- const search_threshold = grid_side_len - square_side_len;
- if (cell_coord.x >= search_threshold or cell_coord.y >= search_threshold) {
+ const search_threshold = (grid_side_len - square_side_len) + 1;
+ if (cell_coord.x > search_threshold or cell_coord.y > search_threshold) {
continue;
}
- var sum: i32 = 0;
- var square_x: u32 = 0;
- while (square_x < square_side_len) : (square_x += 1) {
- var square_y: u32 = 0;
- while (square_y < square_side_len) : (square_y += 1) {
- sum += grid[index_from_point(array_coord.x + square_x, array_coord.y + square_y, grid_side_len)];
- }
+ const ssl = square_side_len - 1;
+
+ // +----------------------+
+ // | | | |
+ // | A| B| |
+ // |------+-----------+ |
+ // | | | |
+ // | | | |
+ // | | | |
+ // | C| D| |
+ // |------+-----------+ |
+ // | |
+ // +----------------------+
+ // sum = D - B - C + A
+
+ // D
+ var sum: i32 = sat[index_from_point(array_coord.x + ssl, array_coord.y + ssl, grid_side_len)];
+
+ if (array_coord.x > 0) {
+ // - C
+ sum -= sat[index_from_point(array_coord.x - 1, array_coord.y + ssl, grid_side_len)];
+ }
+ if (array_coord.y > 0) {
+ // - B
+ sum -= sat[index_from_point(array_coord.x + ssl, array_coord.y - 1, grid_side_len)];
+ }
+ if (array_coord.x > 0 and array_coord.y > 0) {
+ // + A
+ sum += sat[index_from_point(array_coord.x - 1, array_coord.y - 1, grid_side_len)];
}
if (sum > highest_power) {
@@ -68,7 +107,25 @@ fn regionOfHighestTotalPowerUltimateSupremeExtremeBruteForceImSoTiredExtravaganz
}
}
- debug.warn("{},{}\n", highest_highest_power_region, highest_square_side_len);
+ return RegionInfo {
+ .region = highest_highest_power_region,
+ .square_side_len = highest_square_side_len,
+ };
+}
+
+const RegionInfo = struct {
+ region: V2,
+ square_side_len: u32,
+};
+
+test "region of highest total power of any size" {
+ const r18 = regionOfHighestTotalPowerOfAnySize(18);
+ debug.assert(V2.eq(V2.init(90, 269), r18.region));
+ debug.assert(16 == r18.square_side_len);
+
+ const r42 = regionOfHighestTotalPowerOfAnySize(42);
+ debug.assert(V2.eq(V2.init(232, 251), r42.region));
+ debug.assert(12 == r42.square_side_len);
}
fn regionOfHighestTotalPower(gsn: u32) V2{
@@ -159,6 +216,7 @@ test "point from index" {
debug.assert(V2.eq(V2.init(1, 1), point_from_index(6, 5)));
debug.assert(V2.eq(V2.init(2, 1), point_from_index(7, 5)));
debug.assert(V2.eq(V2.init(4, 2), point_from_index(14, 5)));
+ debug.assert(V2.eq(V2.init(4, 4), point_from_index(24, 5)));
}
inline fn index_from_point(x: u32, y: u32, stride: usize) usize {
@@ -170,6 +228,7 @@ test "index from point" {
debug.assert(6 == index_from_point(1, 1, 5));
debug.assert(7 == index_from_point(2, 1, 5));
debug.assert(14 == index_from_point(4, 2, 5));
+ debug.assert(24 == index_from_point(4, 4, 5));
}
const V2 = struct {
