יום 11 - Chronal Charge

aoc2018
#1

קישור לחידה המקורית:
https://adventofcode.com/2018/day/11

פיתרון בשפת רובי:

require 'thread/pool'

GRID_SERIAL_NUMBER = ARGV[0]&.to_i || 1955

class FuelCell
  attr_accessor :x, :y

  def initialize(x, y)
    @x = x
    @y = y
    @sums = {}
  end

  def print_square(grid, size)
    y.upto(y + size - 1) do |yy|
      x.upto(x + size - 1) do |xx|
        next unless grid.key?([xx, yy])
        print " #{grid[[xx, yy]].power} "
      end
      puts
    end
  end

  def sum_square(grid, size)
    return @sums[size] if @sums[size]

    @sums[size] = 0
    y.upto(y + size - 1) do |yy|
      x.upto(x + size - 1) do |xx|
        next unless grid.key?([xx, yy])
        @sums[size] += grid[[xx, yy]].power        
      end
    end

    @sums[size]
  end

  def power
    return @power unless @power.nil?

    rack_id = x + 10
    @power = rack_id * y
    @power += GRID_SERIAL_NUMBER
    @power *= rack_id
    @power = (power / 100) % 10
    @power -= 5
  end

  def to_s
    "#{x},#{y} [#{power}]"
  end
end

class Window
  attr_accessor :grid, :x, :y, :size, :sum_cols

  def initialize(grid, x, y, size)
    @grid, @x, @y, @size = grid, x, y, size
    @sum_cols = {}
  end

  def sums
    Enumerator.new do |yielder|
      loop do
        if @x + size >= 300
          @y += 1
          @x = 1
          @sum_cols = @sum_cols.map do |col, v|
            [x, v - grid[[col, @y - 1]].power]
          end.to_h
        end

        if @y + size >= 300
          break
        end
        yielder.yield [@x, @y, size, sum]
        @x += 1
      end
    end
  end

  def sum
    (x..(x + size - 1)).reduce(0) {|acc, x| acc + sum_col(x) }
  end

  def sum_col(col)
    return @sum_cols[col] if @sum_cols.key?(col)

    @sum_cols[col] = (y..(y + size - 1)).
      map       {|y| grid[[col, y]] }.
      reduce(0) {|acc, cell| acc + cell.power }
  end
end

class FuelGrid
  attr_reader :grid
  def initialize
    @grid = {}
    1.upto(300) do |y|
      1.upto(300) do |x|
        @grid[[x, y]] = FuelCell.new(x, y)
      end
    end
  end

  def max(size)
    cell = @grid.max_by {|k, v| v.sum_square(grid, size) }[1]
    res = cell.sum_square(grid, size)
    "#{cell} / #{res}"
  end
end

pool = Thread.pool(4)

grid = FuelGrid.new

(1..300).each do |size|
  pool.process do
    w = Window.new(grid.grid, 1, 1, size)
    puts w.sums.max_by {|x, y, size, sum| sum }.inspect
  end
end
pool.shutdown

כשישבתי בלילה השבוע על התרגיל הזה היתה לי הרגשה שהכל מתחבר והנה תכף מגיעים לסוף, אבל אז הרצתי וגיליתי שהעניין יותר מסובך ממה שנראה במבט ראשון. לקח עוד כמה ימים עד שהיה לי זמן לחזור לזה ולנסות שוב. הפיתרון בגדול משתמש בטכניקה שנקראת חלון צף ואפשר לקרוא עליה קצת כאן:

#2

הי!
לקראת האתגר של השנה פתרתי עוד כמה חידות אחרי שנטשתי את המשחק שנגמר לי הזמן בשנה שעברה. הנה הפתרון שלי לחידה 11, שמשתמש ב- https://en.wikipedia.org/wiki/Summed-area_table

import numpy as np


def power_level(serial: int) -> np.ndarray:
    v = np.arange(300) + 1
    rack_id = v + 10
    return ((np.multiply.outer(v, rack_id) + serial) * rack_id) // 100 % 10 - 5


def power_level_sumtable(serial: int) -> np.ndarray:
    # https://en.wikipedia.org/wiki/Summed-area_table
    a = power_level(serial)
    return np.cumsum(np.cumsum(a, axis=0), axis=1)


def highest_sum(t: np.ndarray, i: int):
    sums = t[i:, i:] - t[:-i, i:] - t[i:, :-i] + t[:-i, :-i]
    y, x = np.unravel_index(np.argmax(sums), sums.shape)
    return sums[y, x], x + 2, y + 2


def part1(serial):
    t = power_level_sumtable(serial)
    return highest_sum(t, 3)


def part2(serial=9798):
    t = power_level_sumtable(serial)
    return max((highest_sum(t, i), i) for i in range(1, 300))


for x, y, serial, level in [
    (3, 5, 8, 4),
    (122, 79, 57, -5),
    (217, 196, 39, 0),
    (101, 153, 71, 4),
]:
    a = power_level(serial)
    assert a[y - 1, x - 1] == level, a[y - 1, x - 1]

# part 1
assert part1(18) == (29, 33, 45)
assert part1(42) == (30, 21, 61)
print(part1(9798))  # (29, 44, 37)

# part 2
result = part2(18)
assert result == ((113, 90, 269), 16), result
result = part2(42)
assert result == ((119, 232, 251), 12), result
print(part2(9798))  # ((121, 235, 87), 13)

אודי

לייק 1
#3

אני פותר את הדברים האלה עכשיו עם קלוז׳ר… ואוי איך חסר לי NumPy