Der immer größer werdende Graph

23

Betrachten Sie eine eindimensionale Folge von Zahlen innerhalb eines festgelegten Bereichs, d. H

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

Der immer größer werdende Graph * ** ist eine Linie, die alle Punkte in dieser Sequenz von links nach rechts verbindet und immer nach oben zeigt oder eben bleibt. Bei Bedarf wird die Linie von oben nach unten gewickelt und steigt von dort weiter an, um den nächsten Punkt zu erreichen.

Das Ziel dieser Herausforderung ist es, die Sequenz in verschiedene Teilsequenzen zu unterteilen, die alle nicht abnehmen, sodass sie, wenn sie zusammen mit einer begrenzten vertikalen Achse geplottet werden, einen immer größer werdenden Graphen bilden. Dies erfolgt durch Hinzufügen eines Punkts am Ende einer Teilsequenz und am Anfang der nächsten Teilsequenz, sodass der Winkel der Linie, die die obere Grenze kreuzt, mit der Linie, die die untere Grenze kreuzt, und den beiden Kreuzungspunkten übereinstimmt haben die gleiche horizontale Koordinate. Das obige Beispiel würde die folgende Ausgabe ergeben:

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

Und das entsprechende Diagramm sieht folgendermaßen aus: Der immer größer werdende Graph, der eigentlich als immer weniger werdender Graph bezeichnet werden sollte Und zur besseren Immer größer werdender Graph, der eigentlich als Immer kleiner werdender Graph mit erweiterter vertikaler Achse bezeichnet werden sollte. Übersicht mit erweiterter Achse: Die erforderliche Ausgabe ist eine Liste von Teilsequenzen, die die Teile des immer größer werdenden Diagramms bilden. Das Erstellen eines Plots ist nicht erforderlich, bringt Ihnen jedoch Bonuspunkte;). Die Ausgabe muss die Teilsequenzen in irgendeiner Weise klar trennen.

Anmerkungen

  • Der Bereich wird immer Null als linke (inklusive) Grenze haben, und die rechte Grenze wird eine ganze Zahl N sein.
  • Die Sequenz enthält niemals Werte, die nicht innerhalb des Bereichs liegen.
  • Die erste Teilsequenz hat am Anfang keinen zusätzlichen Punkt.
  • Die letzte Untersequenz hat am Ende keinen zusätzlichen Punkt.
  • Es ist nicht erforderlich, die Startindizes anzugeben, die zum Zeichnen der Teilsequenzen erforderlich wären.

Testfälle

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]

Wertung

Dies ist Code-Golf, der kürzeste Code in Bytes gewinnt.

* Nicht der eigentliche Jargon ** Eigentlich sollte man Ever Non-Decreasing Graph nennen, wie @ngm betont hat, aber das klingt weniger beeindruckend.

RvdV
quelle
7
Willkommen bei PPCG! Schöne erste Herausforderung!
AdmBorkBork
1
Sieht so aus, als hätte ich einen Teil der Herausforderung falsch verstanden. Ich denke, das sollte das sein, was du beabsichtigt hast.
user202729
1
Können Sie die y-Achse in Ihrem Beispieldiagramm unter 0 und über 10 erweitern, um die Herausforderung verständlicher zu machen?
JayCe
@ JayCe Ja, guter Vorschlag.
RvdV
2
Der zweite Testfall legt nahe, dass Sie beabsichtigen, dass die Sequenzen nicht abnehmen, sondern zunehmen. Mit anderen Worten, ein wiederholter Wert in der Eingabe stoppt diese aktuelle Teilsequenz nicht. Wenn die letzten beiden Werte in einer Teilsequenz gleich dem "Winkel" zum Starten der nächsten Teilsequenz sind, ist der Wert 0 (also würde er mit einem wiederholten Wert beginnen) auch)?
ngm

Antworten:

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

Probieren Sie es online!

Bearbeiten: Code ist jetzt eine Funktion und nimmt Eingaben entgegen. (Dank an Giuseppe, user202729 und JayCe für den ruhigen Hinweis)
Edit: -21 Bytes, vorgeschlagen von Giuseppe.
Bearbeiten: -7 Bytes durch Entfernen d=NULL;.

PA
quelle
1
Willkommen bei PPCG! Diese Antwort ist derzeit nicht gültig, da sie auf irgendeine Weise eingegeben werden muss (derzeit sind sie in der Umgebung fest codiert). Darüber hinaus finden Sie diese Tipps zum Golfen in R hilfreich. Wenn Sie genug Ruf haben, können Sie mich hier oder im Chat anpingen!
Giuseppe,
Nur um klar zu sein, was eine gültige Vorlage wäre: Dies wäre . Willkommen und genießen Sie Ihre Zeit hier :)
JayCe
Ich denke, s[p+1]-((m+s[p+1])-s[p])vereinfacht sich s[p]-m, und Sie haben, d=c(c(...))wo nur d=c(...)erforderlich ist. Ich vermute sehr, dass es einen golferischeren Weg gibt, aber dies ist immer noch eine schöne Antwort.
Giuseppe
1
@PA muss dnoch initialisiert werden?
JayCe
1
@PA hilft gerne weiter! Ich habe gerade einen R-Golf-Chatroom wiedereröffnet. Wenn Sie spezielle Fragen haben, können Sie sich gerne an mich und alle anderen R-Golfer wenden :-)
Giuseppe,
6

Python 2 , 60 Bytes

Die Eingabe ist N, gefolgt von allen Punkten als einzelne Argumente. Folgen in der Ausgabe werden durch getrennt 0.5.

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

Probieren Sie es online!


Python 2 , 92 77 68 Bytes

Folgen werden durch getrennt [...].

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

Probieren Sie es online!

ovs
quelle
1
Schöne Antwort! Mir gefällt die Verwendung der Variablen k zum selektiven Anhängen von Elementen sehr gut, ich habe hier etwas Neues gelernt!
RvdV
4

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

Probieren Sie es online!

Οurous
quelle
4

Haskell, 82 81 80 Bytes

Dies ist ein Port meiner Clean-Antwort .

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

Probieren Sie es online!

-1, -1 dank Laikoni


quelle
@Laikoni Es ist schade, dass wir nicht flokal definieren können, ohne Klammern um das :Muster, wie in let x<r@(a:_):s|....
3

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

Probieren Sie es online!

Das Operatorargument zu foldrist ein Lambda mit Wache; Es wird analysiert als:

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

Ich habe das nach Haskell portiert .


quelle
2

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

Probieren Sie es online!

-1 Byte dank Keelan

Laikoni
quelle
1

JavaScript (Node.js) , 98 Byte

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)

Probieren Sie es online!Dies ist viel länger als die andere Antwort von JS, aber es wird ein anderer Ansatz verwendet.

Ungolfed und vereinfachte Erklärung

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
quelle