The Ever-Increasing Graph

Question

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.

Answer 1

Jelly, 20 bytes

⁹;+⁴,N¤j.x>ṭḷ
çƝF;Ṫ{

Try it online!

Subsequences are splitted by 0.5.

Answer 2

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

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

Answer 3

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[0]+N,.5,k-N)*(l[0]<k)+f(N,*l))

Try it online!

---

Python 2, 92 77 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!

Answer 4

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.

Answer 5

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

Try it online!

Answer 6

Haskell, 82 81 80 bytes

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

Answer 7

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.

Answer 8

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

Try it online!

-1 byte thanks to Keelan

Answer 9

Haskell, 82 bytes

(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!

Answer 10

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

Answer 11

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))+``

Try it online!