Mi pequeño niño tiene un juguete como este:
Este juguete consta de 10 pequeños cubos apilables, que vamos a numerar de 1 (el más pequeño) a 10 (el más grande). A veces hace pequeños montones y el juguete termina así:
Podemos representar esquemáticamente las pilas como esta:
1 6
4 9 2 7
5 10 3 8
---------- <-- Floor
1 2 3 4 <-- Pile #
O, dicho de otra manera:
[[4,5],[9,10],[1,2,3],[6,7,8]]
Este conjunto de pilas de cubos se puede volver a apilar fácilmente para reconstruir el conjunto original (la primera imagen) simplemente colocando pilas consecutivas de cubos más pequeños dentro de pilas de cubos más grandes:
1 1 6
2 2 7
1 6 3 6 3 8
4 9 2 7 4 9 7 4 9
5 10 3 8 5 10 8 5 10
---------- > [Pile 3 to 1] > ---------- > [Pile 4 to 2] > ---------- > [Pile 1 to 2] > Done!
1 2 3 4 1 2 3 4 1 2 3 4
Sin embargo, a veces mi hijo intenta construir torres o tira cubos, y las pilas terminan siendo inconsistentes y el conjunto original no se puede reconstruir simplemente colocando una pila dentro de otra. Ejemplos de esto:
[[1,3,2],[4]] (the kid tried to build a tower by placing a bigger bucket
over a smaller one, we would need to reorder the buckets
first)
[[1,3,4],[2]] (the kid left aside an unordered bucket, we would need to remove
bucket #1 from pile #1 before restacking)
[[1,2,3],[5]] (the kid lost a bucket, we need to find it first)
Reto
Dada una lista de listas de enteros que representan un conjunto de pilas de cubetas, devuelve un valor verdadero si las listas representan un conjunto de pilas fácilmente re-apilables, o falsey en cualquier otro caso.
- La entrada se dará como una lista de listas de enteros, que representan los cubos de arriba a abajo para cada pila.
- No habrá pilas de inicio vacías (no obtendrá
[[1,2,3],[],[4,5]]
como entrada). - El número total de cubos puede ser cualquiera dentro de un rango entero razonable.
- Mi hijo solo tiene un conjunto de cubos, por lo que no habrá elementos duplicados.
- Puede seleccionar dos valores consistentes (y coherentes) para verdadero o falso.
- Los cubos se etiquetarán del # 1 al #N, siendo
N
el número entero más grande en las listas de enteros. Mi hijo todavía no conoce el concepto de cero. - Puede recibir la entrada en cualquier formato razonable siempre que represente un conjunto de pilas de cubos. Solo especifíquelo en su respuesta si cambia la forma en que recibe la entrada.
- Este es el código de golf , ¡así que puede ganar el programa / función más corto para cada idioma!
Ejemplos
Input: [[4,5],[9,10],[1,2,3],[6,7,8]]
Output: Truthy
Input: [[6,7,8,9,10],[1],[2],[3,4,5],[11,12,13]]
Output: Truthy
Input: [[2,3,4],[1],[5,6,7]]
Output: Truthy
Input: [[1,2],[5,6],[7,8,9]]
Output: Falsey (buckets #3 and #4 are missing)
Input: [[2,3,4],[5,6,7]]
Output: Falsey (bucket #1 is missing)
Input: [[1,3,4],[5,7],[2,6]]
Output: Falsey (non-restackable piles)
Input: [[1,4,3],[2],[5,6]]
Output: Falsey (one of the piles is a tower)
fuente
Respuestas:
Jalea ,
65 bytesGracias a @Lynn por guardar 1 byte.
Pruébalo en línea! (viene con el pie de página de la suite de pruebas)
Explicación
fuente
ṢFµJ⁼
funciona, pero no he pensado en todos los casos límite.1
que no falta el cubo . No estoy seguro de si esto está garantizado por el OP.J
pueden devolverse, lo que garantiza una salida falsa. ¿Me estoy perdiendo de algo?Python 2 ,
5352 bytesGracias por el byte xnor
Pruébalo en línea!
fuente
[]
. Bastante complicado[0]
para que el rango pueda comenzar desde0
.JavaScript (ES6),
5958 bytesExplicación
Casos de prueba
Mostrar fragmento de código
fuente
05AB1E , 4 bytes
Pruébalo en línea!
fuente
Haskell , 54 bytes
Pruébalo en línea!
fuente
Haskell , 37 bytes
Pruébalo en línea!
Comprueba si la lista ordenada concatenada es lexicográficamente más pequeña que la lista infinita
[1,2,3,...]
. Debido a que no hay duplicados, cualquier segmento faltante o fuera de servicio causaría un valor mayor quek
en elk
'th lugar, haciendo que la lista resultante sea más grande ...fuente
Pyth, 6 bytes
Pruébalo aquí.
Explicación:
fuente
UI
parte, por favorU <col>
esrange(len(A))
,I <pfn> <any> <n-1:any>
esA(B, ...) == B
.U <col>
esrange(len(A))
, pero no me había dado cuenta de que portar la solución Python sería más corta ...PROLOG (SWI), 54 bytes
Ahora eso está mejor. Todavía bastante detallado, por desgracia.
Pruébalo en línea!
El
s/1
predicado toma una lista como argumento y es verdadero si la lista es una lista de cubos fácilmente apilables.Mejora en el algoritmo: si clasifico la lista antes de aplanarla, esto obliga a ordenar todas las sublistas para que el predicado sea verdadero. Ligeramente "prestado" de la respuesta de Jelly de Pietu1998 . Gracias a eso puedo volcar lo
forall
que es más de la mitad del programa (ver más abajo la respuesta original).¿Como funciona?
El predicado es verdadero si todas sus cláusulas son verdaderas:
Respuesta anterior, PROLOG (SWI), 109 bytes
Pruébalo en línea!
fuente
Pyth ,
9 1611 bytes (fijo)Utiliza un método completamente diferente de la otra respuesta. Un enfoque más corto de 7 bytes se puede encontrar a continuación.
Banco de pruebas.
Explicación
¿Como funciona esto?
Tomemos un par de ejemplos, que hacen que sea más fácil de entender. Supongamos que la entrada es
[[1,3,4],[5,7],[2,6]]
. El núcleo de este algoritmo es que cada delta en la lista no aplanada debe ser 1 para que los depósitos sean apilables.Primero apagado, lo
S
convierte en[[1, 3, 4], [2, 6], [5, 7]]
.Entonces,
s
la aplana:[1, 3, 4, 2, 6, 5, 7]
.Anteponer un
0
delante:[0, 1, 3, 4, 2, 6, 5, 7]
.+
obtiene los deltas de la lista,[1, 2, 1, -2, 4, -1, 2]
.tM
decrementa cada elemento,[0, 1, 0, -3, 3, -2, 1]
.Cualquier no
0
entero es verdadero en Pyth, por lo que verificamos si hay algún elemento verdadero.E
(lo que significa que la pila no se puede formar correctamente). Nosotros conseguimosTrue
.!
niega el resultado, que se convierteTrue
enFalse
.Si la entrada fuera, por ejemplo
[[6,7,8,9,10],[1],[2],[3,4,5],[11,12,13]]
, el algoritmo funcionaría de esta manera:Ordenado por el elemento más alto:
[[1], [2], [3, 4, 5], [6, 7, 8, 9, 10], [11, 12, 13]]
y aplanado, con un0
antepone:[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13]
.Deltas:
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
. Todo get decrementa:[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
.No hay un elemento de verdad, así que lo entendemos
False
. Por negación lógica, el resultado esTrue
.Pyth , 7 bytes
Banco de pruebas.
Respuesta del puerto de Python y una variación de la solución de @ Erik .
fuente
tM
decrementos de cada elemento? Pensaría que disminuir cada elemento de[1, 2, 1, -2, 4, -1, 2]
produciría[0, 1, 0, -3, 3, -2, 1]
. Pero eso no ayudaría a resolver el problema, así que debo estar malinterpretando lo que significa disminuir cada elemento.tM
disminuye cada elemento en la lista por1
. Hay un error en mi explicación. Arreglará.Brachylog , 5 bytes
Pruébalo en línea!
Unificaciones explicadas:
Explicación analítica:
En primer lugar, ordenamos la lista de listas, y luego concatenamos (es decir, aplanamos 1 profundidad) (
oc
) para que los cubos se apilen de derecha a izquierda si es posible. Luego, para verificar si los cubos se han apilado correctamente (es decir, no faltan cubos o torres), verificamos que la lista resultante sea un rango inclusivo de 1 a su longitud. Ahora, en lugar de verificar la lista con el rango [1..n] de su longitud ({l⟦₁?}
), tratamos de encontrar una entrada a una función que genere dicho rango (~⟦₁
), si existe. Si se encuentra una entrada, el programa finaliza sin problemas, por lo que activa untrue.
estado. Si no se encuentra ninguna entrada, el programa falla y activa unfalse.
estado.fuente
Python 2 , 43 bytes
Pruébalo en línea!
Comprueba si la lista ordenada concatenada es lexicográficamente más pequeña que
[1,2,3,...N]
grandeN
. Dado que no hay duplicados, cualquier depósito faltante o fuera de servicio causaría un valor mayor quek
en elk
lugar 'th, haciendo que la lista resultante sea más grande. La longitud de cadena de la entrada es suficiente como límite superior ya que cada número toma más de 1 carácter.fuente
MATL , 5 bytes
Pruébalo en línea!
(Entrada implícita, por ejemplo
{[4,5],[9,10],[1,2,3],[6,7,8]}
)S
- ordenar matrices de entrada en orden lexicográfico ({[1,2,3],[4,5],[6,7,8],[9,10]}
)g
- convertir en una sola matriz (cell2mat
)t
- duplicar esof
- Encuentra índices de valores distintos de cero. Dado que la entrada aquí no son todos ceros, devuelve la lista de índices de 1 a longitud (matriz) ([1,2,3,4,5,6,7,8,9,10],[1,2,3,4,5,6,7,8,9,10]
)=
- compruebe que la matriz es igual al rango 1 a la longitud (matriz)fuente
Japt ,
131211 bytesEsto probablemente podría ser más corto.
Pruébalo o ejecuta todos los casos de prueba
Explicación
fuente
ä-0 e¥J
oän0 e¥1
ä
matrices todavía. Gracias por el ahorro.Scala, 49 bytes
Sin golf:
fuente
Japt , 9 bytes
Pruébalo en línea!
fuente
g<space>
;)R , 58 bytes
Pruébalo en línea!
NB: FALSO es el resultado verdadero, VERDADERO es el falso
Explicacion:
fuente
seq(a)
por 2 bytes? Además, está permitido usarloTRUE
como un valor falso y viceversa (solo especifique en su respuesta), por lo que puede hacerloany(a-seq(a))
para otro byte.seq(a)
comportarme de manera diferente cuandoa
es de longitud 1 y me perdí que en este caso obtendremos los mismos resultados: D GRACIAS!C # (.NET Core) ,
157145132 bytes-13 bytes gracias a TheLethalCoder
El recuento de bytes también incluye
Pruébalo en línea!
Sin golf:
fuente
x.First()
->x[0]
?Enumerable.Range
->new int[]
yZip
con índice si es posible ..? RetireWhere
y coloque la condición enAny
.new int[]
enfoque requeriría agregar aSelect()
para obtener el índice y, en última instancia, hacer que el byte cuente más grande.CJam , 11 bytes
Pruébalo en línea!
Oww
:(
... si!{$:+_,,:)=}
fuente
Carbón de leña , 19 bytes (¿no compite?)
Pruébalo en línea!
-10 bytes gracias a ASCII-only .
-3 bytes gracias a ASCII-only para una implementación posterior (ver el historial de revisiones para la versión posiblemente competidora).
-
por la verdad,por la falsedad.
La entrada es una lista singleton de una lista de listas, debido a la forma en que Charcoal toma la entrada.
fuente
UP
.UPsorted
.▷
embargo, el uso allí hace que las cosas de alcance sean la prioridad, de modo que, ¿por quéUP
sigue ahí, pero supongo que puede evitar usar los nombres de funciones de Python como nombres var?v
, también O_O, esto ni siquiera es un desafío de arte ascii (no es de extrañar que sea tan despiadado: PJava 10, 213 bytes
Pruébalo en línea.
Parecía una buena idea cuando comencé, pero estas incorporaciones solo lo hacen más largo ... Definitivamente se puede jugar al golf usando un enfoque más manual ...
Inspirado por la respuesta 05AB1E de 4 bytes de @EriktheOutgolfer . 4 contra 213 bytes, rofl ..>.>
Explicación:
fuente