Repliez une matrice!

13

Étant donné une matrice, additionnez ses valeurs vers le haut / bas ou gauche / droite pour former un X, pliez-la et retournez la liste. Je décris ici l'algorithme:

Algorithme

Votre entrée sera une matrice carrée de taille impaire d'entiers dans la capacité numérique raisonnable de votre langue.

Prenons l'exemple de la matrice suivante:

1 2 3 2 1
0 3 2 3 0
4 2 5 6 3
7 4 7 9 4
0 6 7 2 5

Tout d'abord, ajoutez chaque nombre au nombre le plus proche qui se trouve sur la diagonale principale ou l'antidiagonale. Autrement dit, divisez la matrice en quatre sections le long de la diagonale principale et de l'antidiagonale, puis additionnez tous les nombres de chaque section vers le centre, comme suit:

1   2   3   2   1
    ↓   ↓   ↓    
0 → 3   2   3 ← 0
        ↓        
4 → 2 → 5 ← 6 ← 3
        ↑        
7 → 4   7   9 ← 4
    ↑   ↑   ↑    
0   6   7   2   5

Cette étape donne le résultat suivant:

1        1
  5    5
    39
  17  15
0        5

Ensuite, nous le plions en aplatissant le X et en entrelaçant les éléments avec le coin supérieur gauche en premier et le coin inférieur gauche en dernier. Cela donne le résultat suivant:

1, 0, 5, 17, 39, 5, 15, 1, 5

Vous pouvez imaginer cela comme étirer la diagonale principale et la faire tourner dans le sens antihoraire.

Ceci est le résultat final.

Défi

Implémentez cet algorithme. Des échappatoires standard s'appliquent. Tous les formats d'E / S raisonnables sont acceptables.

Cas de test

Input
Output

1 2 3 2 1
0 3 2 3 0
4 2 5 6 3
7 4 7 9 4
0 6 7 2 5

1, 0, 5, 17, 39, 5, 15, 1, 5

1 2 3 4 5
5 4 3 2 1
1 3 5 7 9
0 9 8 7 6
6 7 8 9 0

1, 6, 11, 16, 47, 7, 22, 5, 0

1 3 7 4 8 5 3
8 4 7 5 3 8 0
0 6 3 6 9 8 4
2 6 5 8 7 4 2
0 6 4 3 2 7 5
0 6 7 8 5 7 4
8 5 3 2 6 7 9

1, 8, 15, 11, 23, 20, 62, 32, 25, 13, 18, 3, 9
HyperNeutrino
la source
Pouvez-vous ajouter un cas de test matriciel "pas 5 × 5"?
2017 totalement humain à 11h01
1
@icrieverytim c'est
parti

Réponses:

7

JavaScript, 113 octets

s=>(l=s.length-1,a=[],s.map((v,y)=>v.map((n,x)=>a[q=2*[x,y,l-y].sort((u,v)=>u-v)[1]+(y>l/2),q-=q>l]=~~a[q]+n)),a)

tsh
la source
Umm .. pourquoi le ~~? Ils se neutralisent, il n'y a donc pas besoin d'eux.
Kevin Cruijssen
2
@KevinCruijssen ~~undefined==0, c'est donc plus golfeur que (a[q]||0).
Neil
@Neil Ah, je n'y avais pas pensé undefined. Lorsque j'ai copié le cas de test tsh utilisé, j'ai remarqué que cela fonctionnait sans ~~. Et comme il ~~xse -(-x)neutralise de la même façon, je me suis dit que cela avait été mis en place par accident. Merci pour la correction.
Kevin Cruijssen
5

Gelée , 25 23 21 octets

AṂ×ṠṚ
LHŒRṗ2Ç€ḅLĠịFS€

Essayez-le en ligne!

Version alternative, 19 octets

AṂ×ṠṚ
LHŒRṗ2Ç€ĠịFS€

Cela ne fonctionnait pas Ġauparavant car il se comportait incorrectement pour les tableaux imbriqués. La seule différence est que les paires [q, p] mentionnées dans Comment ça marche sont triées lexicographiquement au lieu de les mapper à p + nq avant le tri.

Essayez-le en ligne!

Contexte

Nous commençons par remplacer ses éléments par des coordonnées, en augmentant vers la gauche et vers le bas et en plaçant (0, 0) au centre de la matrice.

Pour une matrice M 7x7 , on obtient les coordonnées suivantes.

(-3,-3) (-3,-2) (-3,-1) (-3, 0) (-3, 1) (-3, 2) (-3, 3)
(-2,-3) (-2,-2) (-2,-1) (-2, 0) (-2, 1) (-2, 2) (-2, 3)
(-1,-3) (-1,-2) (-1,-1) (-1, 0) (-1, 1) (-1, 2) (-1, 3)
( 0,-3) ( 0,-2) ( 0,-1) ( 0, 0) ( 0, 1) ( 0, 2) ( 0, 3)
( 1,-3) ( 1,-2) ( 1,-1) ( 1, 0) ( 1, 1) ( 1, 2) ( 1, 3)
( 2,-3) ( 2,-2) ( 2,-1) ( 2, 0) ( 2, 1) ( 2, 2) ( 2, 3)
( 3,-3) ( 3,-2) ( 3,-1) ( 3, 0) ( 3, 1) ( 3, 2) ( 3, 3)

Nous calculons maintenant la valeur absolue minimale de chaque paire de coordonnées et multiplions les signes des deux coordonnées par elle, en mappant (i, j) à (signe (i) m, signe (j) m) , où m = min (| i | , | j |) .

(-3,-3) (-2,-2) (-1,-1) ( 0, 0) (-1, 1) (-2, 2) (-3, 3)
(-2,-2) (-2,-2) (-1,-1) ( 0, 0) (-1, 1) (-2, 2) (-2, 2)
(-1,-1) (-1,-1) (-1,-1) ( 0, 0) (-1, 1) (-1, 1) (-1, 1)
( 0, 0) ( 0, 0) ( 0, 0) ( 0, 0) ( 0, 0) ( 0, 0) ( 0, 0)
( 1,-1) ( 1,-1) ( 1,-1) ( 0, 0) ( 1, 1) ( 1, 1) ( 1, 1)
( 2,-2) ( 2,-2) ( 1,-1) ( 0, 0) ( 1, 1) ( 2, 2) ( 2, 2)
( 3,-3) ( 2,-2) ( 1,-1) ( 0, 0) ( 1, 1) ( 2, 2) ( 3, 3)

Les éléments de matrice qui correspondent à la même paire doivent être additionnés. Pour déterminer l'ordre des sommes, nous localiser chaque paire (p, q) de p + nq , où n est le nombre de lignes / colonnes de M .

-24 -16  -8   0   6  12  18
-16 -16  -8   0   6  12  12
 -8  -8  -8   0   6   6   6
  0   0   0   0   0   0   0
 -6  -6  -6   0   8   8   8
-12 -12  -6   0   8  16  16
-18 -12  -6   0   8  16  24

L'ordre des sommes correspond à l'ordre des entiers qui correspondent à ses sommets.

Comment ça fonctionne

LHŒRṗ2Ç€ḅLĠịFS€  Main link. Argument: M (matrix)

L                Compute n, the length (number of rows) of M.
 H               Halve it.
  ŒR             Symmetric range; map t to [-int(t), ..., 0, int(t)].
    ṗ2           Compute the second Cartesian power, yielding all pairs [i, j]
                 with -t ≤ i, j ≤ t.
      ǀ         Map the helper link over the resulting array of pairs.
         L       Yield n.
        ḅ        Unbase; map each pair [q, p] to (p + nq).
          Ġ      Group the indices of the resulting array of n² integers by their
                 corresponding values, ordering the groups by the values.
            F    Flatten M.
           ị     Index into the serialized matrix.
             S€  Compute the sum of each group.


AṂ×ṠṚ            Helper link. Argument: [i, j] (index pair)

A                Absolute value; yield [|i|, |j|].
 Ṃ               Minimum; yield m := min(|i|, |j|).
   Ṡ             Sign; yield [sign(i), sign(j)].
  ×              Multiply; yield [p, q] := [sign(i)m, sign(j)m].
    Ṛ            Reverse; yield [q, p].
Dennis
la source
5
c'est génial.
Uriel
5

Python, 159 158 octets

def f(m):l=len(m)-1;r=range(1,l);return m[0][::l]+f([[sum(m[x][1%y*y:(y>l-2)-~y])+m[0][y]*(x<2)+m[l][y]*(x>l-2)for y in r]for x in r])+m[l][::l]if l else m[0]

Essayez-le en ligne!

KSab
la source
1
y+1+(y>l-2)peut être (y>l-2)-~y.
Jonathan Frech
2

APL (Dyalog) , 60 octets *

En collaboration avec mon collègue Marshall .

Préfixe anonyme lambda. Prend la matrice comme argument et renvoie un vecteur. Suppose que ⎕IO ( I ndex O rigin) est égal à zéro, ce qui est par défaut sur de nombreux systèmes.

{(,⍉{+/,(s×-×⍺)↓⍵×i∊¨⍨s←⌊⊃r÷2}⌺r⊢⍵)/⍨,(⊢∨⌽)=/¨i←⍳r←⍴⍵}

Essayez-le en ligne!

{} Lambda anonyme; est le bon argument (comme la lettre la plus à droite de l'alphabet grec):

⍴⍵ forme de l'argument (liste de deux éléments identiques)

r← stocker comme r(comme dans r ho)

 tous les ɩ ndices d'un tableau de cette taille, c'est (0 0)-à- dire (0 1)

i← stocker dans i(comme dans i ota)

=/¨ Booléen où les coordonnées sont égales (c'est-à-dire la diagonale)

() Appliquer cette fonction de préfixe tacite anonyme:

   inverser l'argument

  ⊢∨ OU qu'avec l'argument non modifié

, ravel (redresser en liste simple)

 Nous avons maintenant un masque booléen pour les diagonales.

()/⍨ Utilisez-le pour filtrer les éléments suivants:

  ⊢⍵ produire (à séparer de r) l'argument

  {}⌺r Appelez l'infixe anonyme lambda suivant sur chaque élément, avec le r-voisinage (complété avec des zéros si nécessaire) comme argument de droite ( ), et une liste de deux éléments de lignes, colonnes (négatif pour le bas / droite, zéro pour aucun) comme argument de gauche ( ):

   r÷2 diviser ravec deux

    choisissez le premier élément (ils sont identiques)

    appuyez sur le champignon

   s← stocker comme s(pour s hape)

   i∊⍨¨ pour chaque élément de i, Boolean si en sest membre

   ⍵× multiplier le quartier avec celui-ci

   ()↓ Supprimez le nombre de lignes et de colonnes suivant (négatif pour le bas / la droite):

    ×⍺ signum de l'argument de gauche (ie la direction des rembourrages)

    - nier

     se multiplier savec

   , ravel (redresser dans la liste)

   +/ somme (plus réduction)

Nous avons maintenant une matrice complète de sommes, mais nous devons filtrer toutes les valeurs lues dans les colonnes.

   transposer

  , ravel (redresser en liste simple)


* En comptant comme ⎕U233A . Essayez-le en ligne!

Adam
la source