Utwórz program lub funkcję, aby odłączyć kwadrat cyfr, odwracając (odwracając punkt środkowy) tylko wiersze i kolumny.
Wkład
Dane wejściowe będą siatką cyfr 9 x 9 w postaci ciągu 9 wierszy, jak poniżej:
986553229
264564891
759176443
643982153
567891234
526917874
685328912
891732537
117644378
Ten format wejściowy nie podlega negocjacji - wszelkie rozwiązania, które są „kreatywne” z formatem wejściowym, zostaną uznane za nieprawidłowe.
Wydajność
Wyjściem powinna być lista ruchów odwracających, które zastosowane do danych wejściowych w podanej kolejności powinny odtworzyć siatkę docelową.
Przykładowe dane wyjściowe (nie rozwiązanie poprzedniego przykładu wprowadzania):
28IF5D3EAB9G3
Ten format wyjściowy również nie podlega negocjacji. Wyjście nie powinno zawierać znaków nowej linii ani spacji, a jedynie znaki 1
- 9
i A
- I
(małe litery są dopuszczalne zamiast wielkich liter, jeśli wolisz).
Siatka docelowa (stan, który należy odtworzyć) jest następująca:
123456789
234567891
345678912
456789123
567891234
678912345
789123456
891234567
912345678
Liczby 1
- 9
powinny być używane jako instrukcje do odwracania wierszy, a litery A
- I
powinny być używane dla kolumn. Jest to pokazane poniżej z przywróconą siatką.
ABCDEFGHI
|||||||||
vvvvvvvvv
1 -> 123456789
2 -> 234567891
3 -> 345678912
4 -> 456789123
5 -> 567891234
6 -> 678912345
7 -> 789123456
8 -> 891234567
9 -> 912345678
Tak więc 8
środek przewraca drugi rząd od dołu, a F
środek przewraca szóstą kolumnę.
W przypadku, gdy żadne rozwiązanie nie jest możliwe, program powinien zakończyć się bez wypisywania niczego.
Przykłady
Wkład:
987654321
234567891
345678912
456789123
567891234
678912345
789123456
891234567
912345678
Wydajność:
1
W takim przypadku tylko górny wiersz wymaga przewrócenia, aby powrócić do stanu docelowego.
Wkład:
123456788
234567897
345678916
456789125
567891234
678912343
789123452
891234561
912345679
Wydajność:
I
W takim przypadku tylko ostatnia kolumna (kolumna I
) wymaga odwrócenia, aby odtworzyć stan celu.
Wkład:
123456788
798765432
345678916
456789125
567891234
678912343
789123452
891234561
912345679
Wydajność:
2I
W takim przypadku musimy odwrócić wiersz, 2
a następnie odwrócić kolumnę, I
aby powrócić do stanu docelowego.
Uwagi:
- W odpowiedzi podaj przykład użycia.
- Podane dane wyjściowe nie muszą być najkrótszą sekwencją, która zwróci stan celu - każda sekwencja, która zwróci stan celu, będzie działać tak długo, jak to działa (tj. Tak długo, jak mogę to przetestować)
- Postaram się przetestować każdą odpowiedź i głosować za tymi wszystkimi, którzy działają i oczywiście próbowali grać w golfa.
- To są zawody otwarte - zaakceptuję najkrótszą odpowiedź w przyszłym tygodniu, ale jeśli pojawi się nowa, ważniejsza odpowiedź, która będzie krótsza w dowolnym momencie w przyszłości, zmienię zaakceptowaną odpowiedź, aby to odzwierciedlić .
Nagroda została ustalona na 200 reputacji za najkrótszą odpowiedź otrzymaną do 23:59:59 (GMT) w dniu 26.01.2014.Nagroda została przyznana Howardowi za jego 268-znakowe rozwiązanie GolfScript .
Testowanie
Podaj odpowiedź swojego programu dla następujących trzech siatek testowych:
986553229
264564891
759176443
643982153
567891234
526917874
685328912
891732537
117644378
927354389
194762537
319673942
351982676
567891234
523719844
755128486
268534198
812546671
813654789
738762162
344871987
341989324
567891234
576217856
619623552
194435598
926543271
Stworzyłem mały program w języku Python do generowania prawidłowych siatek do celów testowych:
import random
def output(array):
print '\n'.join([''.join(row) for row in array])
def fliprow(rownum, array):
return [row[::1-2*(rownum==idx)] for idx,row in enumerate(array)]
def flipcol(colnum, array):
return zip(*fliprow(colnum, zip(*array)))
def randomflip(array):
op=random.randint(0,1)
row=random.randint(0,9)
if(op==1):
return fliprow(row, array)
else:
return flipcol(row, array)
def jumble(array):
arraycopy=array
for i in range(10, 1000):
arraycopy=randomflip(arraycopy)
return arraycopy
startarray=[
['1','2','3','4','5','6','7','8','9'],
['2','3','4','5','6','7','8','9','1'],
['3','4','5','6','7','8','9','1','2'],
['4','5','6','7','8','9','1','2','3'],
['5','6','7','8','9','1','2','3','4'],
['6','7','8','9','1','2','3','4','5'],
['7','8','9','1','2','3','4','5','6'],
['8','9','1','2','3','4','5','6','7'],
['9','1','2','3','4','5','6','7','8']]
print output(jumble(startarray))
(-2, 4)
,(2, 4)
,(2, -4)
, lub(-2, -4)
.A1
) i przesuń ją doB1
. Możesz dostać1
pozycjęB1
, ale będzie to płytka zB9
, a nie płytka zA1
. Ponieważ wolno nam przewracać tylko cały wiersz / kolumnę, najwyższy lewy 1 będzie zawsze w jednym z czterech najbardziej zewnętrznych narożników. Jeśli popełniłem błąd, daj mi znać.Odpowiedzi:
GolfScript,
300279268 znakówZauważ, że ten kod jest bardzo wolny (również z powodu ciężkich manipulacji blokami kodu) i może działać kilka minut. Kod jest bardzo nieskryptowy z dużą ilością zmiennych i wyraźnych pętli.
Napisałem bardziej analityczne rozwiązanie, które działało krócej niż sekundę. Zepsułem to całkowicie podczas gry w golfa. Niestety nie byłem w stanie przywrócić ani naprawić kodu w ciągu ostatnich dwóch dni. Dlatego stworzyłem tę wersję próbną, która i tak jest krótsza.
Odpowiedzi na puzzle podane powyżej:
źródło
Mathematica
582575503464282Do walki z golfistami muszę używać ciężkiej artylerii!
Wydajność:
Tutaj
PermutationGroup[...]
ustawia możliwe odwroty iGroupElementToWord[...]
rozwiązuje problem (około0.2
sekundy). Głównym problemem jest to, że trudno jest ustalić zgodność między pozycją9
w początkowej i końcowej siatce. Do gry w golfa robię to losowo (zajmuje to kilka sekund). Istnieją pewne ostrzeżenia, ale można je zignorować.Inne do testowania siatek:
Całkowicie odtwarza przykłady:
Poprzednie rozwiązanie (464)
bez sprytnych wbudowanych funkcji i przy czasie działania 4 ms:
Wszystkie nowe linie tutaj nie są konieczne.
Wydajność:
Pozostałe dwie siatki testowe:
Wyobrażanie sobie:
Ciąg wejściowy
i
może być generowany losowo przezKrótka dyskusja
Przerzuty mogą zamieniać tylko te elementy („poczwórne”):
Możliwe jest wymienianie tych elementów oddzielnie od innych elementów tylko wtedy, gdy zamówienie początkowe i końcowe ma ten sam podpis.
Odwrócenie tych czterech elementów tworzy naprzemienną grupę stopnia 4 (= grupa obrotów czworościennych). Każdy element z tej grupy składa się z 2 elementów generujących. Więc jeśli znamy pozycję początkową i końcową, możemy dekomponować odpowiednią transformację jako kombinację prostych przerzutów.
Detale
Dla sportowców zamieszczam szczegóły przed końcem nagrody!
Konwertuj ciąg
i
na macierzM
.Dodamy znaki do
S
. Teraz jest to pusty ciąg.H[i,j]
doda znaki
(1,2,3,...,9
) i znakj
(a,b,c,...,i
w bazie 36).Konwertuję elementy jako
aby uzyskać macierz docelową w następującej formie
W moim algorytmie są dwa główne etapy
Znajdź flipy, aby uzyskać podpisy jak w macierzy docelowej (np. Podpis
{-7,-1,1,7}
is1
i podpis{-6,2,-2,6}
is-1
):Obracaj każdy „poczwórny”, aby uzyskać odpowiednią kolejność:
Jest to najbardziej nietrywialna część algorytmu. Na przykład transformacja
1b1b
zostanie przekonwertowana{-7,-1,1,7}
na{-1,1,-7,7}
. Transformacja9h9h
zostanie przekonwertowana{-7,-1,1,7}
na{-7,7,-1,1}
. Mamy więc dwie mapyi chcemy przekształcić dowolną kolejność
{x,y,z,w}
do{1,2,3,4}
. Prostą metodą jest (z wyjątkiem wyszukiwania losowego)Nie mogę tego udowodnić, ale działa!
Ostatnim krokiem jest
Wykonuje trywialne odwrócenie środkowego rzędu i środkowej kolumny i zwraca wynik.
źródło
jot
487438d
jest czasownikiem, który pobiera ciąg siatki w określonym formacie i zwraca ciąg rozwiązania w określonym formacie.Przykładowe zastosowanie:
Teraz akceptuje albo nowy typ linii.
Rozwiązania do siatek testowych:
Jestem dość nowy w J; to może być jeszcze bardziej golfa.
Sprawdzanie, czy siatki są nieprawidłowe / nierozwiązywalne, podlega karze 123 znaków. Nie sądzę, aby inne dotychczasowe odpowiedzi zawierały takie sprawdzanie błędów.
Aby to zrobić, zmień pierwszy wiersz
d
na:i ostatnia linia do tego:
Zdecydowałem się powrócić
0
po takich błędach, że zwrócenie pustego łańcucha byłoby nie do odróżnienia od poprawnego rozwiązania w pełni rozwiązanej siatki. Zauważ, że zakłada to nowe wiersze UNIX (ponownie).źródło
LF
s reprezentują partycje pliku sekwencyjnego.DO#
540399Cóż, poświęcona wydajność (teraz zajmuje to do 30 sekund), wprowadzono zmienne dynamiczne, nieznacznie zmieniono logikę rozwiązania. I tak, teraz oczekuje danych wejściowych jako jednego ciągu z podziałem wierszy (zgodnie z wymaganiami reguł).
Oczywiście C # nie ma predefiniowanych funkcji matematycznych, więc ciężko byłoby walczyć z chłopakami Mathematica. Niemniej jednak było to wielkie wyzwanie, dzięki autorowi!
Siatki testowe:
Stare rozwiązanie (540)
Działa w mniej niż sekundę na dowolnym wejściu (testowane na tysiącach losowo generowanych siatek). Maksymalna długość łańcucha wyjściowego to 165 (początkowo każda siatka została rozwiązana w nie więcej niż 82 rzutach, ale podczas gry w golfa poświęciłem to).
Odpowiedz na przykład 1:
Odpowiedz na przykład 2:
Odpowiedz na przykład 3:
Odpowiedzi na kwadraty testowe:
źródło
1
,A
i2I
które są najprostszymi rozwiązaniami - ale to nie ma znaczenia, ponieważ nie oceniam długości rozwiązania siatki :-) Jeśli mógłbyś edytować i udzielę odpowiedzi na 3 siatki testowe (zobaczę, czy mogę to teraz uruchomić na moim komputerze Mac). Mogę dać ci +1.