Wprowadzenie

Masz nieszczęście utknąć w uciekającym samochodzie na torze przeszkód. Wszystkie funkcje samochodu nie reagują, z wyjątkiem uszkodzonego układu kierowniczego. Może jechać prosto lub skręcić w prawo. Czy samochód można prowadzić bezpiecznie?

Mechanika

Twój samochód zaczyna się w lewym górnym rogu mapy 8x8 i próbuje się bezpiecznie znaleźć w prawym dolnym rogu. Samochód ma orientację (początkowo w prawo), mierzoną co 90 stopni. Samochód może wykonać jedną z dwóch czynności:

1. Jedź o jeden kwadrat do przodu lub
2. Obróć o 90 stopni w prawo, a następnie jedź o jeden kwadrat do przodu

Zauważ, że samochód nie jest w stanie skręcić wystarczająco ostro, aby wykonać obrót o 180 stopni na jednym kwadracie.

Niektóre kwadraty są przeszkodami. Jeśli samochód wjedzie na plac przeszkody, ulega awarii. Zakłada się, że wszystko poza polem 8x8 jest przeszkodą, więc zjechanie z niego jest równoznaczne z awarią.

Kwadrat po prawej stronie jest kwadratem bezpiecznym, który pozwala samochodowi uciec z toru przeszkód. Zakłada się, że kwadrat początkowy i bezpieczny kwadrat nie są przeszkodami.

Zadanie

Musisz napisać program lub funkcję, która przyjmuje jako dane wejściowe tablicę 8x8 (matryca, lista list itp.), Reprezentującą tor przeszkód. Program zwraca lub wypisuje wartość logiczną lub coś podobnego prawdziwego. Jeśli możliwe jest, aby samochód dotarł do bezpiecznego kwadratu bez awarii (tzn. Jeśli mapa jest do rozwiązania), wynik jest True, w przeciwnym razie, jest False.

Punktacja

Standardowe zasady gry w golfa - zwycięzcą jest kod z najmniejszą liczbą bajtów.

Bonusy:

• Jeśli w przypadku mapy możliwej do rozwiązania kod wyprowadza prawidłową serię danych wejściowych kierowcy, które prowadzą samochód do bezpiecznego kwadratu, odejmij 10 punktów procentowych od wyniku. Przykładowym formatem wyjściowym może być SRSSR(wskazujący Prosto, Prawo, Prosto, Prosto, Prawo). To wyjście zastąpiłoby standardowe Truewyjście.

• Jeśli w przypadku nierozwiązywalnej mapy wynik kodu rozróżnia sytuacje, w których awaria jest nieunikniona, i sytuacje, w których można pokonywać tor przeszkód na zawsze, odejmij 10 punktów procentowych od swojego wyniku. Przykładem może być Crashsytuacja, gdy zderzenie jest nieuniknione lub Stucksamochód utknął na drodze z przeszkodami na zawsze. Te dane wyjściowe zastąpiłyby standardowe Falsedane wyjściowe dla nierozwiązywalnej mapy.

Przykład

Jeśli program otrzyma tablicę 8x8, taką jak ta:

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

Będzie to interpretowane jako mapa taka z czarnymi kwadratami wskazującymi przeszkody:

Możliwym rozwiązaniem może być:

Ponieważ istnieje rozwiązanie, program powinien zwrócić / wydrukować Truetę mapę. Pokazana sekwencja ruchów to SSSSRSRRRSRSSRRRSSRSSS.

JavaScript (ES6) - 122 124 148 162 172 178 187 190 193 208 bajtów

Ogromne podziękowania dla Optimizer i DocMax za pomocne sugestie dotyczące ulepszenia tego kodu:

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

Zwraca true(prawda) dla rozwiązania i false(fałsz) dla nierozwiązywalnego.

Działa tylko w przeglądarce Firefox ze względu na funkcje JavaScript 1.7.

Tablica testowa

Python 2 - 123 125 133 146 148 150 154 160

Truena sukces, Falsena porażkę.

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

Musisz podać dane wejściowe takie jak f(b=var_containing_board).

Wersja Lambda - 154

Zwraca 0(fałsz) porażkę, Truesukces.

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

Dzięki Willowi i Brandonowi za sprawienie, że funkcja jest krótsza niż lambda. Również w celu dodania przewijania w poziomie: D

Dzięki xnor za doskonałą bit-bash i logikę!

Edytuj notatkę: Jestem dość pewny, że b[y][x]nigdy nie zostanie wykonane, gdy wyjdziesz poza zasięg. Ponieważ jesteśmy poza planszą, sprawdzenie historii s in cbędzie False. Wtedy kontrola granicy (x|y)&8będzie 8. Wówczas python nawet nie sprawdzi ostatniej wartości, ==ponieważ pierwsze dwa są już różne.

C (GNU-C), 163 bajty * 0,9 = 146,7

# C (GNU-C), 186 bajtów * 0,9 = 167,4

Moja nowa wersja używa liczby całkowitej ze znakiem, a nie bez znaku. Wcześniej bałam się podpisanej prawej zmiany, ale zdałem sobie sprawę, że ponieważ bitem znaku jest pole bramkowe, nie ma znaczenia, co stanie się potem.

Funkcja przyjmuje tablicę bitów (te reprezentują zablokowane kwadraty) w postaci 64-bitowej liczby całkowitej. Bity są ułożone od najmniej do najbardziej znaczących w taki sam sposób, jak czytałbyś książkę. Zwraca -1 za awarię, 0 za wieczną jazdę lub 1 za ucieczkę do prawego dolnego rogu.

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

Program testowy

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

Wynik

Escape
Stuck
Crash

Konwerter tablic na hex w języku Python:

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

Python, 187 213

207 znaków, 10% bonusu za ścieżkę drukowania

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

Na wejściu testowym znajduje nieco inną ścieżkę: SSSSRSRSRRSSRSSRRSRSSRSSSSS

Ogólne podejście polega na tym, aby najpierw przekształcić dane wejściowe w spacje is o. Spacje mają heks 20, więc wszystkie cztery dolne bity są nieustawione. oma heks 6F, więc wszystkie cztery niskie bity są ustawione.

Ramka os jest umieszczona wokół planszy, więc nie musimy się martwić złymi indeksami.

Przechodząc przez planszę, używamy bitów na każdym kafelku, aby sprawdzić, czy wolno nam przejść, gdy przychodzimy z tej strony. W ten sposób unikamy nieskończonych pętli. Nie wystarczy mieć jedną wartość logiczną na płytkę, ponieważ kierunek wyjścia zależy od kierunku wejścia, więc płytki można odwiedzać dwukrotnie.

Następnie przeprowadzamy rekurencyjne wyszukiwanie bezpiecznej ścieżki.

JavaScript - 270 - 20% = 216 262 - 20% = 210 bajtów

Ponieważ powinno być co najmniej jedno rozwiązanie, które zarabia oba bonusy (i nie prowadzi do absurdalnej głębokości stosu;) ...

Zminimalizowane:

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

Rozszerzony:

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

vjest tablicą mieszającą z kluczami, które są potrójnymi stanami (x,y,d)odpowiadającymi współrzędnej (x, y) i kierunkowi wprowadzania d. Do każdego klawisza przypisana jest wartość, czyli ciąg S(prosty) i R(skręć w prawo) ruchów wymaganych do osiągnięcia stanu reprezentowanego przez klucz.

Kod utrzymuje również stos potrójnych (w zmiennej n), które nie zostały jeszcze przetworzone. Stos początkowo zawiera tylko potrójny (0,0,0), odpowiadający stanowi, w którym samochód jest skierowany w prawo w komórce (0,0). W zewnętrznej pętli for( S = ... )procedura sprawdza, czy pozostały jakieś nieprzetworzone potrójne. Jeśli tak, to działa każdy nieprzetworzone potrójne przez wewnętrzną pętlę n.map( ....

Wewnętrzna pętla robi pięć rzeczy:

1. oblicza dwa możliwe ruchy (jazda prosto, skręcanie w prawo) poza bieżący stan
2. jeśli którykolwiek z tych ruchów prowadzi do stanu już zarejestrowanego w tablicy mieszającej, jest on ignorowany do dalszego przetwarzania. Oznaczamy jednak wynik FAŁSZ jako K(zablokowany), ponieważ znaleźliśmy co najmniej jedną pętlę, w której samochód może krążyć wiecznie bez awarii.
3. jeśli stan jest legalny i nowatorski, jest dodawany do tablicy hashtable ( v) i stosu nieprzetworzonych potrójne ( m) dla następnego przejścia pętli zewnętrznej
4. po zarejestrowaniu nowego stanu vjego wartość jest ustawiana na wartość stanu początkowego (sekwencja ruchów) plus Rlub Sna podstawie bieżącego ruchu
5. if xi yare 7, wartość stanu początkowego (sekwencja ruchów podjęta w celu osiągnięcia stanu początkowego) jest kopiowana S, ponieważ ta sekwencja ruchów jest rozwiązaniem problemu

Po zakończeniu pętli wewnętrznej n(stos) zostaje zastąpiony przez m(nowy stos).

Po zakończeniu pętli zewnętrznej (nie osiągnięto żadnych nowych stanów) funkcja zwraca wynik. Jeśli komórka (7,7) została osiągnięta, Sbędzie zawierać sekwencję ruchów prowadzących do tej komórki, i jest ona generowana. Jeśli komórka nie Szostanie osiągnięta, będzie pusty ciąg, a procedura przechodzi do wyjścia O, które będzie zawierało K(zablokowane) wtedy i tylko wtedy, gdy zostanie znaleziona pętla, lub C(awaria), jeśli samochód nieuchronnie ulegnie awarii.

Python 339 - 10% = 305 bajtów

Użyłem rekursywnego wyszukiwania w pierwszej kolejności, które kończy się wcześnie po sukcesie za pośrednictwem exit. Również drukuj ścieżkę sukcesu w formie 00001010101010101010101110100111001000, 0na wprost, 1na prawo. Odpowiedź będzie dłuższa niż optymalna, ponieważ najpierw jest głębia. Jestem pewien, że niektóre optymalizacje algorytmu mogą znacznie zmniejszyć licznik bajtów.

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