Mogłem znaleźć tylko wyzwania związane z golfem dla Mastermind, więc oto wersja z wyzwaniem dla kodu, którą chciałbym wziąć na siebie.
Optymalną strategię dla normalnej gry Mastermind, MM (4,6), odkryli Koyama i Lai w 1993 r., Mając średnią # domysłów = 5625/1296 ~ 4,34. MM (5,8) jest nadal nierozwiązane, ale szacuje się, że ma średnią # domysłów ~ 5,5.
Twoim zadaniem jest stworzenie strategii MM (5,8), czyli dla 5 dołków i 8 kolorów, obejmującej wszystkie pow(8,5) = 32768
możliwe odrębne rozwiązania. Oczywiście nie musi być optymalny. Masz dwie możliwości:
- Opublikuj program deterministyczny, który generuje strategię. Program musi być kompilowany / uruchamialny w systemie Windows 7, Mac OS X lub Linux bez dodatkowego niewolnego oprogramowania.
- Opublikuj swoją strategię (wraz z nazwą StackExchange) gdzieś w Internecie i opublikuj adres URL tutaj.
W obu przypadkach wpisz wynik (patrz poniżej) w nagłówku odpowiedzi.
Strategia musi być zakodowana zgodnie z następującą gramatyką:
strategy : guessing-strategy | known-solution-strategy
guessing-strategy : '{' guess ':' branches '}'
known-solution-strategy : guess
guess : color color color color color
color : 'A'..'H'
branches : '{' branch (',' branch)* '}'
branch : reply ':' strategy
reply : number-of-blacks number-of-whites
number-of-blacks : number-of-key-pegs
number-of-whites : number-of-key-pegs
number-of-key-pegs : '0'..'5'
Algorytm używany do decydowania o liczbie czarnych / białych kołków jest opisany w http://en.wikipedia.org/wiki/Mastermind_(board_game)
Zauważ, że odpowiedź „50” (tj. Prawidłowe odgadnięcie) jest domyślna i nie stanowi części gramatyki.
Punktacja: N = suma liczby domysłów dla każdej z 32768 ścieżek / rozwiązań. Wygrywa strategia z najniższą liczbą N. Pierwszy remis: najniższa maksymalna liczba odgadnięć. Drugi remis: pierwsza opublikowana odpowiedź. Konkurs kończy się 1 sierpnia 2014 r. 0:00 GMT .
Przykład strategii dla MM (2,3) z wynikiem = 21:
{AB:{10:{AC:{10:AA,01:CB,00:BB}},02:BA,01:{BC:{01:CA}},00:CC}}
Korzystając z tej strategii, 9 możliwych gier będzie wyglądać następująco:
- AB 20
- AB 10, AC 20
- AB 10, AC 10, AA 20
- AB 10, AC 01, CB 20
- AB 10, AC 00, BB 20
- AB 02, BA 20
- AB 01, BC 20
- AB 01, BC 01, CA 20
- AB 00, CC 20
Wkrótce opublikuję dla Twojej wygody weryfikator strategii MM (5,8) oparty na Javie.
źródło
{AB:{10|01:BB}}
? Mam odpowiedź, ale jest dość naiwna, a ze względu na strukturę drzewa gramatyki wcale nie skaluje się dobrze (4 dziury, 3 kolory, generuje strategię 147 MB, którą mogłem znacznie zmniejszyć , łącząc części drzewo).Odpowiedzi:
Jawa
Mój algorytm dla MM (5,8) ocenia
177902178006182798182697 z maksymalną głębokością89 i potrzebuje tylko kilku sekund (na moim wolnym komputerze).Przykładowy wynik strategii dla MM (2,3) z wynikiem = 21 znaleziony przez ten algorytm wygląda następująco:
Z moim algorytmem nie ma nic ekscytującego. Bez wynalazku. Właśnie śledziłem przepisy znalezione w sieci i skompresowałem je do tego kodu Java. Jedyną optymalizacją, jaką zrobiłem, jest próba zoptymalizowania linii kodu (w pewien sposób). Wygląda to tak:
@MrBackend: Chyba napisanie weryfikatora jest trudne. ;-)
Kilka uwag:
Strategię
MM(5,8)
można znaleźć tutaj . GitHub ma pewne problemy z wyświetlaniem długich linii, więc kliknij przycisk Raw .źródło
Rubin
EDYCJA: Dodano pewną logikę, aby wykluczyć niemożliwe domysły. Dlatego strategie są teraz zgodne z danym formatem i są o wiele łatwiejsze do zarządzania.
Oto jedna próba uruchomienia tego. Jest dość naiwny (i mało czytelny - pomaga czytać gałąź if / elsif / else od dołu do góry).
Po pierwsze, staram 5 z każdego koloru:
AAAAA
,BBBBB
, itd. Od tego rysunku I na jakie kolory są rzeczywiście używane we wzorcu. A potem po prostu próbuję wszystkich permutacji podanych kolorów, pomijając te, które zostały już wykluczone przez czarne kołki.Oto
MM(2,3)
strategia:Strategia
MM(5,8)
zajmuje 376 KB i można ją znaleźć tutaj . GitHub ma pewne problemy z wyświetlaniem długich linii, więc kliknij przycisk Raw .Teraz, jeśli otrzymam weryfikator, mogę również powiedzieć, jaki jest mój rzeczywisty wynik. :)
źródło