Definição

Dada uma matriz $M$ de números inteiros não negativos e um número inteiro não negativo $k$ , definimos como a função "cortar" que remove todas as linhas e todas as colunas em que contêm . M $F_k$$M$$k$

Exemplo:

$$\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}$$

Sua tarefa

Dada e uma soma alvo S , sua tarefa é encontrar todos os valores possíveis de k tal que a soma dos elementos restantes F_k (M) é igual a S .S k F k ( M ) $M$$S$$k$$F_k(M)$$S$

Exemplo:

Dada a matriz acima $M$ e $S=9$ :

• $k=5$ é uma solução, porque $F_5(M)=\pmatrix{1&2\\6&0}$ e $1+2+6+0=9$
• $k=1$ é a única outra solução possível: $F_1(M)=\pmatrix{5\\4}$ e $5+4=9$

Portanto, a saída esperada seria $\{1,5\}$ .

Esclarecimentos e regras

• A entrada é garantida para admitir pelo menos uma solução.
• A soma dos elementos da matriz original é garantida para ser maior do que $S$ .
• Você pode assumir $S>0$ . Isso significa que uma matriz vazia nunca levará a uma solução.
• Os valores de $k$ podem ser impressos ou retornados em qualquer ordem e em qualquer formato razoável e inequívoco.
• Você tem permissão para não deduplicar a saída (por exemplo, ou são consideradas respostas válidas para o exemplo acima).[ 1 , 5 , 1 , 5 $[1,1,5,5]$$[1,5,1,5]$
• Este é o código-golf .

Casos de teste

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 bytes

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

Experimente online!

obrigado @ Adám por esta explicação :

{… }Função, xé M e yé S

 ,/x achatar M (estes são os k candidatos)

 a: atribuir a a

 x{… }/: Aplique a seguinte função a cada um enquanto estiver usando M como argumento fixo à esquerda ( x):

  x=y Matriz booleana indicando onde os elementos de M são iguais ao candidato atual k

  ~ negar isso

  b: atribuir isso a b

  &/ E redução (localiza colunas sem esse k )

  (… )&\: E com cada um dos seguintes:

   &/'b E redução de cada (encontra linhas sem esse k )

  x* multiplique M por isso

  +// grande soma

 y= lista de booleanos indicando onde S é igual a essas somas

 & índices de Trues

 a@ use isso para indexar nos elementos (os k candidatos)

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

-7 graças a ngn.

Infix anônimo lambda. Toma S como argumento à esquerda e M como argumento à direita.

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

Experimente online!

{… } "Dfn" ⍺e ⍵são argumentos à esquerda e à direita ( S e M ), respectivamente:

 ⍵[… ] Índice M com as seguintes coordenadas:

  ⊂⍵ coloque M para tratá-lo como um único elemento

  ⍵= compare cada elemento (ou seja, k candidato) de M com todo esse M

  (… )¨ Aplique a seguinte função tácita a cada um:

   ∧⌿ vertical AND redução (localiza colunas sem esse k candidato)

… ∘.∧ Produto booleano cartesiano com:

    ∧/ horizontal AND redução (localiza linhas sem esse k candidato)

   ⍵× multiplicar M com essa máscara

   +/∘, somar a matriz achatada

  ⍺= Booleano indicando onde S é igual a essas somas

  ⍸ índices onde isso é verdade

R , 78 73 bytes

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

Experimente online!

Não classifica nem desduplica a saída.

Crédito para J.Doe & Giuseppe por -5 bytes.

Geléia , 20 19 17 15 14 bytes

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

Este é um link monádico que usa M como argumento e lê S de STDIN.

Experimente online!

Como funciona

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 bytes

• -2 bytes graças ao BWO
• -7 bytes graças ao Tesseract

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

Verifique todos os casos de teste .

Explicação

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

Pitão ,  27 23 22 21  20 bytes

fqvzss.DRsxLTQ-I#TQs

Suíte de teste!

Não deduplicado.

Como funciona?

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 bytes

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]))}

Experimente online!

Perl 6 , 80 74 bytes

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

Experimente online!

Explicação

->\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 bytes

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

Experimente online!

Somente depois de escrever essa resposta é que vi a de Kevin . Acredito que isso seja substancialmente diferente, por isso estou publicando separadamente. Minha intuição diz que a contagem ideal de bytes é de cerca de 18, então terei que revisar isso e ver o que mais posso fazer. Com o código atual, é impossível escrever um conjunto de testes, mas eu mesmo verifiquei todos os casos de teste e os resultados estão corretos.

Algoritmo de corte

$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)$ para cada elemento em $R$, destacando as linhas necessárias e ainda preservando a exclusividade das posições horizontais do elemento pesquisado:

$$\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)$$

Em seguida, passa pela transposição de $M$ e para cada coluna $C$, realiza a operação $(\max(C)-1)\space ||\space c\space\forall\space c\in C\:$ (Onde $||$é o OR bit a bit de 05AB1E - a adição também deve funcionar, então substitua ~por +se você quiser testar isso também), o que resulta em:

$$\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)$$

Finalmente, mapeia $0$ para $1$ e todos os outros números inteiros para $0$ e executa multiplicação por elementos com $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)$$

Após o qual a soma da matriz resultante é calculada.

05AB1E (legado) , 27 26 bytes

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

Não classifica nem unifica o resultado.
Só funciona no legado (por enquanto), porque soma-cada parece estar fazendo algumas coisas estranhas quando parte das listas internas são números inteiros e outras são listas.

Experimente online ou verifique todos os casos de teste .

Explicação:

˜              # 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

Gelatina , 22 bytes

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

Experimente online!

-6 bytes usando a abordagem geral da resposta 05AB1E do Sr. Xcoder.

Carvão , 33 bytes

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

Experimente online! Link é uma versão detalhada do código e inclui desduplicação. Explicação:

ＦθＦι⊞υκ

Nivele a primeira matriz de entrada qna lista predefinida 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

Para cada elemento da lista, some a matriz, mas se a linha contiver o elemento, use em 0vez de sua soma e, ao somar linhas que não contêm o elemento, se a coluna contiver o elemento, use em 0vez do valor da coluna . Isso é muito mais fácil do que filtrar os elementos, pois o carvão não pode somar uma lista vazia.

Limpo , 92 bytes

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]

Experimente online!

Explicado:

$ 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 bytes

( Corrigido e ) Compactado:

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

E em uma versão totalmente desenvolvida:

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

---

Obrigado aos comentários para destacar meu erro inicial. Observe que esta versão não desduplica a saída.

É possível deduplicar a saída com mais 5 bytes:

% 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