Wyzwanie polega na napisaniu kodegolfa dla Hafniana matrycy . Hafnian o 2n
-by- 2n
matrycy symetrycznym A
jest zdefiniowany jako:
Tutaj S 2n reprezentuje zestaw wszystkich permutacji liczb całkowitych od 1
do 2n
, to znaczy [1, 2n]
.
Link do wikipedii mówi o macierzach przylegania, ale twój kod powinien działać dla wszystkich symetrycznych macierzy wejściowych o wartościach rzeczywistych.
Dla zainteresowanych aplikacjami Hafnian link do mathoverflow omawia więcej.
Kod może przyjmować dane wejściowe w dowolny sposób i dawać dane wyjściowe w dowolnym rozsądnym formacie, ale w odpowiedzi należy podać pełny sprawdzony przykład, w tym jasne instrukcje dotyczące sposobu wprowadzania danych wejściowych do kodu.
Matryca wejściowa jest zawsze kwadratowa i będzie miała maksymalnie 16 na 16. Nie ma potrzeby obsługi pustej macierzy lub macierzy o nieparzystym wymiarze.
Realizacja referencyjna
Oto przykładowy kod python od pana Xcodera.
from itertools import permutations
from math import factorial
def hafnian(matrix):
my_sum = 0
n = len(matrix) // 2
for sigma in permutations(range(n*2)):
prod = 1
for j in range(n):
prod *= matrix[sigma[2*j]][sigma[2*j+1]]
my_sum += prod
return my_sum / (factorial(n) * 2 ** n)
print(hafnian([[0, 4.5], [4.5, 0]]))
4.5
print(hafnian([[0, 4.7, 4.6, 4.5], [4.7, 0, 2.1, 0.4], [4.6, 2.1, 0, 1.2], [4.5, 0.4, 1.2, 0]])
16.93
print(hafnian([[1.3, 4.1, 1.2, 0.0, 0.9, 4.4], [4.1, 4.2, 2.7, 1.2, 0.4, 1.7], [1.2, 2.7, 4.9, 4.7, 4.0, 3.7], [0.0, 1.2, 4.7, 2.2, 3.3, 1.8], [0.9, 0.4, 4.0, 3.3, 0.5, 4.4], [4.4, 1.7, 3.7, 1.8, 4.4, 3.2]])
262.458
Strona wiki została teraz (2 marca 2018 r.) Zaktualizowana przez ShreevatsaR, aby zawierała inny sposób obliczania Hafniana. Byłoby bardzo interesujące zobaczyć ten golf.
źródło
Odpowiedzi:
R ,
150142127119 bajtówWypróbuj online!
Używa tej samej sztuczki, którą odkryłem, grając w golfa w dół tej odpowiedzi, aby zindeksować macierz
P
, a @ Vlo zasugerował podejście do całkowitego usunięciafor
pętli dla -6 bajtów!Aby utworzyć nowy przypadek testowy, możesz to zrobić
matrix(c(values,separated,by,commas,going,across,rows),nrow=2n,ncol=2n,byrow=T)
.Objaśnienie: (kod jest taki sam; używa
apply
raczejfor
pętli niż pętli, ale logika jest w przeciwnym razie identyczna).źródło
N
i przenosićk
je do jednej instrukcji, usuwając{}
i zapisując kolejne dwa bajty.Pyth , 24 bajty
Wypróbuj tutaj!
Stara wersja, 35 bajtów
Wypróbuj tutaj!
źródło
a[b]
wystarczy konkurować).xÍysè<¹sès·<ysè<è
Lmao? PS Mine ma 40 bajtów i nie działa tak dobrze hah, więc nie krępuj się opublikować, nie jestem pewien, czy uda mi się skończyć, zanim będę musiał wrócić do domu.Stax ,
23221917 bajtówUruchom i debuguj online
Odpowiada to reprezentacji ascii tego samego programu.
W programie występuje błąd zaokrąglania zmiennoprzecinkowego. W szczególności raportuje
33673.5000000011
zamiast33673.5
. Myślę jednak, że dokładność jest do przyjęcia, biorąc pod uwagę, że program ten działa na wartościach zmiennoprzecinkowych. Jest również bardzo wolny, zajmuje prawie minutę na przykładowe dane wejściowe na tym komputerze.źródło
05AB1E , 21 bajtów
Wypróbuj online!
Stara wersja, 32 bajty
Wypróbuj online!
Jak to działa?
źródło
èsè
, hah ... haha ... Jestem karna.Galaretka , 19 bajtów
Wypróbuj online!
Alternatywna wersja, 15 bajtów, wyzwanie postdate
Galaretka wreszcie uzyskała indeksowanie macierzy n-wymiarowych.
Wypróbuj online!
Jak to działa
Wersja 19-bajtowa działa w podobny sposób; po prostu musi się wprowadzić
œị
.źródło
C (gcc) ,
288285282293292272271 bajtówif(...)...k=0...else...,j=0...
doif(k=j=0,...)...else...
- i wykonano przesunięcie indeksu.float
macierzy.2*j+++1
w golfaj-~j++
.int
deklarację typu zmiennej i nie używając funkcji silni, lecz zamiast tego obliczając wartość silni przy użyciu już istniejącej pętli for.S=S/F/(1<<n);
w golfaS/=F*(1<<n);
.Wypróbuj online!
Wyjaśnienie
Wypróbuj online!
Rdzeniem programu jest następujący generator permutacji, który przechodzi przez pętlę
S_n
. Całe obliczenia Hafniana są po prostu oparte na nim - i dalej w golfa.Wypróbuj online!
źródło
float
macierze.2*j+++1
jest równoważne zj+j+++1
, co jest tym samym coj-(-j++-1)
, więc możemy efektywnie wykorzystać bitowe uzupełnienie, aby zapisać bajt:j-~j++
( Wypróbuj online )R ,
8478 bajtówWypróbuj online!
Edycja: Dzięki Vlo za -6 bajtów.
Wygląda na to, że wszyscy tutaj wdrażają standardowy algorytm referencyjny z permutacjami, ale starałem się wykorzystać wiedzę społeczności zdobytą w powiązanym wyzwaniu , które jest w zasadzie tym samym zadaniem ukierunkowanym na najszybszy kod zamiast golfa.
Okazuje się, że dla języka, który jest dobry w krojeniu macierzy (jak R), algorytm rekurencyjny:
hafnian(m) = sum(m[i,j] * hafnian(m[-rows and columns at i,j])
jest nie tylko szybszy, ale także dość golfowy. Oto nielepszy kod:źródło
If
z nawiasami, -4 do użyciaF
jako zmienna zainicjowana, -1 do przypisanian
w obrębieif
. tio.run/##XU/LCsIwELz7FcFTVtOQl1pf1/…Galaretka , 29 bajtów
Wypróbuj online!
Myślę, że
;@€€Wị@/€€P€
część można prawdopodobnie zagrać w golfa. Musisz wrócić później, aby sprawdzić i dodać wyjaśnienie.źródło
J
) przed rozpoczęciem gry w golfa . Galaretowe umysły myślą podobnie ? źródłoLḶŒ!s€2ḅL‘ịFZµPS÷JḤ$P$
TIOHaskell , 136 bajtów
-14 bajtów dzięki ovs.
Wypróbuj online!
Ugh ...
źródło
MATL ,
292422 bajtówWypróbuj online! Lub sprawdź wszystkie przypadki testowe: 1 , 2 , 3 .
Jak to działa
źródło
Wolfram Language (Mathematica) , 85 bajtów
Wypróbuj online!
źródło
Kokos ,
165145128127 127 bajtów-1 bajt dzięki Mr. Xcoder
Wypróbuj online!
źródło
Perl 6, 86 bajtów
źródło