23
\$\begingroup\$

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: The Ever-Increasing Graph which should actually be called Ever Nondecreasing Graph And with the axis extended for a better view: Ever-Increasing Graph which should actually be called Ever Nondecreasing Graph with extended vertical axis. 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.

\$\endgroup\$
  • 7
    \$\begingroup\$ Welcome to PPCG! Nice first challenge! \$\endgroup\$ – AdmBorkBork May 18 '18 at 12:15
  • 1
    \$\begingroup\$ Looks like that I misunderstood some part of the challenge. I think this should be what you intended. \$\endgroup\$ – user202729 May 18 '18 at 13:22
  • 1
    \$\begingroup\$ Can you extend the y axis in your sample graph below 0 and above 10 to make the challenge easier to understand? \$\endgroup\$ – JayCe May 18 '18 at 15:20
  • \$\begingroup\$ @JayCe Yes, good suggestion. \$\endgroup\$ – RvdV May 18 '18 at 16:11
  • 2
    \$\begingroup\$ 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)? \$\endgroup\$ – ngm May 18 '18 at 18:27

11 Answers 11

3
\$\begingroup\$

Jelly, 20 bytes

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

Try it online!

Subsequences are splitted by 0.5.

\$\endgroup\$
8
\$\begingroup\$

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

\$\endgroup\$
  • 1
    \$\begingroup\$ 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! \$\endgroup\$ – Giuseppe May 18 '18 at 13:30
  • \$\begingroup\$ Just to be clear on what would be a valid submission: this would be. Welcome and enjoy your time here :) \$\endgroup\$ – JayCe May 18 '18 at 13:47
  • \$\begingroup\$ 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. \$\endgroup\$ – Giuseppe May 18 '18 at 16:39
  • 1
    \$\begingroup\$ @P.A does d even need to be initialized? \$\endgroup\$ – JayCe May 18 '18 at 17:22
  • 1
    \$\begingroup\$ @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 :-) \$\endgroup\$ – Giuseppe May 18 '18 at 17:43
6
\$\begingroup\$

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!

\$\endgroup\$
  • 1
    \$\begingroup\$ Nice anwser! I really like the use of the variable k for selectively appending items, learned something new here! \$\endgroup\$ – RvdV May 18 '18 at 13:23
4
\$\begingroup\$

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!

\$\endgroup\$
4
\$\begingroup\$

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.

\$\endgroup\$
4
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ @Laikoni it's a pity we cannot define f locally without parentheses around the : pattern, as in let x<r@(a:_):s|.... \$\endgroup\$ – user42682 May 18 '18 at 21:26
3
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

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

\$\endgroup\$
2
\$\begingroup\$

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!

\$\endgroup\$
1
\$\begingroup\$

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;
}
\$\endgroup\$
1
\$\begingroup\$

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!

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.