Tłumacz RoboZZle

10

Twoim zadaniem jest napisanie interpretera RoboZZle. Jeśli nie znasz gry, obejrzyj wideo na robozzle.com lub przeczytaj mój opis poniżej.

Robot żyje na prostokątnej siatce kwadratów w kolorze czerwonym, zielonym, niebieskim lub czarnym. Czarne kwadraty są niedostępne. Inne są dostępne, a niektóre z nich zawierają gwiazdkę. Celem jest zebranie wszystkich gwiazd bez wchodzenia na czarne kwadraty i spadania z mapy. Robot zajmuje jeden kwadrat i jest skierowany w określonym kierunku - w lewo, w prawo, w górę lub w dół. Postępuje zgodnie z instrukcjami podobnymi do złożenia pogrupowanymi w podprogramy F1, F2, ..., F5. Instrukcja jest parą predykatu („brak”, „jeśli na czerwonym”, „jeśli na zielonym”, „jeśli na niebieskim”) i akcja („idź do przodu”, „skręć w lewo”, „skręć w prawo”, „pomaluj bieżący kwadrat na czerwono”, „pomaluj na zielono”, „pomaluj na niebiesko”, „nic nie rób”, „zadzwoń do F1”, ..., „zadzwoń do F5”). Wywołania podprogramów używają stosu i mogą być rekurencyjne. Podobnie jak w konwencjonalnym programowaniu, po zakończeniu ostatniej instrukcji podprogramu wykonywanie jest kontynuowane od momentu wywołania podprogramu. Wykonanie rozpoczyna się od pierwszej instrukcji F1 i trwa do momentu, gdy robot odwiedzi wszystkie kwadraty z gwiazdami lub gdy robot wejdzie na czarny kwadrat lub poza mapę, lub wykona 1000 instrukcji (nieudane predykaty i akcje „nic nie rób”) nie licz) lub nie ma już instrukcji do wykonania (niedopełnienie stosu).

Wejścia:

  • a- matryca 12 x 16 znaków (jak zwykle reprezentowana w twoim języku, np. tablica ciągów znaków), która koduje mapę - '#'dla niedostępnych (czarnych) kwadratów, '*'dla kwadratów z gwiazdą, '.'dla reszty

  • c- matryca znaków 12x16 opisująca kolory dostępnych kwadratów - 'R'(czerwony), 'G'(zielony) lub 'B'(niebieski). Niedostępne kwadraty będą reprezentowane przez dowolną literę z trzech.

  • yoraz x- wiersz i kolumna robota oparte na 0; a[y][x]gwarantowane jest'.'

  • d- kierunek robota stoi: 0 1 2 3na prawo, w dół, w lewo, w górę, czyli w kierunku (y,x+1), (y+1,x), (y,x-1),(y-1,x)

  • f- pojedynczy ciąg, połączone implementacje F1 ... F5. Każda implementacja to (być może pusta) sekwencja par predykat-akcja (maksymalnie 10 par na podprogram), zakończona znakiem '|'.

    • predykaty: '_'brak, 'r'czerwony, 'g'zielony, 'b'niebieski

    • akcje: 'F'idź do przodu, 'L'skręć w lewo, 'R'skręć w prawo, 'r'pomaluj na czerwono, 'g'pomaluj na zielono, 'b'pomaluj na niebiesko, '1'zadzwoń do F1, ..., '5'zadzwoń do F5, '_'nic nie rób

Nie musisz nazywać swoich danych wejściowych jak wyżej, ale ich wartości muszą być zgodne z podanymi.

Wyjście: 1(lub true) jeśli robot zbiera wszystkie gwiazdy zgodnie z zasadami, 0( false) w przeciwnym razie.

Przykład :

a=["################","################","##*....*...*#.##","##.####.#####.##","##.####.#####.##","##.####*...*#.##","##.########.####","##*........*#.##","################","################","################","################"]
c=["RRRRRRRRRRRRRRRR","RRRRRRRRRRRRRRRR","RRRBBBBRGGGGRRRR","RRBRRRRGRRRRRRRR","RRBRRRRGRRRRRRRR","RRBRRRRRGGGBRRRR","RRBRRRRRRRRGRRRR","RRRBBBBGGGGBRBRR","RRRRRRRRRRRRRRRR","RRRRRRRRRRRRRRRR","RRRRRRRRRRRRRRRR","RRRRRRRRRRRRRRRR"]
y=2; x=6; d=2

// and then depending on "f":
f="_FrLg2_1|_FbLrR_2||||" // result:1
f="_FrRg2_1|_FbLrR_2||||" // result:0 (stepped on a black square)
f="_FrLrL_1|_FbLrR_2||||" // result:0 (1000-step limit exceeded)
f="_FrLg2__|________||||" // result:0 (stack underflow)

Kolejny przykład dotyczący instrukcji „malowania”:

a=["#***************","#*###*###*###*##","#*###*###*###*##","***#***#***#***#","***#***#***#***#","*###*###*###*###","***#***#***#***#","***#***#***#***#","***#***#***#***#","*###*###*###*###","*.*#***#***#***#","***#***#***#***#"]
c=["RGGGGGGGGGGGGGGG","RBRRRGRRRGRRRGRR","RBRRRGRRRGRRRGRR","RBRRGGGRGGGRGGGR","BRRRGGGRGGGRGGGR","BRRRGRRRGRRRGRRR","BRRRGGGRGGGRGGGR","RBRRGGGRGGGRGGGR","BRRRGGGRGGGRGGGR","BRRRGRRRGRRRGRRR","BGRRGGGRGGGRGGGR","RBRRGGGRGGGRGGGR"]
y=10; x=1; d=0
f="_2_R_R_1|_FgRgFgFg3rRr4b2_Fgb|_F_F_R|_2_L_r||"
// result:1

Aby wygenerować własny test, przejdź do układanki z listy na stronie robozzle.com , spróbuj ją rozwiązać (lub nie rozwiązać), naciśnij F12 w przeglądarce, wpisz w konsoli JS:

r=robozzle;s=JSON.stringify;with(r.level)console.log('a='+s(Items)+'\nc='+s(Colors)+'\ny='+RobotRow+'\nx='+RobotCol+'\nd='+RobotDir+'\nf='+s(r.encodeSolution()))

i ponownie sformatuj wynik dla swojego języka.

Najkrótsze wygrane. Bez luk.

code-golf grid interpreter ngn
źródło
1
Czy możemy użyć dowolnych odrębnych znaków do przedstawienia danych zamiast dostarczonych?
HyperNeutrino
1
Aby uzyskać odpowiedź APL na wyzwanie „Zapętlić”, możesz posortować ostatnią wartość kąta, zmniejszając złożoną wielkość.
user202729,
1
@ user202729 Uh, nie spodziewałem się komentarza na temat tego wyzwania tutaj :) Twój pomysł działa, dzięki! Spróbuję go wdrożyć, aby postać nie była zbyt haniebna.
ngn
1
Czy możemy traktować matryce znaków jako listę par lokalizacji i znaków?
0
1
@ 0 'Zasada, której tu przestrzegam (patrz także komentarz HyperNeutrino), to pozostawanie jak najbliżej formatu wejściowego faktycznie używanego na robozzle.com, więc obawiam się, że nie powinna to być lista par.
ngn

Odpowiedzi:

5

Prolog (SWI) , 574 bajty

Z*A:-findall(X^Y-D,(nth0(Y,Z,O),nth0(X,O,C),plus(32,C,D)),L),list_to_assoc(L,A).
N^C^G^[P,I|R]^F^X^Y^D:-map_assoc(\=(74),G);N<1e3,get_assoc(X^Y,G,J),J>67,put_assoc(X^Y,G,78,H),T=N+1,((I\=95,(P=95;get_assoc(X^Y,C,P)))->(between(49,53,I),plus(48,M,I),nth1(M,F,Q),append(Q,R,S),T^C^H^S^F^X^Y^D;member(I,`RL`),E is(D-I//3)mod 4,T^C^H^R^F^X^Y^E;I=70,(D=0,U is X+1;D=1,V is Y+1;D=2,U is X-1;D=3,V is Y-1),(U=X;V=Y),T^C^H^R^F^U^V^D;I>97,put_assoc(X^Y,C,I,W),T^W^H^R^F^X^Y^D);N^C^H^R^F^X^Y^D).
A+C+F+L:-A*G,C*B,split_string(F,"|","",P),maplist(string_codes,P,[M|N]),0^B^G^M^[M|N]^L.

Wypróbuj online!

Definiuje to predykat, który po wywołaniu powiedzie się, jeśli wszystkie gwiazdy zostaną pomyślnie zebrane, a inaczej nie powiedzie się. Orzecznik bierze argumenty takie jak: a+c+f+x^y^d.. ai cmuszą być listami ciągów cytowanych wstecznie, podczas gdy fmuszą być ciągami podwójnie cytowanymi.

Wyjaśnienie

Ten program zawiera trzy predykaty, */2, ^/2, i +/2. W */2orzeczniki który określa się na pierwszej linii odpowiada za część przetwarzania sygnału. ^/2Orzecznik rekurencyjnie oblicza jak robot porusza się krok po kroku, a jeśli uda robot prawnie zbiera wszystkie gwiazdy i nie inaczej. +/2Orzecznikiem jest głównym orzecznikiem programu i przygotowuje wejście do ^/2orzecznika z jakiejś pomocy od */2orzecznika. Zauważ, że każdy z tych predykatów technicznie wymaga tylko dwóch argumentów, ale używając operatorów i dopasowywania wzorców, mogą zachowywać się tak, jakby mieli więcej argumentów (omawiam to zjawisko bardziej szczegółowo tutaj ).

*/2

Z*A:-findall(X^Y-D,(nth0(Y,Z,O),nth0(X,O,C),plus(32,C,D)),L),list_to_assoc(L,A).

Ten predykat przyjmuje dwa argumenty. Pierwsza to lista kodów znaków (w ten sposób Prolog analizuje ciągi cudzysłowu). Drugi to mapa asocjacyjna od punktów na mapie 12x16 (reprezentowanych jako X^Y) do 32 plus kod znaku zapisany w tym punkcie na liście list kodów znaków. 32 jest dodawany do każdego z kodów znaków, dzięki czemu w matrycy kolorów zamieni wielkie i kolorowe litery na małe.

W ten sposób generuje listę par punktów i kodów znaków w tym punkcie, używając findall/3. Następnie używa list_to_assoc/2do utworzenia odpowiedniej mapy asocjacyjnej z punktów do kodu znaku w tym punkcie.

findall/3Orzecznikiem jest wbudowane wykonuje „szablon” jako pierwszy argument, cel jako drugi argument i listy jako jej trzeci argument. Predykat wypełnia listę wszystkimi możliwymi wartościami szablonu, które powodują sukces celu. Ze względu na pierwszeństwo operatora, szablon, który jest przekazywany do findall/3w */2jest analizowany jako (X^Y)-D. -Operator reprezentuje parę dwóch wartości w Prologu więc szablon reprezentuje położenie punktu w ( X^Y) w połączeniu z 32 plus point SA kodem znaków ( D). Zauważ, że ^użyte w reprezentacji punktu nie jest w żaden sposób związane z ^/2predykatem.

Rozważmy cel, który jest przekazywany do findall/3orzeczenia.

nth0(Y,Z,O),nth0(X,O,C),plus(32,C,D) % Note that the O (oh) is not a 0 (zero)

Cel zawiera trzy predykaty, z których każdy musi się powieść, aby cel się powiódł. nth0/3Orzecznikiem, który jest używany dwa razy jest używany, aby uzyskać wartość w określonym indeksem liście ( 0w nazwie wskazuje, że jest zerem indeksowane). Pierwsze wywołanie do niego przechowuje Yth wiersz macierzy znaków w, Opodczas gdy drugie wywołanie przechowuje Xth znak w tym rzędzie w C. Ostateczny predykat się plus/3powiedzie, jeśli jego dwa pierwsze argumenty sumują się z trzecim argumentem. Służy to do tego, aby kod znaku w parze był 32 większy niż kod znaku w matrycy znaków, który, jak wspomniano powyżej, zamieni wszystkie wielkie litery na małe.

Na koniec findall/3przechowuje wszystkie X^Y-Dkombinacje, które powodują, że jego cel odnosi sukces na liście, z Lktórej zbudowana jest mapa asocjacyjna.

Więcej wkrótce...

0 '
źródło
4

JavaScript (ES6), 298 276 264 bajtów

Zaoszczędzono 8 bajtów dzięki @ngn

Pobiera dane wejściowe jako (a,c,x,y,d,f), gdzie ai csą tablicami tablic znaków. Zwraca 0lub 1.

(a,c,x,y,d,f,k=1e3)=>(g=(F,p=0,s=f.split`|`[F],r=a[y])=>!k|!r|x&16||r[x]<'$'?2:/\*/.test(a)?(r[x]=o=0,(I=s[p+1],P=s[p])&&(P<'b'|P==c[y][x].toLowerCase()&&I!='_'&&k--?+I?o=g(I-1):I=='L'?d--:I=='R'?d++:I<'b'?y+=(d&=3,x-=~-d%2,2-d)%2:c[y][x]=I:0,o||g(F,p+2))):1)(0)&1

Przypadki testowe

Pokaż fragment kodu

Skomentował

(                                           // main function taking:
  a, c, x, y, d, f,                         //   - input variables
  k = 1e3                                   //   - k = instruction counter
) => (                                      //
  g = (                                     // g = recursive execution function, taking:
    F,                                      //   - F = subroutine id
    p = 0,                                  //   - p = instruction pointer
    s = f.split`|`[F],                      //   - s = instruction string
    r = a[y]                                //   - r = current row in a[]
  ) =>                                      //
    !k |                                    // if we've executed 1000 instructions
    !r | x & 16 ||                          // or we've felt out of the map
    r[x] < '$' ?                            // or we've reached a black square:
      2                                     //   exit with error code 2
    :                                       // else:
      /\*/.test(a) ? (                      //   if there are still some stars:
        r[x] = o = 0,                       //     mark the current cell as visited
        (I = s[p + 1], P = s[p]) &&         //     I = instruction, P = predicate
        (                                   //     if P is defined:
          P < 'b' |                         //       if the predicate is '_'
          P == c[y][x].toLowerCase()        //       or it matches the color of the cell
          && I != '_'                       //       and the instruction is not '_',
          && k-- ?                          //       then decrement k and:
            +I ?                            //         if I is '1' ... '5':
              o = g(I - 1)                  //           process call to subroutine
            :                               //         else:
              I == 'L' ?                    //           if I is 'L':
                d--                         //             turn left
              :                             //           else:
                I == 'R' ?                  //             if I is 'R':
                  d++                       //               turn right
                :                           //             else:
                  I < 'b' ? (               //               if I is not a color:
                    y += (                  //                 I must be 'F',
                      d &= 3,               //                 so make the bot advance
                      x -= ~-d % 2,         //                 by updating x
                      2 - d                 //                 and y
                    ) % 2                   //
                  ) :                       //               else:
                    c[y][x] = I             //                 paint the current cell
          :                                 //       else:
            0,                              //         do nothing
          o ||                              //       provided that o is equal to 0,
          g(F, p + 2)                       //       go on with the next instruction
        )                                   //     end of instruction execution
      ) :                                   //   else:
        1                                   //     success: return 1
  )(0) & 1                                  // initial call to the subroutine F1
Arnauld
źródło
x+='2101'[d&3]-1,y+='1210'[d&3]-1->d&=3,x+=(1-d)%2,y+=(2-d)%2
ngn
1
xzmienia się co najwyżej o 1, więc myślę, że można zastąpić x&~15zx&16
NGN
1

APL (Dyalog Classic) , 236 233 bajtów

-3 dzięki Erikowi Outgolfer

Teraz, gdy rozdałem bonus, zamieszczam przykładowe rozwiązanie mojego własnego wyzwania. Jest tu miejsce na ulepszenia - zachęcamy do kopiowania i gry w golfa dalej.

a c r d f←⎕⋄c←819⌶c⋄F←0,('|'=¯1⌽f)/⍳≢f⋄t←n←0
{~(⊂r)∊⍳⍴a:0⋄'#'=r⌷a:0⋄p q←2↑f↓⍨⊃⌽t⋄(_←p≡'|')∧×≢t:0⋄_:∇t↓←¯1⋄(⊃⌽t)+←2⋄~p∊'_',r⌷c:∇0⋄n+←1⋄n>999:0⋄(r⌷a)←'.'⋄~'*'∊a:1⋄r+←(q≡'F')×11 9○0j1*d⋄d+←4|'.R.L'⍳q⋄q∊'rgb':∇(r⌷c)←q⋄q∊⎕d:∇t,←F[⍎q]⋄∇0}0

Wypróbuj online!

Taki sam jak powyżej, rozszerzony o komentarze:

⎕io←0                   ⍝ 0-based indices (not counted in the score)
a c r d f←⎕             ⍝ decompose eval'ed input (⎕) into variables
c←819⌶c                 ⍝ make c lowercase
F←0,('|'=¯1⌽f)/⍳≢f      ⍝ split f at the '|'-s
t←n←0                   ⍝ t:stack, n:step counter
{                       ⍝ lambda
  ~(⊂r)∊⍳⍴a:0           ⍝ if the robot is off the map, return 0
  '#'=r⌷a:0             ⍝ if the robot is on a wall, return 0
  p q←2↑f↓⍨⊃⌽t          ⍝ current instruction - p:predicate, q:action
  (_←p≡'|')∧1≥≢t:0      ⍝ if at end of func and stack is empty, return 0
  _:∇t↓←¯1              ⍝ if at end of func, pop from stack and recurse
  (⊃⌽t)+←2              ⍝ increment program counter (top of stack)
  ~p∊'_',r⌷c:∇0         ⍝ if predicate doesn't match cell colour, recurse
  n+←1⋄n>999:0          ⍝ if too meany steps, return 0
  (r⌷a)←'.'             ⍝ consume star
  ~'*'∊a:1              ⍝ if no more stars left, return 1
  r+←(q≡'F')×11 9○0j1*d ⍝ if action is F, move forward
  d+←4|'.R.L'⍳q         ⍝ if action is L or R, turn left or right
  q∊'rgb':∇(r⌷c)←q      ⍝ if action is paint (r,g,b), do it
  q∊⎕d:∇t,←F[⍎q]        ⍝ if action is F1...F5, push on stack and recurse
  ∇0                    ⍝ action is nop (_), recurse
}0                      ⍝ call the lambda (argument will be ignored)
ngn
źródło
233 bajty
Erik the Outgolfer
@EriktheOutgolfer zmiana zastosowana, dzięki
ngn