En el juego de sudoku, a muchos jugadores les gusta "marcar" los posibles números que pueden ir en cada casilla:
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 4
puede 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 1
y 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
0
aN-1
estará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 código de golf, así que haz tus respuestas lo más cortas posible
fuente
Respuestas:
Brachylog , 21 bytes
Pruébalo en línea!
Pruébalo en línea!
Predicado 0 (predicado principal)
Predicado 1 (predicado auxiliar 1)
Predicado 2 (predicado auxiliar 2)
fuente
Jalea , 10 bytes
Pruébalo en línea!
fuente
Pyth , 11 bytes
Pruébalo en línea!
fuente
Haskell, 100 bytes
fuente
and.flip(zipWith elem)z
es más cortoEn realidad , 27 bytes
Pruébalo en línea!
fuente
Python 3,
10199 bytesGracias a @TLW por -2 bytes
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
Pruébalo en Ideone
fuente
list(map(set,
es más corto, creoMathematica, 46 bytes
fuente
PHP,
245231 bytes131117 para la función del producto cartesiano, 114 para las otras cosasMe 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.
fuente