Napisz program lub funkcję, która przyjmuje trzy liczby całkowite, szerokość w
, wysokość h
i liczbę kroków s
. Będziesz rysowanie non-self-przecinających błądzenia losowego s
kroki długo na zasadzie 5*w
przez 5*h
piksela obrazu, w którym każda komórka 5 przez 5 piksel jest albo pusty (czysty beż) lub jednej z tych dwanaście prostych „rury”:
Obraz powyżej jest powiększony, aby pokazać szczegóły. Oto rury w rzeczywistym rozmiarze:
(Szare linie służą tylko do oddzielenia typów rur).
Spacer losowy będzie pojedynczą ciągłą ścieżką rury, która zaczyna się w jednym punkcie końcowym rury (jeden z czterech dolnych typów rur) i kończy w innym punkcie końcowym rury.
Start z pustym w
przez h
siatkę i losowo wybrać jedną komórkę być punktem wyjścia. Następnie losowo wybierz jeden z czterech kierunków, od którego chcesz zacząć, i narysuj odpowiedni punkt końcowy rury. Ta komórka początkowa oznacza pierwszy krok na spacerze i za każdym razem, gdy narysujesz nową komórkę lub zastąpisz istniejącą, liczy się to jako kolejny krok.
Teraz, wielokrotnie, losowo wybierz iść w prawo, w lewo lub prosto, rysując odpowiednią komórkę rury, jeśli wybrany kierunek jest prawidłowy. Wróć i wybierz ponownie, jeśli kierunek jest nieprawidłowy, dopóki nie zostanie utworzona pełna s
ścieżka kroku. Ścieżka powinna kończyć się punktem końcowym potoku, który może znajdować się w dowolnym miejscu na siatce, w zależności od kursu pokonanego przez ścieżkę.
Bardzo ważne jest, aby pamiętać, że tylko dwie proste komórki rurowe mogą zostać zastąpione i tylko przez prostą komórkę rurową o przeciwnej orientacji, czego wynikiem jest komórka przecięcia. W przeciwnym razie wszystkie rury muszą być umieszczone w pustych komórkach.
Po narysowaniu skrzyżowania należy narysować część ścieżki dalej od komórki początkowej.
Od Ciebie zależy, czy siatka ma okresowe warunki brzegowe (PBC), tj. Czy rura wychodząca z jednej strony siatki wyjdzie na drugą stronę. Bez PBC granica siatki liczy się jako bariera, na którą można wpaść tak jak inne rury.
Przypadki specjalne
- Gdy
s
wynosi 0, nie należy rysować żadnych rur, a wynik powinien być pusty5*w
według5*h
obrazu (tzn. Wszystkie beżowe). Kiedy
s
1 oznacza pojedynczą końcówkę rurynależy narysować w losowo wybranej komórce początkowej.
Inne szczegóły
- Możesz założyć, że
s
jest to co najwyżej,w*h
więc ścieżka zawsze będzie możliwa. (Chociaż dłuższe ścieżki są możliwe ze względu na skrzyżowania.) w
ih
zawsze będą pozytywne.- Wszystkie losowe wybory muszą być jednakowo losowe. np. nie powinieneś unikać wykonywania skrzyżowań, gdy są one możliwe, nawet jeśli to ułatwia problem. Generatory liczb pseudolosowych są dozwolone.
- Zamiast czarnego, niebieskiego i beżowego można zastosować dowolne trzy odrębne wizualnie kolory.
- Twoje zdjęcia wyjściowe mogą być powiększone, tak aby były naprawdę
5*w*k
w5*h*k
pikselach, gdziek
jest dodatnią liczbą całkowitą. (Zalecane jest powiększenie wszystkich opublikowanych przykładów, nawet jeśli maszk
1.) - Można użyć dowolnego popularnego bezstratnego formatu pliku obrazu, a obraz może zostać zapisany w pliku, wyświetlony lub wyrzucony na surowo na standardowe wyjście.
Najkrótszy kod w bajtach wygrywa.
Przykłady
(Wszystko powiększone o 500%.)
Jeśli wejście jest, w=2, h=1, s=0
wówczas wyjście zawsze będzie:
Jeśli wejście jest, w=2, h=1, s=1
wówczas wyjście będzie jednym z tych obrazów z jednakową szansą:
Jeśli wejście jest, w=2, h=1, s=2
wtedy wyjście będzie
lub ewentualnie
jeżeli zakłada się, że siatka ma PBC.
(Pamiętaj, że rozpoczęcie ścieżki w podobny sposób uniemożliwiłoby drugi krok).
Oto kilka możliwych wyników w=3, h=2, s=6
, przy założeniu PBC:
Oto możliwe wyjście w=3, h=3, s=9
, przy założeniu PBC:
Zauważ, że ścieżka nie musiała obejmować wszystkich komórek z powodu przecięcia liczonego jako dwa kroki. Możemy również wywnioskować, że narożny punkt końcowy był komórką początkową, ponieważ wiadukt przecięcia musiał zostać narysowany później. W ten sposób możemy wywnioskować sekwencję losowych wyborów, które zostały dokonane:
start at top left, facing east
go straight
go right
go right
go right
go straight
go left
go right
end
Na koniec oto przykłady w=4, h=5, s=20
i w=4, h=5, s=16
:
źródło
You will be drawing a non-self-intersecting random walk
czy przecina się samo z siebie czy nie?Odpowiedzi:
CJam, 274
Wypróbuj online
Wykorzystuje PBC, wyjścia w formacie PGM. Możesz usunąć
:+
koniec, aby uzyskać ładniejszy efekt wizualny w przeglądarce.Przy większych nakładach jest bardzo wolny, szczególnie jeśli liczba kroków jest zbliżona do obszaru.
Przykład wyniku dla danych wejściowych
4 3 10
(skalowane 500%):Krótkie wyjaśnienie:
Ogólne podejście to:
źródło
QBasic,
517516 bajtóww
,h
is
od danych wejściowych użytkownika, oddzielonych przecinkami.Podejście polega na wypróbowaniu losowego kierunku na każdym kroku i rozpoczęciu od początku, jeśli spowoduje to nieprawidłowy ruch. Rysujemy rury zgodnie z ustalonymi kierunkami i używamy
POINT
do testowania punktów na ekranie pod kątem naszych warunków ważności. Ruch jest ważny, jeśli nie wykracza poza granice siatki i:Podobnie jak odpowiedź CJam aditsu , ten kod jest bardzo wolny i może być przytłaczająco powolny, jeśli
s
stanowi znaczną częśćw*h
. W mojej konfiguracji QB64 pojawia się odpowiedź5,5,19
dość szybko, ale trwa to dłużej niż byłem gotów czekać5,5,20
.Jeśli chcesz uruchamiać większe / bardziej gęsto upakowane przykłady, oto moje oryginalne podejście z użyciem wyszukiwania w pierwszej kolejności . Jest znacznie wydajniejszy, kosztem aż 300 dodatkowych bajtów.
Przykładowe dane wyjściowe dla danych wejściowych
10, 10, 100
, rzeczywisty rozmiar:Jeszcze bardziej udoskonaloną wersję można znaleźć w tej treści . Oprócz tego, że nie jest golfistą i nie jest dokładnie komentowany, skaluje on wynik o stały współczynnik i pozwala na ustawienie opóźnienia między krokami, umożliwiając obserwowanie algorytmu DFS w działaniu. Oto przykładowy przebieg:
źródło