Przegląd
Pearls (lub Masyu) to gra logiczna rozgrywana na siatce. Na siatce umieszczono czarno-białe perły. Celem jest utworzenie pojedynczej, zamkniętej pętli, która przechodzi przez każdą perłę, używając tylko odcinków linii prostych i kątów prostych.
Istnieją pewne zasady rządzące interakcją pętli z perłami:
- Białe perły należy przepłynąć prosto , ale pętla musi obrócić się w poprzedniej i / lub następnej komórce na swojej drodze.
- Czarne perły należy zwrócił na, ale pętla musi jechać prosto przez następnych i poprzednich komórek w swojej drodze.
- Pętla nie może się przecinać ani przecinać w inny sposób. Wszystkie komórki mają dokładnie zero lub dwie pętle wejścia / wyjścia.
Przykładowa łamigłówka z Wikipedii (i jej rozwiązanie):
Twoim celem jest rozwiązanie danej zagadki. Jeśli istnieje wiele możliwych rozwiązań, nie ma znaczenia, które z nich podasz.
Wejście
Dane wejściowe będą nierozwiązaną kwadratową siatką. Powyższy przykład wygląda następująco:
..w.w.....
....w...b.
..b.b.w...
...w..w...
b....w...w
..w....w..
..b...w...
w...b....w
......ww..
..b......b
w
jest białą perłą, b
jest czarną perłą i .
jest pustą komórką.
Załóżmy, że dane wejściowe są prawidłowe. Oznacza to, że jest dobrze uformowany i możliwe jest co najmniej jedno rozwiązanie. Wszystkie ważne łamigłówki mają co najmniej 3x3 i zawierają co najmniej jedną perłę.
Wynik
Dane wyjściowe to ciąg współrzędnych reprezentujących ścieżkę. Lewy górny róg siatki jest 0 0
, prawy górny jest n-1 0
, gdzie n jest szerokością siatki.
Ścieżka to po prostu seria uporządkowanych współrzędnych:
x1 y1 x2 y2 x3 y3 ...
Zakłada się, że ścieżka jest zamknięta, więc nie musisz powtarzać pierwszej współrzędnej na końcu, ale nie ma za to kary.
Wynik powinien składać się co najmniej ze wszystkich rogów ścieżki. Nie musisz wyprowadzać wszystkich komórek na ścieżce, jeśli nie ma zakrętu. Na przykład dane wyjściowe dla przykładu mogą zaczynać się od:
1 0 5 0 5 1 ...
lub
1 0 2 0 3 0 4 0 5 0 5 1 ...
Dane wyjściowe nie powinny zawierać żadnych komórek spoza ścieżki. Możesz zacząć od dowolnej komórki na ścieżce.
Skrawek
Oto fragment, którego możesz użyć do wizualizacji swojego rozwiązania. Po prostu wklej do siatki, nad którą pracujesz, i ścieżki, którą wypisujesz. Wiem, że patrzenie na mój kod jest bolesne, więc sugeruję, abyś nie;)
Przypadki testowe
Te przypadki testowe pokazują jedno możliwe wyjście dla każdego wejścia (z wyjątkiem ostatniego, który jest pokazany nierozwiązany). Mogą istnieć inne ważne ścieżki, możesz przejść w CW lub CCW lub zacząć w innym punkcie itp. Rozwiązania powinny być w stanie rozwiązać przypadki testowe w sekundach / minutach / godzinach, a nie dniach / tygodniach / eonach.
...
w..
..b
0 0 1 0 2 0 2 1 2 2 1 2 0 2 0 1
.wb..b
......
..b...
w.ww..
......
b....b
0 0 2 0 2 2 4 2 4 1 3 1 3 0 5 0 5 5 3 5 3 4 4 4 4 3 1 3 1 4 2 4 2 5 0 5 0 2 1 2 1 1 0 1
.....w.b.w..
ww..b...b...
.w.....b....
...wbww..b.b
....b.......
w.w.........
..w......b.b
.....bb.....
.....b.....w
w.ww..b.....
...w......w.
b..w.....b..
źródło
Odpowiedzi:
C 590
640 760 880 963 1018Brutalna siła jest do tego dość szybka. Test 12x12 przebiega poniżej 10ms. Wiedząc, że może wybrać język bardziej odpowiedni do gry w golfa.
Nie zakładam, że plansza jest kwadratowa, ponieważ większe puzzle zwykle nie są kwadratowe.
W
Określić ustawia limit wymiarów płyt. Rzeczywisty limit jest mniejszy,W - 2
ponieważ używam dodatkowych wierszy do granic, aby uniknąć kontroli granic.Przetestuj mnie .
Oto trudniejszy przypadek testowy:
Miałem szczęście, że mój kod znalazł rozwiązanie dość wcześnie (<5 minut), ale pełne wyszukiwanie trwa znacznie dłużej (67 minut).
źródło
Python - 1669
Wciąż dość długi, ale wystarczająco szybki, aby uruchomić ostatni przykład w niecałą sekundę na moim komputerze. Prawdopodobnie można go skrócić kosztem prędkości, ale na razie jest to prawie równoważne z nie golfowym kodem.
Przykładowe dane wyjściowe dla ostatniego przypadku testowego:
Kod:
Nie golfowany:
źródło
Lua,
830810765752739729710Działa z board1 i board2 w porządku, ale zajmuje trochę czasu na pokładzie3.
Może zaoszczędzić 9 bajtów, wypisując każdą ścieżkę zamiast tylko pierwszego ...
źródło