Wprowadzenie
To wyzwanie jest podobne do problemów z Project Euler . Wymyśliłem to, ponieważ grałem w zwodniczo prostą grę planszową i nie mogłem znaleźć skutecznego rozwiązania, aby odpowiedzieć na proste pytanie dotyczące jej mechaniki.
Quarto to zabawny wariant 4 z rzędu. Gra się na planszy 4 na 4 z 16 unikalnymi elementami (żadne elementy nie są powielane). W każdej turze każdy gracz kładzie 1 pionek na planszy. Każdy element ma 4 cechy binarne (krótki / wysoki, czarny / biały, kwadratowy / okrągły, pusty / pełny). Celem jest wykonanie czterech z rzędu, poziomo, pionowo lub wzdłuż 2 przekątnych, dla dowolnej z czterech cech! Więc 4 czarne kawałki, 4 białe kawałki, 4 wysokie kawałki, 4 krótkie kawałki, 4 kwadratowe kawałki, 4 okrągłe kawałki, 4 puste kawałki lub 4 solidne kawałki.
Zdjęcie powyżej pokazuje ukończoną grę, cztery z rzędu z powodu 4 kwadratowych elementów.
Wyzwanie
W Quarto niektóre gry mogą zakończyć się remisem.
Całkowita liczba możliwych pozycji końcowych wynosi 16!
około 20 trylionów.
Ile z tych pozycji końcowych to remisy?
Zasady
Rozwiązaniem musi być program, który oblicza i generuje całkowitą liczbę losowanych pozycji końcowych. Poprawna odpowiedź to
414298141056
Możesz używać wyłącznie informacji o regułach gry, które zostały wydedukowane ręcznie (bez dowodu wspomaganego komputerowo).
Matematyczne uproszczenia problemu są dozwolone, ale należy je wyjaśnić i udowodnić (ręcznie) w swoim rozwiązaniu.
Zwycięzca jest tym, który ma najbardziej optymalne rozwiązanie pod względem czasu działania procesora.
Aby wyłonić zwycięzcę, uruchomię każde rozwiązanie ze zgłoszonym czasem pracy poniżej 30 m na MacBooku Pro 2,5 GHz Intel Core i7 z 16 GB pamięci RAM .
Brak punktów bonusowych za wymyślenie rozwiązania, które działa również z innymi rozmiarami plansz. Mimo że byłoby miło.
W stosownych przypadkach program musi się skompilować w ciągu 1 minuty na sprzęcie wymienionym powyżej (aby uniknąć nadużyć związanych z optymalizacją kompilatora)
Domyślne luki są niedozwolone
Zgłoszenia
Proszę pisać:
- Kod lub link github / bitbucket do kodu.
- Dane wyjściowe kodu.
- Twój lokalnie mierzony czas działania
- Wyjaśnienie twojego podejścia.
Ostateczny termin
Termin nadsyłania zgłoszeń upływa 1 marca, więc wciąż jest dużo czasu.
Odpowiedzi:
C: 414298141056 losuje w około
52,5 minuty.Proste wyszukiwanie z głębokością z tabelą transpozycji uwzględniającą symetrię. Używamy symetrii atrybutów w permutacji i 8-krotnej symetrii dwuściennej płytki.
Zmierzony wynik (@wvdz):
Wynik (użytkownik + sys): 1m35,727s
źródło
-O3 -march=native
i dostałem 1m48s na mojej maszynie. (CC @wvdz)Java, 414298141056 losuje, 23m42.272s
Mam nadzieję, że opublikowanie rozwiązania własnego wyzwania nie jest dla niego niezadowolone, ale powodem, dla którego opublikowałem to wyzwanie, było to, że doprowadziłem mnie do szału, że sam nie mogłem znaleźć skutecznego rozwiązania. Wykonanie mojej najlepszej próby zajęłoby kilka dni.
Po przestudiowaniu odpowiedzi użytkownika 1502040 udało mi się zmodyfikować kod, aby działał w dość rozsądnym czasie. Moje rozwiązanie jest wciąż zupełnie inne, ale ukradłem kilka pomysłów:
Główną różnicą między tym rozwiązaniem a użytkownikiem 1502040 jest to, że nie używam tabeli Zobrist, ale kanoniczną reprezentację tablicy, gdzie uważam, że każda tablica ma 48 możliwych transpozycji względem cech (2 * 4!). Nie obracam ani nie transponuję całej planszy, a jedynie cechy poszczególnych elementów.
To najlepsze, co mogłem wymyślić. Najbardziej pożądane są pomysły na oczywiste lub mniej oczywiste optymalizacje!
Zmierzony wynik:
Wynik (użytkownik + sys): 23m42.272s
źródło