Moje małe dziecko ma taką zabawkę:

Ta zabawka składa się z 10 małych wiader, które można ustawiać jeden na drugim, które będziemy numerować od 1 (najmniejszy) do 10 (największy). Czasami robi małe stosy, a zabawka kończy się w ten sposób:

Możemy przedstawić schematyczne stosy w następujący sposób:

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

Lub inaczej:

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

Ten zestaw stosów łyżek można łatwo odtworzyć w celu odtworzenia oryginalnego zestawu (pierwszy obraz), po prostu umieszczając stosy mniejszych wiader wewnątrz stosów większych wiader:

                             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

Niemniej jednak czasami moje dziecko próbuje budować wieże lub wyrzuca wiadra, a stosy stają się niespójne, a oryginalnego zestawu nie można odbudować tylko przez umieszczenie jednego stosu w drugim. Przykłady tego:

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

Wyzwanie

Biorąc pod uwagę listę liczb całkowitych reprezentujących zestaw stosów kubełkowych, zwróć prawdziwą wartość, jeśli listy reprezentują zestaw łatwych do odtworzenia stosów, lub falsey w każdym innym przypadku.

• Dane wejściowe zostaną podane w postaci list liczb całkowitych reprezentujących segmenty od góry do dołu dla każdego stosu.
• Nie będzie pustych stosów początkowych (nie dostaniesz ich [[1,2,3],[],[4,5]]jako danych wejściowych).
• Całkowita liczba segmentów może być dowolna w rozsądnym zakresie liczb całkowitych.
• Moje dziecko ma tylko jeden zestaw wiader, więc nie będzie duplikatów.
• Możesz wybrać dowolne dwie spójne (i spójne) wartości dla wartości true lub falsey.
• Wiadra będą oznaczone od # 1 do # N, będąc Nnajwiększą liczbą całkowitą na listach liczb całkowitych. Moje dziecko wciąż nie zna pojęcia zera.
• Możesz otrzymać dane wejściowe w dowolnym rozsądnym formacie, o ile reprezentuje zestaw stosów wiader. Po prostu określ to w swojej odpowiedzi, jeśli zmienisz sposób odbierania danych wejściowych.
• To jest golf golfowy , więc może wygrać najkrótszy program / funkcja dla każdego języka!

Przykłady

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)

Galaretka , 6 5 bajtów

Dzięki @Lynn za zapisanie 1 bajtu.

ṢFµJ⁼

Wypróbuj online! (pochodzi ze stopką pakietu testowego)

Wyjaśnienie

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

Dzięki za bajt xnor

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

Wypróbuj online!

JavaScript (ES6), 59 58 bajtów

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

Wyjaśnienie

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

Przypadki testowe

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 bajty

{˜āQ

Wypróbuj online!

Haskell , 54 bajty

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

Wypróbuj online!

Haskell , 37 bajtów

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

Wypróbuj online!

Sprawdza, czy konkatenowana lista posortowana jest leksykograficznie mniejsza niż lista nieskończona [1,2,3,...]. Ponieważ nie ma duplikatów, brakujący segment lub segment poza kolejnością spowodowałyby, że wartość byłaby większa niż kna kmiejscu, co spowodowałoby, że wynikowa lista byłaby większa.

Pyth, 6 bajtów

UItMsS

Wypróbuj tutaj.

Wyjaśnienie:

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 bajty

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

To jest to lepiej. Niestety, wciąż dość gadatliwy.

Wypróbuj online!

The s/1Orzecznik bierze jako argument listę i jest prawdziwa, jeśli lista jest listą łatwo wieżowych wiadrach.

Ulepszenie algorytmu: jeśli posortuję listę przed spłaszczeniem, wymusza to posortowanie wszystkich list podrzędnych, aby predykat był prawdziwy. Nieznacznie „pożyczony” z odpowiedzi Galaretki Pietu1998 . Dzięki temu mogę zrzucić forallco stanowi ponad połowę programu (oryginalna odpowiedź znajduje się poniżej).

Jak to działa?

Predykat jest prawdziwy, jeśli wszystkie jego klauzule są prawdziwe:

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

Poprzednia odpowiedź, PROLOG (SWI), 109 bajtów

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

Wypróbuj online!

Pyth , 9 16 11 bajtów (Naprawiono)

Używa zupełnie innej metody niż druga odpowiedź. Krótsze, 7-bajtowe podejście można znaleźć poniżej.

!.EtM.++0sS

Pakiet testowy.

Wyjaśnienie

! .EtM. ++ 0sSQ -> Pełny program, z niejawnym wejściem na końcu.

          SQ -> Posortuj dane wejściowe według najwyższego elementu w każdej liście podrzędnej.
         s -> Spłaszcz.
       +0 -> Przygotuj 0.
     . + -> Uzyskaj delty listy (tj. Różnice między kolejnymi elementami)
   tM -> Zmniejsz każdy element.
 .E -> Dowolny element zgodny z prawdą (1 to prawda, 0 to fałsz)
! -> Neguj (aby mieć spójne wartości prawda / fałsz)

Jak to działa?

Weźmy kilka przykładów, które ułatwiają zrozumienie. Załóżmy, że dane wejściowe to [[1,3,4],[5,7],[2,6]]. Rdzeń tego algorytmu polega na tym, że każda delta na nie spłaszczonej liście musi wynosić 1 , aby można było ustawiać w stosy.

• Po pierwsze Szamienia to w [[1, 3, 4], [2, 6], [5, 7]].

• Następnie sspłaszcza go: [1, 3, 4, 2, 6, 5, 7].

• Przygotuj z 0przodu:[0, 1, 3, 4, 2, 6, 5, 7]

• .+dostaje delty z listy [1, 2, 1, -2, 4, -1, 2].

• tMzmniejsza każdy element, [0, 1, 0, -3, 3, -2, 1].

• Każda 0liczba nie będąca liczbą całkowitą jest zgodna z prawdą w Pyth, więc sprawdzamy, czy istnieje jakiś element zgodny z prawdą .E(co oznacza, że ​​stos nie może zostać poprawnie uformowany). Dostajemy True.

• !neguje wynik, który zamienia się Truew False.

Gdyby na przykład wprowadzono dane, [[6,7,8,9,10],[1],[2],[3,4,5],[11,12,13]]algorytm działałby w ten sposób:

• Klasyfikowane według najwyższego elementu: [[1], [2], [3, 4, 5], [6, 7, 8, 9, 10], [11, 12, 13]]i spłaszczone, z 0poprzedzany: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13].

• Delty: [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]. Wszystko get zmniejszany: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0].

• Nie ma prawdziwego elementu, więc rozumiemy False. Wynikiem logicznej negacji jest True.

Pyth , 7 bajtów

qSlsQsS

Pakiet testowy.

Port odpowiedzi na Python i odmiana rozwiązania @ Erik .

Brachylog , 5 bajtów

oc~⟦₁

Wypróbuj online!

Wyjaśnione unifikacje:

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

Wyjaśnienie analityczne:

Najpierw sortujemy listę list, a następnie konkatenujemy (tj. Spłaszczamy 1 głębokość) ( oc), aby wiadra były układane od prawej do lewej, jeśli to możliwe. Następnie, aby sprawdzić, czy segmenty zostały prawidłowo ułożone w stos (tj. Brak brakujących segmentów lub wież), sprawdzamy, czy wynikowa lista zawiera zakres od 1 do jej długości. Teraz zamiast jednakowego sprawdzania listy z zakresem [1..n] jej długości ( {l⟦₁?}), staramy się znaleźć dane wejściowe do funkcji, która generuje taki zakres ( ~⟦₁), jeśli taki istnieje. Jeśli wejście zostanie znalezione, program kończy się bez problemów, więc wyzwala true.status. Jeśli nie zostanie znalezione żadne wejście, program nie powiedzie się, co spowoduje wyświetlenie false.statusu.

Python 2 , 43 bajty

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

Wypróbuj online!

Sprawdza, czy połączona posortowana lista jest leksykograficznie mniejsza niż [1,2,3,...N]dla dużych N. Ponieważ nie ma duplikatów, brakujący segment lub segment poza kolejnością spowodowałyby, że wartość byłaby większa niż kna kmiejscu, co spowodowałoby, że wynikowa lista byłaby większa. Długość łańcucha wejściowego wystarcza jako górna granica, ponieważ każda liczba zajmuje więcej niż 1 znak.

MATL , 5 bajtów

Sgtf=

Wypróbuj online!

(Powiedzmy, że dane niejawne {[4,5],[9,10],[1,2,3],[6,7,8]})

S- sortuj tablice wejściowe w kolejności leksykograficznej ( {[1,2,3],[4,5],[6,7,8],[9,10]})

g- przekształć w pojedynczą tablicę ( cell2mat)

t - powiel to

f- znaleźć wskaźniki wartości niezerowych. Ponieważ dane wejściowe są tutaj niezerowe, zwraca listę indeksów od 1 do długości (tablica) ( [1,2,3,4,5,6,7,8,9,10],[1,2,3,4,5,6,7,8,9,10])

= - sprawdź, czy tablica jest równa zakresowi od 1 do długości (tablica)

Japt , 13 12 11 bajtów

To może być prawdopodobnie krótsze.

ñÎc äaT e¥1

• 1 bajt zapisany dzięki ETH

Wypróbuj lub uruchom wszystkie przypadki testowe

Wyjaśnienie

                :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 bajtów

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

Nie golfowany:

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 bajtów

ñg c
eUÌõ

Wypróbuj online!

R , 58 bajtów

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

Wypróbuj online!

Uwaga: FAŁSZ to prawdziwy wynik, PRAWDA to fałsz

• -3 bajty dzięki @JayCe

Objaśnienie:

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 bajtów

-13 bajtów dzięki 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);}

Liczba bajtów obejmuje również

using System.Linq;

Wypróbuj online!

Nie golfowany:

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 bajtów

{$:+:(_,,=}

Wypróbuj online!

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

Węgiel drzewny , 19 bajtów (niekonkuruje?)

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

Wypróbuj online!

-10 bajtów dzięki tylko ASCII .

-3 bajty dzięki ASCII-tylko do kolejnej implementacji (patrz historia wersji dla wersji potencjalnie konkurencyjnej).

- dla prawdy za fałsz.

Dane wejściowe to lista pojedyncza listy list ze względu na sposób, w jaki węgiel drzewny przyjmuje dane wejściowe.

Java 10, 213 bajtów

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

Wypróbuj online.

Kiedy zaczynałem, wydawało mi się, że to dobry pomysł, ale te wbudowane elementy tylko wydłużają czas. Z pewnością można grać w golfa przy użyciu bardziej ręcznego podejścia.

Zainspirowany @EriktheOutgolfer jest 4-bajtowy 05AB1E odpowiedź . 4 vs 213 bajtów, rofl ..>.>

Wyjaśnienie:

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]