DEV Community

AoC Day 11: Chronal Charge

Ryan Palo on December 11, 2018

Day 11, and we find ourselves falling further back in time. Our wearable time-machine is running low on juice, and we need to figure out how to ge...

Read full post

Ali Spittel • Dec 11 '18

lolol this is incredibly slow, but I noticed a pattern and was able to easy escape based on it. I think using numpy is the way to go in order to speed this up.

SERIAL_NUMBER = 1308

def get_power_level(x, y):
    rack_id = x + 10
    power_level = rack_id * y
    power_level += SERIAL_NUMBER
    power_level *= rack_id
    hundreds_digit = int(str(power_level)[-3]) if power_level > 100 else 0
    return hundreds_digit - 5


def gen_grid():
    grid = []
    for x in range(300):
        row = []
        for y in range(300):
            row.append(get_power_level(x+1, y+1))
        grid.append(row)
    return grid


def get_box(grid, row, col, size):
    _sum = 0
    for x in range(0, size):
        for y in range(0, size):
            _sum += grid[row + x][col + y]
    return _sum


def find_max_subgrid(grid):
    max_sum = 0
    coordinates = [0, 0]
    for size in range(3, 300):
        for i in range(300 - size):
            for j in range(300 - size):
                box_sum = get_box(grid, i, j, size)
                if box_sum > max_sum:
                    max_sum = box_sum
                    coordinates = [i + 1, j + 1, size]
        print(coordinates, size, max_sum)
    return coordinates, max_sum


print(find_max_subgrid(gen_grid()))

Anant Jain • Dec 11 '18 • Edited

A speed up I can suggest: pre-compute another grid, say sumGrid where sumGrid[x][y] = sum(grid[i][j] where i is in range(x, N) and j in range(y, N)

So, each element in this new sumGrid is the sum of all elements below and right to it, including itself.

Then sum(x,y,size) is now just:

sum(x,y,size) = 
  sumGrid[x][y] 
  - sumGrid[x][y+size] 
  - sumGrid[x+size][y] 
  + sumGrid[x+size][y+size]

As an example, sum(3,2,5) would look like this:

We need to add that 4th last term sumGrid[x+size][y+size] since we have subtracted it twice as part of terms 2 and 3. The solution now avoids two inner for loops — making it much faster :)

Mustafa Haddara • Dec 11 '18 • Edited

I noticed a pattern and was able to easy escape based on it.

what was the pattern?

Ali Spittel • Dec 11 '18

It increased to the high point then decreased from there! After it went negative it stayed negative.

Mustafa Haddara • Dec 11 '18

And it kept going negative even after you switched block sizes? Huh, cool.

Ali Spittel • Dec 11 '18

yup! positive up to a point, then all negative!

Viktors Jenovs • Dec 11 '18

Brute force for part 1 and brute force with slight optimization for part 2 (~70 seconds is acceptable so I'm leaving it as is ;)

<?php
$input = 1309;

function calcPower($x, $y, $sn) {
  $rackId = $x + 10;
  $powerLevel = $rackId * $y;
  $powerLevel += $sn;
  $powerLevel *= $rackId;
  $powerLevel = ($powerLevel / 100) % 10;
  return $powerLevel - 5;
}

$grid = [];
for ($y=1; $y <= 300; $y++) {
  for ($x=1; $x <= 300; $x++) {
    $grid[$y][$x] = calcPower($x, $y, $input);
  }
}

function getCoords($grid, $square = 3) {
  $maxPower = -INF;
  $maxX;
  $maxY;
  $maxSize;

  for ($size=3; $size <= $square; $size++) {
    for ($y=1; $y <= 300 - $size + 1; $y++) {
      $prevPower = NULL;
      for ($x=1; $x <= 300 - $size + 1; $x++) {
        $power = 0;
        $power1 = 0;
        $power2 = 0;
        if ($prevPower == NULL) {
          for ($bottom=0; $bottom < $size; $bottom++) {
            $power1 += $grid[$y + $bottom][$x];
          }
          for ($right=1; $right < $size; $right++) {
            for ($bottom=0; $bottom < $size; $bottom++) {
              $prevPower += $grid[$y + $bottom][$x + $right];
            }
          }
          $power = $power1 + $prevPower;
        } else {
          for ($bottom=0; $bottom < $size; $bottom++) {
             $power1 += $grid[$y + $bottom][$x];
           }
           for ($bottom=0; $bottom < $size; $bottom++) {
             $prevPower += $grid[$y + $bottom][$x + $size - 1];
           }
          $power = $prevPower;
          $prevPower -= $power1;
        }

        if ($power >= $maxPower) {
          $maxPower = $power;
          $maxX = $x;
          $maxY = $y;
          $maxSize = $size;
        }
      }
    }
  }
  $result = $maxX . "," . $maxY;
  $square > 3 && $result = $result . "," . $maxSize;
  return $result;
}

echo "Part 1: ";
echo getCoords($grid) . "\n";
echo "Part 2: ";
echo getCoords($grid, 300) . "\n";
?>

Mustafa Haddara • Dec 11 '18

Damn, so I learned today that Julia has both the / operator AND the ÷ operator! The / operator will produce a float, regardless of the types of the inputs (so 2/5 returns 2.5) but ÷ does integer division! So 2÷5 returns 2.

Anyways, Part 1 was brute-forceable, on my machine it ran in <0.5 seconds.

But when I attempted to brute-force Part 2...well, it ran in 2 minutes 45 seconds. It works, I guess? I can't help thinking there's a smarter solution to this.

Anyways, my part 2 code:

function most_powerful_region(grid_num)
    max_power = nothing
    max_x = 0
    max_y = 0
    max_block_size = 0
    for block_size in 1:300
        upper_bound = 300 - block_size + 1
        for x in 1:upper_bound
            for y in 1:upper_bound
                p = power_level_block(x,y, grid_num, block_size)
                if max_power == nothing || p > max_power
                    max_power = p
                    max_x = x
                    max_y = y
                    max_block_size = block_size
                end
            end
        end
    end
    return (max_x, max_y, max_block_size)
end

function power_level_block(topx,lefty, grid_num, block_size)
    power = 0
    for x in topx:topx+(block_size-1)
        for y in lefty:lefty+(block_size-1)
            p = power_level(x,y, grid_num)
            power += p
        end
    end
    return power
end


function power_level(x,y, grid_num)
    rack_id = x + 10
    power = rack_id * y
    power += grid_num
    power *= rack_id
    if power >= 100
        power = (power ÷ 100) % 10  # WTF: the / does float division but ÷ does integer division?!
    else
        power = 0
    end
    power -= 5
    return power
end

Florian Rohrer • Dec 11 '18

Python

n = 7689

from itertools import product
from math import ceil
import numpy as np
from scipy import ndimage

a = np.zeros((300,300), dtype=int)
for x, y in product(range(300), range(300)):
    rack_id = x+1+10
    power_level = rack_id*(y+1) + n
    a[y,x] = (int((power_level*rack_id) / 100) % 10)-5

Part 1

k = np.ones((3,3), dtype=int)
m = ndimage.convolve(a, k, mode='constant', cval=0)
y, x = np.unravel_index(m.argmax(), m.shape)
print(x, y)

Part 2

r = []
for i in range(1, 301):
    k = np.ones((i,i), dtype=int)
    m = ndimage.convolve(a, k, mode='constant', cval=0)
    r.append((np.max(m), i))

r.sort(reverse=True)
maximum, i = r[0]
k = np.ones((i,i), dtype=int)
m = ndimage.convolve(a, k, mode='constant', cval=0)
y, x = np.unravel_index(m.argmax(), m.shape)
c = ceil(i / 2 - 2)
print(x-c, y-c, i)

Ryan Palo • Dec 12 '18

Nice use of Numpy! I think you proved @aspittel right. :)

Jon Bristow • Dec 11 '18 • Edited

Kotlin Solution

<brag type="unseemly">I took a night off on Saturday (#9), and ceded my top spot to @tech31842. However, it looks like I'm back in business!</brag>

Part 1

Simple enough... a brute force check was fractions of a second.

fun powerLevel(serial: Int, point: Point): Int {
    return ((point.x + 10) * point.y + serial) * (point.x + 10)
}

private fun answer1(input: Int): Point {
    return (2..299).map { x ->
        (2..299).map { y ->
            Point(x - 1, y - 1) to powerLevel(input, Point(x - 1, y - 1)) +
                    powerLevel(input, Point(x - 1, y)) +
                    powerLevel(input, Point(x - 1, y + 1)) +
                    powerLevel(input, Point(x, y - 1)) +
                    powerLevel(input, Point(x, y)) +
                    powerLevel(input, Point(x, y + 1)) +
                    powerLevel(input, Point(x + 1, y - 1)) +
                    powerLevel(input, Point(x + 1, y)) +
                    powerLevel(input, Point(x + 1, y + 1))
        }.maxBy {
            it.second
        }!!
    }.maxBy { it.second }!!.first
}

Part 2

This one took some luck I think. I had it chunking through these as fast as I could, but it was still was going to take a few minutes. Luckily I had it printing out the results for each size, and I tried the point where it seemed to find the first maximum. I tried figuring out if I could detect this more easily, but I lost interest. I think I'll get some sleep tonight instead!

private tailrec fun findBox(
    size: Int,
    maxSize: Int,
    maxLoc: Point,
    maxPower: Int,
    maxPowerSize: Int,
    grid: List<List<Int>>
): List<Int> {
    if (size > maxSize) {
        return listOf(maxLoc.x, maxLoc.y, maxPowerSize, maxPower)
    }
    println("findBox: $size, $maxSize, $maxLoc, $maxPower, $maxPowerSize")
    val biggest = (1..(301 - size)).map { x ->
        (1..(301 - size)).map { y ->
            Point(x, y) to grid.drop(y - 1).take(size)
                .sumBy { it.drop(x - 1).take(size).sum() }
        }.maxBy {
            it.second
        }!!
    }.maxBy { it.second }!!
    return if (biggest.second > maxPower) {
        findBox(size + 1, maxSize, biggest.first, biggest.second, size, grid)
    } else {
        findBox(size + 1, maxSize, maxLoc, maxPower, maxPowerSize, grid)
    }
}

fun fillGrid(input: Int): List<List<Int>> {
    return (1..300).map { y ->
        (1..300).map { x ->
            powerLevel(input, Point(x, y))
        }
    }
}

private fun answer2(input: Int): List<Int> {
    return findBox(1, 300, Point(-1, -1), -6, -1, fillGrid(input))
}

E. Choroba • Dec 12 '18 • Edited

Brute force was enough for part 1:

#!/usr/bin/perl
use warnings;
use strict;
use feature qw{ say };

my $size = 3;
chomp( my $serial_number = <> );

my @grid;
my @squares;
my $max = [1, 1];
for my $x (1 .. 300) {
    for my $y (1 .. 300) {
        my $rack_id = $x + 10;
        my $level = ($rack_id * $y + $serial_number) * $rack_id;
        $level =~ s/^.*(.)..$/$1/ or $level = 0;
        $level -= 5;
        $grid[$x][$y] = $level;
        if ($x >= $size && $y >= $size) {
            for my $i (0 .. $size - 1) {
                for my $j (0 .. $size - 1) {
                    $squares[ $x - $size + 1 ][ $y - $size + 1 ]
                        += $grid[ $x - $i ][ $y - $j ];
                }
            }
            $max = [ $x - $size + 1, $y - $size + 1 ]
                if $squares[ $x - $size + 1 ][ $y - $size + 1 ]
                > $squares[ $max->[0] ][ $max->[1] ];
        }
    }
}

say join ',', @$max;

Part 2 was running for several hours, so I decided to optimize it. Using smaller squares and only adding the right and bottom edge reduced the time to 4m 10s which was good enough for me.

#!/usr/bin/perl
use warnings;
use strict;
use feature qw{ say };

use List::Util qw{ sum };

chomp( my $serial_number = <> );

my @grid;
my @squares;
my $max;
for my $size (1 .. 300) {
    for my $x (1 .. 300 - $size + 1) {
        for my $y (1 .. 300 - $size + 1) {
            if (1 == $size) {
                my $rack_id = $x + 10;
                my $level = ($rack_id * $y + $serial_number) * $rack_id;
                $level =~ s/^.*(.)..$/$1/ or $level = 0;
                $level -= 5;
                $grid[$x][$y] = $squares[$x][$y] = $level;
                $max = [$x, $y, 1, $level] if ! defined $max
                                           || $level > $max->[3];
            } else {
                my $level = sum(
                    $squares[$x][$y],
                    @{ $grid[ $x + $size - 1 ] }[ $y .. $y + $size - 2 ],
                    $grid[ $x + $size - 1 ][ $y + $size - 1 ],
                    map $_->[ $y + $size - 1 ], @grid[ $x .. $x + $size - 2 ] );
                $squares[$x][$y] = $level;
                $max = [$x, $y, $size, $level] if $level > $max->[3];
            }
        }
    }
    warn "@$max";
}

say join ',', @$max[0 .. 2];

Tiago Romero • Dec 11 '18 • Edited

Javascript solution

I was able to optimize Part 2 using dynamic programming! It went from 146 to 21 seconds!

Basically, for a given (x,y) coordinate, as we increment the square size in 1, the result of the new square total is simply the result of the previous square total + the leftmost column + the bottommost row (and make sure not to sum the last cell twice).

For instance, let's suppose the coordinates are (90,244), and square size is 3 so on brute force we would have to sum this:

const totalForSquareSize3 = 
   grid[90][244] + grid[90][245] + grid[90][246] + 
   grid[91][244] + grid[91][245] + grid[91][246] + 
   grid[92][244] + grid[92][245] + grid[92][246];

With dynamic programming, we would have saved the total for square size 2 in a cache, and then this step would be simply retrieving that and summing the last column and last row minus last cell:

const totalForSquareSize2 = 
   grid[90][244] + grid[90][245] 
   grid[91][244] + grid[91][245];

cache.set('90,244,2', totalForSquareSize2);

...

const totalForSquareSize3 = 
   cache.get('90,244,2') +         grid[90][246] +
                                   grid[91][246] +
   grid[92][244] + grid[92][245] + grid[92][246];

cache.set('90,244,3', totalForSquareSize3);

...

So we are taking advantage of the previous calculations here.

11-common.js

const buildCell = (x, y, serialNumber) => {
    const rackId = x + 10;
    const powerLevel = ( rackId * y + serialNumber ) * rackId;
    const digit = Math.trunc(powerLevel % 1000 / 100) - 5; 
    return digit;
};

const buildGrid = serialNumber => {
    const grid = Array.from({length:301}, row => Array.from({length:301}));

    for (let i = 1; i <= 300; i++) {
        for (let j = 1; j <= 300; j++) {
            grid[i][j] = buildCell(i, j, serialNumber);
        }
    }

    return grid;
};

const findPowerSquare = (grid, squareSize, cache = new Map()) => {
    let squarePower;
    let top = 0;
    let left = 0;

    for (let i = 1; i <= 300 - squareSize; i++) {
        for (let j = 1; j <= 300 - squareSize; j++) {
            let power = 0;

            const previousKey = `${i},${j},${squareSize-1}`;
            const currentKey = `${i},${j},${squareSize}`;
            if (cache.has(previousKey)) {
                power = cache.get(previousKey);
                for (let k = i; k < i + squareSize - 1; k++) {
                    power += grid[k][j + squareSize - 1];
                }
                for (let k = j; k < j + squareSize; k++) {
                    power += grid[i + squareSize - 1][k];
                }
                cache.set(currentKey, power);
            }
            else {
                for (let k = i; k < i + squareSize; k++) {
                    for (let l = j; l < j + squareSize; l++) {
                        power += grid[k][l];
                    }
                }
                cache.set(currentKey, power);
            }
            if (squarePower === undefined || power > squarePower) {
                top = i;
                left = j;
                squarePower = power;
            }
        }
    }

    return [top, left, squarePower];
};

module.exports = {
    buildGrid,
    findPowerSquare
};

11a.js

const {
    buildGrid,
    findPowerSquare
} = require('./11-common');

(() => {
    const serialNumber = 5719;
    const grid = buildGrid(serialNumber);
    const [top, left, squarePower] = findPowerSquare(grid, 3);

    console.log(`The X,Y coordinate is ${top},${left} and total power is ${squarePower}`);
})();

11b.js

const {
    buildGrid,
    findPowerSquare
} = require('./11-common');

const findPowerSquareOfAnySize = grid => {
    let squarePower;
    let top = 0;
    let left = 0;
    let size = 0;

    const cache = new Map();
    for (let i = 1; i <= 300; i++) {
        const [x, y, power] = findPowerSquare(grid, i, cache);

        if (squarePower === undefined || power > squarePower) {
            top = x;
            left = y;
            size = i;
            squarePower = power;
        }
    }

    return [top, left, size, squarePower];
}

(() => {
    const serialNumber = 5719;
    const grid = buildGrid(serialNumber);    

    const [top, left, size, squarePower] = findPowerSquareOfAnySize(grid);

    console.log(`The X,Y,size is ${top},${left},${size} and total power is ${squarePower}`);
})();

Ryan Palo • Dec 12 '18

Ah! Nice! I thought it seemed like caching would really speed things up, but I was too lazy to figure it out. Very cool.

Ryan Palo • Dec 12 '18

Finished just in time for the next day!

The first part was not too bad, mostly just making sure my code lined up with the algorithm provided and then checking all the squares.

The second part was super duper slow. I think you could probably cache the calculations or use previous calculations of smaller size to speed up calculating the bigger sizes. However, I'm sleepy, and I noticed that the example problems both had maximum totals at relatively low numbers (12 and 16), so I just checked squares with sizes up to 30 in the hopes that I'd get lucky. I did, since my answer was in that range! So, high five for optimization-by-laziness!

I'm also really really proud of my sum-calculating code inside the nested loop. It feels very Rust-like, making use of iterators, take, skip, and flat_map. I did a little wiggle when I finally got it to compile. :)

/// Day 11: Chronal Charge
/// 
/// Figure out the power contained in power cells

/// A Grid of powercells with variable power levels
pub struct Grid {
    cells: [[i32; 300]; 300],
    serial: isize,
}

impl Grid {
    pub fn new(serial: isize) -> Self {
        let mut grid = Self { serial, cells: [[0; 300]; 300] };
        grid.generate_values();
        grid
    }

    /// Each cell has a location/serial number-based checksum that
    /// determines its power level.  Calculates all cells.
    fn generate_values(&mut self) {
        for (i, row) in self.cells.iter_mut().enumerate() {
            for (j, value) in row.iter_mut().enumerate() {
                *value = Grid::power_level(self.serial, (i + 1) as i32, (j + 1) as i32);
            }
        }
    }

    /// The checksum power level calculation on a cell basis.
    /// 
    /// Depends on the grid's serial number and on the location of the cell
    fn power_level(serial: isize, x: i32, y: i32) -> i32 {
        let mut result = (x as isize + 10) * (y as isize) + serial;
        result *= x as isize + 10;
        result = (result / 100) % 10;
        (result - 5) as i32
    }

    /// Finds the cell that is at the top left of the 3x3 with the highest
    /// total in the grid.
    pub fn best_cell(&self) -> (usize, usize) {
        let mut max_value = 0;
        let mut max_location = (0, 0);
        for i in 0..298 {
            for j in 0..298 {
                let value = self.cells.iter()
                    .skip(i).take(3)
                    .flat_map(|row| row.iter().skip(j).take(3) )
                    .sum();
                if value > max_value {
                    max_value = value;
                    max_location = (i + 1, j + 1);
                }
            }
        }
        max_location
    }

    /// Finds the cell that is at the top left of the N x N grid with
    /// the highest total power level, where N can be any size between
    /// 1 and 300.
    pub fn best_cell_sized(&self) -> (usize, usize, usize) {
        let mut max_value = 0;
        let mut max_location = (0, 0, 0);
        for size in 1..=30 {
            println!("Doing iteration: {}", size);
            for i in 0..=(300 - size) {
                for j in 0..=(300 - size) {
                    let value = self.cells.iter()
                        .skip(i).take(size)
                        .flat_map(|row| row.iter().skip(j).take(size) )
                        .sum();
                    if value > max_value {
                        max_value = value;
                        max_location = (i + 1, j + 1, size);
                    }
                }
            }
        }
        max_location
    }
}