<前回の続き>
網羅 ≦ 総当たり
組み合わせ ≦ 順列 (0≦n)
「 組み合わせ で プログラム組むには ソートとか いるだろうか☆?」
{1, 2, 2}
{2, 1, 2}
{2, 2, 1}
「 上図の3つのセットは 組み合わせで言うと全部同じだからな☆ 小さいもの順に並び替えると分かる☆」
{1, 2, 2}
{1, 2, 2}
{1, 2, 2}
「 Python3 で 小さなもの順に並び替えてくれだぜ☆」
def append_cover(tl, br, bl, tr, succeed, failed):
numbers = [tl, br, bl]
numbers.sort()
key = ((numbers[0]*1000 + numbers[1]) *
1000 + numbers[2])*1000 + tr
if key not in cover_dict:
cover_dict[key] = {"succeed": 0, "failed": 0}
value = {"succeed": cover_dict[key]["succeed"] +
succeed, "failed": cover_dict[key]["failed"] + failed}
cover_dict[key] = value
def init_cover_dict():
import random
for tl in range(0, 6):
for br in range(0, 6):
for bl in range(0, 6):
for tr in range(0, 6):
numbers = [pow6[tl], pow6[br], pow6[bl]]
numbers.sort()
key = ((numbers[0]*1000 + numbers[1]) *
1000 + numbers[2])*1000 + pow6[tr]
value = {"succeed": 0, "failed": 0}
cover_dict[key] = value
# 正方形縛り
Succeed : 11
Failed : 0
Both : 0
None : 325
Total : 336
Rate : 0.0327
# 長方形
Succeed : 26
Failed : 4
Both : 0
None : 306
Total : 336
Rate : 0.0774
「 それでも ナン が多いな……☆ ナンって何なんだぜ☆?」
「 ナンの中には 存在しない組み合わせ もあるだろ☆
存在しない組み合わせは 出てこなかったら Succeed だよな☆?」
「 ややこしいっ! 存在しないから 出てこなかった って 何なのよ!」
「 None を止めて、Nothing succeed と、 Unknown に分けるかだぜ☆?」
def append_cover(tl, br, bl, tr, prop_name, offset):
numbers = [tl, br, bl]
numbers.sort()
key = ((numbers[0]*1000 + numbers[1]) *
1000 + numbers[2])*1000 + tr
if key not in cover_dict:
new_key(key)
cover_dict[key]["nothing_flag"] = numbers[0] * \
numbers[1]*numbers[2] % 1000 != pow6[tr]
cover_dict[key][prop_name] += offset
def init_cover_dict():
import random
for tl in range(0, 6):
for br in range(0, 6):
for bl in range(0, 6):
for tr in range(0, 6):
numbers = [pow6[tl], pow6[br], pow6[bl]]
numbers.sort()
key = ((numbers[0]*1000 + numbers[1]) *
1000 + numbers[2])*1000 + pow6[tr]
value = {"succeed": 0, "failed": 0,
"nothing_flag": False, "nothing_succeed": 0}
value["nothing_flag"] = numbers[0] * \
numbers[1]*numbers[2] % 1000 != pow6[tr]
cover_dict[key] = value
def show_cover_dict():
sum_succeed = 0
sum_failed = 0
sum_both = 0
sum_nothing_succeed = 0
sum_nothing_failed = 0
sum_unknown = 0
for key, value in cover_dict.items():
if value["nothing_flag"]:
if 0 < value["nothing_succeed"]:
sum_nothing_succeed += 1
else:
sum_nothing_failed += 1
elif 0 < value["succeed"] and 0 < value["failed"]:
sum_both += 1
elif 0 < value["succeed"]:
sum_succeed += 1
elif 0 < value["failed"]:
sum_failed += 1
else:
sum_unknown += 1
# print("{}: {}".format(key, value))
print("Succeed : {}".format(sum_succeed))
print("Failed : {}".format(sum_failed))
print("Both : {}".format(sum_both))
print("Nothing succeed : {}".format(sum_nothing_succeed))
print("Nothing failed : {}".format(sum_nothing_failed))
print("Unknown : {}".format(sum_unknown))
total = sum_succeed+sum_failed+sum_both + \
sum_nothing_succeed+sum_nothing_failed+sum_unknown
print("total : {}".format(total))
if 0 < total:
print("Rate : {:>.4f}".format(
(sum_succeed+sum_nothing_succeed)/total))
end = 19
for y in reversed(range(0, end-1)):
for x in range(0, end-1):
for y2 in range(y+1, end):
for x2 in range(x+1, end):
# 左上角、右下角、左下角 はレッドゾーンの外にあること。
# 右上角はレッドゾーンの中にあること。
if not is_red_zone(x, y2) and not is_red_zone(x2, y) and not is_red_zone(x, y) and is_red_zone(x2, y2):
tl = table[y2][x]
br = table[y][x2]
bl = table[y][x]
tr = table[y2][x2]
# 左上角、右下角、左下角 は 0 を踏んではいけない。
stamped_zero = False
if tl == 0 or br == 0 or bl == 0:
stamped_zero = True
# 3つの角のうち 2つだけが同じなら、それは左上と右下の配置でなければいけない。ただし左下が 001 ならこのルールは適用外。
secondary_failed = False
if bl != 1 and ((bl == tl and bl != br) or (bl == br and bl != tl)):
secondary_failed = True
# 正方形なら。
square = False
if y2-y == x2-x:
square = True
if not stamped_zero and not secondary_failed:
# and square:
# 成功。数が合っているか確認する。
result = ""
if tl*br*bl % 1000 == tr:
result = "o"
append_cover(tl, br, bl, tr, "succeed", 1)
else:
result = "x"
append_cover(tl, br, bl, tr, "failed", 1)
"""
# 成功を表示。
if result == "o":
print("[{} {}:{}][{} {}:{}][{} {}:{}]=[{} {}:{}({})]{} ".format(
x, y2, tl, x2, y, br, x, y, bl, x2, y2, tr, tl*br*bl % 1000, result))
show_rect([[x, y2], [x2, y], [x, y], [x2, y2]])
"""
"""
# 反例を表示。
if result == "x":
print("[{} {}:{}][{} {}:{}][{} {}:{}]=[{} {}:{}({})]{} ".format(
x, y2, tl, x2, y, br, x, y, bl, x2, y2, tr, tl*br*bl % 1000, result))
show_rect([[x, y2], [x2, y], [x, y], [x2, y2]])
"""
print("")
「 あれっ、2乗の判定が間違っていたかも知らん☆ 変えた☆」
# 長方形
1 624 249 376 625 376 249 624 1 0 1 624 249 376 625 376 249 624 1
624 376 376 624 0 624 376 376 624 0 624 376 376 624 [ 0] [624] [376] [376] 624
249 376 1 624 625 624 1 376 249 0 249 376 1 624 [625] [624] [ 1] [376] 249
376 624 624 376 0 376 624 624 376 0 376 624 624 376 [ 0] [376] [624] [624] 376
625 0 625 0 625 0 625 0 625 0 625 0 625 0 [625] [ 0] [625] [ 0] 625
376 624 624 376 0 376 624 624 376 0 376 624 [624] [376] 0 376 624 624 376
249 376 1 624 625 624 1 376 249 0 249 376 [ 1] [624] 625 624 1 376 249
624 376 376 624 0 624 376 376 624 0 624 [376] 376 624 0 624 376 376 624
1 624 249 376 625 376 249 624 1 0 1 624 249 376 625 376 249 624 1
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 624 249 376 625 376 249 624 1 0 1 624 249 376 625 376 249 624 1
624 376 376 624 [ 0] [624] [376] [376] 624 0 624 376 376 624 0 624 376 376 624
249 376 1 624 [625] [624] [ 1] [376] 249 0 249 376 1 624 625 624 1 376 249
376 624 624 376 [ 0] [376] [624] [624] 376 0 376 624 624 376 0 376 624 624 376
625 0 625 0 [625] [ 0] [625] [ 0] 625 0 625 0 625 0 625 0 625 0 625
376 624 [624] [376] 0 376 624 624 376 0 376 624 624 376 0 376 624 624 376
249 376 [ 1] [624] 625 624 1 376 249 0 249 376 1 624 625 624 1 376 249
624 [376] 376 624 0 624 376 376 624 0 624 376 376 624 0 624 376 376 624
1 624 249 376 625 376 249 624 1 0 1 624 249 376 625 376 249 624 1
Succeed : 26
Failed : 0
Both : 0
Nothing succeed : 0
Nothing failed : 280
Unknown : 30
total : 336
Rate : 0.0774
Info : Finished.
「 長方形で フェイルドが 0 になったのは 不具合なのかどうか☆
また今度調べよう☆ 寝よ☆」
「 コードが見づらいんで、ループする部分と、処理内容を分けるぜ☆」
def brute_force(callback):
"""
総当たり
"""
end = 19
for y in reversed(range(0, end-1)):
for x in range(0, end-1):
for y2 in range(y+1, end):
for x2 in range(x+1, end):
callback(x, y, x2, y2)
print("")
def process(x, y, x2, y2):
# 左上角、右下角、左下角 はレッドゾーンの外にあること。
# 右上角はレッドゾーンの中にあること。
if not is_red_zone(x, y2) and not is_red_zone(x2, y) and not is_red_zone(x, y) and is_red_zone(x2, y2):
tl = table[y2][x]
br = table[y][x2]
bl = table[y][x]
tr = table[y2][x2]
# 左上角、右下角、左下角 は 0 を踏んではいけない。
stamped_zero = False
if tl == 0 or br == 0 or bl == 0:
stamped_zero = True
# 3つの角のうち 2つだけが同じなら、それは左上と右下の配置でなければいけない。ただし左下が 001 ならこのルールは適用外。
secondary_failed = False
if bl != 1 and ((bl == tl and bl != br) or (bl == br and bl != tl)):
secondary_failed = True
# 正方形なら。
square = False
if y2-y == x2-x:
square = True
if not stamped_zero and not secondary_failed:
# and square:
# 成功。数が合っているか確認する。
result = ""
if tl*br*bl % 1000 == tr:
result = "o"
append_cover(tl, br, bl, tr, "succeed", 1)
else:
result = "x"
append_cover(tl, br, bl, tr, "failed", 1)
"""
# 成功を表示。
if result == "o":
print("[{} {}:{}][{} {}:{}][{} {}:{}]=[{} {}:{}({})]{} ".format(
x, y2, tl, x2, y, br, x, y, bl, x2, y2, tr, tl*br*bl % 1000, result))
show_rect([[x, y2], [x2, y], [x, y], [x2, y2]])
"""
"""
# 反例を表示。
if result == "x":
print("[{} {}:{}][{} {}:{}][{} {}:{}]=[{} {}:{}({})]{} ".format(
x, y2, tl, x2, y, br, x, y, bl, x2, y2, tr, tl*br*bl % 1000, result))
show_rect([[x, y2], [x2, y], [x, y], [x2, y2]])
"""
return
brute_force(process)
「 右上だけ 赤枠を踏むだの どうだのも 分けてしまっていいんじゃないの?」
def brute_force(callback):
"""
総当たり
"""
end = 19
for y in reversed(range(0, end-1)):
for x in range(0, end-1):
for y2 in range(y+1, end):
for x2 in range(x+1, end):
stamp_rectangle(x, y, x2, y2, callback)
print("")
def stamp_rectangle(x, y, x2, y2, callback):
tl = table[y2][x]
br = table[y][x2]
bl = table[y][x]
tr = table[y2][x2]
# 左上角、右下角、左下角 はレッドゾーンの外にあること。
# 右上角はレッドゾーンの中にあること。
if not is_red_zone(x, y2) and not is_red_zone(x2, y) and not is_red_zone(x, y) and is_red_zone(x2, y2):
append_cover(tl, br, bl, tr, "stamped", 1)
callback(x, y, x2, y2)
else:
append_cover(tl, br, bl, tr, "can_not_stamp", 1)
return
1 624 249 376 625 376 249 624 1 0 1 624 249 376 625 376 249 624 1
624 376 376 624 0 624 376 376 624 0 624 376 376 624 [ 0] [624] [376] [376] 624
249 376 1 624 625 624 1 376 249 0 249 376 1 624 [625] [624] [ 1] [376] 249
376 624 624 376 0 376 624 624 376 0 376 624 624 376 [ 0] [376] [624] [624] 376
625 0 625 0 625 0 625 0 625 0 625 0 625 0 [625] [ 0] [625] [ 0] 625
376 624 624 376 0 376 624 624 376 0 376 624 [624] [376] 0 376 624 624 376
249 376 1 624 625 624 1 376 249 0 249 376 [ 1] [624] 625 624 1 376 249
624 376 376 624 0 624 376 376 624 0 624 [376] 376 624 0 624 376 376 624
1 624 249 376 625 376 249 624 1 0 1 624 249 376 625 376 249 624 1
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 624 249 376 625 376 249 624 1 0 1 624 249 376 625 376 249 624 1
624 376 376 624 [ 0] [624] [376] [376] 624 0 624 376 376 624 0 624 376 376 624
249 376 1 624 [625] [624] [ 1] [376] 249 0 249 376 1 624 625 624 1 376 249
376 624 624 376 [ 0] [376] [624] [624] 376 0 376 624 624 376 0 376 624 624 376
625 0 625 0 [625] [ 0] [625] [ 0] 625 0 625 0 625 0 625 0 625 0 625
376 624 [624] [376] 0 376 624 624 376 0 376 624 624 376 0 376 624 624 376
249 376 [ 1] [624] 625 624 1 376 249 0 249 376 1 624 625 624 1 376 249
624 [376] 376 624 0 624 376 376 624 0 624 376 376 624 0 624 376 376 624
1 624 249 376 625 376 249 624 1 0 1 624 249 376 625 376 249 624 1
Stamped : 100
Can not stamp : 132
All : 232
「 あれっ☆? 232 箇所しか 長方形を作れないのかだぜ☆?」
<書きかけ>
Crieitは誰でも投稿できるサービスです。 是非記事の投稿をお願いします。どんな軽い内容でも投稿できます。
また、「こんな記事が読みたいけど見つからない!」という方は是非記事投稿リクエストボードへ!
こじんまりと作業ログやメモ、進捗を書き残しておきたい方はボード機能をご利用ください。
ボードとは?
コメント