Séquences empilables

29

Vous distribuez les cartes étiquetées de 0 à 9 à partir d'un paquet une par une, formant des piles qui commencent à 0 et comptent par 1.

  • Lorsque vous distribuez un 0, vous le placez sur la table pour démarrer une nouvelle pile.
  • Lorsque vous distribuez une autre carte, vous l'empilez au-dessus d'une carte qui a exactement une valeur inférieure, la couvrant. S'il n'y a pas une telle carte, le paquet n'est pas empilable.

Étant donné un paquet, déterminez s'il peut être empilé lorsqu'il est distribué dans l'ordre donné. De manière équivalente, étant donné une liste de chiffres, décidez si elle peut être partitionnée en sous-séquences disjointes chacune du formulaire0,1,..,k

Exemple

Prenez le pont 0012312425. Les deux premières cartes sont 0, donc elles vont sur la table:

Stacks: 00

  Deck: 12312425

Ensuite, nous traitons un 1, qui va sur un 0, peu importe lequel:

        1
Stacks: 00

  Deck: 2312425

Nous traitons ensuite un 2sommet du juste-placé 1et 3le dessus.

        3
        2
        1
Stacks: 00

  Deck: 12425

Ensuite, le 1, 2et placé au sommet de la première pile et 4au sommet de la seconde. 

        4
        3
        22
        11
Stacks: 00

  Deck: 25

Maintenant, nous devons placer un 2, mais il n'y a ni 1sommet ni pile. Donc, ce deck n'était pas empilable.

Entrée: une liste non vide de chiffres 0-9, ou une chaîne d'entre eux. Vous ne pouvez pas supposer que 0 sera toujours dans l'entrée.

Sortie : l'une des deux valeurs cohérentes distinctes, une pour les séquences empilables et une pour les séquences non empilables

Cas de test:

Empilable:

0
01
01234
00011122234567890
012031
0120304511627328390

Non empilable:

1
021
0001111
0012312425
012301210
000112223

Pour plus de commodité, sous forme de listes:

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

Regroupé:

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

Classement:

Afficher l'extrait de code

code-golf sequence decision-problem subsequence xnor
la source
Pouvons-nous supposer une limite sur la longueur de la liste?
orlp
@orlp Aucune limite explicite.
xnor
@xnor, il demande probablement de justifier l'écriture int a[99]en C
Leaky Nun
@LuisMendo Vous pouvez, je dis "non vide".
xnor
@xnor Ah, désolé, je n'ai pas vu ça. Le tableau peut-il être basé sur 1? Autrement dit, les chiffres de 1à10
Luis Mendo

Réponses:

6

Haskell , 55 octets

Une fonction anonyme prenant une liste d'entiers et renvoyant un Bool.

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

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

Essayez-le en ligne!

Comment ça marche

  • foldr(?)[]replie son argument de liste de droite à gauche en utilisant ?, en commençant par une liste vide. Le résultat est la liste des numéros de la liste qui ne correspondait pas au numéro précédent.
  • all(<1) teste si les seuls nombres qui ne correspondent pas au-dessus d'un nombre précédent sont des zéros.
  • m?lajoute un nombre mà une liste lde nombres non ajustés. Si m+1est déjà dans la liste, il peut maintenant être supprimé car il tient sur le dessus m.
    • (p,r)<-span(/=m+1)ldivise la liste len deux parties pet rà la première instance du numéro m+1. S'il n'y en a pas, la bonne partie rsera vide.
    • m:p++drop 1rajoute maux parties divisées. S'il rn'est pas vide, il doit commencer par m+1, qui est supprimé par drop 1.
Ørjan Johansen
la source
Excellente idée de faire l'empilement à l'envers! J'ai essayé de développer votre ?récursivement, mais j'ai la même longueur .
xnor
54 octets avecData.List.delete
H.PWiz
5

Coque , 9 octets

Λ¬ḞS:o-→ø

Essayez-le en ligne!

Renvoie les 1ponts empilables et les ponts 0non empilables.

Il semble que Ørjan Johansen dans sa réponse Haskell ait déjà proposé le même algorithme, mais dans Husk, c'est évidemment beaucoup plus concis.

Explication

Nous abordons le problème d'un autre côté: retournez le pont et faites des piles descendantes. Si après avoir traversé tout le deck, tous les tas ont un 0 en haut, le deck est empilable.

Λ¬Ḟ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)
Leo
la source
4

Gelée , 15 11 octets

‘Ṭ€+\I>0FS¬

Essayez-le en ligne!

Leaky Nun
la source
Ah, très bien. Fonctionnerait ‘Ṭ€+\I>0FṀtoujours?
Jonathan Allan,
@JonathanAllan Eh bien, étant donné la règle des 2 valeurs cohérentes, il devrait.
Erik the Outgolfer
4

C (gcc), 74 73 octets

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

Requiert le tableau d'entrée pour marquer la fin avec -1. Exemple d'utilisation:

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;
}
orlp
la source
Quel est le problème avec plain return r?
Leaky Nun
4

Rétine , 42 octets

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

Essayez-le en ligne!

Explication

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

Cela trie les chiffres, de manière stable, selon la fréquence à laquelle ce même chiffre s'est produit auparavant. En effet, cela rassemble les différentes sous-séquences candidates ensemble. La chaîne résultante aura d'abord la première occurrence de chaque chiffre, puis la deuxième occurrence de chaque chiffre et ainsi de suite. Dans une entrée empilable, le résultat ressemblera à quelque chose 0123...0123...0123..., où chacune de ces sous-chaînes peut se terminer à tout moment.

Il est plus facile de déterminer si l'entrée possède ce type de modèle en unaire.

.
$*1,

Nous remplaçons chaque chiffre n par n 1 s, suivi d'une virgule pour séparer les chiffres individuels.

^(,|1\1)+$

Enfin, nous utilisons une référence directe pour faire correspondre des séries de chiffres croissantes. Nous essayons de faire correspondre la chaîne entière soit en faisant correspondre une seule virgule (représentant un 0 , qui démarre une nouvelle exécution) soit en faisant correspondre la chose précédente précédée d'une autre 1, qui ne fonctionne que si le chiffre actuel est le successeur du précédent.

Martin Ender
la source
3

TI-Basic (série 83), 25 octets (49 caractères)

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

Comment ça marche

Prend l'entrée sous forme de liste Ans. Sorties 1pour entrées empilables, 0sinon.

Pour chacun I, cumSum(Ans=I)calcule une liste du nombre de fois où il Is'est produit dans chaque segment initial, ce min(cumSum(Ans=I)≤cumSum(Ans=I-1))n'est donc que 1 si, à chaque position, nous avons vu I-1au moins autant de fois que I. L'expression globale est 1chaque fois que cela vaut pour chacun I.

Misha Lavrov
la source
3

JavaScript (ES6), 61 45 40 octets

Prend la saisie sous forme de liste.

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

Cas de test

Afficher l'extrait de code

Comment?

Pour chaque valeur 0 ... 9 , nous gardons une trace du nombre de piles disponibles avec la carte précédente au sommet. Ces compteurs sont stockés dans un [-9] à un [0] , où un [] est le tableau d'entrée d'origine. Le seul compteur qui entre en collision avec les données d'entrée est un [0] , mais nous ne nous soucions pas vraiment de celui-ci car 1) les cartes étiquetées 0 sont toujours autorisées et doivent être traitées séparément de toute façon et 2) la valeur d'entrée a [0] ] est traité avant de pouvoir être mis à jour.

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
Arnauld
la source
Tu es plus rapide que moi: o
Leaky Nun
@LeakyNun Vous devez avoir été absent pendant 20 minutes ...;)
Arnauld
2

MATL , 16 octets

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

L'entrée est un tableau de nombres.

Le code sort 1dans STDOUT si l'entrée est empilable, ou se termine avec une erreur et une sortie vide dans STDOUT si l'entrée n'est pas empilable.

Essayez-le en ligne!

Luis Mendo
la source
2

Rétine , 110 octets

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

Essayez-le en ligne! Le lien inclut des cas de test. Je n'ai pas souvent l'occasion d'utiliser $16...

Neil
la source
2

Mathematica, 80 octets

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

R , 88 octets

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}

Essayez-le en ligne!

Fonction qui prend un vecteur R; renvoie TRUEpour empilable et FALSEpour non empilable.

Explication:

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.
}
Giuseppe
la source
2

Nim, 133 octets

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

1si ça marche; 0si ce n'est pas le cas.

J'ai dû tirer quelques affaires géniales pour faire face à la mutabilité des variables dans les boucles for, eh bien.

Quelklef
la source
1

Haskell , 77 75 octets

import Data.List
g[]=1<3
g(x:r)|s<-r\\[x-1]=g r&&(x<1||s/=r&&g s)
g.reverse

Essayez-le en ligne! Utilisation: g.reverse $ [0,1,2]. Renvoie les Trueentrées empilables et Falseautres.

Il s'agit d'une solution récursive qui parcourt une liste donnée d'arrière en avant. Il met en œuvre l'observation selon laquelle

  • la liste vide est empilable.
  • une liste non vide avec préfixe ret dernier élément xest empilable si elle rest empilable et si elle xest nulle ou si les deux x-1apparaissent dans ret ravec x-1supprimé est également empilable.
Laikoni
la source
1

Java 8, 168 150 142 octets

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

Renvoie 0/ 1s'il est correctement empilable ou non.

Explication:

Essayez-le ici.

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
Kevin Cruijssen
la source
1

C, 248 octets

Remarque: Pour imprimer l'état de retour, tapez "echo $ status" dans le terminal

Statut de retour 0: non empilable

Statut de retour 1: empilable

Explication: Incrémente l'élément de tableau avec l'index équivalent au chiffre le plus courant de la pile. Ensuite, le programme vérifie si cet élément de tableau qui vient d'être incrémenté est plus grand que l'élément qui le précède. Si tel est le cas, renvoie 0. Sinon, si le programme arrive à la fin du tableau, il renvoie 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;
}
T. Salim
la source
3
Bienvenue chez Code Golf! Votre code et votre bytecount doivent correspondre, alors assurez-vous de fournir une version complète de votre code. La version non golfée est la version facultative.
Stephen
0

Gelée , 15 octets

œp@ŒQẎµ0rṀ⁼Qµ¿Ẹ

Un lien monadique prenant une liste d'entiers non négatifs et retournant 0s'il est empilable ou 1s'il ne l'est pas.

Essayez-le en ligne!

Comment?

œ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.
Jonathan Allan
la source
Votre coup: P: P
Leaky Nun
Hé, eh bien je doute que j'aurais battu 11 (ou 10?!) Et que je dois m'endormir: D
Jonathan Allan
0

Japt , 16 octets

£=k_¥T©°T}T=0ÃUd

Testez-le en ligne! Sorties falsepour empilable, truepour non empilable.

Explication

 £   = 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.
ETHproductions
la source
0

05AB1E , 25 octets

ηε[DõQ#ZƒDNåiNõ.;Dëˆ#]¯OĀ

Le défi ne semble pas si difficile, mais c'est assez difficile en 05AB1E (pour moi au moins ..)

Sorties 0si empilables et 1si non empilables.

Essayez-le en ligne ou vérifiez tous les cas de test .

Explication:

η             # 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
Kevin Cruijssen
la source
0

Java 8, 87 octets

Au lieu de construire les piles, je calcule simplement si un élément est non empilable sur les éléments précédents et retourne 0 lorsqu'un élément non empilable est rencontré. Si j'atteins la fin, la chaîne entière est empilable et 1 est retourné:

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

Essayez-le en ligne!

Explication:

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
}
tfantonsen
la source