Matrix-Puzzles

24

Eingang:

  • Eine ganze Zahl n
  • Zwei gleich große quadratische Matrizen (deren Breite / Höhe ein Vielfaches von ist n)

Ausgabe:

Einer von zwei unterschiedlichen Werten Ihrer Wahl, einer für wahrheitsgemäße Ergebnisse und einer für falsche Ergebnisse (also ja, 1/0anstatt true/falsegültige Ausgaben für Sprachen wie Java, auch wenn sie nicht als offizielle Wahrheits / Falsch-Werte betrachtet werden ).

Die Ausgabe von truthy / falsey gibt an, ob wir Blöcke der Größe n by nin einer Matrix neu anordnen können , um sie an die andere Matrix anzupassen .

Beispiel:

Eingang:

Matrix 1:
1 2 3 4 5 6
7 8 9 0 1 2
3 4 5 6 7 8
9 8 7 6 5 4
3 2 1 0 9 8
1 1 1 1 1 1

Matrix 2:
3 2 9 8 7 8
1 1 1 1 5 4
3 4 5 6 1 0
9 0 7 6 1 1
5 6 1 2 3 4
1 2 7 8 9 8

Integer n:
2

Ausgabe: truthy

Warum?

Wenn wir die Matrizen in Blöcke von teilen 2 by 2, können wir sehen, dass sich alle Blöcke einer Matrix auch in der anderen Matrix befinden:

Matrix 1:
1 2 | 3 4 | 5 6
7 8 | 9 0 | 1 2
---------------
3 4 | 5 6 | 7 8
9 8 | 7 6 | 5 4
---------------
3 2 | 1 0 | 9 8
1 1 | 1 1 | 1 1

Matrix 2:
3 2 | 9 8 | 7 8
1 1 | 1 1 | 5 4
---------------
3 4 | 5 6 | 1 0
9 0 | 7 6 | 1 1
---------------
5 6 | 1 2 | 3 4
1 2 | 7 8 | 9 8

Herausforderungsregeln:

  • Sie können davon ausgehen, dass die Matrizen nur nicht negative Ziffern enthalten (Bereich [0,9]).
  • Sie können davon ausgehen, dass die Breite / Höhe der Matrizen gleich ist und ein Vielfaches von n
  • Sie können davon ausgehen, ndass Sie sich im Bereich befinden [1, 50]und die Breite / Höhe der Matrizen im Bereich liegen [1,100].
  • Die einzelnen Blöcke von n by nkönnen nur einmal verwendet werden, um zu bestimmen, ob die Matrizen bei der Aufteilung in Blöcke von Permutationen voneinander sind n by n.
  • Es kann mehrere n by nBlöcke geben, die gleich sind.
  • Die n by nBlöcke bleiben in der gleichen Ausrichtung, wenn geprüft wird, ob die beiden Matrizen bei der Aufteilung in Blöcke von einander permutieren n by n.

Allgemeine Regeln:

  • Das ist , also gewinnt die kürzeste Antwort in Bytes.
    Lassen Sie sich von Code-Golf-Sprachen nicht davon abhalten, Antworten mit Nicht-Codegolf-Sprachen zu veröffentlichen. Versuchen Sie, für jede Programmiersprache eine möglichst kurze Antwort zu finden.
  • Für Ihre Antwort gelten Standardregeln mit Standard-E / A-Regeln. Daher dürfen Sie STDIN / STDOUT, Funktionen / Methoden mit den richtigen Parametern und vollständige Programme vom Rückgabetyp, verwenden. Ihr Anruf.
  • Standardlücken sind verboten.
  • Fügen Sie nach Möglichkeit einen Link mit einem Test für Ihren Code hinzu (z. B. TIO ).
  • Außerdem wird dringend empfohlen, eine Erklärung für Ihre Antwort hinzuzufügen.

Testfälle:

Input:
Matrix 1:       Matrix 2:       Integer:
1 2 3 4 5 6     3 2 9 8 7 8     2
7 8 9 0 1 2     1 1 1 1 5 4
3 4 5 6 7 8     3 4 5 6 1 0
9 8 7 6 5 4     9 0 7 6 1 1
3 2 1 0 9 8     5 6 1 2 3 4
1 1 1 1 1 1     1 2 7 8 9 8
Output:
truthy

Input:
Matrix 1:       Matrix 2:       Integer:
1 2 3 4 5 6     3 2 9 8 7 8     1
7 8 9 0 1 2     1 1 1 1 5 4
3 4 5 6 7 8     3 4 5 6 1 0
9 8 7 6 5 4     9 0 7 6 1 1
3 2 1 0 9 8     5 6 1 2 3 4
1 1 1 1 1 1     1 2 7 8 9 8
Output:
truthy

Input:
Matrix 1:       Matrix 2:       Integer:
1 2 3 4 5 6     3 2 9 8 7 8     3
7 8 9 0 1 2     1 1 1 1 5 4
3 4 5 6 7 8     3 4 5 6 1 0
9 8 7 6 5 4     9 0 7 6 1 1
3 2 1 0 9 8     5 6 1 2 3 4
1 1 1 1 1 1     1 2 7 8 9 8
Output:
falsey

Input:
Matrix 1:    Matrix 2:    Integer:
1 2 3 4      1 2 3 4      4
2 3 4 5      2 3 4 5
3 4 5 6      3 4 5 6
4 5 6 7      4 5 6 7
Output:
truthy

Input:
Matrix 1:    Matrix 2:    Integer:
1 2 3 4      3 4 3 4      2
2 3 4 5      4 5 4 5
3 4 5 6      1 2 5 6
4 5 6 7      2 3 6 6
Output:
falsey

Input:
Matrix 1:    Matrix 2:    Integer:
1 2          2 3          1
3 4          1 1
Output:
falsey

Input:
Matrix 1:    Matrix 2:    Integer:
0            8            1
Output:
falsey

Input:
Matrix 1:    Matrix 2:    Integer:
1 2 3 4      1 2 1 2      2
5 6 7 8      5 6 5 6
9 0 0 9      0 9 9 0
4 3 2 1      2 1 4 3
Output:
falsey

Input:
Matrix 1:    Matrix 2:    Integer:
1 2 1 2      9 5 1 2      2
3 4 3 4      7 7 3 4
8 3 9 5      1 2 8 3
6 1 7 7      3 4 6 1
Output:
truthy

Input:
Matrix 1:      Matrix 2:      Integer:
1 0 2 0 0 3    1 1 1 0 0 3    2
1 1 1 1 1 1    2 0 1 1 1 1
2 2 2 2 2 2    2 2 2 2 2 2
3 3 3 3 3 3    3 3 3 3 3 3
4 4 4 4 4 4    4 4 4 4 4 4
5 5 5 5 5 5    5 5 5 5 5 5
Output:
falsey

Pastebin mit Matrizen im [[,]]Format.

Kevin Cruijssen
quelle
Können wir die Matrizen als Liste von Matrizen nehmen?
Jo King
@JoKing Du meinst eine Liste mit beiden Matrizen anstelle von zwei getrennten Matrix-Eingängen? Wenn Sie danach fragen, warum nicht?
Kevin Cruijssen
Warum ist das Beispiel [ [ 0 ] ], [ [ 25 ] ], 1vorhanden? Ich habe damit verstanden, You can assume the matrices will only contain non-negative digits (range [0,9])dass die Matrixwerte nur zwischen 0 und 9 liegen?
Olivier Grégoire
2
@ OlivierGrégoire Sorry, diese Regel über die Reichweite [0,9]später in der Sandbox hinzugefügt . Ich habe den Testfall auf geändert [[0]],[[8]].
Kevin Cruijssen

Antworten:

4

Gelee ,  10  9 Bytes

ż⁹/ẎsṢʋ€E

Probieren Sie es online! (oder mit Vorverarbeitung zum leichteren Kopieren und Einfügen aus den Testfällen)

Ein dyadischer Link, der eine Liste der beiden Matrizen (als Listen von Listen) auf der linken Seite und die ganze Zahl auf der rechten Seite akzeptiert, die 1oder 0für Wahrheit oder Falschheit ergibt.

Wie?

ż⁹/ẎsṢʋ€E - Link: [M1, M2]; N
       €  - for each of [M1, M2]:
      ʋ   -   last four links as a dyad (i.e. f(M, N)):
 ⁹        -     (chain's right argument, N)
 ⁹/       -     N-wise-reduce with:
ż         -       zip together
   Ẏ      -     tighten
    s     -     split into chunks of length N
     Ṣ    -     sort
        E - equal?
Jonathan Allan
quelle
8

APL (Dyalog Extended) , 19 18 17 Bytes

-2 danke an ngn.

Anonyme stillschweigende Infix-Funktion. Nimmt nals linkes Argument und Liste von zwei Matrizen als rechtes Argument. Erfordert die Indizierung von Nullen ( ⎕IO←0). Im Übrigen funktioniert diese Funktion bei Arrays mit einer beliebigen Anzahl von Dimensionen.

≡.{∧,⍵⊂⍨⊂0=⍺|⍳≢⍵}

Probieren Sie es online!

≡.{} Identische Ergebnisse der folgenden Funktion auf jede Matrix angewendet mit nals ?

≢⍵ Größe der Matrix

 Indizes 0… Größe – 1

⍺| Divisionsrest bei Division durch n

 beilegen, um entlang aller Maße zu verwenden

⍵⊂⍨ Verwenden Sie dies, um * die Matrix in eine Matrix von Untermatrizen zu unterteilen.
  * Beginnt eine neue Partition, wenn das entsprechende Element kleiner als das vorherige ist. Entfernt mit Null markierte Elemente

, zerlegen Sie die Matrix in eine Liste von Submatrizen

 aufsteigend sortieren

Adam
quelle
(≢⍵)⍴⍺↑1-> 0=⍺|⍳≢⍵(mit ⎕io←0)
ngn
@ngn Danke. Getan.
Adám
≡/{}¨->≡.{}
31.
@ngn Fertig. Vielen Dank.
Adám,
6

Perl 6 , 94 68 63 Bytes

{[eqv] map *.rotor($^a).map({[Z] $_}).flat.rotor($a²).sort,@_}

Probieren Sie es online!

Anonymer Codeblock, der Eingaben als size, [matrix1, matrix2]akzeptiert und einen Booleschen Wert zurückgibt True/False. Es gibt möglicherweise eine effizientere Methode zum Aufteilen der Matrix in Blöcke als rotor.

Erläuterung:

{                                                            }  # Anonymous code block
       map                                                ,@_   # For both matrices 
           *.rotor($^a)   # Split the matrix into N sized chunks
                       .map({[Z] $_})  # Then zip each of those chunks together
                                     .flat  # Flatten the resulting list
                                          .rotor($a²)  # Then split into the NxN lists
                                                     .sort   # And sort them
 [eqv]    # And then check if the lists are equivalent 
Scherzen
quelle
4

Java (JDK) , 221 Byte

(n,a,b)->{java.util.Arrays A=null;int l=a.length,x=l/n,i=0,j,z;var c=new String[x*x];A.fill(c,"");var d=c.clone();for(;i<l;i++)for(j=0;j<l;d[z]+=b[i][j++])c[z=i/n+j/n*x]+=a[i][j];A.sort(c);A.sort(d);return A.equals(c,d);}

Probieren Sie es online!

Erläuterung

Die Idee ist, jede kleine Zelle als vergleichbare Zeichenfolge auszuwählen und diese Zeichenfolgen dann zu sortieren und nacheinander zu vergleichen.

(n,a,b)->{
 java.util.Arrays A=null;             // Shortcut A for the several java.util.Arrays that'll come
 int l=a.length,x=l/n,i=0,j,z;        // Variable declarations
 var c=new String[x*x];               // Declare the small squares list
 A.fill(c,"");                        // Fill the lists of small squares with the empty string.
 var d=c.clone();                     // Make a copy of the list, for the second matrix
 for(;i<l;i++)
  for(j=0;j<l;d[z]+=b[i][j++])        // For each matrix cell
   c[z=i/n+j/n*x]+=a[i][j];           // Fill the small square with the value, string-wise
 A.sort(c);A.sort(d);                 // Sort both small squares list
 return A.equals(c,d);                // Return true if they're equal, false otherwise.
}

Credits

  • -12 Bytes dank Kevin Cruijssen!
Olivier Grégoire
quelle
Haben Sie das Golfen vergessen for(j=0;j<l;){c[z=i/n+j/n*x]+=a[i][j];d[z]+=b[i][j++];}? .. Sie können die Klammern entfernen, indem Sie alles in die Schlaufe stecken. Auch der i=0in der Schleife befindliche kann entfernt werden, da Ihr ibei Deklaration bereits 0 ist.
Kevin Cruijssen
Und eine Sache, um tatsächlich Golf zu spielen: var d=new String[x*x];kann var d=c.clone();stattdessen sein. 234 Bytes
Kevin Cruijssen
PS: Warum enthält Ihr TIO String, den Sie in 2D-Integer-Arrays konvertieren? Ich habe einen Einfügebehälter mit den Testfällen am unteren Rand hinzugefügt, für den Sie das [und ]durch {und ersetzen }und ein führendes hinzufügen können new int[][], und es wäre genug gewesen. ;)
Kevin Cruijssen
Verdammt, ich hatte den Mülleimer nicht gesehen :( Und im Übrigen spiele ich immer noch Golf. Ich habe einen harten Pass gespielt, aber danke :-)
Olivier Grégoire
Das i=0war ein Überbleibsel, als ich die Arrays selbst füllte, anstatt sie zu benutzen Arrays.fill. Danke :-) Und für das habe cloneich darüber nachgedacht, aber ich dachte immer noch, es hätte einen Objectund nicht den tatsächlichen Typ zurückgegeben. Ich muss in diesem Punkt einige Versionen zu spät sein;)
Olivier Grégoire
4

Japt , 18 Bytes

®mòV yòV rc n qÃr¥

Probieren Sie es online!

Erläuterung:

®              Ã      #Apply this to each of the input matrices:
 mòV                  # Split each row into groups of n
     yòV              # Split each column into groups of n
         rc           # Flatten into a list of nxn submatrices
            n         # Sort that list
              q       # Turn it into a string
                r¥    #Return true if both matrices had identical results

Der Schritt "In einen String verwandeln" ist erforderlich, da Japt Arrays nicht nach Wert vergleicht und das eingebaute Problem, das umgeht, für mehrdimensionale Arrays nicht funktioniert .

Kamil Drakari
quelle
2
Ich werde sehen, ob ich morgen zwischen den Besprechungen etwas Zeit habe, um zu versuchen, A.e()für mehrdimensionale Arrays zu arbeiten. wollte immer darauf zurückkommen. In der Zwischenzeit ÕmòV-> yòVspart Ihnen ein Byte.
Shaggy
Übrigens ist die Einschränkung beim Vergleichen von Arrays auf Gleichheit eher JavaScript als Japt-spezifisch;)
Shaggy
4

TSQL, 164 Bytes

Das Auffüllen einer Tabellenvariablen, um eine Eingabe zu erhalten, das Erstellen von Eingaben und das Einfügen von Daten wurde nicht in die Byteanzahl einbezogen. Nur die eigentliche Abfrage, um die Daten zu extrahieren.

Golf (ohne Testtabelle - in der ungolfed Version):

SELECT iif(exists(SELECT*FROM(SELECT string_agg(v,'')within
group(order by x,y)s,m FROM @t GROUP BY x/@,y/@,m)x
GROUP BY s HAVING max(m)=min(m)or sum(m-.5)<>0),0,1)

Ungolfed:

-- test data
DECLARE @ INT = 2
-- x = x-position of the input
-- y = y-position of the input
-- v = value
-- m = matrix(0 or 1)
DECLARE @t table(x int, y int, v int, m int)
--insert first matrix values
INSERT @t values
(0,0,1,0),(0,1,2,0),(0,2,1,0),(0,3,2,0),
(1,0,3,0),(1,1,4,0),(1,2,3,0),(1,3,4,0),
(2,0,8,0),(2,1,3,0),(2,2,9,0),(2,3,5,0),
(3,0,6,0),(3,1,1,0),(3,2,7,0),(3,3,7,0)
INSERT @t values
(0,0,9,1),(0,1,5,1),(0,2,1,1),(0,3,2,1),
(1,0,7,1),(1,1,7,1),(1,2,3,1),(1,3,4,1),
(2,0,1,1),(2,1,2,1),(2,2,8,1),(2,3,3,1),
(3,0,3,1),(3,1,4,1),(3,2,6,1),(3,3,1,1)

-- query
SELECT iif(exists
  (
    SELECT *
    FROM
    (
      SELECT string_agg(v,'')within group(order by x,y)s,m
      FROM @t
      GROUP BY x/@,y/@,m
    ) x
    GROUP BY s
    HAVING max(m)=min(m)or sum(m-.5)<>0
  ),0,1)

Versuch es

t-clausen.dk
quelle
4

JavaScript (ES6), 88 Byte

(n,a,b)=>(g=a=>a.map((r,y)=>r.map((v,x)=>o[y/n<<7|x/n]+=[v]),o=[])&&o.sort()+o)(a)==g(b)

Probieren Sie es online!

Wie?

Dieser Code lautet:

  • Extrahieren aller Untermatrizen in jeder Eingabematrix als Verkettung von Zellen
  • Sortieren der Untermatrizen in lexikographischer Reihenfolge
  • Testen, ob das Ergebnis für beide Eingabematrizen gleich ist

Es nutzt die in der Herausforderung beschriebenen Grenzen:

  • Eine Matrix besteht aus einzelnen Ziffern, so dass wir einfach alle Zellen einer Untermatrix ohne Trennzeichen verketten und trotzdem eine eindeutige Darstellung davon erhalten können (z. B. [[1,2],[3,4]]kann gespeichert werden als"1234" ).

  • 100(x,y)ich

    ich=yn×128+xn

    oder als JS-Code: y / n << 7 | x << n

Kommentiert

(n, a, b) =>           // n, a, b = input variables (integer, matrix 1, matrix 2)
  (g = a =>            // g = helper function taking one of the two matrices
    a.map((r, y) =>    // for each row r[] at position y in a[]:
      r.map((v, x) =>  //   for each value v at position x in r[]:
        o[             //     update o[]:
          y / n << 7 | //       the position of the slot is computed by taking advantage
          x / n        //       of the limit on the matrix width (see above)
        ] += [v]       //     coerce v to a string and append it to o[slot]
                       //     all slots are initially undefined, so all resulting strings
                       //     are going to start with "undefined", which is harmless
      ),               //   end of inner map()
      o = []           //   start with o = empty array
    ) &&               // end of outer map()
    o.sort() + o       // sort o[] and coerce it to a string by concatenating it with itself
  )(a) == g(b)         // test whether g(a) is equal to g(b)
Arnauld
quelle
3

Kohle , 54 49 Bytes

1FθF⪪ιηF÷L§κ⁰η⊞υEκ§⪪μηλW∧υ⊟υ¿№✂υ⁰⊘⊕Lυ¹ι≔Φυ⁻⌕υιλυ⎚

Probieren Sie es online! Link ist eine ausführliche Version des Codes. Nimmt die Eingabe als Array von gleich großen zweidimensionalen Arrays. Gibt 1 bei Erfolg aus, nichts bei Misserfolg. Erläuterung:

1

Erfolg voraussetzen.

Fθ

Schleife über die Arrays.

F⪪ιη

Teilen Sie das Array in große nZeilenabschnitte auf.

F÷L§κ⁰η

Schleife über jeden Spaltenblock.

⊞υEκ§⪪μηλ

Extrahieren Sie den Spaltenblock für jede Zeile des Zeilenblocks und speichern Sie die resultierende Untermatrix in einer Liste.

W∧υ⊟υ

Entfernen Sie den letzten Teil der Liste, der unter normalen Umständen aus dem zweiten Array stammt, während die Liste nicht leer ist.

¿№✂υ⁰⊘⊕Lυ¹ι

Zählen Sie die Anzahl der Vorkommen dieses Blocks in der ersten Hälfte der Liste, die unter normalen Umständen die verbleibenden Blöcke aus dem ersten Array enthält.

≔Φυ⁻⌕υιλυ

Wenn der Wert nicht Null ist, entfernen Sie das erste Vorkommen dieses Blocks aus der Liste.

Wenn Null, dann lösche die Ausgabe und mache sie falsch.

Neil
quelle
2

J , 55 Bytes

[:-:/[([:/:~([*-@[)]\,@])"3(((;])@(#@]$1{.~[),;.1])&>])

Probieren Sie es online!

Eine schreckliche Lösung, die einfach funktioniert hat - ich kann nicht Golf spielen ...

Galen Ivanov
quelle
2

Haskell, 74 73 Bytes

import Data.Lists
i#m|c<-chunksOf i=c.transpose=<<c m
(m!n)i=i#m\\i#n==[]

Hinweis: TIO wurde nicht installiert Data.Lists, daher verwende ich Data.Liststattdessen eine Funktion, die fehlt chunksOf: Probieren Sie es online aus!

i#m=           -- function '#' makes a list of all transposed jigsaw blocks of matrix 'm'
               -- of size 'i'
 c<-chunksOf i -- define helper function 'c' that splits it's argument into
               -- chunks of site 'i'
         c m   -- split the matrix into chunks of size 'i'
      =<<      -- for each chunk
   transpose   --   transpose
 c.            --   and split into chunks of size 'i', again
               -- flatten one level of nesting ('=<<' is concatMap)

(m!n)i=        -- main function
    i#m\\i#n   -- remove every element of i#n from i#m
      ==[]     -- and check if it results in an empty list  
nimi
quelle
2

C # (Visual C # Interactive Compiler) , 186 Byte

(a,b,n)=>{string[]s(int[][]c){int i=0,j,l=a.Length,m=l/n;var r=new string[m*m];for(;i<l;i++)for(j=0;j<l;)r[i/n*m+j/n]+=c[i][j++];Array.Sort(r);return r;}return s(a).SequenceEqual(s(b));}

Probieren Sie es online!

-1 danke an @KevinCruijssen!

Weniger Golf Code:

// anonymous function
// a and b are 2d jagged arrays
// n is the size of the sub matrix
(a,b,n)=>{
  // helper function that translates
  // the sub matrices into strings
  // of digits.
  string[]s(int[][]c){
    // i and j are loop counters
    int i=0,j,
      // l is the size of a side of a matrix
      l=a.Length,
      // m is the number of sub matrices
      // per side of a matrix
      m=l/n;
    // the concatenated digits are
    // stored in a single dimension
    // array
    var r=new string[m*m];
    // nested loops build up
    // the digit strings
    for(;i<l;i++)
      for(j=0;j<l;)
        r[i/n*m+j/n]+=c[i][j++];
    // The resulting array is
    // sorted before it is returned for
    // ease of comparison.
    Array.Sort(r);
    return r;
  }
  return s(a).SequenceEqual(s(b));
}
Dana
quelle
Eine Kleinigkeit zum Golfspielen, die j++entfernt und platziert werden kann +=c[i][j++]+" ";, um ein Byte zu sparen.
Kevin Cruijssen
Vielen Dank für den Tipp :) Interessanterweise habe ich fast die gleiche Lösung wie die Java-Lösung gefunden.
Dana
1

PHP ,186 163 162 Bytes

function($a,$b,$n){$f=function($j,$n){foreach($j as$x=>$r)foreach($r as$y=>$v)$o[count($j)*($x/$n|0)+$y/$n|0].=$v;sort($o);return$o;};return$f($a,$n)==$f($b,$n);}

Probieren Sie es online!

Wie bei allen guten Herausforderungen dachte ich, dass dies ziemlich einfach ist und es hat mich ein paar Kurven geworfen. Schön gemacht @Kevin Cruijssen!

Unterteilt die Matrix in Zeichenfolgen, die die Werte für jeden Block enthalten. Die Arrays werden dann sortiert und auf Gleichheit verglichen.

Ungolfed:

function jigsaw_chunk( $j, $n ) {
    foreach( $j as $x => $r ) {
        foreach( $r as $y => $v ) {
            $o[ count( $j ) * floor( $x/$n ) + floor( $y/$n )] .= $v;
        }
    }
    sort( $o );
    return $o;
}

function jigsaw_test( $a, $b, $n ) {
    return jigsaw_chunk( $a, $n ) == jigsaw_chunk( $b, $n );
}

// Test 6
var_dump( jigsaw_test( [[1,2],[3,4]], [[2,3],[1,1]], 1 ) );

Ausgabe

bool(false)
640 KB
quelle
1

Rot , 148 147 142 Bytes

func[a b n][g: func[m][
sort collect[loop k:(length? m)/ n[i: 0
loop k[keep/only
collect[loop n[keep
take/part m/(i: i + 1) n]]]]]](g a)= g b]

Probieren Sie es online!

Galen Ivanov
quelle