| Bytes | Lang | Time | Link |
|---|---|---|---|
| 009 | Japt | 170804T083808Z | Shaggy |
| 005 | Vyxal | 210828T085206Z | emanresu |
| 213 | Java 10 | 180724T135337Z | Kevin Cr |
| 005 | MATL | 180720T164040Z | Sundar R |
| 058 | R | 180720T171952Z | digEmAll |
| 009 | Japt | 180720T214539Z | Etheryte |
| 019 | Charcoal | 170805T142149Z | Erik the |
| 052 | Python 2 | 170804T081545Z | Chris_Ra |
| 037 | Haskell | 170806T071517Z | xnor |
| 043 | Python 2 | 170806T071110Z | xnor |
| 005 | Brachylog | 170805T134448Z | Erik the |
| 011 | CJam | 170805T133715Z | Erik the |
| 011 | Pyth | 170804T080255Z | Mr. Xcod |
| 049 | Scala | 170804T214345Z | Ethan |
| 054 | PROLOG SWI | 170804T081449Z | Nathan.E |
| 132 | C# .NET Core | 170804T095202Z | Grzegorz |
| 006 | Pyth | 170804T091107Z | Erik the |
| 005 | Jelly | 170804T074721Z | PurkkaKo |
| 054 | Haskell | 170804T090524Z | lynn |
| 004 | 05AB1E | 170804T090113Z | Erik the |
| 058 | JavaScript ES6 | 170804T080656Z | Arnauld |
Japt, 13 12 11 9 bytes
ñÎc mÉ e¶
- 1 byte saved thanks to ETH
ñÎc mÉ e¶ :Implicit input of 2D array
ñ :Sort by
Î : First element
c :Flatten
m :Map
É : Subtract 1
e :All
¶ : Equal to 0-based indices
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());}
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]
MATL, 5 bytes
Sgtf=
(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)
R, 58 bytes
function(v,a=unlist(v[order(sapply(v,min))]))any(a-seq(a))
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
Charcoal, 19 bytes (non-competing?)
A▷m⟦▷s▷vθυ⟧θ⁼θ…·¹Lθ
-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.
Haskell, 37 bytes
import Data.List
(<[1..]).concat.sort
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..
Python 2, 43 bytes
lambda l:sum(sorted(l),[0])<range(len(`l`))
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.
Brachylog, 5 bytes
oc~⟦₁
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.
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
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,
Sturns it into[[1, 3, 4], [2, 6], [5, 7]].Then,
sflattens it:[1, 3, 4, 2, 6, 5, 7].Prepend a
0in front:[0, 1, 3, 4, 2, 6, 5, 7].+gets the deltas of the list,[1, 2, 1, -2, 4, -1, 2].tMdecrements each element,[0, 1, 0, -3, 3, -2, 1].Any non-
0integer is truthy in Pyth, so we check if there is any truthy element with.E(which means the stack cannot be formed correctly). We getTrue.!negates the result, which turnsTrueintoFalse.
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 a0prepended:[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 isTrue.
Pyth, 7 bytes
qSlsQsS
Port of the Python answer and a variation of @Erik's solution.
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
}
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.
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))).
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;
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
};
Pyth, 6 bytes
UItMsS
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)
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.
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]]))