Sequências empilháveis

29

Você distribui cartas de 0 a 9 de um baralho uma vez, formando pilhas que começam em 0 e contam até 1.

  • Quando você recebe um 0, você o coloca na mesa para iniciar uma nova pilha.
  • Quando você distribui qualquer outra carta, você a empilha sobre uma carta com exatamente um valor menor, cobrindo-a. Se não houver tal carta, o baralho não é empilhável.

Dado um baralho, determine se ele pode ser empilhado quando distribuído na ordem dada. De maneira equivalente, dada uma lista de dígitos, decida se ele pode ser particionado em subsequências separadas, cada um dos formulários.0,1,..,k

Exemplo

Pegue o baralho 0012312425. As duas primeiras cartas são 0, então elas vão para a mesa:

Stacks: 00

  Deck: 12312425

Em seguida, lidamos com a 1, que continua a 0, não importa qual:

        1
Stacks: 00

  Deck: 2312425

Em seguida, lidamos com 2os que acabaram de colocar 1e os que estão 3em cima.

        3
        2
        1
Stacks: 00

  Deck: 12425

Em seguida, o 1, 2e colocado em cima da primeira pilha e 4sobre a segunda. 

        4
        3
        22
        11
Stacks: 00

  Deck: 25

Agora, precisamos colocar a 2, mas não há 1nenhuma pilha no topo. Portanto, esse deck não era empilhável.

Entrada: uma lista não vazia de dígitos de 0 a 9 ou uma sequência deles. Você não pode assumir que 0 sempre estará na entrada.

Saída : um dos dois valores consistentes distintos, um para sequências empilháveis ​​e outro para sequências não empilháveis

Casos de teste:

Empilhável:

0
01
01234
00011122234567890
012031
0120304511627328390

Não empilháveis:

1
021
0001111
0012312425
012301210
000112223

Por conveniência, como listas:

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

Agrupados:

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

Entre os melhores:

Mostrar snippet de código

code-golf sequence decision-problem subsequence xnor
fonte
Podemos assumir um limite no tamanho da lista?
orlp
@orlp Não há limite explícito.
Xnor
@xnor ele provavelmente está pedindo para justificar escrito int a[99]em C
Leaky Nun
@LuisMendo Você pode, eu digo "não vazio".
Xnor
@ xnor Ah, desculpe, eu não vi isso. A matriz pode ser baseada em 1? Ou seja, números de 1até10
Luis Mendo

Respostas:

6

Haskell , 55 bytes

Uma função anônima pegando uma lista de números inteiros e retornando a Bool.

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

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

Experimente online!

Como funciona

  • foldr(?)[]dobra seu argumento de lista da direita para a esquerda usando ?, começando com uma lista vazia. O resultado é a lista de números na lista que não coube em cima de um número anterior.
  • all(<1) testa se os únicos números que não se encaixam em cima de um número anterior são zeros.
  • m?lanexa um número ma uma lista lde números não ajustados. Se m+1já estiver na lista, agora pode ser removido conforme se encaixa m.
    • (p,r)<-span(/=m+1)ldivide a lista lem duas partes pe rna primeira instância do número m+1. Se não houver, a parte certa restará vazia.
    • m:p++drop 1rprecede màs partes divididas. Se rnão estiver vazio, deve começar com m+1, o qual é removido por drop 1.
Ørjan Johansen
fonte
Ótima idéia fazendo o empilhamento ao contrário! Tentei expandir sua ?recursivamente, mas obtive o mesmo comprimento .
Xnor
54 bytes comData.List.delete
H.PWiz 3/17/17
5

Casca , 9 bytes

Λ¬ḞS:o-→ø

Experimente online!

Retorna 1para decks empilháveis ​​e 0para decks não empilháveis.

Parece que Ørjan Johansen em sua resposta Haskell já apresentou o mesmo algoritmo, mas em Husk isso é obviamente muito mais conciso.

Explicação

Abordamos o problema de outro lado: vire o convés e faça pilhas descendentes. Se depois de passar por todo o baralho todas as pilhas tiverem um 0 no topo, o baralho será empilhável.

Λ¬Ḟ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
fonte
4

Geléia , 15 11 bytes

‘Ṭ€+\I>0FS¬

Experimente online!

Freira Furada
fonte
Uau muito bom. Funcionaria ‘Ṭ€+\I>0FṀsempre?
Jonathan Allan
@ JonathanAllan Bem, dada a regra de 2 valores consistentes, deveria.
Erik the Outgolfer
4

C (gcc), 74 73 bytes

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

Requer a matriz de entrada para marcar o final com -1. Exemplo de uso:

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
fonte
O que há de errado com a planície return r?
Leaky Nun
4

Retina , 42 bytes

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

Experimente online!

Explicação

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

Isso classifica os dígitos, de forma estável, pela frequência com que o mesmo dígito ocorreu antes. Com efeito, isso reúne as várias subsequências candidatas. A sequência resultante terá primeiro a primeira ocorrência de cada dígito e, em seguida, a segunda ocorrência de cada dígito e assim por diante. Em uma entrada empilhável, o resultado será semelhante a 0123...0123...0123..., onde cada uma dessas substrings pode terminar a qualquer momento.

É mais fácil determinar se a entrada tem esse tipo de padrão unário.

.
$*1,

Substituímos cada dígito n por n 1 s, seguido por uma vírgula para separar dígitos individuais.

^(,|1\1)+$

Finalmente, usamos uma referência direta para corresponder a consecutivas crescentes execuções de dígitos. Tentamos combinar a sequência inteira combinando uma única vírgula (representando um 0 , que inicia uma nova execução) ou combinando a coisa anterior precedida por uma adicional 1, que só funciona se o dígito atual for o sucessor do anterior.

Martin Ender
fonte
3

TI-Basic (série 83), 25 bytes (49 caracteres)

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

Como funciona

Leva a entrada como uma lista em Ans. Saídas 1para entradas empilháveis, 0caso contrário.

Para cada I, cumSum(Ans=I)calcula uma lista do número de vezes Ique ocorreu em cada segmento inicial; portanto, min(cumSum(Ans=I)≤cumSum(Ans=I-1))é apenas 1 se, em todas as posições, vimos I-1pelo menos quantas vezes I. A expressão geral é 1sempre que isso vale para cada um I.

Misha Lavrov
fonte
3

JavaScript (ES6), 61 45 40 bytes

Leva a entrada como uma lista.

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

Casos de teste

Mostrar snippet de código

Quão?

Para cada valor de 0 a 9 , registramos o número de pilhas disponíveis com o cartão anterior no topo. Esses contadores são armazenados em [-9] a [0] , onde a [] é a matriz de entrada original. O único contador que colide com os dados de entrada é um [0] , mas realmente não nos importamos com este, porque 1) cartões rotulados como 0 são sempre permitidos e precisam ser processados ​​separadamente de qualquer maneira e 2) o valor de entrada a [0 ] é processado antes de poder ser atualizado.

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
fonte
Você é mais rápido do que eu: o
Leaky Nun
@LeakyNun Você deve ter sido afastado por 20 minutos ...;)
Arnauld
2

MATL , 16 bytes

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

Entrada é uma matriz de números.

O código sai 1em STDOUT se a entrada é empilhável ou sai com um erro e esvazia a saída em STDOUT se a entrada não é empilhável.

Experimente online!

Luis Mendo
fonte
2

Retina , 110 bytes

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

Experimente online! O link inclui casos de teste. Não costumo usar $16...

Neil
fonte
2

Mathematica, 80 bytes

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

Python 2 , 69 61 55 47 46 bytes

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

Experimente online!

A saída é error/ no error.

TFeld
fonte
46 bytes
ovs 02/10
2

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}

Experimente online!

Função que aceita um vetor R; retorna TRUEpara empilhável e não empilhável FALSE.

Explicação:

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
fonte
2

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

1se isso funcionar; 0se não

Tive que puxar alguns negócios descolados para lidar com a mutabilidade de variáveis ​​em for-loops, tudo bem.

Quelklef
fonte
1

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

Experimente online! Uso: g.reverse $ [0,1,2]. Retorna Truepara entradas empilháveis ​​e Falseoutros.

Esta é uma solução recursiva que percorre uma determinada lista de trás para frente. Isso implementa a observação de que

  • a lista vazia é empilhável.
  • uma lista não vazia com prefixo re último elemento xé empilhável se rfor empilhável e xé zero ou ambos x-1aparecem em re rcom x-1removido também são empilháveis.
Laikoni
fonte
1

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

Retorna 0/ 1se está corretamente empilhável ou não.

Explicação:

Experimente aqui.

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
fonte
1

C, 248 bytes

Nota: Para imprimir o status de retorno, digite "echo $ status" no terminal

Status de retorno 0: Não empilhável

Status de retorno 1: empilhável

Explicação: Incrementa o elemento da matriz com o índice equivalente ao dígito mais atual na pilha. Em seguida, o programa verifica se esse elemento da matriz agora incrementado é maior que o elemento que o precede. Nesse caso, retorna 0. Caso contrário, se o programa chegar ao final da matriz, retornará 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
fonte
3
Bem-vindo ao Code Golf! Seu código e seu número de bytes devem corresponder, por isso, forneça uma versão completa do seu código. A versão ungolfed é a opcional.
Stephen
0

Gelatina , 15 bytes

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

Um link monádico que obtém uma lista de números inteiros não negativos e retorna 0se empilhável ou 1não empilhável.

Experimente online!

Quão?

œ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
fonte
Seu movimento: P: P
Leaky Nun
Heh, bem, eu duvido que eu iria bater 11 (ou 10 ?!) e tem que pegar no sono: D
Jonathan Allan
0

Japonês , 16 bytes

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

Teste online! Saídas falsepara empilháveis, truepara não empilháveis.

Explicação

 £   = 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
fonte
0

05AB1E , 25 bytes

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

O desafio não parece tão difícil, mas é bastante difícil no 05AB1E (pelo menos para mim ..)

Saídas 0se empilháveis ​​e 1se não empilháveis.

Experimente online ou verifique todos os casos de teste .

Explicação:

η             # 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
fonte
0

Java 8, 87 bytes

Em vez de criar as pilhas, apenas calculo se um elemento é invencível nos elementos anteriores e retorno 0 quando um elemento não empilhável é encontrado. Se eu chegar ao final, toda a cadeia é empilhável e 1 é retornado:

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

Experimente online!

Explicação:

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
fonte