Twój samochód skręca tylko w prawo!

49

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:

wprowadź opis zdjęcia tutaj

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

wprowadź opis zdjęcia tutaj

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

fosgen
źródło
2
Napisałem kilka niezwykle prostych przypadków testowych dla Crashi Stuck. Są tutaj ze względu na ich długość. Wiersz 2 wypełniony, wszystko inne puste -> Crash. Wiersz 7 wypełniony, wszystko inne puste ->Stuck
podziemna
3
Jestem zdezorientowany co do punktów procentowych (w przeciwieństwie do wartości procentowych). Otrzymanie którejkolwiek z premii zwielokrotnia Twój wynik przez 0,9. Czy otrzymanie obu pomnoży to przez 0,8 lub 0,9 ^ 2?
undergroundmonorail
3
Jasne, S i C są w porządku. Moje wyniki były jedynie sugestiami.
fosgen
13
„Dwie krzywdy nie czynią dobra, ale trzy lewe tak”. - tato.
hoosierEE
2
„Twój samochód może wykonać tylko zero lub trzy lewe!”
feersum

Odpowiedzi:

17

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

ja i mój kot
źródło
1
Jest to 193 bajtów: 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).
Optymalizator
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={})- Testowane.
Optymalizator
1
@Optimizer Nadal sprawdzam się w drugim przypadku testowym [[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]]. To powinno dać fałsz.
ja i mój kot
2
Wynika to z faktu, że odtąd xi yoba są globalne, nie można uruchomić dwóch przypadków testowych przed ponownym załadowaniem strony ...
Optymalizator
1
Można zapisać w sumie 9 więcej zastępując x+=d?d^2?0:-1:1z x+=d&1?0:1-di y+=d^1?d^3?0:-1:1z y+=d&1&&2-d.
DocMax,
10

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.

FryAmTheEggman
źródło
1
Wersja funkcjonalna może łączyć dwa ifs, które oba zwracają; ponieważ sam powrót zwraca Brak, co jest fałszem, nie musisz też zwracać 0. wystarczy odwdzięczyć się;)
Czy
Jeśli przerzucisz czeki, możesz także połączyć oba ifs
Czy
Czy można połączyć oba zwroty?
Brandon
1
@Will Dzięki, wiedziałem, że jest lepszy sposób: D Um, nie mogłem znaleźć spacji do usunięcia, które nie powodują błędu składniowego. Naprawdę nie rozumiem, dlaczego x|y>7ordziała, ale x|y<0ornie ...
FryAmTheEggman
1
Możesz stworzyć ósemkowy literał zaczynający się od 0o.
feersum
9

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))
feersum
źródło
1
Zamień memset(&M,~1,8)(15 znaków) na M=~(-1ULL/255)(14 znaków).
R ..
@R .. Niezły! -4 bajty z tego.
feersum
2
Podoba mi się format wejściowy - bardzo fajnie!
fosgen
Dostaję „awarię” dla P(0x00fefefefefefefe);= (Powinien być prosto strzelony w prawy górny róg, jeden obrót, prosto do rogu. To samo dla P(0x00eeeeeeeeeeeeee);(ślepy zaułek na 4. kolumnie). Nie sądzę, że musisz apoczątkowo przypisywać .
@tolos Masz transpozycję kolejności wierszy / kolumn. Aby górny wiersz i prawa kolumna były otwarte, powinno być 0x7f7f7f7f7f7f7f00. Konieczna jest również inicjalizacja, aponieważ później jest modyfikowana tylko przez ORing w dodatkowych bitach, więc nie mogę sobie pozwolić na początkowo ustawiony niechciany bit.
feersum
6

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.

Będzie
źródło
3
„Twój samochód zaczyna się w lewym górnym rogu mapy 8x8” - czy nie możesz na stałe podać kodu 9zamiast w=len(b[0])+1itd.?
FryAmTheEggman
@FryAmTheEggman dziękuję, jak mogłem to przeoczyć? : D
Czy
Możesz odwrócić swoje oświadczenie trójkowe i zastąpić p==79je p-79. Mam błąd składniowy, robiąc to w obie strony bez spacji przed else. Myślę, że ta sztuczka działa tylko z if.
FryAmTheEggman
@FryAmTheEggman Myślę, że test głębokości musi się odbyć przed powtórzeniem? Zamiast tego bawiłem się mnożeniem przez wartość logiczną.
Czy
7
Właśnie znalazłem naprawdę fajną sztuczkę. Prawdopodobnie wiesz, że -~x==, x+1ale oba jednoargumentowe operatory mają wyższy priorytet niż mnożenie, dzielenie i moduł! Tak (d+1)%4może być -~d%4! To też działałoby, x-1ale wystarczy użyć ~-xzamiast tego.
FryAmTheEggman
6

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.

COTO
źródło
1
Otrzymałem potwierdzenie z OP, możesz zmienić nazwę „Crash” i „Stuck” na „C” i „S”.
FryAmTheEggman
Ach To trochę oszczędza. Dzięki. ;)
COTO
Czy możesz wyjaśnić, co robi Twój kod? Nie mogę zrobić z tego głów ani ogonów.
fosgen
@phosgene: Dołączyłem szczegółowe wyjaśnienie.
COTO
To sprytna procedura. Nic się nie marnuje.
fosgen
4

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
stokastic
źródło
3
Ponieważ jest Python 2, można mieszać kart i spacji do wcięcia, jak w a„s forpętli. Nie potrzebujesz również spacji wokół operatorów, np. (v+1) % 4-> (v+1)%4. Można również dołączyć kilka wypowiedzi na jedną linię za pomocą ;, jeśli nie jest iflub foritp na linii, np c(l+"0");c(l+"1"). Niektóre inne golfs: x,y,v=0,0,2, x|y>7 or x|y<0, x==y==7. Powodzenia :)
FryAmTheEggman