前回に引き続き日能研の広告の問題をパソコンに解かせてみました。
ただし今回は、私なりに整理した考えについても記載しようと思います。
ソース自体は大したことないですが、説明の都合上散らばっているためGistにも貼っておきます。
問題文の整理
問題文から読み取れることを挙げ出します。
- 全ての黒塗りマスには前後左右の黒塗りマスの個数を記載する。
- 1 で記載した数の合計をPとする。
- Pを26にするには、どことどこに黒塗りマスを追加すれば良いか(問い)
- 新たに黒塗りマスを追加すると、前後左右の黒塗りマスの個数の2倍だけPに加算する必要がある。
- 黒塗りできるのは、既に黒塗りされたマスの前後左右のマスのみ。※1
- 上記より、追加した黒塗りマスによって次に黒塗りできるマスが変化する。
※1 問題文に記載が無い5が成り立つ理由は次の通りです。
まず黒マスを2つ追加することよって、どれだけPを増やしたいのかを求めます。
最終的なPの値 - 既存の黒マスの合計(下図参照) = 増やしたい数
26 - (1+1+3+1+3+2+3+1+1) = 10
この時、４より新たに黒塗りマスを追加した時に増えるPの値は0,2,4,6,8のいずれかのため、2つしか置けないマスの一方が0だと合計が10にならないからです。
データを挙げ出す
問題文から問題を解くのに必要なデータを挙げ出します。次の3つがあれば十分だと思います。
1.盤面情報
空白マスを0、黒塗りマスを１とした連続した文字列で盤面を表します。
2.新たに黒塗りする箇所の数
3.出力条件(合計数)
ソースで書くと次のようになります。
board = [
"000000",
"001000",
"011010",
"001110",
"001010",
"000000",
]
set_num = 2
output_condition = 26
盤面情報(board)の扱い
直感的には分かりやすいですが、処理する際には扱いづらいため連続したリストに変換して扱うようにします。
>>> [i for i in "".join(board)]
['0', '0', '0', '0', '0', '0', '0', '0', '1', '0', '0', '0', '0', '1', '1', '0', '1', '0', '0', '0', '1', '1', '1', '0', '0', '0', '1', '0', '1', '0', '0', '0', '0', '0', '0', '0']
このリストを下図のイメージで扱います。x,yは枠外の判定を行う時に使用します。
リストのインデックス番号(list_id)とx,yの変換は次のように行います。
SIZE = len(board[0])
# list_idからx,yを求める
x = list_id % SIZE,
y = int(list_id / SIZE)
# x,yからlist_idを求める。
list_id = y*SIZE + x
上下左右のマスを取得
黒塗りマス1つに入る値を求めれるように、黒塗りマスの上下左右のマスのlist_idを返す関数を実装しました。
上下左右のマスが枠外の場合は除くようにしています。
def vectol_list(list_id, size):
v_work = []
v_id_x,v_id_y = (list_id%size, int(list_id/size))
for v_x,v_y in ((0,-1),(0,1),(-1,0),(1,0)):
v_work_x = v_id_x + v_x
v_work_y = v_id_y + v_y
if (-1 < v_work_x < size) and (-1 < v_work_y < size):
v_work.append(v_work_y*size + v_work_x)
return v_work
結果の出力
"アイウエオ..."やlist_idで出力しても分かりづらいので、置ける場所を赤く染めようと思います。
Pythonで色付き文字を出力する方法は直ぐに分かったので色々試してみると、色付き文字もリストで操作できるみたいです。
from fabric.colors import red
text = ["a", "b", "c", "d"]
print(text)
text[0] = red(text[0])
print(text)
print("".join(text))
# 実行結果
['a', 'b', 'c', 'd']
['\x1b[31ma\x1b[0m', 'b', 'c', 'd']
abcd #aだけ赤字で出力される
というわけで盤面情報と答えリストを渡すと、盤面情報の答えの場所を赤色に変えて出力する関数を実装しました。
from fabric.colors import red
def anser_print(board, anser):
size = len(board[0])
for ans_id,ans_val in enumerate(anser):
print("-"*10)
print("No:{0} {1}".format(ans_id+1, ans_val))
board_work = [i for i in "".join(board)] # リストに変換する
for ans in ans_val:
board_work[ans] = red(board_work[ans]) # 赤色に変換する
for x in range(size, size*size, size+1):
board_work.insert(x,"\n") # 改行コードを追加する
print("".join(board_work))
# テスト
board = [
"000",
"010",
"000",
]
anser_print(board, [[1],[1,3],[4]])
テストロジックの実行結果は次のようになります。
実装方法1
問題文の整理で挙げだした次の3つを使って、黒塗りできるマスの組み合わせを全部試してしていく方法で実装してみます。
- 全ての黒塗りマスには前後左右の黒塗りマスの個数を記載する。
- 1 で記載した数の合計をPとする。
- Pを26にするには、どことどこに黒塗りマスを追加すれば良いか(問い)
手順は次の通りです。
- 黒塗りできるマスと黒塗り済みマスの２種類のリストを作成する。
- 作成した黒塗りできるマスリストから2つ選んだ場合の組み合わせリストを作成する。
- 2で作成したリストから一つ取り出し、黒塗り済みマスリストと論理和をとってworkリストを作成する。
- 3で作成したworkリストよりPの数を求める。
- 4で求めたPと出力条件が一致するなら、3で取り出した組み合わせを答えリストに追加する。
- 3,4,5,を2で作成した全ての組み合わせに対して行う。
- 結果を出力する。
この手順をソースで書くと次のようになります。
def method1(board, set_num, sum):
anser = []
size = len(board[0])
# 手順１
work_dic = {"0":[], "1":[]}
for id,val in enumerate("".join(board)):
work_dic[val].append(id)
# 手順2,手順6
for check in itertools.combinations(work_dic["0"], set_num):
# 手順3
black_list = set(work_dic["1"]) | set(check)
# 手順４,手順5
p = reduce(add, list(map(lambda a:len(set(vectol_list(a,size)) & black_list), black_list)))
if sum == p:
anser.append(check)
anser.append(check)
# 手順7
anser_print(board, anser)
vectol_list()とanser_print()は自前で用意した関数になります。
手順2の組み合わせはitertools.combinations()という便利なものが用意されてたので使わせていただきました。
手順4の実装だけは真面目に説明しようと思います。
# 手順４
p = reduce(add, list(map(lambda a:len(set(vectol_list(a,size)) & black_list), black_list)))
盤面が下図のような場合だとします。
この時、black_listは次のようになります。
bl = {8, 13, 14}
このblack_listに対してvectol_list()を呼び、上下左右を示す値に変換しtempに格納します。
temp = [{2,7,9,14}, {7,12,14,19}, {8,13,15,20}]
tempとblack_listで論理積をとりtempに格納します。
temp[0]とblack_listの場合、{2,7,9,14}と{8,13,14}の両方にある数字は14なのでtemp[0]=[14]となります。
temp = [[14], [14], [8,13]]
temp内のリストのサイズをtempに格納します。
temp = [1, 1, 2]
tempの値を合計しpに格納します。
p = 1 + 1 + 2
ここまでの一連の処理を手順4では行なっています。
実装方法2
実装方法1で終わっても良かったのですが、正直ムダな処理が多いです。
- 確認する必要のない組み合わせも試している。
- 毎回全ての黒マスの集計を行なっている。
なので、問題文の整理で挙げだした次の3つも活用してもう少し効率よく解いてみようと思います。
- 新たに黒塗りマスを追加すると、前後左右の黒塗りマスの個数の2倍だけPに加算する必要がある。
- 黒塗りできるのは、既に黒塗りされたマスの前後左右のマスのみ。
- 上記より、追加した黒塗りマスによって次に黒塗りできるマスが変化する
処理としては全パターンを挙げ出して確認していくしかないのですが、パターンを挙げ出すにあたり6.追加した黒塗りマスによって次に黒塗りできるマスが変化するというのがあり単純にはいきません。
なので、下図の時に2つ黒塗りするパターンを手動で挙げ出しながら手がかりを探りたいと思います。
1個目に黒塗り可能なマスは[1,2,6,9,13,14]のいずれかになります。
2個目に黒塗り可能なマスについては1個目が1だった場合、次のようになります。
- 最初に黒塗り可能なマスである[1,2,6,9,13,14]から1を除いた[2,6,9,13,14]
- 新たに黒塗りできるようになったマス[0,2]のうち、最初から黒塗り可能な[2]はを除いた[0]
このように2個目が2,6,9,13,14だった場合を挙げ出して表にまとめると次のようになります。
ここから2個黒塗りするパターンは次の2つに分類することができます。
分類1：1個目に黒塗りできるマスから2つを選んだ時の組み合わせ
分類2：1個目の黒塗りマス と 追加で黒塗り可能になったマス の直積
([1]と[2,3]の直積は[1,2]と[1,3]です。)
パターン網羅の法則が見えてきました。
では法則が見つかったので手順をまとめて実装していこうと思います。
手順は次の通りです。
- 黒塗りできるマスと黒塗り済みマスの２種類のリストを作成する。
- 既存の黒塗りマスに入る値の合計をpre_pとする。
- 1個目に黒塗り可能なマスのリストを作成する。
- 分類1のリストを作成する。
- 分類2のリストを作成する。
- 4,5で作成したリストから一つ取り出しcheckに格納する。
- checkから順に取り出して、checkが示す場所を黒塗りすることによって増える値をtemp_pに加算していく。
- temp_pとsumが一致するならcheckをanserリストに追加する。
- 6,7,8を4,5で作成したリスト全てで行う。
この手順をソースで書くと次のようになります。
def method2(board, set_num, sum):
anser = []
size = len(board[0])
# 手順1
work_dic = {"0":[], "1":[]}
for id,val in enumerate("".join(board)):
work_dic[val].append(id)
# 手順2
temp = set(work_dic["1"])
pre_p = reduce(add, list(map(lambda a:len(set(vectol_list(a,size)) & temp), temp)))
# 手順3
default_put = list(map(lambda a:vectol_list(a,size), work_dic["1"]))
default_put = list(set(reduce(add, default_put)) - set(work_dic["1"]))
# 手順4
check_list1 = [list(i) for i in itertools.combinations(default_put, set_num)]
# 手順5
check_list2 = []
temp = list(map(lambda a:vectol_list(a,size), default_put))
temp = list(map(lambda a:set(a) - set(work_dic["1"] + default_put), temp))
temp = list(map(lambda a:list(set(a) - set(work_dic["1"] + default_put)), temp))
for id, val in enumerate(default_put):
for c in temp[id]:
check_list2.append([val,c])
# 手順6, 手順9
for check in check_list1 + check_list2:
# 手順7
temp_p = pre_p
black_list = work_dic["1"][:]
for c in check:
black_list.append(c)
temp_p += len(set(vectol_list(c,size)) & set(black_list)) * 2
# 手順8
if temp_p == sum:
anser.append(check)
anser_print(board, anser)
このままでは、set_numが3個以上の時は正しく動作しません。
手順5を関数化して再帰処理にすることで実装できそうだとは思うのですが、正直疲れたのでここで終わろうと思います。
最後に
この手のパズル問題は、僕が思いもつかないような方法で実装する方が沢山いると思います。そんな中で投稿のネタとして扱い、考えた解き方を説明することにはすごく抵抗がありました。
ただ、説明することを前提でソースを書くと、次の3つを繰り返し行っていました。
- ソースを書く。
- いざ説明しようとすると全然説明できない。
- 上手く説明するにはどうすればいいかソースを見直す。
これは、普段「動けばいいでしょ」的なノリでソースを書いている僕にとって、このサイクルを回すモチベーションを維持できたのは大きな発見でした。