45 lines
1.1 KiB
Python
Executable File
45 lines
1.1 KiB
Python
Executable File
#!/usr/bin/env python
|
|
|
|
from collections import defaultdict
|
|
|
|
SIZE=300
|
|
SERIAL=8444
|
|
|
|
def get_cell_power(x, y, serial):
|
|
rack_id = x + 10
|
|
power = rack_id * y
|
|
power += serial
|
|
power *= rack_id
|
|
|
|
h = str(power)[-3] if power > 100 else '0'
|
|
return int(h) - 5
|
|
|
|
# creating summed area table
|
|
# https://en.wikipedia.org/wiki/Summed-area_table
|
|
def create_field(serial):
|
|
f = defaultdict(int)
|
|
for y in range(1, SIZE+1):
|
|
for x in range(1, SIZE+1):
|
|
p = get_cell_power(x,y,serial)
|
|
f[(x,y)] = f[(x-1,y)] + f[(x, y-1)] - f[(x-1,y-1)] + p
|
|
return f
|
|
|
|
def get_region_sum(t,x,y,s):
|
|
(x1, y1) = (x-1, y -1)
|
|
(x2, y2) = (x + s -1, y + s - 1)
|
|
return t[(x1,y1)] + t[(x2, y2)] - t[(x1, y2)] - t[(x2, y1)]
|
|
|
|
def get_best(t, s):
|
|
rs = []
|
|
for y in range(1, SIZE -s + 2):
|
|
for x in range(1, SIZE -s +2):
|
|
r = get_region_sum(t, x, y, s)
|
|
rs.append((r,x,y,s))
|
|
return max(rs)
|
|
|
|
|
|
t = create_field(SERIAL)
|
|
print("%d,%d" % get_best(t, 3)[1:3])
|
|
|
|
print("%d,%d,%d" % max([get_best(t, s) for s in range(1, SIZE+1)])[1:])
|