Definicja

Biorąc pod uwagę macierz nieujemnych liczb całkowitych i nieujemną liczbę całkowitą , definiujemy jako funkcję „odcinania”, która usuwa wszystkie wiersze i wszystkie kolumny w które zawierają .$M$$k$$F_k$$M$$k$

Przykład:

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

Twoje zadanie

Biorąc pod uwagę, $M$ i suma cel $S$ , twoim zadaniem jest znaleźć wszystkie możliwe wartości $k$ takie, że suma pozostałych elementów $F_k(M)$ jest równa $S$ .

Przykład:

Biorąc pod uwagę powyższą macierz $M$ i $S=9$ :

• $k=5$ jest rozwiązaniem, ponieważ $F_5(M)=\pmatrix{1&2\\6&0}$ oraz $1+2+6+0=9$
• $k=1$ to jedyne inne możliwe rozwiązanie: $F_1(M)=\pmatrix{5\\4}$ i $5+4=9$

Oczekiwany wynik to $\{1,5\}$ .

Wyjaśnienia i zasady

• Wejście gwarantuje, że przyjmie się co najmniej jedno rozwiązanie.
• Suma pierwiastków w oryginalnej matrycy zagwarantowane jest większa niż $S$ .
• Możesz założyć $S>0$ . Oznacza to, że pusta matryca nigdy nie doprowadzi do rozwiązania.
• Wartości $k$ mogą być drukowane lub zwracane w dowolnej kolejności i w dowolnym rozsądnym, jednoznacznym formacie.
• Możesz nie deduplikować danych wyjściowych (np. lub są uważane za prawidłowe odpowiedzi dla powyższego przykładu).[ 1 , 5 , 1 , 5 $[1,1,5,5]$$[1,5,1,5]$
• To jest golf golfowy .

Przypadki testowe

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 bajtów

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

Wypróbuj online!

dzięki @ Adám za to wyjaśnienie :

{... }funkcja xjest K i yjest S

 ,/x spłaszcz M (są to k kandydaci)

 a: Przypisać do a

 x{… }/: Zastosuj następującą funkcję do każdej z nich, używając M jako stałego lewego argumentu ( x):

  x=y Macierz boolowska wskazująca, gdzie elementy M są równe bieżącemu kandydatowi k

  ~ zaneguj to

  b: przypisz to do b

  &/ ORAZ redukcja (wyszukuje kolumny bez tego k )

  (… )&\: I to z każdym z poniższych:

   &/'b ORAZ zmniejszenie każdego (wyszukuje wiersze bez tego k )

  x* pomnóż M przez to

  +// wielka suma

 y= lista booleanów wskazująca gdzie S równa się tym sumom

 & wskaźniki Trues

 a@ użyj tego, aby zindeksować elementy ( k kandydatów)

APL (Dyalog Unicode) , 35 33 28 bajtów ^SBCS

-7 dzięki ngn.

Anonimowy przyrostek lambda. Traktuje S jako lewy argument, a M jako prawy argument.

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

Wypróbuj online!

{… } „Dfn” ⍺i ⍵są odpowiednio lewym i prawym argumentem ( S i M ):

 ⍵[… ] Indeks M z następującymi współrzędnymi:

  ⊂⍵ dołącz M, aby traktować go jako pojedynczy element

  ⍵= porównaj każdy element (tj. k kandydata) M z całym M

  (… )¨ Zastosuj następującą funkcję ukrytą dla każdego:

   ∧⌿ redukcja pionowa AND (wyszukuje kolumny bez tego k kandydata)

… ∘.∧ Kartezjański boolowski produkt o:

    ∧/ redukcja pozioma ORAZ (wyszukuje wiersze bez tego k kandydata)

   ⍵× pomnóż M przez tę maskę

   +/∘, zsumuj spłaszczoną macierz

  ⍺= Wartość logiczna wskazująca, gdzie S równa się tym sumom

  ⍸ wskaźniki tam, gdzie to prawda

R , 78 73 bajtów

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

Wypróbuj online!

Nie sortuje ani nie deduplikuje danych wyjściowych.

Kredyt dla J.Doe & Giuseppe za -5 bajtów.

Galaretka , 20 19 17 15 14 bajtów

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

To łącze monadyczne, które przyjmuje M jako argument i odczytuje S ze STDIN.

Wypróbuj online!

Jak to działa

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 bajtów

• -2 bajty dzięki BWO
• -7 bajtów dzięki Tesseract

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

Sprawdź wszystkie przypadki testowe .

Wyjaśnienie

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 bajtów

fqvzss.DRsxLTQ-I#TQs

Zestaw testowy!

Nie deduplikuje.

Jak to działa?

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 bajtów

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

Wypróbuj online!

Perl 6 , 80 74 bajtów

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

Wypróbuj online!

Wyjaśnienie

->\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 bajtów

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

Wypróbuj online!

Dopiero po napisaniu tej odpowiedzi zobaczyłem Kevina . Uważam, że jest to zasadniczo inna kwestia, więc publikuję to osobno. Moja intuicja mówi, że optymalna liczba bajtów wynosi około 18, więc będę musiał to sprawdzić i zobaczyć, co jeszcze mogę zrobić. Przy obecnym kodzie nie można napisać zestawu testów, ale sam zweryfikowałem wszystkie przypadki testowe i wyniki są poprawne.

Algorytm kadrowania

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

Po czym obliczana jest suma wynikowej macierzy.

05AB1E (starsza wersja) , 27 26 bajtów

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

Nie sortuje ani nie jednoczy wyniku.
Działa tylko w starszej wersji (na razie), ponieważ suma-każda wydaje się robić dziwne rzeczy, gdy część wewnętrznych list jest liczbami całkowitymi, a inne są listami.

Wypróbuj online lub sprawdź wszystkie przypadki testowe .

Wyjaśnienie:

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

Galaretka , 22 bajty

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

Wypróbuj online!

-6 bajtów przy użyciu ogólnego podejścia z odpowiedzi 05AB1E pana Xcodera.

Węgiel drzewny , 33 bajty

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

Wypróbuj online! Link jest do pełnej wersji kodu i zawiera deduplikację. Wyjaśnienie:

ＦθＦι⊞υκ

Spłaszcz pierwszą tablicę wejściową qna predefiniowanej liście 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

Dla każdego elementu listy zsumuj tablicę, ale jeśli wiersz zawiera element, użyj 0zamiast jego sumy, a podczas sumowania wierszy, które nie zawierają elementu, jeśli kolumna zawiera element, użyj 0zamiast wartości kolumny . Jest to nieco bardziej golfistyczne niż filtrowanie elementów, ponieważ węgiel drzewny nie może zsumować pustej listy.

Czysty , 92 bajty

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]

Wypróbuj online!

Wyjaśnił:

$ 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 bajtów

( Poprawione i ) Kompaktowane:

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

I w pełni rozwiniętej wersji:

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

---

Dzięki komentarzom podkreślam mój początkowy błąd. Pamiętaj, że ta wersja nie duplikuje danych wyjściowych.

Możliwe jest deduplikowanie danych wyjściowych za pomocą 5 dodatkowych bajtów:

% 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