Subcadena de mayor aumento

12

Dada una lista de enteros positivos, escriba código que encuentre la longitud de la sublista contigua más larga que está aumentando (no estrictamente). Esa es la sublista más larga, de modo que cada elemento es mayor o igual que el anterior.

Por ejemplo, si la entrada fue:

[1,1,2,1,1,4 4,5 5,3,2,1,1]

La sublista creciente más larga sería , por lo que obtendría .[1,1,4 4,5 5]4 4

Su respuesta se puntuará tomando su fuente como una lista de bytes y luego encontrando la longitud de la sublista creciente más larga de esa lista. Un puntaje más bajo es el objetivo. Los lazos se rompen a favor de los programas con menos bytes totales.

Ad Hoc Garf Hunter
fuente
¿Está bien devolver verdadero en lugar de 1? ¿Y tenemos que manejar una lista vacía?
Jo King
Para el primero, cualquiera que sea el meta consenso sobre el resultado numérico que puede hacer, no recuerdo Truehaber sido un sustituto, 1pero puede ser. Debería poder manejar la lista vacía (La salida es, por supuesto, 0).
Ad Hoc Garf Hunter
2
Casos de prueba sugeridas: [] => 0, [0] => 1, [3,2,1] => 1,[1,2,1,2] => 2
Sok
¿Te importaría profundizar un poco más en el 'puntaje'?
ouflak
1
@ouflak No estoy seguro de qué más hay que decir sobre el puntaje. Convierta su envío a una lista de bytes y páselo a través de su propio programa y ese es su puntaje. Si los puntajes son iguales, el desempate es el bytecount
Jo King,

Respuestas:

6

Pyth , puntaje 2 (8 bytes)

lefSIT.:

Pruébalo aquí!

Puntos de código [108, 101, 102, 83, 73, 84, 46, 58]. Otra solución más corta, leSI#.:puntajes 3, pero sus puntos de código son [108, 101, 83, 73, 35, 46, 58], en realidad, muy cercanos a un puntaje de 1. Reorganizar un poco puede ayudar a Nevermind, las subcadenas integradas son las .:que no se pueden reorganizar, por lo que la puntuación más baja debe ser 2 si el programa la utiliza.

¿Cómo?

lefSIT.:     Full program. Accepts either a list or a string from STDIN.
      .:     Substrings.
  f  T       Only keep those that are...
   SI        Sorting-Invariant.
le           Length of the last item.
Sr. Xcoder
fuente
5

Haskell , puntaje 2, 66 64 61 60 65 bytes

  • -2 bytes gracias a Max Yekhlakov
  • -1 byte gracias a nimi
  • +5 bytes para manejar la lista vacía
foldr1 max.g
g[]=[0]
g(x:y:z)|x>y=1: g(y:z)
g(_:y)|a:b<-g y=1+a:b

Pruébalo en línea! (se verifica a sí mismo).

Nunca pensé que podría obtener un puntaje de 2 con Haskell, ¡pero aquí estoy!

La función gcalcula las longitudes de todas las subcadenas crecientes de forma recursiva. foldr1 max.gtoma el máximo de esas longitudes ( foldr1 maxes equivalente a maximum, pero con una puntuación más baja).

Delfad0r
fuente
1
Parece que el espacio en blanco 1+a : bno es necesario, por lo que son 62 bytes.
Max Yekhlakov
@MaxYekhlakov Tienes razón, no sé cómo me perdí eso.
Delfad0r
Su código regresa 1para la lista vacía, donde debería regresar0
Jo King
@Jo King De hecho, me había perdido la discusión en los comentarios. Arreglando eso ahora.
Delfad0r
5

JavaScript (Node.js) , puntaje 3, 53 46 bytes puntaje 2, 51 50 bytes

-7 bytes gracias @Arnauld

+5 +4 espacios a cambio de -1 puntaje

a=> a.map($= p=n=>$=(p<=(p=n)?++ x:x=1)<$?$: x)&&$

Pruébalo en línea!

Asume una entrada no vacía. 61 bytes si se debe manejar una lista vacía. Puntuación 2 todavía.

a=> a.map($= p=n=>$=(p<=(p=n)?++ x:x=1)<$?$: x)&& a.length&&$

Pruébalo en línea!

... o 58 si falsese permite regresar . Puntuación 2 todavía.

a=> a.map($= p=n=>$=(p<=(p=n)?++ x:x=1)<$?$: x)&& a>[ ]&&$
Shieru Asakoto
fuente
Esto debería funcionar para 46 bytes y la misma puntuación.
Arnauld
1
@Arnauld agregó 5 espacios a su sugerencia para que ahora sea un puntaje 2
Shieru Asakoto
4

Cáscara , 5 bytes , puntuación = 2

00000000: bc6d 4cdc 14                   ▲mLġ≥

Pruébalo en línea!

Es poco probable que obtenga una puntuación inferior a 2 con Husk porque ġ1 tiene un punto de código realmente alto y debe haber algo antes para obtener el máximo y la longitud. Se podría intentar intentar usar múltiples funciones, pero \nsería antes de cualquier función auxiliar que tenga un punto de código realmente bajo, por lo que cualquier cosa después de esto crearía una secuencia de bytes creciente de al menos longitud 2.

1: Esta parece ser la mejor manera de usarla para los operadores de comparación que necesitarían seguir las diversas funciones divididas como ( span).

Explicación

▲mLġ≥  -- example input: [1,1,2,1,1,4,5,3,2,1,1]
   ġ≥  -- group elements by geq: [[1,1,2],[1,1,4,5],[3],[2],[1,1]]
 mL    -- map length: [3,4,1,1,2]
▲      -- maximum: 4
ბიმო
fuente
3

Retina 0.8.2 , 40 bytes, puntaje 3

\d+
$*
(?<=(1+)),(?!\1)
¶
T`1`_
^O`
\G,?

Pruébalo en línea! El enlace se incluye a sí mismo como códigos de bytes como entrada. Explicación:

\d+
$*

Convierte a unario.

(?<=(1+)),(?!\1)
¶

Dividir en pares decrecientes.

T`1`_

Eliminar los dígitos.

^O`

Ordena las comas en orden inverso. (Normalmente escribiría esto como O^pero no puedo hacer eso aquí por razones obvias).

\G,?

Cuente la ejecución de coma más larga y agregue una para incluir el número final.

Neil
fuente
3

Japt -h, 6 bytes, puntaje 2

No pienses que una puntuación de 1 es posible. También debería funcionar con cadenas y matrices de caracteres.

ò>¹mÊn

Pruébelo : el caso de prueba incluido es el código de la solución.


Explicación

ò          :Partition after each integer
 >         :  That's greater than the integer that follows it
  ¹        :End partition
   m       :Map
    Ê      :  Length
     n     :Sort
           :Implicitly output last element
Lanudo
fuente
3

MATL , puntaje 2, 13 bytes

d0< ~Y'w)X>sQ

La entrada puede ser:

  • Una serie de números.
  • Una cadena entre comillas simples. Las comillas simples dentro de la cadena se escapan duplicando.

MATL usa codificación ASCII. Los puntos de código del código anterior son

100, 48, 60, 32, 126, 89, 39, 119, 41, 88, 62, 115, 81

Pruébalo en línea!

Explicación

d     % Implicit input. Consecutive differences (of code points) 
0<    % Less than 0? Element-wise. Gives true or false
      % Space. This does nothing; but it breaks an increasing substring
~     % Negate
Y'    % Run-length encoding. Gives array of true/false and array of lengths
w     % Swap
)     % Index. This keeps only lenghts of runs of true values
X>    % Maximum. Gives empty array if input is empty
s     % Sum. This turns empty array into 0
Q     % Add 1. Implicit display
Luis Mendo
fuente
3

Pascal (FPC) , puntaje 2

111 bytes

var a,b,c,t:bYte;bEgIn repeat read(a); iNc(c); if a<b then c:=1; if c>t then t:= c;b:= a;until eOf;write(t)eNd.

Pruébalo en línea!

Asume una entrada no vacía. Los números se toman de la entrada estándar separados por espacios.

AlexRacer
fuente
2

Gelatina , 8 bytes , puntaje 2

Probablemente haya una solución de puntuación 1 de alguna manera ...

IṠµṣ-ZL‘

Pruébalo en línea!

Código fuente como una lista de valores de bytes:

[73, 205, 9, 223, 45, 90, 76, 252]

¿Cómo?

IṠµṣ-ZL‘ - Link: list of integers  e.g. [ 1, 1, 2, 1, 1, 4, 5, 3, 2, 1, 1]
I        - increments                    [ 0, 1,-1, 0, 3, 1,-2,-1,-1, 0]
 Ṡ       - sign                          [ 0, 1,-1, 0, 1, 1,-1,-1,-1, 0]
  µ      - start a new monadic chain (a low byte to stop score being 3)
    -    - literal minus one             -1
   ṣ     - split at                      [[0, 1], [0, 1, 1], [], [], [0]]
     Z   - transpose                     [[0, 0, 0], [1, 1], 1]
      L  - length                        3
       ‘ - increment                     4
Jonathan Allan
fuente
2

Perl 6 , puntaje 2, 46 bytes

{my&g=1+*×*;+max 0,|[\[&g]] [ |@_] Z>=0,|@_ }

Pruébalo en línea!

Maneja la lista vacía. El código original fue:

{my&g=1+*×*;+max 0,|[\[&g]] @_ Z>=0,|@_}

Entonces solo 5 bytes adicionales para reducir la puntuación a 2.

Editar: Ah, descubrí cómo eliminar la tarea , pero no puedo obtener esa puntuación por debajo de 3 debido a )]]...

Explicación:

{                                  }  # Anonymous code block
 my&g=     ;  # Assign to &g an anonymous Whatever lambda
      1+*×*   # That multiplies the two inputs together and adds 1
                            @_ Z  0,|@_   # Zip the list with itself off-set by one
                                >=        # And check if each is equal or larger than the previous
                                         # e.g. [5,7,7,1] => [1,1,1,0]
                    [\[&g]]  # Triangular reduce it by the function declared earlier
                          # This results in a list of the longest substring at each index
                          # e.g. [5,7,7,1] => [1,2,3,1]
            +max 0,|      # And return the max value from this list, returning 0 if empty
Jo King
fuente
Entonces [[&(*+*)]]funciona como [+]? Increíble ...
nwellnhof
@nwellnhof Sí, hay algunas advertencias como que no puedes tener ningún espacio en blanco ( en absoluto ), pero incluso puedes usarlo con Zy X. Pruébalo en línea!
Jo King
1
Iba a intentar algo como:{max 0,|.[[X..] ^$_ xx 2].map({+$_ if [<=] $_})}
Brad Gilbert b2gills
1

05AB1E , puntaje 3 (9 bytes )

Œʒ¥dP}éθg

Lo más probable es que sea una puntuación de 2 de alguna manera.

Puntos de código de los bytes del programa: [140,1,90,100,80,125,233,9,103](dos sublistas de longitud 3: [1,90,100]y [80,125,233])

Pruébalo en línea.

Explicación:

Œ            # Sublists
 ʒ   }       # Filter by:
  ¥          #  Take the deltas
   d         #  Check for each whether the number is >= 0
    P        #  And check if it was truthy for all deltas
      é      # Then sort by length
       θ     # Take the last element
        g    # And take its length as result
Kevin Cruijssen
fuente
1

Java (JDK) , puntaje 3, 94 bytes

a->{int m=0,p=0,x=0,i=0,n;while(i<a.length){n=a[i++];m=(p<=(p=n)?++x:(x=1)) <m?m:x;}return m;}

Pruébalo en línea!

Puerto de mi (con sugerencias de Arnauld) JS respuesta. etuin returny hilin whilehacen que sea imposible jugar golf para anotar 2.

for no se puede usar aquí porque:

  • ;for está ascendiendo
  • forno se puede usar al comienzo del cuerpo lambda (restricciones de alcance). Es posible envolverlo {}pero aparentemente usando whilebytes de guardado.
Shieru Asakoto
fuente
Iba a sugerir que posiblemente lo use \uen algunos lugares, pero luego debe haber 00seguido un dígito que es 3 de todos modos ...
ETHproductions
1

Powershell, puntuación 3, 44 bytes

($args|%{$i*=$_-ge$p;$p=$_;(++$i)}|sort)[-1]

Script de prueba:

$f = {

(
    $args|%{        # for each integer from argument list
        $i*=$_-ge$p # -ge means >=.
                    # This statement multiplies the $i by the comparison result.
                    # A result of a logical operator is 0 or 1.
                    # So, we continue to count a current sequence or start to count a new sequence
        $p=$_       # let $p stores a 'previous integer'
        (++$i)      # increment and return incremented as length of a current sequence
    }|sort          # sort lengthes 
)[-1]               # take last one (maximum)

}

@(
    ,(4, 1,1,2,1,1,4,5,3,2,1,1)
) | % {
    $e,$a = $_
    $r = &$f @a
    "$($r-eq$e): $r"
}

Salida:

True: 4

Explicación:

  • El script toma enteros como lista de argumentos ( spaltting ).
  • Cada número entero se asigna por una función a la legth de contiguous sub-list that is increasing (not strictly). Luego, la secuencia de comandos ordena alarga y toma un último (máximo) (...|sort)[-1].

Powershell 6, puntaje 3, 43 bytes

$args|%{$i*=$_-ge$p;$p=$_;(++$i)}|sort -b 1

Lo mismo que arriba. Una diferencia: sort -b 1es el acceso directo para sort -Bottom 1y significa 1 elemento desde el final de la matriz ordenada . Entonces no necesitamos un índice [-1].

mazzy
fuente
1

Python 2 , puntaje 5, 87 bytes puntaje 2, 101 93 92 101 bytes

lambda a,m=1,o=[1]:max(reduce(lambda B,c:[B[:-m]+[B[-m]+m],B+o][c[0]>c[m]],zip(a,a[m:]), o)) *(a>[ ])

Pruébalo en línea!

Ooops! Pensé que este era el código de golf por primera vez ...

Chas Brown
fuente
2
Puntuación de 5. ¡ Pruébelo en línea!
mypetlion
2
Sangra con pestañas para obtener una puntuación de 4.
mypetlion
@mypetition: D'oh! Pensé que esto era código golf ... editando mi respuesta ahora.
Chas Brown
Es curioso que eliminar la m=1,o=[1]pieza no termine guardando bytes una vez que reduzcamos el puntaje
Jo King
@Jo King: ¡Ríete! Tenía la esperanza de que al retorcerme de esa manera, podría saltar otro byte; pero no tanta suerte!
Chas Brown
0

Wolfram Language (Mathematica) , puntaje 3, 45 bytes

Max[Length/@SequenceCases[#,x_/;OrderedQ@x]]&

Pruébalo en línea!

SequenceCasesy OrderedQpor sí mismos dan una puntuación de 3, por lo que la puntuación no se puede mejorar sin cambiar significativamente el enfoque.

Misha Lavrov
fuente
La forma correcta de usar patrones nos haría hacerlo Max[Length/@SequenceCases[#,_?OrderedQ]]&, pero _?Ores una subsecuencia creciente de longitud 4. (Como está _?AnyCamelCaseCommand.)
Misha Lavrov
0

Java (JDK), 126 bytes, puntaje 6

Golfed

private static int l(byte[] o){int m=0;int c=1;int p=0;for(byte i:o){if(m<c){m=c;}if(i>=p){p= i;c++;}else{c=1;p=0;}}return m;}

Sin golf

private static int longest(byte[] input) {
    int maxc = 0;
    int consec = 1;
    int prev = 0;
    for (byte i : input) {
        if (maxc < consec) {
            maxc = consec;
        }
        if (i >= prev) {
            prev = i;
            consec++;
        }
        else {
            consec = 1;
            prev = 0;
        }
    }
    return maxc;
}

Entrada

[112, 114, 105, 118, 97, 116, 101, 32, 115, 116, 97, 116, 105, 99, 32, 105, 110, 116, 32, 108, 40, 98, 121, 116, 101, 91, 93, 32, 111, 41, 123, 105, 110, 116, 32, 109, 61, 48, 59, 105, 110, 116, 32, 99, 61, 49, 59, 105, 110, 116, 32, 112, 61, 48, 59, 102, 111, 114, 40, 98, 121, 116, 101, 32, 105, 58, 111, 41, 123, 105, 102, 40, 109, 60, 99, 41, 123, 109, 61, 99, 59, 125, 105, 102, 40, 105, 62, 61, 112, 41, 123, 112, 61, 32, 105, 59, 99, 43, 43, 59, 125, 101, 108, 115, 101, 123, 99, 61, 49, 59, 112, 61, 48, 59, 125, 125, 114, 101, 116, 117, 114, 110, 32, 109, 59, 125]
Jaden Lee
fuente
No debería byteserlo int, ya byteque estaría restringido a 8 bits?
Jo King
@JoKing No estoy exactamente seguro de lo que quieres decir. ¿Quiere decir que debería cambiar la clase de byte a int class?
Jaden Lee
Sí, ya que la entrada es una lista de enteros
Jo King,
0

Kotlin, puntaje 6, 119 bytes

 fun x(a : IntArray){var m=1;var k=0;var d=1;while(k<a.size-1){if(a[k]<=a[k+1])m++;else{if(d<m)d=m;m=1};k++};println(d)}

Probar en línea

Explicación

  1. Paso 1: verifique el valor anterior al siguiente valor
  2. Paso 2: Si el valor anterior es menor o igual, agregue más 1 siga haciendo mientras la condición sea verdadera
  3. Paso 3: verifique el conteo anterior con el siguiente conteo, mantenga el conteo más alto en la variable d.
Syed Hamza Hassan
fuente
Ok, lo tengo, lo editaré en breve.
Syed Hamza Hassan
Por favor, compruebe, he hecho una función en la que se puede dar entrada. Según mi respuesta de cadena de muestra sería [2,4,5,6,7,7,7] La ​​puntuación es 7.
Syed Hamza Hassan
He actualizado la puntuación y el enlace, por favor verifique.
Syed Hamza Hassan
Ok, le di actualizado.
Syed Hamza Hassan
Continuemos esta discusión en el chat .
Jo King
0

Kotlin, puntaje 4, 67 bytes

{a:IntArray->var i=0;var p=0;a.map{if(it<p){i=0};p=it;(++i)}.max()}

La idea principal es: transformar cada número entero en la longitud de subsecuencias contiguas que está aumentando (no estrictamente). Retorno máximo.

  • a.map{...} - para cada entero en la matriz hacer
  • if(it<p){i=0} - si el número entero actual es menor que un número entero anterior, reinicie el contador
  • p=it - almacenar el entero actual en el anterior
  • (++i) - contador de incremento y valor de retorno de la expresión
  • .max() - obtener el máximo de toda la longitud
mazzy
fuente
0

Ruby , 64 bytes

->e{e.size.downto(1).find{|l|e.each_cons(l).find{|c|c==c.sort}}}

Pruébalo en línea!

Idva
fuente
1
Tenga en cuenta que esto no es código de golf . Tu puntaje actual es 6. Además, su código no maneja la lista vacía (donde debería estar la salida 0)
Jo King