美術館の最少照明数のコード

目的

ペンパ「美術館」についてのプログラム

あるポリオミノの形状に対して、全体を照らすための最少の照明の個数を求めたい。

特に「階段型」のポリオミノについて考える。

プログラムの内容

class Shape

盤面の形状（ポリオミノ）と、そこに入っている照明の状態を表すクラス

class ShapeCreator

盤面の形状（ポリオミノ）を生成するためのクラス

2種類の階段型に対応

MinimumAkariNumberEvaluator

照明の最少個数を調べるためのクラス

既知の形に対する探索の重複を減らすために、キャッシュを保存

wを固定して、hを小さい方から1ずつ増やすように探索すると高速に動作するはず

code:analyze_akari.py

import numpy as np

class Shape:

__slots__ = [

"white_array", # 柱でないマスでTrue

"state_array", # 照らされているマスでTrue

]

def __init__(self, white_array, state_array):

self.white_array = white_array

self.state_array = state_array

@classmethod

def empty(cls):

return cls(None, None)

def is_empty(self):

return (self.white_array is None)

def hash(self):

return str(self.white_array.tolist()) + str(self.state_array.tolist())

def kind_str(self):

if self.is_empty():

return "\x1b[7m \x1b[m"

white_array = np.where(self.white_array, 1, 0)

state_array = np.where(self.state_array, 2, 0)

repr_array = white_array + state_array

value_map = dict(

v0="\x1b[7m \x1b[m", # reverse (wall)

v1="1", # まだ照らされていないマス

v2="\x1b[41m \x1b[m",

v3="\x1b[31m3\x1b[m", # 照らされているマス

)

str_repr_array = [

for row in repr_array

]

inner_str = "\n".join([

for row in str_repr_array

])

content = sep + "\n" + inner_str + "\n" + sep

return content

def shrink(self):

if np.all((~self.white_array) | (self.state_array)):

return Shape.empty()

row_valid_list = np.any(self.white_array & (~self.state_array),

axis=1)

column_valid_list = np.any(self.white_array & (~self.state_array),

axis=0)

return Shape(white_array_shrink, state_array_shrink)

class ShapeCreator:

__slots__ = []

def __init__(self):

...

def create_double_stairs(self, height, width):

size_r = size_c = height + width

ones = np.ones((size_r, size_c), dtype=bool)

mat_base = np.tril(ones, 0)

mat_remove = np.tril(ones, -width)

white_array = mat_base & (~mat_remove)

state_array = np.zeros((size_r, size_c), dtype=bool)

return Shape(white_array, state_array)

def create_slided_rectangle(self, height, width):

size_r = height

size_c = height + width - 1

ones = np.ones((size_r, size_c), dtype=bool)

white_array = np.tril(np.triu(ones, 0), width - 1)

white_array = white_array

state_array = np.zeros((size_r, size_c), dtype=bool)

return Shape(white_array, state_array)

class MinimumAkariNumberEvaluator:

def __init__(self):

self.cache = dict()

def evaluate(self, shape):

hash_str = shape.hash()

if hash_str in self.cache.keys():

# print(shape.kind_str())

row_size, column_size = shape.white_array.shape

# 一番端のマスを求める

base_column = 0

# 端にリーチするマスのリストを求める

reach_rows_columns = np.full(len(reach_rows), fill_value=base_column)

reach_columns_rows = np.full(len(reach_columns), fill_value=base_row)

reach_columns_couples = np.vstack(

akari_rc_list = np.concatenate([

reach_rows_couples,

reach_columns_couples,

])

rsize, csize = shape.white_array.shape

# 端にリーチする全てのマスについて、照明を置いたときにできる

# 新しい形状の最少照明数を求めて、最小値+1を採用する

minimum_value = None

for akari_rc in akari_rc_list:

white_array = shape.white_array.copy()

state_array = shape.state_array.copy()

r, c = akari_rc

for r_ind in range(r + 1, rsize):

break

for r_ind in range(r - 1, -1, -1):

break

for c_ind in range(c + 1, csize):

break

for c_ind in range(c - 1, -1, -1):

break

new_shape = Shape(white_array, state_array)

new_shape_shrink = new_shape.shrink()

# print(new_shape.kind_str())

# print(new_shape_shrink.kind_str())

if new_shape_shrink.is_empty():

value = 1

else:

value = self.evaluate(new_shape_shrink) + 1

if (minimum_value is None) or (value < minimum_value):

minimum_value = value

return minimum_value

def run_test():

shape_creator = ShapeCreator()

min_akari_num_evaluator = MinimumAkariNumberEvaluator()

for i in range(0, 28):

width = 5

height = i

shape = shape_creator.create_double_stairs(height=height, width=width)

min_akari_num = min_akari_num_evaluator.evaluate(shape)

print(f"{height = }\t{width = }\t{min_akari_num = }")

def run_test_2():

shape_creator = ShapeCreator()

min_akari_num_evaluator = MinimumAkariNumberEvaluator()

for i in range(1, 28):

width = 1

height = i

shape = shape_creator.create_slided_rectangle(

height=height, width=width)

# print(shape.kind_str())

min_akari_num = min_akari_num_evaluator.evaluate(shape)

print(f"{height = }\t{width = }\t{min_akari_num = }")

def main():

# run_test()

run_test_2()

if __name__ == "__main__":

main()