Ваша машина только поворачивает направо!

49

Введение

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

механика

Ваша машина начинается в верхнем левом углу карты 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.

фосген
источник
2
Я написал несколько невероятно простых тестов для Crashи Stuck. Они здесь из-за того, как долго они. Строка 2 заполнена, все остальное пусто -> Crash. Строка 7 заполнена, все остальное пусто ->Stuck
подземный
3
Я запутался в процентных пунктах (в отличие от процентов). Получение любого бонуса увеличивает ваш счет на 0,9. Умножение обоих умножает это на 0,8 или 0,9 ^ 2?
подземный
3
Конечно, S и C в порядке. Мои выводы были только предложениями.
Фосген
13
«Два зла не дают права, а три левых делают». Папа
hoosierEE
2
«Ваша машина может сделать только ноль или три левых!»
feersum

Ответы:

17

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.

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

я и мой кот
источник
1
Это составляет 193 байт: D=(x,y,d,t,a)=>!t[i=x+y*8+d*64]&&(t[i]=1,x+=d==0?1:d==2?-1:0,y+=d==1?1:d==3?-1:0,x==7&&y==7||!((x|y)&~7||a[y][x])&&G(x,y,d,t,a));G=(x,y,d,t,a)=>D(x,y,d,t,a)||D(x,y,d+1&3,t,a);F=a=>G(0,0,0,[],a).
Оптимизатор
1
172: D=d=>!t[i=x+y*8+d/4]&&(t[i]=1,x+=d?d^2?0:-1:1,y+=d^1?d^3?0:-1:1,x==7&&y==7||!((x|y)&~7||b[y][x])&&G(x,y,d));G=(X,Y,d)=>D(d,x=X,y=Y)||D(d+1&3,x=X,y=Y);F=a=>G(0,0,0,b=a,t={})- Проверено.
Оптимизатор
1
@Optimizer Я до сих пор вернусь ко второму тесту [[0, 0, 0, 0, 0, 0, 0, 0], [1, 1, 1, 1, 1, 1, 1, 1], [0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0]]. Это должно дать ложь.
я и мой кот
2
Это происходит потому , что так xи yоба Глобал, вы не можете запустить два testcases перед загрузкой страницы ...
Оптимизатор
1
Вы можете сохранить в общей сложности 9 более заменой x+=d?d^2?0:-1:1с x+=d&1?0:1-dи y+=d^1?d^3?0:-1:1с y+=d&1&&2-d.
DocMax
10

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 даже не будет проверять последнее значение, ==потому что первые два уже различны.

FryAmTheEggman
источник
1
Функциональная версия может объединять два if, которые оба возвращают; поскольку возвращение само по себе не возвращает None, что является ложным, вам также не нужно возвращать 0.. Просто возвращая услугу;)
Будет
Если вы перевернете чеки, вы можете объединить оба ifs
Will
Можете ли вы объединить оба оператора возврата?
Брэндон
1
@ Спасибо, я знал, что есть лучший способ сделать это: D Хм, я не смог найти пробелы для удаления, которые не вызывают у меня синтаксическую ошибку. Я действительно не понимаю, почему x|y>7orработает, но x|y<0orне ...
FryAmTheEggman
1
Вы можете сделать восьмеричное буквальное начало, начиная с 0o.
feersum
9

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))
feersum
источник
1
Заменить memset(&M,~1,8)(15 символов) на M=~(-1ULL/255)(14 символов).
R ..
@R .. Хороший! -4 байта от этого.
Feersum
2
Мне нравится формат ввода - очень круто!
Фосген
Я получаю 'крах' для P(0x00fefefefefefefe);= (Должен быть прямым выстрелом в верхний правый угол, один поворот, прямо в угол. То же самое для P(0x00eeeeeeeeeeeeee);(тупик на 4-м столбце). Я не думаю, что вам нужно назначать aизначально.
@tolos Вы получили транспонированный порядок строк / столбцов. Чтобы верхний ряд и правая колонка были открыты, это должно быть так 0x7f7f7f7f7f7f7f00. Также необходимо выполнить инициализацию, aпотому что позже она изменяется только путем ORing в дополнительных битах, поэтому я не могу позволить себе изначально установить нежелательный бит.
feersum
6

Питон, 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 размещена вокруг доски, поэтому нам не нужно беспокоиться о плохих показателях.

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

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

Будет
источник
3
«Ваш автомобиль начинается в верхнем левом углу карты 8х8» - вы не можете жёстко 9на месте w=len(b[0])+1, и т.д.?
FryAmTheEggman
@FryAmTheEggman спасибо, как я мог это пропустить? : D
Will
Вы можете отменить свое троичное заявление и заменить p==79на p-79. Я получил синтаксическую ошибку, делающую это в обоих направлениях без пробела перед else. Я думаю, что этот трюк работает только с if.
FryAmTheEggman
@FryAmTheEggman Я думаю, что тест глубины должен до рекурса? Вместо этого я играл с умножением на логическое.
Будет
7
Я только что нашел очень интересный трюк. Вы, вероятно, знаете это -~x==, x+1но оба унарных оператора имеют более высокий приоритет, чем умножение, деление и модуль! Так (d+1)%4может быть -~d%4! Это также будет работать, x-1но просто использовать ~-xвместо этого.
FryAmTheEggman
6

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(сбой), если автомобиль неизбежно потерпит крах.

COTO
источник
1
Получив подтверждение от OP, вы можете переименовать «Crash» и «Stuck» в «C» и «S».
FryAmTheEggman
Ах. Это немного экономит, тогда. Благодарю. ;)
COTO
Можете ли вы объяснить, что делает ваш код? Я не могу сделать головы или хвосты этого.
Фосген
@phosgene: я включил подробное объяснение в строке.
COTO
Это умная процедура. Ничего не потеряно.
Фосген
4

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
stokastic
источник
3
Так как это Python 2, вы можете смешать вкладки и пробелы для отступов, как в a«S forцикла. Вам также не нужны пробелы вокруг операторов, например (v+1) % 4-> (v+1)%4. Вы также можете объединить несколько операторов в одну строку, используя, ;если нет ifили for, и т. Д. В строке, например c(l+"0");c(l+"1"). Некоторые другие гольфы: x,y,v=0,0,2, x|y>7 or x|y<0, x==y==7. Удачи :)
FryAmTheEggman