13
\$\begingroup\$

Befunge Chess is an esolang mini-game I invented that is centered around the Befunge esolang. The general gist of the game is to make the instruction pointer land on a specific target cell while avoiding the opponent's target cell. Today's challenge isn't to play the game, but to simply execute arbitrary boards.

The Rules of Befunge Chess (Context)

Quoting the Befunge esolangs article:

A Befunge program is laid out on a two-dimensional playfield of fixed size. The playfield is a rectangular grid of ASCII characters, each generally representing an instruction. The playfield is initially loaded with the program. Execution proceeds by the means of a [instruction pointer]. This points to a grid cell on the playfield. The instruction pointer has inertia: it can travel to any of the four cardinal directions, and keep traveling that way until an instruction changes the direction. The instruction pointer begins at a set location (the upper-left corner of the playfield) and is initially travelling in a set direction (right). As it encounters instructions, they are executed. [C]ontrol flow is done by altering the direction of the [instruction pointer], sending it to different literal code paths.

Source

Befunge chess is a 2-player game. The players are called A and B At the start of the game, a board is randomly generated with two cells already filled, like so:

.....
.....
.A...
.....
...B.

The A and the B can go anywhere on the board - their position is arbitrary. However, they cannot go in the top left corner where the instruction pointer would start.

Players take turns placing commands from a modified subset of Befunge commands onto the board in an attempt to make the instruction pointer reach their target square. These commands will be described in their own section. The board is not executed during this phase.

On a player's turn, if they feel that the instruction pointer will land on their target cell, they can choose to execute the board instead of placing a command. This initiates the end sequence of the game. If the instruction pointer does reach the executing player's target piece they win. If it doesn't (i.e. it a) reaches the opponent's target piece, b) reaches a cell it's already passed or c) errors), then the other player wins. Note: stop condition b means that there aren't any infinite loops - hence there will always be an outcome for every possible board

If the board is completely full, then execution is automatic. Errors/reaching an already passed square lead to a tie.

Commands

While the full mini-game I devised uses 28 commands, you'll be required to implement an 8 command subset:

^        Set the instruction pointer's direction to up (north)
v        Set the instruction pointer's direction to down (south)
<        Set the instruction pointer's direction to left (west)
>        Set the instruction pointer's direction to right (east)
#        Jump over the next cell
.        Do nothing (NOP)
A        Player A's target piece
B        Player B's target piece

Execution

The instruction pointer starts in the top left corner (0, 0). It initially moves right (east). It transverses the board until one of the following conditions is met:

A) A player piece is reached B) An error occurs C) A cell is reached that has already been passed once

Note that if the instruction pointer would fall off the board (i.e. reach an edge), it "wraps around to the other side:

...>        # upon reaching the >, the instruction pointer would wrap back to the first cell in the row
....
.v..        # if the v were reached, the instruction pointer would continuing heading down and then wrap around to the second column in the first row.
....

Your challenge is to output the outcome of executing the board.

Testcases

  • The board is guaranteed to contain an A and B piece
>....v.
.....A.
..B....
.......

Output: A


>.v..v.
....>A.
.<B....
..^....

Output: B

....
....
.AB.
....

Output: Tie


v.
AB

Output: A

Note that this is the smallest possible board you have to handle.


.v. 
>.A
^<B 

Output: Tie

This is because the middle cell is passed twice.


>v....
B#....
.A....
^>....

Output: B


...^^...
..<A>...
.^.v....
<B>.....
.v......

Output: Tie

Extra Rules

  • Input/output can be given in any reasonable/convenient format
  • The board size will always be rectangular (have a length and a width), will always be valid (have A, B and a mixture of commands).
  • The board size will always be 2x2 or larger.
  • You can use any character set you like for the different tiles, as long as you have 8 consistent characters/values.

Finally, this is , so the shortest program in each language wins.

\$\endgroup\$
10
  • \$\begingroup\$ Just a consistency note, per the instructions the AB board is invalid since A is in the top left position, where the instruction pointer starts. \$\endgroup\$
    – cnamejj
    Apr 23 '21 at 1:36
  • \$\begingroup\$ Can we use numbers of our choice to represent the cells of the matrix instead of characters? \$\endgroup\$
    – Jonah
    Apr 23 '21 at 3:30
  • 1
    \$\begingroup\$ @jonah You can use any character set you like for the different tiles, as long as you have 8 consistent characters/values., so yes \$\endgroup\$
    – lyxal
    Apr 23 '21 at 3:31
  • \$\begingroup\$ What does error mean? \$\endgroup\$
    – l4m2
    Apr 23 '21 at 4:41
  • 5
    \$\begingroup\$ Bonus points for writing a program in Befunge? \$\endgroup\$ Apr 23 '21 at 14:27
5
\$\begingroup\$

Charcoal, 55 bytes

WS⊞υ⪪ι¹≔⁰θW¬№αψ«≔§§υⅉⅈψ§≔§υⅉⅈTF№>^<vψ≔⊗⌕>^<ψθM⊕⁼#ψ✳θ»⎚ψ

Try it online! Link is to verbose version of code. Takes input as a newline-terminated list of strings and outputs A or B, or T for a tie. Explanation:

WS⊞υ⪪ι¹

Input the map and split it into characters.

≔⁰θ

Start off facing right.

W¬№αψ«

Repeat while the last seen character is not a letter.

≔§§υⅉⅈψ

Look at the current character in the map. Charcoal's array indexing is cyclic, so although I'm wandering around the canvas, I'm still seeing the correct character here.

§≔§υⅉⅈT

Replace the character with a T to show that we've seen it before.

F№>^<vψ

If the current character is a direction, then...

≔⊗⌕>^<ψθ

... update the direction variable.

M⊕⁼#ψ✳θ

Move one or two steps in the current direction as appropriate.

»⎚ψ

Output the winner.

\$\endgroup\$
1
  • \$\begingroup\$ I guess I could save 5 bytes by using ruld instead of >^<v... \$\endgroup\$
    – Neil
    Apr 23 '21 at 18:47
5
\$\begingroup\$

JavaScript (V8), 134 bytes

f=D=>eval('for(w=D[c=x=y=X=0].length,h=D.length;c--||(c=D[y][x],D[y][x]=f,c>2?c=[,X=c-4]:c<f);y=(--t%2+y+h)%h)x=-(t=X,--t%2-x-w)%w;c')

Try it online!

Optimized from tsh's, input map {"A":"a","B":"b","<":"6",">":"4","^":"5","v":"7",".":"0","#":"1",}

JavaScript (V8), 153 bytes

f=D=>eval('x=y=Y=0,X=1;for(w=D[0].length,h=D.length;c=D[y][x],D[y][x]=f,+c?Y=![X=c-4]:1/c?(x+=X,y+=Y):c+1-0?Y=c+1-[X=0]:0,c<f;x=(x+X+w)%w)y=(Y+y+h)%h;c')

Try it online!

Rewritten from Redwolf Programs's template

\$\endgroup\$
5
\$\begingroup\$

JavaScript (V8), 218 bytes

-3 thanks to @Arnauld

d=>eval('x=y=r=0,p=[],q=1;while(((m=d[y][x])-6)*(m-7)*!p.includes(w=x+[,y])){p.push(w);[q,r]=[[0,-1],[1,0],[0,1],[-1,0],[q,r],[q,r]][m];x=(x-q*~(m==5)+(z=d[0].length))%z;y=(y-r*~(m==5)+(z=d.length))%z};"AB"[m-6]||"T"')

Try it online!

\$\endgroup\$
8
  • \$\begingroup\$ Very nice. Very good \$\endgroup\$
    – lyxal
    Apr 23 '21 at 3:15
  • \$\begingroup\$ Can you use the eval`str`; trick? \$\endgroup\$ Apr 23 '21 at 13:01
  • \$\begingroup\$ @Wezl eval wont work that way \$\endgroup\$
    – tsh
    Apr 23 '21 at 13:11
  • \$\begingroup\$ @Wezl More specifically, the fn`str` doesn't pass the string itself, but [str] (and sometimes some other stuff), which most built-ins will stringify anyway \$\endgroup\$ Apr 23 '21 at 13:22
  • \$\begingroup\$ Some golf abc: p.includes(w=x+","+y), p.push(w) can be p[w=[x,y]], p[w]=1; [q,r]=[[0,-1],[1,0],[0,1],[-1,0],[q,r],[q,r]][m] can be m<4?[q,r]=[[0,-1],[1,0],[0,1],[-1,0]][m]:0; x;while(y){z1;z2;z3} can be for(x;y;z3){z1;z2} \$\endgroup\$
    – tsh
    Apr 23 '21 at 13:32
4
\$\begingroup\$

Python 3.8, 134 bytes

f=lambda s,r=0,c=0,d=5,*v:(g:=s[r][c])//9+((r,c)in v)or f(s,(r+(d:=g%8or d)//3*(k:=g//8+1)-k)%len(s),(c+d%3*k-k)%len(s[0]),d,*v,(r,c))

Try it online!

Takes advantage of the looser input/output formats. In particular the input grid is mapped in the following way: { '^': 1, 'v': 7, '<': 3, '>': 5, '#': 8, '.': 0, 'A': 18, 'B': 27 }. For output, it returns 1 on a tie, 2 if A wins, and 3 if B wins.

\$\endgroup\$
2
  • \$\begingroup\$ I was really hoping someone would take advantage of the loose input format in a creative way. Thank you! \$\endgroup\$
    – lyxal
    Apr 23 '21 at 8:50
  • \$\begingroup\$ @Lyxal only say any character set so I only dare use {"A":"a","B":"b","<":"3",">":"5","^":"-","v":"+",".":"!","#":"0",}, not ` 'A': 18, 'B': 27 }` \$\endgroup\$
    – l4m2
    Apr 23 '21 at 8:55
4
\$\begingroup\$

JavaScript (V8), 125 bytes

a=>eval("for(d=5,w=a[x=y=0].length,h=a.length;(c=a[y%=h][x%=w])<9;d%2?x+=w+m:y+=h+m)a[y][x]='T',d=c>2?c:d,m=(d%3-1)*-~!+c;c")

Try it online!

    '<': '3',
    '^': '6',
    '>': '5',
    'v': '8',
    '.': '2',
    '#': '0',
    'A': 'A',
    'B': 'B',
\$\endgroup\$
3
\$\begingroup\$

APL(Dyalog Unicode), 149 147 bytes SBCS

p v o g←(1 1)(0 1)⍬⎕
l←{v⊢←0 ¯1}
r←{v⊢←0 1}
u←{v⊢←¯1 0}
d←{v⊢←1 0}
b←{o,←⊂p⋄p+←v⋄p⊢←1+(⍴g)|p-1}
{o∊⍨⊂p:'T'⋄'.'=⍨x←p⌷g:b⍵⋄x∊⎕A:x⋄⍎x,'⍵⋄b⍵'}⍣{⊃⍵∊⎕A}0

Try it on APLgolf!

A tradfn submission which takes the grid as a character matrix. I'm sure there's multiple places to improve this.

><^v# → rludb and the rest of the instructions .AB remain the same.

Here's a testcase converter, in case there are other inputs.

\$\endgroup\$
4
  • \$\begingroup\$ Can you save 4 bytes by returning 0 in case of a tie, instead of 'Tie'? \$\endgroup\$ Apr 23 '21 at 10:19
  • \$\begingroup\$ the check in place is for whether the first letter of the output is an alphabet, so I can change Tie to 'T' saving 3. \$\endgroup\$
    – Razetime
    Apr 23 '21 at 11:03
  • \$\begingroup\$ if numbers are allowed, that'd probabaly reduce a lot. \$\endgroup\$
    – Razetime
    Apr 23 '21 at 11:41
  • \$\begingroup\$ @Razetime Numbers are definitely allowed. I used a number encoding for my J answer. \$\endgroup\$
    – Jonah
    Apr 25 '21 at 21:56
3
\$\begingroup\$

J, 116 bytes

g=.1#.,@]
f=._3 g@{[:,/]((*0&=),:[(]]`]`(2*[)`[@.(|@g*4>|@g)(*0&~:))](%|)@|.~0j_1+.@*(*4>|)@g)/^:a:@,:]{:@,:0,~0{,^3~:,

Try it online!

Will try to add explanation later. The concept is more elegant than the J itself for this one.

\$\endgroup\$
2
\$\begingroup\$

Python 3, 221 bytes

def f(g,*a):x,y,a,b,s=a or[0,0,1,0,[]];c=g[y][x];k=(c=="#")+1;a,b=c in".#"and(a,b)or[(1,0),(0,1),(-1,0),(0,-1)][">v<".find(c)];return"T"if(x,y)in s else c in"AB"and c or f(g,(x+a*k)%len(g[0]),(y+b*k)%len(g),a,b,s+[(x,y)])

Try it online!

Perfectly ties Redwolf's JS, by pure coincidence, lol. This could probably be shortened a lot.

\$\endgroup\$
2
\$\begingroup\$

AWK, 267 258 bytes

R=NR,C=NF{for(j=0;k=$++j;v=v?v:k)b[R][j]=k!="."?k:0}END{c=d=f=1;a["^"]=-3;a["v"]=3;a[">"]=4;a["<"]=-4;s["A"]=s["B"]=1;for(s[1]--;y=="#"||!s[v];z=s[v=b[d][f]]>0?v:"tie"){y=="#"?0:w=a[v]?g=c=a[v]:b[d][f]=1;d=(d+=g%2)?d>R?0:d:R;f=(f+=c%3)?f>C?0:f:C;y=v}print z}

Try it online!

I thought the state machine properties of AWK would help make this shorter, but this particular approach probably won't get much smaller then this...

The first clause reads in the board... The board definitions expected are as listed in the description, with spaces between each character on the board.

R=NR,C=NF{ ... }

Each time a record is read in, R (the max rows) is set to the line number and C (the max columns) is set to the number of blank delimited fields. Those are use for the wrapping code later.

for(j=0;k=$++j;v=v?v:k)b[R][j]=k!="."?k:0

The for loop does a couple of things, primarily it sets elements of a two dimensional array b to either the character in the board cell or 0 if the input character was ..

The v=v?v:k bit at the end the loop just sets v to the first character in the board (the top left position).

END{ ... }

On EOF, meaning once the whole board has been read in, the END clause runs the simulation to find the answer.

c=d=f=1;a["^"]=-3;a["v"]=3;a[">"]=4;a["<"]=-4;s["A"]=s["B"]=1;

This long mess is just initiallization I couldn't find a way to shorten. The a array is used to compute what deltas should be applied to the current row and column for a given character. And the s array is used to recognize stop conditions.

for(s[1]--;y=="#"||!s[v];z=s[v=b[d][f]]>0?v:"tie"){ ... }

This inner loop does whatever one "command" implies, stopping when the s value of the current board position is A or B or a number greater than 0 (meaning we've been here more than once). The # test is to make sure the code will ignore the current cell is the previous character was the "skip the next character" command.

The body of the loop is several statement. It should be possibly be combined into one with more ternary nesting, but I gave up after hitting my deadend limit. :)

y=="#"?0:w=a[v]?g=c=a[v]:b[d][f]=1

Speaking of nested ternaries... This statement short circuits and does nothing if we're supposed to skip the cell, when the previous command was #.

Otherwise if the current command implies a change in direction (the a check), the code uses the mapped value for this command in the a directory to set new row and column deltas.

The "else" logic after that, is b[d][f]=1, which sets the current cell to a value that will trigger the "we've been here" check and exit the loop if we come back to this spot on the board.

d=(d+=g%2)?d>R?0:d:R;
f=(f+=c%3)?f>C?0:f:C;

These two statements adjust the row and column positions respectively using the offsets associated with the current command, wrapping if the values are too big or too small. The %2 operation gives the row change (-1, 0, 1) and the %3 operation gives the column change, also (-1, 0, 1).

y=v

And lastly, we have to save the current command in order to skip the next character is this command it #.

print z

When the loop exits z will either be A, B or tie.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.