Problem

Betrachten Sie ein Quadrat aus nicht negativen ganzen Zahlen im Verhältnis 3 zu 3. Für jede Zeile wird idie Summe der ganzen Zahlen auf gesetzt r_i. In ähnlicher Weise wird für jede Spalte jdie Summe der Ganzzahlen in dieser Spalte auf gesetzt c_j.

Die Aufgabe besteht darin, Code zu schreiben, um alle möglichen unterschiedlichen Zuordnungen von Ganzzahlen zu dem Raster unter Berücksichtigung der Summenbedingungen für Zeilen und Spalten aufzulisten. Ihr Code sollte jeweils eine Zuweisung ausgeben.

Eingang

Ihr Code sollte 3 nicht negative Ganzzahlen, die die Zeilenbeschränkungen angeben, und 3 nicht negative Ganzzahlen, die die Spaltenbeschränkungen angeben, enthalten. Sie können davon ausgehen, dass diese gültig sind, dh dass die Summen- oder Zeileneinschränkungen der Summe der Spalteneinschränkungen entsprechen. Ihr Code kann dies auf jede bequeme Weise tun.

Ausgabe

Ihr Code sollte die verschiedenen 2D-Gitter, die er berechnet, in einem von Menschen lesbaren Format Ihrer Wahl ausgeben. Je schöner, desto besser natürlich. Die Ausgabe darf keine doppelten Raster enthalten.

Beispiel

Wenn alle Zeilen- und Spalteneinschränkungen exakt sind, 1gibt es nur 6verschiedene Möglichkeiten. Für die erste Reihe können Sie eine 1in eine der ersten drei Spalten einfügen, für die zweite Reihe gibt es jetzt 2Alternativen und die letzte Reihe ist jetzt vollständig durch die beiden vorhergehenden bestimmt. Alles andere im Raster sollte auf eingestellt sein 0.

Angenommen, die Eingabe gilt 2 1 0für die Zeilen und 1 1 1für die Spalten. Unter Verwendung des schönen Ausgabeformats von APL sind die möglichen Ganzzahlgitter:

┌─────┬─────┬─────┐
│0 1 1│1 0 1│1 1 0│
│1 0 0│0 1 0│0 0 1│
│0 0 0│0 0 0│0 0 0│
└─────┴─────┴─────┘

Sagen wir nun, die Eingabe gilt 1 2 3für die Zeilen und 3 2 1für die Spalten. Die möglichen Ganzzahlgitter sind:

┌─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┐
│0 0 1│0 0 1│0 0 1│0 1 0│0 1 0│0 1 0│0 1 0│1 0 0│1 0 0│1 0 0│1 0 0│1 0 0│
│0 2 0│1 1 0│2 0 0│0 1 1│1 0 1│1 1 0│2 0 0│0 1 1│0 2 0│1 0 1│1 1 0│2 0 0│
│3 0 0│2 1 0│1 2 0│3 0 0│2 1 0│2 0 1│1 1 1│2 1 0│2 0 1│1 2 0│1 1 1│0 2 1│
└─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┘

APL (Dyalog) , 42 Bytes

{o/⍨(⍵≡+/,+⌿)¨o←3 3∘⍴¨(,o∘.,⊢)⍣8⊢o←⍳1+⌈/⍵}

Probieren Sie es online!

Verwendet ⎕IO←0die Standardeinstellung auf vielen Systemen. Das andere Zeug in der Kopfzeile ist nur ein hübscher Ausdruck für die Matrizen (Boxed Display).

Die Eingabe ist eine Liste mit sechs Werten, wobei zuerst die Zeilensummen und dann die Spaltensummen angegeben werden.

Wie?

o←⍳1+⌈/⍵- oRuft den Bereich 0bis zum Maximum ( ⌈/) der Eingabe ab

,o∘.,⊢- kartesisches Produkt mit ound Abflachen ( ,)

⍣8 - Achtmal wiederholt

3 3∘⍴¨ - Formen Sie jede 9-Elemente-Liste in eine 3 × 3-Matrix

¨o←- Speichern Sie diese Matrizen in ound für jeden

+/,+⌿- Überprüfen Sie, ob die Zeilen Summen ( +/) mit den Spaltensummen ( +⌿) verknüpft sind.

⍵≡ - entsprechen der Eingabe

o/⍨- Filter o(das Matrizenarray) nach Wahrheitswerten

Schale , 20 17 Bytes

fȯ=⁰mΣS+Tπ3π3Θḣ▲⁰

-3 Bytes dank @ H.PWiz

Nimmt die Eingabe als Liste xs, die die Einschränkungen codiert [r_1,r_2,r_3,c_1,c_2,c_3], und probiert es online aus!

Erläuterung

Brute-Force-Ansatz: P Generiere alle 3x3-Gitter mit Einträgen [0..max xs]:

f(=⁰mΣS+T)π3π3Θḣ▲⁰  -- input ⁰, for example: [1,1,1,1,1,1]
                ▲⁰  -- max of all constraints: 1
               ḣ    -- range [1..max]: [1]
              Θ     -- prepend 0: [0,1]
            π3      -- 3d cartesian power: [[0,0,0],...,[1,1,1]]
          π3        -- 3d cartesian power: list of all 3x3 matrices with entries [0..max] (too many)
f(       )          -- filter by the following predicate (eg. on [[0,0,1],[1,0,0],[0,1,0]]):
      S+            --   append to itself, itself..: [[0,0,1],[1,0,0],[0,1,0],..
        T           --   .. transposed:             ..[0,1,0],[0,0,1],[1,0,0]]
      mΣ            --   map sum: [1,1,1,1,1,1]
    =⁰              --   is it equal to the input: 1

Brachylog , 17 Bytes

{~⟨ṁ₃{ℕᵐ+}ᵐ²\⟩≜}ᶠ

Probieren Sie es online!

WARNUNG: HÄSSLICHE AUSGABE! Nicht ausflippen, es ist immer noch lesbar, ich muss nicht erklären, wie viel. ;)

Aus irgendeinem Grund muss es viel länger dauern als erwartet (13 Bytes):

⟨ṁ₃{ℕᵐ+}ᵐ²\⟩ᶠ

Diese letztere Version hätte, wenn es funktioniert hätte, stattdessen Eingaben von der Ausgabe (dh Befehlszeilenargument) genommen.

Python 2 , 149 145 142 141 138 136 Bytes

lambda s:[i for i in product(range(max(sum(s,[]))+1),repeat=9)if[map(sum,(i[j:j+3],i[j/3::3]))for j in 0,3,6]==s]
from itertools import*

Probieren Sie es online!

Nimmt Eingaben als Liste von Listen entgegen: [[r1, c1], [r2, c2], [r3, c3]]

Haskell, 94 88 84 79 Bytes

q=mapM id.(<$"abc")
f r=[k|k<-q$q$[0..sum r],(sum<$>k)++foldr1(zipWith(+))k==r]

Nimmt die Summen der Zeilen und Spalten als einzelne flache Liste mit 6 Elementen [r1,r2,r3,c1,c2,c3].

Probieren Sie es online!

q=mapM id.(<$"abc")         -- helper function 

f r =                       -- 
  [k | k <-   ,    ]        -- keep all k
    q$q$[0..sum r]          --   from the list of all possible matrices with
                            --   elements from 0 to the sum of r
                            -- where
    (sum<$>k) ++            --   the list of sums of the rows followed by
    foldr1(zipWith(+))k     --   the list of sums of the columns
    == r                    -- equals the input r

Da die Elemente der zu testenden Matrizen die Summe von erreichen r, endet der Code bei großen Zeilen- / Spaltensummen nicht in angemessener Zeit. Hier ist eine Version, die bis zu dem Maximum rschneller ist, aber 4 Bytes länger: Probieren Sie es online aus!

Mathematica, 81 Bytes

Select[0~Range~Max[s=#,t=#2]~g~3~(g=Tuples)~3,(T=Total)@#==s&&T@Transpose@#==t&]&

findet alle 3x3 Matrizen mit den Elementen 0..Max und wählt die richtigen aus
dies bedeutet, dass (Max+1)^9Matrizen überprüft werden müssen

Probieren Sie es online!

R , 115–110 Bytes

function(S)for(m in unique(combn(rep(0:max(S),9),9,matrix,F,3,3)))if(all(c(rowSums(m),colSums(m))==S))print(m)

Probieren Sie es online!

Nimmt die Eingabe als c(r1,r2,r3,c1,c2,c3)Single vectorund druckt die Matrizen auf Standardausgabe.

Es ist der APL-Antwort von Uriel ziemlich ähnlich, generiert jedoch die 3x3-Gitter etwas anders.

Lässt M=max(S)es den Vektor erzeugen 0:Mund repisst ihn dann neunmal, dh [0..M, 0...M, ..., 0...M]neunmal. Dann werden alle Kombinationen dieses neuen Vektors ausgewählt, die jeweils 9 Mal aufgenommen wurden, wobei matrix, 3, 3jede 9-Kombination in eine 3x3Matrix konvertiert wird und simplify=Feine Liste anstelle eines Arrays zurückgegeben wird. Diese Liste wird dann vereinheitlicht und als gespeichert m.

Dann wird mnach denjenigen gefiltert, bei denen die Zeilen- / Spaltensummen mit der Eingabe identisch sind, und diejenigen gedruckt, die vorhanden sind, und für diejenigen, die nicht vorhanden sind, wird nichts unternommen.

Da es choose(9*(M+1),9)verschiedene mögliche Gitter berechnet (mehr als das(M+1)^9 Möglichkeiten), geht ihm der Speicherplatz / die Zeit schneller aus als die effizientere (aber weniger golfige) Antwort unten:

R , 159 Bytes

function(S,K=t(t(expand.grid(rep(list(0:max(S)),9)))))(m=lapply(1:nrow(K),function(x)matrix(K[x,],3,3)))[sapply(m,function(x)all(c(rowSums(x),colSums(x))==S))]

Probieren Sie es online!

MATL , 35 22 Bytes

-13 Bytes dank Luis Mendo

X>Q:q9Z^!"@3et!hsG=?4M

Probieren Sie es online!

Der Link verweist auf eine Version des Codes, die etwas besser gedruckt wird. Diese Version druckt nur alle Matrizen mit einer einzelnen Zeile dazwischen.

Übernimmt die Eingabe als [c1 c2 c3 r1 r2 r3].

Offensichtlich berechnet dies die kartesische Potenz X^von 0...max(input)Exponent 9und Transponieren !. Anschließend werden "die Spalten durchlaufen und jeweils @als 3x3-Matrix umgeformt 3e, dupliziert t, transponiert !und horizontal verkettet h. Dann berechnet es die Spaltensummen s, die den Vektor ergeben [c1 c2 c3 r1 r2 r3]. Wir führen eine elementweise Gleichheit mit der Eingabe durch G=, und wenn ?alle ungleich Null sind, stellen wir die richtige Matrix wieder her, indem wir die Eingabe für die Funktion !mit auswählen 4M.

Batch, 367 Bytes

@echo off
for /l %%i in (0,1,%1)do for /l %%j in (%%i,1,%1)do for /l %%k in (%%i,1,%4)do call:c %* %%i %%j %%k
exit/b
:c
set/a"a=%1-%8,c=%4-%9,f=%8-%7,g=%9-%7,l=%5-f,m=%2-g,l^=m-l>>31&(m^l),m=%5+c-%3-f,m&=~m>>31
for /l %%l in (%m%,1,%l%)do set/a"b=%2-g-%%l,d=%5-f-%%l,e=%6-a-b"&call:l %7 %%l
exit/b
:l
echo %1 %f% %a%
echo %g% %2 %b%
echo %c% %d% %e%
echo(

Das 2 × 2-Quadrat oben links erzwingt das Ergebnis. Daher ist es am besten, alle Werte für die Ganzzahl oben links, alle gültigen Werte für die Summe der Ganzzahl oben links und oben in der Mitte sowie alle gültigen Werte für die Summe der Ganzzahl oben links zu generieren Ganzzahl links und Mitte links, und berechnen Sie den Bereich der gültigen Werte für die Ganzzahl Mitte. Nachdem Sie alle entsprechenden Bereiche durchlaufen haben, berechnen Sie die verbleibenden Werte aus den Einschränkungen.

Python 2 , 118 Bytes

def f(v,l=[],i=0):n=len(l);V=v*1;V[~n/3]-=i;V[n%3]-=i;return[l][any(V):]if n>8else V*-~min(V)and f(V,l+[i])+f(v,l,i+1)

Probieren Sie es online!

Python 2 , 123 Bytes

V=input()
n=max(V)+1
for k in range(n**9):
 m=[];exec"m+=[k%n,k/n%n,k/n/n%n],;k/=n**3;"*3
 if map(sum,m+zip(*m))==V:print m

Probieren Sie es online!