Do a BackFlip for ais523!

Question

^{This challenge is a prize for ais523 for winning the "Rookie of the Year" category in "Best of PPCG 2016". Congratulations!}

---

BackFlip is an esoteric programming language made by user ais523, who has created well over 30 other interesting esolangs.

BackFlip is a 2D language like Befunge or ><> where the instruction pointer traverses a grid of text (the program), moving up, down, left, and right, changing direction depending on the character it's on. Critically, the grid in a BackFlip program changes as it is being traversed, a bit like Langton's Ant.

For this challenge you may assume that a BackFlip program is always a rectangular grid of text (all lines the same length), 1×1 in size at minimum, only containing the characters ./\<>^V. (. is used for visibility rather than space.) Semantically the BackFlip we'll use here is identical to the original spec.

The instruction pointer (IP) in BackFlip always starts just left of the top-left corner of the program, heading right. There are three types of commands it can encounter:

1. . is a no-op. The IP continues on in the direction it was going. The no-op stays a no-op.

2. / and \ are mirrors. They reflect the IP in the direction indicated by their angle, then they change into the other type of mirror.

   • For example, if the IP heads left into a \, it starts moving upward instead of left and the \ becomes a /.

3. <, >, ^, and V are arrows. They redirect the IP to the direction they point in, then they change into an arrow that points in the direction the IP came from (opposite the direction the IP was moving).

   • For example, if the IP heads downward into >, it starts moving right instead of downwards and the > becomes a ^ because that is the direction the IP came from.

A BackFlip program terminates when the IP moves out of bounds, i.e. goes off the grid. It turns out all BackFlip programs eventually end because infinite loops are impossible. (You may assume this is true.)

Your goal in this challenge is to write a program or function that takes in a BackFlip program and outputs the number of moves the instruction pointer takes before the program terminates. That is, how many steps does the IP take in the course of running a program? This includes the initial step onto the grid and the final step off of it.

For example, the instruction pointer takes 5 steps in the trivial grid ....:

 ....  <- empty 4×1 grid
012345 <- step number of the IP

So the output to .... is 5.

In the more complex 4×2 grid

\...
\.><

the IP exits the grid on its 9th step, so the output is 9:

step  grid  IP position (@)
0     \...  @....
      \.><   ....

1     \...   @...
      \.><   ....

2     /...   ....
      \.><   @...

3     /...   ....
      /.><   .@..

4     /...   ....
      /.><   ..@.

5     /...   ....
      /.<<   ...@

6     /...   ....
      /.<<   ..@.

7     /...   ....
      /.><   .@..

8     /...   ....
      /.><   @...

9     /...   ....
      \.><   ....
             @

The shortest code in bytes wins.

You may take input as an array of lines or matrix of characters instead of a multiline string if desired, but you must use the characters ./\<>^V (not integer opcodes). You may use space instead of . if preferred. It's fine if characters like \ need to be escaped in input. Output is always an integer more than one.

Test Cases

....
5

\...
\.><
9

.
2

..
3

.
.
2

\
2

^
2

.^.
3

<.
2

\\
\/
7

>V
^<
6

>\
>/
6

\><
2

\><
\><
7

\><
\><
\><
12

\.V.
\.\<
5

\.V.
\./<
9

V./\
V./\
>./<
..\/
14

\V..
.^..
\/><
.V..
.^..
20

\.V.V.
\./.\<
.>\<..
..^.^.
31

\.V.V.V.
\./>/.\<
.>\>\<..
..^.^.^.
69

\.V.V.V.V.
\./>/>/.\<
.>\>\>\<..
..^.^.^.^.
145

\.V.V.V.V.V.V.V.V.V.V.
\./>/>/>/>/>/>/>/>/.\<
.>\>\>\>\>\>\>\>\>\<..
..^.^.^.^.^.^.^.^.^.^.
9721

Answer 1

JavaScript (ES6), 158 bytes

f=(a,x=0,y=0,d=3)=>a[x]&&(c=a[x][y])?(a[x][y]=c=='.'?c:c=='/'?(d^=3,'\\'):c=='\\'?(d^=1,'/'):'v>^<'[d][d='^<v>'.search(c),0],f(a,d<3?x+d-1:x,d?y+d-2:y,d)+1):1

Developed independently from @tsh's answer although strikingly similar.

The mapping of directions ^<v> to integers 0-3 is governed by the fact that .search('^') returns 0 since ^ is a regexp metacharacter.

Answer 2

Haskell, 333 325 bytes

EDIT:

• -8 bytes: Made f pointfree and merged into b.

b takes a list of Strings and returns an Integer.

data C a=C{c::a->(a,C a)}
b g=[0,0]#([0,1],map(maybe(C$m 1)C.(`lookup`zip"./^>V<"[n,m(-1),a[-1,0],a[0,1],a[1,0],a[0,-1]]))<$>g)
[y,x]#(d,g)|g&y||g!!0&x=1|n@([f,e],_)<-(($d).c)?x?y$g=1+[y+f,x+e]#n
l&i=i<0||i>=length l
(f?i)l|(p,a:r)<-splitAt i l=(p++).(:r)<$>f a
n d=(d,C n)
a v d=(v,C$a$(0-)<$>d)
m s[d,e]=([s*e,s*d],C$m(-s))

Try it online!

How it works

• C a is a data type used because Haskell won't allow a type to be recursive without declaring it explicitly. C is also a wrapping constructor and c is its corresponding unwrapping function. It is only used with a=[Int].
  • The type C [Int] represents a cell command, as a function that takes a direction ([Int]) argument, and returns a pair of a new direction, and a new C [Int] value.
• b is the main function. It converts each character into a C value, then it calls #.
  • g is the grid as a list of strings.
  • Since \ needs to be escaped and so is the longest character to mention, its result is instead used as the default value for the list lookup.
• # runs the main simulation, checking bounds with & and generating new grids with ?. [y,x] is the current position, d the current direction, and g the current grid. [f,e] is the next direction, and n is a pair of it and the next grid.
• l&i checks if the index i is out of bounds for the list l. (It returns True for out of bounds, since that avoids a dummy guard condition in #.)
• When f(l!!i)==(d,x), (f?i)l==(d,m) where m is the list l with the ith element replaced with x.
  • Technically (?i) is a more general lens, focusing on the i'th element of a list, in this case used with the (,) [Int] functor instance.
• n is the function representing a dot.
• a v is a function representing an arrow in direction v.
• m s is a function representing a mirror; s==1 for \\ and s==-1 for /.

Answer 3

Python 3, 286 bytes

[f() takes input in the form of {(0,0):'/',(0,1):'.'} so I have also written a function g() for converting an array of lines to that form]

def f(r):
 x=y=0;d='>';s=1
 while 1:
  try:c=r[y,x];m='>^<V'.find(d)
  except:break
  if(c=="\\"):d='V<^>'[m];r[y,x]="/"
  elif(c=="/"):d='^>V<'[m];r[y,x]="\\"
  elif(c!="."):r[y,x]='<V>^'[m];d=c
  x+=1if(d=='>')else-1if(d=='<')else 0;y+=1if(d=='V')else-1if(d=='^')else 0;s+=1
 return s

Try it online!

Answer 4

JavaScript, 172 bytes

f=(a,d=3,x=0,y=0,n=1)=>(p=a[y]||[],q=p[x])?(p[x]=~(t='^<V>'.indexOf(q))?'^<V>'[d^2]:q=='/'?(t=3-d,'\\'):q=='\\'?(t=d^1,'/'):(t=d,q),f(a,t,x+(t&1&&t-2),y+(~t&1&&t-1),n+1)):n

But i cannot test last testcase since i got stack overflow on my machine. (should work if there is a machine with larger ram)

We use a number for direction:

• 0: ^
• 1: <
• 2: V
• 3: >

Let d be the direction number...

• if we meet a '/', we need d = 3 - d;
• if we meet a '\' we need d = d ^ 1;
• if we meet a '^<V>' we need d = '^<V>'.indexOf(note)

Let (x, y) be current position, the next position is: x+(t&1&&t-2), y+(~t&1&&t-1)

Note:

The function takes one paramter with the following format:

[ [ '\\', '.', 'V', '.', 'V', '.', 'V', '.', 'V', '.' ],
  [ '\\', '.', '/', '>', '/', '>', '/', '.', '\\', '<' ],
  [ '.', '>', '\\', '>', '\\', '>', '\\', '<', '.', '.' ],
  [ '.', '.', '^', '.', '^', '.', '^', '.', '^', '.' ] ]

Test it here

f=(a,d=3,x=0,y=0,n=1)=>(p=a[y]||[],q=p[x])?(p[x]=~(t='^<V>'.indexOf(q))?'^<V>'[d^2]:q=='/'?(t=3-d,'\\'):q=='\\'?(t=d^1,'/'):(t=d,q),f(a,t,x+(t&1&&t-2),y+(~t&1&&t-1),n+1)):n

    ;k=x=>x.split('\n').map(t=>t.split(''));

<textarea id=v>\.V.V.V.V.
\./>/>/.\<
.>\>\>\<..
..^.^.^.^.</textarea><br/><button onclick="r.textContent=f(k(v.value))">Solve</button>
<p>Result: <output id=r></output></p>

Answer 5

C, 232 221 bytes

d,n,t,m[4]={1,-1};char*w="><^V/\\.",*P;main(o,v)char**v;{for(P=v[1],m[2]=-(m[3]=strchr(P,10)-P+1);P>=v[1]&&P<strchr(v[1],0)&&*P^10;++n)*P=w[((o=d,t=strchr(w,*P)-w)<4)?d=t,o^1:(t<6)?d^=t-2,9-t:6],P+=m[d];printf("%d",n+1);}

Takes input in first argument, prints result. Requires that input contains at least 1 newline (so if there's only 1 row, it must end with a newline)

Example usage:

./backflip '....
';

Breakdown:

d,                                          // Direction
n,                                          // Step counter
t,
m[4]={1,-1};                                // Movement offsets
char*w="><^V/\\.",                          // Command lookup
*P;                                         // Cursor location
main(o,v)char**v;{
    for(P=v[1],                             // Begin at 0,0
        m[2]=-(m[3]=strchr(P,10)-P+1);      // Find width of grid
        P>=v[1]&&P<strchr(v[1],0)&&*P^10;   // While inside grid:
        ++n)                                //  Increment step
        *P=w[                               //  Update the current cell
            ((o=d,t=strchr(w,*P)-w)         //  (store current direction & command)
              <4)?d=t,o^1:                  //   If <>^V, write backflip & set dir
            (t<6)?d^=t-2,9-t:               //   If / or \, write flip & bounce
            6],                             //   If ., write unchanged & continue
        P+=m[d];                            //  Move
    printf("%d",n+1);                       // Print result
}