Matrix quebra-cabeças

24

Entrada:

  • Um inteiro n
  • Duas matrizes quadradas de tamanho igual (com sua largura / altura sendo um múltiplo de n)

Saída:

Um dos dois valores distintos de sua própria escolha, um para resultados de verdade e outro para resultados de falsey (então sim, em 1/0vez de true/falsesão saídas válidas para linguagens como Java, mesmo que não sejam considerados valores oficiais de truthy / falsey ).

A saída truthy / falsey indica se podemos reorganizar blocos de tamanho n by nem uma matriz para torná-lo igual à outra matriz.

Exemplo:

Entrada:

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

Saída: truthy

Por quê?

Se dividirmos as matrizes em blocos de 2 by 2, podemos ver que todos os blocos em uma matriz também podem ser encontrados na outra matriz:

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

Regras do desafio:

  • Você pode assumir que as matrizes conterão apenas dígitos não negativos (intervalo [0,9])
  • Você pode assumir que a largura / altura das matrizes são iguais e um múltiplo de n
  • Você pode assumir nque estará no intervalo [1, 50], e a largura / altura das matrizes estão no intervalo [1,100].
  • Os blocos individuais de n by npodem ser usados ​​apenas uma vez para determinar se as matrizes são permutações uma da outra quando divididas em blocos de n by n.
  • Pode haver vários n by nblocos iguais.
  • Os n by nblocos permanecerão na mesma orientação ao verificar se as duas matrizes são permutadas uma da outra quando divididas em blocos de n by n.

Regras gerais:

  • Isso é , então a resposta mais curta em bytes vence.
    Não permita que idiomas com código de golfe o desencorajem a postar respostas com idiomas que não sejam codegolf. Tente encontrar uma resposta o mais curta possível para 'qualquer' linguagem de programação.
  • As regras padrão se aplicam à sua resposta com as regras de E / S padrão , para que você possa usar STDIN / STDOUT, funções / método com os parâmetros adequados e programas completos do tipo retorno. Sua chamada.
  • As brechas padrão são proibidas.
  • Se possível, adicione um link com um teste para o seu código (ou seja, TIO ).
  • Além disso, é altamente recomendável adicionar uma explicação para sua resposta.

Casos de teste:

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 com matrizes em [[,]]formato.

Kevin Cruijssen
fonte
Podemos tomar as matrizes como uma lista de matrizes?
Jo King
@JoKing Você quer dizer uma lista com ambas as matrizes em vez de duas entradas de matriz separadas? Se é isso que você está perguntando, então por que não.
Kevin Cruijssen 14/01
Por que o exemplo está [ [ 0 ] ], [ [ 25 ] ], 1presente? Eu entendi com You can assume the matrices will only contain non-negative digits (range [0,9])isso que os valores da matriz são apenas entre 0 e 9?
Olivier Grégoire
2
@ OlivierGrégoire Desculpe, adicionou essa regra sobre o alcance [0,9]mais tarde na Sandbox. Eu mudei o caso de teste para [[0]],[[8]].
Kevin Cruijssen 14/01

Respostas:

4

Geléia ,  10  9 bytes

ż⁹/ẎsṢʋ€E

Experimente online! (ou com pré-processamento para copiar e colar mais facilmente dos casos de teste)

Um link diádico que aceita uma lista das duas matrizes (como listas de listas) à esquerda e o inteiro à direita que produz 1ou 0para verdade ou falsidade, respectivamente.

Quão?

ż⁹/Ẏ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
fonte
8

APL (Dyalog Extended) , 19 18 17 bytes

-2 graças a ngn.

Função de infixo tácito anônimo. Toma ncomo argumento à esquerda e lista de duas matrizes como argumento à direita. Requer indexação zero ( ⎕IO←0). Aliás, essa função funciona em matrizes de qualquer número de dimensões.

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

Experimente online!

≡.{} Resultados idênticos da seguinte função aplicada a cada matriz com nas ?

≢⍵ tamanho da matriz

 índices 0… tamanho – 1

⍺| restante divisão quando dividido por n

 coloque para usar em todas as dimensões

⍵⊂⍨ use isso para particionar * a matriz em uma matriz de submatricias
  * inicia uma nova partição quando o elemento correspondente for menor que o anterior; remove os elementos marcados com zero

, misturar a matriz em uma lista de submatrizes

 ordernar ascendente

Adão
fonte
(≢⍵)⍴⍺↑1-> 0=⍺|⍳≢⍵(with ⎕io←0)
ngn 14/01
@ngn Obrigado. Feito.
Adám 14/01
≡/{}¨->≡.{}
ngn 31/01
@ngn Feito. Obrigado.
Adám 31/01
6

Python 2 , 108 103 bytes

lambda s,*a:len(set(`sorted(sum([zip(*[iter(zip(*l))]*s)for l in zip(*[iter(m)]*s)],[]))`for m in a))<2

Experimente online!

TFeld
fonte
6

Perl 6 , 94 68 63 bytes

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

Experimente online!

Bloco de código anônimo que recebe entrada como size, [matrix1, matrix2]e retorna um booleano True/False. Pode haver uma maneira mais eficiente de dividir a matriz em pedaços do que rotor.

Explicação:

{                                                            }  # 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 
Brincadeira
fonte
4

Java (JDK) , 221 bytes

(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);}

Experimente online!

Explicação

A idéia é escolher cada célula pequena como uma string, o que é comparável e, em seguida, classificá-las e compará-las em ordem.

(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.
}

Créditos

  • -12 bytes graças a Kevin Cruijssen!
Olivier Grégoire
fonte
Você esqueceu de jogar golfe for(j=0;j<l;){c[z=i/n+j/n*x]+=a[i][j];d[z]+=b[i][j++];}? .. Você pode remover os suportes colocando tudo dentro do loop. Além disso, o i=0no loop pode ser removido, porque você ijá é 0 na declaração.
Kevin Cruijssen 14/01
E uma coisa para realmente jogar golfe: var d=new String[x*x];pode ser var d=c.clone();. 234 bytes
Kevin Cruijssen 14/01
PS: Por que o seu TIO contém String que você converte em matrizes de número inteiro 2D? Eu adicionei uma pasta-bin com os casos de teste na parte inferior, para o qual você pode substituir o [e ]com {e }e adicionar um líder new int[][], e que teria sido suficiente. ;)
Kevin Cruijssen 14/01
Droga, eu não tinha visto o colar-bin :( E para o resto, ainda estou jogando golfe. Fiz um passe difícil, mas obrigado :-)
Olivier Grégoire
O i=0era um remanescente quando eu enchia as matrizes por mim ao invés de usar Arrays.fill. Obrigado :-) E pelo cloneque pensei em usá-lo, mas ainda pensei que teria retornado um Objecte não o tipo real. Devo estar com várias versões atrasadas nesse ponto;)
Olivier Grégoire
4

Japonês , 18 bytes

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

Experimente online!

Explicação:

®              Ã      #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

A etapa "Transformar em uma string" é necessária porque o Japt não compara matrizes por valor e o built-in para contornar isso não funciona para matrizes multidimensionais .

Kamil Drakari
fonte
2
Vou ver se consigo algum tempo entre as reuniões amanhã para tentar A.e()trabalhar para matrizes multidimensionais; sempre quis voltar a isso. Enquanto isso ÕmòV-> yòVvocê economizará um byte.
Shaggy
By the way, a limitação na comparação de matrizes para a igualdade é JavaScript, em vez de ser particular para Japt;)
Shaggy
4

TSQL, 164 bytes

Preenchendo uma variável de tabela para ter entrada, essa criação de entrada e inserção de dados não foi incluída na contagem de bytes. Somente a consulta real para extrair os dados.

Golfe (não incluindo a tabela de teste - pode ser encontrado na versão não destruída):

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)

Experimente

t-clausen.dk
fonte
4

JavaScript (ES6), 88 bytes

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

Experimente online!

Quão?

Este código é:

  • extraindo todas as sub-matrizes em cada matriz de entrada como uma concatenação de células
  • ordenando as sub-matrizes em ordem lexicográfica
  • testando se o resultado é o mesmo para ambas as matrizes de entrada

Ele está aproveitando os limites descritos no desafio:

  • Uma matriz consiste em um dígito, portanto, podemos concatenar todas as células de uma sub-matriz sem qualquer separador e ainda obter uma representação exclusiva dela (por exemplo, [[1,2],[3,4]]pode ser armazenada como "1234").

  • 100(x,y)I

    I=yn×128+xn

    ou como código JS: y / n << 7 | x << n

Comentado

(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
fonte
3

Carvão , 54 49 bytes

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

Experimente online! Link é a versão detalhada do código. Recebe entrada como uma matriz de matrizes bidimensionais de tamanho igual. Saídas 1 em caso de sucesso, nada em caso de falha. Explicação:

1

Assuma o sucesso.

Fθ

Faça um loop sobre as matrizes.

F⪪ιη

Divida a matriz em npedaços de linha com tamanho.

F÷L§κ⁰η

Faça um loop sobre cada parte da coluna.

⊞υEκ§⪪μηλ

Extraia o pedaço de coluna para cada linha do pedaço de linha e salve a submatriz resultante em uma lista.

W∧υ⊟υ

Enquanto a lista não estiver vazia, remova o último pedaço da lista, que em circunstâncias normais vem da segunda matriz.

¿№✂υ⁰⊘⊕Lυ¹ι

Conte o número de ocorrências desse pedaço na primeira metade da lista, que em circunstâncias normais contém os pedaços restantes da primeira matriz.

≔Φυ⁻⌕υιλυ

Se diferente de zero, remova a primeira ocorrência desse pedaço da lista.

Se zero, limpe a saída, tornando-a falsa.

Neil
fonte
2

J , 55 bytes

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

Experimente online!

Uma solução horrível, apenas fez funcionar - não tenho poder para jogar golfe ...

Galen Ivanov
fonte
2

Haskell, 74 73 bytes

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

Nota: O TIO não foi instalado Data.Lists, por isso estou usando Data.Listuma função que está faltando chunksOf: Experimente online!

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

C # (compilador interativo do Visual C #) , 186 bytes

(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));}

Experimente online!

-1 graças a @KevinCruijssen!

Menos código de golfe:

// 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
fonte
Uma coisa pequena para o golfe, o j++pode ser removido e pode ser colocado em +=c[i][j++]+" ";para salvar um byte.
Kevin Cruijssen 15/01
Obrigado pela dica :) Curiosamente, eu vim com quase a mesma solução que a Java.
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);}

Experimente online!

Como todos os bons desafios, comecei pensando que isso era bastante fácil e me jogou algumas curvas. Bem feito @Kevin Cruijssen!

Divide a matriz em cadeias contendo os valores para cada bloco. As matrizes são classificadas e comparadas para igualdade.

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

Saída

bool(false)
640KB
fonte
1

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

Experimente online!

Galen Ivanov
fonte