Stackable sequences

You deal cards labeled 0 to 9 from a deck one a time, forming stacks that start at 0 and count up by 1.

• When you deal a 0, you place it on the table to start a new stack.
• When you deal any other card, you stack it atop a card that's exactly one lower in value, covering it. If there's no such card, the deck isn't stackable.

Given a deck, determine whether it can be stacked when dealt in the order given. Equivalently, given a list of digits, decide whether it can be partitioned into disjoint subsequences each of the form 0,1,..,k

Example

Take the deck 0012312425. The first two cards are 0, so they go on the table:

Stacks: 00

Deck: 12312425


Next, we deal a 1, which goes on a 0, doesn't matter which:

        1
Stacks: 00

Deck: 2312425


We then deal a 2 atop the just-placed 1, and the 3 on top of it.

        3
2
1
Stacks: 00

Deck: 12425


Next, the 1, 2 and placed atop the first stack and 4 atop the second one.

        4
3
22
11
Stacks: 00

Deck: 25


Now, we need to place a 2, but there's no 1 atop either stack. So, this deck was not stackable.

Input: A nonempty list of digits 0-9, or a string of them. You can't assume that 0 will always be in the input.

Output: One of two distinct consistent values, one for stackable sequences and one for non-stackable ones

Test cases:

Stackable:

0
01
01234
00011122234567890
012031
0120304511627328390


Not stackable:

1
021
0001111
0012312425
012301210
000112223


For convenience, as lists:

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

[1]
[0, 2, 1]
[0, 0, 0, 1, 1, 1, 1]
[0, 0, 1, 2, 3, 1, 2, 4, 2, 5]
[0, 1, 2, 3, 0, 1, 2, 1, 0]
[0, 0, 0, 1, 1, 2, 2, 2, 3]


Grouped:

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


var QUESTION_ID=144201,OVERRIDE_USER=20260;function answersUrl(e){return"https://api.stackexchange.com/2.2/questions/144201/answers?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+ANSWER_FILTER}function commentUrl(e,s){return"https://api.stackexchange.com/2.2/answers/"+s.join(";")+"/comments?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+COMMENT_FILTER}function getAnswers(){jQuery.ajax({url:answersUrl(answer_page++),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){answers.push.apply(answers,e.items),answers_hash=[],answer_ids=[],e.items.forEach(function(e){e.comments=[];var s=+e.share_link.match(/\d+/);answer_ids.push(s),answers_hash[s]=e}),e.has_more||(more_answers=!1),comment_page=1,getComments()}})}function getComments(){jQuery.ajax({url:commentUrl(comment_page++,answer_ids),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){e.items.forEach(function(e){e.owner.user_id===OVERRIDE_USER&&answers_hash[e.post_id].comments.push(e)}),e.has_more?getComments():more_answers?getAnswers():process()}})}function getAuthorName(e){return e.owner.display_name}function process(){var e=[];answers.forEach(function(s){var r=s.body;s.comments.forEach(function(e){OVERRIDE_REG.test(e.body)&&(r="<h1>"+e.body.replace(OVERRIDE_REG,"")+"</h1>")});var a=r.match(SCORE_REG);a&&e.push({user:getAuthorName(s),size:+a[2],language:a[1],link:s.share_link})}),e.sort(function(e,s){var r=e.size,a=s.size;return r-a});var s={},r=1,a=null,n=1;e.forEach(function(e){e.size!=a&&(n=r),a=e.size,++r;var t=jQuery("#answer-template").html();t=t.replace("{{PLACE}}",n+".").replace("{{NAME}}",e.user).replace("{{LANGUAGE}}",e.language).replace("{{SIZE}}",e.size).replace("{{LINK}}",e.link),t=jQuery(t),jQuery("#answers").append(t);var o=e.language;/<a/.test(o)&&(o=jQuery(o).text()),s[o]=s[o]||{lang:e.language,user:e.user,size:e.size,link:e.link}});var t=[];for(var o in s)s.hasOwnProperty(o)&&t.push(s[o]);t.sort(function(e,s){return e.lang>s.lang?1:e.lang<s.lang?-1:0});for(var c=0;c<t.length;++c){var i=jQuery("#language-template").html(),o=t[c];i=i.replace("{{LANGUAGE}}",o.lang).replace("{{NAME}}",o.user).replace("{{SIZE}}",o.size).replace("{{LINK}}",o.link),i=jQuery(i),jQuery("#languages").append(i)}}var ANSWER_FILTER="!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe",COMMENT_FILTER="!)Q2B_A2kjfAiU78X(md6BoYk",answers=[],answers_hash,answer_ids,answer_page=1,more_answers=!0,comment_page;getAnswers();var SCORE_REG=/<h\d>\s*([^\n,]*[^\s,]),.*?(\d+)(?=[^\n\d<>]*(?:<(?:s>[^\n<>]*<\/s>|[^\n<>]+>)[^\n\d<>]*)*<\/h\d>)/,OVERRIDE_REG=/^Override\s*header:\s*/i;
body{text-align:left!important}#answer-list,#language-list{padding:10px;width:290px;float:left}table thead{font-weight:700}table td{padding:5px}
<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script> <link rel="stylesheet" type="text/css" href="//cdn.sstatic.net/codegolf/all.css?v=83c949450c8b"> <div id="answer-list"> <h2>Leaderboard</h2> <table class="answer-list"> <thead> <tr><td></td><td>Author</td><td>Language</td><td>Size</td></tr></thead> <tbody id="answers"> </tbody> </table> </div><div id="language-list"> <h2>Winners by Language</h2> <table class="language-list"> <thead> <tr><td>Language</td><td>User</td><td>Score</td></tr></thead> <tbody id="languages"> </tbody> </table> </div><table style="display: none"> <tbody id="answer-template"> <tr><td>{{PLACE}}</td><td>{{NAME}}</td><td>{{LANGUAGE}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr></tbody> </table> <table style="display: none"> <tbody id="language-template"> <tr><td>{{LANGUAGE}}</td><td>{{NAME}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr></tbody> </table>

• Can we assume a limit on the list length?
– orlp
Oct 1 '17 at 22:56
• @orlp No explicit limit.
– xnor
Oct 1 '17 at 22:58
• @xnor he's probably asking to justify writing int a[99] in C Oct 1 '17 at 23:00
• @LuisMendo You may, I say "nonempty".
– xnor
Oct 1 '17 at 23:22
• @xnor Ah, sorry, I didn't see that. Can the array be 1-based? That is, numbers from 1 to 10 Oct 1 '17 at 23:23

Python 2, 45 43 bytes

-2 bytes thanks to @TFeld

s=[]
for c in input():s+=c,-1;s.remove(c-1)


Try it online!

Husk, 9 bytes

Λ¬ḞS:o-→ø


Try it online!

Returns 1 for stackable decks and 0 for non-stackable decks.

It looks like Ørjan Johansen in his Haskell answer already came up with the same algorithm, but in Husk this is obviously much more concise.

Explanation

We takle the problem from another side: flip the deck and make descending piles. If after going through all the deck all the piles have a 0 on the top, the deck is stackable.

Λ¬ḞS:(-→)ø
ø    Starting with the empty list (each element of this list will be the top card
of a stack)
ḞS          Traverse the input from right to left. For each card:
-→        Remove the successor of this card from our list (if present)
:           Add this card to our list
Λ¬            At the end, check if all the cards in our list are zeroes (falsy)


An anonymous function taking a list of integers and returning a Bool.

Usage: (all(<1).foldr(?)[]) [0,1,2,3,4].

all(<1).foldr(?)[]
m?l|(p,r)<-span(/=m+1)l=m:p++drop 1r


Try it online!

How it works

• foldr(?)[] folds its list argument from right to left using ?, starting with an empty list. The result is the list of numbers in the list that didn't fit on top of a previous number.
• all(<1) tests if the only numbers not fitting on top of a previous number are zeroes.
• m?l prepends a number m to a list l of non-fitting numbers. If m+1 is already in the list, it can now be removed as it fits on top of m.
• (p,r)<-span(/=m+1)l splits the list l into two parts p and r at the first instance of the number m+1. If there aren't any, the right part r will be empty.
• m:p++drop 1r prepends m to the split parts. If r is nonempty, then it must start with m+1, which is removed by drop 1.
• Great idea doing the stacking in reverse! I tried expanding out your ? recursively, but got the same length.
– xnor
Oct 3 '17 at 0:05
• 54 bytes with Data.List.delete Oct 3 '17 at 14:30

Retina, 42 bytes

O$#(.)(?<=(\1.*?)*)$#2
.
$*1, ^(,|1\1)+$


Try it online!

Explanation

O$#(.)(?<=(\1.*?)*)$#2


This sorts the digits, stably, by how often that same digit has occurred before. In effect, this collates the various candidate subsequences together. The resulting string will first have the first occurrence of each digit, and then the second occurrence of each digit and so on. In a stackable input, the result will look something like 0123...0123...0123..., where each of these substrings may terminate at any point.

It's easiest to determine whether the input has this kind of pattern in unary.

.
$*1,  We replace each digit n by n 1s, followed by a comma to separate individual digits. ^(,|1\1)+$


Finally we make use of a forward reference to match consecutively increasing runs of digits. We try to match the entire string either by matching a single comma (representing a 0, which starts a new run) or by matching the previous thing preceded by an additional 1, which only works if the current digit is the successor of the previous one.

Jelly, 15 11 bytes

‘Ṭ€+\I>0FS¬


Try it online!

• Oh very nice. Would ‘Ṭ€+\I>0FṀ work always? Oct 1 '17 at 23:35
• @JonathanAllan Well, given the rule of 2 consistent values it should. Oct 2 '17 at 10:13

C (gcc), 74 73 bytes

f(int*l){int s[10]={},r=1;for(;~*l;s[*l++]++)r*=!*l||s[*l-1]--;return r;}


Requires the input array to mark the end with -1. Example usage:

int main(int argc, char** argv) {
int a[] = {0, 0, 0, 1, 1, 1, 2, 2, 2, 3, 4, 5, 6, 7, 8, 9, 0, -1};
printf("%d\n",  f(a));
return 0;
}

• What's wrong with plain return r? Oct 2 '17 at 0:53

TI-Basic (83 series), 25 bytes (49 characters)

:min(seq(min(cumSum(Ans=I)≤cumSum(Ans=I-1)),I,1,9


How it works

Takes input as a list in Ans. Outputs 1 for stackable inputs, 0 otherwise.

For each I, cumSum(Ans=I) computes a list of the number of times I has occurred in each initial segment, so min(cumSum(Ans=I)≤cumSum(Ans=I-1)) is only 1 if, at every position, we've seen I-1 at least as many times as I. The overall expression is 1 whenever this holds for each I.

JavaScript (ES6), 6145 40 bytes

Takes input as a list.

a=>a.every(k=>a[~k]=!k|a[-k]--&&-~a[~k])


Test cases

let f =

a=>a.every(k=>a[~k]=!k|a[-k]--&&-~a[~k])

console.log('[Truthy]');
console.log(f([0]))
console.log(f([0,1]))
console.log(f([0,1,2,3,4]))
console.log(f([0,0,0,1,1,1,2,2,2,3,4,5,6,7,8,9,0]))
console.log(f([0,1,2,0,3,1]))
console.log(f([0,1,2,0,3,0,4,5,1,1,6,2,7,3,2,8,3,9,0]))

console.log('[Falsy]');
console.log(f([1]))
console.log(f([0,2,1]))
console.log(f([0,0,0,1,1,1,1]))
console.log(f([0,0,1,2,3,1,2,4,2,5]))
console.log(f([0,1,2,3,0,1,2,1,0]))
console.log(f([0,0,0,1,1,2,2,2,3]))

How?

For each value 0...9, we keep track of the number of available stacks with the preceding card atop. These counters are stored in a[-9] to a[0], where a[] is the original input array. The only counter that collides with the input data is a[0], but we don't really care about this one because 1) cards labeled 0 are always allowed and have to be processed separately anyway and 2) the input value a[0] is processed before it has a chance to be updated.

a => a.every(k =>  // given the input array a, for each card k in a:
a[~k] =          // the card is valid if:
!k |           //   - it's a 0 or
a[-k]-- &&     //   - there's at least one stack with the card k-1 atop
-~a[~k]        // in which case we allow a new card k+1 and go on with the next card
)                  // otherwise, every() fails immediately

• You're faster than me :o Oct 1 '17 at 22:57
• a=>a.every(k=>a[a[~k]=-~a[~k],-k]--|!k)
– tsh
Jul 15 '21 at 3:10

Nim, 133 bytes

proc s(d:seq[int]):int=
var
t= @[0]
r=1
for c in d:(t.add(0);var f=0;for i,s in t.pairs:(if s==c:(t[i]=c+1;f=1;break));r*=f)
r


1 if it works; 0 if it doesn't.

Had to pull some funky business to deal with mutability of variables in for-loops, oh well.

• You don't need .pairs, it's called automatically. Jul 18 '21 at 18:45

MATL, 16 bytes

0*GQ"@yQy=f1)(]a


Input is an array of numbers.

The code outputs 1 in STDOUT if input is stackable, or exits with an error and empty output in STDOUT if input is not stackable.

Try it online!

Retina, 110 bytes

+0((.*?)1((.*?)2((.*?)3((.*?)4((.*?)5((.*?)6((.*?)7((.*?)8((.*?)9)?)?)?)?)?)?)?)?)?
$2$4$6$8$10$12$14$16$+ ^$


Try it online! Link includes test cases. I don't often get to use \$16...

Mathematica, 80 bytes

Catch[Fold[#~Join~{-1}/.{{p___,#2-1,q___}:>{p,#2,q},-1:>Throw[1<0]}&,{},#];1>0]&


Python 2, 69615547 46 bytes

s=[]
for c in input():s+=-1,;s[s.index(c-1)]=c


Try it online!

Output is error/ no error.

• 46 bytes
– ovs
Oct 2 '17 at 7:13

R, 88 bytes

function(d){s={}
for(e in d)if(!e)s=c(s,0)else{k=match(e,s+1)
if(is.na(k))T=F
s[k]=e}
T}


Try it online!

Function that takes an R vector; returns TRUE for stackable and FALSE for unstackable.

Explanation:

function(d){
s <- {}              # initialize the stacks as empty
for(e in d){         # iterate over the deck
if(!e)              # if e is zero
s <- c(s,0)        # start a new stack
else {              # otherwise
k <- match(e,s+1)  # find where e should go in s, NA if not there
if(is.na(k))       # if no match (unstackable)
T <- F            # set T to F (False)
s[k] <- e          # set s[k] to e
}
T                    # return the value of T, which is TRUE by default and only gets changed in the loop to F.
}


Haskell, 77 75 bytes

import Data.List
g[]=1<3
g(x:r)|s<-r\$x-1]=g r&&(x<1||s/=r&&g s) g.reverse  Try it online! Usage: g.reverse  [0,1,2]. Returns True for stackable inputs and False otherwise. This is a recursive solution which traverses a given list from back to front. It implements the observation that • the empty list is stackable. • a non-empty list with prefix r and last element x is stackable if r is stackable and either x is zero or both x-1 appears in r and r with x-1 removed is also stackable. C, 248 bytes Note: To print return status, type "echo status" into the terminal Return status 0: Not stackable Return status 1: Stackable Explanation: Increments array element with the index equivalent to the current-most digit in the stack. Then, the program checks if this just-now-incremented array element is larger than the element preceding it. If so, returns 0. Else if program makes it to the end of the array returns 1.  main(int argc, char ** argv) { static int stack[10]; while ( *++argv != 0x0 ) { stack[**argv - 0x30]++; if ( **argv - 0x30 > 0 ) { if ( stack[**argv - 0x30] > stack[**argv - 0x30 - 1] ) { return 0; } } } return 1; }  • Welcome to Code Golf! Your code and your bytecount should match, so make sure to provide a fully golfed version of your code. The ungolfed version is the optional one. Jul 30 '19 at 21:41 Java 8, 168150142 136 bytes a->{int x[]=new int[a.length],s=0,i;A:for(int n:a){if(n<1)s++;else{for(i=s;i-->0;)if(x[i]==n-1){x[i]=n;continue A;}return 0;}}return 1;}  -6 bytes thanks to @ceilingcat. Returns 0/1 whether it is correctly stackable or not. Explanation: Try it here. a->{ // Method with integer-array parameter & integer return-type int x[]=new int[a.length],// Array for the stacks, (max) size equal to input-size s=0, // Amount of stacks, starting at 0 i; // Index integer a:for(int n:a){ // Loop A over the input if(n<1) // If the current item is a zero: s++; // Increase amount of stacks s by 1 else{ // Else: for(i=s;i-->0;) // Inner loop (2) over the stacks if(x[i]==n-1){ // If a top item of a stack equals the current item - 1: x[i]=n; // Set this item in the stacks-array continue A;} // And go to the next iteration of loop A return 0;}} // If we haven't encountered a continue, return 0 return 1;} // Return 1 if we were able to correctly stack everything  Jelly, 8 bytes ‘Ṭ€+\I’Ȧ  Try it online! Essentially a port of my other answer, but with ‘ to handle zero-indexing Jelly, 15 bytes œp@ŒQẎµ0rṀ⁼Qµ¿Ẹ  A monadic link taking a list of non-negative integers and returning 0 if stackable or 1 if non-stackable. Try it online! How? œp@ŒQẎµ0rṀ⁼Qµ¿Ẹ - Link: list ¿ - while loop: µ µ - ...condition chain: 0 - literal zero Ṁ - maximum of current list r - inclusive range = [0,1,2,...,max(list)] Q - de-duplicate list (unique values in order of appearance) ⁼ - equal? - ...do: ŒQ - distinct sieve (1s at first occurrences 0s elsewhere) @ - use swapped arguments: œp - partition (the list) at truthy values (of the distinct sieve) Ẏ - tighten (makes the list flat again ready for the next loop) Ẹ - any truthy? 1 if the resulting list has any non-zero integers remaining - - effectively isNotEmpty for our purposes since a list of only - zeros gets reduced to an empty list via the loop.  • Your move :P :P Oct 1 '17 at 23:30 • Heh, well I doubt I'd beat 11 (or 10?!) and have to get to sleep :D Oct 1 '17 at 23:36 Japt, 16 bytes £=k_¥T©°T}T=0ÃUd  Test it online! Outputs false for stackable, true for non-stackable. Explanation  £ = k_ ¥ T© ° T}T=0Ã Ud UmX{U=UkZ{Z==T&&++T}T=0} Ud Ungolfed Implicit: U = input array UmX{ } For each item X in the array: T=0 Set T to 0. UkZ{ } Remove the items Z where Z==T&&++T Z == T (and if so, increment T). This has the effect of removing the largest stack. U= Reset U to the result. This process is repeated U.length times, which is evidently enough to handle any U. Ud Return whether there are any truthy items in U. Any items not part of a stack are non-zero/truthy, so this works for every possible case.  05AB1E, 25 bytes ηε[DõQ#ZƒDNåiNõ.;Dëˆ#]¯OĀ  The challenge doesn't look all that difficult, but it's quite hard in 05AB1E (for me at least..) Outputs 0 if stackable, and 1 if not stackable. Explanation: η # Prefixes of the (implicit) input # i.e. '012031' → ['0','01','012','0120','01203','012031'] # i.e. 021 → ['0','02','021'] ε # Map each to: [ # Start an infinite inner loop D # Duplicate the current value õQ# # If it's an empty String, stop the infinite loop Z # Get the maximum (without popping) # i.e. '01203' → 3 # i.e. '02' → 2 ƒ # Inner loop N in the range [0,max] D # Duplicate the current value Nåi # If it contains the current digit N # i.e. '01203' and 1 → 1 (truthy) # i.e. '02' and 1 → 0 (falsey) Nõ.; # Remove the first one (by replacing the first N with an empty string) # i.e. '1203' and 1 → '203' D # And duplicate it again for the next iteration of the inner loop ë # Else (does not contain the digit N): ˆ # Push N to the global stack # # And break the infinite loop ] # Close the if-else, inner loop, infinite loop, and mapping (short for }}}}) ¯ # Push the global stack O # Take the sum # i.e. [] → 0 # i.e. ['2'] → 2 Ā # And get the trutified value of that (which we implicitly output as result) # i.e. 0 → 0 # i.e. 2 → 1  Java 8, 87 bytes Instead of building the stacks I just calculate if an element is unstackable on the previous elements, and return 0 when an unstackable element is encountered. If I reach the end, the entire string is stackable and 1 is returned: s->{int l[]=new int[10];for(int n:s)if(n!=0&&l[n]>=l[n-1]||l[n]++<0)return 0;return 1;}  Try it online! Explanation: s->{ int l[]=new int[10]; # initialise the counts of each digit encountered prefix of element, all initialised to 0 for(int n:s) # Iterate over all entries in input if(n!=0&&l[n]>=l[n-1]||++l[n]<0) # Check if the element is stackable on the previous elements. Last check is always evaluated and false, but the sideeffect is to add the element to the handled, prefixed element og the next element. return 0; # Unstackable return 1; # No unstackable elements, so the result is stackable }  J, 25 23 bytes {{(-:\:~"1)+/\y=/i.10}}  -2 bytes thanks to Bubbler Note: No TIO for this version as it relies on newer J feater called direct definition {{...}} Working 24 byte TIO link Just a port of caird's great answer to make sure I understood it. • [:(-:\:~"1)[:+/$=/i.@10 is one byte shorter. Using J9 lambda (what is it actually called?) would save one more byte: {{(-:\:~"1)+/\y=/i.10}}` Jul 15 '21 at 6:11
• Thanks Bubbler. It's called Direct Definition according to Nuvoc. Jul 15 '21 at 14:25