Teilen Sie ein Raster in ein Raster

22

Einführung

Es gibt ein kleines Dorf mit nur ein paar Häusern und leeren Feldern. Die örtlichen Bürokraten wollen das Dorf in Grundstücke aufteilen, so dass jedes Grundstück genau ein Haus enthält und die Grundstücksgrenzen ein schönes, geradliniges Raster bilden. Ihre Aufgabe ist es festzustellen, ob dies möglich ist.

Die Aufgabe

Ihre Eingabe ist ein rechteckiges 2D-Array von Bits. 1 steht für ein Haus und 0 für ein leeres Feld. Ihre Größe beträgt mindestens 1 × 1 und sie enthält mindestens eine 1. Sie können die Eingabe in jedem vernünftigen Format vornehmen (verschachtelte Liste von Ganzzahlen, Liste von Zeichenfolgen, mehrzeilige Zeichenfolge usw.).

Ihr Programm muss bestimmen, ob das Array mithilfe von geraden horizontalen und vertikalen Linien in Gitterzellen unterteilt werden kann, sodass jede Gitterzelle genau eine 1 enthält. Die Gitterzellen können unterschiedliche Größen und Formen haben, obwohl sie immer rechteckig sind. Die Linien müssen von einer Kante des Arrays zur gegenüberliegenden Kante verlaufen.

Das Folgende ist beispielsweise eine gültige Aufteilung eines Arrays:

00|0010|01|1
01|0000|00|0
--+----+--+-
00|0000|00|1
01|0010|01|0
--+----+--+-
01|1000|10|1

Die folgende Unterteilung ist ungültig, da es Gitterzellen mit keiner 1 oder mehr als einer 1 gibt:

00|0010|01|1
--+----+--+-
01|0000|00|0
00|0000|00|1
01|0010|01|0
--+----+--+-
00|1000|10|1

Wenn eine gültige Unterteilung vorliegt, geben Sie einen Wahrheitswert und ansonsten einen falschen Wert aus.

Regeln und Wertung

Sie können ein vollständiges Programm oder eine Funktion schreiben. Die niedrigste Byteanzahl gewinnt.

Testfälle

[[1]] -> True
[[0,1],[1,0]] -> True
[[1,1],[1,0]] -> False
[[1,0,1],[0,1,0]] -> True
[[1,0],[0,1],[0,1]] -> True
[[1,0,0],[0,0,1],[0,1,1]] -> True
[[1,1,1],[1,1,1],[1,1,1]] -> True
[[1,0,1],[0,1,0],[1,0,0]] -> True
[[1,0,0],[1,0,0],[0,1,1]] -> False
[[0,0,0,0,1],[1,0,0,1,0],[0,0,0,1,0]] -> False
[[0,0,1,0,1],[0,0,0,1,0],[0,0,0,0,0]] -> True
[[1,1,0,0,0],[0,0,0,0,0],[1,0,1,0,0]] -> True
[[1,1,0,1,1],[0,1,0,1,1],[1,0,0,0,0]] -> True
[[0,0,0,0,0,0,0],[0,1,1,1,0,1,0],[0,1,0,0,1,0,0],[0,0,0,0,0,0,1],[0,0,1,0,0,0,1],[1,1,0,1,1,0,0]] -> False
[[1,1,0,0,0,0,0],[1,0,1,1,0,1,0],[0,0,0,0,1,0,0],[0,1,0,1,1,0,0],[1,0,0,0,1,1,0],[0,0,0,0,0,1,0]] -> False
[[0,1,0,1,1,1,0],[0,0,0,0,1,0,0],[0,0,0,0,0,0,0],[1,0,0,1,0,0,0],[0,0,0,0,0,0,0],[0,0,0,0,0,0,1]] -> True
[[0,1,0,0,1,0,1],[1,0,0,0,1,0,1],[0,0,1,0,1,0,1],[1,0,0,0,1,1,0],[0,0,0,1,1,1,0],[0,1,0,0,1,0,1]] -> True
[[0,1,0,0,1,0,0,1,0],[0,0,0,0,1,1,0,1,0],[1,1,0,0,1,0,0,0,0],[0,0,1,0,1,0,1,0,0],[0,0,1,0,1,0,1,0,0],[0,1,0,0,0,1,0,0,1],[0,1,0,0,0,0,1,0,0]] -> False
[[1,0,1,0,0,1,1,0,1],[0,1,1,0,0,1,1,0,1],[1,0,0,0,0,1,0,0,0],[0,0,0,0,0,0,0,0,0],[0,0,1,0,0,0,0,1,1],[0,1,1,0,1,0,1,0,1],[1,0,1,0,0,1,1,0,1]] -> True
Zgarb
quelle
kann [[0,0,1,0,1], [1,0,0,1,0], [0,0,0,1,0]] unterteilt werden in: 3X1, 2X1, 3X2, 2X1, 2X1 Rechtecke auf diese Weise oder nicht? 001 | 01 --- + - 100 | 10 + - 000 | 10
officialaimm
4
@officialaimm Nein, das ist nicht gültig. Die Gitterlinien müssen von einer Seite des Arrays bis zur anderen Seite verlaufen.
Zgarb,
Vorgeschlagener Testfall: [[1, 0, 1], [0, 1, 0], [1, 0, 0]]Das war die einzige 3x3-Matrix, bei der mein neuer Ansatz versagte.
Dennis
@ Tennis Danke, fügte hinzu.
Zgarb

Antworten:

7

Pyth, 30 29 26 24 23 Bytes

sm.Asmmq1ssbCkds./MC./M

Probieren Sie es online aus.

Ich bin sicher, das wird kürzer. Das ist O (2 Min. ) , Wobei m und n die Breite und Höhe des Arrays sind, aber die letzten beiden Testfälle auf meinem Laptop mit Akku (i5-5200U mit eingeschränkter Leistung) in 45 Sekunden abgeschlossen sind.

Gibt die Anzahl der Lösungen aus.

Erläuterung

Die Arbeit mit fünfdimensionalen Arrays macht wirklich Spaß. </ sarcasm> Sie sollten nicht verstehen, wie das auch mit der Erklärung funktioniert.

                    ./M    Find all partitions of each row. Now we have a list of rows,
                           each containing the ways to split the row, each containing
                           the parts of the split (3D).
                   C       Transpose. Now we have a list of ways to split the columns,
                           each containing the rows, each containing the parts of the
                           row (3D).
                ./M        Find all partitions of each row list. Now we have a list of
                           ways to split the columns, each containing the ways to split
                           the rows, each containing the bunch of rows, each containing 
                           the rows in the bunch, each containing the parts of the row
                           (6D).
               s           Combine the ways to split rows & columns into one array (5D).
 m            d            Do the following for each way to split rows & columns (4D):
     m       k                 Do the following for each bunch of rows (3D):
            C                      Transpose the array. We now have a list of column
                                   groups, each containing the row parts (3D).
      m    b                       Do the following for each column group (2D):
          s                            Combine the row parts in the column group. We now
                                       have the list of cells in this row/column group
                                       (1D).
         s                             Sum the cells.
       q1                              Check if the sum is one.
                                   We now have the list of booleans that tell if each
                                   row/column group is valid (1D).
                               We now have the 2D list of booleans that tell if each
                               row/column group in each bunch of rows is valid. (2D)
    s                          Combine the 2D list of booleans to 1D.
  .A                           Check if all values are truthy; if the split is valid.
                           We now have the validity of each split.
s                          Sum the list to get the number of valid solutions.
PurkkaKoodari
quelle
2

Haskell , 116 Bytes

import Data.List
m(a:b)=[a:e|e<-m b]++[zipWith(+)a d:e|d:e<-m b];m e=[e]
d=(any$any$all$all(==1)).map(m.transpose).m

Probieren Sie es online!

Roman Czyborra
quelle
1
Dies wird nicht kompiliert. Bitte löschen Sie Ihre Antwort, bis sie behoben ist. Es gibt auch viel Golfpotential, z. Umbenennung mergerowsin m.
Laikoni
Ich hatte vor, wegen der unschlagbaren Pyth-Kürze keine Konkurrenz mehr zu haben, und danke dir @Laikoni, dass du gesehen hast, dass ich wahrscheinlich meine Einrückungsklammern durcheinander gebracht habe.
Roman Czyborra
2
Dies gibt fälschlicherweise False an [[1,0],[0,1],[1,0]]. Das Problem ist, dass ein gieriger Zusammenbruch einem späteren besseren Zusammenbruch im Wege stehen kann.
xnor
In der Tat [[1,1],[1,0]]behindert mein Zusammenbruch fälschlicherweise die[[1],[1],[1]] Lösung. Lass mich darüber schlafen oder soll ich es löschen?
Roman Czyborra
1

Gelee , 20 Bytes

ŒṖS€€ỊȦ$ÐfZ€µ⁺€Ȧ€€FS

Dies ist immer noch eine Brute-Force-Lösung, aber sie ist viel schneller als meine andere Antwort - die die letzten beiden Testfälle auf TIO nicht bewältigen kann - und bearbeitet alle Testfälle in ~ 4 Sekunden.

Probieren Sie es online!

Wie es funktioniert

ŒṖS€€ỊȦ$ÐfZ€µ⁺€Ȧ€€FS  Main link. Argument: M (matrix, array of rows)

ŒṖ                    Compute all partitions, i.e., all groupings of M's rows.
  S€€                 Map sum over all individual groupings, collapsing the grouped
                      rows into a single row.
        Ðf            Filter; keep only those partially collapsed matrices for
                      which the link to the left returns a truthy value.
       $                Group the two links to the left into a monadic chain.
     Ị                    Insignificant; map 0 and 1 to 1, greater integers to 0.
      Ȧ                   All; return 1 iff the matrix contains no zeroes.
          Z€          Zip/transpose all kept matrices,
            µ         Combine all links to the left into a monadic chain.
             ⁺€       Duplicate the chain and map it over the individual results
                      from the first call. We now have all possible combinations
                      of row and column groupings (represented by the corresponding
                      matrices of collapsed rows and columns) that do not have a
                      2 anywhere. However, they still may contain zeroes.
               Ȧ€€    Map the all atom over the matrices, returning 1 only for
                      matrices that consist entirely of ones.
                  FS  Flatten and sum, counting the number of valid divisions.
Dennis
quelle