Simplified Piet Interpreter

Question

Background

Piet is an esoteric stack-based programming language in which programs are images meant to resemble abstract paintings.

To keep the challenge from being unnecessarily complex, you will not have to consider most of the colors present in Piet, which determine what instructions are executed; instead, each type of instruction will be assigned a specific number or character (more in Code Instructions).

A codel is the basic unit of Piet code, and can be at any size. For the sake of this challenge, you can assume that a codel is a number/character.

A color block is a contiguous region of codels of the same color which is bounded by codels of other colors, or the edge of the program image. A color block can contain another color block within itself, which is counted as a separate color block from the surrounding one. Codels that share corners are not considered to be part of the same color block.

Piet uses a stack to store all data values, which are integers.

Code Execution

A Piet program begins execution in the color block which contains the top left codel of the program. The interpreter contains a Direction Pointer (DP), which initially points to the right. The DP can point up, down, left or right. The interpreter also contains a Codel Chooser (CC), which is initially pointing left. The CC can either point left or right.

As the program is executed, the interpreter travels through the program under the following rules:

1. The interpreter finds the edge of the current color block which is furthest in the direction of the DP. (This edge may be disjoint if the block is of a complex shape.)
2. The interpreter finds the codel of the current color block on that edge which is furthest to the CC's direction of the DP's direction of travel. (Visualize this as standing on the program and walking in the direction of the DP; see table at below.)
3. The interpreter travels from that codel into the color block containing the codel immediately in the direction of the DP.

The program continues following these rules until the code terminates.

(CC table)

DP	CC	Codel Chosen
right	left	uppermost
right	right	lowermost
down	left	rightmost
down	right	leftmost
left	left	lowermost
left	right	uppermost
up	left	leftmost
up	right	rightmost

More Info on Color Blocks

Each non-black and non-white color block (white and black are special colors; more on that later) represents a number equal to the number of codels in that block. Though the interpreter may pass through a color block during execution, it does not necessarily do anything with the color block's stored value; there are specific instructions that deal with these values.

Black color blocks and edges of the program restrict program flow. If the Piet interpreter attempts to move into a black block or off an edge, it is stopped and the CC is toggled. The interpreter then attempts to move from its current block again. If it fails a second time, the DP is moved clockwise one step. These attempts are repeated, with the CC and DP being changed between alternate attempts. If after eight attempts the interpreter cannot leave its current color block, there is no way out and the program terminates.

White color blocks are essentially no-op's in which the interpreter passes unhindered. When the interpreter moves into a white block, it follows the following steps:

• The interpreter "slides" across the white block in a straight line.
• If it hits a restriction, the CC is toggled. Since this results in no difference in where the interpreter is trying to go, the DP is immediately stepped clockwise.
• The interpreter now begins sliding from its current white codel, in the new direction of the DP, until it either enters a colored block or encounters another restriction.
• Each time the interpreter hits a restriction while within the white block, it toggles the CC and steps the DP clockwise, then tries to slide again. This process repeats until the interpreter either enters a colored block (where execution then continues); or until the interpreter begins retracing its route. If it retraces its route entirely within a white block, there is no way out of the white block and execution should terminate.

In the actual Piet language, no instructions are executed upon exiting a white color block. In this regard, this challenge is different from Piet; namely, instructions are executed upon exiting a white color block.

Code Instructions

As stated at the very beginning, to simplify the challenge, colors will not be used. Instead, each instruction will be mapped to a specific number/character of your choosing. When the interpreter enters a color block of a certain number/character, the corresponding instruction is executed. Any operations which cannot be performed (such as popping values when not enough are on the stack) are simply ignored, and processing continues with the next command. The corresponding instruction of the top left color block is not executed when initially running the program (though it will still have a value), but will run on any subsequent visits to the color block.

The instructions are as follows (these are just a subset of all the Piet instructions):

• Push: Pushes the value of the color block just exited onto the top of the stack.
• Pop: Deletes the value on the top of the stack
• Add: Pops the top two values off the stack and pushes the sum of those two numbers onto the stack
• Subtract: Pops the top two values off the stack and pushes the difference between the second topmost value and the top value of the stack
• Multiply: Pops the top two values off the stack and pushes the product of those two numbers onto the stack
• Divide: Pops the top two values off the stack and pushes the quotient between the second topmost value and the top value
• Pointer: Pops the top value off the stack and rotates the DP clockwise that many steps (anticlockwise if negative).
• Switch: Pops the top value off the stack and toggles the CC that many times (the absolute value of that many times if negative).

Task

Choose 10 distinct numbers/characters which each represent one of the code instructions and the black and white codels, and clearly specify which 10 you chose in your answer.

Given a 2d rectangular grid, matrix, or a similar default I/O format consisting of the 10 different characters/numbers of your choosing representing a Piet program, output the final state of the stack after the input program has halted. Assume that all input programs will eventually halt.

The output can be in any reasonable or default output format, as long as it's clear what the state of the stack is. You can also output the stack with the "first" value representing the top of the stack, or the "last" value representing the top of the stack. For example, if the final state of the stack has 2 as the top value, 3 as the second topmost value, and 4 at the bottom of the stack, then both [2,3,4] and [4,3,2] are acceptable output formats. Make sure to include in your answer which output format you are using out of the two.

You can also optionally take in the dimensions of the Piet program.

Worked Example

In this example, 0 is push, 1 is pop, 2 is add, 3 is subtract, 4 is multiply, 5 is divide, 6 is pointer, 7 is switch, 8 is white, 9 is black.

I will also use >, <, ^, v to indicate where the interpreter is and what direction the DP is pointing.

Program:

111090908004
911088808944
911069912399

The program starts in the color block containing the top left codel, which is the 3 by 3 block of 1's. Remember that the initial instruction upon running the code is not ran, so pop (the instruction mapped to 1 in our example) is not ran. Also note that this color block has a value of 7, because it consists of 7 codels.

>11090908001
911088808911
911069912399

Initially, the DP is pointing right, so the interpreter goes to the right edge of the color block. The CC is pointing left, which means that the interpreter first tests the top-right edge for any restrictions.

11>090908001
911088808911
911069912399

There are none, so it travels to the right into the next color block, which is the block of 0's. 0 represents the push instruction, so 7 is pushed to the top of the stack. The stack is now [7]. At this point, the DP is pointing right, and the CC is pointing left, so it first tests the top-right edge for restrictions.

111>90908004
911088808944
911069912399

There is a black codel (9) restricting the program flow, so the CC is toggled and is now pointing to the right. The bottom right edge is now tested:

111090908004
911088808944
911>69912399

There are no restrictions here, so the interpreter travels to the code block to the right, which is the 6. 6 is the pointer instruction, which rotates the DP clockwise 7 times (7 is on the top of the stack) and pops the 7 off the stack, leaving the stack empty. The DP was pointing right, so after 7 clockwise rotations, it points up.

111090908004
911088808944
9110^9912399

There are no restrictions in that direction, so the interpreter moves into the white code block.

111090908004
9110^8808944
911069912399

In white code blocks, the interpreter slides across white codels in a straight line until it hits a restriction, after which the DP is rotated clockwise, and the CC is toggled once. In this case, right after entering the white codel, there is a restriction in the upwards direction, so the DP is turned to the right, and the CC is toggled from right to left.

111090908004
9110>8808944
911069912399

There are no restrictions in this direction, so the interpreter slides across the remaining white codels until it reaches the block of 0's. 0 is the push instruction, so it pushes 3 to the top of the stack (because the white block that the interpreter just exited contains 3 codels). The stack is now [3]. The DP is pointing right and the CC is pointing left, so the interpreter checks the top-right edge first:

1110909>8004
911088808944
911069912399

There are no restrictions in this direction, so it travels into the white block.

11109090>004
911088808944
911069912399

The interpreter slides across the white block in a straight line until it enters the block of 0's. 0 is the push command, so 2 (the value of the white block that the interpreter just exited) is pushed onto the top of the stack. The stack is now [2,3]. The DP is pointing right and the CC is pointing left, so the top-right edge is checked:

1110909080>4
911088808944
911069912399

There are no restrictions in that direction, so it enters into the block of 4's. 4 is the multiply command, so it pops the top two values off the stack and pushes the product of the two popped values. The stack is [2,3], so the 2 and 3 are popped off, and 2*3=6 is pushed onto the stack. The stack is now [6].

The DP is pointing the the right and the CC is pointing to the left, so the top right edge is tested first:

11109090800>
911088808944
911069912399

There is a restriction in that direction (namely, the edge of the program), so the CC is toggled, making it point to the right. The bottom right edge is now tested:

111090908004
91108880894>
911069912399

There is also a restriction in that direction, so the DP is rotated clockwise once, making it point downwards. The CC is pointing to the right, so the bottom left edge is tested:

111090908004
9110888089v4
911069912399

There is also a restriction in that direction, so the CC is toggled, making it point to the left. The bottom right edge is now tested:

111090908004
91108880894v
911069912399

There is also a restriction in that direction, so the DP is rotated clockwise once, making it point to the left. The CC is pointing to the right, so the top left edge is tested:

111090908004
9110888089<4
911069912399

There is a restriction in that direction, so the CC is toggled, making it point to the left. This results in the same edge being chosen, which we already established to have a restriction. The DP is then rotated clockwise once, making it point upwards. The CC is pointing to the left, so the top leftmost edge is tested:

11109090800^
911088808944
911069912399

There's also a restriction in that direction, so the CC is toggled, making it point to the right. This results in the same edge being chosen, which is already known to have a restriction. At this point, 8 unsuccessful attempts have been made at getting out of this color block, so the interpreter concludes that there is no way out of this color block and terminates the program.

The final state of the stack is [6].

Test Cases

Uses the same character set as the worked example above.

111090908004
911088808944
911069912399
-> [6]

1199999999999999
9890888898889889
8880888000888808
8880889888988898
-> [3,9,7,9,7]

21234567000880
99999900000999
40330000000088
44988888888889
-> [-22]

This is code-golf, so shortest code in bytes wins!

---

Reference: official Piet specification

Answer 1

Python3, 1383 bytes:

lambda b:M(set(),b,0,2,[],(0,0))
T={0:(L:={0:max,2:min}),1:(K:={0:min,2:max}),2:K,3:L}
Q={0:(0,1),1:(1,0),2:(0,-1),3:(-1,0)}
I={0:lambda s,v,*a:[*a,[v]+s],1:lambda s,v,*a:[*a,s[1:]],2:lambda s,v,*a:[*a,[sum(s[:2])]+s[2:]],3:lambda s,v,*a:[*a,[s[1]-s[0]]+s[2:]],4:lambda s,v,*a:[*a,[s[0]*s[1]]+s[2:]],5:lambda s,v,*a:[*a,[s[1]/s[0]]+s[2:]],6:lambda s,v,DC,CC:[(s[0]+DC)%4,CC,s[1:]]if s else[DC,CC,s],7:lambda s,v,DC,CC:[DC,[0,2][abs(s[0])%2],s[1:]]}
def V(b,x,y):
 try:
  return 0 if b[x][y]==9 or x<0 or y<0 else 1
 except:return 0
def C(b,v,s):
 q,S,D,d=[s],[s],{s[0]:[s[1]]},{s[1]:[s[0]]}
 while q:
  x,y=q.pop(0)
  for n,m in Q.values():
   if(X:=x+n)>=0 and(Y:=y+m)>=0:
    try:
     if(X,Y)not in S and b[X][Y]==v:q+=[(X,Y)];S+=[(X,Y)];D[X]=D.get(X,[])+[Y];d[Y]=d.get(Y,[])+[X]
    except:1
 return S,D,d
def M(H,b,DC,CC,s,c,P=0,E=[]):
 if(_:=str([DC,CC,s,c,P,E,b[c[0]][c[1]]]))in H:return s
 H.add(_)
 x,*y=C(b,S:=b[c[0]][c[1]],c)
 if P==8:return s
 if S==8:X,Y=c 
 else:
  if DC in[0,2]:X=T[DC][CC](y[1][(Y:=[max,min][DC==2](y[1]))])
  else:Y=T[DC][CC](y[0][(X:=[max,min][DC==3](y[0]))])
 if V(b,A:=X+Q[DC][0],B:=Y+Q[DC][1]):return M(H,b,*(I[b[A][B]](s,len(x),DC,CC)if b[A][B]in I and(s or b[A][B]<2)else[DC,CC,s]),(A,B),0,[])
 if S!=8:return M(H,b,(DC+1)%4 if P%2 else DC,[0,2][CC==0]if not P%2 else CC,s,(X,Y),P+1,[])
 return M(H,b,(DC+1)%4,[0,2][CC==0],s,(X,Y),0,E+[(X,Y)])

Try it online!