# 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.
}


import Data.List