30
\$\begingroup\$

Super Mario Galaxy features two rhombicuboctahedron-shaped* planets tiled with platforms that shrink as Mario runs across. Should Mario fall into a triangular hole or a gap left by a tile he previously touched, he will be consumed by the black hole at the core. (Watch: Hurry-Scurry Galaxy, Sea Slide Galaxy)

Image: MarioWiki.com

Image: MarioWiki.com

(You can think of the planet as a 2x2x2 cube whose faces have been detached and connected to each other by 2x3 "bridges".)

Unfortunately, since my controller is very broken, Mario cannot jump and is limited to the four cardinal directions. Additionally, Mario moves very slowly and cannot retrace even one step without first having the platform behind him disappear.

Let's assume the camera is always above Mario's head and he starts at the bottom right of a 2x2 face:

      ■ ■
      ■ ■
      ■ ■
■ ■ ■ ■ ■ ■ ■ ■
■ ■ ■ ■ M ■ ■ ■
      ■ ■
      ■ ■
      ■ ■

Your program will take a list or string of directions, U D L R (up, down, left, right), representing Mario's walk around the planet so far as a series of steps. The program can output one of two distinct outputs: one representing that Mario is still alive and walking, and the other representing that somewhere along his walk, Mario has fallen into the Shrinking Satellite.

RR:   ■ ■                 RRD:  ■ ■                 RRL:  ■ ■      
      ■ ■                       ■ ■                       ■ ■      
      ■ ■                       ■ ■                       ■ ■      
■ ■ ■ ■ ■ ■ ■ ■           ■ ■ ■ ■ ■ ■ ■ ■           ■ ■ ■ ■ ■ ■ ■ ■
■ ■ ■ ■ □ □ M ■           ■ ■ ■ ■ □ □ □ ■           ■ ■ ■ ■ □ M □ ■
      ■ ■    \                  ■ ■   M                   ■ ■  \
      ■ ■     Let's-a go!       ■ ■    \                  ■ ■   W-aaaaaaaaaahh!
      ■ ■                       ■ ■     W-aaaaaaaaaahh!   ■ ■

Of course, unlike the above diagrams, you'll have to take the 3D into account. Here's a diagram that might help you visualize the scenario better:

                Top 2x2 face
   <- clockwise           anticlockwise ->
   -   ■    -    ■    -    ■    -    ■   -
     /   \     /   \     /   \     /   \  
   ■       ■ ■       ■ ■       ■ ■       ■
   ■       ■ ■       ■ ■       ■ ■       ■
   ■       ■ ■       ■ ■       ■ ■       ■
   ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■    Left and right
   ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ M ■ ■ ■ ■ ■ ■ ■ ■ ■    edges wrap around.
   ■       ■ ■       ■ ■       ■ ■       ■
   ■       ■ ■       ■ ■       ■ ■       ■
   ■       ■ ■       ■ ■       ■ ■       ■
     \   /     \   /     \   /     \   /  
   -   ■    -    ■    -    ■    -    ■   -
   <- anticlockwise           clockwise ->
               Bottom 2x2 face

So according to this diagram, UUUUURRRR might look like this:

   -   ■    -    ■    -    □    -    ■   -
     /   \     /   \     /   \     /   \  
   ■       ■ ■       ■ □       □ ■       ■
   ■       ■ ■       ■ □       □ ■       ■
   ■       ■ ■       ■ □       □ ■       ■
   ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ □ ■ ■ ■ M ■ ■ ■ ■ ■
   ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ □ ■ ■ ■ ■ ■ ■ ■ ■ ■
   ■       ■ ■       ■ ■       ■ ■       ■
   ■       ■ ■       ■ ■       ■ ■       ■
   ■       ■ ■       ■ ■       ■ ■       ■
     \   /     \   /     \   /     \   /  
   -   ■    -    ■    -    ■    -    ■   -

And UUUUUUUUULURRRRRR might look like this:

   -   ■    -    ■    -    □    -    □   -
     /   \     /   \     /   \     /   \  
   ■       ■ ■       ■ □       ■ ■       □
   ■       ■ ■       ■ □       ■ ■       □
-> □       ■ ■       ■ □       ■ ■       □ ->
<- □ ■ ■ ■ ■ ■ ■ ■ ■ ■ □ ■ ■ ■ M □ □ □ □ □ <-
   ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ □ ■ ■ ■ ■ ■ ■ ■ ■ ■
   ■       ■ ■       ■ ■       ■ ■       ■
   ■       ■ ■       ■ ■       ■ ■       ■
   ■       ■ ■       ■ ■       ■ ■       ■
     \   /     \   /     \   /     \   /  
   -   ■    -    ■    -    ■    -    ■   -

May the shortest program in bytes w-aaaaaaaaaahh!

Test Cases

Output 1: Still Alive

DDDDDLUUUUU - Mario walks across a bridge and back.

RRRRDDDDLLL - Mario walks in a triangle.

LLLLLLUUUUUURRRRR - Mario walks in a bigger triangle.

ULLDRDDDRU - Mario puts himself in peril.

RURDRURDRDLDRDLDLDLULDLLLLLLLLLLLLLLLLURRRRRRRRRRRRRR - Mario takes an unconventional route... and puts himself in peril.

Mario crosses every tile exactly once. DDDDLUUUULLLLDDDLUUULLLLDDDDLUUUULLLLDDDLUUULLLURRRUUURDDDRRRRUUURDDDRRRRUUURDDDRRRRUUUUURDDDDD DLDRDLDLLLDRRRDDDDLLLLLLLLLDRRRRRRRRRDDDDLLLDRRRDDDRUUURRRRULLLLUUUURRRULLLUUUUURDRURDRUURULURU

Output 2: W-aaaaaaaaaahh!

LLR - Mario attempts to retrace a step and falls off.

UULDR - Mario attempts to cross a tile twice and steps into air.

RRDDDDD - Mario walks off a bridge at the first D (ignore any following steps).

RRRRDDDDLLLL - Mario walks in a triangle and falls through the starting tile.

LLLLLLUUUUUURRRRRR - Mario walks in a bigger triangle and falls through the starting tile.

UUUUUUUUUUUUUUUUUUUU - Mario walks all the way around the planet and falls through the starting tile.

RURDRURDRDLDRDLDLDLULDLLUU - Mario takes an unconventional route and becomes disoriented.

Mario, realizing the peril he is in, is left with no choice.

ULLDRDDDRUUU ULLDRDDDRUUL ULLDRDDDRUUR ULLDRDDDRUUD RURDRURDRDLDRDLDLDLULDLLLLLLLLLLLLLLLLURRRRRRRRRRRRRRR RURDRURDRDLDRDLDLDLULDLLLLLLLLLLLLLLLLURRRRRRRRRRRRRRU RURDRURDRDLDRDLDLDLULDLLLLLLLLLLLLLLLLURRRRRRRRRRRRRRL RURDRURDRDLDRDLDLDLULDLLLLLLLLLLLLLLLLURRRRRRRRRRRRRRD

Finally, copy any test case from "Mario crosses every tile exactly once" and change or add one step at random. Mario should fall. (If you add a step to the end, Mario falls to grab the Power Star!)

*Cantellated cube would be a more correct term as some faces aren't square, but you've got to admit - "rhombicuboctahedron" flows nicer.

\$\endgroup\$
  • 7
    \$\begingroup\$ Bonus points for solving this in Cubix or Cubically \$\endgroup\$ – Stephen Aug 2 '17 at 22:44
  • 1
    \$\begingroup\$ This brings back so many memories of playing Mario Galaxy - easily one of my favorite games of all time. \$\endgroup\$ – notjagan Aug 2 '17 at 22:45
  • 9
    \$\begingroup\$ @StepHen Or MarioLANG :P \$\endgroup\$ – ETHproductions Aug 3 '17 at 0:51
  • \$\begingroup\$ @Stephen even though it's an octogon, hexagony sti... Y'know what, never mind, who'd do this in hexAgony. \$\endgroup\$ – Magic Octopus Urn Aug 3 '17 at 19:04
  • \$\begingroup\$ In the 4th from last test case, Mario doesn't die unless you add an extra R. I have worked this out on paper to be sure my code is correct. \$\endgroup\$ – Level River St Aug 7 '17 at 12:15
6
\$\begingroup\$

Ruby, golfed, 244 230 bytes

Seems to work fine, will test a bit more.

->s{a=[8**8/5]*8
v=[-1,x=d=0,1,0]
y=m=4
s.chars{|c|a[y]&=~(1<<x) 
y+=v[e="URDL".index(c)+d&3]
x+=v[e-1]
r= ~0**q=x/4
i=q+x&1
j=q+y&1
y%9>7&&(y=4-i;x+=4-j*11-x%2;d+=r)
x&2>0&&-y/2==-2&&(y=i*7;x+=6-x%2*9+j;d-=r)
m*=1&a[y]>>x%=24}
m}

Ruby, first working version, 260 bytes

Try it online

Lambda function taking a string argument. Returns 4 for alive, 0 for dead.

->s{a=[0x333333]*8
v=[0,-1,0,1]
x=d=0
y=m=4
s.chars{|c|a[y]&=~(1<<x) 
e="URDL".index(c)+d
x+=v[e%4]
y+=v[-~e%4]
p=x&-2
q=x/4%2
y%9>7&&(d-=q*2-1;y,x=4-(q+x)%2,(p+4-(q+y)%2*11)%24)
x&2>0&&-y/2==-2&&(y,x=(q+x)%2*7,(p+6-x%2*8+(q+y)%2)%24;d+=q*2-1)
m*=a[y]>>x&1}
m}

Explanation

The board is unfolded into 6 strips of size 2x8, represented by the /\ and O characters below. These are mapped onto a 24*8 2D map, where x=(strip number)*4+(horizontal position on strip) and y=vertical position on strip.

       Map        4         2         0          Initial state of array a
                 /         /         /   
                / /       / /       / /          1100110011001100110011
               / /       / /       / /           1100110011001100110011 
              O /       O /       O /            1100110011001100110011
             O O       O O       O O             1100110011001100110011
      \     / O \     / O \     / X              110011001100110011001X
     \ \   / / \ \   / / \ \   / /               1100110011001100110011
      \ \ / /   \ \ / /   \ \ / /                1100110011001100110011
       \ O /     \ O /     \ O /                 1100110011001100110011
        O O       O O       O O 
         O \       O \       O \                 X=Mario's start point 
          \ \       \ \       \ \  
           \ \       \ \       \ \    
            \         \         \
             5         3         1

These are stored in an array of 8 binary numbers, so x increases going left and y increases going down.

The array is intialized with 8 copies of the number 0x33333333. This forms the squares Mario is allowed to step on. As Mario moves around the square he is on is set to zero, and the square he is moving to is tested - he lives it contains a 1, and dies if it contains a 0.

If Mario walks off the top or bottom of the strip he is on, he moves to another strip. If he walks off the side of the strip he is on, if he is on a square with y=3 or y=4 he moves to another strip. If y is not 3 or 4, he does not move to another strip and ends up on a square which had 0 in it from the outset of the game, so he dies.

Because the camera is always above Mario's head, whenever Mario changes strip, the reference for the directions must be rotated by 90 degrees.

Ungolfed in test program

f=->s{                             #Move sequence is taken as string argument s.
  a=[0x333333]*8                   #Setup board as an array of 8 copies of 1100110011001100110011.
  v=[0,-1,0,1]                     #Displacements for moving.
  x=d=0                            #Mario starts at 0,4.
  y=m=4                            #d=offset for directions. m=4 when Mario is alive (value chosen for golfing reasons) 0 when dead.

  s.chars{|c|                      #For each character c in s
    a[y]&=~(1<<x)                  #Set the square where Mario is to 0.

    e="URDL".index(c)+d            #Decode the letter and add the offset 
    x+=v[e%4]                      #x movement direction is v[e%4]   
    y+=v[-~e%4]                    #y movement direction is v[(e+1)%4]
    p=x&-2                         #p is a copy of x with the last bit set to zero (righthand edge of strip).
    q=x/4%2                        #q is 0 for an even number strip, 1 for an odd number strip.
    y%9>7&&(                       #If y out of bounds (8 or -1)
      d-=q*2-1;                    #Adjust d so directions will be interpreted correctly on the next move.
      y,x=
        4-(q+x)%2,                 #y becomes 3 or 4 depending on the values of q and x.
        (p+4-(q+y)%2*11)%24        #If q+y is even, move 1 strip left. if even, move 2 strips right. Take x%24.  
    )
    x&2>0&&-y/2==-2&&(             #If x&2>0 Mario has walked sideways off a strip. If y is 3 or 4, move him to a different strip.
      y,x=                       
        (q+x)%2*7,                 #y becomes 0 or 7, depending on the values of q and x.
        (p+6-x%2*8+(q+y)%2)%24;    #If x%2 is even, move 2 strips left. If odd, move 1 strip right*. Pick the left or right column of the strip depending on (q+y)%2. Take x%24 
        d+=q*2-1                   #Adjust d so directions will be interpreted correctly on the next move.
    )

    m*=a[y]>>x&1                   #Multiply m by the value (0 or 1) of the current square. Mario is either alive (4) or dead (0).  
    #puts x,y,m,a.map{|i|"%022b"%i}#Uncomment this line for diagnostics.
  }
m}                                 #Return value of m.  


#Still alive, return value 4
puts f["DDDDDLUUUUU"] # Mario walks across a bridge and back.
puts f["RRRRDDDDLLL"] # Mario walks in a triangle.
puts f["LLLLLLUUUUUURRRRR"] # Mario walks in a bigger triangle.
puts f["ULLDRDDDRU"] # Mario puts himself in peril.
puts f["RURDRURDRDLDRDLDLDLULDLLLLLLLLLLLLLLLLURRRRRRRRRRRRR"] # Mario takes an unconventional route... and puts himself in peril.
puts f["DDDDLUUUULLLLDDDLUUULLLLDDDDLUUUULLLLDDDLUUULLLURRRUUURDDDRRRRUUURDDDRRRRUUURDDDRRRRUUUUURDDDDD"] 
puts f["DLDRDLDLLLDRRRDDDDLLLLLLLLLDRRRRRRRRRDDDDLLLDRRRDDDRUUURRRRULLLLUUUURRRULLLUUUUURDRURDRUURULURU"]

#Dead, return value 0

puts f["LLR"] #  Mario attempts to retrace a step and falls off.
puts f["UULDR"] #  Mario attempts to cross a tile twice and steps into air.
puts f["RRDDDDD"] #  Mario walks off a bridge at the first D (ignore any following steps).
puts f["RRRRDDDDLLLL"] #  Mario walks in a triangle and falls through the starting tile.
puts f["LLLLLLUUUUUURRRRRR"] #  Mario walks in a bigger triangle and falls through the starting tile.
puts f["UUUUUUUUUUUUUUUUUUUU"] #  Mario walks all the way around the planet and falls through the starting tile.
puts f["RURDRURDRDLDRDLDLDLULDLLUU"] # 

puts f["ULLDRDDDRUUU"] 
puts f["ULLDRDDDRUUL"] 
puts f["ULLDRDDDRUUR"] 
puts f["ULLDRDDDRUUD"] 
puts f["RURDRURDRDLDRDLDLDLULDLLLLLLLLLLLLLLLLURRRRRRRRRRRRRRR"] #text case in q is wrong. one more R added to make the kill.
puts f["RURDRURDRDLDRDLDLDLULDLLLLLLLLLLLLLLLLURRRRRRRRRRRRRU"] 
puts f["RURDRURDRDLDRDLDLDLULDLLLLLLLLLLLLLLLLURRRRRRRRRRRRRL"] 
puts f["RURDRURDRDLDRDLDLDLULDLLLLLLLLLLLLLLLLURRRRRRRRRRRRRD"]
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Nicely done! I really like the "strip" mapping and the way you accounted for the camera angle. \$\endgroup\$ – darrylyeo Aug 8 '17 at 14:55
5
+200
\$\begingroup\$

APL (Dyalog), 457 441 bytes (Classic Dyalog Character Set)

r←'RULD'
S←{(r⍳⍵)⌷4 4⍴2 3 4 1 4 3 1 2 4,(⍳3),3 4 2 1}
C←{(⊂⍺)⌷⍵}
P←,⍉0 1 2 3∘.{2 4 1 3(C⍨⍣⍺)⍵}(⊂⍳4),C\S¨'LUULU'
v←6 6⍴(3⍴0),2(⊥⍣¯1)4512674568
a←1 4 4
N←{s y x←⍵+0,(r⍳⍺)⌷4 2⍴0 1 ¯1 0 0 ¯1 1 0
t Y X←⊃(1+(7<y+x)(0<y-x))⌷2 2⍴('U'5 0)('L'0 5)('R'0 ¯5)('D'¯5 0)
⊃(1+(1+y x)⌷(¯2⊖¯2⌽8 8↑4 4⍴1)∨¯1⊖¯1⌽8 8↑v)⌷((P⍳⊂(⊃s⌷P)C(S t)),(Y X+y x))(s y x)}
M←{T←24 6 6⍴0
~∨/,0>(6 6 6⍴v)-+/[2]6 4 6 6⍴↑(24⍴⍳4){{⊖⍉⍵}⍣⍺⊢⍵}¨⊂[2 3]T⊣{T[⊂⍵]+←1}¨(⊂a),{⊃N/(⌽⍵),⊂a}¨,\⍵}

Thanks, Bubbler, for helping me shave off several bytes!

Try it online!

To see how this works, let's learn some group theory! First, observe that the entire cuboid structure can be realized as the following shape, tessellated onto the six faces of a cube.

      .
    . .
. . . . .
  . . . . .
    . .
    .

Now, in our case, I won't be using just six faces. Because Mario's position doesn't just depend on which face he's on; it also depends on his current orientation (i.e. the direction he's facing). So I'll be using 24 states to represent his current state (24 = 6 faces × 4 orientations). Since this is APL, we'll do the calculation in a massive array. Specifically, we'll use a 24×6×6 array to store every position Mario steps on, and how many times he's been there. So Mario's position at a given moment with be a 3-vector s y x, where s is the cuboid state (face times orientation) and y, x are the coordinates within that face.

Now, if Mario is in the middle of a face, then when he moves we simply update the position vector accordingly. So a movement U (up) would add 0 ¯1 0 to his position. A movement R (right) would add 0 0 1, etc., etc.

The tricky case comes into play when Mario is at an edge. So if we're here

      M
    . .
. . . . .
  . . . . .
    . .
    .

and we move up, what do we do? We end up moving four down (effectively wrapping around) and to some other cuboid state. So if we started as s y x, our new position will be t (y + 4) x. But what is t? To figure that out, we need to look at rotations of a cube.

As I already mentioned, there are 24 rotations of a cube. Let's try to represent the vertices of a cube numerically.

  5--6
 /| /|
1--2 |
| 7|-8
|/ |/
3--4

Okay, neat. But that's not all of the information we have. In particular, any rotation of a cube will take opposite vertices to opposite vertices. So, in the above diagram, 1 and 8 are at opposite sides. No matter which way I rotate this cube, 1 and 8 will still be opposites. So we really only have four points we care about, as the other four can be calculates from those.

  4--3
 /| /|
1--2 |
| 2|-1
|/ |/
3--4

As it turns out, this is all of the information we need. If we look at the cube head-on so that the above cube looks like

1--2
|  |
|  |
3--4

Then every permutation of those four points is a rotation of the cube, and every rotation of the cube can be represented as a permutation of those four points. You can read more about that on Wikipedia, but the basic idea is that rotations of the cube can be represented using the symmetric group S4, which has 24 elements. We'll represent it this way, since APL has some nice built-in functions to apply permutations.

Now, how does this help us? Well, we wanted to know, given a state s and a side of the screen we went off (say, to the right, for this example), what is our new state t? If we can enumerate the 24 elements of S4 in a nice order, then s is simply some element of that enumeration. Then we figure out what the permutation for "go off the screen to the right" is, and compose the two to get t. So, if our cube is

  5--6
 /| /|
1--2 |
| 7|-8
|/ |/
3--4

Then, if we go off the screen to the right, we rotate the cube so the face Mario is now on is facing frontward. We get

  1--5
 /| /|
2--6 |
| 3|-7
|/ |/
4--8

Remember that we're identifying opposite vertices, so

  1--4
 /| /|
2--3 |
| 3|-2
|/ |/
4--1

Looking from the front, we turned a 1 2 3 4 cube into a 2 3 4 1 cube. So our permutation group element is 2 3 4 1. This works whenever we move right. If we take our current cuboid state (which is an element of S4), and compose it with 2 3 4 1, we get the new state. A pencil and a bit of effort, and we can calculate the element of S4 representing right, up, left, and down movements.

Right 2 3 4 1
Up    4 3 1 2
Left  4 1 2 3
Down  3 4 2 1
*     2 4 1 3

That last one (with the *) is a rotation of the current face that doesn't change which face Mario is on. So it corresponds to Mario just facing a different direction without walking. In the problem statement, it's not possible for Mario to do that, but we'll need that permutation later for our calculations.

Alright, that should be all the background we need. Let's dig into the code.

r←'RULD'

Nothing to see here. We use the string 'RULD' a few times, so it saves us a couple characters to store it.

S←{(r⍳⍵)⌷4 4⍴2 3 4 1 4 3 1 2 4,(⍳3),3 4 2 1}

S is the function which takes R, U, L, or D and converts it to the corresponding permutation we found above.

C←{(⊂⍺)⌷⍵}

Like I mentioned earlier, APL has nice built-ins for applying permutations. C composes two elements of S4. This is how we model multiple steps, like "go right, then go right again".

P←,⍉0 1 2 3∘.{2 4 1 3(C⍨⍣⍺)⍵}(⊂⍳4),C\S¨'LUULU'

P consists of all permutations of 1 2 3 4, i.e. all elements of the group S4. Let's break it down.

(⊂⍳4),C\S¨'LUULU'

From the starting orientation, LUULU will visit each face of the cube exactly once. So the above expression consists of one permutation representing each face of the cube, ignoring rotations for the moment. We manually tack on the identity 1 2 3 4, which is our starting state.

{2 4 1 3(C⍨⍣⍺)⍵}

I mentioned earlier that 2 4 1 3 corresponds to Mario turning his head 90 degrees. We have each face, so we'll want to rotate the faces to get every possible state. This function rotates a face once.

0 1 2 3∘.{2 4 1 3(C⍨⍣⍺)⍵}(⊂⍳4),C\S¨'LUULU'

Now we rotate every face zero times, once, twice, and thrice, to get every possible permutation.

,⍉0 1 2 3∘.{2 4 1 3(C⍨⍣⍺)⍵}(⊂⍳4),C\S¨'LUULU'

will transpose the result, which gives us the permutations in a nice order (namely, every cube is represented contiguously, by its four rotations in a sequence in the array). Then we ravel , the array to get one nice, flat vector of vectors.

v←6 6⍴(3⍴0),2(⊥⍣¯1)4512674568

v is a representation of the below valid positions grid, encoded in base 10 for compactness.

0 0 0 1 0 0
0 0 1 1 0 0
1 1 1 1 1 0
0 1 1 1 1 1
0 0 1 1 0 0
0 0 1 0 0 0

 

a←1 4 4

Mario's starting state. Again, we use this twice, so it's just barely shorter to assign it to a variable.

N←{...}

N is a big one. Given a direction (one of the letter RULD) and a position , this moves Mario in that direction. Remember, our position is a 3-vector s y x, so we'll be moving in 3-dimensional space, where the third dimension is our state space.

s y x←⍵+0,(r⍳⍺)⌷4 2⍴0 1 ¯1 0 0 ¯1 1 0

In the easy case, we simply shift y and x and leave s alone. This is fine as long as we don't run off the edge. If we don't, then s y x, as declared above, is the correct answer. If we do, then we need to do some more work.

2 2⍴('U'5 0)('L'0 5)('R'0 ¯5)('D'¯5 0)

On the other hand, if we do run off the edge, this tells us what we have to do. In the first case, we shift the cube up and move Mario down 5. In the second case, we shift the cube left and shift Mario to the right 5, and so on.

t Y X←⊃(1+(7<y+x)(0<y-x))⌷...

To figure out which case we're in, we draw two diagonal lines along the grid as follows

\     .   /
  \ . . /
. . \ / .
  . / \ . .
  / . . \
/   .     \

This partitions our grid space into four sections. The lines are determined by 7<y+x and 0<y-x. Then we look up our cases in the previous 2×2 array. Note that if we're in the easy case, then this calculation is pointless but ultimately harmless. We'll determine which case we're in next.

(¯2⊖¯2⌽8 8↑4 4⍴1)∨¯1⊖¯1⌽8 8↑v

This expression uses v above and produces the array below

0 0 0 0 0 0 0 0
0 0 0 0 1 0 0 0
0 0 1 1 1 1 0 0
0 1 1 1 1 1 0 0
0 0 1 1 1 1 1 0
0 0 1 1 1 1 0 0
0 0 0 1 0 0 0 0
0 0 0 0 0 0 0 0

Then, if Mario ends up on a 0, we need to change cuboid state. If not, then we're good. Note that I include a few "out of bounds" points here where there aren't platforms. This prevents Mario from warping to out of the array bounds if he walks off the edge.

(1+y x)⌷(...)

Look at Mario's position and see if it's a zero in the above array.

⊃(1+(1+y x)⌷(¯2⊖¯2⌽8 8↑4 4⍴1)∨¯1⊖¯1⌽8 8↑v)⌷(...)(s y x)

We use the above 0 or 1 to index into our two cases. If it's a 1, simply return s y x. If not, then we have more work to do.

(P⍳⊂(⊃s⌷P)C(S t)),(Y X+y x)

The Y and X coordinates are simply y x added to our shift amount we calculated earlier. As for the new cuboid state, we have our direction t. Then S t is the permutation, which we compose with our permutation for our current state ⊃s⌷P, then we convert the permutation back to an index in state space P⍳⊂.

M←{...}

Now, M is the final piece. It's the function that, given a sequence of inputs, actually determines whether or not Mario falls. It will return 1 on success and 0 if he falls off.

T←24 6 6⍴0

Our initial state is a 24×6×6 state space, consisting of all zeroes, since Mario hasn't been anywhere yet.

(⊂a),{⊃N/(⌽⍵),⊂a}¨,\⍵

Now we take all of the prefixes of our input (,\⍵) and we move Mario along those paths ({⊃N/(⌽⍵),⊂a}¨). Then we tack on the initial state ((⊂a),), since Mario clearly starts off by visiting the initial position. Now we have a vector of all of Mario's positions at every moment.

{T[⊂⍵]+←1}¨...

For each position Mario ever visits, go to that place in the array T and add one to it.

(24⍴⍳4){{⊖⍉⍵}⍣⍺⊢⍵}¨⊂[2 3]T

We have 24 faces on our "cube". In reality, our cube only has 6 faces. So it's time to account for which faces are rotations of which others. Remember, we enumerated our permutations earlier so that the first four states are rotations of one another, then the next four are rotations of one another, and so on. So we'll take T (a 24×6×6 array) and, along the first axis (state space), we rotate. We'll rotate the first 6×6 once, the second twice, the third three times, then four times, then once, then twice, and so on. The actual rotation is done by {⊖⍉⍵}, which is a transpose followed by a flip. This corresponds to a 90 degree rotation. Now everything is oriented correctly.

+/[2]6 4 6 6⍴↑...

Now that everything has the right orientation, we want to add together the faces that are actually the same. So reshape the array to a 6×4×6×6 (where the dimensions are, respectively: face, orientation, y, x). Then we sum along the second axis, which represents orientation, giving us a 6×6×6 array of all of the actual positions on the grid.

(6 6 6⍴v)-...

v tells us which positions Mario is allowed to visit. So we subtract the ones we actually visited from this. If we ever end up with a negative number, that means Mario either went somewhere he shouldn't have or he revisited the same space twice.

R←~∨/,0>...

See if any positions are less than zero. Then invert the result (since success means they're all greater than zero, and failure means there is one which is less).

And that's all there is to it. If you actually read this dissertation of mine, then congratulations! This is my first APL golf, so I'm sure there's room for improvement. But I enjoyed the opportunity to use a bit of math in my answer as well.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Do you have a reason using tradfn (-function) over dfn ({}-function) for the functions N and M? \$\endgroup\$ – Bubbler Jul 24 at 2:05
  • \$\begingroup\$ Not particularly. I started with tradfn's for everything, then converted everything that could be one-lined to dfn. Those two use, respectively, pattern matching and mutable state, which can't be put into one statement. So I just didn't bother converting them. \$\endgroup\$ – Silvio Mayolo Jul 24 at 2:23
  • 1
    \$\begingroup\$ They can be converted to dfns like this. After all, what you call "pattern matching" is just multi-assignment, and side effects can be used by chaining the statements with . Also, you can use the "footer" section to demonstrate the test cases to better show the score (or use "input" section, which works like the session for Dyalog APL). \$\endgroup\$ – Bubbler Jul 24 at 2:31
  • \$\begingroup\$ Thanks a lot! I'll update the answer. I only learned APL a few months ago, and I'm a Haskeller by trade, hence my terminology and jumping to calling it "pattern matching". Any advice is a huge help. \$\endgroup\$ – Silvio Mayolo Jul 24 at 2:49
  • \$\begingroup\$ If you haven't already, check out the chat room dedicated to APL, where we discuss golfing and general programming in APL and related languages. We have regular lessons on APL too. \$\endgroup\$ – Bubbler Jul 24 at 3:29

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.