El gráfico cada vez mayor

23

Considere una secuencia unidimensional de números dentro de un rango fijo, es decir

[1, 2, 4, 6, 8, 0, 2, 7, 3] in range [0, 10⟩

El gráfico cada vez mayor * ** es una línea que conecta todos los puntos de esta secuencia de izquierda a derecha, y siempre sube o se mantiene nivelado. Si es necesario, la línea se envuelve de arriba a abajo y continúa subiendo desde allí para encontrar el siguiente punto.

El objetivo de este desafío es dividir la secuencia en diferentes subsecuencias que no son decrecientes, de modo que cuando se trazan junto con un eje vertical limitado, se formará un gráfico cada vez mayor. Esto se realiza agregando un punto al final de una subsecuencia y al comienzo de la siguiente subsecuencia, de modo que el ángulo de la línea que cruza el límite superior se alinee con la línea que cruza el límite inferior y los dos puntos de cruce tener la misma coordenada horizontal. El ejemplo anterior daría el siguiente resultado:

[1, 2, 4, 6, 8, 10]
[-2, 0, 2, 7, 13]
[-3, 3]

Y el gráfico correspondiente se verá de la siguiente manera: El gráfico cada vez mayor que en realidad debería llamarse Gráfico siempre no decreciente Y con el eje extendido para una mejor vista: Gráfico cada vez mayor que en realidad debería llamarse Gráfico siempre no decreciente con eje vertical extendido. La salida requerida es una lista de subsecuencias que forman las partes del Gráfico en constante aumento. No es necesario hacer una trama, pero te dará puntos de bonificación;). La salida debe separar claramente las subsecuencias de alguna manera.

Notas

  • El rango siempre tendrá cero como límite izquierdo (inclusive), y el límite derecho será algún número entero N.
  • La secuencia nunca contendrá valores que no estén dentro del rango.
  • La primera subsecuencia no tiene un punto adicional al principio.
  • La última subsecuencia no tiene un punto adicional al final.
  • No es necesario proporcionar los índices iniciales que serían necesarios para trazar las subsecuencias.

Casos de prueba

Input: [0, 2, 4, 6, 1, 3, 5, 0], 7
Output: [0, 2, 4, 6, 8], [-1, 1, 3, 5, 7], [-2, 0]
Input: [1, 1, 2, 3, 5, 8, 3, 1], 10
Output: [1, 1, 2, 3, 5, 8, 13],[-2, 3, 11],[-7, 1]
Input: [5, 4, 3, 2, 1], 10
Output: [5, 14],[-5, 4, 13],[-6, 3, 12],[-7, 2, 11],[-8, 1]
Input: [0, 1, 4, 9, 16, 15, 0], 17
Output: [0, 1, 4, 9, 16, 32], [-1, 15, 17], [-2, 0]

Tanteo

Este es el código de golf, gana el código más corto en bytes.

* No es una jerga real ** En realidad debería llamarse Gráfico nunca decreciente, como señaló @ngm, pero eso suena menos impresionante.

RvdV
fuente
77
Bienvenido a PPCG! ¡Buen primer desafío!
AdmBorkBork
1
Parece que entendí mal parte del desafío. Creo que esto debería ser lo que pretendías.
user202729
1
¿Puede extender el eje y en su gráfico de muestra por debajo de 0 y por encima de 10 para que el desafío sea más fácil de entender?
JayCe
@ JayCe Sí, buena sugerencia.
RvdV
2
El segundo caso de prueba sugiere que tiene la intención de que las secuencias no disminuyan, en lugar de aumentar. En otras palabras, un valor repetido en la entrada no detiene esa subsecuencia actual, y si los últimos dos valores en una subsecuencia son iguales que el "ángulo" para comenzar la siguiente subsecuencia es 0 (por lo que comenzaría con un valor repetido también)?
ngm

Respuestas:

8

R , 179 158 151 bytes

function(s,m){p=1;t=c(which(diff(s)<0),length(s));for(i in t){d=c(s[p]-m,s[(p+1):i],s[i+1]+m);if(p==1)d[1]=s[1];if(p==t[-1])d=head(d,-1);print(d);p=i}}

Pruébalo en línea!

Editar: El código ahora es una función y toma entrada. (Gracias a Giuseppe, user202729 y JayCe por señalarlo con calma)
Editar: -21 bytes sugeridos por Giuseppe.
Editar: -7 bytes eliminando d=NULL;.

Pensilvania
fuente
1
bienvenido a PPCG! Esta respuesta actualmente no es válida ya que debe recibir información de alguna manera (actualmente están codificados en el entorno). Además, puede encontrar útiles estos consejos para jugar golf en R. ¡Siéntete libre de hacerme ping aquí o en el chat una vez que obtengas suficiente reputación!
Giuseppe
Solo para tener claro lo que sería una presentación válida: esto sería . Bienvenido y disfruta tu tiempo aquí :)
JayCe
Creo que se s[p+1]-((m+s[p+1])-s[p])simplifica s[p]-m, y tienes d=c(c(...))donde solo d=c(...)se requiere. Sospecho firmemente que hay una forma más golfista, pero esta sigue siendo una buena respuesta.
Giuseppe
1
¿@PA dincluso necesita ser inicializado?
JayCe
1
@PA encantado de ayudar! Acabo de volver a abrir una sala de chat de golf R, así que no dude en ponerse en contacto conmigo y con todos los demás golfistas R para preguntas específicas que pueda tener :-)
Giuseppe
6

Python 2 , 60 bytes

La entrada es N, seguida de todos los puntos como argumentos individuales. Las subsecuencias en la salida están separadas por 0.5.

f=lambda N,k,*l:(k,)+(l and(l[0]+N,.5,k-N)*(l[0]<k)+f(N,*l))

Pruébalo en línea!


Python 2 , 92 77 68 bytes

Las subsecuencias están separadas por [...].

l,N=input();r=[];k=0
for a in l:r+=[a+N,r,k-N]*(a<k)+[a];k=a
print r

Pruébalo en línea!

ovs
fuente
1
Buen respuesta! Realmente me gusta el uso de la variable k para agregar elementos selectivamente, ¡aprendí algo nuevo aquí!
RvdV
4

Limpio , 279 269 258 bytes

import StdEnv
s=snd o unzip
$[]=[]
$l#(a,b)=span(uncurry(<))(zip2[-1:l]l)
=[s a: $(s b)]
?l n#[h:t]= $l
=[h:if(t>[])(?(map((+)n)(flatten t))n)t]
@l n#l= ?l n
=[[e-i*n\\e<-k]\\k<-[a++b++c\\a<-[[]:map(\u=[last u])l]&b<-l&c<-tl(map(\u=[hd u])l)++[[]]]&i<-[0..]]

Pruébalo en línea!

Οurous
fuente
4

Haskell, 82 81 80 bytes

Este es un puerto de mi respuesta limpia .

r!n|let f x(r@(a:_):s)|x>a=[x,n+a]:(x-n:r):s|y<-x:r=y:s=foldr f[[last r]]$init r

Pruébalo en línea!

-1, -1 gracias a Laikoni


fuente
@Laikoni es una pena que no podamos definir flocalmente sin paréntesis alrededor del :patrón, como en let x<r@(a:_):s|....
3

Limpio , 92 bytes

import StdEnv
@r n=foldr(\x[r=:[a:_]:s]|x>a=[[x,n+a]:[x-n:r]:s]=[[x:r]:s])[[last r]](init r)

Pruébalo en línea!

El argumento del operador foldres una lambda con guardia; se analiza como:

\x [r=:[a:_]:s]
    | x > a     = [[x,n+a]:[x-n:r]:s]
    | otherwise = [[x:run]:s]

Lo porté a Haskell .


fuente
2

Limpias , 110 109 104 100 97 bytes

import StdEnv
@[x:r]n=let$s=:[x:r]a|x<last a=[a++[n+x]: $s[last a-n]]= $r(a++[x]);$_ a=[a]in$r[x]

Pruébalo en línea!

-1 byte gracias a Keelan

Laikoni
fuente
1

JavaScript (Node.js) , 98 bytes

a=>m=>(r=[],b=[],a.map((e,i)=>e<a[--i]?(b[p](m+e),r[p](b),b=[a[i]-m,e]):b[p='push'](e)),r[p](b),r)

Pruébalo en línea! Esto es bastante más largo que la otra respuesta JS, pero utiliza un enfoque diferente.

Explicación sin golf y simplificada

g=(a,m)=>{
    // r is the final array of arrays to return.
    // b is the current subset of only ascending numbers.
    r=[],b=[];

    a.map((e,i)=>{
        if(e<a[i-1]){
            // if the current value is less than the previous one,
            // then we're descending, so start a new array b.
            // add the proper value to b to match slopes with the next
            b.push(m+e);
            // add r to b, and restart b with the starter value and the current value in a
            r.push(b);
            b=[a[i-1]-m,e];
        } else{
            // otherwise, we're ascending, so just addd to to b.
            b.push(e);
        }
    });
    r.push(b); // add the final b to r, and return r
    return r;
}
NinjaOsoMono
fuente