Введение

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

механика

Ваша машина начинается в верхнем левом углу карты 8x8 и пытается добраться до безопасности в правом нижнем углу. Автомобиль имеет ориентацию (первоначально вправо), измеряемую с шагом в 90 градусов. Автомобиль может выполнять одно из двух действий:

1. Двигайтесь на одну клетку вперед или
2. Поверните на 90 градусов по часовой стрелке, затем поверните на один квадрат вперед

Обратите внимание, что автомобиль не может поворачивать достаточно резко, чтобы выполнить поворот на 180 градусов на одном квадрате.

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

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

задача

Вы должны написать программу или функцию, которая принимает в качестве входных данных массив 8x8 (матрица, список списков и т. Д.), Представляющий полосу препятствий. Программа возвращает или печатает логическое значение, или что-то похожее правдивое. Если автомобиль может добраться до безопасного квадрата без сбоев (т. Е. Если карта разрешима), то в Trueпротивном случае вывод получится False.

счет

Стандартный код правил гольфа - победителем становится код с наименьшим количеством байтов.

Бонусы:

• Если для разрешимой карты ваш код выводит правильную серию входов водителя, которые ведут автомобиль к безопасному квадрату, вычтите 10 процентных пунктов из вашей оценки. Примерным форматом вывода может быть SRSSR(с указанием Straight, Right, Straight, Straight, Right). Этот вывод заменит стандартный Trueвывод.

• Если для неразрешимой карты выходные данные вашего кода будут различаться между ситуациями, когда сбой неизбежен, и ситуациями, в которых возможно объездить полосу препятствий навсегда, вычтите 10 процентных пунктов из вашей оценки. Примером может быть вывод, Crashесли авария неизбежна, или Stuckесли автомобиль застрял на полосе препятствий навсегда. Эти выходы заменили бы стандартный Falseвывод для неразрешимой карты.

пример

Если программе дан массив 8x8, такой как этот:

[[0, 0, 0, 0, 0, 1, 0, 0],
 [0, 0, 0, 0, 0, 0, 1, 0], 
 [1, 1, 0, 0, 0, 0, 0, 0], 
 [0, 1, 0, 1, 0, 0, 0, 0], 
 [0, 0, 1, 1, 0, 0, 0, 0], 
 [0, 0, 0, 0, 1, 0, 1, 0], 
 [0, 0, 0, 0, 0, 0, 1, 0], 
 [0, 1, 1, 0, 0, 0, 1, 0]]

Это будет интерпретироваться как карта с черными квадратами, обозначающими препятствия:

И возможное решение может быть:

Поскольку решение существует, программа должна вернуть / напечатать Trueдля этой карты. Последовательность ходов , показанная здесь SSSSRSRRRSRSSRRRSSRSSS.

JavaScript (ES6) - 122 124 148 162 172 178 187 190 193 208 байт

Большое спасибо Optimizer и DocMax за полезные советы по улучшению этого кода:

F=a=>(D=(x,y,d)=>!D[i=[x,y,d]]&&(D[i]=1,x-=~d%2,y-=~-~d%2,x*y==49||!((x|y)&8||a[y][x])&&(D(x,y,d)||D(x,y,~-d%4))),D(-1,0))

Возвращает true(истинно) для разрешимого и false(ложно) для неразрешимого.

На сегодняшний день работает только в Firefox благодаря возможностям JavaScript 1.7.

Тестовая доска

Python 2 - 123 125 133 146 148 150 154 160

Trueв случае успеха, Falseв случае неудачи.

def f(h=1,v=0,b=0,x=0,y=0,c=[]):s=x,y,h,v;a=b,x+h,y+v,c+[s];return(s in c)==(x|y)&8==b[y][x]<(x&y>6or f(h,v,*a)|f(-v,h,*a))

Вы должны предоставить вход как f(b=var_containing_board).

Лямбда-версия - 154

Возвращает 0(ложно) для неудачи, Trueдля успеха.

F=lambda b,x=0,y=0,h=1,v=0,c=[]:0if[x,y,h,v]in c or x|y>7or x|y<0 or b[y][x]else x&y==7or F(b,x+h,y+v,h,v,c+[[x,y,h,v]])or F(b,x+h,y+v,-v,h,c+[[x,y,h,v]])

Спасибо Уиллу и Брэндону за то, что они сделали функцию короче лямбды. Также для добавления дополнительной горизонтальной прокрутки: D

Спасибо xnor за превосходную битовую биту и логику!

Редактировать примечание: я достаточно уверен, что b[y][x]никогда не будет выполнен при выходе за пределы диапазона. Поскольку мы за пределами доски, проверка истории s in cбудет False. Тогда проверка границы (x|y)&8будет 8. Тогда python даже не будет проверять последнее значение, ==потому что первые два уже различны.

C (GNU-C), 163 байта * 0,9 = 146,7

#C (GNU-C), 186 байт * 0,9 = 167,4

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

Функция принимает массив битов (единицы представляют собой блокированные квадраты) в виде 64-битного целого числа. Биты расположены от младшего к старшему так же, как вы читаете книгу. Возвращает -1 для аварии, 0 для движения навсегда или 1 для выхода в правый нижний угол.

g(long long o) {
    typeof(o) a=0,i=255,r=1,u=0,l=0,d=0,M=~0LLU/i,D;
    for( ;i--;d = D<<8&~o)
        a |= D = d|r,
        r = (r|u)*2&~M&~o,
        u = (u|l)>>8&~o,
        l = ((l|d)&~M)/2&~o;
    return a<0?:-!(d|r|u|l);
}

Тестовая программа

f(long long o){typeof(o)a=0,i=255,r=1,u=0,l=0,d=0,M=~0LLU/i,D;for(;i--;d=D<<8&~o)a|=D=d|r,r=(r|u)*2&~M&~o,u=(u|l)>>8&~o,l=((l|d)&~M)/2&~o;return a<0?:-!(d|r|u|l);}
{
    char* s[] = {"Crash", "Stuck", "Escape"};
    #define P(x) puts(s[f(x)+1])
    L ex = 0x4640500C0A034020;
    P(ex);
    L blocked = 0x4040404040404040;
    P(blocked);

    L dead = 0x10002;
    P(dead);

    return 0;
}

Выход

Escape
Stuck
Crash

Преобразователь массива в шестигранник Python:

a2b=lambda(A):"0x%X"%sum(A[i/8][i%8]<<i for i in range(64))

Питон, 187 213

207 символов, 10% бонус за путь печати

b=map(ord," "*9+" ".join("".join("o "[i]for i in j)for j in input())+" "*9)
def r(p,d,s):
 p+=(1,9,-1,-9)[d]
 if b[p]&1<<d:b[p]^=1<<d;return(s+"S")*(p==79)or r(p,d,s+"S")or r(p,(d+1)%4,s+"R")
print r(8,0,"")

На входе теста он находит немного другой путь: SSSSRSRSRRSSRSSRRSRSSRSSSSS

Общий подход заключается в том, чтобы сначала превратить ввод в пробелы и os. Пробелы имеют шестнадцатеричный код 20, поэтому все четыре младших бита не установлены. oимеет шестнадцатеричный код 6F, поэтому младшие четыре бита все установлены.

Граница os размещена вокруг доски, поэтому нам не нужно беспокоиться о плохих показателях.

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

Затем мы делаем рекурсивный поиск безопасного пути.

Javascript - 270 - 20% = 216 262 - 20% = 210 байтов

Так как должно быть хотя бы одно решение, которое зарабатывает оба бонуса (и не приводит к нелепой глубине стека;) ...

уменьшенная:

V=I=>{n=[N=[0,0,0]];v={};v[N]='';O='C';for(S='';n[0];){m=[];n.map(h=>{[x,y,d]=h;D=i=>[1,0,-1,0][d+i&3];p=v[h];for(j=2;j--;){O=v[c=[X=x+D(j),Y=y+D(3-3*j)),d+j&3]]?'K':O;J=X|Y;J<0||J>7||I[Y][X]||v[c]?O:(m.push(c),v[c]=p+'SR'[j])}S=(x&y)>6?p:S});n=m;}return S||O;};

Expanded:

V = I => {
    n = [N=[0,0,0]];
    v = {};
    v[N] = '';
    O = 'C';

    for( S = ''; n[0]; ) {
        m = [];
        n.map( h => {
            [x,y,d] = h;
            D = i => [1,0,-1,0][d+i&3];
            p = v[h];
            for( j = 2; j--; ) {
                O = v[c = [X = x+D(j),Y = y+D(3-3*j),d+j&3]] ? 'K' : O;
                J = X|Y;
                J<0 || J>7 || I[Y][X] || v[c] ? O : (
                    m.push( c ),
                    v[c] = p + 'SR'[j]
                );
            }

            S = (x&y) > 6 ? p : S;
        } );
        n = m;
    }
    return S || O;
};

vявляется хеш-таблицей с ключами, которые являются тройками состояний, (x,y,d)соответствующими координате (x, y) и направлению входа d. У каждого ключа есть связанное значение, которое представляет собой строку S(прямое) и R(повернуть направо) ходов, необходимых для достижения состояния, представленного ключом.

Код также поддерживает стек троек (в переменной n), которые еще не были обработаны. Стек изначально содержит только тройку (0,0,0), соответствующую состоянию, в котором автомобиль стоит прямо в ячейке (0,0). Во внешнем цикле for( S = ... )подпрограмма проверяет, остаются ли необработанные тройки. Если это так, то каждый необработанный триплет проходит по внутреннему циклу n.map( ....

Внутренний цикл делает пять вещей:

1. вычисляет два возможных движения (движение прямо, поворот направо) из текущего состояния
2. если любое из этих перемещений приводит к состоянию, уже зарегистрированному в хеш-таблице, оно игнорируется для дальнейшей обработки. Однако мы помечаем вывод FALSE как K(застрял), поскольку мы нашли по крайней мере один цикл, в котором автомобиль может продолжать вращаться вечно, не разбиваясь.
3. если состояние допустимо и является новым, оно добавляется в hashtable ( v) и в стек необработанных триплетов ( m) для следующего прохода внешнего цикла
4. когда новое состояние зарегистрировано v, его значение устанавливается равным значению исходного состояния (последовательности ходов) плюс Rили Sна основе текущего хода
5. если xи yесть 7, значение исходного состояния (последовательность ходов, предпринятых для достижения исходного состояния) копируется S, поскольку эта последовательность ходов является решением проблемы

После завершения внутреннего цикла n(стек) заменяется на m(новый стек).

После завершения внешнего цикла (новые состояния не были достигнуты), функция возвращает свой вывод. Если ячейка (7,7) была достигнута, Sбудет содержать последовательность ходов, ведущих к этой ячейке, и это выводится. Если ячейка не была достигнута, Sбудет пустой строкой, и процедура переходит к выводу O, который будет содержать K(застрял), если и только если был найден цикл, или C(сбой), если автомобиль неизбежно потерпит крах.

Python 339 - 10% = 305 байт

Я использовал рекурсивный поиск в глубину, который был прерван в случае успеха через exit. Также печатание пути на удачу в виде 00001010101010101010101110100111001000, 0прямо, 1направо. Ответ будет длиннее, чем оптимальный, так как он в глубину. Я уверен, что некоторые оптимизации алгоритма могут немного снизить количество байтов.

b=input()
D=[(-1,0),(0,-1),(1,0),(0,1)]
def a(l):
 x,y=0,0
 v=2
 for d in l:
  if d=='1':v=(v+1) % 4
  x+=D[v][0]
  y+=D[v][1]
  if x<0 or x>7 or y<0 or y>7:return 0,x,y
  if b[y][x]:return -1,x,y
 return 1,x,y
def c(l):
 if len(l) < 39:
  t,x,y=a(l)
  if t==1:
   if (x,y)==(7,7):
    print l;exit(0)
   c(l+"0")
   c(l+"1")
c("")
print 0