El principio de permutación del palomar

25

En el juego de sudoku, a muchos jugadores les gusta "marcar" los posibles números que pueden ir en cada casilla:

Fila de sudoku

La fila anterior se puede representar como una matriz:

[[1,2,9], [6], [5], [7], [1,2,9], [1,2,9], [3], [1,2,4], [8]]

Ahora, tenga en cuenta que solo hay 1 lugar donde 4puede ir. Esto efectivamente nos permite simplificar la lista anterior para:

[[1,2,9], [6], [5], [7], [1,2,9], [1,2,9], [3], [4], [8]]

El objetivo de este desafío es tomar una lista de posibles números en una permutación y deducir qué posibilidades se pueden eliminar .

Como otro ejemplo, supongamos que tiene la siguiente variedad de posibilidades:

[[0,1,3], [0,2,3], [1,2], [1,2]]

Los dos últimos lugares deben llenarse con 1 y 2. Por lo tanto, podemos eliminar esas posibilidades de los dos primeros elementos en la matriz:

[[0,3], [0,3], [1,2], [1,2]]

Como otro ejemplo:

[[0,1,2,3], [0,2], [0,2], [0,2]]

Es imposible construir una permutación a partir de las posibilidades anteriores, ya que solo hay 1 ubicación para ambos 1y 3, y desearía devolver una matriz vacía.

Debe ingresar una lista de posibilidades y generar las posibilidades restantes después de que se haya eliminado el número máximo de posibilidades.

  • Si una matriz en particular es imposible, debe devolver una matriz vacía o una matriz donde una de las submatrices está vacía.
  • Puede suponer que la matriz estará bien formada y tendrá al menos 1 elemento.
  • Dada una matriz de tamaño N, puede suponer que los números en la submatriz siempre estarán en el rango [0:N), y esoN <= 10
  • No puede suponer que todos los números de 0a N-1estarán presentes
  • Puede suponer que los números dentro de una sola subcadena son únicos.
  • Si una submatriz contiene solo una posibilidad, puede representar la posibilidad en una matriz o por sí misma. [[1],[2],[0]], [1,2,0], [[1,2],0,[1,2]]Son todos válidos.
  • Puede aceptar la matriz en un formato de cadena razonable o en formato de lista / matriz.
  • Las submatrices pueden estar en cualquier orden.
  • En lugar de lidiar con matrices irregulares, puede rellenar lugares vacíos -1.

Casos de prueba

[[0]]                                         -> [[0]]
[[1],[0]]                                     -> [[1],[0]]
[[1],[1]]                                     -> []
[[1],[0,1]]                                   -> [[1],[0]]
[[0,1,2],[1,2],[1,2]]                         -> [[0],[1,2],[1,2]]
[[0,1],[1,2],[0,2]]                           -> [[0,1],[1,2],[0,2]]
[[2,1],[1,2],[1,2]]                           -> []
[[0,3],[2,1],[3,0],[3,2]]                     -> [[0,3],[1],[0,3],[2]]
[[0,1],[0,1],[2,3],[2,3,0]]                   -> [[0,1],[0,1],[2,3],[2,3]]
[[0,1],[0,3],[3,2],[0]]                       -> [[1],[3],[2],[0]]
[[3,5,2],[0,2,4],[4,0],[0,1,3,5],[2,1],[2,4]] -> [[3,5],[0,2,4],[4,0],[3,5],[1],[2,4]]
[[6,9,8,4],[4,5],[5,3,6],[3,8,6,1,4],[3,1,9,6],[3,7,0,2,4,5],[9,5,6,8],[6,5,8,1,3,7],[8],[8,0,6,2,5,6,3]] -> [[6,9,4],[4,5],[5,3,6],[3,6,1,4],[3,1,9,6],[0,2],[9,5,6],[7],[8],[0,2]]
[[3,5,0],[5,7],[5,1,2],[1,3,0],[5,3],[5,0],[5,3,7,8,0,6],[7,5,0,1,8],[1,0,8],[0,6]] -> []
[[9,0,2,3,7],[0,7,6,5],[6,9,4,7],[9,1,2,3,0,5],[2,8,5,7,4,6],[6,5,7,1],[5,9,4],[5,9,3,8,1],[5,0,6,4],[0,7,2,1,3,4,8]] -> [[9,0,2,3,7],[0,7,6,5],[6,9,4,7],[9,1,2,3,0,5],[2,8,5,7,4,6],[6,5,7,1],[5,9,4],[5,9,3,8,1],[5,0,6,4],[0,7,2,1,3,4,8]]
[[2,6,0],[0,4,3],[0,6,2],[0,7],[0,9,2,3,6,1,4],[1,7,2],[2,7,8],[8,6,7],[6,5,2,8,0],[5,8,1,4]] -> [[2,6,0],[3],[0,6,2],[0,7],[9],[1],[2,7,8],[8,6,7],[5],[4]]
[[8],[8,0,6,5,7,2,4,1],[8,6,9,3,5,0,7],[3,9,1,0],[9],[9,2,6],[2,8,3],[3,1,6,8,2],[6],[6,4,5,3,0,7]] -> [[8],[5,7,4],[5,7],[0],[9],[2],[3],[1],[6],[4,5,7]]
[[8,1,0],[5,8,7,6,2,0],[6,8,2],[2,4,0,9],[4,1,7,3,6,8],[8,1],[8,0,3],[0,8,2],[0,8,3],[1,8,0]] -> []

Este es un así que haz tus respuestas lo más cortas posible

Nathan Merrill
fuente
Cualquier número mayor que 9?
Leaky Nun
No necesita admitir números mayores que 9.
Nathan Merrill
¿Puedo regresar con duplicados en submatrices?
Leaky Nun
@LeakyNun no. Las submatrices solo pueden contener elementos únicos.
Nathan Merrill
Creo que tienes algunos errores en tu cuarto caso de prueba; Una de las sublistas está entre corchetes.
TheBikingViking

Respuestas:

17

Brachylog , 21 bytes

:1fz:da|,[]
:2a#d
:Am

Pruébalo en línea!

Pruébalo en línea!

Predicado 0 (predicado principal)

:1fz:da|,[]
:1f            Find all solutions of Predicate 1 using Input as Input.
   z           Transpose
    :da        Deduplicate each.
       |,[]    If there is no solution, return [] instead.

Predicado 1 (predicado auxiliar 1)

:2a#d
:2a     Each element of Output satisfies Predicate 2 with each element of Input as Input
   #d   Each element is different

Predicado 2 (predicado auxiliar 2)

:Am     Output is member of Input
Monja permeable
fuente
8

Jalea , 10 bytes

Œp⁼Q$ÐfZQ€

Pruébalo en línea!

Œp⁼Q$ÐfZQ€   Main chain, argument: z

Œp           Cartesian product
  ⁼Q$Ðf      Filter for those that remain unchanged when uniquified
       Z     Transpose
        Q€   Uniquify each subarray
Monja permeable
fuente
Parece un poco falso decir 10 bytes cuando Jelly usa caracteres fuera de latin1. Representada como UTF-8, la secuencia anterior requiere 16 bytes.
Chris Becke
1
@ChrisBecke Jelly tiene su propio
juego de
Y, sin embargo, si lo pruebo en línea. - Necesito enviar 16 bytes.
Chris Becke
@ChrisBecke Sí, pero si descargas Jelly solo tendrías que escribir un programa de 10 bytes.
Leaky Nun
¿Y guardarlo en un archivo de texto que no puedo editar con otra cosa que no sea Jelly? Según ese argumento, si Jelly comprimió su programa, ¿solo deberíamos contar los bytes comprimidos?
Chris Becke
7

Pyth , 11 bytes

{MC{I#.nM*F

Pruébalo en línea!

{MC{I#.nM*F
         *F  reduce by Cartesian product
             produces nested arrays
      .nM    flatten each
   {I#       filter for invariant under deduplication
  C          transpose
{M           deduplicate each
Monja permeable
fuente
6

Haskell, 100 bytes

import Data.List
p z=map nub$transpose$filter(and.(flip$zipWith elem)z)$permutations[0..length z-1]
Geoff Reedy
fuente
Buena solución! and.flip(zipWith elem)zes más corto
Damien
2

Python 3, 101 99 bytes

Gracias a @TLW por -2 bytes

from itertools import*
lambda x:list(map(set,zip(*[i for i in product(*x)if len(i)==len(set(i))])))

Una función anónima que toma datos a través del argumento de una lista de listas y devuelve una lista de conjuntos.

Cómo funciona

from itertools import*        Import Python's library for iterator generation
lambda x                      Anonymous function with input possibilities x as a
                              list of lists
...for i in product(*x)...    For i in the Cartesian product of x, ie all candidate
                              arrangements:
[...if len(i)==len(set(i))]    Filter into list by non-duplicity (set removes
                               duplicates, so there are no duplicates if the length
                               of i is the same as the length of the set of
                               the elements of i)
zip(*...)                     Unpack and take the transpose, leaving the modified
                              possibilities with duplicates
map(set,...)                  Remove duplicates
:list(...)                    Return the modified possibilities as a list of sets

Pruébalo en Ideone

TheBikingViking
fuente
list(map(set,es más corto, creo
TLW
2

Mathematica, 46 bytes

Union/@Thread@Select[Tuples@#,DuplicateFreeQ]&
alephalpha
fuente
0

PHP, 245 231 bytes

131 117 para la función del producto cartesiano, 114 para las otras cosas

function c($a){if ($a){if($u=array_pop($a))foreach(c($a)as$p)foreach($u as$v)yield $p+[count($p)=>$v];}else yield[];}
function p($a){foreach(c($a)as$i)if(max(array_count_values($i))<2)foreach($i as$k=>$v)$r[$k][$v]=$v;return$r?:[];}

Me encontré con problemas de memoria en algunos de los casos de prueba, con una función recursiva para el producto cartesiano. Funcionó mejor con esta clase de generador y function c($a){$b=[];foreach($a as$i)$b[]=new \ArrayIterator($i);return new CartesianProductIterator($b);}.
Pero mi generador es más corto y hace el mismo trabajo.

Sin embargo, los ejemplos más grandes resultan en un error interno del servidor (tanto con el iterador como con el generador) después de un tiempo en mi máquina. Actualmente no hay tiempo para verificar los registros del servidor, desafortunadamente.

Titus
fuente