Problem

Utwórz program lub funkcję, która może obliczyć wynik macierzy podniesionej do n- ^tej potęgi. Kod weźmie dowolnej macierzy kwadratowej A i nieujemną liczbę całkowitą, n i powrót macierz wartości A ⁿ .

Ograniczenia

Wbudowane funkcje obliczające moc macierzy i iloczyn macierzy są niedozwolone.

Obowiązują pozostałe standardowe zasady gry w golfa kodowego.

Wyjaśnienie

Biorąc pod uwagę macierz kwadratową A , wartość A ⁿ = AA ⋯ A (iloczyn macierzy A z samym sobą, n razy). Jeśli n jest dodatnie, stosowany jest właśnie wspomniany standard. Gdy n wynosi zero, macierz identyczności z tego samego rzędu A jest wynik.

Cel

To jest gra w golfa i wygrywa najkrótszy kod.

Przypadki testowe

Tutaj A jest macierzą wejściową, n jest liczbą całkowitą na wejściu, a r jest macierzą wyjściową, gdzie r = A ⁿ .

n = 0
A = 62 72
    10 34
r =  1  0
     0  1

n = 1
A = 23 61 47
    81 11 60
    42  9  0
r = 23 61 47
    81 11 60
    42  9  0

n = 2
A =  12  28 -26  3
     -3 -10 -13  0
     25  41   3 -4
    -20 -14  -4 29
r = -650 -1052  -766 227
    -331  -517   169  43
     332   469 -1158 -53
    -878  -990   574 797

n = 4
A = -42 -19  18 -38
    -33  26 -13  31
    -43  25 -48  28
     34 -26  19 -48
r = -14606833  3168904 -6745178  4491946
      1559282  3713073 -4130758  7251116
      8097114  5970846 -5242241 12543582
     -5844034 -4491274  4274336 -9196467

n = 5
A =  7  0 -3  8 -5  6 -6
     6  7  1  2  6 -3  2
     7  8  0  0 -8  5  2
     3  0  1  2  4 -3  4
     2  4 -1 -7 -4 -1 -8
    -3  8 -9 -2  7 -4 -8
    -4 -5 -1  0  5  5 -1
r =  39557  24398 -75256 131769  50575   14153  -7324
    182127  19109   3586 115176 -23305    9493 -44754
    146840  31906 -23476 190418 -38946   65494  26468
     42010 -21876  41060 -13950 -55148   19290   -406
     44130  34244 -35944  34272  22917  -39987 -54864
      1111  40810 -92324  35831 215711 -117849 -75038
    -70219   8803 -61496   6116  45247   50166   2109

Galaretka , 17 16 15 bajtów

Z×'³S€€
LṬ€z0Ç¡

Wypróbuj online!

Permalink z wyjściem siatki: przypadek testowy 1 | przypadek testowy 2 | przypadek testowy 3 | przypadek testowy 4 | walizka testowa 5

Jak to działa

LṬ€z0Ç¡  Main link. Arguments: A (matrix), n (power)

L        Get the length l of A.
 Ṭ€      Turn each k in [1, ..., l] into a Boolean list [0, 0, ..., 1] of length k.
   z0    Zip; transpose the resulting 2D list, padding with 0 for rectangularity.
         This constructs the identity matrix of dimensions k×k.
     Ç¡  Execute the helper link n times.

Z×'³S€€  Helper link. Argument: B (matrix)

Z        Zip; transpose rows and columns of B.
   ³     Yield A.
 ×'      Spawned multiplication; element-wise mutiply each rows of zipped B (i.e.,
         each column of B) with each row of A.
         This is "backwards", but multiplication of powers of A is commutative.
    S€€  Compute the sum of each product of rows.

MATL , 20 bajtów

XJZyXyi:"!J2$1!*s1$e

Wypróbuj online!

Wyjaśnienie

Pozwala to uniknąć mnożenia macierzy, wykonując ją ręcznie, wykorzystując mnożenie elementarne z rozgłoszeniem, a następnie sumę wektorową. W szczególności, aby pomnożyć macierze Mi Noba rozmiary s × s :

1. Transpozycji M. Wywołaj macierz wynikową P.
2. Dopuść wymiary Ntakich, które Nsą „obrócone” za pomocą osi obrotu wzdłuż pierwszego wymiaru, dając , powiedzmy, macierz 3D s × 1 × s 3D Q.
3. Pomnóż każdy element Prazy każdy element Q, z niejawną transmisją. Oznacza to, że Pjest on automatycznie replikowany s razy wzdłuż trzeciego wymiaru i Qjest replikowany s razy wzdłuż drugiego wymiaru, aby uzyskać oba s × s × s , zanim nastąpi rzeczywiste zwielokrotnienie elementarne.
4. Zsumuj wzdłuż pierwszego wymiaru, aby uzyskać tablicę 1 × s × s .
5. Ściśnij wiodący wymiar singletonu, aby uzyskać wynik s × s .

Skomentowany kod:

XJ      % take matrix A. Copy to clipboard J
ZyXy    % generate identity matrix of the same size
i:      % take exponent n. Generate range [1 2 ... n] (possibly empty)
"       % for each element in that range
  !     %   transpose matrix with product accumulated up to now (this is step 1)
  J     %   paste A
  2$1!  %   permute dimensions: rotation along first-dimension axis (step 2)
  *     %   element-wise multiplication with broadcast (step 3)
  s     %   sum along first dimension (step 4)
  1$e   %   squeeze out singleton dimension, i.e. first dimension (step 5)
        % end for. Display

APL, 32 31 znaków

{⍺=0:(⍴⍵)⍴1⍨1+≢⍵⋄+.×⍨⍣(⍺-1)⊣⍵}

Lewy argument moc do podniesienia, prawy argument macierz. Najtrudniejszym (najbardziej zajmującym miejsce) bitem jest budowanie macierzy tożsamości dla przypadku, gdy pożądanym wykładnikiem jest 0. Rzeczywiste obliczenia oparte są na fakcie, że uogólniony produkt wewnętrzny ( .) z operandami +i ×jako operandami jest faktycznie produktem macierzy. To w połączeniu z ⍣operatorem mocy („powtórzenie”) tworzy mięso roztworu.

Sage, 112 bajtów

lambda A,n:reduce(lambda A,B:[[sum(map(mul,zip(a,b)))for b in zip(*B)]for a in A],[A]*n,identity_matrix(len(A)))

Wypróbuj online

Wyjaśnienie:

Wewnętrzna lambda ( lambda A,B:[[sum(map(mul,zip(a,b)))for b in zip(*B)]for a in A]) jest prostą implementacją mnożenia macierzy. Zewnętrzna lambda ( lambda A,n:reduce(...,[A]*n,identity_matrix(len(A)))) używa reducedo obliczania mocy macierzy przez iterowane mnożenie macierzy (przy użyciu wspomnianej wcześniej domowej funkcji mnożenia macierzy), z macierzą tożsamości jako wartością początkową do obsługi n=0.

Julia, 90 86 68 bajtów

f(A,n)=n<1?eye(A):[A[i,:][:]⋅f(A,n-1)[:,j]for i=m=1:size(A,1),j=m]

Jest to funkcja rekurencyjna, która przyjmuje matrycę ( Array{Int,2}) i liczbę całkowitą i zwraca macierz.

Nie golfowany:

function f(A, n)
    if n < 1
        # Identity matrix with the same type and dimensions as the input
        eye(A)
    else
        # Compute the dot product of the ith row of A and the jth column
        # of f called on A with n decremented
        [dot(A[i,:][:], f(A, n-1)[:,j]) for i = (m = 1:size(A,1)), j = m]
    end
end

Wypróbuj online! (obejmuje wszystkie przypadki testowe oprócz ostatniego, co jest zbyt wolne dla witryny)

Zaoszczędź 18 bajtów dzięki Dennisowi!

Python 2.7, 158 145 bajtów

Najgorsza odpowiedź tutaj, ale moja najlepsza gra w golfa w Pythonie. Przynajmniej fajnie było się uczyć mnożenia macierzy.

Gra w golfa:

def q(m,p):
 r=range(len(m))
 if p<1:return[[x==y for x in r]for y in r]
 o=q(m,p-1)
 return[[sum([m[c][y]*o[x][c]for c in r])for y in r]for x in r]

Wyjaśnienie:

#accepts 2 arguments, matrix, and power to raise to
def power(matrix,exponent):
 #get the range object beforehand
 length=range(len(matrix))
 #if we are at 0, return the identity
 if exponent<1:
  #the Boolean statement works because Python supports multiplying ints by bools
  return [[x==y for x in length] for y in length]
 #otherwise, recur
 lower=power(matrix,exponent-1)
 #and return the product
 return [[sum([matrix[c][y]*lower[x][c] for c in length]) for y in length] for x in length]

JavaScript (ES6), 123 bajty

(n,a)=>[...Array(n)].map(_=>r=m(i=>m(j=>m(k=>s+=a[i][k]*r[k][j],s=0)&&s)),m=g=>a.map((_,n)=>g(n)),r=m(i=>m(j=>+!(i^j))))&&r

Używałem wersji 132-bajtowej, reduceale atak często mapowałem, że okazało się, że jest o 9 bajtów krótszy, aby napisać funkcję pomocnika, która zrobi to za mnie. Działa, tworząc macierz tożsamości i mnożąc ją przez adługi nczas. Istnieje wiele wyrażeń, które powracają 0lub 1dla i == jktórych wszystkie wydają się mieć długość 7 bajtów.

Python 3 , 147 bajtów

def f(a,n):
 r=range(len(a));r=[[i==j for j in r]for i in r]
 for i in range(n):r=[[sum(map(int.__mul__,x,y))for y in zip(*a)]for x in r]
 return r

Wypróbuj online!

R, 49 bajtów

f=function(m,n)`if`(n,m%*%f(m,n-1),diag(nrow(m)))

Funkcja rekurencyjna, która wymaga matriki i mocy, naby ją podnieść. Wywołania rekurencyjne %*%, które obliczają iloczyn skalarny. Wartość początkowa rekurencji jest macierzą tożsamości tego samego rozmiaru co m. Ponieważ m %*% m = m %*% m %*% Ito działa dobrze.

Python 2 , 131 bajtów

f=lambda M,n:n and[[sum(map(int.__mul__,r,c))for c in zip(*f(M,n-1))]for r in M]or[[0]*i+[1]+[0]*(len(M)+~i)for i in range(len(M))]

Wypróbuj online!