Создайте программу, которая определяет, учитывая ввод пути, может ли Марио достигнуть конца, обозначенного E, с самого начала, обозначенного как S.

Путь будет выглядеть примерно так:

S = E
=====

В пути различные символы и то, что они представляют:

• =: стена / пол / потолок. Марио не может пройти сквозь стену и не может упасть сквозь пол или прыгнуть через потолок (он ударит себя по голове)
• (пространство): воздух. Марио может пройти через это, и прыгнуть через это, и провалиться через это
• S: air, кроме показа, где начинается Марио. Это всегда будет отображаться в крайнем левом столбце ввода на уровне земли.
• E: air, кроме показа, куда Марио хочет попасть. Это всегда будет отображаться в крайнем правом столбце ввода на уровне земли.

Вход будет иметь пробелы в каждом месте, где Марио может ходить.

Марио может двигаться только вперед; в этом примере Марио не может добраться до цели

S
===

 ===
   E
====

и при этом он не может в этом

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

Тем не менее, он может достичь пространства, обозначенного #(которое не появится на входе), потому что он может прыгать до четырех ячеек; Марио сверхчеловек. Как еще один пример его сверхчеловечества:

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

Марио может добраться до E, прыгнув на большое расстояние, выжить и спокойно идти к E. Обратите внимание, что он не может достичь #, потому что Марио падает прямо вниз.

Марио может прыгать очень высоко, но не очень далеко вперед по сравнению.

S   E
== ==
 = =

Марио может попытаться преодолеть разрыв, но он потерпит неудачу и упадет прямо. Он не может достичь конца.

Марио может достичь цели во всех этих примерах:

 E
 =
 =
 =
S=
==

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

S
=






=  E
====

Это код гольф, поэтому побеждает меньше байтов!

Слип , 38 27 25 байт

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

Требует, чтобы ввод был дополнен прямоугольником так, чтобы в каждой ячейке были пробелы, которые должен пройти Марио (потенциально с линией, полной пробелов). Печатает либо строку, представляющую действительный путь (который включает и все пройденные пути S, кроме последнего), либо ничего, если пути не существует.E=

Проверьте это здесь.

объяснение

Slip - это вступление Sp3000 к нашей задаче разработки языка сопоставления двухмерных шаблонов. Это немного похоже на 2D-расширение регулярного выражения, где вы можете давать инструкции движку движка, когда ему разрешено или необходимо совершать левый или правый повороты. Он также имеет удобную функцию, позволяющую предотвратить продвижение курсора, позволяя сопоставлять одну позицию дважды подряд (с разными рисунками).

Slip не имеет ничего похожего на обходные выражения в регулярных выражениях, но, поскольку вы можете перемещаться по любой позиции несколько раз, можно просто проверить условие и затем вернуться. Мы используем это, чтобы гарантировать, что мы прыгаем только на земле, перемещаясь в плитку земли после каждого шага.

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 байт

Смотри, я победил C и Python? Я достиг истинного превосходства среди смертных! Все шутки в сторону, это было забавное испытание. Следующая функция принимает входные данные как массив строк столбцов, каждая из которых имеет одинаковую длину. Если это противоречит правилам, пожалуйста, дайте мне знать. Он выводит 1, означающий успешный запуск Марио, и любое другое значение, подразумевающее неудачный запуск Марио.

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

Вот старая логика (которая похожа на текущую версию) с примером использования и вывода. Плюс несколько комментариев, объясняющих логику

/**
 *
 * @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=");

    }

}

Python, 260 239 222 215 209 206 байт,

попробуй его на ideone (с тестовыми примерами)

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))

позвоните как: f([' S=', ' E='])

примечания к патчу:

Теперь, как и некоторые другие решения, предполагается, что input - это массив строк столбцов, каждая из которых начинается с ""

Оболочка для старой формы ввода: g=lambda x:f(map("".join,zip(*([" "*x.index("\n")]+x.split("\n")))))

Также я исправил ошибку, из-за которой Марио мог прыгать через блоки над ним.

Нежелательная версия с объяснениями:

fрекурсивно называет себя во всех направлениях, куда Марио может перейти y,x. Он возвращается, Trueкогда достигает "E"nd, который затем проходит через все вызовы функций, пока, gнаконец, не вернется 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

Улитки , 41 37 29 байт

Спасибо feersum за некоторую помощь в избежании перекрывающихся путей и за сохранение 4 байтов.

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

Требует, чтобы ввод был дополнен прямоугольником так, чтобы в каждой ячейке были пробелы, которые должен пройти Марио (потенциально с линией, полной пробелов).

Попробуйте онлайн!

объяснение

Улитки были началом работы Feersum в нашей языковой задаче по сопоставлению шаблонов. Как и Slip, он также похож на регулярное выражение, но основное отличие состоит в том, что a) этот поддерживает утверждения (lookarounds) и b), кроме этих утверждений, невозможно пересечь любую ячейку в сетке дважды. Это делает эту проблему немного сложнее, поскольку есть случаи, когда Марио нужно упасть в яму и выпрыгнуть назад, например:

S E
= =
===

Помимо этих различий, синтаксис двух языков также довольно сильно отличается.

Чтобы обойти проблему, заключающуюся в том, что мы не можем пройти через ячейку дважды, мы всегда чередуем горизонтальный шаг с вертикальным шагом. Однако это означает, что нам нужно выдержать падение, прежде чем мы перешагнем через уступ. Таким образом, падения будут технически проходить сквозь плитки, но мы будем следить за тем, чтобы они происходили только рядом с открытым пространством

=\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 256 236 213 197 байтов

20 байтов, сохраненных с помощью «Это всегда будет отображаться в крайнем левом столбце ввода»
23 байта, сохраненных благодаря системе на основе столбцов @ RohanJhunjhunwala

Попробуйте это на ideone, с тестовыми примерами ...

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

Разгромленный с объяснением:

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
}

PHP, 399 338 284 265 251 байт

<?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)));

ожидает ввод в качестве аргумента командной строки с разрывами строки в стиле Unix и конечными пробелами в каждой строке, возвращает код завершения 1для успеха, 0для ошибки

разбивка на функции

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
}

тесты (по функции м)

$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>';

Рубин, 153 147 байт

Извините, Ява ... Ваше место как лучшего не-гольф-ланга для работы занято!

Входные данные представляют собой список строк столбцов с предваряющим одним пробелом в стиле того, как решения Slip и Snails требуют, чтобы их входы были дополнены прямоугольником пустого пространства.

Попробуйте онлайн!

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

Грязь, 46 байт (не конкурирует)

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

После публикации этого задания я несколько раз обновлял Grime, поэтому этот ответ не имеет права на победу. Некоторые изменения настолько новы, что я не смог получить их в TIO, но как только я это сделаю, вы можете попробовать программу . В любом случае мой репозиторий содержит версию, которая правильно обрабатывает этот код.

Программа печатает, 1если Марио может достичь цели, а 0если нет. Вход должен содержать пробелы во всех местах, которые необходимо посетить Марио. Для общих входных данных у меня есть следующее 57-байтовое решение:

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

объяснение

Высокоуровневое объяснение состоит в том, что нетерминал A, определенный в первой строке, соответствует под прямоугольнику 1 × 1 ввода, где Марио может достичь цели. Aопределяется как литерал E(Марио уже у цели) или как шаблон 1 × 1 , который находится в левом столбце некоторого прямоугольника 2 × n, содержащего действительный переход Марио к другому совпадению Aв правом столбце. Вторая строка подсчитывает количество совпадений, Aкоторые также содержат начальный символ S, и печатает это.

Вот разбивка кода:

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.

Идея состоит в том, что \ {,-4}часть слева соответствует пространству, через которое Марио прыгает вверх, а \ /*часть справа соответствует пространственной впадине, в которую он затем падает. Мы требуем, чтобы он приземлился на матч A(так как мы хотим достичь цели), который находится на вершине =. Вертикальные стеки под обоими столбцами просто гарантируют, что столбцы имеют одинаковую высоту, поэтому мы можем объединить их (что и делает одно пространство в середине). Вот художественная схема ASCII примера прыжка, разбитого на вышеупомянутые прямоугольники и с пробелами, замененными на *s:

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

Во второй строке эта опция nзапускает подсчет всех совпадений вместо того, чтобы найти первое совпадение. В общем решении пробелы также могут быть специальными символами без ввода, и опция bзаставляет ввод дополняться символами без ввода.

Я надеюсь, что все это имеет смысл!