W grze Flood Paint celem gry jest uzyskanie całej planszy w tym samym kolorze w jak najmniejszej liczbie tur.
Gra rozpoczyna się od planszy wyglądającej mniej więcej tak:
3 3 5 4 1 3 4 1 5
5 1 3 4 1 1 5 2 1
6 5 2 3 4 3 3 4 3
4 4 4 5 5 5 4 1 4
6 2 5 3[3]1 1 6 6
5 5 1 2 5 2 6 6 3
6 1 1 5 3 6 2 3 6
1 2 2 4 5 3 5 1 2
3 6 6 1 5 1 3 2 4
Obecnie liczba (reprezentująca kolor) na środku planszy wynosi 3. W każdej turze kwadrat w środku zmienia kolor, a wszystkie kwadraty tego samego koloru są osiągalne od środka, poruszając się poziomo lub pionowo ( tj. w rejonie zalewowym środkowego kwadratu) zmieni wraz z nim kolory. Jeśli więc środkowy kwadrat zmieni kolor na 5:
3 3 5 4 1 3 4 1 5
5 1 3 4 1 1 5 2 1
6 5 2 3 4 3 3 4 3
4 4 4 5 5 5 4 1 4
6 2 5 5[5]1 1 6 6
5 5 1 2 5 2 6 6 3
6 1 1 5 3 6 2 3 6
1 2 2 4 5 3 5 1 2
3 6 6 1 5 1 3 2 4
wtedy 3, które było na lewo od środkowej 3, również zmieni kolor. Teraz dostępnych jest siedem 5 z centrum, więc jeśli zmienimy kolor na 4:
3 3 5 4 1 3 4 1 5
5 1 3 4 1 1 5 2 1
6 5 2 3 4 3 3 4 3
4 4 4 4 4 4 4 1 4
6 2 4 4[4]1 1 6 6
5 5 1 2 4 2 6 6 3
6 1 1 5 3 6 2 3 6
1 2 2 4 5 3 5 1 2
3 6 6 1 5 1 3 2 4
obszar malowany ponownie dramatycznie powiększa się.
Twoim zadaniem jest stworzenie programu, który pobierze siatkę kolorów 19 na 19 od 1 do 6, w dowolnej formie:
4 5 1 1 2 2 1 6 2 6 3 4 2 3 2 3 1 6 3
4 2 6 3 4 4 5 6 4 4 5 3 3 3 3 5 4 3 4
2 3 5 2 2 5 5 1 2 6 2 6 6 2 1 6 6 1 2
4 6 5 5 5 5 4 1 6 6 3 2 6 4 2 6 3 6 6
1 6 4 4 4 4 6 4 2 5 5 3 2 2 4 1 5 2 5
1 6 2 1 5 1 6 4 4 1 5 1 3 4 5 2 3 4 1
3 3 5 3 2 2 2 4 2 1 6 6 6 6 1 4 5 2 5
1 6 1 3 2 4 1 3 3 4 6 5 1 5 5 3 4 3 3
4 4 1 5 5 1 4 6 3 3 4 5 5 6 1 6 2 6 4
1 4 2 5 6 5 5 3 2 5 5 5 3 6 1 4 4 6 6
4 6 6 2 6 6 2 4 2 6 1 5 6 2 3 3 4 3 6
6 1 3 6 3 5 5 3 6 1 3 4 4 5 1 2 6 4 3
2 6 1 3 2 4 2 6 1 1 5 2 6 6 6 6 3 3 3
3 4 5 4 6 6 3 3 4 1 1 6 4 5 1 3 4 1 2
4 2 6 4 1 5 3 6 4 3 4 5 4 2 1 1 4 1 1
4 2 4 1 5 2 2 3 6 6 6 5 2 5 4 5 4 5 1
5 6 2 3 4 6 5 4 1 3 2 3 2 1 3 6 2 2 4
6 5 4 1 3 2 2 1 1 1 6 1 2 6 2 5 6 4 5
5 1 1 4 2 6 2 5 6 1 3 3 4 1 6 1 2 1 2
i zwróć sekwencję kolorów, którą środkowy kwadrat będzie zmieniał w każdym zakręcie, ponownie w wybranym przez Ciebie formacie:
263142421236425431645152623645465646213545631465
Na końcu każdej sekwencji ruchów kwadraty na siatce 19 na 19 muszą być tego samego koloru.
Twój program musi być całkowicie deterministyczny; dozwolone są rozwiązania pseudolosowe, ale program musi za każdym razem generować to samo wyjście dla tego samego przypadku testowego.
Zwycięski program wykona najmniejszą liczbę kroków, aby rozwiązać wszystkie 100 000 przypadków testowych znalezionych w tym pliku (skompresowany plik tekstowy, 14,23 MB). Jeśli dwa rozwiązania wykonają tę samą liczbę kroków (np. Jeśli oba znalazły optymalną strategię), krótszy program wygra.
BurntPizza napisał program w Javie do weryfikacji wyników testu. Aby użyć tego programu, uruchom przesyłanie i potokuj dane wyjściowe do pliku o nazwie steps.txt
. Następnie uruchom ten program steps.txt
i floodtest
plik w tym samym katalogu. Jeśli twój wpis jest prawidłowy i daje prawidłowe rozwiązania dla wszystkich plików, powinien przejść wszystkie testy i zwrócićAll boards solved successfully.
import java.io.*;
import java.util.*;
public class PainterVerifier {
public static void main(String[] args) throws FileNotFoundException {
char[] board = new char[361];
Scanner s = new Scanner(new File("steps.txt"));
Scanner b = new Scanner(new File("floodtest"));
int lineNum = 0;
caseloop: while (b.hasNextLine()) {
for (int l = 0; l < 19; l++) {
String lineb = b.nextLine();
if (lineb.isEmpty())
continue caseloop;
System.arraycopy(lineb.toCharArray(), 0, board, l * 19, 19);
}
String line = s.nextLine();
if (line.isEmpty())
continue;
char[] steps = line.toCharArray();
Stack<Integer> nodes = new Stack<Integer>();
for (char c : steps) {
char targetColor = board[180];
char replacementColor = c;
nodes.push(180);
while (!nodes.empty()) {
int n = nodes.pop();
if (n < 0 || n > 360)
continue;
if (board[n] == targetColor) {
board[n] = replacementColor;
if (n % 19 > 0)
nodes.push(n - 1);
if (n % 19 < 18)
nodes.push(n + 1);
if (n / 19 > 0)
nodes.push(n - 19);
if (n / 19 < 18)
nodes.push(n + 19);
}
}
}
char center = board[180];
for (char c : board)
if (c != center) {
s.close();
b.close();
System.out.println("\nIncomplete board found!\n\tOn line " + lineNum + " of steps.txt");
System.exit(0);
}
if (lineNum % 5000 == 0)
System.out.printf("Verification %d%c complete...\n", lineNum * 100 / 100000, '%');
lineNum++;
}
s.close();
b.close();
System.out.println("All boards solved successfully.");
}
}
Również tablica wyników, ponieważ wyniki nie są tak naprawdę sortowane według wyników, a tutaj ma to naprawdę duże znaczenie:
- 1 985,078 - smack42, Java
- 2 075 452 - użytkownik 1502040, C
- 2 098,382 - tigrou, C #
- 2 155 834 - CoderTao, C #
- 2 201 995 - MrBackend, Java
- 2 383,569 - CoderTao, C #
- 2 384 020 - Herjan, C
- 2 403 189 - Origineil, Java
- 2 445,761 - Herjan, C
- 2 475 056 - Jeremy List, Haskell
- 2480,714 - SteelTermite, C (2395 bajtów)
- 2480,714 - Herjan, Java (4702 bajty)
- 2588847 - BurntPizza, Java (2748 bajtów)
- 2 588 847 - Gero3, node.js (4 641 bajtów)
- 2 979 145 - Teun Pronk, Delphi XE3
- 4 780,841 - BurntPizza, Java
- 10 800 000 - Joe Z., Python
Odpowiedzi:
Java - 1,985,078 kroków
https://github.com/smack42/ColorFill
Kolejne spóźnione wejście. Plik wyników zawierający 1,985,078 kroków można znaleźć tutaj .
Niektóre informacje w tle:
Odkryłem to wyzwanie kilka lat temu, kiedy zacząłem programować własny klon gry Flood-it.
„najlepszy z niekompletnych” algorytm DFS i A *
Od samego początku chciałem stworzyć dobry algorytm solvera dla tej gry. Z czasem mogłem ulepszyć mój solver, włączając kilka strategii, które przeprowadzały różne niekompletne wyszukiwania (podobne do tych używanych w innych programach tutaj) i wykorzystując najlepszy wynik tych strategii dla każdego rozwiązania. Zaimplementowałem nawet algorytm A * tigrou w Javie i dodałem go do mojego solvera, aby osiągnąć ogólnie lepsze rozwiązania niż wynik tigrou.
wyczerpujący algorytm DFS
Następnie skupiłem się na algorytmie, który zawsze znajduje optymalne rozwiązania. Poświęciłem dużo wysiłku, aby zoptymalizować moją wyczerpującą strategię wyszukiwania w pierwszej kolejności. Aby przyspieszyć wyszukiwanie, dołączyłem skrót, który przechowuje wszystkie zbadane stany, dzięki czemu wyszukiwanie może uniknąć ponownego ich eksploracji. Chociaż ten algorytm działa dobrze i rozwiązuje wszystkie łamigłówki 14x14 wystarczająco szybko, zużywa zbyt dużo pamięci i działa bardzo wolno z łamigłówkami 19x19 w tym wyzwaniu kodowym.
Algorytm Pucherta A *
Kilka miesięcy temu skontaktowałem się z Aaronem i Simonem Puchertem, aby sprawdzić solver Flood-It . Ten program korzysta z algorytmu typu A * z dopuszczalną heurystyką (w przeciwieństwie do tigrou) i przycinaniem ruchów podobnym do wyszukiwania Jump-Point. Szybko zauważyłem, że ten program jest bardzo szybki i znajduje optymalne rozwiązania !
Oczywiście musiałem zaimplementować ten wspaniały algorytm i dodać go do mojego programu. Starałem się zoptymalizować mój program Java, aby działał tak szybko, jak oryginalny program C ++ braci Puchert. Potem postanowiłem spróbować 100 000 przypadków testowych tego wyzwania. Na mojej maszynie program działał przez ponad 120 godzin, aby znaleźć 1,985,078 kroków, używając mojej implementacji algorytmu Puchert A * .
To ma być najlepsze możliwe rozwiązanie tego wyzwania, chyba że w programie występują pewne błędy, które mogą skutkować nieoptymalnymi rozwiązaniami. Wszelkie opinie są mile widziane!
edycja: dodano tutaj odpowiednie części kodu:
klasa AStarPuchertStrategy
część klasy AStarSolver
część klasy AStarNode
źródło
C # - 2 098 382 kroków
Próbuję wielu rzeczy, większość z nich zawodzi i do niedawna po prostu nie działała. Mam coś na tyle interesującego, aby opublikować odpowiedź.
Z pewnością istnieją sposoby na dalszą poprawę tego. Myślę, że przejście pod stopnie 2M może być możliwe.
7 hours
Generowanie wyników zajęło około . Oto plik txt ze wszystkimi rozwiązaniami, na wypadek gdyby ktoś chciał je sprawdzić: results.zipWięcej informacji o tym, jak to działa:
Wykorzystuje algorytm A * Pathfinding .
Trudno jest znaleźć dobro
heuristic
. Jeśliheuristic
nie doceni koszty, będzie działał prawie jak algorytm Dijkstry , a ze względu na złożoność płytki 19x19 z 6 kolorami będzie działał wiecznie. Jeśli przeszacuje koszt, szybko zbiegnie się do rozwiązania, ale w ogóle nie da dobrych (coś w rodzaju 26 ruchów było 19 możliwych). Znalezienie ideałuheuristic
który dałby dokładnie pozostałą liczbę kroków do rozwiązania byłoby najlepsze (byłoby szybkie i dałoby najlepsze możliwe rozwiązanie). To jest (chyba że się mylę) niemożliwe. W rzeczywistości wymaga to najpierw rozwiązania samej planszy, podczas gdy to właśnie próbujesz zrobić (problem z kurczakiem i jajkiem)Próbowałem wielu rzeczy, oto, co zadziałało dla
heuristic
:node
reprezentuje zestaw sąsiadujących ze sobą kwadratów tego samego koloru. Używam tegograph
, mogę łatwo obliczyć dokładną minimalną odległość od środka do dowolnego innego węzła. Na przykład odległość od środka do góry po lewej stronie wynosiłaby 10, ponieważ co najmniej 10 kolorów dzieli je.heuristic
: gram na bieżącej planszy do końca. Dla każdego kroku wybieram kolor, który zminimalizuje sumę odległości od korzenia do wszystkich innych węzłów.Liczba ruchów potrzebnych do osiągnięcia tego celu to
heuristic
.Estimated cost
(używane przez A *) =moves so far
+heuristic
Nie jest idealny, ponieważ nieznacznie zawyża koszty (dlatego nie znaleziono optymalnego rozwiązania). W każdym razie jest szybki, aby obliczyć i dać dobre wyniki.
Byłem w stanie uzyskać ogromną poprawę prędkości, używając grafu do wykonywania wszystkich operacji. Na początku miałem
2-dimension
tablicę. Zalewam go i w razie potrzeby ponownie obliczam wykres (np .: do obliczenia heurystyki). Teraz wszystko odbywa się za pomocą wykresu, który obliczono tylko na początku. Aby zasymulować kroki, wypełnianie powodzi nie jest już potrzebne, zamiast tego scalam węzły. To jest o wiele szybsze.źródło
code blocks
do podkreślania tekstu. Mamy do tego kursywę i pogrubienie .Python - 10 800 000 kroków
Jako rozwiązanie referencyjne ostatniego miejsca, rozważ następującą sekwencję:
Przejście przez wszystkie
n
czasy kolorów oznacza, że każdy kwadratowyn
krok będzie miał ten sam kolor, co kwadrat środkowy. Każdy kwadrat znajduje się co najwyżej 18 kroków od centrum, więc 18 cykli zagwarantuje, że wszystkie kwadraty będą tego samego koloru. Najprawdopodobniej zakończy się w mniejszym stopniu, ale program nie musi się kończyć, gdy tylko wszystkie kwadraty będą tego samego koloru; jest to o wiele bardziej korzystne. Ta stała procedura wynosi 108 kroków na przypadek testowy, w sumie 10 800 000.źródło
1 2 3 4 5 6 ...
zamiast obecnego rozwiązania, które daje123456...
.Java - 2480714 kroków
Popełniłem wcześniej mały błąd (wstawiam jedno kluczowe zdanie przed pętlą zamiast w pętli:
źródło
C - 2 075 452
Wiem, że jestem wyjątkowo spóźniony na przyjęcie, ale widziałem to wyzwanie i chciałem spróbować.
Algorytm oparty jest na wyszukiwaniu drzewa Monte-Carlo z próbkowaniem Thompsona i tabeli transpozycji w celu zmniejszenia przestrzeni wyszukiwania. Na mojej maszynie trwa około 12 godzin. Jeśli chcesz sprawdzić wyniki, możesz je znaleźć na https://dropfile.to/pvjYDMV .
źródło
hash ^= zobrist_table[i][(int)solution[i]];
sięhash ^= zobrist_table[i%len][(int)solution[i]];
do katastrofy programu fix.Java -
24431082588847 krokówObecnie wygrywa (~ 46 tys. Przed Herjan) od 4/26Welp, więc MrBackend nie tylko mnie pokonał, ale znalazłem błąd, który dał zwodniczo dobry wynik. Zostało już naprawione (było również w weryfikatorze! Ack), ale niestety nie mam w tej chwili czasu na odzyskanie korony. Spróbuję później.
Jest to oparte na moim innym rozwiązaniu, ale zamiast malować kolorem najczęściej występującym na krawędziach wypełnienia, maluje kolorem, który spowoduje odsłonięcie krawędzi o wielu sąsiadujących kwadratach tego samego koloru. Nazwij to LookAheadPainter. W razie potrzeby zagram w golfa później.
EDYCJA: Napisałem weryfikator, nie krępuj się, oczekuje pliku steps.txt zawierającego kroki generowane przez program oraz plik testowy: Edycja-Edycja: (patrz OP)
Jeśli ktoś znajdzie problem, zgłoś go mi!
źródło
C - 2480,714 kroków
Nadal nie jest optymalny, ale teraz jest szybszy i osiąga lepsze wyniki.
źródło
Java - 2
245529 2201995 krokówWyszukiwanie równoległe i buforowanie drzewa na głębokości 5, minimalizując liczbę „wysp”. Ponieważ poprawa z głębokości 4 na głębokość 5 była tak niewielka, nie sądzę, aby poprawianie jej było bardziej uzasadnione. Ale jeśli trzeba by to poprawić, moje przeczucie mówi, że trzeba pracować z obliczaniem liczby wysp jako różnicy między dwoma stanami, zamiast przeliczania wszystkiego.
Obecnie wyjścia na standardowe wyjście, dopóki nie znam formatu wejściowego weryfikatora.
źródło
24
spowodowałoby to znacznie bardziej wydajne działanie.Mój ostatni wpis: C - 2 384 020 kroków
Tym razem „sprawdź wszystkie możliwości” ... Ten wynik jest uzyskiwany przy Głębokości ustawionej na 3. Głębokość przy 5 powinna dać ~ 2,1 miliona kroków ... ZBYT WOLNO. Głębokość 20+ daje najmniejszą możliwą liczbę kroków (tylko sprawdza wszystkie mecze i najkrótsze wygrane oczywiście) ... Ma najmniejszą liczbę kroków, chociaż nienawidzę tego, ponieważ jest tylko trochę lepszy, ale wydajność jest do kitu. Wolę mój inny wpis w C, który również znajduje się w tym poście.
Kolejna ulepszona sztuczna inteligencja napisana w C - 2 445 761 kroków
Na podstawie SteelTermite's:
źródło
Java -
26107974780841 kroków(Naprawiono błąd wypełniania, wynik jest teraz znacznie gorszy -_-)
To jest moje podstawowe zgłoszenie algorytmu referencyjnego, po prostu tworzy histogram kwadratów na krawędziach malowanego obszaru i maluje najczęściej używanym kolorem. Uruchamia 100k w kilka minut.
Oczywiście nie wygra, ale na pewno nie będzie to trwało. Prawdopodobnie złożę kolejne zgłoszenie za sprytne rzeczy. Wykorzystaj ten algorytm jako punkt wyjścia.
Cofnij komentarz do komentowanych wierszy dla pełnego wyniku. Domyślnie drukuje liczbę podjętych kroków.
Gra w golfa do 860 znaków (nie wliczając nowych wierszy do formatowania), ale może być bardziej skurczony, gdybym chciał spróbować:
źródło
Haskell - 2 475 056 kroków
Algorytm jest podobny do sugerowanego przez MrBackend w komentarzach. Różnica polega na tym, że jego sugestia znajduje najtańszą drogę do kwadratu o najwyższym koszcie, moje łapczywie zmniejsza ekscentryczność wykresu na każdym kroku.
źródło
C # - 2 383,569
Jest to głęboka przemiana możliwych rozwiązań, która z grubsza wybiera ścieżkę najlepszej poprawy (podobna / taka sama jak pozycja C Herjana), z tym wyjątkiem, że sprytnie odwróciłem kolejność generowania rozwiązań kandydujących po tym, jak Herjan opublikował te same liczby. Trwa to ponad 12 godzin.
źródło
Java - 2 403 189
To miała być moja próba brutalnej siły. Ale! Moja pierwsza implementacja „najlepszego” wyboru pojedynczej głębokości przyniosła:
Kod użyty dla obu jest taki sam, z brutalną siłą przechowującą „migawkę” innych możliwych ruchów i uruchamiającą algorytm nad nimi wszystkimi.
W przypadku pracy z podejściem „wielokrotnym” zdarzają się awarie. W teście jednostkowym ustawiam pierwsze 100 wpisów układanki i mogę uzyskać 100% zaliczenia, ale nie w 100% przypadków. Aby to zrekompensować, właśnie prześledziłem numer bieżącej łamigłówki w momencie niepowodzenia i zacząłem podnosić nowe wątki od miejsca, w którym ostatni został przerwany. Każdy wątek zapisał swoje wyniki w pliku. Pula plików została następnie skondensowana w jeden plik.
Node
reprezentuje kafelek / kwadrat planszy i przechowuje odniesienie do wszystkich jego sąsiadów. Śledzić trzySet<Node>
zmienne:Remaining
,Painted
,Targets
. Każda iteracja sprawdza,Targets
aby pogrupować wszystkiecandidate
węzły według wartości, wybierająctarget value
liczbę „dotkniętych” węzłów. Dotknięte węzły stają się następnie celami następnej iteracji.Źródło jest rozproszone na wiele klas, a fragmenty nie mają większego znaczenia poza kontekstem całości. Moje źródło można przeglądać za pośrednictwem GitHub . Ja również zawiedli wokół z JSFiddle demo do wizualizacji.
Niemniej jednak moja metoda konia roboczego z
Solver.java
:źródło
C # - 2
196462 2155834Jest to faktycznie takie samo podejście do „szukania najlepszego potomka”, jak mój inny solver, ale z kilkoma optymalizacjami, które ledwo, równolegle, pozwalają mu dotrzeć do głębokości 5 w niecałe 10 godzin. W trakcie testowania znalazłem również błąd w oryginale, taki, że algorytm od czasu do czasu podążał nieefektywnymi trasami do stanu końcowego (nie uwzględniał głębokości stanów z wynikiem = 64; wykryty podczas zabawy z wynikami głębokości = 7).
Główną różnicą między tym a poprzednim solwerem jest to, że zachowuje stany gry Flood w pamięci, więc nie musi regenerować stanów 6 ^ 5. W oparciu o użycie procesora podczas pracy, jestem całkiem pewien, że zmieniło się to z CPU na ograniczenie przepustowości pamięci. Świetna zabawa. Tyle grzechów.
Edycja: Z przyczyn algorytm głębokości 5 nie zawsze daje najlepszy wynik. Aby poprawić wydajność, wykonajmy tylko głębokość 5 ... i 4 ... oraz 3 i 2 i 1, i zobaczmy, która jest najlepsza. Ogoliłem kolejne 40 000 ruchów. Ponieważ głębokość 5 stanowi większość czasu, dodanie 4 do 1 zwiększa tylko czas działania z ~ 10 godzin do ~ 11 godzin. Tak!
źródło
Delphi XE3 2 979 145 kroków
Ok, więc to moja próba. Nazywam zmieniającą się część kroplą, za każdym razem tworzy kopię tablicy i testuje każdy możliwy kolor, aby zobaczyć, który kolor da największą kroplę.
Uruchamia wszystkie łamigłówki w 3 godziny i 6 minut
Myśląc również o metodzie śledzenia brutalnej siły.
Może zabawa w ten weekend ^^
źródło
JavaScript / node.js - 2 588 847
Algorytm jest nieco inny niż większość tutaj, ponieważ wykorzystuje wstępnie obliczone regiony i stany różnic między obliczeniami. Działa tutaj poniżej 10 minut, jeśli martwisz się szybkością z powodu javascript.
źródło
Kod C, który gwarantuje znalezienie optymalnego rozwiązania przez prostą brutalną siłę. Działa dla siatek o dowolnym rozmiarze i wszystkich danych wejściowych. Uruchomienie większości sieci zajmuje bardzo, bardzo długo.
Wypełnienie powodziowe jest wyjątkowo nieefektywne i polega na rekurencji. Może być konieczne zwiększenie twojego stosu, jeśli jest bardzo mały. System brutalnej siły używa sznurka do przechowywania liczb i prostego dodawania z przenoszeniem, aby przełączać wszystkie możliwe opcje. Jest to również bardzo nieefektywne, ponieważ powtarza większość etapów z biliardami razy.
Niestety nie byłem w stanie przetestować go na wszystkich testach, ponieważ umrę ze starości, zanim się skończy.
O ile wiem, to obecny zwycięzca. Konkurs wymaga, aby:
Czek
Ponieważ zawsze znajduje to najmniejszą liczbę kroków do ukończenia każdej planszy, a żadna z nich tego nie zrobiła, obecnie jest przed nami. Jeśli ktoś może wymyślić krótszy program, może wygrać, dlatego przedstawiam następującą wersję zoptymalizowaną pod kątem wielkości. Wykonanie jest nieco wolniejsze, ale czas wykonania nie jest częścią warunków wygranej:
źródło