W grze Freecell Twoim zadaniem jest zbudowanie czterech stosów fundamentów w kolorze od asa do króla, w układzie, w którym budujesz w dół w naprzemiennych kolorach. Możesz jednak zbudować tylko jedną kartę na raz, więc otrzymujesz cztery „wolne komórki”, z których każda może zawierać jedną kartę, aby pomóc Ci przenieść całe sekwencje. Chodzi o to, aby wplatać i wyjmować pojedyncze karty z wolnych komórek zgodnie z wymaganiami, aby pomóc ci rozwiązać grę.
Twoim zadaniem jest zbudowanie programu, który rozwiąże te gry przy jak najmniejszej liczbie ruchów.
Twój program pobierze jako sekwencję 52 kart w następującym formacie:
2S 9H 10C 6H 4H 7S 2D QD KD QC 10S AC ...
Które będą rozpatrywane w początkowym układzie w tej kolejności:
01 02 03 04 05 06 07 08
09 10 11 12 13 14 15 16
17 18 19 20 21 22 23 24
25 26 27 28 29 30 31 32
33 34 35 36 37 38 39 40
41 42 43 44 45 46 47 48
49 50 51 52
I zwróć listę ruchów, aby rozwiązać grę. Każdy ruch będzie w tym formacie:
- Liczba reprezentująca numer stosu (
1przez8) lub wolna komórka (AdoD) reprezentująca stos źródłowy. - Kolejna cyfra lub litera reprezentująca stos docelowy lub wolną komórkę lub
Fpodstawa tego koloru.
Dane wyjściowe będą wyglądać mniej więcej tak:
18 28 3A 8B 8C 85 B5 35 4F etc.
Po włożeniu karty do podstawy nie można jej usunąć. Ponieważ tylko jedna karta jest przesuwana na raz, przesunięcie sekwencji 3 kart wymaga 5 ruchów, a sekwencja 5 kart wymaga 9 ruchów.
Jeśli gra jest nierozwiązywalna, Twój program powinien to wskazać. Jednak Twój program musi być w stanie rozwiązać każdą grę do rozwiązania.
Twój program będzie oceniany na podstawie 32 768 ofert znalezionych w oryginalnym programie Microsoft FreeCell. Aby być ważnym, Twój program musi pomyślnie rozwiązać każdą umowę oprócz transakcji nr 11 982 , która jest nierozwiązalna. Twój wynik będzie całkowitą liczbą ruchów potrzebnych do rozwiązania tych 32 767 umów, przy czym krótszy kod będzie rozstrzygającym.
Plik ze wszystkimi deckami w formacie wymaganym przez powyższą specyfikację jest dostępny do pobrania tutaj (plik 5,00 MB): https://github.com/joezeng/pcg-se-files/raw/master/freecell_decks
źródło
Odpowiedzi:
C 64 643 bajty, wynik: ~ 6,5 miliona
Poniższy fragment kodu (dzięki uprzejmości Mego) wyświetla cały kod w postaci pojedynczego pliku C:
Pokaż fragment kodu
Pobierz oryginalne źródło tutaj . Użyj GCC i uruchom
makenastępnie, korzystając z wytycznych w pliku Readme.Moje formatowanie jest złe (wszystkie różne pliki są w jednym bloku kodu) i można by je jeszcze bardziej rozegrać (12 000 bajtów na raz). Każda pomoc byłaby kochana!
Część kodu nie jest moja. Użyłem go z niechronionego prawem autorskim źródła. Jednak poprawiłem metodę wejścia / wyjścia, aby mieściła się w ramach wyzwania (długie zadanie, ponieważ jestem okropny w C (5 godzin). Musiałem też ponownie napisać dużo kodu i wszystko debugować. Ogromne podziękowania dla mojego taty za pomoc i bycie gumową kaczką (i wskazanie moich błędów zarządzania pamięcią) oraz dla wszystkich w TNB, którzy zajmowali się moimi złymi wściekłościami na temat segfaultów i C.
źródło