Meu filho pequeno tem um brinquedo como este:

Este brinquedo consiste em 10 pequenos baldes empilháveis, que vamos numerar de 1 (o menor) a 10 (o maior). Às vezes, ele faz pequenas pilhas e o brinquedo acaba assim:

Podemos representar esquematicamente as pilhas assim:

      1  6
4  9  2  7
5  10 3  8
----------  <-- Floor
1  2  3  4  <-- Pile #

Ou, de outra forma:

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

Esse conjunto de pilhas de baldes é facilmente reembalável para reconstruir o conjunto original (a primeira imagem) apenas colocando consecutivamente pilhas de baldes menores dentro de pilhas de baldes maiores:

                             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

No entanto, às vezes meu filho tenta construir torres ou joga baldes fora, e as pilhas acabam sendo inconsistentes e o conjunto original não pode ser reconstruído apenas colocando uma pilha dentro da outra. Exemplos disso:

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

Desafio

Dada uma lista de listas de números inteiros que representam um conjunto de pilhas do balde, retorne um valor verdadeiro se as listas representarem um conjunto de pilhas facilmente reorganizáveis ​​ou falsey em qualquer outro caso.

• A entrada será fornecida como uma lista de listas de números inteiros, representando os buckets de cima para baixo para cada pilha.
• Não haverá pilhas iniciais vazias (você não receberá [[1,2,3],[],[4,5]]como entrada).
• O número total de buckets pode estar dentro de um intervalo inteiro razoável.
• Meu filho tem apenas um conjunto de baldes para que não haja elementos duplicados.
• Você pode selecionar quaisquer dois valores consistentes (e coerentes) para verdade ou falsidade.
• Os buckets serão rotulados de # 1 a #N, sendo No maior número inteiro nas listas de números inteiros. Meu filho ainda não conhece o conceito de zero.
• Você pode receber a entrada em qualquer formato razoável, desde que represente um conjunto de pilhas de baldes. Apenas especifique-o na sua resposta se você alterar a maneira como recebe a entrada.
• Isso é código-golfe , portanto, pode ganhar o programa / função mais curto para cada idioma!

Exemplos

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)

Gelatina , 6 5 bytes

Obrigado a @Lynn por economizar 1 byte.

ṢFµJ⁼

Experimente online! (vem com rodapé da suíte de teste)

Explicação

Ṣ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.

Python 2 , 53 52 bytes

Obrigado pelo byte xnor

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

Experimente online!

JavaScript (ES6), 59 58 bytes

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

Explicação

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 teste

let f =

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

// truthy
console.log(f([[4,5],[9,10],[1,2,3],[6,7,8]]))
console.log(f([[6,7,8,9,10],[1],[2],[3,4,5],[11,12,13]]))
console.log(f([[2,3,4],[1],[5,6,7]]))

// falsy
console.log(f([[1,2],[5,6],[7,8,9]]))
console.log(f([[2,3,4],[5,6,7]]))
console.log(f([[1,3,4],[5,7],[2,6]]))
console.log(f([[1,4,3],[2],[5,6]]))

05AB1E , 4 bytes

{˜āQ

Experimente online!

Haskell , 54 bytes

import Data.List
f l=(sort l>>=id)==[1..length$l>>=id]

Experimente online!

Haskell , 37 bytes

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

Experimente online!

Verifica se a lista classificada concatenada é lexicograficamente menor que a lista infinita [1,2,3,...]. Como não há duplicatas, qualquer depósito ausente ou fora de ordem causaria um valor maior que ko do k'lugar, tornando a lista resultante maior.

Pitão, 6 bytes

UItMsS

Experimente aqui.

Explicação:

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)

PROLOG (SWI), 54 bytes

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

Agora está melhor. Ainda bastante detalhado, infelizmente.

Experimente online!

O s/1predicado recebe uma lista como argumento e é verdadeiro se a lista for uma lista de depósitos facilmente empilháveis.

Melhoria no algoritmo: se eu classifico a lista antes de achatá-la, isso força todas as sublistas a serem classificadas para que o predicado seja verdadeiro. Um pouco "emprestado" da resposta de Pietu1998 Jelly . Graças a isso, posso despejar o forallque é mais da metade do programa (veja abaixo a resposta original).

Como funciona?

O predicado é verdadeiro se todas as suas cláusulas forem verdadeiras:

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

Resposta 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))).

Experimente online!

Pitão , 9 16 11 bytes (Fixo)

Usa um método completamente diferente da outra resposta. Uma abordagem mais curta de 7 bytes pode ser encontrada abaixo.

!.EtM.++0sS

Suíte de teste.

Explicação

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

          SQ -> Classifique a entrada pelo elemento mais alto em cada sub-lista.
         s -> Achatar.
       +0 -> Anexa um 0.
     . + -> Obter os deltas da lista (ou seja, diferenças entre elementos consecutivos)
   tM -> Decrementa cada elemento.
 .E -> Qualquer elemento verdadeiro (1s é verdade, 0s é falso)
! -> Negar (para ter valores coerentes de verdade / falsidade)

Como é que isso funciona?

Vamos dar alguns exemplos, que facilitam a compreensão. Vamos assumir que a entrada é [[1,3,4],[5,7],[2,6]]. O núcleo desse algoritmo é que cada delta na lista não nivelada deve ser 1 para que os buckets sejam empilháveis.

• Primeiro, Svira [[1, 3, 4], [2, 6], [5, 7]].

• Então, sachata-lo: [1, 3, 4, 2, 6, 5, 7].

• Coloque um 0na frente:[0, 1, 3, 4, 2, 6, 5, 7]

• .+obtém os deltas da lista [1, 2, 1, -2, 4, -1, 2],.

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

• Qualquer não 0inteiro é verdade em Pyth, portanto, verificamos se existe algum elemento verdadeiro .E(o que significa que a pilha não pode ser formada corretamente). Nós recebemos True.

• !nega o resultado, que se Truetransforma False.

Se a entrada fosse, por exemplo [[6,7,8,9,10],[1],[2],[3,4,5],[11,12,13]], o algoritmo funcionaria desta maneira:

• Classificadas pelo maior elemento: [[1], [2], [3, 4, 5], [6, 7, 8, 9, 10], [11, 12, 13]]e achatada, com um 0prefixado: [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]. Todos get diminuído: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0].

• Não existe um elemento de verdade, então chegamos False. Por negação lógica, o resultado é True.

Pitão , 7 bytes

qSlsQsS

Suíte de teste.

Resposta do porto do Python e uma variação da solução do @ Erik .

Braquilog , 5 bytes

oc~⟦₁

Experimente online!

Unificações 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)

Explicação analítica:

Primeiro, ordenamos a lista de listas e, em seguida, concatenamos (ou seja, aplainamos 1 profundidade) ( oc) para que os baldes sejam empilhados da direita para a esquerda, se possível. Em seguida, para verificar se os baldes foram empilhados corretamente (ou seja, não há baldes ou torres ausentes), verificamos se a lista resultante é uma faixa abrangente de 1 a seu comprimento. Agora, em vez de verificar a lista com o intervalo [1..n] de seu comprimento ( {l⟦₁?}), tentamos encontrar uma entrada para uma função que gera esse intervalo ( ~⟦₁), se houver um. Se uma entrada for encontrada, o programa será encerrado sem problemas e, portanto, disparará um true.status. Se nenhuma entrada for encontrada, o programa falhará, acionando um false.status.

Python 2 , 43 bytes

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

Experimente online!

Verifica se a lista classificada concatenada é lexicograficamente menor do que [1,2,3,...N]a grande N. Como não há duplicatas, qualquer depósito ausente ou fora de ordem causaria um valor maior que ko do k'lugar, tornando a lista resultante maior. O comprimento da string da entrada é suficiente como um limite superior, pois cada número ocupa mais de um caractere.

MATL , 5 bytes

Sgtf=

Experimente online!

(Entrada implícita, digamos {[4,5],[9,10],[1,2,3],[6,7,8]})

S- classificar matrizes de entrada em ordem lexicográfica ( {[1,2,3],[4,5],[6,7,8],[9,10]})

g- converter em uma única matriz ( cell2mat)

t - duplicar isso

f- encontre índices de valores diferentes de zero. Como a entrada aqui é toda sem zeros, retorna a lista de índices de 1 para comprimento (matriz) ( [1,2,3,4,5,6,7,8,9,10],[1,2,3,4,5,6,7,8,9,10])

= - verifique se a matriz é igual ao intervalo de 1 a comprimento (matriz)

Japonês , 13 12 11 bytes

Provavelmente isso poderia ser mais curto.

ñÎc äaT e¥1

• 1 byte economizado graças ao ETH

Experimente ou execute todos os casos de teste

Explicação

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

Scala, 49 bytes

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

Ungolfed:

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
}

Japonês , 9 bytes

ñg c
eUÌõ

Experimente online!

R , 58 bytes

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

Experimente online!

NB: FALSO é o resultado verdadeiro, VERDADEIRO é o falso

• -3 bytes graças a @JayCe

Explicação:

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

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

-13 bytes graças 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);}

A contagem de bytes também inclui

using System.Linq;

Experimente online!

Ungolfed:

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

CJam , 11 bytes

{$:+:(_,,=}

Experimente online!

Oww :(... sim!{$:+_,,:)=}

Carvão , 19 bytes (não concorrente?)

Ａ▷m⟦▷s▷vθυ⟧θ⁼θ…·¹Ｌθ

Experimente online!

-10 bytes, graças apenas ao ASCII .

-3 bytes graças ao ASCII-only para uma implementação subsequente (consulte o histórico de revisões para uma versão possivelmente concorrente).

-por verdade, por falsidade.

Entrada é uma lista única de uma lista de listas, por causa de como o carvão vegetal recebe entrada.

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

Experimente online.

Parecia uma boa idéia quando comecei, mas esses componentes apenas o tornam mais longos. Definitivamente, você pode jogar golfe usando uma abordagem mais manual.

Inspirado na resposta 05AB1E de 4 bytes de @EriktheOutgolfer . 4 vs 213 bytes, rofl ..>.>

Explicação:

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]