python challenge 32网址:www.pythonchallenge.com/pc/rock/arecibo.html
好像是个游戏
每行没列前头都用数字表示本行本列各连续方块的个数
网页提示 Fill in the blanks <!-- for warmup.txt -->
下载 http://www.pythonchallenge.com/pc/rock/warmup.txt
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
网上查了一下,这种根据行列连续块的信息还原点阵图的游戏有个专门的名称叫Nonogram
见 http://zh.wikipedia.org/zh-cn/Nonogram
完成程序的过程比较曲折:
1)一开始看到是9*9的小图,就直接用0-512枚举生成每行每列的可能,
然后用穷举的方式通过正则匹配测试,得到了画着上箭头的图 ==> http://www.pythonchallenge.com/pc/rock/up.html
此时得到的需要还原的图是 32*32 的大图,原来的生成每行每列可能排列的方法的效率太低,没法用了;
2)然后用非递归方式写出生成每行每列可能排列的新方法(genlist()),但是在进行穷举时,发现
需要穷举的次数是个天文数字了,根本不可能短时间内算出结果;
3)经过仔细研究,开始尝试先从现有的可能排列中得到能确定是留空还是填充的点,再根据这些点反过来再次过滤所有
可能以去掉不符合的排列,然后再根据保留下的可能排列再次得到能确定的新的留空/填充的点,再用这些点反过来
过滤掉不符合的排列,如此反复进行 确定留空/填充点->过滤不符合排列->确定新的留空/填充点,经过26次后
终于将32*32个点都确定,最终得到画着蟒蛇的图;
4)最初的程序需要执行近22秒,经过优化后,单独执行大概需要近2秒,基本满意。后来从攻略中看到了
通过递归生成每行每列可能排列的函数(genv()),稍微修改就拿来用了,比genlist()要快0.5秒。
现在的程序算这个32*32的蟒蛇图需要约1.5秒(test3())。
5)考虑到应该尽早的以行/列新确定的点为过滤条件减少对应列/行的可能排列,这样可以减少迭代次数,并且减少函数调用
将主要逻辑放在一起,经测试32*32需要约1.3秒(test4())
根据蟒蛇图 ==> http://www.pythonchallenge.com/pc/rock/python.html
ps: 值得注意是网页也给出了解出的蟒蛇图js代码(http://www.pythonchallenge.com/pc/rock/python.js)
网页提示:
Congrats! You made it through to the smiling python.
"Free" as in "Free speech", not as in "free...
上面每个单词都认识,组合起来啥意思不知道:(,google之
搜 “Free as in Free speech, not as in free”搜到第一条是
http://www.gnu.org/philosophy/free-sw.html 中的
"Free software" is a matter of liberty, not price. To understand the concept, you should think of "free" as in "free speech," not as in "free beer."
好像意思是说自由软件指权利上的自由而不是指免费。要理解这一点,你可以比较“自由演讲”和“免费啤酒”中的free的区别。
所以提示中"free..."中的"..."指的是 beer ==> http://www.pythonchallenge.com/pc/rock/beer.html
源代码如下:
def level_32(): def test3(width,height): UNKNOWN,FILL,EMPTY='?','1',' ' resovled=[[UNKNOWN for _ in xrange(width)] for _ in xrange(height)] totalnumber=width*height print totalnumber def genv(v,l,marks): '''递归方式获取可能的排列 v=描述串(tuple列表) l=行/列长度 marks=(填满,留空) ''' r=[] j=0 if v: if len(v)==1: j=1 for i in range(l+2-len(v)-sum(v)): ri=marks[1]*i+marks[0]*v[0]+marks[1]*(1-j) if j: rr=[marks[1]*(l-len(ri))] else: rr=genv(v[1:],l-len(ri),marks) r+=[ri+vv for vv in rr] return r else: return [marks[1]*l] # 非递归方式获取可能的排列,比上面递归方式的genv要慢一点 def genlist(dim,blocklist,marks=('1','0')): '''非递归方式获取可能的排列 dim=行/列长度 blocklist=描述串(tuple列表) marks=(填满,留空) ''' ret=[] blankcnt=dim-sum(blocklist) blockcnt=len(blocklist) idxl=[1 for i in xrange(blockcnt+1)] idxl[0]=0 idxl[-1]=blankcnt-(blockcnt-1) cur=len(idxl)-2 tmp=cur while tmp!=-1: tmpstr=''.join([ marks[1]*idxl[x]+marks[0]*blocklist[x] for x in range(blockcnt)]+[marks[1]*idxl[-1],]) ret.append(tmpstr) if idxl[-1]==0: # 需要进位 tmp=cur-1 # 上一位 while tmp!=-1: # tmp=-1 无位可进,说明列举完毕,退出 if idxl[tmp]<blankcnt-(blockcnt-tmp-1)-sum(idxl[:tmp]): # 此位可以再增加1 idxl[tmp]+=1 for i in range(tmp+1,blockcnt): idxl[i]=1 idxl[-1]=blankcnt-sum(idxl[:-1]) break else: # 此位不能再增加,需要查看更前的一位 tmp-=1 else: idxl[cur]+=1 for i in range(cur+1,blockcnt): idxl[i]=1 idxl[-1]=blankcnt-sum(idxl[:-1]) return ret ## assert sum(sum(x) for x in Horizontal)==sum(sum(x) for x in Vertical) ## Hlist=[genlist(width,item,(FILL,EMPTY)) for item in Horizontal] ## Vlist=[genlist(height,item,(FILL,EMPTY)) for item in Vertical] Hlist=[genv(a,width,(FILL,EMPTY)) for a in Horizontal] Vlist=[genv(a,height,(FILL,EMPTY)) for a in Vertical] print 'all possible row/col generated.' def checksingle(idx,l): '''检查l中所有item的第idx项是否一致,不一致则返回None,否则返回这项的值''' for item in l: if item[idx]!=l[0][idx]: return None return l[0][idx] def confirmed(): '''根据现有的Hlist Vlist搜索可确定的块,在resovled中标出,并返回包含这些新确定的块的列表''' ret=[] # 按行搜索可确定块 for i,rows in enumerate(Hlist): for j in range(width): if resovled[i][j]==UNKNOWN: t= checksingle(j,rows) if t: resovled[i][j]=t ret.append((i,j)) # 按列搜索可确定块 for i,cols in enumerate(Vlist): for j in range(height): if resovled[j][i]==UNKNOWN: t= checksingle(j,cols) if t: resovled[j][i]=t ret.append((j,i)) return ret def reducePossible(obj2check): '''根据obj2check过滤不符合条件的可能排列''' for i,j in obj2check: # 行过滤 c=resovled[i][j] # 有此中间变量可使程序快0.05s Hlist[i]=[item for item in Hlist[i] if item[j]==c] # 列过滤 Vlist[j]=[item for item in Vlist[j] if item[i]==c] print 'H after: ', print ','.join([str(len(x)) for x in Hlist]) print 'V after: ', print ','.join([str(len(x)) for x in Vlist]) resovlednumber=0 itercnt=1 while resovlednumber!=totalnumber: print 'itercnt=%d'%(itercnt,) tocheck=confirmed() if len(tocheck)==0: print 'no more number can confirm! %d'%(resovlednumber,) break resovlednumber+=len(tocheck) reducePossible(tocheck) print 'resolved number: %d'%(resovlednumber,) ## print out itercnt+=1 print 'n'.join([''.join(j) for j in resovled]) print '%s done! %s'%('='*30,'='*30) def test4(width,height): UNKNOWN,FILL,EMPTY='?','1',' ' resovled=[[UNKNOWN for _ in xrange(width)] for _ in xrange(height)] totalnumber=width*height print totalnumber def genv(v,l,marks): r=[] j=0 if v: if len(v)==1: j=1 for i in range(l+2-len(v)-sum(v)): ri=marks[1]*i+marks[0]*v[0]+marks[1]*(1-j) if j: rr=[marks[1]*(l-len(ri))] else: rr=genv(v[1:],l-len(ri),marks) r+=[ri+vv for vv in rr] return r else: return [marks[1]*l] def checksingle(idx,l): '''检查l中所有item的第idx项是否一致,不一致则返回None,否则返回这项的值''' for item in l: if item[idx]!=l[0][idx]: return None return l[0][idx] Hlist=[genv(a,width,(FILL,EMPTY)) for a in Horizontal] Vlist=[genv(a,height,(FILL,EMPTY)) for a in Vertical] print 'all possible row/col generated.' resovlednumber=0 itercnt=1 while resovlednumber!=totalnumber: print 'nitercnt=%d'%(itercnt,) for i,rows in enumerate(Hlist): for j in range(width): if resovled[i][j]==UNKNOWN: t=checksingle(j,rows) if t: resovled[i][j]=t Vlist[j]=[item for item in Vlist[j] if item[i]==t] # 马上用确定的点来减少Vlist对应列的可能数量 resovlednumber+=1 for i,cols in enumerate(Vlist): for j in range(height): if resovled[j][i]==UNKNOWN: t= checksingle(j,cols) if t: resovled[j][i]=t Hlist[j]=[item for item in Hlist[j] if item[i]==t] # 马上用确定的点来减少Hlist对应行的可能数量 resovlednumber+=1 print 'H after: ', print ','.join([str(len(x)) for x in Hlist]) print 'V after: ', print ','.join([str(len(x)) for x in Vlist]) itercnt+=1 print 'n'.join([''.join(j) for j in resovled]) print '%s done! %s'%('='*30,'='*30) 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)) test4(9,9) Horizontal=((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=((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,)) test4(32,32)