Stackable sequences

Question

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

Leaderboard:

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>

Answer 1

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!

Answer 2

Haskell, 55 bytes

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.

Answer 3

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)

Answer 4

Jelly, 15 11 bytes

‘Ṭ€+\I>0FS¬

Try it online!

Answer 5

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

Answer 6

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.

Answer 7

JavaScript (ES6), 61 45 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

Answer 8

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.

Answer 9

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!

Answer 10

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

Answer 11

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.

Answer 12

Mathematica, 80 bytes

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

Answer 13

Python 2, 69 61 55 47 46 bytes

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

Try it online!

Output is error/ no error.

Answer 14

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

Answer 15

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.

Answer 16

Java 8, 168 150 142 bytes

a->{int x[]=new int[a.length],s=0,i;a:for(int n:a){if(n<1){s++;continue;}for(i=0;i<s;i++)if(x[i]==n-1){x[i]=n;continue a;}return 0;}return 1;}

Returns 0/1 whether it is correctly stackable or not.

Explanation:

Try it here.

a->{                         // Method with integer-array parameter and 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 (1) over the input
    if(n<1){                 //   If the current item is a zero:
      s++;                   //    Increase amount of stacks `s` by 1
      continue;}             //    And go to the next iteration
    for(i=0;i<s;i++)         //   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 (1)
    return 0;                //   If we haven't encountered a `continue`, return 0
  }                          //  End of loop (1)
  return 1;                  //  Return 1 if we were able to correctly stack everything
}                            // End of method

Answer 17

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

Answer 18

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.

Answer 19

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.

Answer 20

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.

Try it online or verify all test cases.

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

Answer 21

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
}