python challenge 32解题总结

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)

最后一关网址:www.pythonchallenge.com/pc/rock/beer.html