Napisz program, który określi, czy dana macierz reprezentuje quandle. Quandle to zespół wyposażony w pojedynczy (nie przemiennego, nie-asocjacyjnej) działania ◃ która spełnia następujące axioms:
- Operacja jest zamknięta, co oznacza, że
a◃b = c
zawsze jest elementem zestawu, jeślia
ib
są elementami zestawu. - Operacja jest tuż-self-rozdzielcze:
(a◃b)◃c = (a◃c)◃(b◃c)
. - Operacja jest podzielna na prawo: dla dowolnej wybranej pary
a
ib
istnieje jedna unikalnac
takac◃a = b
- Operacja jest idempotentna:
a◃a = a
Skończony quandle może być reprezentowany jako macierz kwadratowa. Poniżej znajduje się przykład quandle rzędu 5 ( źródło ).
0 0 1 1 1
1 1 0 0 0
3 4 2 4 3
4 2 4 3 2
2 3 3 2 4
Wartość znajdująca się w n-tym rzędzie i m-tej kolumnie (indeksowana 0) jest wartością n◃m. Na przykład w tym quandle 4◃1 = 3
. Niektóre właściwości quandle są łatwo widoczne z tej matrycy:
- Jest zamknięty, ponieważ w tej matrycy 5x5 pojawiają się tylko wartości 0-4.
- Jest idempotentny, ponieważ przekątna matrycy wynosi 0 1 2 3 4
- Jest podzielny na prawo, ponieważ żadna kolumna nie zawiera żadnych zduplikowanych wartości. (Wiersze mogą i zwykle będą.)
Trudniej jest przetestować właściwość samo-dystrybucji. Może istnieć skrót, ale najprostszą metodą jest iteracja każdej możliwej kombinacji trzech indeksów, aby to sprawdzić m[m[a][b]][c] = m[m[a][c]][m[b][c]]
.
Wejście
Dane wejściowe będą listą wierszy macierzy kwadratowej, przy użyciu indeksowania 0 lub indeksu 1 (do wyboru). Każdy wpis będzie jednocyfrową liczbą od 0
do 8
(lub 1
poprzez 9
). Będę elastyczny w zakresie formatu wejściowego. Niektóre dopuszczalne formaty obejmują:
- Najbardziej naturalne formatowanie języka dla macierzy lub list, takich jak
[[0 0 0][2 1 1][1 2 2]]
lub(0,0,0,2,1,1,1,2,2)
. - Lista wartości rozdzielonych spacjami, znakami nowej linii, przecinkami itp.
- Pojedynczy ciąg składający się ze wszystkich połączonych ze sobą wartości, takich jak
000211122
.
Możesz również przyjąć transpozycję macierzy jako dane wejściowe (zamieniając wiersze z kolumnami). Pamiętaj tylko, aby podać to w swojej odpowiedzi.
Wynik
Pojedyncza wartość true / falsey wskazująca status matrycy jako quandle.
Przykłady quandles
0
0 0
1 1
0 0 0
2 1 1
1 2 2
0 0 1 1
1 1 0 0
3 3 2 2
2 2 3 3
0 3 4 1 2
2 1 0 4 3
3 4 2 0 1
4 2 1 3 0
1 0 3 2 4
Przykłady non-quandles
nie zamknięte
1
0 0 0
2 1 1
1 9 2
nie jest samodystrybucyjny
0 0 1 0
1 1 0 1
2 3 2 2
3 2 3 3
(3◃1)◃2 = 2◃2 = 2
(3◃2)◃(1◃2) = 3◃0 = 3
nie podzielny na prawo
0 2 3 4 1
0 1 2 3 4
3 4 2 2 2
3 3 3 3 3
4 1 1 1 4
0 1 2 3
3 1 2 0
3 1 2 3
0 1 2 3
nie idempotentny
1 1 1 1
3 3 3 3
2 2 2 2
0 0 0 0
2 1 0 4 3
3 4 2 0 1
4 2 1 3 0
1 0 3 2 4
0 3 4 1 2
Odpowiedzi:
Python 2 ,
104103102 bajtówWejście jest transponowane. Wyjście odbywa się za pomocą kodu wyjścia, więc 0 (sukces) jest prawdą, a 1 (niepowodzenie) jest fałszem.
Wypróbuj online!
Jak to działa
e(t)
zwraca wyliczone wiersze macierzy wejściowej t - która reprezentuje operator ◃ - jako pary (indeks, wiersz).for(a,A)in e(t)
Np iteruje nich przechowywania indeks i rząd umieszczonego w A , więc staje się skrót .A
t[a]
Pomiędzy tym pierwszym,
for(b,B)in e(t)
ifor C in t
, iterujemy wszystkie możliwe uporządkowane krotki (a, b, c) w potędze kartezjańskiej t 3 .Dla każdej z tych krotek oceniamy wyrażenie
Wartość w nawiasach logicznych jest Fałsz wtedy i tylko wtedy, gdy jedno lub więcej z poniższych indywidualnych porównań robi to samo.
a==A[a]
zawiedzie (dla pewnej wartości a ) iff ◃ nie jest idempotentny.A[a]in B
nie powiedzie się, jeśli B nie zawiera wszystkich wskaźników A .Ponieważ A ma n wskaźników, a B ma n elementów, brak awarii oznacza, że elementy B pasują do wskaźników A , więc ◃ jest zamknięte i podzielne na prawo.
B>C[B[a]]
jest tautologią, ponieważ Python 2 uważał liczby za „mniejsze” niż iterowalne.C[B[a]]==t[C[b]][C[a]]
zawiedzie dla pewnej wartości, jeśli ◃ nie jest samorozdzielcze .Jeśli którekolwiek z porównań zwróci False , wyrażenie
(0%...)
wyrzuci błąd ZeroDivisionError . Ponadto, jeśli ◃ nie jest zamknięteA[a]
lubC[b]
może również wygenerować błąd IndexError . W obu przypadkach program kończy działanie z kodem stanu 1 (awaria).Jeśli wszystkie testy zakończą się pomyślnie, program zakończy się normalnie z kodem stanu 0 (sukces).
źródło
Haskell, 100 bajtów
Ta odpowiedź wykorzystuje transponowane dane wejściowe.
Wygląda na to, że nie mogę użyć osłony wzorca do powiązania operatora infix, więc
where
w tym przypadku używam .(Pierwsza wersja miała 108 bajtów, ale brakowało testu idempotencji, stała wersja wynosiła 120 bajtów, późniejsze wersje miały 108, 103 i 98 bajtów, ale musiałem zdać sobie sprawę z @nimi, że wszystkie były w błędzie: oczywiście muszę zrobić dobrze - test podzielności (co oznacza zamknięcie) przed wykonaniem jakichkolwiek niebezpiecznych
!!
operacji, ale nadal mogłem wykorzystać większość moich późniejszych pomysłów na golfa, a z jeszcze jednym było 102 bajty, teraz ulepszone przez zmianę kolejności operandów#
(co jest i tak ładniejsze, aby zrekompensować transpozycja), aby lepiej wykorzystać jego skojarzenie po lewej)Użyj w ten sposób:
źródło
Python 2 , 138 bajtów
m
to lista list liczb całkowitych.Wypróbuj online!
źródło
JavaScript (ES6), 150 bajtów
Pobiera dane wejściowe jako tablicę tablic kolumn liczb całkowitych.
źródło
Mathematica, 122 bajty
Czysta funkcja przyjmująca jako dane wejściowe tablicę 2D liczb całkowitych (indeksowanych 1), z wierszami i kolumnami odwróconymi od konwencji w pytaniu i zwracająca
True
lubFalse
. Pierwszy wiersz definiuje operację binarnejn_±m_
poprawki jako operację quandle.Dla tablicy
l
xl
, zamknięty i podzielny na prawo jest równoważny każdemu wierszowi (w moim przypadku) będącym pewną permutacją{1, ..., l}
, a idempotent jest równoważny dokładnie głównej przekątnej{1, ..., l}
.#&@@Union[Sort/@#]==Range@l==Array[#±#&,l=Length@#]
Wykrywa więc te trzy warunki. (ZastosowanieSort/@#
tutaj jest powodem, dla którego zdecydowałem się zamienić wiersze i kolumny).W celu zapewnienia właściwej dystrybucji dosłownie sprawdzamy wszystkie możliwości za pomocą
Array[±##2±#==(#2±#)±(#3±#)&,{l,l,l}])
. (Zauważ, że±##2±#
automatycznie rozwija się do(#2±#3)±#
, ponieważ##2
reprezentuje sekwencję drugiego i trzeciego argumentu w funkcji czystego z trzema zmiennymi). Następnie&&And@@Flatten@
sprawdza, czy każdy pojedynczy test został zaliczony. W przypadku niektórych nie zamkniętych quandli błędy mogą być zgłaszane, gdy próbuje uzyskać dostęp do części matrycy, która nie istnieje, ale poprawna odpowiedź jest nadal zwracana.źródło
±m__:=#[[m]];
Myślę. I jestDiagonal
wbudowany. I±
jest po lewej asocjacyjne, dzięki czemu można używać#2±#±(#3±#)
, ale jeśli nie pomylisz to krótszy o przeniesieniu#
się#3
i zrobić#±#2±#3==#±#3±±##2&
. I powinno być również możliwe zastąpienie całejFlatten@
części(...&~Array~{l,l,l}<>"")
l=Length
doRange@l
tego, ponieważ ten należy najpierw ocenić, więc jeśli używasz tej funkcji wielokrotnie, myślę, żeRange
nadal dostaje poprzedniel
, nie?C ++ 14, 175 bajtów
Jako nienazwana lambda, zakładając, że
n
jest podobnastd::vector<std::vector<int>>
i wraca przez parametr referencyjny. 0 jest fałszem, wszystko inne jest prawdą.Niegolfowane i użytkowanie:
źródło
int a,b,c,u,s=r=m.size()F
zamiastint s=r=m.size(),a,b,c F
,u=0;r*=s==A.size()&&a==A[a]F
zamiastr*=s==A.size()&&A[a]==a;int u=0 F
,r*=s>A[b]F
zamiastr*=A[b]<s F
i~u+(1<<s)
zamiastu-(1<<s)+1