Rozważ kwadratowy wykres siatki n na n, który wygląda tak.

Należy zauważyć, że ten wykres to 11 na 11 .

W dowolnym momencie mężczyzna stoi na skrzyżowaniu i porusza się tylko pionowo lub poziomo, krok po kroku, do następnego skrzyżowania. Niestety, wypił trochę za dużo, więc wybiera losowy kierunek z maksymalnie 4 możliwych kierunków (góra, dół, lewo, prawo). Jest to do 4, jak gdyby stał przy ścianie, ma oczywiście tylko 3 opcje, aw rogu ma tylko 2.

Zaczyna w lewym dolnym rogu, a jego celem jest powrót do domu, który jest w prawym górnym rogu. Czas to po prostu liczba kroków, które trzeba mu podjąć.

Jesteś jednak złośliwym przeciwnikiem, który chce, aby wracał do domu tak wolno, jak to możliwe. Możesz usunąć dowolną liczbę krawędzi z wykresu w dowolnym momencie podczas jego spaceru. Jedynym ograniczeniem jest to, że zawsze musisz zostawić mu drogę do powrotu do domu i nie możesz usunąć krawędzi, z której już skorzystał.

Wyzwanie polega na tym, aby wymyślić tak złośliwego przeciwnika, jak to możliwe, a następnie przetestować go na wykresie 100 na 100 20 na 20 za pomocą przypadkowego pijanego piechura. Twój wynik to po prostu średni czas, jaki zajmuje losowemu piechurowi powrót do domu powyżej 10 1000 biegów.

Możesz używać dowolnego języka i bibliotek, które lubisz, o ile są one swobodnie dostępne i łatwe do zainstalowania w systemie Linux.

Co muszę wdrożyć?

Powinieneś zaimplementować kod dla chodzika losowego, a także dla przeciwnika, a kod powinien być połączony, aby wynik po uruchomieniu był po prostu średnią z 1000 przebiegów przy użyciu kodu przeciwnika. Losowy kod walkera powinien być bardzo prosty do napisania, ponieważ po prostu wybiera spośród (x-1, y), (x + 1, y), (x, y-1) i (x, y + 1), upewniając się, że żaden z nich nie został usunięty lub nie jest poza zasięgiem.

Kod przeciwnika jest oczywiście trudniejszy i musi również pamiętać, które krawędzie pijak już przeszedł, aby nie próbował go usunąć i upewnić się, że dla pijaka jest jeszcze droga do domu, która jest nieco trudniejsza zrobić szybko.

Uzupełnienie 10 biegów to za mało, ale nie chciałem karać ludzi, którym udało się zrobić naprawdę długie spacery. Teraz zwiększyłem go do 1000 z powodu popularnej prośby. Jeśli jednak spacer jest tak długi, że nie możesz wykonać 1000 biegów w realistycznym czasie, po prostu zgłoś maksymalną liczbę biegów, jaką możesz.

Tabela najlepszych wyników dla 100 na 100.

• 976124.754 firmy Optimizer.
• 103000363.218 autor: Peter Taylor.

Edycja 1. Zmieniłem rozmiar wykresu na 20 na 20, aby pomóc w czasie wykonywania testów ludzi. Zrobię nowy wysoki wynik tabeli dla tego rozmiaru, gdy ludzie będą przedstawiać wyniki.

Tabela najlepszych wyników dla 20 na 20.

230,794.38 (100k runs) by justhalf
227,934 by Sparr 
213,000 (approx) by Peter Taylor
199,094.3 by stokastic
188,000 (approx) by James_pic
 64,281 by Geobits

230 794,38 na biegach 20 x 20, 100 000

Ostatnia aktualizacja: W końcu zbudowałem idealne dynamiczne rozwiązanie 2-ścieżkowe. Powiedziałem doskonale, ponieważ poprzednia wersja faktycznie nie jest symetryczna, łatwiej było uzyskać dłuższą ścieżkę, jeśli pijak przeszedł jedną ścieżkę nad drugą. Obecny jest symetryczny, dzięki czemu może uzyskać wyższą oczekiwaną liczbę kroków. Po kilku próbach wydaje się, że wynosi około 230 tys., Co oznacza poprawę w stosunku do poprzedniego, wynoszącą około 228 tys. Ale statystycznie rzecz biorąc liczby te wciąż mieszczą się w swoich ogromnych odchyleniach, więc nie twierdzę, że jest to znacznie lepsze, ale uważam, że powinno to być lepsze niż poprzednia wersja.

Kod znajduje się na dole tego postu. Jest aktualizowany, dzięki czemu jest znacznie szybszy niż poprzednia wersja, wykonując 1000 uruchomień w 23s.

Poniżej znajduje się przykładowy przebieg i przykładowy labirynt:

Idealny piechur
Średnia: 230794,384
Maks .: 1514506
Min: 25860
Ukończone w 2317.374s
 _ _ _ _ _ _ _ _ _ _ _ _ _. 
| | | | | | | | | | | | | | | _ _ _ _  
| | | | | | | | | | | | | | | | _ _ _ _  
| | | | | | | | | | | | | | | _ _ _ _ |
| | | | | | | | | | | | | | | | _ _ _ _  
| | | | | | | | | | | | | | | _ _ _ _ |
| | | | | | | | | | | | | | | | _ _ _ _  
| | | | | | | | | | | | | | | _ _ _ _ |
| | | | | | | | | | | | | | _ | | _ _ _ _  
| | | | | | | | | | | | | _ _ _ _ _ _ |
| | | | | | | | | | | | | | _ _ _ _ _ _  
| | | | | | | | | | | | | _ _ _ _ _ _ |
| | | | | | | | | | | | | | _ _ _ _ _ _  
| | | | | | | | | | | | | _ _ _ _ _ _ |
| | | | | | _ | | _ | | _ | | _ | | _ _ _ _ _ _  
| | | | | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |
| | | | | | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _  
| | | | | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |
| | _ | | _ | | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _  
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ | 

Poprzednie zgłoszenia

Wreszcie mogę dopasować wynik Sparra! = D.

Opierając się na moich wcześniejszych eksperymentach (patrz na dole tego postu), najlepszą strategią jest posiadanie podwójnej ścieżki i zamknięcie jednej, gdy pijak dotrze do dowolnego z nich, a zmienna wynika z tego, jak dobrze możemy dynamicznie przewidzieć, dokąd pójdzie pijak zwiększyć szansę, że dostanie się na dłuższą ścieżkę.

Tak więc w oparciu o moją DOUBLE_PATHstrategię zbudowałem kolejny, który zmienia labirynt (mój DOUBLE_PATHlabirynt można łatwo modyfikować) w zależności od ruchu pijaka. Gdy będzie podążał ścieżką z więcej niż jedną dostępną opcją, zamknę ścieżki tak, aby pozostawić tylko dwie możliwe opcje (jedna, z której przyszedł, druga nietrawerowana).

Brzmi to podobnie do tego, co osiągnął Sparr, jak pokazuje wynik. Różnica w stosunku do jego jest zbyt mała, aby uznać ją za lepszą, ale powiedziałbym, że moje podejście jest bardziej dynamiczne niż on, ponieważ mój labirynt jest bardziej modyfikowalny niż Sparra =)

Wynik z przykładowym labiryntem końcowym:

EXTREME_DOUBLE_PATH
Średnia: 228034,89
Maks .: 1050816
Min: 34170
Ukończone w 396,728s
 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
| | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |
| | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |
| | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |
| | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |
| | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |
| | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |
 _ _ _ _ _ _ _ _ _ _ | | | _ _ _ _ _ _ _ _ _
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |
 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ | |
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |
 _ _ _ _ _ | | _ _ _ _ _ _ _ _ _ _ _ _ _ _
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |

Sekcja Eksperymentów

Najlepsza okazuje się ta sama strategia co stokastic, jestem dumny z eksperymentowania przy użyciu różnych strategii i drukowania dobrych wyników :)

Każdy z drukowanych labiryntów poniżej jest ostatnim labiryntem po dotarciu pijaka do domu, więc mogą się nieznacznie różnić od biegu do biegu ze względu na losowość ruchów pijaka i dynamikę przeciwnika.

Opiszę każdą strategię:

Jedna ścieżka

Jest to najprostsze podejście, które utworzy jedną ścieżkę od wejścia do wyjścia.

SINGLE_PATH
Średnia: 162621.612
Maks .: 956694
Min: 14838
Ukończone w 149,430
 _ _ _ _ _ _ _ _ _ _ _
| | _ | | _ | | _ | | _ | | _ | | _ | | _ | | _ | | _ | |
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 
 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 
 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 
 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 
 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 
 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 
 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 
 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 
 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 
 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |

Wyspa (poziom 0)

To podejście próbuje złapać pijaka w prawie odizolowanej wyspie. Nie działa tak dobrze, jak się spodziewałem, ale jest to jeden z moich pierwszych pomysłów, więc go uwzględniam.

Do wyjścia prowadzą dwie ścieżki, a gdy pijak zbliża się do jednej z nich, przeciwnik zamyka ją, zmuszając go do znalezienia drugiego wyjścia (i prawdopodobnie ponownie uwięziony na wyspie)

WYSPA
Średnia: 74626,070
Maks .: 428560
Min: 1528
Ukończone w 122.512s
 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _   
| | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | |
| | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | |
| | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | |
| | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | |
| | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | |
| | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | |
| | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | |
| | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | |
| | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | |
| | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | |
| | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | |
| | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | |
| | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | |
| | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | |
| | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | |
| | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | |
| _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | |
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |

Podwójna ścieżka

Jest to najczęściej dyskutowana strategia, polegająca na posiadaniu dwóch ścieżek o równej długości do wyjścia i zamykaniu jednej z nich, gdy pijak zbliży się do jednej z nich.

DOUBLE_PATH
Średnia: 197743,472
Maks .: 1443406
Min: 21516
Ukończone w 308,177
 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 
 _ _ _ _ _ _ _ _ _ _ | | _ _ _ _ _ _ _ _ _ _
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |
 _ _ _ _ _ _ _ _ _ _ | | _ _ _ _ _ _ _ _ _ _
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |
 _ _ _ _ _ _ _ _ _ _ | | _ _ _ _ _ _ _ _ _ _
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |
 _ _ _ _ _ _ _ _ _ _ | | _ _ _ _ _ _ _ _ _ _
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |
 _ _ _ _ _ _ _ _ _ _ | | _ _ _ _ _ _ _ _ _ _
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |
 _ _ _ _ _ _ _ _ _ _ | | _ _ _ _ _ _ _ _ _ _
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |
 _ _ _ _ _ _ _ _ _ _ | | _ _ _ _ _ _ _ _ _ _
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |
 _ _ _ _ _ _ _ _ _ _ | | _ _ _ _ _ _ _ _ _ _
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |
 _ _ _ _ _ _ _ _ _ _ | | _ _ _ _ _ _ _ _ _ _
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |

Wyspa (poziom 1)

Zainspirowani wieloma ścieżkami wyspy i wysoką liczbą kroków w pojedynczej ścieżce, łączymy wyspę z wyjściem i wykonujemy labirynt pojedynczej ścieżki na wyspie, tworząc w sumie trzy ścieżki wyjścia i podobnie jak w poprzednim przypadku, zamknij dowolną z wyjdź, gdy pijak się zbliży.

Działa to nieco lepiej niż czysta pojedyncza ścieżka, ale nadal nie pokonuje podwójnej ścieżki.

WYSPA
Średnia: 166265.132
Maks .: 1162966
Min: 19544
Ukończone w 471,982s
 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
| _ _ _ _ _ _ _ _ _ | _
| | | _ | | _ | | _ | | _ | | _ | | _ | | _ | | _ | |  
| | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ | |
| | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ | |
| | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ | |
| | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ | |
| | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ | |
| | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ | |
| | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ | |
| | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ | |
| _ | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |

Wyspa (poziom 2)

Próbując rozwinąć poprzedni pomysł, stworzyłem zagnieżdżoną wyspę, tworząc w sumie pięć ścieżek, ale wydaje się, że to nie działa dobrze.

WYSPA
Średnia: 164222,712
Maks .: 927608
Min: 22024
Ukończone w 793,591
 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ | _
| | _ _ _ _ _ _ _ _ | _ | |  
| | | | _ | | _ | | _ | | _ | | _ | | _ | | _ | | |
| | | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ | |
| | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ | | |
| | | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ | |
| | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ | | |
| | | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ | |
| | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ | | |
| | | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ | |
| | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ | | |
| | | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ | |
| | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ | | |
| | | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ | |
| | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ | | |
| | | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ | |
| | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ | | |
| _ | _ | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ | |
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |

Wyspa (poziom 3)

Zauważając, że podwójna ścieżka faktycznie działa lepiej niż pojedyncza ścieżka, zróbmy wyspę podwójną ścieżką!

Rezultatem jest poprawa w stosunku do wyspy (poziom 1), ale wciąż nie pokonuje podwójnej ścieżki.

Dla porównania wynik dla podwójnej ścieżki wielkości wyspy wynosi średnio 131 134,42 ruchów. To dodaje dość znacznej liczby ruchów (około 40k), ale nie wystarcza, aby pokonać podwójną ścieżkę.

WYSPA
Średnia: 171730,090
Maks .: 769080
Min: 29760
Ukończone w 587,646
 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ | _
| | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |  
| _ _ _ _ _ _ _ _ | | _ _ _ _ _ _ _ _ | |
| | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ | |
| _ _ _ _ _ _ _ _ | | _ _ _ _ _ _ _ _ | |
| | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ | |
| _ _ _ _ _ _ _ _ | | _ _ _ _ _ _ _ _ | |
| | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ | |
| _ _ _ _ _ _ _ _ | | _ _ _ _ _ _ _ _ | |
| | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ | |
| _ _ _ _ _ _ _ _ | | _ _ _ _ _ _ _ _ | |
| | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ | |
| _ _ _ _ _ _ _ _ | | _ _ _ _ _ _ _ _ | |
| | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ | |
| _ _ _ _ _ _ _ _ | | _ _ _ _ _ _ _ _ | |
| | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ | |
| _ _ _ _ _ _ _ _ | | _ _ _ _ _ _ _ _ | |
| | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ | |
| _ | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |

Wyspa (poziom 4)

Ponownie, eksperymentowanie z zagnieżdżoną wyspą i znowu to nie działa tak dobrze.

WYSPA
Średnia: 149723.068
Maks .: 622106
Min: 25752
Ukończone w 830.889s
 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _    
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ | _ |
| | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ | _ |  
| | | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |
| | _ _ _ _ _ _ _ | | _ _ _ _ _ _ _ | | |
| | | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ | | |
| | _ _ _ _ _ _ _ | | _ _ _ _ _ _ _ | | |
| | | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ | | |
| | _ _ _ _ _ _ _ | | _ _ _ _ _ _ _ | | |
| | | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ | | |
| | _ _ _ _ _ _ _ | | _ _ _ _ _ _ _ | | |
| | | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ | | |
| | _ _ _ _ _ _ _ | | _ _ _ _ _ _ _ | | |
| | | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ | | |
| | _ _ _ _ _ _ _ | | _ _ _ _ _ _ _ | | |
| | | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ | | |
| | _ _ _ _ _ _ _ | | _ _ _ _ _ _ _ | | |
| | _ | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ | | |
| _ | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ | |
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |

Wniosek

Podsumowując, dowodzi to, że posiadanie pojedynczej długiej ścieżki od aktualnej pozycji pijaka do wyjścia działa najlepiej, co osiąga się dzięki strategii podwójnej ścieżki, ponieważ po zamknięciu wyjścia pijak będzie musiał przebyć maksymalną możliwą odległość, aby dostać się do wyjście.

To dalsze wskazówki, że podstawową strategią powinna nadal być podwójna ścieżka, i możemy jedynie modyfikować dynamikę tworzenia ścieżek, co zrobiło Sparr. Uważam więc, że jego strategia jest najlepsza!

Kod

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.TreeSet;

public class Walker {

    enum Strategy{
        SINGLE_PATH,
        ISLAND,
        DOUBLE_PATH,
        EXTREME_DOUBLE_PATH,
        PERFECT_DOUBLE_PATH,
    }

    int width,height;
    int x,y; //walker's position
    int dX,dY; //destination
    Point[][] points;
    int stepCount = 0;

    public static void main(String[]args){
        int side = 20;
//      runOnce(side, Strategy.EXTREME_DOUBLE_PATH, 0);
        runOnce(side, Strategy.PERFECT_DOUBLE_PATH, 0);
//      for(Strategy strategy: Strategy.values()){
//          runOnce(side, strategy, 0);
//      }
//      runOnce(side, Strategy.ISLAND, 1);
//      runOnce(side, Strategy.ISLAND, 2);
//      Scanner scanner = new Scanner(System.in);
//      System.out.println("Enter side, strategy (SINGLE_PATH, ISLAND, DOUBLE_PATH, EXTREME_DOUBLE_PATH), and level:");
//      while(scanner.hasNext()){
//          side = scanner.nextInt();
//          Strategy strategy = Strategy.valueOf(scanner.next());
//          int level = scanner.nextInt();
//          scanner.nextLine();
//          runOnce(side, strategy, level);
//          System.out.println("Enter side, strategy (SINGLE_PATH, ISLAND, DOUBLE_PATH, EXTREME_DOUBLE_PATH), and level:");
//      }
//      scanner.close();
    }

    private static Walker runOnce(int side, Strategy strategy, int level) {
        Walker walker = null;
        long total = 0;
        int max = 0;
        int min = Integer.MAX_VALUE;
        double count = 1000;
        long start = System.currentTimeMillis();
        for(int i=0; i<count; i++){
            walker = new Walker(0,0,side,side,side-1,side-1, strategy, level, false);
            total += walker.stepCount;
            max = Math.max(walker.stepCount, max);
            min = Math.min(walker.stepCount, min);
//          System.out.println("Iteration "+i+": "+walker.stepCount);
        }
        System.out.printf("%s\nAverage: %.3f\nMax: %d\nMin:%d\n",strategy, total/count, max, min);
        System.out.printf("Completed in %.3fs\n", (System.currentTimeMillis()-start)/1000.0);
        walker.printPath();
        return walker;
    }

    private void createIsland(int botLeftX, int botLeftY, int topRightX, int topRightY){
        for(int i=botLeftY+1; i<topRightY; i++){
            if(i>botLeftY+1) deletePath(points[botLeftX][i].right());
            if(i<topRightY-1) deletePath(points[topRightX][i].left());
        }
        for(int i=botLeftX+1; i<topRightX; i++){
            if(i>botLeftX+1) deletePath(points[i][botLeftY].up());
            if(i<topRightX-1) deletePath(points[i][topRightY].down());
        }
    }

    private void createSinglePath(int botLeftX, int botLeftY, int topRightX, int topRightY){
        for(int i=botLeftY; i<topRightY; i++){
            if(i==topRightY-1 && (topRightY+1-botLeftY)%2==0){
                for(int j=botLeftX; j<topRightX; j++){
                    if(j==topRightX-1 && (j-botLeftX)%2==0){
                        deletePath(points[topRightX][topRightY].down());
                    } else {
                        deletePath(points[j][topRightY-1+((j-botLeftX)%2)].right());
                    }
                }
            } else {
                for(int j=botLeftX+(i-botLeftY)%2; j<topRightX+((i-botLeftY)%2); j++){
                    deletePath(points[j][i].up());
                }
            }
        }
    }

    private void createDoublePath(int botLeftX, int botLeftY, int topRightX, int topRightY){
        for(int i=botLeftY; i<topRightY; i++){
            if(i>botLeftY && (width%4!=1 || i<topRightY-1)) deletePath(points[width/2-1][i].right());
            if(i==topRightY-1 && (topRightY+1-botLeftY)%2==1){
                for(int j=botLeftX; j<topRightX; j++){
                    if((j-botLeftX)%2==0 || j<topRightX-1){
                        deletePath(points[j][topRightY-1+((j-botLeftX)%2)].right());
                    } else {
                        deletePath(points[topRightX-1][topRightY-1].right());
                    }
                }
            } else {
                if((i-botLeftY)%2==0){
                    for(int j=botLeftX+1; j<topRightX; j++){
                        deletePath(points[j][i].up());
                    }
                } else {
                    for(int j=botLeftX; j<topRightX+1; j++){
                        if(j!=width/2 && j!=width/2-1){
                            deletePath(points[j][i].up());
                        }
                    }
                }
            }
        }
    }

    public Walker(int startingX,int startingY, int Width, int Height, int destinationX, int destinationY, Strategy strategy, int level, boolean animate){
        width = Width;
        height = Height;
        dX = destinationX;
        dY = destinationY;
        x=startingX;
        y=startingY;
        points = new Point[width][height];
        for(int y=0; y<height; y++){
            for(int x=0; x<width; x++){
                points[x][y] = new Point(x,y);
            }
        }
        for(int y=0; y<height; y++){
            for(int x=0; x<width; x++){
                if(x<width-1) new Edge(points[x][y], points[x+1][y]);
                if(y<height-1) new Edge(points[x][y], points[x][y+1]);
            }
        }

        if(strategy == Strategy.SINGLE_PATH) createSinglePath(0,0,width-1,height-1);

        if(strategy == Strategy.DOUBLE_PATH) createDoublePath(0,0,width-1,height-1);

        List<EdgeList> edgeLists = new ArrayList<EdgeList>();
        if(strategy == Strategy.ISLAND){
            List<Edge> edges = new ArrayList<Edge>();
            if(level==0){
                createIsland(0,0,width-1,height-1);
                deletePath(points[width-2][height-2].right());
                deletePath(points[width-2][height-2].up());
            } else {
                for(int i=0; i<level; i++){
                    createIsland(i,i,width-1-i, height-1-i);
                }
                createDoublePath(level,level,width-1-level,height-1-level);
                for(int i=height-1; i>=height-level; i--){
                    edges.add(points[i-2][i].right());
                    edges.add(points[i][i-2].up());
                    edgeLists.add(new EdgeList(points[i-1][i].right(), points[i][i-1].up()));
                }
            }
            edges.add(points[width-1-level][height-1-level].down());
            edges.add(points[width-1-level][height-1-level].left());
            edgeLists.add(new EdgeList(edges.toArray(new Edge[0])));
        }

        int[] availableVerticals = new int[height];
        if(strategy == Strategy.EXTREME_DOUBLE_PATH){
            for(int i=1; i<width-1; i++){
                deletePath(points[i][0].up());
            }
            availableVerticals[0] = 2;
            for(int i=1; i<height; i++){
                availableVerticals[i] = width;
            }
        }

        boolean[][] available = new boolean[width][height];
        if(strategy == Strategy.PERFECT_DOUBLE_PATH){
            for(int x=0; x<width; x++){
                for(int y=0; y<height; y++){
                    if(x%2==1 && y%2==1){
                        available[x][y] = true;
                    } else {
                        available[x][y] = false;
                    }
                }
            }
        }
//      printPath();
        while(!walk()){
            if(animate)try{Thread.sleep(500);}catch(InterruptedException e){}
            if(strategy == Strategy.ISLAND){
                if(x==y && (x==1 || (x>=2 && x<=level))){
                    if(!hasBeenWalked(points[x][x].down())){
                        deletePath(points[x][x].down());
                    } else if(!hasBeenWalked(points[x][x].left())){
                        deletePath(points[x][x].left());
                    }
                }
            }
            if(strategy == Strategy.EXTREME_DOUBLE_PATH){
                Point cur = points[x][y];
                int untravelled = 0;
                for(Edge edge: cur.edges) if(edge!=null && !edge.walked) untravelled++;
                if(untravelled>1){
                    if(cur.up()!=null && availableVerticals[y]>2 && !cur.up().walked){
                        deletePath(cur.up());
                        availableVerticals[y]--;
                    }
                    if(cur.down()!=null && !cur.down().walked){
                        deletePath(cur.down());
                        availableVerticals[y-1]--;
                    }
                    if(cur.up()!=null && cur.left()!=null && !cur.left().walked){
                        deletePath(cur.left());
                        deletePath(points[x][y+1].left());
                    }
                    if(cur.up()!=null && cur.right()!=null && !cur.right().walked){
                        deletePath(cur.right());
                        if(y<height-1) deletePath(points[x][y+1].right());
                    }
                }
            }
            if(strategy == Strategy.PERFECT_DOUBLE_PATH){
                Point cur = points[x][y];
                int untravelled = 0;
                for(Edge edge: cur.edges) if(edge!=null && !edge.walked) untravelled++;
                if(x%2!=1 || y%2!=1){
                    if(untravelled>1){
                        if(cur.down()==null && hasBeenWalked(cur.right())){
                            if(canBeDeleted(cur.up())) deletePath(cur.up());
                        }
                        if(cur.down()==null && hasBeenWalked(cur.left())){
                            if(x%2==0 && y%2==1 && canBeDeleted(cur.right())) deletePath(cur.right());
                            else if(cur.right()!=null && canBeDeleted(cur.up())) deletePath(cur.up());
                        }
                        if(cur.left()==null && hasBeenWalked(cur.up())){
                            if(canBeDeleted(cur.right())) deletePath(cur.right());
                        }
                        if(cur.left()==null && hasBeenWalked(cur.down())){
                            if(x%2==1 && y%2==0 && canBeDeleted(cur.up())) deletePath(cur.up());
                            else if (cur.up()!=null && canBeDeleted(cur.right())) deletePath(cur.right());
                        }
                    }
                } else {
                    if(!hasBeenWalked(cur.left())){
                        if(x>1 && available[x-2][y]){
                            if(untravelled>1){
                                available[x-2][y] = false;
                                deletePath(cur.up());
                            }
                        } else if(cur.up()!=null){
                            if(canBeDeleted(cur.left())) deletePath(cur.left());
                            if(canBeDeleted(points[x][y+1].left())) deletePath(points[x][y+1].left());
                        }
                    }
                    if(!hasBeenWalked(cur.down())){
                        if(y>1 && available[x][y-2]){
                            if(untravelled>1){
                                available[x][y-2] = false;
                                deletePath(cur.right());
                            }
                        } else if(cur.right()!=null){
                            if(canBeDeleted(cur.down())) deletePath(cur.down());
                            if(canBeDeleted(points[x+1][y].down())) deletePath(points[x+1][y].down());
                        }
                    }
                }
            }
            if(strategy == Strategy.DOUBLE_PATH || strategy == Strategy.EXTREME_DOUBLE_PATH
                    || strategy == Strategy.PERFECT_DOUBLE_PATH){
                if(x==width-2 && y==height-1 && points[width-1][height-1].down()!=null){
                    deletePath(points[width-1][height-1].left());
                }
                if(x==width-1 && y==height-2 && points[width-1][height-1].left()!=null){
                    deletePath(points[width-1][height-1].down());
                }
            } else if(strategy == Strategy.ISLAND){
                for(EdgeList edgeList: edgeLists){
                    boolean deleted = false;
                    for(Edge edge: edgeList.edges){
                        if(edge.start.x == x && edge.start.y == y){
                            if(!hasBeenWalked(edge)){
                                deletePath(edge);
                                edgeList.edges.remove(edge);
                                if(edgeList.edges.size() == 1){
                                    edgeLists.remove(edgeList);
                                }
                                deleted = true;
                                break;
                            }
                        }
                    }
                    if(deleted) break;
                }
            }
            if(animate)printPath();
        }
    }

    public boolean hasBeenWalked(Edge edge){
        if(edge == null) return false;
        return edge.walked;
    }

    public boolean canBeDeleted(Edge edge){
        if(edge == null) return false;
        return !edge.walked;
    }

    public List<Edge> getAdjacentUntravelledEdges(){
        List<Edge> result = new ArrayList<Edge>();
        for(Edge edge: points[x][y].edges){
            if(edge!=null && !hasBeenWalked(edge)) result.add(edge); 
        }
        return result;
    }

    public void printPath(){
        StringBuilder builder = new StringBuilder();
        for(int y=height-1; y>=0; y--){
            for(int x=0; x<width; x++){
                Point point = points[x][y];
                if(this.x==x && this.y==y){
                    if(point.up()!=null) builder.append('?');
                    else builder.append('.');
                } else {
                    if(point.up()!=null) builder.append('|');
                    else builder.append(' ');
                }
                if(point.right()!=null) builder.append('_');
                else builder.append(' ');
            }
            builder.append('\n');
        }
        System.out.print(builder.toString());
    }

    public boolean walk(){
        ArrayList<Edge> possibleMoves = new ArrayList<Edge>();
        Point cur = points[x][y];
        for(Edge edge: cur.edges){
            if(edge!=null) possibleMoves.add(edge);
        }
        int random = (int)(Math.random()*possibleMoves.size());
        Edge move = possibleMoves.get(random);
        move.walked = true;
        if(move.start == cur){
            x = move.end.x;
            y = move.end.y;
        } else {
            x = move.start.x;
            y = move.start.y;
        }
        stepCount++;
        if(x==dX && y == dY){
            return true;
        } else {
            return false;
        }
    }

    public boolean isSolvable(){
        TreeSet<Point> reachable = new TreeSet<Point>();
        Queue<Point> next = new LinkedList<Point>();
        next.offer(points[x][y]);
        reachable.add(points[x][y]);
        while(next.size()>0){
            Point cur = next.poll();
            ArrayList<Point> neighbors = new ArrayList<Point>();
            if(cur.up()!=null) neighbors.add(cur.up().end);
            if(cur.right()!=null) neighbors.add(cur.right().end);
            if(cur.down()!=null) neighbors.add(cur.down().start);
            if(cur.left()!=null) neighbors.add(cur.left().start);
            for(Point neighbor: neighbors){
                if(!reachable.contains(neighbor)){
                    if(neighbor == points[dX][dY]) return true;
                    reachable.add(neighbor);
                    next.offer(neighbor);
                }
            }
        }
        return false;
    }

    public boolean deletePath(Edge toDelete){
        if(toDelete == null) return true;
//      if(toDelete.walked){
//          System.err.println("Edge already travelled!");
//          return false;
//      }
        int startIdx = toDelete.getStartIdx();
        int endIdx = toDelete.getEndIdx();
        toDelete.start.edges[startIdx] = null;
        toDelete.end.edges[endIdx] = null;
//      if(!isSolvable()){
//          toDelete.start.edges[startIdx] = toDelete;
//          toDelete.end.edges[endIdx] = toDelete;
//          System.err.println("Invalid deletion!");
//          return false;
//      }
        return true;
    }

    static class EdgeList{
        List<Edge> edges;

        public EdgeList(Edge... edges){
            this.edges = new ArrayList<Edge>();
            this.edges.addAll(Arrays.asList(edges));
        }
    }

    static class Edge implements Comparable<Edge>{
        Point start, end;
        boolean walked;

        public Edge(Point start, Point end){
            walked = false;
            this.start = start;
            this.end = end;
            this.start.edges[getStartIdx()] = this;
            this.end.edges[getEndIdx()] = this;
            if(start.compareTo(end)>0){
                Point tmp = end;
                end = start;
                start = tmp;
            }
        }

        public Edge(int x1, int y1, int x2, int y2){
            this(new Point(x1,y1), new Point(x2,y2));
        }

        public boolean exists(){
            return start.edges[getStartIdx()] != null || end.edges[getEndIdx()] != null;
        }

        public int getStartIdx(){
            if(start.x == end.x){
                if(start.y < end.y) return 0;
                else return 2;
            } else {
                if(start.x < end.x) return 1;
                else return 3;
            }
        }

        public int getEndIdx(){
            if(start.x == end.x){
                if(start.y < end.y) return 2;
                else return 0;
            } else {
                if(start.x < end.x) return 3;
                else return 1;
            }
        }

        public boolean isVertical(){
            return start.x==end.x;
        }

        @Override
        public int compareTo(Edge o) {
            int result = start.compareTo(o.start);
            if(result!=0) return result;
            return end.compareTo(o.end);
        }
    }

    static class Point implements Comparable<Point>{
        int x,y;
        Edge[] edges;

        public Point(int x, int y){
            this.x = x;
            this.y = y;
            edges = new Edge[4];
        }

        public Edge up(){ return edges[0]; }
        public Edge right(){ return edges[1]; }
        public Edge down(){ return edges[2]; }
        public Edge left(){ return edges[3]; }

        public int compareTo(Point o){
            int result = Integer.compare(x, o.x);
            if(result!=0) return result;
            result = Integer.compare(y, o.y);
            if(result!=0) return result;
            return 0;
        }
    }
}

227934 (20x20)

Moja trzecia próba. Stosuje to samo ogólne podejście co @stokastic z dwiema ścieżkami do wyjścia. Kiedy piechur dotrze do końca jednej ścieżki, zamyka się, wymagając od niego powrotu, aby dostać się do końca drugiej ścieżki w celu wyjścia. Moje ulepszenie polega na generowaniu ścieżek wraz z postępem piechura, aby każda ścieżka, którą posunie się dalej w pierwszej połowie procesu, skończy się dłuższą drogą niż druga.

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <math.h>
#include <iostream>

#define DEBUG 0
#define ROUNDS 10000

#define Y 20
#define X 20
#define H (Y*2+1)
#define W (X*2+1)

int maze[H][W];
int scores[ROUNDS];

int x, y;

void print_maze(){
    char line[W+2];
    line[W+1]=0;
    for(int row=0;row<H;row++) {
        for(int col=0;col<W;col++) {
            switch(maze[row][col]) {
                case 0:
                    line[col]=' ';
                    break;
                case 1:
                    line[col]=row%2?'-':'|';
                    break;
                case 8:
                    line[col]=(row==y*2+1&&col==x*2+1)?'@':'?';
                    break;
                case 9:
                    line[col]=(row==y*2+1&&col==x*2+1)?'@':'*';
                    break;
            }
        }
        line[W]='\n';
        printf("%s",line);
    }
    printf("%d %d\n",y,x);
}

int main(){
    srand (time(NULL));
    long long total_turns = 0;
    for(int round=0;round<ROUNDS;round++) {
        for (int r=0;r<H;r++) {
            for (int c=0;c<W;c++) {
                maze[r][c]=0;
            }
        }
        maze[1][1]=9;
        maze[1][2]=1;
        maze[2][1]=1;
        maze[1][3]=8;
        maze[3][1]=8;
        int progress_l = 0;
        int progress_r = 0;
        int side = 0;
        int closed_exit = 0;
        x=0;
        y=0;
        if (DEBUG) print_maze();
        long long turn = 0;
        int in = 0;
        while (x!=X-1||y!=Y-1) {
            turn++;
            int r = y*2+1;
            int c = x*2+1;
            int dx=0, dy=0;
            if (DEBUG) {
                std::cin>>in;
                switch(in) {
                    case 0:
                        dy=-1; dx=0; break;
                    case 1:
                        dy=0; dx=1; break;
                    case 2:
                        dy=1; dx=0; break;
                    case 3:
                        dy=0; dx=-1; break;
                    default:
                        dy=0; dx=0; break;
                }
            } else {
                int exits = maze[r-1][c] + maze[r][c+1] + maze[r+1][c] + maze[r][c-1];
                int exit_choice = -1;
                do {
                    if (rand()%exits == 0) {
                        exit_choice = exits;
                        break;
                    } else {
                        exits--;
                    }
                }while(exits);

                --exits;

                if (maze[r-1][c]&&!dx&&!dy) {
                    if (exits) {
                        --exits;
                    } else {
                        dy = -1;
                        dx = 0;
                    }
                }
                if (maze[r][c+1]&&!dx&&!dy) {
                    if (exits) {
                        --exits;
                    } else {
                        dy = 0;
                        dx = 1;
                    }
                }
                if (maze[r+1][c]&&!dx&&!dy) {
                    if (exits) {
                        --exits;
                    } else {
                        dy = 1;
                        dx = 0;
                    }
                }
                if (maze[r][c-1]&&!dx&&!dy) {
                    if (exits) {
                        --exits;
                    } else {
                        dy = 0;
                        dx = -1;
                    }
                }
            }

            x+=dx;
            y+=dy;

            if(x==X-1 && y==Y-1) continue;

            if (x==0&&y==1) side=-1;
            if (x==1&&y==0) side=1;
            if (maze[y*2+1][x*2+1]==8) { // room needs another exit, maybe
                if (side==-1) { // left half of maze
                    if (y==1) { // top of a column
                        if (x%2) { // going up, turn right
                            maze[y*2+1][x*2+2]=1;
                            maze[y*2+1][x*2+3]=8;
                        } else { // going right, turn down
                            maze[y*2+2][x*2+1]=1;
                            maze[y*2+3][x*2+1]=8;
                        }
                    } else if (y==Y-1) { // bottom of a column
                        if (x%2 && x<(X-progress_r-3)) { // going right, turn up if there's room
                            maze[y*2+0][x*2+1]=1;
                            maze[y*2-1][x*2+1]=8;
                            progress_l=x+1;
                        } else { // going down or exiting, go right
                            if (x!=X-2 or closed_exit==1) {
                                maze[y*2+1][x*2+2]=1;
                                maze[y*2+1][x*2+3]=8;
                            } else {
                                closed_exit = -1;
                            }
                        }
                    } else { // in a column
                        if (maze[y*2+0][x*2+1]) { // going down
                            maze[y*2+2][x*2+1]=1;
                            maze[y*2+3][x*2+1]=8;
                        } else { // going up
                            maze[y*2+0][x*2+1]=1;
                            maze[y*2-1][x*2+1]=8;
                        }
                    }
                } else { // right half of maze
                    if (y==0) { // top row
                        if (x<X-1) { // go right
                            maze[y*2+1][x*2+2]=1;
                            maze[y*2+1][x*2+3]=8;
                        } else { // go down
                            maze[y*2+2][x*2+1]=1;
                            maze[y*2+3][x*2+1]=8;
                        }
                    } else if (y==Y-2) { // heading right to the exit
                        if (x<X-1) { // go right
                            maze[y*2+1][x*2+2]=1;
                            maze[y*2+1][x*2+3]=8;
                        } else { // go down
                            if (x!=X-1 or closed_exit==-1) {
                                maze[y*2+2][x*2+1]=1;
                                maze[y*2+3][x*2+1]=8;
                            } else {
                                closed_exit = 1;
                            }
                        }
                    } else if (y==Y-3) { // bottom of a column
                        if (x>progress_l+1) { // do we have room for another column?
                            if (!(x%2)&&y>1) { // going left, turn up
                                maze[y*2+0][x*2+1]=1;
                                maze[y*2-1][x*2+1]=8;
                            } else { // going down, turn left
                                maze[y*2+1][x*2+0]=1;
                                maze[y*2+1][x*2-1]=8;
                                progress_r=X-x-1;
                            }
                        } else { // abort, move down to escape row
                            maze[y*2+2][x*2+1]=1;
                            maze[y*2+3][x*2+1]=8;
                        }
                    } else if (y==1) { // top of a column
                        if (!(x%2)) { // going up, turn left
                            maze[y*2+1][x*2+0]=1;
                            maze[y*2+1][x*2-1]=8;
                        } else { // going left, turn down
                            maze[y*2+2][x*2+1]=1;
                            maze[y*2+3][x*2+1]=8;
                        }
                    } else { // in a column
                        if (maze[y*2+0][x*2+1]) { // going down
                            maze[y*2+2][x*2+1]=1;
                            maze[y*2+3][x*2+1]=8;
                        } else { // going up
                            maze[y*2+0][x*2+1]=1;
                            maze[y*2-1][x*2+1]=8;
                        }
                    }

                }
                maze[y*2+1][x*2+1]=9;
            }

            if (DEBUG) print_maze();
        }
        // print_maze();
        printf("turns:%lld\n",turn);
        scores[round] = turn;
        total_turns += turn;
    }
    printf("%d rounds in a %d*%d maze\n",ROUNDS,X,Y);
    long long avg = total_turns/ROUNDS;
    printf("average: % 10lld\n",avg);
    long long var = 0;
    for(int r=0;r<ROUNDS;r++){
        var += (scores[r]-avg)*(scores[r]-avg);
    }
    var/=ROUNDS;
    // printf("variance: %lld\n",var);
    int stddev=sqrt(var);
    printf("stddev:  % 10d\n",stddev);

}

wyjście (z czasem):

...
turns:194750
turns:506468
turns:129684
turns:200712
turns:158664
turns:156550
turns:311440
turns:137900
turns:86948
turns:107134
turns:81806
turns:310274
100000 rounds in a 20*20 maze
average:     227934
stddev:      138349
real    10m54.797s
...

przykład mojego labiryntu z mniej więcej równymi połówkami ścieżki, pokazujący ścieżkę w lewo / w dół odciętą od wyjścia (prawy dolny róg):

  _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
 |  _   _   _   _   _   _   _   _   _  |
 | | | | | | | | | | | | | | | | | | | |
 | | | | | | | | | | | | | | | | | | | |
 | | | | | | | | | | | | | | | | | | | |
 | | | | | | | | | | | | | | | | | | | |
 | | | | | | | | | | | | | | | | | | | |
 | | | | | | | | | | | | | | | | | | | |
 | | | | | | | | | | | | | | | | | | | |
 | | | | | | | | | | | | | | | | | | | |
 | | | | | | | | | | | | | | | | | | | |
 | | | | | | | | | | | | | | | | | | | |
 | | | | | | | | | | | | | | | | | | | |
 | | | | | | | | | | | | | | | | | | | |
 | | | | | | | | | | | | | | | | | | | |
 | | | | | | | | | | | | | | | | | | | |
 | | | | | | | | | | | | | | | | | | | |
 | | | | | | | | | | |_| |_| |_| |_| |_|
 | | | | | | | | | |_ _ _ _ _ _ _ _ _ _
 |_| |_| |_| |_| |_ _ _ _ _ _ _ _ _ _  !

PS: Zdaję sobie sprawę z niewielkiej poprawy tego algorytmu, która wymaga bardziej sprytnego kodu, aby wygenerować inny kształt dla dwóch ścieżek, klatek schodowych zamiast spójnych wysokości zygzaków.

135 488 307,9 dla 98 x 98

199094.3 dla 20x20

Wdrożyłem rozwiązanie, które tworzy dwie ścieżki do mety i zamyka dokładnie jedną z nich, gdy dotrze do niej pijak. To symuluje długość ścieżki, która będzie co najmniej 1,5 raza większa niż długość pojedynczej ścieżki od początku do końca. Po 27 biegach trafiłem średnio około 135 milionów. Niestety zajmuje to kilka minut na spacer, więc będę musiał go uruchomić przez kilka następnych godzin. Jedno zastrzeżenie - mój generator podwójnych ścieżek działa tylko wtedy, gdy rozmiar wykresu ma postać 4 * n + 2, co oznacza, że ​​najbliższe 100 to 102 lub 98. Zamierzam opublikować wyniki przy użyciu 98, czego oczekuję aby nadal przewyższać metodę ścieżki zygzakowej. Później będę pracować nad lepszym systemem ścieżki. Obecnie wyniki wyjściowe mają postać (numSteps, currentA Average) po każdym marszu.

EDYCJA: naprawiono, więc kod działa teraz na rozmiarach wykresów, które są dowolną wielokrotnością liczby 2, a nie 4 * n + 2.

Kod: (dodaj argument „True” do konstruktora walkera w linii 187 w celu rysowania wykresu przez żółwia).

import random
import turtle

WIDTH  = 20
HEIGHT = 20
L, U, R, D = 1, 2, 4, 8

def delEdge(grid, x1, y1, x2, y2):

    # check that coordinates are in-bounds
    if not (0 <= x1 < WIDTH):  return False
    if not (0 <= y1 < HEIGHT): return False
    if not (0 <= x2 < WIDTH):  return False
    if not (0 <= y2 < HEIGHT): return False

    # swap order such that x1 <= x2 and y1 <= y2
    if x2 < x1:
        x2 ^= x1
        x1 ^= x2
        x2 ^= x1
    if x2 < x1: print "Swap failure: {}, {}".format(x1, x2)

    if y2 < y1:
        y2 ^= y1
        y1 ^= y2
        y2 ^= y1
    if y2 < y1: print "Swap failure: {}, {}".format(y1, y2)

    # check that only one of the deltas is = 1
    dx = x2 - x1
    dy = y2 - y1

    if dx and dy:       return False
    if not (dx or dy):  return False
    if dx > 1:          return False
    if dy > 1:          return False

    #print "<{}, {}>, <{}, {}>".format(x1, y1, x2, y2)

    if dx > 0:
        try: grid[x1][y1].remove(R)
        except: pass
        try: grid[x2][y2].remove(L)
        except: pass
    if dy > 0:
        try: grid[x1][y1].remove(D)
        except: pass
        try: grid[x2][y2].remove(U)
        except: pass

    return True

def newGrid():

    grid = [[[] for y in xrange(HEIGHT)] for x in xrange(WIDTH)]

    for x in xrange(WIDTH):
        for y in xrange(HEIGHT):
            if x > 0:
                grid[x][y].append(L)
            if x < WIDTH-1:
                grid[x][y].append(R)
            if y > 0:
                grid[x][y].append(U)
            if y < HEIGHT-1:
                grid[x][y].append(D)

    return grid

class walker:

    def __init__(self, grid, mode, draw=False):
        self.x  = 0
        self.y  = 0
        self.dx = WIDTH-1
        self.dy = HEIGHT-1

        self.grid     = grid
        self.mode     = mode
        self.draw     = draw
        self.numSteps = 0

        self.initGrid()

    def initGrid(self):
        if self.mode == 0:
            #pass
            if self.draw: drawGrid(grid)

        elif self.mode == 1:

            for y in xrange(HEIGHT-1):
                if y % 2 == 0:
                    for x in xrange(WIDTH - 1):
                        delEdge(grid, x, y, x, y+1)
                else:
                    for x in xrange(1, WIDTH):
                        delEdge(grid, x, y, x, y+1)
            if self.draw: drawGrid(grid)

        elif self.mode == 2:
            for y in xrange(HEIGHT/2):
                if y % 2 == 0:
                    for x in xrange(1, WIDTH-1):
                        delEdge(grid, x, y, x, y+1)
                else:
                    for x in xrange(2, WIDTH):
                        delEdge(grid, x, y, x, y+1)
            for y in xrange(HEIGHT/2, HEIGHT-1):
                if y%2 == 0:
                    for x in xrange(1, WIDTH-1):
                        delEdge(grid, x, y, x, y+1)
                else:
                    for x in xrange(0, WIDTH-2):
                        delEdge(grid, x, y, x, y+1)
            for y in xrange(1, HEIGHT-1):
                midpoint = HEIGHT/2
                if HEIGHT % 4 == 0: 
                    midpoint = HEIGHT/2 + 1
                if y < midpoint:
                    delEdge(grid, 0, y, 1, y)
                else:
                    delEdge(grid, WIDTH-1, y, WIDTH-2, y)
            if self.draw: drawGrid(grid)

    def walk(self):
        self.numSteps += 1
        choices = grid[self.x][self.y]
        direction = random.choice(choices)
        #print (self.x, self.y), grid[self.x][self.y], direction
        if direction   == L: self.x -= 1
        elif direction == U: self.y -= 1
        elif direction == R: self.x += 1
        elif direction == D: self.y += 1

    def main(self):
        hasBlocked = False
        while (self.x, self.y) != (self.dx, self.dy):
            #print (self.x, self.y), (self.dx, self.dy)
            self.walk()
            if self.mode == 2:
                if not hasBlocked:
                    if (self.x, self.y) == (WIDTH-2, HEIGHT-1):
                        delEdge(self.grid, WIDTH-2, HEIGHT-1, WIDTH-1, HEIGHT-1)
                        hasBlocked = True
                    elif (self.x, self.y) == (WIDTH-1, HEIGHT-2):
                        delEdge(self.grid, WIDTH-1, HEIGHT-1, WIDTH-1, HEIGHT-2)
                        hasBlocked = True

        return self.numSteps

def drawGrid(grid):
    size = 3
    turtle.speed(0)
    turtle.delay(0)
    turtle.ht()
    for x in xrange(WIDTH):
        for y in xrange(HEIGHT):
            dirs = grid[x][y]
            for dir in dirs:
                if dir == L:
                    turtle.pu()
                    turtle.setpos((x*4, y*4))
                    turtle.pd()
                    turtle.setpos(((x-1)*4, y*4))
                elif dir == R:
                    turtle.pu()
                    turtle.setpos((x*4, y*4))
                    turtle.pd()
                    turtle.setpos(((x+1)*4, y*4))
                elif dir == U:
                    turtle.pu()
                    turtle.setpos((x*4, y*4))
                    turtle.pd()
                    turtle.setpos((x*4, (y-1)*4))
                elif dir == D:
                    turtle.pu()
                    turtle.setpos((x*4, y*4))
                    turtle.pd()
                    turtle.setpos((x*4, (y+1)*4))
    turtle.mainloop()

numTrials  = 100
totalSteps = 0.0
i = 0
try:
    while i < numTrials:
        grid = newGrid()

        w = walker(grid, 2)
        steps = w.main()
        totalSteps += steps
        print steps, totalSteps/(i+1)
        i += 1

    print totalSteps / numTrials

except KeyboardInterrupt:
    print totalSteps / i

Surowe dane: (bieżąca liczba kroków, średnia bieżąca)

358796490 358796490.0
49310430 204053460.0
106969130 171692016.667
71781702 146714438.0
49349086 127241367.6
40874636 112846912.333
487607888 166384194.571
56423642 152639125.5
71077302 143576700.667
101885368 139407567.4
74423642 133499937.818
265170542 144472488.167
59524778 137938048.923
86919630 134293876.143
122462528 133505119.6
69262650 129489965.25
85525556 126903823.529
161165512 128807250.667
263965384 135920836.632
128907594 135570174.5
89535930 133378067.619
97344576 131740181.636
98772132 130306788.174
140769524 130742735.5
198274280 133443997.28
95417374 131981434.846
226667006 135488307.852

4-ścieżkowe podejście, 213 tys

Podejście jednościeżkowe to

i zdobywa średnią N^2 .

Podejście dwutorowe jest

ale kiedy pierwszy raz pijak znajdzie się w zasięgu punktu końcowego, zostaje odcięty:

Uzyskuje średnią (N/2)^2 + N^2 .

Podejście czterościeżkowe wykorzystuje dwa cięcia:

Załóżmy, że zewnętrzna pętla ma długość, xNa wewnętrzna pętla jest długa (1-x)N. Dla uproszczenia dokonam normalizacjiN=1 .

Od początku do pierwszego cięcia przeciętnie wynosi (x/2)^2. Od pierwszego cięcia do drugiego cięcia ma dwie opcje, długości xi 1-x; daje to średnio(1-x)x^2 + x(1-x)^2 = x-x^2 . Wreszcie pozostała ścieżka daje 1. Tak więc całkowity wynik to N^2 (1 + x - 3/4 x^2).

Początkowo założyłem, że utrzymanie dostępnych ścieżek o równej długości na każdym kroku byłoby optymalne, więc w moim początkowym podejściu wykorzystałem x = 1/2wynik 1.3125 N^2. Ale po wykonaniu powyższej analizy okazuje się, że optymalny podział daje się x = 2/3z wynikiem 1.3333 N^2.

1000 walks with average 210505.738 in 202753ms

1000 walks with average 212704.626 in 205191ms

z kodem

import java.awt.Point;
import java.util.*;

// http://codegolf.stackexchange.com/q/37484/194
public class RandomWalker {
    private static final int SIZE = 19;
    private static final Point dest = new Point(SIZE, SIZE);

    private final Random rnd = new Random();
    private Point p = new Point(0, 0);
    private int step = 0;
    private Set<Set<Point>> edges;
    private Map<Set<Point>, String> cuttableEdgeNames;
    private Set<String> cutSequences;
    private String cutSequence = "";

    public static void main(String[] args) {
        long start = System.nanoTime();
        long total = 0;
        int walks = 0;
        while (walks < 1000 && total < 1L << 40) {
            RandomWalker rw = new RandomWalker();
            total += rw.walk();
            walks++;
        }

        long timeTaken = System.nanoTime() - start;
        System.out.println(walks + " walks with average " + total / (double)walks + " in " + (timeTaken / 1000000) + "ms");
    }

    RandomWalker() {
        loadMaze(
            "+-+ +-+ +-+ +-+ +-+ +-+ +-+-+-+-+-+-+-+",
            "| | | | | | | | | | | | |             |",
            "+ + + + + + + + + + + + + +-+ +-+ +-+ +",
            "| | | | | | | | | | | | | | | | | | | |",
            "+ + + + + + + + + + + + + + + + + + + +",
            "| | | | | | | | | | | | | | | | | | | |",
            "+ + + + + + + + + + + +-+ + + + + + + +",
            "| | | | | | | | | | |     | | | | | | |",
            "+ + + + + + + + + + + +-+-+ + + + + + +",
            "| | | | | | | | | | | |     | | | | | |",
            "+ + + + + + + + + + + + +-+ + + + + + +",
            "| | | | | | | | | | | | | | | | | | | |",
            "+ + + + + + + + + + + + + + + + + + + +",
            "| | | | | | | | | | | | | | | | | | | |",
            "+ + + + + + + + + + + + + + + + + + + +",
            "| | | | | | | | | | | | | | | | | | | |",
            "+ + + + + + + + + + + + + + + + + + + +",
            "| | | | | | | | | | | | | | | | | | | |",
            "+ +-+ +-+ +-+ +-+ +-+ + + + + + + + + +",
            "|                     | | | | | | | | |",
            "+ +-+ +-+ +-+ +-+ +-+ + + + + + + + + +",
            "| | | | | | | | | | | | | | | | | | | |",
            "+ + + + + + + + + + + + + + + + + + + +",
            "| | | | | | | | | | | | | | | | | | | |",
            "+ + + + + + + + + + + + + + + + + + + +",
            "| | | | | | | | | | | | | | | | | | | |",
            "+ + + + + + + + + + + + + + + + + + + +",
            "| | | | | | | | | | | | | | | | | | | |",
            "+ + + + + + + + + + + + + + + + + + + +",
            "| | | | | | | | | | | | | | | | | | | |",
            "+ + + + + + + + + + + +-+ + + + + + + +",
            "| | | | | | | | | | |     | | | | | | |",
            "+ + + + + + + + + + + +-+ + + + + + + +",
            "| | | | | | | | | | | | | | | | | | | d",
            "+ + + + + + + + + + + + + + +-+ +-+ +c+",
            "| | | | | | | | | | | | | |           |",
            "+ + + + + + + + + + + + + +-+-+-+-+-+ +",
            "| | | | | | | | | | | | |           f b",
            "+-+ +-+ +-+ +-+ +-+ +-+ +-+-+-+-+-+e+a+"
        );
        cutSequences = new HashSet<String>();
        cutSequences.add("ac");
        cutSequences.add("ad");
        cutSequences.add("be");
        cutSequences.add("bf");
    }

    private void loadMaze(String... row) {
        edges = new HashSet<Set<Point>>();
        cuttableEdgeNames = new HashMap<Set<Point>, String>();

        // Horizontal edges
        for (int y = 0; y <= SIZE; y++) {
            for (int x0 = 0; x0 < SIZE; x0++) {
                char ch = row[y * 2].charAt(x0 * 2 + 1);
                if (ch == ' ') continue;
                Set<Point> edge = new HashSet<Point>();
                edge.add(new Point(x0, y));
                edge.add(new Point(x0 + 1, y));
                edges.add(edge);
                if (ch != '-') cuttableEdgeNames.put(edge, "" + ch);
            }
        }

        // Vertical edges
        for (int y0 = 0; y0 < SIZE; y0++) {
            for (int x = 0; x <= SIZE; x++) {
                char ch = row[y0 * 2 + 1].charAt(x * 2);
                if (ch == ' ') continue;
                Set<Point> edge = new HashSet<Point>();
                edge.add(new Point(x, y0));
                edge.add(new Point(x, y0 + 1));
                edges.add(edge);
                if (ch != '|') cuttableEdgeNames.put(edge, "" + ch);
            }
        }
    }

    int walk() {
        while (!p.equals(dest)) {
            List<Point> neighbours = neighbours(p);
            int idx = rnd.nextInt(neighbours.size());
            p = neighbours.get(idx);
            step++;
        }

        return step;
    }

    List<Point> neighbours(Point p) {
        List<Point> rv = new ArrayList<Point>();
        if (p.x > 0) handlePossibleNeighbour(rv, p, new Point(p.x - 1, p.y));
        if (p.x < SIZE) handlePossibleNeighbour(rv, p, new Point(p.x + 1, p.y));
        if (p.y > 0) handlePossibleNeighbour(rv, p, new Point(p.x, p.y - 1));
        if (p.y < SIZE) handlePossibleNeighbour(rv, p, new Point(p.x, p.y + 1));
        return rv;
    }

    private void handlePossibleNeighbour(List<Point> neighbours, Point p1, Point p2) {
        if (edgeExists(p1, p2)) neighbours.add(p2);
    }

    private boolean edgeExists(Point p1, Point p2) {
        Set<Point> edge = new HashSet<Point>();
        edge.add(p1);
        edge.add(p2);

        // Is it cuttable?
        String id = cuttableEdgeNames.get(edge);
        if (id != null) {
            String prefix = cutSequence + id;
            for (String seq : cutSequences) {
                if (seq.startsWith(prefix)) {
                    // Cut it
                    cutSequence = prefix;
                    edges.remove(edge);
                    return false;
                }
            }
        }

        return edges.contains(edge);
    }
}

Eksperymentowałem z przecinaniem siatki prawie całkowicie w każdym krzędzie. To skutecznie zamienia go na czymś podobnym do błądzenia losowego na kprzez N * N/ksiatkę. Najbardziej skuteczną opcją jest krojenie każdego rzędu, aby zmusić pijaka do zygzaka.

Dla przypadku 20x20 ( SIZE=19) mam

time java RandomWalker 
1000 walks with average 148577.604

real    0m14.076s
user    0m13.713s
sys     0m0.360s

z kodem

import java.awt.Point;
import java.util.*;

// http://codegolf.stackexchange.com/q/37484/194
// This handles a simpler problem where the grid is mutilated before the drunkard starts to walk.
public class RandomWalker {
    private static final int SIZE = 19;
    private final Random rnd = new Random();

    public static void main(String[] args) {
        RandomWalker rw = new RandomWalker();
        long total = 0;
        int walks = 0;
        while (walks < 1000 && total < 1L << 40) {
            total += rw.walk();
            walks++;
        }

        System.out.println(walks + " walks with average " + total / (double)walks);
    }

    int walk() {
        Point dest = new Point(SIZE, SIZE);
        Point p = new Point(0, 0);
        int step = 0;

        while (!p.equals(dest)) {
            List<Point> neighbours = neighbours(p);
            int idx = rnd.nextInt(neighbours.size());
            p = neighbours.get(idx);
            step++;
        }

        return step;
    }

    List<Point> neighbours(Point p) {
        List<Point> rv = new ArrayList<Point>();
        if (p.x > 0) handlePossibleNeighbour(rv, p, new Point(p.x - 1, p.y));
        if (p.x < SIZE) handlePossibleNeighbour(rv, p, new Point(p.x + 1, p.y));
        if (p.y > 0) handlePossibleNeighbour(rv, p, new Point(p.x, p.y - 1));
        if (p.y < SIZE) handlePossibleNeighbour(rv, p, new Point(p.x, p.y + 1));
        return rv;
    }

    private void handlePossibleNeighbour(List<Point> neighbours, Point p1, Point p2) {
        if (edgeExists(p1, p2)) neighbours.add(p2);
    }

    private boolean edgeExists(Point p1, Point p2) {
        return p1.x != p2.x || p1.x == SIZE * (Math.max(p1.y, p2.y) & 1);
    }
}

Dla tych, którzy nie chcą odkrywać koła od nowa

Nie martw się! Wymyślę to dla ciebie :)

Nawiasem mówiąc, jest to w Javie.

Stworzyłem klasę Walker, która zajmuje się chodzeniem losowo. Zawiera także przydatną metodę określania, czy ruch jest prawidłowy (jeśli został już wykonany).

Zakładam, że wszyscy sprytni ludzie mogą wymyślić losowe liczby dla konstruktora, zostawiłem to tobie, abyś mógł przetestować pewne przypadki. Również po prostu wywołaj funkcję walk (), aby (zgadłeś!), Aby pijak chodził (losowo).

Zaimplementuję funkcję canComeHome () kiedyś. Najlepiej po znalezieniu najlepszego sposobu na zrobienie tego.

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.TreeSet;

public class Walker {
    int width,height;
    int x,y; //walker's position (does anyone else keep thinking about zombies?!?)
    int dX,dY; //destination
    TreeSet<Edge> pathsNoLongerAvailable = new TreeSet<Edge>();
    TreeSet<Edge> previouslyTraveled = new TreeSet<Edge>();
    int stepCount = 0;

    public static void main(String[]args){
        int side = 10;
        Walker walker = null;
        int total = 0;
        double count = 1000;
        for(int i=0; i<count; i++){
            walker = new Walker(0,0,side,side,side-1,side-1);
            total += walker.stepCount;
            System.out.println("Iteration "+i+": "+walker.stepCount);
        }
        System.out.printf("Average: %.3f\n", total/count);
        walker.printPath();
    }

    public Walker(int startingX,int startingY, int Width, int Height, int destinationX, int destinationY){
        width = Width;
        height = Height;
        dX = destinationX;
        dY = destinationY;
        x=startingX;
        y=startingY;
        while(!walk()){
            // Do something
        }
    }

    public void printPath(){
        for(int i=0; i<width-1; i++){
            if(!pathsNoLongerAvailable.contains(new Edge(i,height-1,i+1,height-1))){
                System.out.print(" _");
            } else {
                System.out.print("  ");
            }
        }
        System.out.println();
        for(int i=height-2; i>=0; i--){
            for(int j=0; j<2*width-1; j++){
                if(j%2==0){
                    if(!pathsNoLongerAvailable.contains(new Edge(j/2,i,j/2,i+1))){
                        System.out.print("|");
                    } else {
                        System.out.print(" ");
                    }
                } else {
                    if(!pathsNoLongerAvailable.contains(new Edge(j/2,i,j/2+1,i))){
                        System.out.print("_");
                    } else {
                        System.out.print(" ");
                    }
                }
            }
            System.out.println();
        }
    }

    public boolean walk(){
        ArrayList<int[]> possibleMoves = new ArrayList<int[]>();
        if(x!=0 && !pathsNoLongerAvailable.contains(new Edge(x,y,x-1,y))){
            possibleMoves.add(new int[]{-1,0});
        }
        if(x!=width-1 && !pathsNoLongerAvailable.contains(new Edge(x,y,x+1,y))){
            possibleMoves.add(new int[]{1,0});
        }
        if(y!=0 && !pathsNoLongerAvailable.contains(new Edge(x,y,x,y-1))){
            possibleMoves.add(new int[]{0,-1});
        }
        if(y!=height-1 && !pathsNoLongerAvailable.contains(new Edge(x,y,x,y+1))){
            possibleMoves.add(new int[]{0,1});
        }
        int random = (int)(Math.random()*possibleMoves.size());
        int[] move = possibleMoves.get(random);
        previouslyTraveled.add(new Edge(x,y,x+move[0],y+move[1]));
        x+=move[0];
        y+=move[1];
        stepCount++;
        if(x==dX && y == dY){
            return true;
        } else {
            return false;
        }
    }

    public boolean isSolvable(){
        TreeSet<Point> reachable = new TreeSet<Point>();
        Queue<Point> next = new LinkedList<Point>();
        next.offer(new Point(x,y));
        reachable.add(new Point(x,y));
        while(next.size()>0){
            Point cur = next.poll();
            int x = cur.x;
            int y = cur.y;
            ArrayList<Point> neighbors = new ArrayList<Point>();
            if(x!=0 && !pathsNoLongerAvailable.contains(new Edge(x,y,x-1,y))){
                neighbors.add(new Point(x-1, y));
            }
            if(x!=width-1 && !pathsNoLongerAvailable.contains(new Edge(x,y,x+1,y))){
                neighbors.add(new Point(x+1, y));
            }
            if(y!=0 && !pathsNoLongerAvailable.contains(new Edge(x,y,x,y-1))){
                neighbors.add(new Point(x, y-1));
            }
            if(y!=height-1 && !pathsNoLongerAvailable.contains(new Edge(x,y,x,y+1))){
                neighbors.add(new Point(x, y+1));
            }
            for(Point neighbor: neighbors){
                if(!reachable.contains(neighbor)){
                    if(neighbor.compareTo(new Point(dX, dY))==0){
                        return true;
                    }
                    reachable.add(neighbor);
                    next.offer(neighbor);
                }
            }
        }
        return false;
    }

    public boolean hasBeenWalked(int x1, int y1, int x2, int y2){
        return previouslyTraveled.contains(new Edge(x1, y1, x2, y2));
    }

    public boolean hasBeenWalked(Edge edge){
        return previouslyTraveled.contains(edge);
    }

    public void deletePath(int startX, int startY, int endX, int endY){
        Edge toAdd = new Edge(startX,startY,endX,endY);
        if(hasBeenWalked(toAdd)){
            System.out.println("Edge already travelled!");
            return;
        }
        pathsNoLongerAvailable.add(toAdd);
        if(!isSolvable()){
            pathsNoLongerAvailable.remove(toAdd);
            System.out.println("Invalid deletion!");
        }
    }

    static class Edge implements Comparable<Edge>{
        Point start, end;

        public Edge(int x1, int y1, int x2, int y2){
            start = new Point(x1, y1);
            end = new Point(x2, y2);
            if(start.compareTo(end)>0){
                Point tmp = end;
                end = start;
                start = tmp;
            }
        }

        @Override
        public int compareTo(Edge o) {
            int result = start.compareTo(o.start);
            if(result!=0) return result;
            return end.compareTo(o.end);
        }
    }

    static class Point implements Comparable<Point>{
        int x,y;
        public Point(int x, int y){
            this.x = x;
            this.y = y;
        }
        public int compareTo(Point o){
            int result = Integer.compare(x, o.x);
            if(result!=0) return result;
            result = Integer.compare(y, o.y);
            if(result!=0) return result;
            return 0;
        }
    }
}