Can Mario go to the end of this map

Question

Create a program that determines, given an input of the path, whether Mario can reach the end, denoted by E, from the start, denoted by S.

A path will look something like this:

S = E
=====

In a path, the various symbols and what they represent are:

• =: wall/floor/ceiling. Mario cannot walk through wall , and cannot fall past a floor, or jump past a ceiling (he would hit his head)
• (space): air. Mario can walk through this, and jump through it, and fall through it
• S: air, except showing where Mario starts. This will always appear in the left-most column of the input, at ground level.
• E: air, except showing where Mario wants to get. This will always appear in the right-most column of the input, at ground level.

The input will have spaces at every place where Mario could walk.

Mario can only move forward; in this example Mario cannot get to the goal

S
===

 ===
   E
====

nor can he in this one

    E
   ==
== 
  #==
==
   ==
==
S  ==
======

However, he can reach the space denoted by # (which will not appear in input), because he can jump up to four cells high; Mario is superhuman. As another example of his superhumanity:

S
=
=
=
=
=
= #
= =
=
=
=
=     E
=======

Mario can get to the E by falling the great distance, surviving, and walking calmly to E. Note that he cannot reach the #, because Mario falls straight down.

Mario can jump really high, but not very far forward by comparison.

S   E
== ==
 = =

Mario may attempt to jump the gap, but he will fail, and fall straight in. he cannot reach the end.

Mario can reach the goal in all of these examples:

 E
 =
 =
 =
S=
==

 =
 =   E
S=   =
==   =
 =   =
 =====

S
=






=  E
====

This is code golf, so fewest bytes wins!

Answer 1

Slip, 38 27 25 bytes

S>(`=<<`P{1,5}>`P>`P*)+#E

Requires input to be padded to a rectangle such that there are spaces in every cell Mario needs to traverse (potentially with a leading line full of spaces). Prints either a string representing the valid path (which includes S, E and all the = walked on except the last) or nothing if no path exists.

Test it here.

Explanation

Slip was Sp3000's entry to our 2D pattern matching language design challenge. It's a bit like a 2D-extension of regex where you can give instructions to the engine's cursor when it's allowed or required to make left or right turns. It also has a convenient feature where you can prevent the cursor from advancing, allowing you to match a single position twice in a row (with different patterns).

Slip doesn't have something comparable to lookarounds in regex, but since you can move over any position multiple times, one can just test the condition and then return. We use this to ensure that we only jump when on the ground by moving into the ground tile after each step.

S           Match the starting position S.
>           Turn right, so that the cursor points south.
(           One or more times... each repetition of this group represents
            one step to the right.
  `=          Match a = to ensure we've ended up on ground level before.
  <<          Turn left twice, so that the cursor points north.
  `P{1,5}     Match 1 to 5 non-punctuation characters (in our case, either space,
              S or E, i.e. a non-ground character). This is the jump.
  >           Turn right, so that the cursor points east.
  `P          Match another non-ground character. This is the step to the right.
  >           Turn right, so that the cursor points south.
  `P*         Match zero or more non-ground characters. This is the fall.
)+
#           Do not advance the cursor before the next match.
E           Match E, ensuring that the previous path ended on the exit.

Answer 2

Java 234 230 221 216 208 207 205 179 Bytes

Look, I beat C and python? I have acheived true transcendence among mortals! All jokes aside, this was a fun challenge. The following function takes input as an array of column strings each with the same length. If this is against the rules please do let me know. It outputs 1 meaning a successful mario run, and any other value implying a failed mario run.

int m(String[]a){int l=a.length-1,z=a[l].indexOf(69),m=a[0].indexOf(83),i=1,x;a[l]=a[l].replace("E"," ");for(;i<=l;m=x,i++){if(m-(x=a[i].indexOf('='))>3|x<1)return-1;}return m-z;}

Here is the older logic (which is similar to the current version) with example use and output. Plus some comments explaining the logic

/**
 *
 * @author Rohans
 */
public class Mario {

    int m(String[] a) {
//declare variables for the finish the location of mario and the length
        int z, l = a.length - 1, m = a[0].indexOf("S");
        //treat the exit as a space
        z = a[l].indexOf("E");
        a[l] = a[l].replaceAll("E", " ");
        //go through the map
        for (int i = 1, x, r = 1; i <= l; i++) {
            //if mario can safely jump to the next platform (it picks the highest one)
            if (((x = a[i].indexOf("=")) != 0 && (x = a[i].indexOf(" =")) == -1) || m - x > 4) {
                return 0;
            }
            //adjust marios y location
            m = x;
        }
        //make sure mario made it to the end of the level
        return m == z ? 1 : 0;
    }

    public static void MarioTest(String... testCase) {
        System.out.println(new Mario().m(testCase) == 1 ? "Mario made it" : "Mario did not make it");
    }

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        MarioTest("   S=", "=====", "     =", "     =", "=   =", "     E=");

    }

}

Answer 3

Python, 260 239 222 215 209 206 Bytes,

try it on ideone (with test cases)

f=lambda m,y=-1,x=0:f(m,m[0].find("S"))if y<0else y<len(m[0])-1and x<len(m)and m[x][y]!="="and(m[x][y]=="E"or m[x][y+1]=="="and any(f(m,y-i,x+1)for i in range(5)[:(m[x][y::-1]+"=").find("=")])or f(m,y+1,x))

call like: f([' S=', ' E='])

patch notes:

Now, like some of the other solutions, assumes input is an array of coloumn strings, each starting with a " "

Wrapper for old input form: g=lambda x:f(map("".join,zip(*([" "*x.index("\n")]+x.split("\n")))))

Also, I fixed a bug where Mario could jump through blocks above him.

ungolfed version with explanations:

f recursivly calls itself in all directions Mario can move to from y,x. It returns True when it reaches the "E"nd, which then goes back through all the function calls until g finally returns True.

def g(x):
    #create a array of strings which are the rows of the input
    global m
    m=x.split("\n")
    m=[" "*len(m[0])]+m # because Mario can jump over sometimes
    #Mario starts at the S
    return f([i for i,a in enumerate(m) if a[0]=="S"][0],0)

def f(y,x):
    #print y,x
    if y>len(m)-2 or x>=len(m[0]) or y<0: return False #out of bounds
    if m[y][x]=="E":return True #Reached the goal
    if m[y][x]=="=":return False #We got stuck inside a wall
    if m[y+1][x]=="=": #if you have ground under your feet
        for i in range(5): #jump max 4
            if f(y-i,x+1): #go one forward and try to go further from there
                return True
    return f(y+1,x) ##fall down

Answer 4

Snails, 41 37 29 bytes

Thanks to feersum for some help with avoiding overlapping paths and for saving 4 bytes.

=\S(^=d=\=u\ ,4(r!\=d.),r),\E

Requires input to be padded to a rectangle such that there are spaces in every cell Mario needs to traverse (potentially with a leading line full of spaces).

Try it online!

Explanation

Snails was feersum's entry to our 2D pattern matching language design challenge. Like Slip it's also similar to regex, but the major difference is that a) this one supports assertions (lookarounds) and b) aside from these assertions, it's not possible to traverse any cell in the grid twice. That makes this problem a bit tricky, since there are cases where Mario needs to fall into a hole and jump back out, e.g.:

S E
= =
===

Apart from these differences, the syntax of the two languages also differs quite a lot.

To circumvent the issue that we can't traverse a cell twice, we always alternate a horizontal step with a vertical step. However, this means that we have need to handle a fall before we step over the ledge. So falls will technically actually go through ground tiles but we'll ensure that they only happen next to open space.

=\S        Ensure that the match starts on an S, without actually matching it.
(          This group matches zero or more steps to the right (with a potential
           vertical step after each one).
  ^=         Match a non-ground cell, stepping right (on the first iteration,
             there is no step yet, so this matches the S).
  d=\=       Ensure that there's a ground tile below, so that the step ends on
             a valid position.
  u\ ,4      Match 0 to 4 spaces going up. This the optional jump.
  (          This group matches zero or more steps down, if a fall is valid here.
    r!\=       Ensure that there is no ground-tile right of the current cell.
    d.         Take one step down onto any character.
  ),
  r          Reset the direction to right for the next iteration.
),
\E        Match the exit.

Answer 5

C, 256 236 213 197 bytes

20 bytes saved by "This will always appear in the left-most column of the input"
23 bytes saved thanks to @RohanJhunjhunwala's column-based system

Try it on ideone, with test cases...

k,y,x,h;f(v,l)char**v;{h=strlen(*v);x=strcspn(*v,"S");while(y<l&x<h)if(v[y][x]==69)return 0;else if(v[y][x+1]^61)x++;else{if(v[y+1][x]==61)while(k<4)if(v[y+1][x-++k]^61){x-=k;break;}y++;}return 1;}

Usage:

$ ./mario "S=" " =" " =" " =" "E="
main(c,v)char**v;{printf("%s",f(v+1,c-1)==0?"true":"false");}

---

Ungolfed with explanation:

k,y,x,h; //omitting int for saving 4 bytes, global variables initialize as 0 by default
f(v,l)char**v;{ //saving 2 bytes
    h=strlen(v[0]); //get height of map
    x=strcspn(v[0],"S"); //where is start point?
    while(y<l&&x<h) //while not out of bounds
        if(v[y][x]==69)return 0; //if we hit end return 0 (69 is ASCII E)
        else if(v[y][x+1]!=61)x++; //we fall one block if there isn't floor underneath us (61 is ASCII =)
        else{
            if(v[y+1][x]==61) //if there is a wall in front of us
                while(k<4) //start counting
                    if(v[y+1][x-++k]!=61){ //if found a way
                        x-=k; //go to there
                        break; //we don't want to jump multiple times
                    }
            y++; //finally, walk one block forwards
        }
    return 1; //if out of bounds
}

Answer 6

PHP, 399 338 284 265 251 bytes

<?function w($m,$p){$w=strpos($m,"
")+1;if($p>strlen($m)|($p%$w)>$w-2|$p<0|'='==$m[$p])return 0;if('E'==$m[$p])die(1);if('='!=$m[$p+$w])return w($m,$p+$w);else for(;$z<5&'='!=$m[$q=$p-$w*$z];$z++)if(w($m,$q+1))die(1);}die(w($m=$argv[1],strpos($m,S)));

expects input as command line argument with unix style line breaks and trailing spaces in every line, returns exit code 1 for success, 0 for failure

breakdown to function

function w($m,$p) // function walk
{
    $w=strpos($m,"\n")+1;
    if($p<0|$p>strlen($m)|($p%$w)>$w-2  // too high / too low / too far right
        | '='==$m[$p]                   // or inside a wall
    )return 0;
    if('E'==$m[$p])return 1;            // Exit found
    if('='!=$m[$p+$w])return w($m,$p+$w); // no wall below: fall down
    else for($z=0;$z<5                  // else: jump
        & '='!=$m[$q=$p-$w*$z]          // do not jump through walls
        ;$z++)
        if(w($m,$q+1))                  // try to walk on from there
            return 1;
    // no success, return failure (NULL)
}
function m($i){$argv=[__FILE__,$i];
    return w($m=$argv[1],strpos($m,S));     // walk through map starting at position of S
}

tests (on function m)

$cases=[
    // examples
    "S = E\n=====",0,
    "S   \n=== \n    \n ===\n   E\n====",0,
    "    E \n   == \n==    \n   == \n==    \n   == \n==    \nS  == \n======",0,
    "S      \n=      \n=      \n=      \n=      \n=      \n=      \n= =    \n=      \n=      \n=      \n=     E\n=======",1,
    "S   E\n== ==\n = = ",0,
    " E\n =\n =\n =\nS=\n==",1,
    "      \n =    \n =   E\nS=   =\n==   =\n =   =\n =====",1,
    "S   \n=   \n    \n    \n    \n    \n    \n    \n=  E\n====",1,
    // additional cases
    "S \n= \n=E",1,
    " == \n == \n    \nS==E\n==  ",1
];
echo'<table border=1><tr><th>input</th><th>output</th><th>expected</th><th>ok?</th></tr>';
while($cases)
{
    $m=array_shift($cases);
    $e=array_shift($cases);
    $y=m($m);
    $w=strpos($m,"\n");
    echo"<tr><td><div style=background-color:yellow;width:",$w*8,"px><pre>$m</pre></div>width=$w</td>
        <td>$y</td><td>$e</td><td>",$e-$y?'N':'Y',"</td></tr>";
}
echo'</table>';

Answer 7

Ruby, 153 147 bytes

Sorry, Java... your spot as best non-golf lang for the job is being taken over!

Input is a list of column strings, prepended with a single space in the style of how the Slip and Snails solutions require their inputs to be padded with a rectangle of empty space.

Try it online!

f=->m,j=0,s=p{c,n=m[j,2]
s||=c=~/S/
e=c=~/E/
s+=1 while(k=c[s+1])&&k!=?=
s==e||(0..4).any?{|i|k&&s>=i&&c[s-i,i]!~/=/&&n&&n[s-i]!=?=&&f[m,j+1,s-i]}}

Answer 8

Grime, 46 bytes (non-competing)

A=\E|[S ]&<\ {,-4}/0/./* \ /*/A/\=/./*>
n`\S&A

I have updated Grime several times after this challenge was posted, so this answer is not eligible for winning. Some of the changes are so new that I haven't been able to get them into TIO, but once I do, you can try out the program. In any case, my repository contains a version that handles this code correctly.

The program prints 1 if Mario can reach the goal, and 0 if not. The input has to contain spaces in all places Mario needs to visit. For general inputs, I have the following 57-byte solution:

A=\E|[ \bS]&<[ \b]{,-4}/0/[]/* [ \b]/*/A/\=/[]/*>
nb`\S&A

Explanation

The high-level explanation is that the nonterminal A, defined on the first line, matches a 1×1 sub-rectangle of the input where Mario can reach the goal. A is defined as either the literal E (Mario is already at the goal), or as a 1×1 pattern that's on the left column of some 2×n rectangle containing a valid Mario jump to another match of A on the right column. The second line counts the number of matches of A that also contain the start character S, and prints that.

Here's a break-down of the code:

A=\E|[ S]&<\ {,-4}/0/./* \ /*/A/\=/./*>
A=                                       Define A as
  \E|                                    a literal E, or
     [ S]&                               a literal space or S
          <                           >  contained in a larger rectangle
                                         that this bracketed expression matches.
           \ {,-4}/0/./*                 Left half of the bracketed expression:
           \ {,-4}                        Rectangle of spaces with height 0-4,
                  /                       below that
                   0                      the 1x1 rectangle we're currently matching,
                    /.                    below that any 1x1 rectangles
                      /*                  stacked any number of times vertically.
                         \ /*/A/\=/./*   Right half of the bracketed expression:
                         \ /*             Spaces stacked vertically,
                             /A           below that another match of A,
                               /\=        below that a literal =,
                                  /./*    below that 1x1 rectangles stacked vertically.

The idea is that the \ {,-4} part on the left matches the space through which Mario jumps upward, and the \ /* part on the right matches the space trough which he then falls down. We require that he lands on a match of A (since we want to reach the goal) that's on top of a =. The vertical stacks below both columns will simply guarantee that the columns have the same height, so we can concatenate them (which is what the single space in the middle does). Here's an ASCII art diagram of an example jump, broken into the aforementioned rectangles, and with spaces replaced by *s:

Left column:     Right column:   +---+---+
a = \ {,-4}      d = \ /*        | * | * |
b = 0            e = A           +   +   + d
c = ./*          f = \=          | * | * |
                 g = ./*       a +   +---+
                                 | * | * | e
                                 +   +---+
                                 | * | = | f
                                 +---+---+
                               b | S | = |
                                 +---+   | g
                               c | = | * |
                                 +---+---+

On the second line, the option n triggers counting of all matches, instead of finding the first match. In the general solution, the spaces can also be special out-of-input characters, and option b causes the input to be padded with out-of-input characters.

I hope all of this makes sense!