¿Puedo volver a apilar los cubos?

30

Mi pequeño niño tiene un juguete como este:

Apilado

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í:

Dispersado

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 Nel 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 , ¡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)
Charlie
fuente
Esto viene de la caja de arena .
Charlie
2
@ Mr.Xcoder no, no habrá elementos duplicados (mi hijo solo tiene un juego de cubos y todos son diferentes.
Charlie
1
¿Podemos suponer que el cubo 1 nunca falta?
PurkkaKoodari
2
@ Pietu1998 puede faltar el cubo # 1, acabo de agregar un caso de prueba (de hecho, el cubo más pequeño es el más fácil de perder).
Charlie
1
Los diversos desafíos de la Torre de Hanoi están relacionados (no duplicados) de esto.
AdmBorkBork

Respuestas:

12

Jalea , 6 5 bytes

Gracias a @Lynn por guardar 1 byte.

ṢFµJ⁼

Pruébalo en línea! (viene con el pie de página de la suite de pruebas)

Explicación

ṢFµJ⁼    Main link. Argument: piles
Ṣ          Sort the piles by the size of the top bucket.
 F         Stack the piles, putting the left one to the top.
   J       See what a full pile with this many buckets would look like.
    ⁼      See if that looks like the pile you built.
PurkkaKoodari
fuente
Creo que ṢFµJ⁼funciona, pero no he pensado en todos los casos límite.
Lynn
@ Lynn Eso funciona asumiendo 1que no falta el cubo . No estoy seguro de si esto está garantizado por el OP.
PurkkaKoodari
@Lynn bucket # 1 puede faltar, sí. Acabo de agregar un nuevo caso de prueba.
Charlie
Si faltan cubos, la lista ordenada siempre contendrá números mayores que los que Jpueden devolverse, lo que garantiza una salida falsa. ¿Me estoy perdiendo de algo?
Lynn
¿Creo que todavía puedes usar la versión de 5 bytes con el cubo # 1 perdido?
Erik the Outgolfer
8

Python 2 , 53 52 bytes

Gracias por el byte xnor

lambda x:sum(sorted(x),[0])==range(len(sum(x,[]))+1)

Pruébalo en línea!

Chris_Rands
fuente
Me gusta que comience la suma a las []. Bastante complicado
bioweasel
2
Puede guardar un byte iniciando la suma en [0]para que el rango pueda comenzar desde 0.
xnor
5

JavaScript (ES6), 59 58 bytes

a=>!(a.sort((a,[b])=>a[i=0]-b)+'').split`,`.some(v=>v-++i)

Explicación

a=>                                                        // given a 2D-array 'a'
     a.sort((a,[b])=>a[i=0]-b)                             // sort by first item
                              +''                          // flatten
    (                            ).split`,`                // split again
                                           .some(v=>v-++i) // i such that a[i] != i+1?
   !                                                       // true if none was found

Casos de prueba

Arnauld
fuente
5

Haskell , 37 bytes

import Data.List
(<[1..]).concat.sort

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 que ken el k'th lugar, haciendo que la lista resultante sea más grande ...

xnor
fuente
4

Pyth, 6 bytes

UItMsS

Pruébalo aquí.

Explicación:

UItMsSQ
UI      Invariant from U (range(len(A)) for our purpose)
  tM     Map t (A - 1 for our purpose)
    s     s (flatten 1-deep for our purpose)
     S     S (sort for our purpose)
      Q     Q (autoinitialized to input) (implicit)
Erik el Outgolfer
fuente
¿Wat? Agregue una explicación a la UIparte, por favor
Sr. Xcoder
@ Mr.Xcoder U <col>es range(len(A)), I <pfn> <any> <n-1:any>es A(B, ...) == B.
Erik the Outgolfer
Entonces me sobrepasé terriblemente>. <. Aunque podría jugar golf en el mío. Genio, solución brillante, ahora que veo cómo funciona ... ¡Felicidades!
Sr. Xcoder
@ Mr.Xcoder Realmente solo está buscando cosas en los documentos ...
Erik the Outgolfer
No, no es. Yo sabía que U <col>es range(len(A)), pero no me había dado cuenta de que portar la solución Python sería más corta ...
Sr. Xcoder
4

PROLOG (SWI), 54 bytes

s(L):-sort(L,M),flatten(M,N),last(N,O),numlist(1,O,N).

Ahora eso está mejor. Todavía bastante detallado, por desgracia.

Pruébalo en línea!

El s/1predicado 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 forallque 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:

s(L) :-
    sort(L,M),                % M is L sorted in ascending order
    flatten(M,N),             % N is the 1-dimention version of M
    last(N,O),                % O is the last elemnt of N
    numlist(1,O,N).           % N is the list of all integers from 1 to O

Respuesta anterior, PROLOG (SWI), 109 bytes

s(L):-flatten(L,M),sort(M,N),last(N,O),numlist(1,O,N),forall(member(A,L),(A=[B|_],last(A,C),numlist(B,C,A))).

Pruébalo en línea!

Nathan.Eilisha Shiraini
fuente
3

Pyth , 9 16 11 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.

!.EtM.++0sS

Banco de pruebas.


Explicación

! .EtM. ++ 0sSQ -> Programa completo, con entrada implícita al final.

          SQ -> Ordenar la entrada por el elemento más alto en cada sublista.
         s -> Acoplar.
       +0 -> Anteponer un 0.
     . + -> Obtener los deltas de la lista (es decir, diferencias entre elementos consecutivos)
   tM -> Disminuye cada elemento.
 .E -> Cualquier elemento verdadero (1 son verdaderos, 0 son falsos)
! -> Negar (tener valores de verdad / falsedad coherentes)

¿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 Sconvierte en [[1, 3, 4], [2, 6], [5, 7]].

  • Entonces, sla aplana: [1, 3, 4, 2, 6, 5, 7].

  • Anteponer un 0delante:[0, 1, 3, 4, 2, 6, 5, 7]

  • .+obtiene los deltas de la lista, [1, 2, 1, -2, 4, -1, 2].

  • tMdecrementa cada elemento, [0, 1, 0, -3, 3, -2, 1].

  • Cualquier no 0entero 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 conseguimos True.

  • !niega el resultado, que se convierte Trueen False.

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 un 0antepone: [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 es True.


Pyth , 7 bytes

qSlsQsS

Banco de pruebas.

Respuesta del puerto de Python y una variación de la solución de @ Erik .

Sr. Xcoder
fuente
¡Muchas gracias por tomarse el tiempo para explicar cómo funciona esto!
Charlie
Continuemos esta discusión en el chat .
Sr. Xcoder
@ Mr.Xcoder ¿Qué quiere decir con tMdecrementos 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.
Brian J
@BrianJ tMdisminuye cada elemento en la lista por 1. Hay un error en mi explicación. Arreglará.
Sr. Xcoder
@BrianJ fijo. Gracias por ver eso
Sr. Xcoder
3

Brachylog , 5 bytes

oc~⟦₁

Pruébalo en línea!

Unificaciones explicadas:

?o₀c₀~⟦₁.
?         The input (implicit)
 o₀       Sorted (subscript default = 0 => ascending)
   c₀     Concatenated (subscript default = 0 => no length check)
     ~    Inverse (find the input)
      ⟦₁   Range (subscript = 1 => [1..input])
        . The output (implicit)

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 un true.estado. Si no se encuentra ninguna entrada, el programa falla y activa un false.estado.

Erik el Outgolfer
fuente
3

Python 2 , 43 bytes

lambda l:sum(sorted(l),[0])<range(len(`l`))

Pruébalo en línea!

Comprueba si la lista ordenada concatenada es lexicográficamente más pequeña que [1,2,3,...N]grande N. Dado que no hay duplicados, cualquier depósito faltante o fuera de servicio causaría un valor mayor que ken el klugar '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.

xnor
fuente
Bien, pensé que debería haber una manera de mejorar sustancialmente mi solución, ¡y esto es todo!
Chris_Rands
3

MATL , 5 bytes

Sgtf=

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 eso

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

sundar - Restablece a Monica
fuente
3

Japt , 13 12 11 bytes

Esto probablemente podría ser más corto.

ñÎc äaT e¥1
  • 1 byte guardado gracias a ETH

Pruébalo o ejecuta todos los casos de prueba


Explicación

                :Implicit input of 2D array `U`
ñÎ              :Sort sub-arrays by their first element
  c             :Flatten
      T         :Prepend 0
    äa          :Consecutive absolute differences
        e¥1     :Does every element equal 1?
Lanudo
fuente
Sí, tienes razón, creo. Sin embargo, valió la pena
intentarlo
Creo que puede guardar un byte en la última línea con ä-0 e¥Joän0 e¥1
ETHproductions
Otra solución similar de 13 bytes: ethproductions.github.io/japt/…
Oliver
@ETHproductions, ¡no tengo idea de lo que está sucediendo allí! : D No creo que haya tenido ocasión de tocar ämatrices todavía. Gracias por el ahorro.
Shaggy
1
@LuisfelipeDejesusMunoz Funciona cuando usa la primera línea de esta solución y la segunda línea de la solución vinculada, tal como dije, nueve bytes: codegolf.stackexchange.com/a/168967/16484
Nit
2

Scala, 49 bytes

p=>{val s=p.sortBy(_(0)).flatten
s==(1 to s.max)}

Sin golf:

piles: List[List[Int]] =>
{
  val sorted = piles.sortBy(pile=>pile(0)).flatten //Since piles are sequential, we can sort them by their first element
  sorted == (1 to sorted.max) //If all the buckets are present and in order, after sorting them it should be equivalent to counting up from 1 to the max bucket
}
Ethan
fuente
2

R , 58 bytes

function(v,a=unlist(v[order(sapply(v,min))]))any(a-seq(a))

Pruébalo en línea!

NB: FALSO es el resultado verdadero, VERDADERO es el falso

  • -3 bytes gracias a @JayCe

Explicacion:

a=unlist(v[order(sapply(v,min))])  # order the list of vector by the min value and flatten
all(a==seq(a=a))                   # if the flattened list is equal to 1:length then it's ok
digEmAll
fuente
1
¿Simplemente seq(a)por 2 bytes? Además, está permitido usarlo TRUEcomo un valor falso y viceversa (solo especifique en su respuesta), por lo que puede hacerlo any(a-seq(a))para otro byte.
JayCe
@ JayCe: Soy un tonto ... Estaba tan preocupado por seq(a)comportarme de manera diferente cuando aes de longitud 1 y me perdí que en este caso obtendremos los mismos resultados: D GRACIAS!
digEmAll
1

C # (.NET Core) , 157 145 132 bytes

-13 bytes gracias a TheLethalCoder

l=>{var k=l.OrderBy(x=>x[0]).SelectMany(x=>x);return!Enumerable.Range(1,k.Count()).Zip(k,(x,y)=>x==y).Any(x=>!x);}

El recuento de bytes también incluye

using System.Linq;

Pruébalo en línea!

Sin golf:

l => {
        var k = l.OrderBy(x=>x[0])              // First, sort stacks by first bucket
                 .SelectMany(x => x);           // Concatenate stacks into one
        return !Enumerable.Range(1, k.Count())  // Create a sequence [1...n]
               .Zip(k, (x, y) => x == y)        // Check if our big stack corresponds the sequence
               .Any(x => !x);                   // Return if there were any differences
     };
Grzegorz Puławski
fuente
1
x.First()-> x[0]? Enumerable.Range-> new int[]y Zipcon índice si es posible ..? Retire Wherey coloque la condición en Any.
TheLethalCoder
@TheLethalCoder ¡Gracias por los consejos! Y el new int[]enfoque requeriría agregar a Select()para obtener el índice y, en última instancia, hacer que el byte cuente más grande.
Grzegorz Puławski
1

Carbón de leña , 19 bytes (¿no compite?)

A▷m⟦▷s▷vθυ⟧θ⁼θ…·¹Lθ

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.

Erik el Outgolfer
fuente
Es la primera respuesta en carbón que veo que utiliza UP.
Charlie
@CarlosAlejo Tenía que encontrar una manera de ordenar, y la forma más fácil era simplemente UPsorted.
Erik the Outgolfer
24 bytes
solo ASCII el
Sin embargo, el uso allí hace que las cosas de alcance sean la prioridad, de modo que, ¿por qué UPsigue ahí, pero supongo que puede evitar usar los nombres de funciones de Python como nombres var?
Solo ASCII el
yay agregó eval como v, también O_O, esto ni siquiera es un desafío de arte ascii (no es de extrañar que sea tan despiadado: P
Solo ASCII
0

Java 10, 213 bytes

import java.util.*;m->{Arrays.sort(m,(a,b)->Long.compare(a[0],b[0]));var r=Arrays.stream(m).flatMapToInt(Arrays::stream).toArray();return Arrays.equals(r,java.util.stream.IntStream.range(1,r.length+1).toArray());}

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:

import java.util.*;      // Required import for Arrays
m->{                     // Method with 2D integer-array parameter and boolean return-type
  Arrays.sort(m,         //  Sort the 2D input-array on:
    (a,b)->Long.compare(a[0],b[0])); 
                         //  The first values of the inner arrays
var r=Arrays.stream(m).flatMapToInt(Arrays::stream).toArray();
                         //  Flatten the 2D array to a single integer-array
return Arrays.equals(r,  //  Check if this integer-array is equal to:
  java.util.stream.IntStream.range(1,r.length+1).toArray());} 
                         //  An integer-array of the range [1, length+1]
Kevin Cruijssen
fuente