Mon petit enfant a un jouet comme celui-ci:

Ce jouet se compose de 10 petits seaux empilables, que nous allons numéroter de 1 (le plus petit) à 10 (le plus grand). Parfois, il fait de petits tas et le jouet finit comme ceci:

Nous pouvons représenter schématiquement les piles comme ceci:

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

Ou, autrement dit:

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

Cet ensemble de piles de seaux est facilement réempilable pour reconstruire l'ensemble d'origine (la première image) simplement en plaçant consécutivement des piles de petits seaux à l'intérieur de piles de plus grands seaux:

                             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

Néanmoins, parfois mon enfant essaie de construire des tours, ou jette des seaux, et les piles finissent par être incohérentes et l'ensemble d'origine ne peut pas être reconstruit simplement en plaçant une pile à l'intérieur d'une autre. Exemples de ceci:

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

Défi

Étant donné une liste de listes d'entiers représentant un ensemble de piles de seaux, renvoyez une valeur vraie si les listes représentent un ensemble de piles facilement réempilable, ou falsey dans tout autre cas.

• L'entrée sera donnée sous la forme d'une liste de listes d'entiers, représentant les compartiments de haut en bas pour chaque pile.
• Il n'y aura pas de piles de départ vides (vous n'obtiendrez pas [[1,2,3],[],[4,5]]en entrée).
• Le nombre total de compartiments peut être n'importe lequel dans une plage entière raisonnable.
• Mon enfant n'a qu'un seul ensemble de seaux, il n'y aura donc pas d'éléments en double.
• Vous pouvez sélectionner deux valeurs cohérentes (et cohérentes) pour truey ou falsey.
• Les compartiments seront étiquetés de # 1 à #N, étant Nle plus grand entier dans les listes d'entiers. Mon enfant ne connaît toujours pas le concept du zéro.
• Vous pouvez recevoir l'entrée dans n'importe quel format raisonnable tant qu'elle représente un ensemble de piles de seaux. Précisez-le simplement dans votre réponse si vous modifiez la façon dont vous recevez les données.
• C'est du golf de code , donc le programme / la fonction la plus courte pour chaque langue peut gagner!

Exemples

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)

Gelée , 6 5 octets

Merci à @Lynn d'avoir économisé 1 octet.

ṢFµJ⁼

Essayez-le en ligne! (livré avec le pied de page de la suite de tests)

Explication

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

Merci pour l'octet xnor

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

Essayez-le en ligne!

JavaScript (ES6), 59 58 octets

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

Explication

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

Cas de test

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 octets

{˜āQ

Essayez-le en ligne!

Haskell , 54 octets

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

Essayez-le en ligne!

Haskell , 37 octets

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

Essayez-le en ligne!

Vérifie si la liste triée concaténée est lexicographiquement plus petite que la liste infinie [1,2,3,...]. Puisqu'il n'y a pas de doublons, tout compartiment manquant ou en panne entraînerait une valeur supérieure kà la kplace, ce qui rend la liste résultante plus grande.

Pyth, 6 octets

UItMsS

Essayez-le ici.

Explication:

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 octets

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

Maintenant c'est mieux. Hélas encore assez verbeux.

Essayez-le en ligne!

Le s/1prédicat prend une liste en argument et est vrai si la liste est une liste de compartiments facilement empilables.

Amélioration de l'algorithme: si je trie la liste avant de l' aplatir, cela force toutes les sous-listes à être triées pour que le prédicat soit vrai. Légèrement «emprunté» à la réponse Jelly de Pietu1998 . Grâce à cela, je peux vider ce forallqui représente plus de la moitié du programme (voir ci-dessous pour la réponse originale).

Comment ça marche?

Le prédicat est vrai si toutes ses clauses sont vraies:

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

Réponse précédente, PROLOG (SWI), 109 octets

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

Essayez-le en ligne!

Pyth , 9 16 11 octets (fixe)

Utilise une méthode complètement différente de l'autre réponse. Une approche plus courte de 7 octets peut être trouvée ci-dessous.

!.EtM.++0sS

Suite de tests.

Explication

! .EtM. ++ 0sSQ -> Programme complet, avec entrée implicite à la fin.

          SQ -> Trier l'entrée en fonction de l'élément le plus élevé dans chaque sous-liste.
         s -> Aplatir.
       +0 -> Ajouter un 0.
     . + -> Récupère les deltas de la liste (ie différences entre éléments consécutifs)
   tM -> décrémente chaque élément.
 .E -> Tout élément véridique (1s sont véridiques, 0s sont fausses)
! -> Nier (pour avoir des valeurs cohérentes de vérité / fausse)

Comment cela marche-t-il?

Prenons quelques exemples qui facilitent la compréhension. Supposons que l'entrée soit [[1,3,4],[5,7],[2,6]]. Le cœur de cet algorithme est que chaque delta de la liste non aplatie doit être égal à 1 pour que les compartiments soient empilables.

• Tout d'abord, le Stransforme en [[1, 3, 4], [2, 6], [5, 7]].

• Puis, l' saplatit: [1, 3, 4, 2, 6, 5, 7].

• Ajoutez un 0devant:[0, 1, 3, 4, 2, 6, 5, 7]

• .+obtient les deltas de la liste, [1, 2, 1, -2, 4, -1, 2].

• tMdécrémente chaque élément [0, 1, 0, -3, 3, -2, 1].

• Tout non 0entier est véridique en Pyth, donc nous vérifions s'il y a un élément véridique avec .E(ce qui signifie que la pile ne peut pas être formée correctement). Nous obtenons True.

• !annule le résultat, qui se transforme Trueen False.

Si l'entrée était, par exemple [[6,7,8,9,10],[1],[2],[3,4,5],[11,12,13]], l'algorithme fonctionnerait de cette façon:

• Trié par l'élément le plus élevé: [[1], [2], [3, 4, 5], [6, 7, 8, 9, 10], [11, 12, 13]]et aplati, avec un 0pré - ajouté: [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]. Tous get décrémenté: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0].

• Il n'y a aucun élément véridique, donc nous obtenons False. Par négation logique, le résultat est True.

Pyth , 7 octets

qSlsQsS

Suite de tests.

Port de la réponse Python et une variante de la solution @ Erik .

Brachylog , 5 octets

oc~⟦₁

Essayez-le en ligne!

Unifications expliquées:

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

Explication analytique:

Tout d'abord, nous trions la liste des listes, puis nous concaténons (c'est-à-dire aplatissons à 1 profondeur) ( oc) de sorte que les compartiments soient empilés de droite à gauche si possible. Ensuite, pour vérifier si les godets ont été empilés correctement (c.-à-d. Pas de godets ou de tours manquants), nous vérifions que la liste résultante est une plage inclusive de 1 à sa longueur. Maintenant, au lieu de vérifier la liste avec la plage [1..n] de sa longueur ( {l⟦₁?}), nous essayons de trouver une entrée pour une fonction qui génère une telle plage ( ~⟦₁), s'il y en a une. Si une entrée est trouvée, le programme se termine sans aucun problème, il déclenche donc un true.état. Si aucune entrée n'est trouvée, le programme échoue, déclenchant un false.état.

Python 2 , 43 octets

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

Essayez-le en ligne!

Vérifie si la liste triée concaténée est lexicographiquement plus petite que [1,2,3,...N]pour grande N. Comme il n'y a pas de doublons, tout compartiment manquant ou en panne entraînerait une valeur supérieure kà la kplace, ce qui rend la liste résultante plus grande. La longueur de chaîne de l'entrée suffit comme limite supérieure car chaque nombre prend plus d'un caractère.

MATL , 5 octets

Sgtf=

Essayez-le en ligne!

(Entrée implicite, par exemple {[4,5],[9,10],[1,2,3],[6,7,8]})

S- trier les tableaux d'entrée dans l'ordre lexicographique ( {[1,2,3],[4,5],[6,7,8],[9,10]})

g- convertir en un seul tableau ( cell2mat)

t - dupliquer cela

f- trouver des indices de valeurs non nulles. Puisque l'entrée ici est entièrement non nulle, retourne la liste des indices de 1 à length (array) ( [1,2,3,4,5,6,7,8,9,10],[1,2,3,4,5,6,7,8,9,10])

= - vérifier que le tableau est égal à la plage de 1 à la longueur (tableau)

Japt , 13 12 11 octets

Cela pourrait probablement être plus court.

ñÎc äaT e¥1

• 1 octet économisé grâce à ETH

Essayez-le ou exécutez tous les cas de test

Explication

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

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

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

Japt , 9 octets

ñg c
eUÌõ

Essayez-le en ligne!

R , 58 octets

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

Essayez-le en ligne!

NB: FAUX est le résultat véridique, VRAI est le faux

• -3 octets grâce à @JayCe

Explication:

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 octets

-13 octets grâce à 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);}

Le nombre d'octets comprend également

using System.Linq;

Essayez-le en ligne!

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

CJam , 11 octets

{$:+:(_,,=}

Essayez-le en ligne!

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

Charbon de bois , 19 octets (non concurrentiel?)

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

Essayez-le en ligne!

-10 octets grâce à ASCII uniquement .

-3 octets grâce à ASCII uniquement pour une implémentation ultérieure (voir l'historique des révisions pour une version éventuellement concurrente).

-pour la vérité, pour la fausseté.

L'entrée est une liste unique d'une liste de listes, en raison de la façon dont Charcoal prend l'entrée.

Java 10, 213 octets

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

Essayez-le en ligne.

Cela semblait être une bonne idée quand j'ai commencé, mais ces modules ne font que l'allonger. Peut certainement être joué au golf en utilisant une approche plus manuelle ..

Inspiré par la réponse 05AB1E à 4 octets de @EriktheOutgolfer . 4 vs 213 octets, rofl ..>.>

Explication:

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]