# Can Mario go to the end of this map

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!

• In the falling example, you mention that "he cannot reach the #, because Mario falls straight down." If I'm viewing this correctly, wouldn't he fall straight down onto the #? Also, are jumps defined as a maximum of 4 spaces up and maximum of 1 space right? – GuitarPicker Jul 23 '16 at 21:58
• @GuitarPicker I thought that at first aswell but if you look closely you can see there is another column of spaces before the column with the #. As to the second question: I'm not OP but I'm guessing you are right. (that's what I assumed in my solution) – KarlKastor Jul 23 '16 at 22:59
• In the third example (demonstrating Mario's jump height), E does not appear in the right-most column because the ground level extends one to the right from the rest of the map. – Taylor Lopez Jul 25 '16 at 18:49
• @Joffan: Mario cannot walk through wall , and cannot fall past a floor, or jump past a ceiling – Titus Jul 25 '16 at 23:28
• @Titus I'm thinking about Mario jumping into clear air and having a choice of different floors to land on - can he get to the lower one? – Joffan Jul 25 '16 at 23:41

## Slip, 3827 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.


# 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.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.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;
}
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=");

}

}

• – betseg Jul 25 '16 at 20:57
• Does not work if the correct path is below a reachable "=" – KarlKastor Jul 25 '16 at 22:27
• @KarlKastor, you did get me, but the given test case is correct. The issue is that the op did not spefcify whether there would be multiple ways the mario could go at each step – Rohan Jhunjhunwala Jul 25 '16 at 23:53
• Well, I assumed there would be because I would always assume the more genral version if additional constrainst aren't specified. – KarlKastor Jul 25 '16 at 23:56
• @KarlKastor yeah ur right – Rohan Jhunjhunwala Jul 26 '16 at 0:04

# Python, 260239222215209 206 Bytes,

### try it on ideone (with test cases)

f=lambda m,y=-1,x=0:f(m,m.find("S"))if y<0else y<len(m)-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)]+m # because Mario can jump over sometimes
#Mario starts at the S
return f([i for i,a in enumerate(m) if a=="S"],0)

def f(y,x):
#print y,x
if y>len(m)-2 or x>=len(m) 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

• If jumping doesn´t help, you fall through the ground. Add an else before the final return? – Titus Jul 26 '16 at 0:27

## Snails, 4137 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.


# C, 256236213 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

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;}


$./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); //get height of map x=strcspn(v,"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 }  • Ideone say that there is a runtime error – TuxCrafting Jul 24 '16 at 20:01 • Wait, you are coding on mobile ಠ_ಠ – TuxCrafting Jul 24 '16 at 20:10 • Ye, I spilled coke on my laptop :P – betseg Jul 24 '16 at 20:11 • (Not to be mean to betseg, just to ensure fairness) @TùxCräftîñg: Is this solution compliant with your challenge because it takes a array of Strings (already split on "\n") and also has as input the length and width of the map (not part of the input in your challenge)? – KarlKastor Jul 24 '16 at 22:56 # PHP, 399338284265 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,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,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,
"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>';

• to whoever: Will let you please let me know why you downvoted this? – Titus Jul 26 '16 at 14:08

# 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]}}

• nooooo.... but u did "borrow" my method of columnar strings – Rohan Jhunjhunwala Jul 26 '16 at 3:14
• Well I mean, all the cool kids were doing it already. Might craft a row-based solution later, doing a "quick fix" to modify rows into columns to keep my current code loses to your Java by 10 bytes, but an actual solution might be shorter regardless – Value Ink Jul 26 '16 at 3:27

## 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!