Maze
Jump to navigation
Jump to search
Maze is a programming language based on variables that move over instructions. Each Variable is called a Car. Their passage is guided by walls and other controls.
Syntax
Maze controls
| Symbol | Description |
|---|---|
##
|
Wall. Cars will not pass through these. |
..
|
Path. Cars will follow these. |
,
|
Separator. Put this after every command (except at end of line.) |
<>
|
Splitter. Create a new thread. |
42
|
Any two-digit numeral. Pause the car for this amount of 'ticks'. |
^^
|
Start. One per maze only. |
()
|
Hole. Kill cars. |
>>
|
Print. Output the value held by the car. |
<<
|
Grab. Input a value. |
--
|
Will turn into a wall after being run over. |
%L, %R, %D, %U
|
Directions. Force the car to go Left, Right, Down or Up. |
**
|
Signal. See below. |
AA
|
Any two letters. A function to be applied to the car. |
Function commands
| Command | Description |
|---|---|
=
|
Make equal to. Assign a new value to the car. |
-=
|
Subtracts a value from the car and store the result in the car. |
+=
|
Addition. Similar to -=
|
*=
|
Multiplication. Similar to -=
|
/=
|
Division. Similar to -=
|
<=, ==, >=, >, <
|
Comparative statements. |
%L, %R, %D, %U
|
Directions. Force the car to go Left, Right, Down or Up. |
**
|
Signal statement. Return true if there exists a signal in the maze that has a car on it, false otherwise. |
IF condition
|
Conditional branch statement. |
//
|
Comment. Ignore the rest of the line. |
->
|
Define. Assign a function to a function name. |
Functions are defined by putting 2 letters in the maze in the path of the car. The code for the function follows the maze. Example:
AA-> ="Hello" //Make car equal Hello AB-> IF ** THEN %U ELSE %D //If there is a signal in the maze with a car on it, the car will go UP. If not, it will go down. AC-> -=30 //Subtract 30 from value of car
Timing:
Every 'Tick', every car will move 1 step.
Examples
Hello World
##,##,## ##,^^,## //Car Starts ##,AA,## //Do AA to Car ##,>>,## //Print Car ##,(),## //Destroy Car ##,##,## AA-> ="Hello World!"
99 bottles of beer
##,##,##,##,##,##,##,##,##,##,##,##,## ##,##,##,##,##,^^,##,##,##,##,##,##,## //Start Car ##,##,##,##,..,<>,..,..,##,##,##,##,## //Make New Car ##,..,..,..,..,##,##,..,##,##,##,##,## ##,..,##,##,##,..,..,<>,..,..,##,##,## //Make New Car ##,AA,##,##,##,AB,##,##,##,AC,##,##,## //Set Values of Cars ##,%D,..,..,##,%D,..,..,##,%D,..,..,## //Make sure car goes down ##,>>,##,..,##,..,##,..,##,..,##,..,## //Printing... ##,..,##,>>,##,>>,##,>>,##,..,##,AC,## ##,>>,##,..,##,..,##,..,##,..,##,>>,## ##,..,##,..,##,..,##,..,##,>>,##,AF,## ##,AD,**,AG,##,..,AE,..,##,..,AE,..,## //Have we got to one? ##,(),##,##,##,##,(),##,##,##,(),##,## //Destroy Cars ##,##,##,##,##,##,##,##,##,##,##,##,## AA-> =99 AB-> ="Bottles of Beer on the wall," AC-> ="Bottles of Beer\n" AD-> IF == 1 THEN %D ELSE %R AE-> IF ** THEN %R ELSE %D AF-> ="You Take one down, Pass it around," AG-> -= 1
Truth-machine
##,##,##,##,##,##,## ##,##,##,^^,##,##,## ##,##,##,<<,##,##,## ##,(),>>,AA,>>,..,## ##,##,##,..,##,..,## ##,##,##,..,..,..,## ##,##,##,##,##,##,## AA-> IF ==0 THEN %L ELSE %R
Fibonacci sequence
This program works in the Python interpreter below.
##,##,## // fibonacci
##,##,^^,##,##
##,..,<>,PP,##
##,..,##,..,##,##,##,##,##,##,##,## // left column is fib(n), right column is fib(n+1).
##,##,##,##,##,%D,..,LD,..,**,..,..,..,..,..,## // the small left loop sets fib(n) to 0; simultaneously,
##,..,..,..,##,>>,##,..,## ##,##,##,##,##,..,## // the small right loop sets a clone of fib(n+1) to fib(n+1)+f(n).
##,MM,##,..,##,..,##,..,##,##,..,..,..,##,..,## // (this technique is similar to brainfuck [->+<])
##,..,**,FL,..,02,##,%R,..,##,..,##,PP,##,..,## // the small loop at the bottom does nothing, but make sure
##,##,##,NL,##,##,##,%D,<>,01,FR,..,..,##,..,## // that the original fib(n+1) is synchronized with the other cars.
##,>>,##,##,##,..,##,##,03,##,##,##,..,## // then fib(n+1) goes to left column and fib(n+1)+fib(n) to right column
##,(),##,..,..,FM,..,..,%R,..,..,..,..,##
##,##,##,..,##,..,##,##,##,##,##,##,##,##
##,..,..,..,##
##,##,##,##,##
PP-> +=1
MM-> -=1
FR-> IF ** THEN %U ELSE %D
FL-> IF ==0 THEN %D ELSE %L
FM-> IF ** THEN %L ELSE %R
LD-> IF ** THEN %L ELSE %D
NL-> ="\n"
Computational class
Let's show that Maze is Turing complete, via reduction from 3-cell brainfuck +-><[], which is known to be Turing complete.
(See Collatz function for a proof that 3-cell brainfuck is Turing complete.)
Any 3-cell brainfuck program is equivalent to the following Maze program:
- Begin the Maze program with the code:
##,##,##,##,##,##,##
##,##,^^,##,##,##,##
##,..,<>,%R,..,##,##
##,02,##,%D,<>,..,##
##,..,##,..,##,..,##
- Translate brainfuck instructions into Maze, one instruction per line, as follow:
##,..,##,..,##,PP,## // +
##,..,##,..,##,MM,## // -
##,%D,..,%L,##,..,## // >
##,**,##,%D,..,..,##
##,..,##,..,##,##,##
##,SW,01,SW,..,..,##
##,..,##,**,##,..,##
##,03,##,03,##,..,##
##,..,##,%R,..,%D,## // <
##,..,..,%D,##,**,##
##,##,##,..,##,..,##
##,..,..,WS,01,WS,##
##,..,##,**,##,..,##
##,..,##,03,##,03,##
##,##,##,##,##,##,##,##,..,##,..,##,..,## // [
##,..,..,..,..,..,..,..,SW,..,SW,..,%D,##
##,..,##,##,##,##,##,##,..,##,..,##,..,##
##,..,##,..,..,..,..,..,SW,..,%D,##,..,##
##,..,##,..,##,##,##,##,..,##,..,##,..,##
##,..,##,..,##,..,..,..,%D,##,..,##,..,##
##,..,##,..,##,**,##,##,..,##,..,##,..,##
##,..,##,..,##,..,##,##,..,##,..,##,..,##
##,..,##,..,##,**,##,##,..,##,..,##,..,##,##,##,##,##,##,##,##
##,..,##,..,##,..,##,##,..,##,..,##,LO,..,**,..,**,..,**,..,##
##,..,##,..,##,**,##,##,..,##,..,##,..,##,##,##,##,##,##,**,##
##,..,##,08,##,16,##,##,..,##,SW,..,SW,..,..,..,..,..,##,..,##
##,..,##,..,##,..,##,##,..,##,..,##,..,##,##,##,##,..,##,..,##
##,..,##,..,##,..,##,##,SW,..,SW,..,SW,..,..,..,##,..,##,..,##
##,..,##,..,##,..,##,##,..,##,..,##,..,##,##,..,##,..,##,..,##
##,..,##,08,##,16,##,##,..,##,..,##,..,##,##,..,##,..,##,..,## // ]
##,..,##,..,##,..,..,..,..,##,..,##,..,##,##,..,##,..,##,..,##
##,..,##,..,##,##,##,##,##,##,..,##,..,##,##,..,##,..,##,..,##
##,..,##,..,..,..,..,..,..,..,..,##,..,##,##,..,##,..,##,..,##
##,..,##,##,##,##,##,##,##,##,##,##,..,##,##,..,##,..,##,..,##
##,..,..,..,..,..,..,..,..,..,..,..,..,##,##,..,##,..,##,..,##
##,##,##,##,##,##,##,##,##,##,##,##,##,##,##,..,##,..,##,..,##
##,..,..,..,..,..,..,..,..,##,..,##,..,##
##,..,##,##,##,##,##,##,##,##,..,##,..,##
##,..,##,..,..,..,..,..,..,..,..,##,..,##
##,..,##,..,##,##,##,##,##,##,##,##,..,##
##,..,##,..,##,..,..,..,..,..,..,..,..,##
##,..,##,..,##,..,##,##,##,##,##,##,##,##
- Append to the end of the program the code:
##,(),##,(),##,(),##
##,##,##,##,##,##,##
PP-> +=1
MM-> -=1
SW-> IF ** THEN %R ELSE %D
WS-> IF ** THEN %L ELSE %D
LO-> IF ==0 THEN %R ELSE %D
How it works:
When the program begins, three cars are created, each representing a brainfuck cell. The cars travel on three parallel routes; the car in the rightmost route is the "current" cell. Instructions + and - increment and decrement that car's value. Instructions > and < make the cars swap routes: the car matching the "new current cell" comes to the rightmost route and the other two follow accordingly. Instruction [ spawn three new routes, leading to the matching ]. Nested loops are not an issue, as long as extra routes from outer loops are moved to the right to get round inner routes. Similarly, ] spawn three routes that lead back to the matching [. Needless to say, all those peripheral routes must be continued in the body of the loop, parallel to the three main routes.
External resources
- A C++ Maze interpreter
- A Python Maze interpreter