turn is a two-dimensional programming language that is invariant under 90-degree rotations and has any number of program counters.
A program counter (PC) has a location, direction, and turn direction.
A direction is up, right, down, or left.
A turn direction is left, straight, right, or u-turn.
Each cycle, each PC executes the operation at its location, then moves to its next location. If the next location is a wall and the turn direction is not straight, the direction is changed in the turn direction until the next location is not a wall. If the PC cannot turn to a location is not a wall, the PC dies. A PC also dies if it moves off the grid. If multiple PCs have the same location, direction, and turn direction, all but one of those PCs die. Execution ends when there are no remaining PCs.
There are 8 types of locations and their operations:
/: If the direction is horizontal, the turn direction rotates 90 degrees left. If the direction is vertical, the turn direction rotates 90 degrees right.
\: If the direction is horizontal, the turn direction rotates 90 degrees right. If the direction is vertical, the turn direction rotates 90 degrees left.
-: If the direction is horizontal, there is no effect. If the direction is vertical, the turn direction rotates 180 degrees.
|: If the direction is horizontal, the turn direction rotates 180 degrees. If the direction is vertical, there is no effect.
Z: If the direction is horizontal, read a bit from input. If the direction is vertical, write a bit to output.
N: If the direction is horizontal, write a bit to output. If the direction is vertical, read a bit from input.
+: Create a new PC at this location with direction in the turned direction and turn direction straight.
O: Read from this location or write to this location. If this location contains a bit, then read that bit, otherwise, write a bit. This location initially does not contain a bit.
space or dot (.): No-op.
^ > v <: No-op. Defines the starting location and direction of a PC. The initial turn direction is straight.
any other character: Wall. No-op.
When reading a bit, if the bit read is a 0, the turn direction is rotated 90 degrees to the left. If the bit read is a 1, the turn direction is rotated 90 degrees to the right. At EOF, the turn direction is rotates 180 degrees.
If multiple PCs read the input in a cycle, they all read the same bit. If multiple PCs read the same location in a cycle, they all read the same bit.
When writing a bit, if the turn direction is left, a 0 is written. If the turn direction is right, a 1 is written. Otherwise, nothing is written.
If multiple PCs are writing to the output in a cycle, if they all write the same value, then one bit with that value is written, otherwise nothing is written. If multiple PCs are writing to the same location in a cycle, if they all write the same value, then that value is written, otherwise nothing is written.
Examples
Hello world
>/N|N|NN|N|NNNN|NN|NN|N|N|N|N|NN|N|NN|NNN|NN|N|NN|NNN|NN|N|NNNN|NN|N|NNNNNN|NN#
#N|N|NNNN|N|NNNN|N|NNNN|N|NN|NN|NNN|NN|N|NN|NN|N|NN|NNN|N|NNNN|N|NN|N|NNN|N|Z
- #
N|Z
#
cat
_v_
+
ZNZ
( )
===
approximate touppercase
##|###|#||##---------#
#.......++.-.........#
##.###.#..#NO.......+#
##.......+|-.........#
##/###.#..##.........#
-.O......O...O......+#
##.###.#..##.........#
#.|N|#...............#
#.....|#.Z##.........#
AT##-#-#\.##.........#
PO.#+/+.+.....O......N
PU.#+.+.+......O.....N
RP.#+.+.+.......O....N
OP.#+.+.+........O...N
XE.#+.+.+.........O..N
IR.#+.+.+..........O.N
MC.#.#.#..##NNNNNNNN.#
AA\#+.+.+.>/++++++++.#
TS.\/\/...|APPROXIMATE
EE#######|#TOUPPERCASE
Interpreter
import java.io.BufferedReader;
import java.io.FileReader;
import java.io.InputStream;
import java.io.IOException;
import java.io.OutputStream;
import java.util.ArrayList;
import java.util.Iterator;
public class Turn {
private int height;
private int width;
private ArrayList<ArrayList<Instruction>> grid = new ArrayList<ArrayList<Instruction>>();
private ArrayList<ArrayList<Boolean>> data = new ArrayList<ArrayList<Boolean>>();
private ArrayList<PC> pcs = new ArrayList<PC>();
public enum Instruction {
SLASH, BACKSLASH, DASH, VERT, N, Z, PLUS, O, NOOP, WALL,
}
public enum TurnDir {
STRAIGHT, RIGHT, UTURN, LEFT,
}
public class PC {
private int x;
private int y;
private int dx;
private int dy;
private TurnDir turnDir;
public PC(int x, int y, char dir) {
this.x = x;
this.y = y;
switch (dir) {
case '^': dx = 0; dy = -1; break;
case '>': dx = 1; dy = 0; break;
case 'v': dx = 0; dy = 1; break;
case '<': dx = -1; dy = 0; break;
default: assert false; break;
}
turnDir = TurnDir.STRAIGHT;
}
public PC(PC pc) {
this.x = pc.x;
this.y = pc.y;
this.dx = pc.dx;
this.dy = pc.dy;
this.turnDir = pc.turnDir;
doTurn();
this.turnDir = TurnDir.STRAIGHT;
}
public boolean inBounds() {
return x >= 0 && x < width && y >= 0 && y < height;
}
public void move() {
x += dx;
y += dy;
}
public Instruction rotate(Instruction insn) {
if (dx == 0)
return insn;
switch (insn) {
case SLASH: return Instruction.BACKSLASH;
case BACKSLASH: return Instruction.SLASH;
case DASH: return Instruction.VERT;
case VERT: return Instruction.DASH;
case N: return Instruction.Z;
case Z: return Instruction.N;
default: return insn;
}
}
public TurnDir getTurnDir() {
return turnDir;
}
public void setTurnDir() {
switch (rotate(grid.get(y).get(x))) {
case SLASH:
turnDir = TurnDir.values()[(turnDir.ordinal()+1)%4];
break;
case BACKSLASH:
turnDir = TurnDir.values()[(turnDir.ordinal()+3)%4];
break;
case DASH:
turnDir = TurnDir.values()[(turnDir.ordinal()+2)%4];
break;
}
}
public boolean facingWall() {
return x + dx >= 0 && x + dx < width
&& y + dy >= 0 && y + dy < height
&& grid.get(y + dy).get(x + dx) == Instruction.WALL;
}
public void doTurn() {
int t;
switch (turnDir) {
case RIGHT: t = dx; dx = -dy; dy = t; break;
case LEFT: t = dx; dx = dy; dy = -t; break;
case UTURN: dx = -dx; dy = -dy; break;
}
}
public boolean isInput() {
return rotate(grid.get(y).get(x)) == Instruction.N;
}
public void doInput(boolean eof, boolean bit) {
if (eof)
turnDir = TurnDir.values()[(turnDir.ordinal()+2)%4];
else if (bit)
turnDir = TurnDir.values()[(turnDir.ordinal()+1)%4];
else
turnDir = TurnDir.values()[(turnDir.ordinal()+3)%4];
}
public boolean isOutput() {
return (turnDir == TurnDir.LEFT || turnDir == TurnDir.RIGHT)
&& rotate(grid.get(y).get(x)) == Instruction.Z;
}
public boolean getOutput() {
return turnDir == TurnDir.RIGHT;
}
public boolean isSpawn() {
return grid.get(y).get(x) == Instruction.PLUS
&& turnDir != TurnDir.STRAIGHT;
}
public boolean isReadSignal() {
return grid.get(y).get(x) == Instruction.O
&& data.get(y).get(x) != null;
}
public void readSignal() {
doInput(false, data.get(y).get(x));
}
public void clearSignal() {
data.get(y).set(x, null);
}
public boolean isWriteSignal() {
return (turnDir == TurnDir.LEFT || turnDir == TurnDir.RIGHT)
&& grid.get(y).get(x) == Instruction.O
&& data.get(y).get(x) == null;
}
public void setSignal() {
data.get(y).set(x, getOutput());
}
public boolean equals(PC pc) {
return pc.x == x && pc.y == y && pc.dx == dx && pc.dy == dy
&& pc.turnDir == turnDir;
}
public boolean sameLocation(PC pc) {
return pc.x == x && pc.y == y;
}
}
public Turn(BufferedReader in) throws IOException {
String line;
while ((line = in.readLine()) != null)
parseLine(line);
height = grid.size();
width = 0;
for (ArrayList<Instruction> row : grid)
width = Math.max(width, row.size());
for (ArrayList<Instruction> row : grid)
while (row.size() < width)
row.add(Instruction.NOOP);
while (data.size() < height)
data.add(new ArrayList<Boolean>());
for (ArrayList<Boolean> row : data)
while (row.size() < width)
row.add(null);
}
private void parseLine(String line) {
ArrayList<Instruction> row = new ArrayList<Instruction>();
for (int i = 0; i < line.length(); i++)
switch (line.charAt(i)) {
case '^': case '>': case 'v': case '<':
pcs.add(new PC(i, grid.size(), line.charAt(i)));
/*FALLTHROUGH*/
case ' ': case '.':
row.add(Instruction.NOOP);
break;
case '/': row.add(Instruction.SLASH); break;
case '\\': row.add(Instruction.BACKSLASH); break;
case '-': row.add(Instruction.DASH); break;
case '|': row.add(Instruction.VERT); break;
case 'N': row.add(Instruction.N); break;
case 'Z': row.add(Instruction.Z); break;
case '+': row.add(Instruction.PLUS); break;
case 'O': row.add(Instruction.O); break;
case 'X': row.add(Instruction.WALL); break;
default: row.add(Instruction.WALL); break;
}
grid.add(row);
}
public void run(BitInputStream in, BitOutputStream out) throws IOException {
ArrayList<PC> list = new ArrayList<PC>();
ArrayList<PC> list2 = new ArrayList<PC>();
for (;;) {
for (PC pc : pcs)
if (pc.isOutput())
list.add(pc);
boolean doOutput = false;
boolean output = false;
for (PC pc : list)
if (doOutput) {
if (output != pc.getOutput()) {
doOutput = false;
break;
}
} else {
doOutput = true;
output = pc.getOutput();
}
if (doOutput)
out.write(output);
list.clear();
for (PC pc : pcs) {
pc.setTurnDir();
if (pc.isInput())
list.add(pc);
}
if (list.size() > 0) {
boolean eof = in.eof();
boolean bit = in.read();
for (PC pc : list)
pc.doInput(eof, bit);
list.clear();
}
for (PC pc : pcs) {
if (pc.isReadSignal()) {
pc.readSignal();
list2.add(pc);
continue;
} else if (!pc.isWriteSignal() || list.contains(pc)) {
continue;
}
doOutput = true;
for (PC pc2 : pcs)
if (pc != pc2 && pc.sameLocation(pc2)) {
list.add(pc2);
if (pc.getOutput() != pc2.getOutput())
doOutput = false;
}
if (doOutput)
pc.setSignal();
}
list.clear();
for (PC pc : list2)
pc.clearSignal();
list2.clear();
for (PC pc : pcs)
if (pc.isSpawn())
list.add(new PC(pc));
pcs.addAll(list);
list.clear();
loop:
for (Iterator<PC> i = pcs.iterator(); i.hasNext(); ) {
PC pc = i.next();
for (PC pc2 : pcs)
if (pc2 != pc && pc2.equals(pc)) {
i.remove();
continue loop;
}
if (pc.getTurnDir() != TurnDir.STRAIGHT) {
for (int n = 0; n < 4 && pc.facingWall(); n++)
pc.doTurn();
if (pc.facingWall())
i.remove();
}
}
for (Iterator<PC> i = pcs.iterator(); i.hasNext(); ) {
PC pc = i.next();
pc.move();
if (!pc.inBounds())
i.remove();
}
if (pcs.isEmpty())
break;
}
out.flush();
}
public static class BitInputStream {
private InputStream in;
private int bit;
private int octet;
public BitInputStream(InputStream in) {
this.in = in;
this.bit = 0;
this.octet = 0;
}
public boolean eof() throws IOException {
if (octet >= 0 && bit == 0) {
bit = 128;
octet = in.read();
}
return octet < 0;
}
public boolean read() throws IOException {
if (octet >= 0 && bit == 0) {
bit = 128;
octet = in.read();
}
try {
return (octet & bit) != 0;
} finally {
bit >>>= 1;
}
}
public void close() throws IOException {
in.close();
}
}
public static class BitOutputStream {
private OutputStream out;
private int bit;
private int octet;
public BitOutputStream(OutputStream out) {
this.out = out;
this.bit = 128;
this.octet = 0;
}
public void write(boolean b) throws IOException {
if (b)
octet |= bit;
bit >>>= 1;
if (bit == 0) {
out.write(octet);
bit = 128;
octet = 0;
}
}
public void close() throws IOException {
out.close();
}
public void flush() throws IOException {
out.flush();
}
}
public static class ASCIIBitOutputStream extends BitOutputStream {
private OutputStream out;
public ASCIIBitOutputStream(OutputStream out) {
super(out);
this.out = out;
}
public void write(boolean b) throws IOException {
out.write(b ? '1' : '0');
}
}
public static void main(String[] args) throws Exception {
String src;
BitOutputStream out;
if ("-b".equals(args[0])) {
src = args[1];
out = new ASCIIBitOutputStream(System.out);
} else {
src = args[0];
out = new BitOutputStream(System.out);
}
new Turn(new BufferedReader(new FileReader(src))).run(new BitInputStream(System.in), out);
}
}
No comments:
Post a Comment