Secuencias apilables

29

Reparte cartas etiquetadas de 0 a 9 de un mazo una por vez, formando pilas que comienzan en 0 y cuentan hasta 1.

  • Cuando reparte un 0, lo coloca en la mesa para comenzar una nueva pila.
  • Cuando repartes cualquier otra carta, la apilas sobre una carta que tiene exactamente un valor inferior, cubriéndola. Si no hay tal carta, el mazo no es apilable.

Dado un mazo, determina si se puede apilar cuando se reparte en el orden dado. De manera equivalente, dada una lista de dígitos, decida si puede dividirse en subsecuencias disjuntas de cada uno de los formularios.0,1,..,k

Ejemplo

Toma la cubierta 0012312425. Las dos primeras cartas son 0, así que van sobre la mesa:

Stacks: 00

  Deck: 12312425

A continuación, tratamos un 1, que sigue a un 0, no importa cuál:

        1
Stacks: 00

  Deck: 2312425

Luego tratamos 2encima de lo que acaba de colocar 1, y 3encima.

        3
        2
        1
Stacks: 00

  Deck: 12425

A continuación, el 1, 2y se coloca encima de la primera pila y 4la cima de la segunda. 

        4
        3
        22
        11
Stacks: 00

  Deck: 25

Ahora, necesitamos colocar un 2, pero no hay 1ninguna pila encima. Entonces, este mazo no era apilable.

Entrada: una lista no vacía de dígitos 0-9, o una cadena de ellos. No puede suponer que 0 siempre estará en la entrada.

Salida : uno de dos valores consistentes distintos, uno para secuencias apilables y otro para secuencias no apilables

Casos de prueba:

Apilable:

0
01
01234
00011122234567890
012031
0120304511627328390

No apilable:

1
021
0001111
0012312425
012301210
000112223

Por conveniencia, 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]

Agrupado:

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

Tabla de clasificación:

Mostrar fragmento de código

code-golf sequence decision-problem subsequence xnor
fuente
¿Podemos suponer un límite en la longitud de la lista?
orlp
@orlp Sin límite explícito.
xnor
@xnor probablemente esté pidiendo justificar la escritura int a[99]en C
Leaky Nun
@LuisMendo Puedes, digo "no vacío".
xnor
@xnor Ah, lo siento, no vi eso. ¿Puede la matriz estar basada en 1? Es decir, números de 1a10
Luis Mendo

Respuestas:

6

Haskell , 55 bytes

Una función anónima que toma una lista de enteros y devuelve 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

Pruébalo en línea!

Cómo funciona

  • foldr(?)[]dobla su argumento de lista de derecha a izquierda usando ?, comenzando con una lista vacía. El resultado es la lista de números en la lista que no cabía encima de un número anterior.
  • all(<1) prueba si los únicos números que no se ajustan sobre un número anterior son ceros.
  • m?lantepone un número ma una lista lde números no adecuados. Si m+1ya está en la lista, ahora se puede eliminar ya que cabe encima m.
    • (p,r)<-span(/=m+1)ldivide la lista len dos partes py ren la primera instancia del número m+1. Si no hay ninguno, la parte correcta restará vacía.
    • m:p++drop 1rantecede ma las partes divididas. Si rno está vacío, debe comenzar con m+1, que se elimina con drop 1.
Ørjan Johansen
fuente
¡Gran idea hacer el apilamiento a la inversa! Intenté expandir tu ?recursivamente, pero obtuve la misma longitud .
xnor
54 bytes conData.List.delete
H.PWiz
5

Casco , 9 bytes

Λ¬ḞS:o-→ø

Pruébalo en línea!

Devoluciones 1para mazos apilables y 0para mazos no apilables.

Parece que Ørjan Johansen en su respuesta de Haskell ya presentó el mismo algoritmo, pero en Husk esto es obviamente mucho más conciso.

Explicación

Abordamos el problema desde otro lado: volteamos la baraja y hacemos pilas descendentes. Si después de pasar por todo el mazo, todas las pilas tienen un 0 en la parte superior, el mazo es apilable.

Λ¬Ḟ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)
León
fuente
4

Jalea , 15 11 bytes

‘Ṭ€+\I>0FS¬

Pruébalo en línea!

Monja permeable
fuente
Oh, muy bien. ¿ ‘Ṭ€+\I>0FṀFuncionaría siempre?
Jonathan Allan
@JonathanAllan Bueno, dada la regla de 2 valores consistentes, debería.
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;}

Requiere la matriz de entrada para marcar el final con -1. Ejemplo 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
fuente
¿Qué hay de malo en simple return r?
Leaky Nun
4

Retina , 42 bytes

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

Pruébalo en línea!

Explicación

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

Esto ordena los dígitos, de manera estable, según la frecuencia con la que ese mismo dígito ha ocurrido antes. En efecto, esto recopila las diversas subsecuencias candidatas juntas. La cadena resultante tendrá primero la primera aparición de cada dígito, y luego la segunda aparición de cada dígito, y así sucesivamente. En una entrada apilable, el resultado se verá más o menos así 0123...0123...0123..., donde cada una de estas subcadenas puede terminar en cualquier punto.

Es más fácil determinar si la entrada tiene este tipo de patrón en unario.

.
$*1,

Reemplazamos cada dígito n por n 1 s, seguido de una coma para separar los dígitos individuales.

^(,|1\1)+$

Finalmente, hacemos uso de una referencia directa para que coincida con series de dígitos consecutivamente crecientes. Intentamos hacer coincidir toda la cadena ya sea haciendo coincidir una coma (que representa un 0 , que comienza una nueva ejecución) o haciendo coincidir lo anterior precedido por un adicional 1, que solo funciona si el dígito actual es el sucesor del anterior.

Martin Ender
fuente
3

TI-Basic (serie 83), 25 bytes (49 caracteres)

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

Cómo funciona

Toma la entrada como una lista en Ans. Salidas 1para entradas apilables, de lo 0contrario.

Para cada uno I, cumSum(Ans=I)calcula una lista de la cantidad de veces que Iha ocurrido en cada segmento inicial, por min(cumSum(Ans=I)≤cumSum(Ans=I-1))lo que solo es 1 si, en cada posición, hemos visto I-1al menos tantas veces como I. La expresión general es 1cuando esto se cumple para cada uno I.

Misha Lavrov
fuente
3

JavaScript (ES6), 61 45 40 bytes

Toma la entrada como una lista.

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

Casos de prueba

Mostrar fragmento de código

¿Cómo?

Para cada valor 0 ... 9 , hacemos un seguimiento del número de pilas disponibles con la carta anterior encima. Estos contadores se almacenan en un [-9] a un [0] , donde a [] es la matriz de entrada original. El único contador que colisiona con los datos de entrada es un [0] , pero realmente no nos importa este porque 1) las tarjetas etiquetadas como 0 siempre están permitidas y deben procesarse por separado de todos modos y 2) el valor de entrada a [0 ] se procesa antes de que pueda actualizarse.

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
fuente
Eres más rápido que yo: o
Leaky Nun
@LeakyNun Debes haber estado fuera durante 20 minutos ...;)
Arnauld
2

MATL , 16 bytes

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

La entrada es una matriz de números.

El código 1sale en STDOUT si la entrada es apilable, o sale con un error y vacía la salida en STDOUT si la entrada no es apilable.

Pruébalo en línea!

Luis Mendo
fuente
2

Retina , 110 bytes

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

Pruébalo en línea! El enlace incluye casos de prueba. No suelo usarlo $16...

Neil
fuente
2

Mathematica, 80 bytes

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

Pruébalo en línea!

Función que toma un vector R; devuelve TRUEapilables y apilables FALSE.

Explicación:

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

1si funciona; 0si no es así

Tuve que sacar algunos negocios extravagantes para lidiar con la mutabilidad de las variables en for-loops, oh, bueno.

Quelklef
fuente
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

Pruébalo en línea! Uso: g.reverse $ [0,1,2]. Devoluciones Truepara entradas apilables y de Falseotra manera.

Esta es una solución recursiva que atraviesa una lista dada de atrás hacia adelante. Implementa la observación de que

  • La lista vacía es apilable.
  • una lista no vacía con prefijo ry último elemento xes apilable si res apilable y xes cero o ambos x-1aparecen en ry rcon x-1eliminado también es apilable.
Laikoni
fuente
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;}

Devoluciones 0/1 si es correctamente apilable o no.

Explicación:

Pruébalo aquí.

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

C, 248 bytes

Nota: para imprimir el estado de devolución, escriba "echo $ status" en el terminal

Estado de retorno 0: no apilable

Estado de retorno 1: apilable

Explicación: Incrementa el elemento de matriz con el índice equivalente al dígito más actual en la pila. Luego, el programa verifica si este elemento de matriz incrementado ahora es más grande que el elemento que lo precede. Si es así, devuelve 0. De lo contrario, si el programa llega al final de la matriz, devuelve 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
fuente
3
¡Bienvenido a Code Golf! Su código y su bytecount deben coincidir, así que asegúrese de proporcionar una versión completa de su código. La versión sin golf es la opcional.
Stephen
0

Jalea , 15 bytes

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

Un enlace monádico que toma una lista de enteros no negativos y devuelve 0si es apilable o 1no apilable.

Pruébalo en línea!

¿Cómo?

œ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
fuente
Su movimiento: P: P
Leaky Nun
Je, bueno, dudo que gane 11 (¡¿o 10 ?!) y tenga que dormirme: D
Jonathan Allan
0

Japt , 16 bytes

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

¡Pruébelo en línea! Salidas falsepara apilables,true para no apilable.

Explicación

 £   = 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.
ETHproducciones
fuente
0

05AB1E , 25 bytes

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

El desafío no parece tan difícil, pero es bastante difícil en 05AB1E (al menos para mí ...)

Salidas 0si son apilables y 1si no apilables.

Pruébelo en línea o verifique todos los casos de prueba .

Explicación:

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

Java 8, 87 bytes

En lugar de construir las pilas, solo calculo si un elemento no es apilable en los elementos anteriores, y devuelvo 0 cuando se encuentra un elemento no apilable. Si llego al final, toda la cadena es apilable y se devuelve 1:

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

Pruébalo en línea!

Explicación:

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
fuente