Chop off the matrix to get the desired sum

Given a matrix $M$ of non-negative integers and a non-negative integer $k$, we define $F_k$ as the "chop-off" function that removes all rows and all columns in $M$ that contain $k$.

Example:

$$beginalignM=pmatrixcolorred6&colorred1&colorwhitebbox[red,1pt]5\1&2&colorred8\colorred9&colorred8&colorwhitebbox[red,1pt]5\6&0&colorred4\\F_5(M)=pmatrix1&2\6&0endalign$$

Given $M$ and a target sum $S$, your task is to find all possible values of $k$ such that the sum of the remaining elements in $F_k(M)$ is equal to $S$.

Example:

Given the above matrix $M$ and $S=9$:

So the expected output would be $1,5$.

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


[[1,5],[1],[5],]

14 Answers
14

K (ngn/k), 39 bytes

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


Try it online!

thanks @Adám for this explanation:

… function, x is M and y is S

x

y

 ,/x flatten M (these are the k candidates)

,/x

 a: assign to a

a:

a

 x…/: apply the following function to each while using M as fixed left argument (x):

x

/:

x

  x=y Boolean matrix indicating where elements of M equal the current k candidate

x=y

  ~ negate that

~

  b: assign that to b

b:

b

  &/ AND reduction (finds columns without that k)

&/

  (…)&: AND that with each of the following:

(

)&:

   &/'b AND reduction of each (finds rows without that k)

&/'b

  x* multiply M by that

x*

  +// grand sum

+//

 y= list of Booleans indicating where S equals those sums

y=

 & indices of Trues

&

 a@ use that to index into the elements (the k candidates)

a@

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

-7 thanks to ngn.

Anonymous infix lambda. Takes S as left argument and M as right argument.

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


Try it online!

… "dfn", ⍺ and ⍵ are left and right arguments (S and M) respectively:

⍺

⍵

 ⍵[…] index M with the following coordinates:

⍵[

]

  ⊂⍵ enclose M to treat it as a single element

⊂⍵

  ⍵= compare each element (i.e. k candidate) of M to that entire M

⍵=

  (…)¨ apply the following tacit function to each:

(

)¨

   ∧⌿ vertical AND reduction (finds columns without that k candidate)

∧⌿

…∘.∧ Cartesian Boolean product with:

∘.∧

    ∧/ horizontal AND reduction (finds rows without that k candidate)

∧/

   ⍵× multiply M with that mask

⍵×

   +/∘, sum the flattened matrix

+/∘,

  ⍺= Boolean indicating where S equals those sums

⍺=

  ⍸ indices where that's true

⍸

M[⍸⍺=+/,(∧⌿d)/M⌿⍨∧/d←M≠⍵¨M←⍵]

M

⍵

⍺

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

R, 78 73 bytes

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


Try it online!

Does not sort or deduplicate the output.

Credit to J.Doe & Giuseppe for -5 bytes.

Jelly, 20 19 17 15 14 bytes

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


This is a monadic link that takes M as argument and reads S from STDIN.

Try it online!

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

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


Verify all testcases.

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 bytes

fqvzss.DRsxLTQ-I#TQs


Test suite!

Does not deduplicate.

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)ifa-set(l)-set(zip(*m)[i]))


Try it online!

Perl 6, 80 74 bytes

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


Try it online!

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


Try it online!

Only after I've written this answer have I seen Kevin's. I believe this is substantially different, so I am posting it separately. My intuition says that the optimal byte count is around 18, so I'll have to revisit this and see what else I can do. With the current code, it is impossible to write a test suite but I have verified all test cases myself and the results are correct.

To better illustrate the technique used, let's grab an example, with the element to crop $k=5$:

$$M=left(beginmatrix6&1&bbox[green,1pt]colorwhite5\1&2&8\9&8&bbox[green,1pt]colorwhite5\6&0&4endmatrixright)$$

It first generates the matrix of equality with $k$:

$$left(beginmatrix0&0&1\0&0&0\0&0&1\0&0&0endmatrixright)$$

Then, it goes through $M$ and for each row $R$, it adds $max(R)$ to each element in $R$, highlighting the necessary rows while still preserving the uniqueness of the horizontal positions of the searched element:

$$left(beginmatrixcolorgreen1&colorgreen1&bbox[green,1pt]colorwhite2\0&0&0\colorgreen1&colorgreen1&bbox[green,1pt]colorwhite2\0&0&0endmatrixright)$$

Then, it goes through the transpose of $M$ and for each column $C$, it performs the operation $(max(C)-1)space ||space cspaceforallspace cin C:$ (where $||$ is 05AB1E's bitwise OR – addition should work too, so replace ~ with + if you want to test that too), which results in:

~

+

$$left(beginmatrixcolorgreen1&colorgreen1&bbox[green,1pt]colorwhite3\0&0&colorgreen1\colorgreen1&colorgreen1&bbox[green,1pt]colorwhite3\0&0&colorgreen1endmatrixright)$$

Finally, it maps $0$ to $1$ and all other integers to $0$ and performs element-wise multiplication with $M$:

$$left(beginmatrixcolorgreen0&colorgreen0&colorgreen0\1&1&colorgreen0\colorgreen0&colorgreen0&colorgreen0\1&1&colorgreen0endmatrixright):longrightarrow:left(beginmatrixcolorgreen0&colorgreen0&colorgreen0\1&2&colorgreen0\colorgreen0&colorgreen0&colorgreen0\6&0&colorgreen0endmatrixright)$$

After which the sum of the resulting matrix is computed.

[[1,1,0,1],[2,0,0,2],[2,0,1,0]]

1

1|2

1 2~

logical OR

binary OR

0

1

+

05AB1E (legacy), 27 26 bytes

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


Does not sort nor uniquify the result.

Only works in the legacy (for now), because sum-each seems to be doing some odd things when part of the inner lists are integers and other are lists..

Try it online or verify all test cases.

Explanation:

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


Jelly, 22 bytes

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


Try it online!

-6 bytes using the general approach from Mr. Xcoder's 05AB1E answer.

Charcoal, 33 bytes

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


Try it online! Link is to verbose version of code and includes deduplication. Explanation:

ＦθＦι⊞υκ


Flatten the first input array q into the predefined list u.

q

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


For each element of the list, sum the array, but if the row contains the element then use 0 instead of its sum, and when summing rows that don't contain the element, if the column contains the element then use 0 instead of the column's value. This is very slightly golfier than filtering the elements out as Charcoal can't sum an empty list.

0

0

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


Try it online!

Explained:

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


(Corrected and) Compacted:

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


And in a fully developped version:

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


Thanks to the comments to highlight my initial mistake. Note that this version does not de-duplicate the output.

It is possible to deduplicate the output with 5 more 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


If this is an answer to a challenge…

…Be sure to follow the challenge specification. However, please refrain from exploiting obvious loopholes. Answers abusing any of the standard loopholes are considered invalid. If you think a specification is unclear or underspecified, comment on the question instead.

…Try to optimize your score. For instance, answers to code-golf challenges should attempt to be as short as possible. You can always include a readable version of the code in addition to the competitive one.
Explanations of your answer make it more interesting to read and are very much encouraged.

…Include a short header which indicates the language(s) of your code and its score, as defined by the challenge.

More generally…

…Please make sure to answer the question and provide sufficient detail.

…Avoid asking for help, clarification or responding to other answers (use comments instead).

Some of your past answers have not been well-received, and you're in danger of being blocked from answering.

Please pay close attention to the following guidance:

But avoid …

To learn more, see our tips on writing great answers.

Required, but never shown

Required, but never shown

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.