Zagrajmy w chowanego!


12

Użytkownik ukryje się, a komputer spróbuje je znaleźć.

Najpierw program pobierze dane wejściowe dotyczące wielkości siatki. Jak 5x5, 10x10, 15x15 itd. Siatka nie zawsze będzie idealnym kwadratem.

Siatka przypomina swego rodzaju szachownicę:

_______________________________
|     |     |     |     |     |
| A1  |     |     |     |     | A
|_____|_____|_____|_____|_____|
|     |     |     |     |     |
|     | B2  |     |     |     | B
|_____|_____|_____|_____|_____|
|     |     |     |     |     |
|     |     | C3  |     |     | C
|_____|_____|_____|_____|_____|
|     |     |     |     |     |
|     |     |     | D4  |     | D
|_____|_____|_____|_____|_____|
|     |     |     |     |     |
|     |     |     |     | E5  | E
|_____|_____|_____|_____|_____|
   1     2     3     4     5

Teraz użytkownik wybierze kwadrat, taki jak B2 (bez powiadamiania komputera)

Komputer zacznie zgadywać kwadraty. Jeśli wybierze właściwy kwadrat, użytkownik odpowie za pomocąy . Jeśli nie, wprowadzą kierunek, w którym znajduje się ich kafelek od wybranego (N, NE, E, SE, S, SW, W).

Więc jeśli użytkownik wybrał B2, a komputer zgadłC3 , użytkownik wprowadziłby dane NW.

Oto przykład danych wyjściowych i wejściowych:

Grid?
5x5

C3?
NW

C2?
N

B2?
y

Punktacja:

To będzie punktowane nieco inaczej niż normalne wyzwanie.

Zwycięzcą jest program, który przyjmuje najmniejszą liczbę zgadnięć (średnio), potrzebną do odgadnięcia właściwego kwadratu. Przypadki testowe, które należy uśrednić, to wszystkie możliwe kwadraty w 5 x 5, a następnie w 10 x 10.

Musi jednak działać również z każdym wzorem siatki do 26 rzędów (tj. 5x8, 6x2, 20x5 itp.).

Podaj sposób jego przetestowania, na przykład JSFiddle.

I na koniec, w przypadku remisu, wygrywa najkrótszy program.


1
Jeśli się chowam, A1a komputer zgaduje B9, czy to właściwa odpowiedź, NWczy W?
Greg Martin

@GregMartin To byłoby NW .... N, W, S, E muszą być proste, podczas gdy wszystko w innym wierszu / kolumnie musi być NW, NE, SW, SE
JKonowitz

Czy istnieje elastyczność w określonym formacie wejścia i wyjścia? Jeśli jest więcej niż 26 wierszy, jak się nazywają?
Greg Martin

@GregMartin Możesz być elastyczny w kwestii wyników, ale postaraj się zachować prostotę. Nie musi być dokładnie taki sam, ale powinien mieć podobny styl. Nie musisz brać pod uwagę niczego powyżej 26, ja to wyedytuję.
JKonowitz

Nie wiem, co znaczy „podobny styl”. Czy możemy przyjmować dane wejściowe jako uporządkowaną parę liczb całkowitych (wiersz nr, kolumna nr)? (PS: Tego rodzaju pytania są powodem, dla którego wyzwania związane z publikowaniem postów w piaskownicy są świetnym pomysłem.)
Greg Martin

Odpowiedzi:


3

Python 3.6 , 466 398 392 bajtów, minimax

x, y = 1, 1
w, h = [int(x) for x in input('Grid?\n').split('x')]


def split_factor(a, b):
    N = b-y
    W = a-x
    S = h+~N
    E = w+~W
    return max(1, N, W, S, E, N*W, S*W, S*E, N*E)


def move(a, b):
    *Z, = zip([a, x, a, a+1, x, x, a+1, a+1],
              [y, b, b+1, b, y, b+1, b+1, y],
              [1, a-x, 1, w+x+~a, a-x, a-x, w+x+~a, w+x+~a],
              [b-y, 1, h+y+~b, 1, b-y, h+y+~b, h+y+~b, b-y])
    return Z[['N', 'W', 'S', 'E', 'NW', 'SW', 'SE', 'NE'].index(d)]

d = ''
while d != 'y':
    print()
    splits = {(a, b): split_factor(a, b) for a in range(x, x+w) for b in range(y, y+h)}
    a, b = min(splits, key=splits.get)
    d = input(f'{a}{"ABCDEFGHIJKLMNOPQRSTUVWXYZ"[b]}?\n')
    x, y, w, h = move(a, b)

Dane wejściowe i wyjściowe powinny mieć formę pokazaną w przykładzie. Znajduje kwadrat z minimalnym „współczynnikiem podziału” - który jest największym pozostałym obszarem, który może wynikać z odpowiedzi gracza (tj. NW, E, y itd.) - i zgaduje. Tak, to zawsze jest środek pozostałego obszaru w tej grze, ale ta technika minimalizacji najgorszego przypadku będzie działać bardziej ogólnie w podobnych grach z różnymi zasadami.

Nieczytelna wersja:

x=y=d=1
w,h=map(int,input('Grid?\n').split('x'))
while d!='y':print();s={(a,b):max(b-y,h+y+~b)*max(w+x+~a,a-x)for a in range(x,x+w)for b in range(y,y+h)};a,b=min(s,key=s.get);d=input(f'{a}{chr(64+b)}?\n');*z,=zip([a+1,x,a+1,x,a,a,a+1,x],[b+1,b+1,y,y,b+1,y,b,b],[w+x+~a,a-x,w+x+~a,a-x,1,1,w+x+~a,a-x],[h+y+~b,h+y+~b,b-y,b-y,h+y+~b,b-y,1,1]);x,y,w,h=z[~'WENS'.find(d)or-'NWNESWSE'.find(d)//2-5]

2

Matematyka, optymalne zachowanie przypadków testowych, 260 bajtów

For[a=f=1;{c,h}=Input@Grid;z=Characters;t=<|Thread[z@#->#2]|>&;r="";v=Floor[+##/2]&;b:=a~v~c;g:=f~v~h,r!="y",r=Input[g Alphabet[][[b]]];{{a,c},{f,h}}={t["NSu",{{a,b-1},{b+1,c},{b,b}}]@#,t["uWX",{{g,g},{f,g-1},{g+1,h}}]@#2}&@@Sort[z@r/.{c_}:>{c,"u"}/."E"->"X"]]

Ten program można przetestować, wycinając i wklejając powyższy kod do chmury Wolfram . (Testuj jednak szybko: Myślę, że istnieje limit czasowy dla każdego uruchomienia programu.) Zgadnięcia programu wyglądają 2 czamiast C2, ale w przeciwnym razie działają zgodnie z powyższą specyfikacją. Siatka musi być wprowadzana jako uporządkowana para liczb całkowitych itp. {26,100}, A odpowiedzi na domysły programu muszą być wprowadzane jako ciągi znaków, takie jak "NE"lub "y".

Program śledzi najmniejszy i największy numer wiersza i numeru kolumny, który jest zgodny z dotychczasowymi danymi wejściowymi i zawsze zgaduje punkt środkowy podsiatki możliwości (zaokrąglanie NW). Program jest deterministyczny, więc łatwo jest obliczyć liczbę domysłów, których wymaga średnio na stałej siatce. Na siatce 10x10 program wymaga 1 zgadywania dla pojedynczego kwadratu, 2 zgadywania dla ośmiu kwadratów, 3 zgadywania dla 64 kwadratów i 4 zgadywania dla pozostałych 27 kwadratów, średnio 3,17; i jest to teoretyczne minimum, biorąc pod uwagę, ile sekwencji 1 zgadnij, 2 zgadnij itd. może prowadzić do poprawnych domysłów. Rzeczywiście, program powinien osiągnąć teoretyczne minimum na dowolnej siatce rozmiarów z podobnych powodów. (Na siatce 5x5 średnia liczba domysłów wynosi 2,6.)

Małe wyjaśnienie kodu, chociaż jest całkiem proste, inne niż gra w golfa. (Wymieniłem kolejność niektórych instrukcji inicjujących do celów ekspozycyjnych - bez wpływu na liczbę bajtów).

1  For[a = f = 1; z = Characters; t = <|Thread[z@# -> #2]|> &;
2      v = Floor[+##/2] &; b := a~v~c; g := f~v~h;
3      r = ""; {c, h} = Input@Grid, 
4    r != "y", 
5    r = Input[g Alphabet[][[b]]];
6      {{a, c}, {f, h}} = {t["NSu", {{a, b - 1}, {b + 1, c}, {b, b}}]@#, 
7        t["uWX", {{g, g}, {f, g - 1}, {g + 1, h}}]@#2} & @@ 
8        Sort[z@r /. {c_} :> {c, "u"} /. "E" -> "X"]
   ]

Linie 1-3 inicjują Forpętlę, która w rzeczywistości jest tylko Whileukrytą pętlą, więc hej, dwa mniej bajtów. Możliwe zakresy numerów wierszy i numerów kolumn w dowolnym momencie są przechowywane {{a, c}, {f, h}}, a wyśrodkowane zgadywanie w tej podsiatce jest obliczane przez funkcje {b, g}zdefiniowane w wierszu 2. Wiersz 3 inicjuje maksimum wiersza ci maksimum kolumny na hpodstawie danych wprowadzonych przez użytkownika, oraz inicjuje również rzmienną testowaną w pętli, a także kolejne dane wejściowe użytkownika.

Podczas gdy test na linii 4 jest spełniony, linia 5 otrzymuje dane wejściowe od użytkownika, gdzie monit pochodzi z bieżącej domysły {b, g}( Alphabet[][[b]]]konwertuje numer wiersza na literę). Następnie linie 6-8 aktualizują podsiatkę możliwości (i domyślnie następną przypuszczenie). Na przykład t["NSu", {{a, b - 1}, {b + 1, c}, {b, b}}](biorąc pod uwagę definicję tw wierszu 1) rozwija się do

<| "N" -> {a, b - 1}, "S" -> {b + 1, c}, "u" -> {b, b}|>

gdzie można zobaczyć, że numery wierszy min i wierszy są aktualizowane zgodnie z ostatnim wejściem użytkownika. Wiersz 8 konwertuje wszelkie możliwe dane wejściowe na uporządkowaną parę znaków formularza { "N" | "S" | "u", "u" | "W" | "X"}; tutaj "u"oznacza prawidłowy wiersz lub kolumnę i "X"oznacza wschód (tylko po to, Sortaby ładnie pracować). Kiedy użytkownik w końcu wprowadza dane "y", wiersze te generują błąd, ale test pętli kończy się niepowodzeniem, a błąd nigdy nie jest propagowany (program i tak po prostu zatrzymuje się).


0

Partia, dziel i rządź

@echo off
set z = ABCDEFGHIJKLMNOPQRSTUVWXYZ
set /p g = Grid?
set /a w = 0, n = 0, e = %g :x= + 1, s = % + 1
:l
set /a x = (w + e) / 2, y = (n + s) / 2
call set c = %%z :~%y%,1%%
set /p g = %c %%x%?
if %g :w=.% == %g % set /a w = x
if %g :n=.% == %g % set /a n = y
if %g :e=.% == %g % set /a e = x
if %g :s=.% == %g % set /a s = y
if %g :y=.% == %g % goto l

Działa, tworząc obwiednię obszaru, który ma być nadal przeszukiwany. Następne przypuszczenie jest zawsze środkiem pudełka. W przypadku punktów kompasu, które nie zostały uwzględnione w odpowiedzi, pole jest zmniejszane w tym kierunku. Na przykład dla odpowiedzi Nlewy, prawy i dolny bok pola są ustawione na odgadnięty kwadrat.

Przy 369 bajtach nie spodziewam się nikogo pokonać, więc zostawiłem wolne miejsca dla czytelności.


Cóż, funkcja dziel i zwyciężaj jest ogólnie przydatna w przypadku dużych przypadków testowych, ale nie w przypadku małych przypadków, czy są jakieś lepsze algorytmy?
Matthew Roh

@SIGSEGV Nie wiesz, co masz na myśli; Odpowiedzi Grega i Bena również wykorzystują metodę środka pola.
Neil

Nadal potrzebujemy lepszego algorytmu.
Matthew Roh

@SIGSEGV Metoda środka pola jest optymalna. Nie ma lepszego algorytmu.
TheNumberOne
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.