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函数的默认参数有什么介绍文档呢？
SGF Tree
试图将SGF文件变成树，简化版本
SGF是一种可以是用于围棋棋谱记录的文本格式，关键的部分大概类似这样：
(;B[cd];W[pq](;B[cq];W[do])(;B[cf];W[pn]))
如果先从简单的模型开始，例如简化成：
(AB(CD)(EF))
要把这样的字符串解析成一棵二叉树（最简单的情况），使用下面的代码：
#!/usr/bin/env python
# -*- coding: utf-8 -*-
def make_node(color='@', left={}, right={}):
node = {
'color': color,
'left': left,
'right': right
}
return node
def make_sgf_tree(sgf_str='', index=[0], head=make_node()):
current_node = head
# 遍历字符串
while True:
index[0] += 1 # 记录字符串被处理的当前位置，技巧：参数修改
# 循环退出条件
if sgf_str[index[0]] == ')':
break
# 递归处理内层的括号对
elif sgf_str[index[0]] == '(':
make_sgf_tree(sgf_str, index, current_node)
# 非括号字符作为节点的color
else:
n = make_node(color=sgf_str[index[0]])
# 尽量插在树的右边
if not current_node['right']:
current_node['right'] = n
elif not current_node['left']:
current_node['left'] = n
else:
print 'should NOT be there....'
current_node = n
# 前序遍历
def tree_pre_trav(head=make_node()):
start = head
if not start:
return
print start['color'],
tree_pre_trav(start['left'])
tree_pre_trav(start['right'])
# 后序遍历
def tree_post_trav(head=make_node()):
start = head
if start['left']:
tree_post_trav(start['left'])
if start['right']:
tree_post_trav(start['right'])
print start['color'],
# 中序遍历
def tree_in_trav(head=make_node()):
start = head
if start['left']:
tree_in_trav(start['left'])
print start['color'],
if start['right']:
tree_in_trav(start['right'])
if __name__=='__main__':
# sgf_str = '(B(W(BW)(BWB))(WBW))'
sgf_str = '(A(B(CD)(EFG))(HIJ))'
print 'SGF String: \"' + sgf_str + '\"'
sgf_str_index = [0]
head = make_node()
make_sgf_tree(sgf_str=sgf_str, index=sgf_str_index, head=head)
print '\nThe SGF Tree:'
print head
print '\nPreorder Traversal:'
tree_pre_trav(head)
print '\n\nPostorder Traversal:'
tree_post_trav(head)
print '\n\nInorder Traversal:'
tree_in_trav(head)
输出：
SGF String: "(A(B(CD)(EFG))(HIJ))"
The SGF Tree:
{'color': '@', 'right': {'color': 'A', 'right': {'color': 'B', 'right': {'color': 'C', 'right': {'color': 'D', 'right': {}, 'left': {}}, 'left': {}}, 'left': {'color': 'E', 'right': {'color': 'F', 'right': {'color': 'G', 'right': {}, 'left': {}}, 'left': {}}, 'left': {}}}, 'left': {'color': 'H', 'right': {'color': 'I', 'right': {'color': 'J', 'right': {}, 'left': {}}, 'left': {}}, 'left': {}}}, 'left': {}}
Preorder Traversal:
@ A H I J B E F G C D
Postorder Traversal:
J I H G F E D C B A @
Inorder Traversal:
@ H I J A E F G B C D
应该就是下图的样子：
其实最后得到的代码，不过是将一个表示二叉树的字符串变成一颗二叉树而已。再稍微扩展一下，应该就能解析SGF文件了。再然后，就可以设计一个围棋打谱程序了。
还有一个我之前写的C语言的版本，指针与二叉树，可能适合C语言的思维：
#include <stdio.h>
#include <stdlib.h>
struct node {
char color;
char x;
char y;
struct node *left;
struct node *right;
};
// record the beginning of sgf string
char *start = NULL;
void make_sgf_tree(struct node *head, char *str) {
start = str;
struct node *current_node = head;
while (*start != '\n') {
start += 1;
if (*start == ')')
break;
else if (*start == '(')
make_sgf_tree(current_node, start); // 递归，我们都喜欢
else {
if (*start == ';') { // 围棋动作的开始，期望类似 ;W[ab]...
struct node *new_node = (struct node*)malloc(sizeof(struct node));
new_node->color = *(start+1);
new_node->x = *(start+3);
new_node->y = *(start+4);
printf("(%c,%c)\n", new_node->x, new_node->y);
start += 5; //FIXME, there is a better way to parse
if (current_node->right == NULL)
current_node->right = new_node;
else if (current_node->left == NULL)
current_node->left = new_node;
else
printf("22not children........\n");
current_node = new_node;
}
}
}
}
// 前序遍历
void show_tree_pre(struct node *head)
{
struct node *start = head;
if (start != NULL)
printf("<%c(%c,%c)>\n", start->color, start->x, start->y);
if (start->left != NULL)
show_tree_pre(start->left);
if (start->right != NULL)
show_tree_pre(start->right);
}
int main()
{
// 简单的测试，sgf文件的子集，且限定成最简单的二叉树（假定某手棋的变化之多有两种）
char *str = "(;W[ab];B[cd](;W[ef];B[ac](;W[ss];B[rr])(;W[gg];B[hh]))(;W[ee];B[bc]))\n";
printf("SGF string: %s",str);
// 我们把它变成一颗树
struct node *head = (struct node*)malloc(sizeof(struct node));
make_sgf_tree(head, str);
// 再前序遍历看看这个树是不是我们想想的样子
printf("\npreorder travelsal:\n");
show_tree_pre(head->right);
return 0;
}
test
