30
\$\begingroup\$

My little kid has a toy like this:

Stacked

This toy consists of 10 stackable little buckets, that we are going to number from 1 (the smallest one) to 10 (the biggest one). Sometimes he makes small piles and the toy ends up like this:

Scattered

We can represent schematically the piles like this:

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

Or, put it another way:

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

This set of bucket piles is easily restackable to rebuild the original set (the first image) just by consecutively placing piles of smaller buckets inside piles of bigger buckets:

                             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

Nonetheless, sometimes my kid tries to build towers, or throws buckets away, and the piles end up being inconsistent and the original set cannot be rebuild just by placing one pile inside another. Examples of this:

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

Challenge

Given a list of lists of integers representing a set of bucket piles, return a truthy value if the lists represent an easily restackable set of piles, or falsey in any other case.

  • Input will be given as a list of lists of integers, representing the buckets from top to bottom for each stack.
  • There won't be empty starting piles (you won't get [[1,2,3],[],[4,5]] as input).
  • The total number of buckets can be any within a reasonable integer range.
  • My kid only has one set of buckets so there won't be duplicate elements.
  • You can select any two consistent (and coherent) values for truthy or falsey.
  • The buckets will be labelled from #1 to #N, being N the largest integer in the lists of integers. My kid still does not know the concept of zero.
  • You may receive the input in any reasonable format as long as it represents a set of piles of buckets. Just specify it in your answer if you change the way you receive the input.
  • This is , so may the shortest program/function for each language win!

Examples

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)
\$\endgroup\$
  • \$\begingroup\$ This comes from the sandbox. \$\endgroup\$ – Charlie Aug 4 '17 at 7:47
  • 2
    \$\begingroup\$ @Mr.Xcoder no, there won't be duplicate elements (my kid only has one set of buckets and they are all different. \$\endgroup\$ – Charlie Aug 4 '17 at 7:55
  • 1
    \$\begingroup\$ May we assume that bucket 1 is never missing? \$\endgroup\$ – PurkkaKoodari Aug 4 '17 at 8:50
  • 2
    \$\begingroup\$ @Pietu1998 bucket #1 can be missing, I just added a test case (in fact, the smallest bucket is the easiest to lose). \$\endgroup\$ – Charlie Aug 4 '17 at 8:54
  • 1
    \$\begingroup\$ The various Tower of Hanoi challenges are related (not duplicates) of this. \$\endgroup\$ – AdmBorkBork Aug 4 '17 at 15:04

20 Answers 20

12
\$\begingroup\$

Jelly, 6 5 bytes

Thanks to @Lynn for saving 1 byte.

ṢFµJ⁼

Try it online! (comes with test-suite footer)

Explanation

Ṣ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.
\$\endgroup\$
  • \$\begingroup\$ I think ṢFµJ⁼ works, but I haven’t thought about all the edge cases. \$\endgroup\$ – Lynn Aug 4 '17 at 8:40
  • \$\begingroup\$ @Lynn That works assuming bucket 1 isn't missing. I'm not sure if this is guaranteed by the OP. \$\endgroup\$ – PurkkaKoodari Aug 4 '17 at 8:49
  • \$\begingroup\$ @Lynn bucket #1 can be missing, yes. I just added a new test case. \$\endgroup\$ – Charlie Aug 4 '17 at 8:53
  • \$\begingroup\$ If there are buckets missing, then the sorted list will always contain numbers larger than J can return, guaranteeing false output. am I missing something? \$\endgroup\$ – Lynn Aug 4 '17 at 8:57
  • \$\begingroup\$ I think you can still use the 5-byte version with bucket #1 missing? \$\endgroup\$ – Erik the Outgolfer Aug 4 '17 at 8:58
8
\$\begingroup\$

Python 2, 53 52 bytes

Thanks for the byte xnor

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

Try it online!

\$\endgroup\$
  • \$\begingroup\$ I like that starting the sum at []. Pretty tricky \$\endgroup\$ – bioweasel Aug 4 '17 at 13:43
  • 2
    \$\begingroup\$ You can save a byte by starting the sum at [0] so that the range can start from 0. \$\endgroup\$ – xnor Aug 6 '17 at 7:00
5
\$\begingroup\$

JavaScript (ES6), 59 58 bytes

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

Explanation

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

Test cases

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

\$\endgroup\$
5
\$\begingroup\$

05AB1E, 4 bytes

{˜āQ

Try it online!

\$\endgroup\$
5
\$\begingroup\$

Haskell, 54 bytes

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

Try it online!

\$\endgroup\$
5
\$\begingroup\$

Haskell, 37 bytes

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

Try it online!

Checks whether the concatenated sorted list is lexicographically smaller than the infinite list [1,2,3,...]. Since there are no duplicates, any missing bucket or out-of-order bucket would cause a value greater than k in the k'th place, making the resulting list be bigger..

\$\endgroup\$
4
\$\begingroup\$

Pyth, 6 bytes

UItMsS

Try it here.

Explanation:

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)
\$\endgroup\$
  • \$\begingroup\$ Wat?! Add an explanation to the UI part, please \$\endgroup\$ – Mr. Xcoder Aug 4 '17 at 9:12
  • \$\begingroup\$ @Mr.Xcoder U <col> is range(len(A)), I <pfn> <any> <n-1:any> is A(B, ...) == B. \$\endgroup\$ – Erik the Outgolfer Aug 4 '17 at 9:14
  • \$\begingroup\$ Then I got terribly outgolfed >.<. I might golf mine, though. Genius, brilliant solution, now that I see how it works... Congrats! \$\endgroup\$ – Mr. Xcoder Aug 4 '17 at 9:14
  • \$\begingroup\$ @Mr.Xcoder It's really just searching the docs for stuff... \$\endgroup\$ – Erik the Outgolfer Aug 4 '17 at 9:51
  • \$\begingroup\$ No, it's not. I knew that U <col> is range(len(A)), but I didn't realise that porting the Python solution would be shorter... \$\endgroup\$ – Mr. Xcoder Aug 4 '17 at 9:52
4
\$\begingroup\$

PROLOG (SWI), 54 bytes

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

Now that's better. Still quite verbose, alas.

Try it online!

The s/1 predicate takes a list as argument and is true if the list is a list of easily stackable buckets.

Improvement in algorithm: if I sort the list before I flatten it, this forces all the sublists to be sorted for the predicate to be true. Slightly "borrowed" from Pietu1998's Jelly answer. Thanks to that I can dump the forall which is more than half of the program (see below for the original answer).

How does it work?

The predicate is true if all of its clauses are true:

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

Previous answer, 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))).

Try it online!

\$\endgroup\$
3
\$\begingroup\$

Pyth, 9 16 11 bytes (Fixed)

Uses a completely different method from the other answer. A shorter, 7-byte approach can be found below.

!.EtM.++0sS

Test Suite.


Explanation

!.EtM.++0sSQ  -> Full program, with implicit input at the end.

          SQ  -> Sort the input by the highest element in each sublist.
         s    -> Flatten.
       +0     -> Prepend a 0.
     .+       -> Get the deltas of the list (i.e. differences between consecutive elements)
   tM         -> Decrement each element.
 .E           -> Any truthy element (1s are truthy, 0s are falsy)
!             -> Negate (to have coherent truthy / falsy values)

How does this work?

Let's take a couple of examples, which make it easier to understand. Let's assume the input is [[1,3,4],[5,7],[2,6]]. The core of this algorithm is that each delta in the unflattened list must be 1 in order for the buckets to be stackable.

  • First off, S turns it into [[1, 3, 4], [2, 6], [5, 7]].

  • Then, s flattens it: [1, 3, 4, 2, 6, 5, 7].

  • Prepend a 0 in front: [0, 1, 3, 4, 2, 6, 5, 7]

  • .+ gets the deltas of the list, [1, 2, 1, -2, 4, -1, 2].

  • tM decrements each element, [0, 1, 0, -3, 3, -2, 1].

  • Any non-0 integer is truthy in Pyth, so we check if there is any truthy element with .E (which means the stack cannot be formed correctly). We get True.

  • ! negates the result, which turns True into False.

If the input was, for example, [[6,7,8,9,10],[1],[2],[3,4,5],[11,12,13]], the algorithm would work this way:

  • Sorted by the highest element: [[1], [2], [3, 4, 5], [6, 7, 8, 9, 10], [11, 12, 13]] and flattened, with a 0 prepended: [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]. All get decremented: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0].

  • There is no truthy element, so we get False. By logical negation, the result is True.


Pyth, 7 bytes

qSlsQsS

Test Suite.

Port of the Python answer and a variation of @Erik's solution.

\$\endgroup\$
  • \$\begingroup\$ Thank you very much for taking the time to explain how this works! \$\endgroup\$ – Charlie Aug 4 '17 at 8:31
  • \$\begingroup\$ Let us continue this discussion in chat. \$\endgroup\$ – Mr. Xcoder Aug 4 '17 at 8:48
  • \$\begingroup\$ @Mr.Xcoder What do you mean by tM decrements each element? I would think that decrementing each element of [1, 2, 1, -2, 4, -1, 2] would yield [0, 1, 0, -3, 3, -2, 1]. But that wouldn't help solve the problem, so I must be misunderstanding what decrementing each element means. \$\endgroup\$ – Brian J Aug 4 '17 at 19:15
  • \$\begingroup\$ @BrianJ tM decreases each element in the list by 1. There is a mistake in my explanation. Will fix. \$\endgroup\$ – Mr. Xcoder Aug 4 '17 at 19:16
  • \$\begingroup\$ @BrianJ Fixed. Thanks for spotting that \$\endgroup\$ – Mr. Xcoder Aug 4 '17 at 19:17
3
\$\begingroup\$

Brachylog, 5 bytes

oc~⟦₁

Try it online!

Explained unifications:

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

Analytical explanation:

First of all we sort the list of lists, and then we concatenate (i.e. flatten 1-deep) (oc) so that the buckets get stacked right-to-left if possible. Then, to check if the buckets have been stacked correctly (i.e. no missing buckets or towers), we check that the resulting list is an inclusive range from 1 to its length. Now, instead of equal-checking the list with the [1..n] range of its length ({l⟦₁?}), we try to find an input to a function that generates such a range (~⟦₁), if there is one. If an input is found, then the program ends with no issues, so it triggers a true. status. If no input is found, the program fails, triggering a false. status.

\$\endgroup\$
3
\$\begingroup\$

Python 2, 43 bytes

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

Try it online!

Checks whether the concatenated sorted list is lexicographically smaller than [1,2,3,...N] for large N. Since there are no duplicates, any missing bucket or out-of-order bucket would cause a value greater than k in the k'th place, making the resulting list be bigger. The string-length of the input suffices as an upper bound since each numbers takes more than 1 character.

\$\endgroup\$
  • \$\begingroup\$ Nice, I thought there should be a way to improve substantially on my solution, and this it it! \$\endgroup\$ – Chris_Rands Aug 7 '17 at 8:38
3
\$\begingroup\$

MATL, 5 bytes

Sgtf=

Try it online!

(Implicit input, say {[4,5],[9,10],[1,2,3],[6,7,8]})

S - sort input arrays in lexicographic order ({[1,2,3],[4,5],[6,7,8],[9,10]})

g - convert into a single array (cell2mat)

t - duplicate that

f - find indices of non-zero values. Since input here is all non-zeros, returns the list of indices from 1 to length(array) ([1,2,3,4,5,6,7,8,9,10],[1,2,3,4,5,6,7,8,9,10])

= - check that the array is equal to the range 1 to length(array)

\$\endgroup\$
3
\$\begingroup\$

Japt, 13 12 11 bytes

This could probably be shorter.

ñÎc äaT e¥1
  • 1 byte saved thanks to ETH

Try it or run all test cases


Explanation

                :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?
\$\endgroup\$
  • \$\begingroup\$ Yeah, you're right I think. It was worth a shot though \$\endgroup\$ – ETHproductions Aug 4 '17 at 14:20
  • \$\begingroup\$ I think you can save a byte on the last line with either ä-0 e¥J or än0 e¥1 \$\endgroup\$ – ETHproductions Aug 4 '17 at 16:34
  • \$\begingroup\$ Another similar 13-byte solution: ethproductions.github.io/japt/… \$\endgroup\$ – Oliver Aug 4 '17 at 16:38
  • \$\begingroup\$ @ETHproductions, I have no idea what's happening there! :D Don't think I've had occasion to touch ä for arrays yet. Thanks for the saving. \$\endgroup\$ – Shaggy Aug 4 '17 at 16:45
  • 1
    \$\begingroup\$ @LuisfelipeDejesusMunoz It works when you use the first line of this solution and the second line of the linked solution, just as I said, nine bytes: codegolf.stackexchange.com/a/168967/16484 \$\endgroup\$ – Nit Jul 20 '18 at 21:44
2
\$\begingroup\$

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
}
\$\endgroup\$
2
\$\begingroup\$

Japt, 9 bytes

ñg c
eUÌõ

Try it online!

\$\endgroup\$
  • \$\begingroup\$ Don't forget the new shortcut for g<space> ;) \$\endgroup\$ – Shaggy Jul 24 '18 at 14:50
2
\$\begingroup\$

R, 58 bytes

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

Try it online!

N.B. : FALSE is the truthy outcome, TRUE is the falsy one

  • -3 bytes thanks to @JayCe

Explanation :

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
\$\endgroup\$
  • 1
    \$\begingroup\$ Simply seq(a) for 2 byte?. Also, it's allowed to use TRUE as a falsy value and vice versa (just specify in your answer), so you can do any(a-seq(a)) for another byte. \$\endgroup\$ – JayCe Jul 20 '18 at 17:51
  • \$\begingroup\$ @JayCe: I'm a fool... I was so concerned about seq(a) behaving differently when a is of length 1 and I missed that in this case we'll get the same results :D THanks ! \$\endgroup\$ – digEmAll Jul 20 '18 at 19:37
1
\$\begingroup\$

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

-13 bytes thanks to 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);}

Byte count also includes

using System.Linq;

Try it 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
     };
\$\endgroup\$
  • 1
    \$\begingroup\$ x.First() -> x[0]? Enumerable.Range -> new int[] and Zip with index if possible..? Remove Where and place the condition into Any. \$\endgroup\$ – TheLethalCoder Aug 4 '17 at 10:05
  • \$\begingroup\$ @TheLethalCoder Thank you for the tips! And the new int[] approach would require adding a Select() to get the index, and ultimately make the byte count bigger. \$\endgroup\$ – Grzegorz Puławski Aug 4 '17 at 10:24
1
\$\begingroup\$

CJam, 11 bytes

{$:+:(_,,=}

Try it online!

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

\$\endgroup\$
1
\$\begingroup\$

Charcoal, 19 bytes (non-competing?)

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

Try it online!

-10 bytes thanks to ASCII-only.

-3 bytes thanks to ASCII-only for a subsequent implementation (see revision history for possibly competing version).

- for truthy, for falsy.

Input is a singleton list of a list of lists, because of how Charcoal takes input.

\$\endgroup\$
  • \$\begingroup\$ It's the first answer in Charcoal I see that uses UP. \$\endgroup\$ – Charlie Aug 5 '17 at 20:05
  • \$\begingroup\$ @CarlosAlejo I had to find a way to sort, and the easiest way was just UPsorted. \$\endgroup\$ – Erik the Outgolfer Aug 5 '17 at 20:06
  • \$\begingroup\$ 24 bytes \$\endgroup\$ – ASCII-only Aug 7 '17 at 1:54
  • \$\begingroup\$ the used there makes scope things the priority though so that;s why UP is still there but i guess you can just avoid using python function names as varnames? \$\endgroup\$ – ASCII-only Aug 7 '17 at 1:56
  • \$\begingroup\$ yay added eval as v, also O_O this isn't even an ascii art challenge (no wonder it's so ungolfy :P \$\endgroup\$ – ASCII-only Aug 8 '17 at 0:44
0
\$\begingroup\$

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

Try it online.

It seemed like a good idea when I started, but these builtins only make it longer.. Can definitely be golfed by using a more manual approach..

Inspired by @EriktheOutgolfer's 4-byte 05AB1E answer. 4 vs 213 bytes, rofl.. >.>

Explanation:

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]
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.