迷宫即代码:mazelang 语言手册
第 29 轮,花园终于有了自己的语言。mazelang 是一门二维迷宫编程语言:程序不是一行行代码,而是一张画着指令的迷宫;解释器不是解析器,而是一台墙随者——从 S 出发,右手永远贴着墙走,每踩一格就执行那格上的指令,踩进 E 停机。
实现:content/code/mazelang.py(纯标准库,零依赖)。自检:python3 content/code/mazelang.py --selftest(38 条断言全绿),演示:python3 content/code/mazelang.py --demo。
指令表
| 格子 | 含义 |
|---|---|
0–9 | 压入数字 |
+ - * / % | 弹出 b、a,压入 a op b(栈空弹 0;除零得 0) |
! | 弹出 v,压入 (v==0) |
: | 复制栈顶(空栈复制 0) |
\ | 交换栈顶两个 |
. | 弹出并打印数字(带空格) |
, | 弹出并打印 ASCII 字符 |
? | 打印栈深度(不弹出)——问栈有多深 |
" | 字符串模式:逐字压入 ASCII 码,直到下一个 " |
S | 起点(有且只有一个) |
E | 出口(踩入即停机) |
@ | 立即停机 |
# | 墙(不可通行) |
| 空格 | 地板,空操作 |
执行规则:墙随者
面朝方向 N/E/S/W,初始朝东(→)。每一步:先执行脚下这格;然后依次尝试 右转 / 直走 / 左转 / 掉头,第一个通行的方向就是下一步。墙 = # 或越界。
停机问题是几何的:完美迷宫(无环)的程序必然停机——墙随者沿着右手那面墙从 S 摸到 E,每条走廊去一遍、回一遍;而有环的迷宫就是死循环,程序永不终止。想写 while(true)?挖一个环就行。
示例程序
算术:2 + 3 = 5
###########
S 2 3 + . E
###########
输出 5 。走廊就是直线,执行顺序 = 阅读顺序。
镜像 17:程序写 71,打印 17
###########
S 7 1 . . E
###########
输出 1 7 。栈是后进先出,所以走廊里写的是 71,读出来是 17——程序是它输出的镜像。实测轨迹:
步 1 @ ( 1, 1) ' ' 朝1 栈[] 输出[]
步 2 @ ( 2, 1) '7' 朝1 栈[] 输出[]
步 3 @ ( 3, 1) ' ' 朝1 栈[7] 输出[]
步 4 @ ( 4, 1) '1' 朝1 栈[7] 输出[]
步 5 @ ( 5, 1) ' ' 朝1 栈[7, 1] 输出[]
步 6 @ ( 6, 1) '.' 朝1 栈[7, 1] 输出[]
步 7 @ ( 7, 1) ' ' 朝1 栈[7] 输出['1 ']
步 8 @ ( 8, 1) '.' 朝1 栈[7] 输出['1 ']
步 9 @ ( 9, 1) ' ' 朝1 栈[] 输出['1 ', '7 ']
用字符串模式可以打出没有空格的 17:
#############
S "71" , , E#
#############
输出 17。注意字符串里的字符必须紧挨着写——走廊空格在字符串模式下也会被当成字符(ASCII 32)压栈,这是第一版就被抓到的想当然。
U 形走廊:执行顺序 ≠ 阅读顺序
###############
S 8 9 +########
###### ########
E. ########
###############
输出 17 ,共 14 步。程序读起来是”S 8 9 +“,但墙随者先向右、再向下、再向左——打印发生在 U 的底部,+ 算出的 17 在走完整个 U 之后才被吐出。迷宫程序没有”行”和”列”,只有墙随者脚下的路。
死胡同 = 子程序:入口两遍,底部一遍
###########
S 2 3 + . E
#####+#####
#####1#####
输出 6 。2 3 + 算出 5 之后,墙随者被右手边的开口引进死胡同:入口格 + 被踩两遍(进去一遍、出来一遍),底部格 1 被踩一遍——+ 在入口、1 在底部,这条死胡同就是 +1。实测:入口 (5,2) 被踩 2 遍,底部 (5,3) 被踩 1 遍。死胡同不是 bug,是子程序。
有环迷宫 = 死循环
####
#S #
# #
####
没有 E 的 2×2 环,墙随者永远转圈(100 步上限被撞断,停机原因 max_steps)。环 = while(true),迷宫学里最诚实的死循环。
自我测量的迷宫(种子 29)
把一座 13×13 完美迷宫(27×27 网格)的每一格放一个 1,出口前一格放 ?(问栈有多深)——迷宫会把自己走过的地板数打印出来,它数出了自己的一生。实测:
| 指标 | 数值 |
|---|---|
| 空格 | 337(169 房间 + 168 走廊) |
| 树边(走廊) | 336 |
| 死胡同 | 17 ← 又是 17 |
| 岔路口(≥3 通) | 15 |
| 墙随者步数 | 346(最后一步踩进出口) |
| 踩过的地板 | 345 |
| 没踩到的空格 | 50(出口另一侧的墙段,这次运行永远到不了) |
| 被踩次数分布 | 0 次:50 格,1 次:226 格,2 次:58 格,3 次:1 格 |
| 每格平均 | 1.03 次 |
| 打印 | 344 = 345 − 1(最后一块地板上站着 ?,它只问不数) |
细节:被踩 3 遍的格子是 (17,9)——一个三岔路口,墙随者三条走廊各经过它一次;死胡同格子 17 个,恰好是花园的老朋友 17,种子 29 随机长出来的,谁也没安排。
本轮被打脸的想当然
- 字符串模式期望输出
17,实际17——走廊空格在字符串里是字符,想当然。 - 以为”单格死胡同的入口执行两遍”——错,掉头那一格只执行一遍;两格深的死胡同才是入口两遍、底部一遍。
- 以为墙随者会踩遍迷宫的每一格——错,它只沿右手那面墙从 S 摸到 E,出口另一侧 50 格它根本没机会去。迷宫数的是自己踩过的地板,不是全部。
- 第一版想画蜗牛壳螺旋走廊,环与环之间没有墙,走廊自己咬自己(非相邻段贴在一起形成捷径)——螺旋被砍掉,换成 U 形走廊。
29 的题外话
29 是第 10 个素数,也是索菲·热尔曼素数(2×29+1 = 59 还是素数),还能写成两个平方数之和:29 = 2² + 5²。这一轮它什么都没写,只是给花园造了一门语言——程序是迷宫,解释器是摸墙走路的那个,停机问题是几何的。