# The Ever-Increasing Graph

Consider a one-dimensional sequence of numbers within a fixed range, i.e.

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


The Ever-Increasing Graph* ** is a line that connects all the points in this sequence left to right, and always goes upwards or stays level. If necessary, the line wraps around from top to bottom and continues going up from there to meet the next point.

The goal of this challenge is to split the sequence in different subsequences that are all nondecreasing, so that when plotted together with a limited vertical axis they will form an Ever-Increasing Graph. This is done by adding an a point to the end of one subsequence and to the beginning of the next subsequence, so that the angle of the line that crosses the top boundary aligns with the line that crosses the bottom boundary, and the two crossing points have the same horizontal coordinate. The example above would give the following output:

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


And the corresponding graph will look as follows: And with the axis extended for a better view: The required output is a list of subsequences that form the parts of the Ever-Increasing Graph. Making a plot is not required but will earn you bonus points ;). The output must clearly separate the subsequences in some way.

Notes

• The range will be always have zero as the left (inclusive) boundary, and the right boundary will be some integer N.
• The sequence will never contain values that are not within the range.
• The first subsequence does not have an additional point at the beginning.
• The last subsequence does not have an additional point at the end.
• It is not required to provide the starting indices that would be required to plot the subsequences.

Test cases

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]


Scoring

This is code-golf, the shortest code in bytes wins.

*Not actual jargon **Actually should be called Ever Non-Decreasing Graph, as @ngm pointed out, but that sounds less impressive.

• Welcome to PPCG! Nice first challenge! May 18, 2018 at 12:15
• Looks like that I misunderstood some part of the challenge. I think this should be what you intended. May 18, 2018 at 13:22
• Can you extend the y axis in your sample graph below 0 and above 10 to make the challenge easier to understand? May 18, 2018 at 15:20
• @JayCe Yes, good suggestion.
– RvdV
May 18, 2018 at 16:11
• The second test case suggests you intend the sequences to be non-decreasing, as opposed to increasing? In other words, a repeated value in the input doesn't stop that current subsequence, and if the last two values in a subsequence are equal than the "angle" to start the next subsequence is 0 (so it would start with a repeated value as well)?
– ngm
May 18, 2018 at 18:27

# R, 179158 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=s;if(p==t[-1])d=head(d,-1);print(d);p=i}}


Try it online!

Edit: Code is now a function and takes input. (Thanks to Giuseppe, user202729 and JayCe for calmly pointing that out)
Edit: -21 bytes suggested by Giuseppe.
Edit: -7 bytes by removing d=NULL;.

• welcome to PPCG! This answer is currently not valid as it must take input in some manner (currently they are hard-coded in the environment). Additionally, you may find these tips for golfing in R helpful. Feel free to ping me here or in chat once you get enough reputation! May 18, 2018 at 13:30
• Just to be clear on what would be a valid submission: this would be. Welcome and enjoy your time here :) May 18, 2018 at 13:47
• I think s[p+1]-((m+s[p+1])-s[p]) simplifies to s[p]-m, and you have d=c(c(...)) where only d=c(...) is required. I strongly suspect there's a golfier way but this is still a nice answer. May 18, 2018 at 16:39
• @P.A does d even need to be initialized? May 18, 2018 at 17:22
• @P.A happy to help! I just re-opened an R golfing chatroom so feel free to get in touch with me and all the other R golfers for specific questions you might have :-) May 18, 2018 at 17:43

# Python 2, 60 bytes

Input is N, followed by all points as individual arguments. Subsequences in the output are seperated by 0.5.

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


Try it online!

# Python 2, 9277 68 bytes

Subsequences are seperated by [...].

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


Try it online!

• Nice anwser! I really like the use of the variable k for selectively appending items, learned something new here!
– RvdV
May 18, 2018 at 13:23

# Clean, 279269 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..]]


Try it online!

# JavaScript (Node.js), 104 82 bytes

n=>a=>a.map((e,i)=>e>a[s.push(e),++i]&&s.push(a[r.push(s=[e-n]),i]+n),r=[s=[]])&&r


Try it online! Port of @ovs's Python answer.

This is a port of my Clean answer.

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  Try it online! -1, -1 thanks to Laikoni • @Laikoni it's a pity we cannot define f locally without parentheses around the : pattern, as in let x<r@(a:_):s|.... – user42682 May 18, 2018 at 21:26 # Jelly, 20 bytes ⁹;+⁴,N¤j.x>ṭḷ çƝF;Ṫ{  Try it online! Subsequences are splitted by 0.5. # Clean, 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)  Try it online! The operator argument to foldr is a lambda with guard; it is parsed as: \x [r=:[a:_]:s] | x > a = [[x,n+a]:[x-n:r]:s] | otherwise = [[x:run]:s]  I ported this to Haskell. # Clean, 110109104100 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]


Try it online!

-1 byte thanks to Keelan

(x:r)#n|let b@(a:_)%s@(x:r)|x<a=(n+x:b):[a-n]%s|c<-x:b=c%r;a%_=[a]=reverse<$>[x]%r  Try it online! Port of my Clean answer. ### Alternative, also 82 bytes (x:r)#n|let a%s@(x:r)|x<last a=(a++[n+x]):[last a-n]%s|c<-a++[x]=c%r;a%_=[a]=[x]%r  Try it online! # 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)  Try it online! This is quite a bit longer than the other JS answer, but it uses a different approach. ## Ungolfed and simplified explanation 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; }  # JavaScript (Node.js), 48 bytes, arrays separated by ,, s=>n=>s.map(r=t=>(t<r?[t+n,,r-n,,]:)+(r=t))+  Try it online! # JavaScript (Node.js), 50 bytes, arrays separated by | s=>n=>s.map(r=t=>(t<r?t+n+|${r-n},:)+(r=t))+