Na temat naszych przyjaciół z Puzzling.SE opublikowano następującą łamigłówkę: Czy tę łamigłówkę chromatyczną zawsze można rozwiązać? autor: Edgar G. Możesz zagrać tutaj .
Wyjaśnienie puzzli
Biorąc pod uwagę m x n
siatkę z kafelkami trzech różnych kolorów, możesz wybrać dowolne dwa sąsiednie kafelki , jeśli ich kolory są różne . Te dwa kafelki są następnie konwertowane na trzeci kolor, tj. Na jeden kolor nie reprezentowany przez te dwa kafelki. Układanka jest rozwiązana, jeśli wszystkie płytki mają ten sam kolor . Najwyraźniej można udowodnić, że ta łamigłówka jest zawsze do rozwiązania, jeśli ani m
nie n
można podzielić przez 3.
Oczywiście wymaga to algorytmu rozwiązywania. Napiszę funkcję lub program, który rozwiązuje tę zagadkę. Zauważ, że funkcje z „efektami ubocznymi” (tj. Wyjście jest włączone, stdout
a nie w niektórych niezręcznych wartościach zwracanych przez dane) są wyraźnie dozwolone.
Wejście wyjście
Wejście będzie m x n
macierz składa się z liczb całkowitych 1
, 2
i 3
(lub 0
, 1
, 2
jeśli jest to wygodniejsze). Możesz wziąć to wejście w dowolnym rozsądnym formacie. Zarówno m
a n
są >1
i nie jest podzielna przez 3. Można założyć puzzli nie jest rozwiązany
Następnie rozwiążesz zagadkę. Będzie to wymagało powtórnego wyboru dwóch sąsiadujących ze sobą płytek do „konwersji” (patrz wyżej). Będziesz generować dwie współrzędne tych płytek dla każdego kroku, który wykonał algorytm rozwiązywania. Może to być również dowolny rozsądny format wyjściowy. Możesz swobodnie wybierać między indeksowaniem współrzędnych w oparciu o 0 lub w oparciu o 1, a także o tym, czy wiersze lub kolumny są najpierw indeksowane. Proszę jednak o tym wspomnieć w swojej odpowiedzi.
Twój algorytm powinien działać w rozsądnym czasie na oryginalnej obudowie 8x8. Brutalne wymuszanie go całkowicie jest wyraźnie niedozwolone, tzn. Twój algorytm powinien działać zgodnie O(k^[m*(n-1)+(m-1)*n])
z k
liczbą kroków potrzebnych do rozwiązania. Jednak rozwiązanie nie musi być optymalne. Dowód podany w połączonym pytaniu może dać ci wyobrażenie, jak to zrobić (np. Najpierw zrób wszystkie kolumny, używając tylko sąsiadujących pionowo płytek, a następnie zrób wszystkie rzędy)
Przypadki testowe
W tych przypadkach testowych współrzędne są oparte na 1, a wiersze są najpierw indeksowane (jak MATLAB / Octave i prawdopodobnie wiele innych).
Input:
[1 2]
Output: (result: all 3's)
[1 1],[1,2]
Input:
[ 1 2
3 1 ]
Output: (result: all 1's)
[1 1],[2 1] (turn left column into 2's)
[2 1],[2 2] (turn right column into 3's)
[1 1],[1 2] (turn top row into 1's)
[2 1],[2 2] (turn bottom row into 1's)
Input:
[1 2 3 2
3 2 1 1]
Output: (result: all 3's)
[1 1],[1 2]
[1 3],[1 4]
[1 2],[1 3]
[1 1],[1 2]
[1 2],[1 3]
[1 1],[1 2]
[1 3],[1 4]
[2 1],[2 2]
[1 1],[2 1]
[1 2],[2 2]
[1 3],[2 3]
[1 4],[2 4]
W razie potrzeby mogę opublikować zestawienie większych przypadków testowych, ale myślę, że powinno to wystarczyć.
źródło
Odpowiedzi:
Rubinowy, 266 bajtów
Mniej więcej tylko port rozwiązania Octave, tyle że najpierw rozwiązuje wiersze zamiast kolumn. Dane wejściowe to tablica tablic, przy czym tablice wewnętrzne są wierszami. Ruchy wyjściowe są
[row, column, row, column]
. Zestaw testowyNie obeznany z wyjaśnieniem
źródło
intersect
jest to tak nieporęczne słowo kluczowe)intersect
, nie wiem, czy możesz naprawić to, jak działa mój, ponieważ Rubyfind
działa w zasadzie na funkcje, a twojefunction
słowo kluczowe jest równie nieporęczne.find
- dzięki! Mimo to nigdzie nie jest blisko ciebie ...Oktawa,
334313 bajtówPonieważ wyzwanie może wydawać się nieco zniechęcające, przedstawiam własne rozwiązanie. Nie udowodniłem formalnie, że ta metoda działa (przypuszczam, że sprowadzi się to do udowodnienia, że algorytm nigdy nie utknie w pętli), ale jak dotąd działa idealnie, wykonując 100x100 testów w ciągu 15 sekund. Zauważ, że wybrałem funkcję z efektami ubocznymi, a nie taką, która zwraca wszystkie współrzędne, ponieważ zaoszczędziło mi to kilka bajtów. Współrzędne są główne, oparte na 1 i sformatowane jako
row1 col1 row2 col2
. Kolory wejściowe są,0,1,2
ponieważ działa to lepiejmod
, kosztem konieczności używanianumel
zamiastnnz
. Wersja w golfa: Edycja: zapisano kilka kolejnych bajtów przy użyciu techniki z odpowiedzi Kevina Lau.Przykład GIF algorytmu rozwiązywania:
Wersja bez golfa:
źródło
Lua,
594575559 bajtówOstrzeżenie Przed golfem jest jeszcze wiele pracy! Powinienem być w stanie wziąć to co najmniej poniżej 500 bajtów. Na razie jest to pierwsze rozwiązanie, które zadziałało i wciąż nad tym pracuję.
Po zakończeniu przedstawię pełne wyjaśnienie.
źródło
Rdza,
496495 bajtówNiestety nie mogę pokonać OP, ale jeśli chodzi o odpowiedź Rust, jestem całkiem zadowolony z bajtu.
Wkład: wektor liczb oraz liczba kolumn. Na przykład
wyjścia
do wiersza poleceń.
Najpierw rozwiązuję każdy wiersz, a następnie wynikową kolumnę tylko raz, ale drukuję kroki dla wszystkich kolumn. Jest to więc całkiem wydajne :-P.
Z formowaniem:
Edycja: teraz zwraca kolor rozwiązania, co oszczędza mi średnik ^^
źródło
Befunge ,
197368696754 bajtów(tak, robię golf w odwrotnym kodzie, im więcej bajtów, tym lepiej)
Pomyślałem, że napisanie tego algorytmu w Befunge może być wyzwaniem i może być świetną zabawą
Chciałbym, aby był to program społecznościowy, więc jeśli ktoś chce nad tym popracować, zrób to.W końcu wszystko zrobiłem do tej pory sam, więc skończę sam (prawie gotowe)
Co jeszcze zostało zrobione: kod w kształcie trolla
(tak, to troll, uwierz mi)
Zasadniczo czyta tablicę i oblicza ruch do rozwiązania wierszy, biorąc pod uwagę dane wejściowe jako
(cała tablica jest przekazywana jako lista [wiersz 1, wiersz 2, wiersz 3,…])
wyjście jest
wiersze i kolumny zaczynają się od 0.
Teraz, gdy rzędy są rozwiązane, prawie gotowe! Brawo!
Objaśnienie: (zostanie zaktualizowany później)
Jest więc 5 głównych części:
Szare części są inicjalizacjami
Oto głębsze objaśnienie modułu, który znajduje pola do połączenia (które są tutaj zakodowane)
Część CALL ma miejsce, gdy wskaźnik instrukcji przechodzi do innego modułu, aby połączyć się z ramkami. Wraca do tego modułu poprzez wpis „B”
Oto pseudo kod: (currentx jest powiązany z odczytem tablicy) Dla:
Zauważ, że jeśli chcesz go przetestować, będziesz musiał wstawić trochę miejsca na końcu i nowych linii, aby było wystarczająco dużo miejsca do przechowywania tablicy, jeśli chcesz użyć interpretacji, którą połączyłem. 22 + liczba wierszy na wejściu jako końcowe linie, a 34 + liczba kolumn jako końcowe spacje w jednym wierszu powinny być prawidłowe.
źródło
\r\n
zamiast\n
tylko?)C, 404 bajty
Mój pierwszy golf w golfa, jestem całkiem zadowolony z tego, jak się okazało. Jednak trwało to o wiele za długo. Nie jest to w pełni standardowy C, tylko cokolwiek skompiluje się pod gcc bez specjalnych flag (i ignorując ostrzeżenia). Jest tam więc funkcja zagnieżdżona. Funkcja
f
przyjmuje wymiarym
in
jako pierwsze argumenty, a jako trzeci argument przenosi (wskaźnik wewnętrzny) do tablicy o rozmiarzem
×n
(najpierw indeksowane wierszami). Pozostałe argumenty są fałszywymi argumentami, nie musisz ich przekazywać, są one po prostu, aby zaoszczędzić bajty na deklarowaniu zmiennych. Zapisuje każdą zmienioną parę do STDOUT w formacierow1,col1:row1,col1;
, z średnikiem oddzielającym pary. Wykorzystuje indeksowanie 0.Użyłem nieco innego algorytmu niż OP do rozwiązywania pojedynczych wierszy / kolumn. To idzie mniej więcej tak (pseudokod):
W
for(;~b;b--)
Wykonuje pętla dokładnie dwa razy, przy drugim przejściu rozwiązuje kolumn zamiast wierszy. Odbywa się to poprzez zamianęn
im
oraz zmianę wartościo
ip
które są wykorzystywane w celu rozwiązania arytmetyki wskaźnik tablicy.Oto wersja, która nie jest golfem, z testową kartą główną i drukuje całą tablicę po każdym ruchu (naciśnij klawisz Enter, aby przejść do kroku 1):
źródło