Uogólniony ślad macierzy

23

Inspiracja.

Biorąc pod uwagę (w jakikolwiek sposób):

  • Dwu-argument (lub pojedyncza argumentu składającego się z listy dwuelementowej) funkcja czarna skrzynka , (wejście i wyjście są 1, 2, 3, ...)f: ℤ+ × ℤ+ → ℤ+
  • Ściśle dodatnia macierz liczb całkowitych z co najmniej dwoma wierszami i dwiema kolumnami

zwraca ślad funkcji macierzy .

Co to jest ślad funkcji ?

Normalny ślad macierzy jest sumą głównej przekątnej (od lewej górnej do prawej dolnej) macierzy:

[[1,2,3],[4,5,6],[7,8,9]][1,5,9]1+5+915

Ale zamiast sumowania, chcemy zastosować fwzdłuż przekątnej:

[[1,2,3],[4,5,6],[7,8,9]][1,5,9]f(f(1,5),9)lubf(1,f(5,9))

Podaj, czy używasz od lewej do prawej, czy od prawej do lewej.

Podana macierz i wszystkie wartości pośrednie będą ściśle dodatnimi liczbami całkowitymi w domenie liczb całkowitych twojego języka. Matryca może być niekwadratowa.

Przykłady

f(x,y) = xy, [[1,2,3],[4,5,6],[7,8,9]]1×5×945

f(x,y) = xy, [[1,2,3],[4,5,6],[7,8,9]]→ →1591

f(x,y) = x-y, [[4,5,6],[1,2,3]]4-22

f(x,y) = (x+y)⁄2, [[2,3,4],[5,6,7],[8,9,10]]5lub7

f(x,y) = x+2y, [[1,2,3],[4,5,6],[7,8,9]]47lub29

f(x,y) = max(x,y), [[1,2,3],[4,5,6],[7,8,9]]max(1,5,9)9

f(x,y) = 2x, [[1,2,3],[4,5,6],[7,8,9]]2lub4

f(x,y) = lcm(x,y), [[2,2,2],[2,2,3],[2,3,3],[4,4,4]]lcm(2,2,3)6

Realizacja referencyjna.

Adám
źródło
Jaka jest przekątna [[2,2,2],[2,2,3],[2,3,3],[4,4,4]]?
totalnie ludzki
3
@totallyhuman:[2,2,3]
Emigna
1
Cholera, przeczytałem ten tytuł jako „Uogólniony trans Matrix” i byłem bardzo rozczarowany, gdy strona się załadowała
tar

Odpowiedzi:

9

R , 40 30 bajtów

function(m,F)Reduce(F,diag(m))

Wypróbuj online!

Sprawdź przypadki testowe.

Przechodzi po przekątnej, więc w tym przypadku od lewej do prawej. W przypadku operatorów arytmetycznych możesz używać "+"lub wstawiać wokół operatorów ( +,*,-,%/%,^,%%)

Całkiem proste: ReduceR jest równoważne a fold, a przekątna macierzy to te elementy, w a_ijktórych i==j, tj. Gdzie wskaźniki rowi column są takie same. diagma odpowiednie zachowanie dla macierzy niekwadratowych.

Giuseppe
źródło
8

Haskell , 39 bajtów

Dzięki @Laikoni za pomoc w naprawieniu wcześniej nieprawidłowego rozwiązania!

f!m=foldl1 f[h|h:_<-zipWith drop[0..]m]

Współpracownicy po lewej, spróbuj online! (zamień foldl1na foldr1na prawo-asocjacyjne)

ბიმო
źródło
jak o foldl1 f$zipWith(!!)m[0..]?
dumny haskeller
@proudhaskeller: Tak próbowali już inni, ale to się nie udaje w przypadku macierzy
niekwadratowych
5

Mathematica , 16 bajtów

-1 bajt dzięki Martin Ender.

#~Tr~Fold[g]@*0&

Wypróbuj online!

Alternatywne rozwiązanie, 17 bajtów

Fold[g]@*Diagonal

Wypróbuj online!

całkowicie ludzki
źródło
17 bajtów (pod jedną nazwą można założyć funkcje czarnej skrzynki)
Pan Xcoder
Ta @*{}składnia nie ma większego sensu (prawdopodobnie miałeś na myśli @*List), ale fakt, że i tak działa, jest całkiem fajny. W rzeczywistości oznacza to, że możesz zamienić na {}a 0i zapisać bajt.
Martin Ender
@MartinEnder Tak naprawdę miałem Listpierwszy, ale próbowałem {}tylko do cholery i byłem bardzo zaskoczony, że zadziałało. Ma sens, ale jak 0działa? o0
całkowicie ludzki
1
@totallyhuman Taki sam sposób jak {}. Obecnie używasz {}jako funkcji (a właściwie jako „głowy” używając terminologii Mathematica). Jeśli użyjesz ftam generycznego , dostaniesz f[1,2,3](jeśli to przekątna). Ale z {}tobą dostaniesz {}[1,2,3]. To całkowicie pozbawione znaczenia wyrażenie, ale głowy mogą same być dowolnymi wyrażeniami, a jeśli Mathematica nie wie, co z nimi zrobić, pozostawia je takimi, jakie są. Większość funkcji manipulowania listami Mathematiki faktycznie działa z wyrażeniami z dowolną głową, aw przypadku Foldgłowy jest ona po prostu ignorowana. [do potwierdzenia]
Martin Ender
Możesz więc użyć 0zamiast głowy, co daje 0[1,2,3]to, co jest nadal bez znaczenia, ale działa tak samo.
Martin Ender
4

Oktawa , 61 57 53 bajtów

function m=g(f,m)for i=diag(m)'(2:end)m=f(m(1),i);end

Wypróbuj online!

Definiuje funkcję, gktóra przyjmuje uchwyt funkcji fi macierz m. Przy pierwszej iteracji m(1)zwraca lewy górny element macierzy; potem po prostu wraca m.

Sanchises
źródło
53 bajty
Giuseppe
@Giuseppe Tak właśnie zrobiłem z moją początkową 61-bajtową wersją. Oczywiście powinienem był połączyć mocne strony mojej 57- i 61-bajtowej wersji, która rzeczywiście daje 53-bajtową odpowiedź. Dzięki za ponowne spojrzenie na mnie!
Sanchises
3

Czysty , 56 bajtów

t[[h:_]]f=h
t[[h]:_]f=h
t[[h:_]:r]f=f h(t[t\\[_:t]<-r]f)

Wypróbuj online! Składa się od prawej do lewej.

[t\\[_:t]<-r]jest taki sam jak map tl r, ale nie potrzebuje import StdEnv.

Laikoni
źródło
Bardzo eleganckie unikanieStdEnv
Οurous
3

Haskell , 47 45 42 bajtów

f%((h:t):r)|[]<-t*>r=h|x<-tail<$>r=f h$f%x

Wypróbuj online! Definiuje funkcję, (%)która przyjmuje funkcję i macierz jako listę list jako dane wejściowe.

Funkcja składa się od prawej do lewej:

f % [[1,2,3], -> f 1 ( f % [[5,6],   -> f 1 ( f 5 ( f % [[9]] ) ) -> f 1 ( f 5 ( f 9 ) ) )
     [4,5,6],               [8,9]] )
     [7,8,9]]

f % ((h:t):r)              -- (h:t) is the first row and r the remaining rows
 | [] <- t *> r = h         -- a shorter way of checking wether t==[] or r==[]
 | x<-tail<$>r = f h $ f%x -- apply f to h and the result of recursively calling (%) on
                           -- the remaining matrix with the first column removed

Edycja: -2 bajty dzięki BMO i -3 bajty dzięki Zgarb !

Laikoni
źródło
1
43 bajty za pomocą $i upraszczając warunkowe za pomocą *>.
Zgarb
@Zgarb Fajny pomysł *>!
Laikoni
3

APL (Dyalog Unicode) , 7 bajtów ( Adám's SBCS )

⎕/1 1⍉⎕

Wypróbuj online!

-3 dzięki sugestii, aby przekonwertować to na pełny program Adám .

Od prawej do lewej.

Erik the Outgolfer
źródło
Nie musisz tutaj używać SBCS firmy Adám: wystarczy użyć Dyalog Classic.
Zacharý
@ Zacharý Chodzi o to, że odpowiadam w Dyalog Unicode, Classic z czasem staje się przestarzały.
Erik the Outgolfer,
Ale nie strona kodowa, ale strona kodowa będzie dostępna
Zacharý
@ Zacharý Cóż, bądźmy raczej konsekwentni. : P
Erik the Outgolfer
2

Haskell , 44 bajty

f#m=foldl1 f$zipWith(!!)m[0..length(m!!0)-1]

Wypróbuj online!

całkowicie ludzki
źródło
2

Python 2 , 61 bajtów

lambda f,m:reduce(f,[l[i]for i,l in enumerate(m)if len(l)>i])

Wypróbuj online!

Działa od lewej do prawej.

Pręt
źródło
@AsoneTuhid może być dowolny sposób, sprawdź (x+y)⁄2i x+2yprzykłady
Rod
Tak, źle odczytałem, przepraszam
Asone Tuhid
2

JavaScript (ES6), 58 56 bajtów

g=(f,a,r=a[i=0][0],e=a[++i]&&a[i][i])=>e?g(f,a,f(r,e)):r

Składa się od lewej do prawej. Edycja: Zapisano 2 bajty, wykorzystując fakt, że tablica jest ściśle dodatnia. Alternatywne rozwiązanie, również 56 bajtów:

(f,a,g=r=>(e=a[++i]&&a[i][i])?g(f(r,e)):r)=>g(a[i=0][0])
Neil
źródło
To nie wygląda tak, jak potrzebne 1/i można zaoszczędzić kolejne 2 bajty przesuwając niektóre rzeczy wokół: f=>a=>(h=r=>(e=a[++i]&&a[i][i])?h(f(r,e)):r)(a[i=0][0]). TIO
Kudłaty
@Shaggy Oh, to jest absolutnie pozytywne, nie widziałem tego.
Neil
Najwyraźniej możemy założyć, że funkcje czarnej skrzynki są przypisane do predefiniowanej zmiennej, więc możesz zapisać 2 bajty, jeśli chcesz z tego skorzystać.
Kudłaty
@Shaggy Właściwie myślę, że zaoszczędziłoby 4 bajty (2x f,) na pierwszej wersji?
Neil
Masz rację; przepraszam, zapomniałem policzyć, f,kiedy dzwonię gponownie.
Kudłaty
2

JavaScript, 46 bajtów

f=>a=>a.reduce((p,l,i)=>l[i]?f(p[0]|p,l[i]):p)

Dzięki @Shaggy używaj bitów lub oszczędzaj jeden bajt. To magia.

tsh
źródło
Nie wydaje się to działać, jeśli macierz ma więcej wierszy niż kolumn.
Kudłaty
@ Shaggy so sad, 47 bytes now ...
tsh
Tak, to też miałem pierwotnie. Właśnie miałem edytować poprawkę w moim rozwiązaniu, ale mnie też pobiłeś :( Myślę jednak, że możesz odzyskać jeden bajt, używając bitowej LUB, chociaż.
Shaggy
@ Shaggy so magic
tsh
Zapomniałem wspomnieć: Najwyraźniej możemy założyć, że funkcje czarnej skrzynki są przypisane do predefiniowanej zmiennej, więc możesz zapisać 3 bajty, jeśli chcesz z tego skorzystać.
Kudłaty
2

Java 8, 88 81 70 bajtów

m->{int r=m[0][0],i=1;try{for(;;)r=f(r,m[i][i++]);}finally{return r;}}

Składa się [[1,2,3],[4,5,6],[7,8,9]]na f(f(1,5),9).

-7 bajtów pośrednio dzięki @KamilDrakari przy użyciu podobnej sztuczki jak w odpowiedzi C # : zamiast mieć maksymalną granicę dla pętli opartą na wierszach / kolumnach, po prostu spróbuj złapać ArrayIndexOutOfBoundsException.
-11 bajtów wymiana catch(Exception e)z finally.

Wypróbuj online.

Stara 88 bajtów odpowiedź:

m->{int r=m[0][0],i=1;for(;i<Math.min(m.length,m[0].length);)r=f(r,m[i][i++]);return r;}

Wypróbuj online.

Wyjaśnienie:

m->{                   // Method with integer-matrix parameter and integer return-type
  int r=m[0][0],       //  Start the result at the integer of position 0,0 (0-indexed)
      i=1;             //  Start the index at 1 (0-indexed)
  try{for(;;)          //  Loop indefinitely
    r=f(r,m[i][i++]);} //   Call f with the result + next diagonal cell as arguments
                       //   (and increase `i` by 1 with `i++` afterwards)
  finally{             //  If an ArrayIndexOutOfBoundsException occurred we're done,
   return r;}}         //   in which case we return the result-integer

Format wejściowy czarnej skrzynki:

Zakłada, że ​​nazwana funkcja int f(int x,int y)jest obecna, co jest dozwolone zgodnie z tą meta odpowiedzią .

Mam klasę abstrakcyjną Testzawierającą funkcję domyślną f(x,y), a także powyższą lambda:

abstract class Test{
  int f(int x,int y){
    return x+y;
  }

  public java.util.function.Function<int[][],Integer>c=
    m->{int r=m[0][0],i=1;for(;i<Math.min(m.length,m[0].length);)r=f(r,m[i][i++]);return r;}
  ;
}

W przypadkach testowych nadpisuję tę funkcję f. Na przykład pierwszy przypadek testowy nazywa się tak:

System.out.println(new Test(){
  @Override
  int f(int x,int y){
    return x*y;
  }
}.c.apply(new int[][]{
  new int[]{1,2,3},
  new int[]{4,5,6},
  new int[]{7,8,9}
}));
Kevin Cruijssen
źródło
2

Attache , 14 bajtów

Fold#/Diagonal

Wypróbuj online! Ustaw fi dzwoń jako f[function, array].

Wyjaśnienie

Jest to rozwidlenie dwóch funkcji: Foldi /Diagonal. Dla argumentów fi ajest to równoważne z:

Fold[f, (/Diagonal)[f, a]]

/, zastosowane monadycznie do funkcji, zwraca funkcję zastosowaną do jej ostatniego argumentu. Odpowiada to:

Fold[f, Diagonal[a]]

To składa funkcję fna głównej przekątnej a.

Conor O'Brien
źródło
Domowy język, który jest czytelny‽
Adám
@ Adám; D rzeczywiście tak!
Conor O'Brien
2

AWK , 77 bajtów

func z(F,M,r){for(e=1;e<M[1]&&e<M[2];)r=@F(r==""?M[1,1]:r,M[++e,e])
return r}

Wypróbuj online!

Byłem ciekawy czy AWK could do functional programming at all. I think this counts.

„Matryca” jest zdefiniowana jako standardowa tablica asocjacyjna z dodatkowymi polami M[1]=#rowsi M[2]=#columns. Nazwa funkcji jest przekazywana jako ciąg znaków, który jest analizowany przez @F(...)składnię. Ocena przeprowadzana jest od lewej do prawej. Ten rparametr jest symbolem zastępczym, aby zapobiec zastąpieniu istniejącej rzmiennej i uniknąć konieczności ponownej inicjalizacji każdego połączenia. Zazwyczaj dodaje się dodatkowe miejsce do oznaczenia takich symboli zastępczych AWK, ale jest to kod golfowy, więc liczy się każdy bajt. :)

The TIO link implements all the test cases.

Robert Benson
źródło
2

05AB1E, 15 10 bytes

Folds from right-to-left
Saved 5 bytes using a new built-in as suggested by Kevin Cruijssen

Å\`[.g#I.V

Explanation

Works the same as the old version, except that Å\ is a new built-in for pushing the main diagonal.

Try it online! or as a Test Suite

Old Version

¬g£vyNè}[.g#I.V

Try it online! or as a Test suite

Explanation

¬                 # get the head of the input (first row)
 g                # get its length (number of columns)
  £               # take that many rows from input
   v              # for each row_index, row (N,y) do:
    y             # push the row
     Nè           # get the nth element of the row
       }          # end loop
        [.g#      # loop until one value remain on the stack
            I.V   # run the input function
Emigna
źródło
1
¬g£vyNè}[ can be Å\`[ now, saving 5 bytes.
Kevin Cruijssen
1

Husk, 7 bytes

Thanks @Zgarb for fixing my submission!

Ḟ₁§z!Tŀ

Associates to the left, Try it online! (for a right-associative version simply replace by F)

Explanation

Unfortunately there's no easy way to get the diagonal of a matrix, so most the bytes are for that:

Ḟ₁§z!Tŀ  -- function ₁ is the function and matrix A implicit, example: 
  §      -- fork A
     T   -- | transpose A: [[1,4,7],[2,5,8],[3,6,9]]
      ŀ  -- | enumerate A: [1,2,3]
   z!    -- and zipWith index: [1,5,9]
Ḟ₁       -- right fold function
ბიმო
źródło
Huh, built-in for anti-diagonals, but not for diagonals‽
Adám
2
@Adám I assume that's because you can compute antidiagonals of infinite matrices but not diagonals.
Martin Ender
1

SNOBOL4 (CSNOBOL4), 86 bytes

T	I =1
	T =M<1,1>
I	I =I + 1
	T =EVAL(F '(T,M<I,I>)')	:S(I)F(RETURN)
	DEFINE('T(M,F)')

Try it online!

Defines a function T (for TRACE) that takes an ARRAY and a string F that's the name of a function. Folds left-to-right.

Using indirect reference ($) doesn't work with functions. So using EVAL and passing a string to the name seems to be the only way to get a black-box function in SNOBOL.

Also, it's quite painful to define arrays; however, because invalid array references cause FAILURE, this works for non-square arrays -- if I is out-of-bounds in either dimension, the F(RETURN) forces the function to return.

Edit:

Possibly, based on this meta post, I may assume that the black-box function F is defined under the name F, which would drop this to 75 bytes (remove use of EVAL and ,F in the function definition). However, I prefer this version since it's closer to passing a reference to a function.

Giuseppe
źródło
1

C, 76 bytes

i,t;f(g,A,n,m)int*A,(*g)();{for(t=*A,i=m+1;--n*--m;t=g(t,*A))A+=i;return t;}

Left-to-right.

Try it online!

Steadybox
źródło
1

tinylisp, 79 bytes

(load library
(d D(q((M)(i(h M)(c(h(h M))(D(map t(t M))))(
(q((F M)(foldl F(D M

The last line is an unnamed lambda function that takes a function and matrix and returns the matrix trace. The trace is left-associative (i.e. f(f(1,5),9)). Try it online!

Ungolfed

We define a helper function to compute the diagonal; then generalized-trace is merely a small wrapper around the library function foldl.

(load library)

(def diagonal
 (lambda (matrix)
  (if (head matrix)
   (cons
    (head (head matrix))
    (diagonal (map tail (tail matrix))))
   nil)))

(def generalized-trace
 (lambda (func matrix)
  (foldl func (diagonal matrix))))

When computing the diagonal recursively, we check whether (head matrix) is truthy. If the matrix is out of rows, it will be the empty list (nil), and head of nil is nil--falsey. Or, if the matrix is out of columns, its first row (head) will be the empty list (nil)--falsey. Otherwise, there will be a nonempty first row, which is truthy.

So, if the first row doesn't exist or is empty, we return nil. Otherwise, if there is a nonempty first row, we take (head (head matrix))--the first element of the first row--and cons (prepend) it to the result of the recursive call. The argument to the recursive call is (map tail (tail matrix))--that is, take all rows but the first, and take all but the first element of each row.

DLosc
źródło
1

C# (Visual C# Compiler), 72 69 60 bytes

m=>{try{for(int i=1;;m[0][0]=f(m[0][0],m[i][i++]));}catch{}}

Try it online!

try/catch allows the diagonal to be correctly reached by simply going along it and terminating when out of bounds.

3 bytes saved because, as pointed out by Kevin Cruijssen, black-box functions can be assumed to exist under a specific name.

9 bytes saved by returning via modifying an argument.

Thus, the function is called by storing the desired function under the name f, calling trace(matrix), and the result is stored in matrix[0][0].

Alternatively, if you really like verbosity,

C# (Visual C# Compiler), 97 + 13 = 110 78 69 bytes

(int[][]m)=>{try{for(int i=1;;m[0][0]=f(m[0][0],m[i][i++]));}catch{}}

Try it online!

32 bytes saved by using a predefined function, because not taking the function as a parameter allowed removing the System import and the long Func generic type.

Kamil Drakari
źródło
Nice trick with the try-catch. I've been able to golf 7 bytes on my Java 8 answer (even though I have to use catch(Exception e) instead of catch. :) EDIT: Oh, been able to replace the catch(Exception e) with finally to save more bytes. Thanks again. +1 from me.
Kevin Cruijssen
@KevinCruijssen you may also be able to benefit from my newest improvement (though I don't remember for sure whether Java is amenable to modifying arguments)
Kamil Drakari
Thanks for letting me know. Although it is possible in Java, it means I'll have to change the finally into catch(Exception e), because I'm not returning inside the finally anymore. So m->{try{for(int i=1;;m[0][0]=f(m[0][0],m[i][i++]));}catch(Exception e){}} (73 bytes) is unfortunately longer for me in comparison to my current answer m->{int r=m[0][0],i=1;try{for(;;)r=f(r,m[i][i++]);}finally{return r;}} (70 bytes) But indeed a nice way to save bytes in your answer! :) Too bad I can only +1 your answer once.
Kevin Cruijssen
1

JavaScript, 61 57 56 52 50 44 42 bytes

Reduces left to right. Assumes the function is assigned to variable f, as per this meta post brought to my attention by Mr. Xcoder & totallyhuman. Can't say as I agree with it as it directly contradicts our existing consensus that we may not assume input is assigned to a pre-defined variable, but I'll take the few bytes saving for now.

a=>a.map((y,z)=>x=(n=y[z])?z?f(x,n):n:x)|x

Test Cases

g=
a=>a.map((y,z)=>x=(n=y[z])?z?f(x,n):n:x)|x
o.innerHTML=[[`f(x,y) = xy`,[[1,2,3],[4,5,6],[7,8,9]],(x,y)=>x*y,45],[`f(x,y) = x<sup>y</sup>`,[[1,2,3],[4,5,6],[7,8,9]],(x,y)=>x**y,1],[`f(x,y) = x-y`,[[4,5,6],[1,2,3]],(x,y)=>x-y,2],[`f(x,y) = <sup>(x+y)</sup>⁄<sub>2</sub>`,[[2,3,4],[5,6,7],[8,9,10]],(x,y)=>(x+y)/2,7],[`f(x,y) = x+2y`,[[1,2,3],[4,5,6],[7,8,9]],(x,y)=>x+2*y,29],[`f(x,y) = max(x,y)`,[[1,2,3],[4,5,6],[7,8,9]],(x,y)=>Math.max(x,y),9],[`f(x,y) = 2x`,[[1,2,3],[4,5,6],[7,8,9]],(x,y)=>2*x,4],[`f(x,y) = lcm(x,y)`,[[2,2,2],[2,2,3],[2,3,3],[4,4,4]],(x,y)=>-~[...Array(x*y).keys()].find(z=>!(++z%x|z%y)),6]].map(([a,b,c,d],e)=>`Test #${++e}:  ${a}\nMatrix:   ${JSON.stringify(b)}\nFunction: ${f=c}\nResult:   ${g(b)}\nExpected: ${d}`).join`\n\n`
<pre id=o></pre>

Shaggy
źródło
1

APL NARS, 20 bytes, 10 chars

{⍺⍺/1 1⍉⍵}

test:

  f←{⍺⍺/1 1⍉⍵}
  ⎕←q←3 3⍴⍳10    
1 2 3
4 5 6
7 8 9
  ×f q
45
  *f q
1
  {⍺+2×⍵}f q
47
  ⌈f q
9
  {2×⍺+0×⍵}f q
2
  -f ⊃(4 5 6)(1 2 3)
2
  {(⍺+⍵)÷2}f ⊃(2 3 4)(5 6 7)(8 9 10)
5
  ∧f ⊃(2 2 2)(2 2 3)(2 3 3)(4 4 4)
6
RosLuP
źródło
Good job. While I think you arrive to this on you own, it happens to be identical to Erik the Outgolfer's original solution.
Adám
0

Jelly, 5 bytes

Left-to-right.

ŒDḢç/

Try it online!

Disclaimer: I do not know if this an acceptable input method for black-box functions. This assumes that the function is implemented in the link above, and is thus "named" (that is, it's callable with) ç, but otherwise I have no way to assign it to ç. If anyone has more experience with Jelly + black box functions, I would appreciate thoughts. After spending some time in chat, we figured that using ç might indeed be valid.

Mr. Xcoder
źródło
0

Clojure, 30 bytes

#(reduce %2(map nth %(range)))

Reduces "from the left".

NikoNyrh
źródło