Trace de matrice généralisée

23

Inspiration.

Étant donné (par tout moyen):

  • Une fonction de boîte noire à deux arguments (ou un seul argument composé d'une liste à deux éléments) , (l'entrée et la sortie sont 1, 2, 3,…)f: ℤ+ × ℤ+ → ℤ+
  • Une matrice entière strictement positive avec au moins deux lignes et deux colonnes

retourne la trace de fonction de la matrice .

Qu'est-ce qu'une trace de fonction ?

Une trace matricielle normale est la somme de la diagonale principale (en haut à gauche à en bas à droite) d'une matrice:

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

Mais au lieu de résumer, nous voulons appliquer le flong de la diagonale:

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

Veuillez indiquer si vous utilisez de gauche à droite ou de droite à gauche.

La matrice donnée et toutes les valeurs intermédiaires seront des entiers strictement positifs dans le domaine entier de votre langue. La matrice peut être non carrée.

Exemples

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]]5ou7

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

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]]2ou4

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

Implémentation de référence.

Adam
la source
Quelle est la diagonale de [[2,2,2],[2,2,3],[2,3,3],[4,4,4]]?
totalement humain le
3
@totallyhuman:[2,2,3]
Emigna
1
Bon sang, je l' ai lu le titre comme « transe Généralisée Matrix » et a été très déçu lorsque la page chargée
tar

Réponses:

9

R , 40 30 octets

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

Essayez-le en ligne!

Vérifiez les cas de test.

Traverse la diagonale, donc de gauche à droite dans ce cas. Pour les opérateurs arithmétiques, vous pouvez utiliser des "+"barres obliques inverses autour des opérateurs ( +,*,-,%/%,^,%%)

Assez simple: Reduceest l'équivalent de R à a fold, et la diagonale d'une matrice est les éléments a_iji==j, c'est-à-dire où les indices rowet column sont les mêmes. diaga le comportement approprié pour les matrices non carrées.

Giuseppe
la source
8

Haskell , 39 octets

Merci @Laikoni de m'avoir aidé à corriger la solution précédemment invalide!

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

Associés à gauche, essayez-le en ligne! (remplacer foldl1par foldr1pour associatif à droite)

ბიმო
la source
que diriez-vous foldl1 f$zipWith(!!)m[0..]?
fier haskeller le
@proudhaskeller: C'est ce que d'autres ont déjà essayé, mais cela échoue sur les matrices non carrées ..
ბიმო
5

Mathematica , 16 octets

-1 octet merci à Martin Ender.

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

Essayez-le en ligne!

Solution alternative, 17 octets

Fold[g]@*Diagonal

Essayez-le en ligne!

totalement humain
la source
17 octets (les fonctions de boîte noire peuvent être assumées sous un nom donné)
M. Xcoder
Cette @*{}syntaxe n'a pas beaucoup de sens (vous vouliez probablement dire @*List), mais le fait qu'elle fonctionne de toute façon est plutôt cool. En fait, cela signifie que vous pouvez remplacer le {}par un 0et enregistrer un octet.
Martin Ender
@MartinEnder J'avais en fait d' Listabord, mais j'ai essayé {}juste pour le diable et j'ai été extrêmement surpris que cela fonctionne. C'est logique, mais comment ça 0marche? o0
totallyhuman
1
@totallyhuman De la même manière que {}. Vous utilisez actuellement {}une fonction (ou en fait une "tête" en utilisant la terminologie Mathematica). Si vous utilisiez un générique flà-bas, vous obtiendriez f[1,2,3](si c'est la diagonale). Mais avec {}vous obtenez {}[1,2,3]. C'est une expression complètement dénuée de sens, mais les têtes peuvent être des expressions arbitraires elles-mêmes, et si Mathematica ne sait pas quoi en faire, il les laisse telles quelles. La plupart des fonctions de manipulation de liste de Mathematica fonctionnent réellement avec des expressions avec une tête arbitraire et dans le cas de Fold, la tête est simplement ignorée. [à confirmer]
Martin Ender
Vous pouvez donc utiliser 0comme tête à la place, ce qui donne 0[1,2,3]ce qui n'a toujours pas de sens, mais fonctionne tout de même.
Martin Ender
4

Octave , 61 57 53 octets

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

Essayez-le en ligne!

Définit une fonction gqui prend un descripteur de fonction fet une matrice m. À la première itération, m(1)renvoie l'élément de matrice en haut à gauche; après cela, il revient juste m.

Sanchises
la source
53 octets
Giuseppe
@ Giuseppe C'est ce que j'ai fait avec ma version initiale de 61 octets. Bien sûr, j'aurais dû combiner les points forts de ma version 57 et 61 octets, ce qui donne en effet une réponse de 53 octets. Merci de m'avoir fait revoir ça!
Sanchises
3

Nettoyer , 56 octets

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

Essayez-le en ligne!Se plie de droite à gauche.

[t\\[_:t]<-r]est le même que map tl r, mais n'a pas besoin import StdEnv.

Laikoni
la source
Évitement très élégant deStdEnv
Οurous
3

Haskell , 47 45 42 octets

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

Essayez-le en ligne! Définit une fonction(%) qui prend une fonction et une matrice comme liste de listes en entrée.

La fonction se plie de droite à gauche:

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

Edit: -2 octets grâce à BMO et -3 octets grâce à Zgarb !

Laikoni
la source
1
43 octets en utilisant $et en simplifiant le conditionnel avec *>.
Zgarb
@Zgarb Belle idée à utiliser *>!
Laikoni
3

APL (Dyalog Unicode) , 7 octets ( SBCS d'Adám )

⎕/1 1⍉⎕

Essayez-le en ligne!

-3 grâce à une suggestion de convertir cela en un programme complet par Adám .

De droite à gauche.

Erik le Outgolfer
la source
Pas besoin d'utiliser le SBCS d'Adám ici: vous pouvez simplement utiliser Dyalog Classic.
Zacharý
@ Zacharý Le fait est que je réponds en Dyalog Unicode, Classic devient obsolète au fil du temps.
Erik the Outgolfer
Pas la page de codes bien que la page de codes va continuer à vivre
Zacharý
@ Zacharý Eh bien, soyons plutôt cohérents. : P
Erik the Outgolfer
2

Python 2 , 61 octets

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

Essayez-le en ligne!

Cela fonctionne de gauche à droite.

Barre
la source
@AsoneTuhid cela peut être de toute façon, consultez les exemples (x+y)⁄2etx+2y
Rod
Bon, j'ai mal lu, désolé
Asone Tuhid
2

JavaScript (ES6), 58 56 octets

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

Se plie de gauche à droite. Edit: enregistré 2 octets en utilisant le fait que le tableau est strictement positif. Solution alternative, également 56 octets:

(f,a,g=r=>(e=a[++i]&&a[i][i])?g(f(r,e)):r)=>g(a[i=0][0])
Neil
la source
Il ne semble pas que vous avez besoin de la 1/et vous pouvez enregistrer 2 autres octets en déplaçant des choses autour de : f=>a=>(h=r=>(e=a[++i]&&a[i][i])?h(f(r,e)):r)(a[i=0][0]). TIO
Shaggy
@Shaggy Oh, c'est strictement positif, je n'avais pas vu ça.
Neil
Apparently we can assume that black-box functions are assigned to a predefined variable so you could save 2 bytes if you want to take advantage of that.
Shaggy
@Shaggy Actually I think it would save 4 bytes (2x f,) off the first version?
Neil
You're right; sorry, forgot to count the f, when calling g again.
Shaggy
2

JavaScript, 46 bytes

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

Thanks to @Shaggy, use bitwise or save one byte. That's magic.

tsh
la source
This doesn't seem to work if the matrix has more rows than columns.
Shaggy
@Shaggy so sad, 47 bytes now...
tsh
Yeah, that's what I had originally, too. Was just about to edit the fix into my solution but you beat me too it :( I think you can get one byte back, though, by using bitwise OR, though.
Shaggy
@Shaggy so magic
tsh
Forgot to mention: Apparently we can assume that black-box functions are assigned to a predefined variable so you could save 3 bytes if you wanted to take advantage of that.
Shaggy
2

Java 8, 88 81 70 bytes

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

Folds [[1,2,3],[4,5,6],[7,8,9]] to f(f(1,5),9).

-7 bytes indirectly thanks to @KamilDrakari by using a similar trick as he did in his C# answer: instead of having a maximum boundary for the loop based on the rows/columns, simply try-catch the ArrayIndexOutOfBoundsException.
-11 bytes replacing catch(Exception e) with finally.

Try it online.

Old 88 bytes answer:

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;}

Try it online.

Explanation:

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

Black box input format:

Assumes a named function int f(int x,int y) is present, which is allowed according to this meta answer.

I have an abstract class Test containing the default function f(x,y), as well as the lambda above:

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;}
  ;
}

For the test cases, I overwrite this function f. For example, the first test case is called like this:

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
la source
2

Attache, 14 bytes

Fold#/Diagonal

Try it online! Set to f and call as f[function, array].

Explanation

This is a fork of two functions: Fold and /Diagonal. This, for arguments f and a, is equivalent to:

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

/, when applied monadically to a function, returns a function that is applied to its last argument. So, this is equivalent to:

Fold[f, Diagonal[a]]

This folds the function f over the main diagonal of a.

Conor O'Brien
la source
A home-brewed language which is readable‽
Adám
@Adám ;D yes indeed!
Conor O'Brien
2

AWK, 77 bytes

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}

Try it online!

I was curious if AWK could do functional programming at all. I think this counts.

The "Matrix" is defined as a standard associative array, with extra fields M[1]=#rows and M[2]=#columns. The function name is passed in as a string which is evaluated via the @F(...) syntax. Evaluation is performed left to right. The r parameter is a placeholder to prevent overwriting an existing r variable and to avoid the need to reinitialize for each call. Typically extra space is added to designate such placeholders in AWK, but this is code golf, so every byte counts. :)

The TIO link implements all the test cases.

Robert Benson
la source
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
la source
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
ბიმო
la source
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
la source
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
la source
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
la source
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
la source
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
la source
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
la source
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
la source
0

Clojure, 30 bytes

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

Reduces "from the left".

NikoNyrh
la source