Python - nixBlog

Python走迷宫,递归

递归走迷宫,练手。

23下午就写好的,可是测试几种不同的迷宫后,发现有个Bug,我以为算法有问题,今早才发现,原来是isDest函数里r和c都写成r了,拷贝out函数的语句再改写造成的悲剧。

#!/usr/bin/env python

# author: @nixzhu
# date: 2012.02.25
# description: Maze, use recursive. 
#		Door is (7, 7), as follow shows
# license: GPL

maze = [
	[1,1,0,0,0,0,1,0],
	[0,1,0,0,0,1,1,0],
	[0,1,1,1,1,1,0,0],
	[1,1,0,0,0,1,0,0],
	[1,0,0,0,0,1,1,1],
	[1,1,1,1,1,1,0,0],
	[0,0,0,1,0,1,1,1],
	[0,0,0,1,0,1,0,1]
]
maze_ = [
	[0,0,0,0,0,0,0,0],
	[0,0,0,0,0,0,0,0],
	[0,0,0,0,0,0,0,0],
	[0,0,0,0,0,0,0,0],
	[0,0,0,0,0,0,0,0],
	[0,0,0,0,0,0,0,0],
	[0,0,0,0,0,0,0,0],
	[0,0,0,0,0,0,0,0]
]

def showMaze(maze):
	print '-----------------S'
	for line in maze:
		for l in line:
			print l,
		print ''
	print '-----------------E'

def findDest(p={'r':0, 'c':0}):
	if out(p):
		#print '>> ++ out\t', p['r'], p['c']
		return False
	#print '>> -- out\t', p['r'], p['c']
	if isWall(p):
		return False
	if wasVisited(p):
		return False

	visit(p)

	if isDest(p):
		print '('+str(p['r'])+', '+str(p['c'])+')'
		maze_[p['r']][p['c']] = '#'
		return True
	else:
		if findDest(p=left(p)):
			print '('+str(p['r'])+', '+str(p['c'])+')'
			maze_[p['r']][p['c']] = '#'
			return True
		if findDest(p=up(p)):
			print '('+str(p['r'])+', '+str(p['c'])+')'
			maze_[p['r']][p['c']] = '#'
			return True
		if findDest(p=right(p)):
			print '('+str(p['r'])+', '+str(p['c'])+')'
			maze_[p['r']][p['c']] = '#'
			return True
		if findDest(p=down(p)):
			print '('+str(p['r'])+', '+str(p['c'])+')'
			maze_[p['r']][p['c']] = '#'
			return True
		return False

def out(p={'r':0, 'c':0}):
	if p['r'] < 0 or p['r'] > 7:
		return True
	if p['c'] < 0 or p['c'] > 7:
		return True
	return False

def isWall(p={'r':0, 'c':0}):
	if maze[p['r']][p['c']] == 0:
		return True
	else:
		return False

def wasVisited(p={'r':0, 'c':0}):
	if maze[p['r']][p['c']] == 2:
		return True
	else:
		return False

def isDest(p={'r':0, 'c':0}):
	if p['r'] == 7 and p['c'] == 7:
		return True
	else:
		return False

def visit(p={'r':0, 'c':0}):
	maze[p['r']][p['c']] = 2
	
def left(p={'r':0, 'c':0}):
	return {'r':p['r'], 'c':p['c']-1}
def right(p={'r':0, 'c':0}):
	return {'r':p['r'], 'c':p['c']+1}
def up(p={'r':0, 'c':0}):
	return {'r':p['r']-1, 'c':p['c']}
def down(p={'r':0, 'c':0}):
	return {'r':p['r']+1, 'c':p['c']}


if __name__=='__main__':
	showMaze(maze)
	if not findDest(p={'r':0, 'c':0}):	# Enter is (0, 0)
		print "No, can't find destination"
	else:
		print "Yes, find destination"
	showMaze(maze)
	showMaze(maze_)

基本上没什么说的,主要是递归的思想。

迷宫的形式:0是墙,1是可走路径,2代表被走过的路。maze_用来显示路径,直观些。

如果我早些在最后调用findDest函数时加上条件判断来确认findDest的返回值,我应该能早些发现isDest里字符的错误。开始检查了几遍函数,居然都没发现,眼神不行了。今早还以为是visit函数的调用位置有问题,胡乱试是不会有结果的。

Python脚本:sgf2asy.py

 

项目地址: https://github.com/nixzhu/sgf2asy

简单来说,就是将SGF格式的围棋棋谱变成 Asymptote 格式的矢量图脚本。

原来我想写一些围棋方面的文档,也想自己整理一些棋谱,或者每个礼拜出个Kindle版的棋谱,用PDF格式,那么使用矢量图会看着很舒服。而且,控制脚本,就可以输出一盘棋不同阶段的图像,还可以将棋谱里的评论提出来作为文档的文字。如果这一切都是自动化的肯定很舒服。

截止到2012-01-26,脚本基本可以工作,还要处理一些棋盘方向、坐标重复以及很重要的棋谱分支情况。现在能生成棋谱树,但是还没有实现分支输出。

 

http://ubuntuone.com/11jdRTzXPGkeci5W2rZaZ9

这是我原来写的一个围棋介绍文章《围棋急速入门》,有兴趣可以看看。

或者包含tex源文件和asy矢量图脚本的完整文档,可以fork。
https://github.com/nixzhu/rushGo

关于Python函数的默认参数

演示Python的函数参数默认值让人困惑的地方,如下代码:

#!/usr/bin/env python
# -*- coding: utf-8 -*-

# 关于函数的默认参数,Block A 和 Block B 有差别吗?
# 从输出来看,是有,但是为什么呢?

def make_node(color='@', children=list()):
	node = {
		'color': color,
		'children': children
	}
	return node

if __name__=='__main__':
	if True: # Block A
		a = make_node(color='#', children=list())
		x = a
		b = make_node(color='$', children=list())
		x['children'].append(b)
		x = b
		c = make_node(color='%', children=list())
		x['children'].append(c)
		print a
		print '---------------------------------------A END\n\n'
	
	if True: # Block B
		a = make_node(color='#')
		x = a
		b = make_node(color='$')
		x['children'].append(b)
		x = b
		c = make_node(color='%')
		x['children'].append(c)
		print a
		print '---------------------------------------B END'

看看输出:

{'color': '#', 'children': [{'color': '$', 'children': [{'color': '%', 'children': []}]}]}
---------------------------------------A END


{'color': '#', 'children': [{'color': '$', 'children': [...]}, {'color': '%', 'children': [...]}]}
---------------------------------------B END

Block A的输出是我要达到的效果。而在Block B里,节点的list是同一个(也就是对象ID一样),这当然是我不希望看到的结果!

那么是什么原因导致我不能少敲些字符呢?关于Python函数的默认参数有什么介绍文档呢?