python小练习（097）：etch-a-scetch（一）

jerryxjr1220 · 发表于 2017-5-9 21:36:29

马上注册，结交更多好友，享用更多功能^_^

您需要登录才可以下载或查看，没有账号？立即注册

x

python小练习马上要接近100期了，但是一直有一个python小练习的遗留问题没有解决，那就是在第0期中的etch-a-scetch的谜题始终没有解决，传送门

我准备在接下来的3期中，解决掉这个困扰我好久的难题，也给python小练习系列一个完美的收官。（或许以后就不会再更新了）

先来看一下，这个谜题的描述：

这个图片是热身题

可以看到图片中左边和上边的数字分别描述了对应横行和纵行的红色连续方块的数量。

例如第一行的2 1 2表示第一横行2个红色方块相连，1个红色方块，2个红色方块相连。其余行和列类似。

那么假设现在知道了所有横行和纵行的数字描述，求这些数字描述所组成的图形。
热身题：

# Dimensions
9 9
# Horizontal
2 1 2
1 3 1
5
7
9
3
2 3 2
2 3 2
2 3 2
# Vertical
2 1 3
1 2 3
3
8
9
8
3
1 2 3
2 1 3

复制代码

正式题：

# Dimensions
32 32
# Horizontal lines
3 2
8
10
3 1 1
5 2 1
5 2 1
4 1 1
15
19
6 14
6 1 12
6 1 10
7 2 1 8
6 1 1 2 1 1 1 1
5 1 4 1
5 4 1 4 1 1 1
5 1 1 8
5 2 1 8
6 1 2 1 3
6 3 2 1
6 1 5
1 6 3
2 7 2
3 3 10 4
9 12 1
22 1
21 4
1 17 1
2 8 5 1
2 2 4
5 2 1 1
5
# Vertical lines
5
5
5
3 1
3 1
5
5
6
5 6
9 5
11 5 1
13 6 1
14 6 1
7 12 1
6 1 11 1
3 1 1 1 9 1
3 4 10
8 1 1 2 8 1
10 1 1 1 7 1
10 4 1 1 7 1
3 2 5 2 1 2 6 2
3 2 4 2 1 1 4 1
2 6 3 1 1 1 1 1
12 3 1 2 1 1 1
3 2 7 3 1 2 1 2
2 6 3 1 1 1 1
12 3 1 5
6 3 1
6 4 1
5 4
4 1 1
5

复制代码

jerryxjr1220 · 发表于 2017-5-9 21:41:53

我们可以把这个问题的求解分成几步来操作，今天先分析第一步。
因为每一行的数字描述是由一个列表组成，但是反过来一个列表可以描述的数字组合有很多种，那么能否把所有的组合全部列出来呢？
比如，我们知道[2,1,2] 这个数字列表，同时我们知道这个行的长度是9
那么全排列所有的可能组合：（用1表示红色方块，0表示黑色方块）

['110101100', '110100110', '110100011', '110010110', '110010011', '110001011', '011010110', '011010011', '011001011', '001101011']

复制代码

jerryxjr1220 · 发表于 2017-5-9 21:48:42

分步程序，取得所有数字列表描述的可能排列：

def gen_candi(num,maxlen):
candi = []
for i in range(maxlen+2-sum(num)-len(num)):
head = '0'*i + '1'*num[0]
if len(num)==1:
tail = '0'*(maxlen-len(head))
candi.append(head+tail)
else:
tail = ['0'+j for j in gen_candi(num[1:], maxlen-len(head)-1)]
candi.extend([head + j for j in tail])
return candi

复制代码

账号		自动登录	找回密码
密码			立即注册

[技术交流] python小练习（097）：etch-a-scetch（一）

马上注册，结交更多好友，享用更多功能^_^

本帖被以下淘专辑推荐: