Définition

Étant donné une matrice d'entiers non négatifs et un entier non négatif , nous définissons comme la fonction de "coupure" qui supprime toutes les lignes et toutes les colonnes de qui contiennent .$M$$k$$F_k$$M$$k$

Exemple:

$$\begin{align}M=\pmatrix{\color{red}6&\color{red}1&\color{white}{\bbox[red,1pt]{5}}\\1&2&\color{red}8\\\color{red}9&\color{red}8&\color{white}{\bbox[red,1pt]{5}}\\6&0&\color{red}4}\\\\F_5(M)=\pmatrix{1&2\\6&0}\end{align}$$

Ta tâche

Compte tenu de $M$ et une somme cible $S$ , votre tâche est de trouver toutes les valeurs possibles de $k$ tel que la somme des éléments restants dans $F_k(M)$ est égal à $S$ .

Exemple:

Étant donné la matrice ci-dessus $M$ et $S=9$ :

• $k=5$ est une solution, car $F_5(M)=\pmatrix{1&2\\6&0}$ et $1+2+6+0=9$
• $k=1$ est la seule autre solution possible: $F_1(M)=\pmatrix{5\\4}$ et $5+4=9$

La sortie attendue serait donc $\{1,5\}$ .

Clarifications et règles

• L'entrée est garantie pour admettre au moins une solution.
• La somme des éléments de la matrice d' origine est garanti pour être supérieur à $S$ .
• Vous pouvez supposer que $S>0$ . Cela signifie qu'une matrice vide ne mènera jamais à une solution.
• Les valeurs de $k$ peuvent être imprimées ou renvoyées dans n'importe quel ordre et dans n'importe quel format raisonnable et sans ambiguïté.
• Vous êtes autorisé à ne pas dédupliquer la sortie (par exemple ou sont considérés comme des réponses valides pour l'exemple ci-dessus).[ 1 , 5 , 1 , 5 $[1,1,5,5]$$[1,5,1,5]$
• C'est du code-golf .

Cas de test

M = [[6,1,5],[1,2,8],[9,8,5],[6,0,4]]
S = 9
Solution = {1,5}

M = [[7,2],[1,4]]
S = 7
Solution = {4}

M = [[12,5,2,3],[17,11,18,8]]
S = 43
Solution = {5}

M = [[7,12],[10,5],[0,13]]
S = 17
Solution = {0,13}

M = [[1,1,0,1],[2,0,0,2],[2,0,1,0]]
S = 1
Solution = {2}

M = [[57,8,33,84],[84,78,19,14],[43,14,81,30]]
S = 236
Solution = {19,43,57}

M = [[2,5,8],[3,5,8],[10,8,5],[10,6,7],[10,6,4]]
S = 49
Solution = {2,3,4,7}

M = [[5,4,0],[3,0,4],[8,2,2]]
S = 8
Solution = {0,2,3,4,5,8}

K (ngn / k) , 39 octets

{a@&y=x{+//x*(&/'b)&\:&/b:~x=y}/:a:,/x}

Essayez-le en ligne!

merci @ Adám pour cette explication :

{… }Fonction, xest M et yest S

 ,/x aplatir M (ce sont les k candidats)

 a: affecter à a

 x{… }/: Appliquez la fonction suivante à chacun en utilisant M comme argument gauche fixe ( x):

  x=y Matrice booléenne indiquant où les éléments de M sont égaux au candidat k actuel

  ~ nier cela

  b: attribuer cela à b

  &/ ET réduction (trouve les colonnes sans ce k )

  (… )&\: ET avec chacun des éléments suivants:

   &/'b ET réduction de chacun (recherche les lignes sans ce k )

  x* multiplier M par cela

  +// grande somme

 y= liste des booléens indiquant où S est égal à ces sommes

 & indices de Trues

 a@ utiliser cela pour indexer dans les éléments (les k candidats)

APL (Dyalog Unicode) , 35 33 28 octets ^SBCS

-7 grâce à ngn.

Infixe anonyme lambda. Prend S comme argument de gauche et M comme argument de droite.

{⍵[⍸⍺=(+/∘,⍵×∧/∘.∧∧⌿)¨⍵≠⊂⍵]}

Essayez-le en ligne!

{… } "Dfn", ⍺et ⍵sont respectivement des arguments gauche et droit ( S et M ):

 ⍵[… ] Index M avec les coordonnées suivantes:

  ⊂⍵ entourez M pour le traiter comme un élément unique

  ⍵= comparer chaque élément (c'est-à-dire k candidat) de M à l'ensemble de M

  (… )¨ Appliquer à chacun la fonction tacite suivante:

   ∧⌿ vertical ET réduction (recherche les colonnes sans ce k candidat)

… ∘.∧ Produit booléen cartésien avec:

    ∧/ réduction AND horizontale (recherche les lignes sans ce k candidat)

   ⍵× multiplier M avec ce masque

   +/∘, additionner la matrice aplatie

  ⍺= Booléen indiquant où S est égal à ces sommes

  ⍸ indices où c'est vrai

R , 78 73 octets

function(m,s)m[Map(function(y)sum(m[(w=-which(m==y,T))[,1],w[,2]]),m)==s]

Essayez-le en ligne!

Ne trie ni ne dédoublonne la sortie.

Crédit à J.Doe & Giuseppe pour -5 octets.

Gelée , 20 19 17 15 14 octets

pZnⱮFȦ€€ḋFẹƓịF

Il s'agit d'un lien monadique qui prend M comme argument et lit S à partir de STDIN.

Essayez-le en ligne!

Comment ça marche

pZnⱮFȦ€€ḋFẹƓịF  Main link. Argument: M

 Z              Zip; transpose the rows and columns of M.
p               Take the Cartesian product of M and its transpose, yielding all pairs
                (r, c) of rows and columns of M.
    F           Flatten; yield the elements of M.
  nⱮ            Not equal map; for each element e of M, compare the elements of the
                pairs (r, c) with e.
     Ȧ€€        All each each; for each array of Booleans corresponding to an (r, c)
                pair, test if all of them are true.
         F      Flatten; yield the elements of M.
        ḋ       Take the dot product of each list of resulting Booleans and the
                elements of M.
           Ɠ    Read an integer S from STDIN.
          ẹ     Find all indices of S in the dot products.
             F  Flatten; yield the elements of M.
            ị   Retrieve the elements of the right at the indices from the left.

Haskell , 88 86 84 77 octets

• -2 octets grâce à BWO
• -7 octets grâce à Tesseract

m!s=[k|k<-m>>=id,s==sum[x|r<-m,all(/=k)r,(i,x)<-zip[0..]r,all((/=k).(!!i))m]]

Vérifiez tous les cas de test .

Explication

m ! s =                                         -- function !, taking m and s as input
    [k |                                        -- the list of all k's such that
        k <- m >>= id,                          -- * k is an entry of m
        s == sum                                -- * s equals the sum of
            [x |                                --     the list of x's such that
                r <- m,                         --     * r is a row of m
                all (/= k) r,                   --     * r does not contain k
                (i, x) <- zip [0 ..] r,         --     * i is a valid column index; also let x = r[i]
                all ((/= k) . (!! i)) m         --     * none of the rows contain k at index i
            ]
    ]

Pyth ,  27 23 22 21  20 octets

fqvzss.DRsxLTQ-I#TQs

Suite de tests!

Ne dédoublonne pas.

Comment ça marche?

fqvzss.DRsxLTQ-I#TQs     Full program.
f                  s     Flatten M and keep only those elements T which satisfy:
 qvzss.DRsxLTQ-I#TQ      The filtering function. Breakdown:
              -I#TQ      Discard the rows that contain T. More elaborate explanation:
                # Q         |-> In M, keep only those elements that are...
               I            |-> Invariant under (equal to themselves after...)
              -  T          |-> Removing T.
                         Let's call the result of this expression CR (chopped rows).
          xLTQ           Map over the rows M and retrieve all indices of T.
         s               Collect indices in 1D list (flatten). Call this I.
      .DR                For each row left in CR, remove the elements at indices in I.
    ss                   Sum all the elements of this matrix flattened.
 qvz                     And then finally check whether they equal S.

Python 2 , 114 108 octets

lambda m,s:{a for a in sum(m,[])if s==sum(v for l in m for i,v in enumerate(l)if{a}-set(l)-set(zip(*m)[i]))}

Essayez-le en ligne!

Perl 6 , 80 74 octets

->\m,\s{grep {s==sum m[m.$_;[[Z](m).$_]]}o{*.grep(:k,!*.grep($_))},m[*;*]}

Essayez-le en ligne!

Explication

->\m,\s{...}  # Anonymous block taking arguments m and s
  grep {...}o{...},m[*;*]   # Filter matrix elements
                            # with combination of two functions
    *.grep(:k,!*.grep($_))  # (1) Whatever code returning matching rows
    s==sum m[               # (2) s equals sum of elements
      m.$_;                 #     in matched rows
      [                     #     (array supporting multiple iterations)
       [Z](m).$_            #     and matched columns (matched rows
                            #     of m transposed with [Z])
      ]
    ]

05AB1E , 21 octets

²˜ʒQεZ+}øεZ<~}ø_*OO¹Q

Essayez-le en ligne!

Ce n'est qu'après avoir écrit cette réponse que j'ai vu celle de Kevin . Je crois que c'est substantiellement différent, donc je le poste séparément. Mon intuition dit que le nombre optimal d'octets est d'environ 18, donc je vais devoir revoir cela et voir ce que je peux faire d'autre. Avec le code actuel, il est impossible d'écrire une suite de tests mais j'ai moi-même vérifié tous les cas de test et les résultats sont corrects.

Algorithme de recadrage

$k=5$

$$M=\left(\begin{matrix}6&1&\bbox[green,1pt]{\color{white}{5}}\\1&2&8\\9&8&\bbox[green,1pt]{\color{white}{5}}\\6&0&4\end{matrix}\right)$$

$k$

$$\left(\begin{matrix}0&0&1\\0&0&0\\0&0&1\\0&0&0\end{matrix}\right)$$

$M$$R$$\max(R)$$R$

$$\left(\begin{matrix}\color{green}{1}&\color{green}{1}&\bbox[green,1pt]{\color{white}{2}}\\0&0&0\\\color{green}{1}&\color{green}{1}&\bbox[green,1pt]{\color{white}{2}}\\0&0&0\end{matrix}\right)$$

$M$$C$$(\max(C)-1)\space ||\space c\space\forall\space c\in C\:$$||$~+

$$\left(\begin{matrix}\color{green}{1}&\color{green}{1}&\bbox[green,1pt]{\color{white}{3}}\\0&0&\color{green}{1}\\\color{green}{1}&\color{green}{1}&\bbox[green,1pt]{\color{white}{3}}\\0&0&\color{green}{1}\end{matrix}\right)$$

$0$$1$$0$$M$

$$\left(\begin{matrix}\color{green}{0}&\color{green}{0}&\color{green}{0}\\1&1&\color{green}{0}\\\color{green}{0}&\color{green}{0}&\color{green}{0}\\1&1&\color{green}{0}\end{matrix}\right)\:\longrightarrow\:\left(\begin{matrix}\color{green}{0}&\color{green}{0}&\color{green}{0}\\1&2&\color{green}{0}\\\color{green}{0}&\color{green}{0}&\color{green}{0}\\6&0&\color{green}{0}\end{matrix}\right)$$

Après quoi la somme de la matrice résultante est calculée.

05AB1E (hérité) , 27 26 octets

˜ʒ©¹ε®å_}¹ζʒ®å_}ζ‚ζ€€OPOIQ

Ne trie ni n'unifie le résultat.
Ne fonctionne que dans l'héritage (pour l'instant), car sum-each semble faire des choses étranges lorsqu'une partie des listes internes sont des entiers et d'autres des listes.

Essayez-le en ligne ou vérifiez tous les cas de test .

Explication:

˜              # Flatten the (implicit) matrix-input
               #  i.e. [[6,1,5],[1,2,8],[9,8,5],[6,0,4]] → [6,1,5,1,2,8,9,8,5,6,0,4]
 ʒ             # Filter this list by:
  ©            #  Store the current value in a register-variable
   ¹           #  Take the matrix-input
    ε   }      #  Map it to:
     ®å_       #   0 if the current number is in this row, 1 if not
               #    i.e. [[6,1,5],[1,2,8],[9,8,5],[6,0,4]] and 6 → [0,1,1,0]
   ¹           #  Take the matrix-input again
    ζ          #  Swap its rows and columns
               #   i.e. [[6,1,5],[1,2,8],[9,8,5],[6,0,4]] → [[6,1,9,6],[1,2,8,0],[5,8,5,4]]
     ʒ   }     #  Filter it by:
      ®å_      #   Only keep the inner lists that does not contain the current number
               #    i.e. [[6,1,9,6],[1,2,8,0],[5,8,5,4]] and 6 → [[1,2,8,0],[5,8,5,4]]
               #    i.e. [[1,2,2],[1,0,0],[0,0,1],[1,2,0]] and 1 → []
          ζ    #  After filtering, swap it's rows and columns back again
               #   i.e. [[1,2,8,0],[5,8,5,4]] → [[1,5],[2,8],[8,5],[0,4]]
   ‚ζ          #  Pair both lists together and zip them
               #   i.e. [0,1,1,0] and [[1,5],[2,8],[8,5],[0,4]]
               #    → [[0,[1,5]],[1,[2,8]],[1,[8,5]],[0,[0,4]]]
               #   i.e. [0,1,0] and [] → [[0,' '],[1,' '],[0,' ']]
     €         #  Map each inner list / value to:
      €O       #   Sum each
               #    i.e. [[0,[1,5]],[1,[2,8]],[1,[8,5]],[0,[0,4]]]
               #     → [[0,6],[1,10],[1,13],[0,4]]
               #    i.e. [[0,' '],[1,' '],[0,' ']]
               #     → [[0,0],[1,0],[0,0]]
               #  (NOTE: For most test cases just `O` instead of `€€O` would be enough,
               #   but not if we removed ALL zipped inner lists for a number, like the 
               #   second example above with input [[1,1,0,1],[2,0,0,2],[2,0,1,0]] and 1)
        P      #  Now take the product of each inner list
               #   i.e. [[0,6],[1,10],[1,13],[0,4]] → [0,10,13,0]
         O     #  Then take the sum of those
               #   i.e. [0,10,13,0] → 23
          IQ   #  And only keep those that are equal to the number-input
               #   i.e. 23 and 9 → 0 (falsey), so it's removed from the flattened input

Gelée , 22 octets

=+Ṁ$€Z$⁺’¬×⁸FS
F³ç=⁹ƲƇ

Essayez-le en ligne!

-6 octets en utilisant l'approche générale de la réponse 05AB1E de M. Xcoder.

Fusain , 33 octets

ＦθＦι⊞υκＩΦυ⁼ηΣＥθ∧¬№λιΣＥλ∧¬№Ｅθ§πξιν

Essayez-le en ligne! Le lien est vers la version détaillée du code et inclut la déduplication. Explication:

ＦθＦι⊞υκ

Aplatissez le premier tableau d'entrée qdans la liste prédéfinie u.

  υ                          Flattened array
 Φ                           Filter elements
       θ                     Input array
      Ｅ                      Map over rows
            ι                Current element
           λ                 Current row
          №                  Count matching elements
         ¬                   Logical Not
        ∧                    Logical And
               λ             Current row
              Ｅ              Map over columns
                    θ        Input array
                   Ｅ         Map over rows
                      π      Inner row
                       ξ     Column index
                     §       Inner element
                        ι    Current element
                  №          Count matching elements
                 ¬           Logical Not
                ∧            Logical And
                         ν   Current element
             Σ               Sum
     Σ                       Sum
    η                        Second input
   ⁼                         Equals
Ｉ                            Cast to string
                             Implicitly print each result on its own line

Pour chaque élément de la liste, additionnez le tableau, mais si la ligne contient l'élément, utilisez-le à la 0place de sa somme, et lorsque vous additionnez des lignes qui ne contiennent pas l'élément, si la colonne contient l'élément, utilisez-le à la 0place de la valeur de la colonne . C'est très légèrement plus golfique que de filtrer les éléments car le charbon ne peut pas additionner une liste vide.

Nettoyer , 92 octets

import StdEnv
$m s=[c\\r<-m,c<-r|sum[b\\a<-m|all((<>)c)a,b<-a&x<-[0..]|all(\u=u!!x<>c)m]==s]

Essayez-le en ligne!

Expliqué:

$ m s                       // the function $ of `m` and `s`
 = [                        // is equal to
  c                         // the value `c`
  \\ r <- m                 // for every row `r` in `m`
  , c <- r                  // for every value `c` in `r`
  | sum [                   // where the sum of
   b                        // the value `b`
   \\ a <- m                // for every row `a` in `m`
   | all ((<>)c) a          // where `c` isn't in `a`
   , b <- a                 // for every value `b` in `a`
   & x <- [0..]             // with every column index `x` from zero
   | all (\u = u!!x <> c) m // where `c` isn't in column `x`
  ] == s                    // equals `s`
 ]

MATLAB - 80 octets

( Corrigé et ) Compacté:

function f(M,s);for k=M(:)';if sum(sum(M(~sum(M==k,2),~sum(M==k))))==s;k,end;end

Et dans une version entièrement développée:

function getthesum(M,s)

for k=M(:)'                         % For each element of M
    x = M==k ;                      % Index elements equal to "k"
    N = M( ~sum(x,2) , ~sum(x) ) ;  % New matrix with only the appropriate rows/columns
    if sum(sum(N))==s               % sum rows and columns and compare to "s"
        k                           % display "k" in console if "k" is valid
    end
end

---

Merci aux commentaires pour souligner mon erreur initiale. Notez que cette version ne supprime pas la sortie.

Il est possible de dédupliquer la sortie avec 5 octets supplémentaires:

% This will only cycle through the unique elements of 'M' (85 bytes):

function f(M,s);for k=unique(M)';if sum(sum(M(~sum(M==k,2),~sum(M==k))))==s;k,end;end