Maze

From Esolang
Jump to: navigation, 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
THEN statement
ELSE statement
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