Trouvez la sous-matrice avec la plus petite moyenne, 2.0

15

On vous donne une matrice n-par-m d'entiers, où n, m> 3 . Votre tâche consiste à trouver la sous-matrice 3 x 3 qui a la moyenne la plus faible et à sortir cette valeur.

Règles et clarifications:

  • Les entiers seront non négatifs
  • Format d'entrée et de sortie en option
  • La sortie doit être précise jusqu'à au moins 2 décimales (si elle n'est pas entière)
  • Les sous-matrices peuvent être constituées de colonnes et de lignes arbitraires

Cas de test:

1   0   4   0   1   0
1   0   4   0   1   0
4   3   4   3   4   3
1   0   4   0   1   0

Minimum mean: 0   (We have chosen columns 2,4,6 and rows 1,2,4 (1-indexed)
-----------------------------
4    8    9    7
5   10    1    5
8    5    2    4
8    3    5   10
6    6    3    4

Minimum mean: 4.2222
-----------------------------
1   0   0   0   0
0   2   0   0   0
0   0   3   0   0
0   0   0   4   0
0   0   0   0   5

Minimum mean: 0.11111
-----------------------------
371   565   361   625   879   504   113   104
943   544   157   799   726   832   228   405
743   114   171   506   943   181   823   454
503   410   333   735   554   227   423   662
629   439   191   707    52   751   506   924

Minimum mean: 309.56
Stewie Griffin
la source
Qu'est-ce qui la différencie de la première version de ce défi?
Kritixi Lithos
2
@KritixiLithos Il utilise la définition plus générale de "sous-matrice" où une sous-matrice est n'importe quelle matrice que vous pouvez obtenir en supprimant un nombre quelconque de lignes et de colonnes de l'original (de sorte que les lignes / colonnes restantes ne doivent pas être adjacentes).
Martin Ender

Réponses:

9

Mathematica, 77 50 octets

±x_:=x~Subsets~{3}
Min[Mean/@Mean/@±#&/@±#]&

est l'opérateur de transposition de Mathematica (et est rendu en exposant T dans Mathematica).

Cette réponse définit d'abord un opérateur d'assistance ±qui renvoie tous les sous-ensembles à 3 éléments d'une liste, puis évalue une fonction sans nom qui utilise cet opérateur pour résoudre le problème.

Cela se fait en calculant d'abord tous les sous-ensembles à 3 éléments des lignes de la matrice. Ensuite, pour chacun de ces sous-ensembles, nous le transposons et calculons son sous-ensemble de lignes à 3 éléments. Cela nous donne toutes les sous-matrices 3x3 possibles (bien qu'elles soient transposées). Nous calculons ensuite la moyenne sur chacun d'eux et trouvons le minimum global.

Martin Ender
la source
7

Gelée , 15 12 octets

œc3S€Zµ⁺FṂ÷9

Essayez-le en ligne!

Comment ça fonctionne

œc3S€Zµ⁺FṂ÷9  Main link. Argument: M (matrix)

œc3           Yield all combinations of 3 rows.
   S€         Map column-wise sum over the combinations.
     Z        Zip, transposing rows and columns.
      µ       Combine all links to the left into a chain.
       ⁺      Duplicate the chain, executing it twice.
        F     Flatten.
         Ṃ    Take the minimum.
          ÷9  Divide it by 9.
Dennis
la source
œc3S€µ⁺€FṂ÷9c'est ce que j'ai ... EDIT - hah et juste comme ça vous faites la même chose: D
Jonathan Allan
Ninja'd de 17 secondes. : P Merci quand même. :)
Dennis
Je ne peux pas m'empêcher de penser qu'il existe un moyen de se débarrasser de la 9en divisant par l' 3intérieur de la chaîne répétée, mais est-il possible d'obtenir 3comme le bon argument tel qu'il est possible en 11?
Jonathan Allan
Pas dans un octet, et c'est ce qu'il faudrait pour en enregistrer un. Vous ne pouvez pas placer 3 en dehors de la chaîne (à la fois parce que c'est monadique et que vous devez le grouper pour l'utiliser ), et à l'intérieur de la chaîne, vous devez soit le spécifier 3explicitement, soit le grouper ÷.
Dennis
4

05AB1E , 21 16 octets

2Fvyæ3ùO})ø}˜9/W

Essayez-le en ligne!

Explication

  • Pour chaque ligne, obtenez la somme de chaque sous-ensemble ordonné de taille 3
  • Transposer la matrice résultante
  • Pour chaque ligne, obtenez la somme de chaque sous-ensemble ordonné de taille 3
  • Aplatir la matrice résultante
  • Diviser par 9
  • Obtenez le minimum
Emigna
la source
1

Haskell , 90 octets

import Data.List
t r=[a+b+c|[a,b,c]<-subsequences r]
s=(/9).minimum.(t=<<).transpose.map t

Essayez-le en ligne!

Roman Czyborra
la source
1
concatMap tpeut être raccourci à(>>=t)
Laikoni
0

Bean , 198 octets

Hexdump:

00000000 bc 81 bd a0 65 40 a0 5d dd a0 68 50 80 a0 77 20  ¼.½ e@ ]Ý hP. w 
00000010 80 01 dd a0 66 25 3b 52 cc cb c0 50 84 a0 5d 20  ..Ý f%;RÌËÀP. ] 
00000020 66 87 4c cc a0 68 8b 20 66 8c 25 3b cd d0 84 a0  f.LÌ h. f.%;ÍÐ. 
00000030 5d 20 66 80 4e a0 66 81 4c d3 a0 65 a0 5d a0 68  ] f.N f.LÓ e ] h
00000040 4c a0 66 8c 25 3a 8b 25 3a 50 84 a0 5d 20 66 bd  L f.%:.%:P. ] f½
00000050 a0 6e 43 a5 39 a5 3a a5 3b 00 bd a0 5f 43 cf 20   nC¥9¥:¥;.½ _CÏ 
00000060 6e 00 3d a0 69 20 12 b6 a7 36 a7 26 4d a0 69 80  n.= i .¶§6§&M i.
00000070 53 d0 80 a0 1f 20 80 45 a0 69 53 d0 80 a0 6e 20  SÐ. . .E iSÐ. n 
00000080 80 8b 40 a0 6f a0 75 4c a0 6f 8b 53 d0 80 a0 5f  ..@ o uL o.SÐ. _
00000090 20 80 8b 40 a0 6f a0 74 4c a0 6f 8b 50 84 d0 84   ..@ o tL o.P.Ð.
000000a0 a0 77 20 75 20 74 4c d3 a0 65 a0 5f 50 80 a0 43   w u tLÓ e _P. C
000000b0 20 80 01 81 25 3b 4c d3 a0 65 20 6e 81 25 3b 26   ...%;LÓ e n.%;&
000000c0 4c a0 69 8e 25 42                                L i.%B
000000c6

JavaScript équivalent:

// indices array increment function
var i=(a,l=$.length,j=2)=>++a[j]>=l+j-2?a[j]=j&&i(a,l,j-1)+1:a[j],
// row indices
    r=[0,1,2],
// column indices
    c=[...r],
// minimum sum
    m=Infinity;
do{
  do{
// calculate sum of current row/column indices and keep minimum
    m=Math.min(m,
      (r.reduce((s,y)=>s+c.reduce((s,x)=>s+$[y][x])))
    )
// until column indices loop
  }while(i(c,A.length)!=2)
// until row indices loop
}while(i(r)!=2)
// output mean
m/9

Essayez la démo ici

Patrick Roberts
la source