きっかけ
ボケーっとTwitterを眺めながら過ごすという怠惰な生活をしていると、
を見かけた。とっても素敵で面白そう。
以下でお買い求めできるようです。（まだ届いていないけど、注文しました)
https://www.dragonfjord.com/product/a-puzzle-a-day/
おそらく、99%の人は4日後にはあきるか、ストレスで禿げ散らかすに違いない。
難しいことは、賢いPythonに任せよう
これ、最適化問題として解けます。
戦略
制約充足問題ととらえて
- ブロックを置いたときに当日の日付のマスは空いている
- ブロックを置いたときに当日の日付でないマスはある1つのブロックによりふさがっている
- すべてのブロックを使用する（本当はなくても大丈夫）
で解けます。
2番目の条件が、ブロックが重ならないという 条件を同時に満たしてくれます。
問題定義
このパズルのブロックの形状などを定義します。
問題定義
import datetime
import numpy as np
from copy import deepcopy
#実行日の 月、日を取得する。
dt_now = datetime.datetime.now()
MONTH=dt_now.month
DAY=dt_now.day
#ブロック形状定義
BLOCKS=[
[
[0,0,1],
[1,1,1],
[1,0,0]
],[
[0,0,1,1],
[1,1,1,0]
],[
[1,1,0],
[1,1,1]
],[
[1,1,1],
[1,0,0],
[1,0,0]
],[
[1,0,1],
[1,1,1]
],[
[0,0,1,0],
[1,1,1,1]
],[
[1,1,1,1],
[1,0,0,0]
],[
[1,1,1],
[1,1,1]
]
]
BLOCKS_ARRAY=[]
for block in BLOCKS:
BLOCKS_ARRAY.append(np.array(block))
AREA = np.array(
[[0,0,0,0,0,0,1,1],
[0,0,0,0,0,0,1,1],
[0,0,0,0,0,0,0,1],
[0,0,0,0,0,0,0,1],
[0,0,0,0,0,0,0,1],
[0,0,0,0,0,0,0,1],
[0,0,0,1,1,1,1,1],
[1,1,1,1,1,1,1,1]])
便利ツール定義
同時に、便利ツールも実装しましょう
ブロックは裏表の両面が使用でき、かつ回転もできるのでその操作をした結果のブロック形状を返す関数を定義します。
また、マスクの当たり判定の応用でブロックが配置できるエリアに置こうとしているかどうかの判定を行う関数も定義します。
ちょいちょい出てくる、位置から月、日のデータを返す処理も関数にしておきましょう。
便利ツール
#Blockの変形（回転と、反転）
def reform_block(blockdata,rot=0,flip=False):
if flip:
return np.fliplr(np.rot90(blockdata,rot))
else:
return np.rot90(blockdata,rot)
#array_1 のlocの位置にarray_2を足す
def np_add(array_1,array_2,loc=(0,0)):
_x = loc[0]
_y = loc[1]
_block_y_size = len(array_2)
_block_x_size = len(array_2[0])
for _y_move in range(_block_y_size):
array_1[_y+_y_move][_x:_x+_block_x_size] = array_1[_y+_y_move][_x:_x+_block_x_size] + array_2[_y_move]
def check_putable(blockdata,loc):
_x = loc[0]
_y = loc[1]
_block_y_size = len(blockdata)
_block_x_size = len(blockdata[0])
#最初から枠から出ていると判断できる場合
if _x+_block_x_size > 8 or _y + _block_y_size > 8:
return False
#ベタなチェックはめんどくさいので…
_AREA = deepcopy(AREA)
np_add(_AREA,blockdata,loc)
if np.max(_AREA) != 1:
return False
else:
return True
def get_date_from_loc(loc=(0,0)):
_x = loc[0]
_y = loc[1]
#もし、月を表現するマスだったら
if _y in range(2) and _x in range(6):
return ("MONTH", loc[0] + loc[1]*6 +1)
#もし、日を表現するマスだったら
elif _y in range(2,7) and _x in range(7):
ret = (_y - 2)*7 + _x + 1
if ret > 31:
return ("ERR","ERR")
else:
return ("DAY", (_y - 2)*7 + _x + 1)
else:
return ("ERR","ERR")
メイン処理定義
pulp+CBCで整数計画法として解きます。
処理の流れは
- すべてのブロックに対して
- 配置可能な場所に対して
- とりうるパターンの形状(回転、裏表）
について、採用するかどうかの変数x(0は採用しない、1は採用する）を定義します。
ある条件でブロックがおかれた場合（x=1）、ブロックがふさぐマスにそのxを足していきます。(つまり、マスがふさがることを意味する）
工夫は、
- 変数のKeyをブロックのID,配置した位置,回転状態、反転状態で定義。（最適化後に処理が楽）
- ゲームの当たり判定のような処理で範囲チェック
- ブロックの重なりと、必要なマスが埋まっているかを同時に判定していること
部分です。
メイン処理
from pulp import LpProblem,LpVariable,LpBinary,LpAffineExpression,LpStatus
from itertools import product
p = LpProblem("DailyPuzzle")
x = {}
each_area = np.array([[LpAffineExpression(0)]*8 for i in range(8)])
variable_count = 0
#全てのブロックの配置パターンについてチェックし、配置可能であれば変数を追加し、ブロックがふさぐ位置に+1とする
for block_id,block in enumerate(BLOCKS_ARRAY):
block_used_check = 0
#とりうるxの位置(0-6だけど、ブロックのサイズが最小2なので実質0-5),同様にyがとりうる位置は(0-5)
for x_loc,y_loc in product(range(6),range(6)):
#とりうるBlockの回転、フリップのパターン
for rot_state,flip_state in product(range(4),(True,False)):
#もし変形させたブロックがおけなければスキップ
_reformed_block = reform_block(block,rot_state,flip_state)
if check_putable(_reformed_block,loc=(x_loc,y_loc)) == False:
continue
#もし変形させたブロックがおけるのであれば、その置き方をするかどうかの変数追加
tmp_x = LpVariable(name=f"x{variable_count}",upBound=1,lowBound=0,cat=LpBinary)
variable_count += 1
#辞書型にしてKeyにブロックの変形情報を保持する
x[(block_id,x_loc,y_loc,rot_state,flip_state)] = tmp_x
#ブロックを置いた場合にどこをふさぐかの情報を追加
np_add(array_1=each_area,array_2=_reformed_block*tmp_x,loc=(x_loc,y_loc))
block_used_check += tmp_x
#全てのブロックは必ず1度使用する
p += block_used_check == 1
#月部分が当月の場所は空いている(=0)それ以外は重複なくふさがっている（=1）
for _x,_y in product(range(7),range(7)):
value = get_date_from_loc(loc=(_x,_y))
if value[0] == "MONTH":
if value[1] == MONTH:
p += each_area[_y][_x] == 0
else:
p += each_area[_y][_x] == 1
elif value[0] == "DAY":
if value[1] == DAY:
p += each_area[_y][_x] == 0
else:
p += each_area[_y][_x] == 1
#あとは解くだけ
status = p.solve()
print(LpStatus[status])
可視化
はっきり言って可視化が一番苦労しました。
こんなことならUE5で実装したほうが良かったか(笑)
やる気ないのでネットのコードをコピペです。
可視化
%matplotlib inline
import matplotlib.pyplot as plt
import matplotlib.patches as patch
import matplotlib
import random
if LpStatus[status] == "Optimal":
#解いた情報
block_colors = np.array([[0]*8 for i in range(8)])
for block_id,x_loc,y_loc,rot_state,flip_state in x.keys():
if x[(block_id,x_loc,y_loc,rot_state,flip_state)].value() == 1:
np_add(block_colors,(block_id+1)* reform_block(BLOCKS_ARRAY[block_id],rot_state,flip_state),loc=(x_loc,y_loc))
PLOT_BLOCK_SIZE=2
PLOT_Y_START = PLOT_BLOCK_SIZE*7
MONTHS=["Jan","Feb","Mar","Apr","May","Jun","Jul","Aug","Sep","Oct","Nov","Dec"]
COLORS = random.sample(list(matplotlib.colors.cnames),10)
fig = plt.figure(figsize=(7,7))
ax = plt.axes()
for _x,_y in product(range(7),range(7)):
value = get_date_from_loc(loc=(_x,_y))
if value[0] == "MONTH":
_plt_x = _x*PLOT_BLOCK_SIZE
_plt_y = PLOT_Y_START - _y*PLOT_BLOCK_SIZE
if block_colors[_y][_x] != 0:
rect = patch.Rectangle(xy=(_plt_x, _plt_y), width=PLOT_BLOCK_SIZE, height=PLOT_BLOCK_SIZE, fc=COLORS[block_colors[_y][_x]])
ax.add_patch(rect)
plt.text(_plt_x + PLOT_BLOCK_SIZE/4.0, _plt_y + PLOT_BLOCK_SIZE/2.0, MONTHS[value[1]-1],fontsize=PLOT_BLOCK_SIZE*9)
elif value[0] == "DAY":
_plt_x = _x*PLOT_BLOCK_SIZE
_plt_y = PLOT_Y_START - _y*PLOT_BLOCK_SIZE
if block_colors[_y][_x] != 0:
rect = patch.Rectangle(xy=(_plt_x, _plt_y), width=PLOT_BLOCK_SIZE, height=PLOT_BLOCK_SIZE, fc=COLORS[block_colors[_y][_x]])
ax.add_patch(rect)
plt.text(_plt_x + PLOT_BLOCK_SIZE/4.0, _plt_y + PLOT_BLOCK_SIZE/2.0, value[1],fontsize=PLOT_BLOCK_SIZE*9)
pass
plt.axis('scaled')
ax.set_aspect('equal')
結果
まとめ
必要な変数だけ定義する方法や定式化などがいい感じに思いついたため、するする実装できました。
処理自体も1秒くらいで終わります。
あなたの大切な髪の毛を守るために、365日（うるう年も考えると366日分？）のパターンを全部用意しておくのもよいでしょう。
#蛇足
ARサポートアプリを作成中です。
最初せっかくARだからということで、ブロックを置く部分に直接描画してたらすごくやりにくくなったので今は右下のマークあたりにヒントを出すようにしてる。
そのうち、リリースしたいですねぇ。（パズルの開発者にOKか確認したが、「How Wonderful！」と喜んでくれてたようだ）