[Level 32]
Title: etch-a-scetch
求解有点复杂，是一个叫 Nonogram 的游戏。
从源码的 warmup.txt 解到 up.txt，再解 up.txt。代码没优化，用时比网上大神的要慢个三倍多吧。
from PIL import Image
import time
def load(file):# 返回hl（len(hor)），vl（len(ver)），hor，ver
with open(file, encoding='utf-8') as f:
lines = f.readlines()
lines = [line.strip() for line in lines if (not line.startswith('#')) and line.strip()!='']
raw = [list(map(int, line.split())) for line in lines]
return raw[0][0], raw[0][1], raw[1:raw[0][0] + 1], raw[raw[0][0] + 1:]
def game(hor, ver, hl, vl):# x 表示行，y 表示列。
hor_alts = [[],] * hl# 用于存储行可能性
ver_alts = [[],] * vl# 用于存储列可能性
line = ['-',] * vl# hl 行，vl列
board = []
for h in range(hl):
board.append(line+[])
dires = [0, 1]# 0 表示水平，1 表示垂直。
init(hor, hor_alts, dires[0])
init(ver, ver_alts, dires[1])
temp_board = []
count = 0
print(time.process_time())
while True:
rever_map(hor_alts, hl, board, dires[0])
rever_map(ver_alts, vl, board, dires[1])
count = count +1
if count == 15:
break
for b in board:
if '-' in b:
print('未解决，还应该再改进！')
return board
def init(hor, alts, d):
for i, line in enumerate(hor):# Such as line = (2, 1, 3)
x, d, pos = getData(line, hl)
alts[i] = []# 需重新开辟空间
getP(x, d, pos, alts[i])# 获取可能性。（列表）
def rever_map(schemes, length, board, d):
for i in range(length):
pss, ass = [], []
line = getLine(i, board, d)
getIndex('#', line, pss)
getIndex('*', line, ass)
schemes[i] = del_im(pss, ass, schemes[i])# 去除第 i 行/列不可能的备选方案。
times = getTimes(schemes[i], length)
if len(schemes[i]) !=0:
setMap(i, schemes[i], times, board, d)# 将确定的选项写入。
def setMap(i, schemes, times, board, d):# 将确定的选项写入。
l = len(schemes)
for j, t in enumerate(times):
if t == l and d == 1:
board[j][i] = '#'
elif t == 0 and d == 1:
board[j][i] = '*'
elif t == l and d == 0:
board[i][j] = '#'
elif t == 0 and d == 0:
board[i][j] = '*'
if l == 1:
schemes = []
def getLine(i, board, d):# 获取第 i 行/列。
if d == 0:
return board[i]
else:
return [board[j][i] for j in range(len(board))]
def del_im(pss, ass, scheme):# 去除某行/列不可能的备选方案。
res = []#最终 scheme = res
for s in scheme:# scheme 为某一种备选方案。
flag = True
for p in pss:
if s[p] != 1:
flag = False
break
for p in ass:
if s[p] != 0:
flag = False
break
if flag:
res.append(s)
return res
def getTimes(source, l):# 获取所有方案中元素在其各个位置出现次数，如source = [[1, 1, 0, 0], [0, 1, 1, 0]]
res = [0,] * l# 出现次数。
for s in source:
for i in range(l):
res[i] = res[i] + s[i]
return res
def getIndex(s, source, res):# 获取所有 s 在 source 中的索引。s 表示要查找的元素，sour 可以是列表、字符串等，res 存储结果。
t = 0
while True:
if s in source[t:]:
i = source.index(s, t)
res.append(i)
t = i + 1
else:
break
def getP(x, d, pos, res):# 获取可能性
if len(pos) == 1:
d = d + [0,] * x
res.append(d)
return
for m in range(x,-1,-1):
if m > 0:
new_d = d[:pos[0]] + [0,] * m + d[pos[0]:]
new_pos = [p+m for p in pos]
if x - m > 0:# 剩余可分配0的个数为 x-m 个
getP(x-m, new_d, new_pos[1:], res)
elif x - m == 0:# 剩余可分配0的个数为0，完成需要
res.append(new_d)
elif m == 0:
getP(x, d, pos[1:], res)
def getData(data, n):# x 为剩余可用于插入的点，d 为可用于插入的列表，pos 为插入的位置
d = []
for i in data:# 转化序列，[2, 1, 3] → [1, 1, 0, 1, 0, 1, 1, 1]
d = d + [1,] * i + [0]
d = d[:-1]
x = n - len(d)
pos = {0}
i = 0
try:
while True:
t = d.index(0, i)
pos.add(t)
i = t + 1
except:
if len(d) > 1:
pos.add(len(d) - 1)# [0, 2, 4, 7] 零所在位置（2，4）和头尾（0，7）都可用于插入。
pos = list(pos)
pos.sort()
return x, d, pos
def print_board(board):
for b in board:
print(''.join(b))
def drawPic(board, x, y):
img = Image.new('L', (x, y))
data = []
for b in board:
for p in b:
if p == '#':
data.append(0)
else:
data.append(255)
img.putdata(data)
return img
hl, vl, hor, ver = load('up.txt')
board = game(hor, ver, hl, vl)
print_board(board)
print(time.process_time())
img = drawPic(board, vl, hl)
img.resize((100, 100)).show()
得到蛇的图片，Python，从 python.html 最终得到 [Level 33]
