O gráfico cada vez maior

23

Considere uma sequência unidimensional de números dentro de um intervalo fixo, ou seja,

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

O gráfico sempre crescente * ** é uma linha que conecta todos os pontos nessa sequência da esquerda para a direita e sempre sobe ou permanece nivelada. Se necessário, a linha passa de cima para baixo e continua subindo de lá para encontrar o próximo ponto.

O objetivo desse desafio é dividir a sequência em diferentes subseqüências que não diminuem, de modo que, quando plotadas em conjunto com um eixo vertical limitado, elas formem um gráfico sempre crescente. Isso é feito adicionando um ponto a ao final de uma subsequência e ao início da próxima, para que o ângulo da linha que cruza o limite superior se alinhe com a linha que cruza o limite inferior e os dois pontos de cruzamento. tem a mesma coordenada horizontal. O exemplo acima daria a seguinte saída:

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

E o gráfico correspondente terá a seguinte aparência: O gráfico sempre crescente, que na verdade deveria ser chamado de gráfico sempre decrescente E com o eixo estendido para uma melhor visualização: Gráfico sempre crescente, que na verdade deve ser chamado de Gráfico sempre não decrescente com eixo vertical estendido. A saída necessária é uma lista de subsequências que formam as partes do Gráfico cada vez maior. Não é necessário fazer um enredo, mas você ganhará pontos de bônus;). A saída deve separar claramente as subsequências de alguma forma.

Notas

  • O intervalo sempre terá zero como o limite esquerdo (inclusive), e o limite direito será algum número inteiro N.
  • A sequência nunca conterá valores que não estão dentro do intervalo.
  • A primeira subsequência não possui um ponto adicional no início.
  • A última subsequência não possui um ponto adicional no final.
  • Não é necessário fornecer os índices iniciais que seriam necessários para plotar as subsequências.

Casos de teste

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]

Pontuação

Isso é código-golfe, o código mais curto em bytes vence.

* Não é um jargão real ** Na verdade, deve ser chamado de Gráfico sempre não decrescente, como o @ngm apontou, mas isso parece menos impressionante.

RvdV
fonte
7
Bem-vindo ao PPCG! Bom primeiro desafio!
AdmBorkBork
1
Parece que eu não entendi uma parte do desafio. Eu acho que isso deveria ser o que você pretendia.
User202729 18/0118
1
Você pode estender o eixo y em seu gráfico de amostra abaixo de 0 e acima de 10 para facilitar o entendimento do desafio?
21418 JayCe
@ JayCe Sim, boa sugestão.
RvdV
2
O segundo caso de teste sugere que você pretende que as sequências não sejam decrescentes, em vez de aumentar? Em outras palavras, um valor repetido na entrada não interrompe a subsequência atual, e se os dois últimos valores em uma subsequência forem iguais ao "ângulo" para iniciar a próxima subsequência é 0 (portanto, iniciaria com um valor repetido também)?
Ng

Respostas:

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

Experimente online!

Editar: o código agora é uma função e recebe entrada. (Agradecimentos a Giuseppe, user202729 e JayCe por apontar isso com calma)
Editar: -21 bytes sugeridos por Giuseppe.
Edite: -7 bytes removendo d=NULL;.

PA
fonte
1
bem-vindo ao PPCG! Atualmente, esta resposta não é válida, pois precisa receber informações de alguma maneira (atualmente elas são codificadas no ambiente). Além disso, você pode encontrar essas dicas para golfe em R útil. Sinta-se à vontade para me enviar um ping aqui ou no bate-papo, uma vez que você tenha reputação suficiente!
Giuseppe
Apenas para esclarecer o que seria uma submissão válida: isso seria . Bem-vindo e desfrutar do seu tempo aqui :)
Jayce
Eu acho que s[p+1]-((m+s[p+1])-s[p])simplifica s[p]-m, e você tem d=c(c(...))onde apenas d=c(...)é necessário. Eu suspeito fortemente que exista uma maneira de jogar golfe, mas essa ainda é uma boa resposta.
Giuseppe
1
O @PA dprecisa mesmo ser inicializado?
Jayce
1
@PA feliz em ajudar! Eu só reabriu uma sala de chat R golfe tão à vontade para entrar em contato comigo e todos os outros golfistas R para perguntas específicas que você pode ter :-)
Giuseppe
6

Python 2 , 60 bytes

A entrada é N, seguida por todos os pontos como argumentos individuais. Subseqüências na saída são separadas por 0.5.

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

Experimente online!


Python 2 , 92 77 68 bytes

As subseqüências são 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

Experimente online!

ovs
fonte
1
Nice anwser! Eu realmente gosto do uso da variável k para acrescentar itens seletivamente, aprendi algo novo aqui!
RvdV
4

Limpos , 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..]]

Experimente online!

Furioso
fonte
4

Haskell, 82 81 80 bytes

Esta é uma porta da minha resposta limpa .

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

Experimente online!

-1, -1 graças a Laikoni


fonte
@Laikoni, é uma pena que não possamos definir flocalmente sem parênteses ao redor do :padrão, como em let x<r@(a:_):s|....
3

Limpo , 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)

Experimente online!

O argumento do operador para foldré um lambda com guarda; é analisado como:

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

Eu enviei isso para Haskell .


fonte
2

Limpo , 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]

Experimente online!

-1 byte graças a Keelan

Laikoni
fonte
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)

Experimente online! Isso é um pouco mais longo que a outra resposta JS, mas usa uma abordagem diferente.

Explicação não-gasta e 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;
}
NinjaBearMonkey
fonte