Czy Gravity Guy to zrobi?

27

Gravity Guy to gra, w której jedynym wkładem użytkownika jest pojedynczy klawisz, który zmienia kierunek grawitacji. Biorąc pod uwagę poziom sztuki ASCII, ustal, czy Gravity Guy może dojść do końca.


Zasady

  • Początkowy kierunek grawitacji jest w dół .
  • Pierwsza kolumna danych wejściowych zawsze będzie zawierać tylko jedną # , od której zaczyna się Gravity Guy .
  • W każdej iteracji przechodzi do postaci bezpośrednio po jego prawej stronie .
  • Jeśli jego ścieżka jest zablokowana, a on porusza się do #, gracz przegrywa .
  • Po przeprowadzce gracz może opcjonalnie przełączać grawitację z dołu na górę lub z góry na dół.
  • Gravity Guy następnie przechodzi do następnego# (w bieżącym kierunku grawitacji).
  • Jeśli nie ma #na co wpadać, a on spadnie z pola , gracz przegrywa .
  • Jeśli Gravity Guy zejdzie z prawej strony siatki wejściowej, gracz wygrywa .

Przykład

Jeśli to była siatka wejściowa:

  ### 

#  # #
 ###  

Gravity Guy zaczynałby xsię w tych pozycjach po każdej iteracji. ^= przełączyć grawitację w górę i v= przełączyć grawitację w dół.

v                        ^                               v
-------------------------------------------------------------
  ###   |    ###   |    ###   |    ###   |    ###   |    ### 
x       |          |    x     |     x    |      x   |        
#  #    |  #x #    |  #  #    |  #  #    |  #  #    |  #  # x
 ### #  |   ### #  |   ### #  |   ### #  |   ### #  |   ### #

Jak widać, przełączając grawitację w tych czasach Gravity Guy osiąga koniec, więc to wejście zwróci prawdziwą wartość.

Dane techniczne

  • Siatka wejściowa może być w dowolnym odpowiednim formacie „siatka” (ciąg wielowierszowy wypełniony spacjami, tablica ciągów linii, tablica znaków itp.).
  • Jeśli jest to możliwe dla gracza, aby wygrać poziomie, wyjście na truthywartość. Jeśli nie, wpisz falseywartość.
  • Szerokość i wysokość siatki będą 50najwyżej znakami.
  • To , niech wygra najkrótszy kod w bajtach!

Przypadki testowe

(każdy przypadek oddzielony ----------dowolnymi pustymi liniami należy również uzupełnić spacjami)

Prawdziwe

 #########   ########      ######     ######    
          #  #       #    #      #   #      #   
###    #   # #    #   #  #       #  #        #  
  #    ##  # #    ##  # #     # #  #      ##    
  #    #   # #    #   # #    #     #     #######
  #       #  #       #  #     ###  #          # 
  #    ##    #    ##     #       #  #         # 
  #    #          #              #        #   # 
  #    ####################################   # 
  #                                           # 
  ############################################# 

----------


###

----------

   #####

####    

----------

 #####
 # # #

# # # 
 #####

----------

   ############   

######      ######

   ############   

----------

  ###   ###  
     # #     
####  #  ####
    #   #    
     # #     
      #      

----------

    ######  
   #        
 ##         
     #######
###     #   
   #    #   
    #####   


----------

    #####   
   #    #   
 ##     #   
     #######
###         
   #        
    ######  

----------

  ### 

#  # #
 ###  

----------

  ###  ###

###     ##
   #    # 
    ##### 

----------

  #        
     #   # 
       #   
#   #     #
        #  
   #       
      #    
 #         

----------

    ##### ####   
   #     #    #  
  #   # #  ##  # 
             #  #
#####  ####   #  
               # 
     #########   

----------

 ########################### 
 #   #   #   #     #   #   # 
 # # # #   #   # #   #   # # 
 # # # ######### ########### 
 # # # #  #       #     #  # 
   # # # ## ##### ### #      
## #   #    #          ## ###
 # ##### #### ###########  # 
 # #     #  #     #     ## # 
 # # #####  ### # # # # #  # 
 #              #   # #   ## 
 ########################### 

Fałszywe

 ###
   #
####

----------


### ###

----------

    #   
 ### ###

#### ###
    #   

----------

  ###     ###  
     # # #     
####  # #  ####
    #     #    
     #   #     
      # #      
       #       

----------

  ####### 
  #     # 
 ## ##### 

### ######
  #     # 
  ####### 

----------

 ########################### 
 #   #   #   #  #  #   #   # 
 # # # #   #   # #   #   # # 
 # # # ######### ########### 
 # # # #  #       #     #  # 
   # # # ## ##### ### #      
## #   #    #          ## ###
 # ##### #### ###########  # 
 # #     #  #     #     ## # 
 # # #####  ### # # # # #  # 
 #              #   # #   ## 
 ########################### 
użytkownik 81655
źródło
Czy dozwolona jest siatka w formacie kolumnowym?
Neil,
@ Neil Masz na myśli transponowaną / obróconą tablicę? Powiem „nie”, ponieważ zmienia to wejście. Ale jeśli twój język ma specjalny columntyp, to byłoby OK do użycia.
user81655
Czy jest możliwe, aby #pierwsza kolumna znajdowała się w pierwszym rzędzie?
feersum
@feersum Nie, możesz założyć, że siatka będzie zawierać przestrzeń, w której Gravity Guy może „stać”.
user81655
Wstyd; transpozycja zwiększa liczbę moich bajtów o 20%.
Neil,

Odpowiedzi:

19

Ślimaki , 15 bajtów

Wypróbuj online?

^
\ n\ ,=\#r}+~

0. ^jest opcją, która wymaga, aby wzorzec zaczynał się w lewym górnym rogu.

  1. \ ​: dopasuj miejsce

  2. n: Obróć o 90 stopni w dowolnym kierunku

  3. \ ,​: dopasuj spację zero lub więcej razy

  4. =\#sprawdź, czy jest #przed nami

  5. r: ustaw kierunek w prawo

  6. }+: wykonaj wszystkie poprzednie jeden lub więcej razy

  7. ~ dopasuj komórkę, która jest poza granicami siatki

feersum
źródło
Daje to 0 dla większości prawdziwych przypadków testowych
Bassdrop Cumberwubwubwub
@Bas Czy wypełniłeś puste linie spacjami?
Martin Ender
@ MartinBüttner Bezpośrednio skopiowałem niektóre dane wejściowe, w ten sposób rzeczywiście usunąłem niektóre spacje. Rzeczywiście działa po dodaniu spacji
Bassdrop Cumberwubwubwub
5
Ponieważ nikt jeszcze tego nie powiedział: To jest niesamowite!
DLosc
9

Perl, 93 89 81 77 76 75 74 bajtów

Obejmuje +2 za -0p

Uruchom ze wzorcem wejściowym (ze wszystkimi wierszami wypełnionymi spacją na tej samej długości) na STDIN:

gravity.pl < gravity.txt

gravity.pl:

#!/usr/bin/perl -0p
/
/;$n=".{@-}";s/#$n\K( $n)*\b |(^|w)([w ]$n)*\K $n#/w|$&/es&&redo;$_=m;w

Ta wersja oparta na plikach wymaga ostatniego nowego wiersza, czyli tak naprawdę 75 bajtów. Ale wersja oparta na linii poleceń nie potrzebuje tej nowej linii, więc liczy się to jako 74 bajty:

perl -0pe '/
/;$n=".{@-}";s/#$n\K( $n)*\b |(^|w)([w ]$n)*\K $n#/w|$&/es&&redo;$_=m;w' < gravity.txt

Wyjaśnienie:

Spowoduje to skonstruowanie sznurka z wgrawitacją w każdej pozycji, jaką facet może osiągnąć. Tak więc od drugiego do ostatniego zgodnego z prawdą przykładu zbuduje:

     #########   
    ##### ####   
   #wwwww#wwww#  
  #w  # #w ##ww# 
wwwww wwwwwww#ww#
#####  ####  w#ww
     wwwwwwwwww# 
     #########   

Facet z grawitacją może to zrobić tylko wtedy, gdy jest ww ostatniej kolumnie. Sznurek zostanie zbudowany przez zastąpienie jednego dostępnego miejsca ww każdej rundzie.

Każda wymiana będzie miała formę

s/prefix \K space postfix/ w | $& /e

który będzie wymagał, aby spacja była poprzedzona prefiksem, a po niej postfiksem, ale zastąpi tylko spację wbez potrzeby dużej ilości zaawansowanego grupowania.

Załóżmy, że $nzawiera wyrażenie regularne, które będzie się rozwijało na tyle, że lewa i prawa strona będą dokładnie pod sobą. Odpowiednie wyrażenia regularne to:

/^( $n)*\K $n#/       From the first position drop down as long as you
                      encounter spaces until you encounter a #. 
                      This puts gravity guy on his starting platform

/#$n\K( $n)*\b /      A space immediately below a # and if you (optionally)
                      go down further from there (as as the descent is
                      over spaces) you get to a space that follows a word
                      boundary. The only way to get a word boundary is if 
                      there is a w in front of that space. This selects the
                      position gravity guy ends up on if starting from that
                      w and gravity is up
/w([w ]$n)*\K $n#/    A w followed by a space (or w) and if you go down from
                      there as long as it is over spaces (or w) you finally
                      end up on a space directly above a #. This handles the
                      gravity down case. The test uses "space or w" instead
                      of just space to handle this case:

                       #
                      ww
                      #x  
                       #

                      Position x is currently a space and must be replaced by a
                      w but the gravity up regex has already put a w directly
                      after the w gravity guy takes off from. So for gravity
                      down we must handle w as if it is still a space. This
                      is not needed for gravity up because regex always matches
                      starting at the earliest possible character, so 
                      gravity up matches before gravity down

Dzięki temu program jest prosty:

#!/usr/bin/perl -0p   Slurp all of STDIN into $_, at the end print $_

/\n/                  Match the first newline (needed to measure the row
                      length)
$n=".{@-}"            $n effectively becomes rowlength-1 times ".". This
                      will be the regex that goes one step down a column

s/#$n\K( $n)*\b |(^|w)([w ]$n)*\K $n#/w|$&/es

                     This is the 3 regexes shown above combined. The s 
                     modifier is needed so the . in $n also matches newline

    &&redo           Keep looping as long as w's keep getting added

$_=m;w\n;            Check if the last column contains a w: He made it!
                     The \n; at the end is not written. These 2 bytes sneakily
                     come from the -p option for the ; and the -e option
                     for the \n
Ton Hospel
źródło
3

JavaScript (ES6), 174 bajty

a=>[...a[0]].map((_,i)=>[...t].map(x=>s[x]<'#'&&g(s.indexOf('#',x),-1)&&g(s.lastIndexOf('#',x),1),s=a.map(s=>s[i]),t=new Set),t=new Set([0]),g=(i,d)=>i<0||t.add(i+d))&&t.size

Pobiera poziomy ciąg ciągów i zwraca liczbę punktów wyjścia. Transpozycja tablicy kosztuje mnie 29 bajtów. Nie golfowany:

function gravity(array) {
    var set = new Set;
    set.add(0); // starting point
    for (var i = 0; i < array[0].length; i++) {
        var s = array.map(s => s[i]); // transpose array
        var old = set;
        set = new Set;
        for (var x of old) {
            if (s[x] == '#') continue; // hit wall
            var j = s.indexOf('#', x); // try downward gravity
            if (j >= 0) set.add(j - 1);
            j = s.lastIndexOf('#', x); // try upward gravity
            if (j >= 0) set.add(j + 1);
        }
    }
    return set.size;
}
Neil
źródło
3

Pip , 85 68 62 59 + 1 = 60 bajtów

Używa -rflagi do odczytu wszystkich linii standardowego wejścia.

FcZg{YlFxiIc@xQsyPB(Jc@<x@?`# *$`)+1PB(c@>x@?'#)+x-1i:UQy}i

Wypróbuj online!

Krótkie wyjaśnienie

Strategia jest zasadniczo szerokim wyszukiwaniem. Transponujemy dane wejściowe i pętlę nad liniami (kolumnami), zachowując listę pozycji Y, które gracz może osiągnąć w tej kolumnie. Wyjście po ostatniej kolumnie jest niepustą listą, jeśli gracz może wygrać, lub pustą listą (która drukuje się jako końcowa nowa linia), jeśli gracz przegra.

Pełne wyjaśnienie

Wbudowany w zmiennych wykorzystywanych w tym programie: i == 0, l == [], s == " ".

-rFlag umieszcza listę linii wejścia język g. FcZg{...}zamki gi pętle nad każdą kolumną c. (Unary Z, po zastosowaniu do listy iterowalnych, działa jak Python zip(*g), porządnie transponując tablicę 2D.) Zauważ, że cbędzie to lista, a nie ciąg znaków.

Wewnątrz pętli kolumny resetujemy ysię do pustej listy przez Yanking l. Fxizapętla się i. W późniejszych iteracjach ipojawi się lista współrzędnych y, do których gracz był w stanie dotrzeć w poprzedniej kolumnie. Za pierwszym razem chcemy zacząć od 0(lewy górny róg). Zmienna jest wstępnie zainicjalizowana na Skalar 0, a nie na Listę [0], ale Pip iteruje po niej w porządku.

Dla każdej prawidłowej pozycji w ostatniej kolumnie Ic@xQssprawdza, czy w tej pozycji jest spacja w bieżącej kolumnie. Jeśli nie, gracz po prostu wpadł na ścianę i przechodzimy do następnej możliwości. Jeśli tak, to chcemy znaleźć pozycje, na które gracz spadnie w tej kolumnie dla każdego kierunku grawitacji, i dodać je do listy yza pomocą operatora Push Back.

Grawitacja w górę (w lewo, w wersji transponowanej):

(Jc@<x@?`# *$`)+1
  c@<x             Slice everything left of x in the column
 J                 Join into a string so we can do a regex search on it
      @?`# *$`     Find index of the last # in this string
(             )+1  The player's index is the space below/to the right of this #

Grawitacja spada (w prawo, w wersji transponowanej):

(c@>x@?'#)+x-1
 c@>x              Slice everything right of x in the column
     @?'#          Find index of the first # in this list (no need to join into string)
(        )+x       Translate to index number in entire column
            -1     The player's index is the space above/to the left of this #

Jeśli gracz spadnie z siatki w określonym kierunku, odpowiednia @?operacja nie znajdzie znaku #i da zero. To nie jest poprawny indeks i wygeneruje ostrzeżenia w następnej iteracji - które jednak nie są widoczne bez -wflagi. Dla naszych celów przypadki te są zasadniczo wykluczone z rozpatrzenia.

Po wewnętrznej pętli i:UQybierze listę yzbudowanych przez nas pozycji, eliminuje duplikaty i przypisuje ją i. (Eliminowanie duplikatów jest konieczne, ponieważ w przeciwnym razie lista będzie się wykładniczo wykładniczo.) Następnie przechodzimy do następnej kolumny. Gdy przejdziemy przez wszystkie kolumny, jeśli istnieje prawidłowa ścieżka, ipojawi się niepusta lista pozycji (prawda); jeśli nie, będzie to pusta lista (falsey).

DLosc
źródło