Ganzzahlige Intervalle maximal verlängern

14

Angenommen, Sie erhalten eine Reihe von sich nicht überschneidenden Intervallen von ganzen Zahlen [a1,b1],[a2,b2],[a3,b3],...,[aN,bN]. (Wo [a,b]ist die Menge der ganzen Zahlen größer als oder gleich aund kleiner als oder gleich b.)

Das Intervall bei Index Xumfasst bX - aX + 1Werte. Wir werden diese Nummer anrufen cX.

Vorausgesetzt, dass jedes Intervall entweder ...

  • unverändert (bleibt wie [aX,bX]),
  • nach rechts zur +Seite der Zahl die Linie verlängert durch cX(werden [aX,bX + cX]),
  • oder nach links in Richtung der -Seite der Linie verlängert durch cX(werden [aX - cX,bX]),

Wie viele Werte können maximal durch die Vereinigung aller aktualisierten Intervalle abgedeckt werden, da sie sich immer noch nicht überschneiden?

Schreiben Sie eine Funktion oder ein Programm, das eine Zeichenfolge der Form annimmt [a1,b1],[a2,b2],[a3,b3],...,[aN,bN]und dieses Maximum berechnet. Wenn Sie eine Funktion schreiben, geben Sie den Wert zurück. Wenn Sie ein vollständiges Programm schreiben, geben Sie stdin ein und geben Sie den Wert stdout aus (oder verwenden Sie die nächstgelegenen Alternativen).

Sie können davon ausgehen, dass alle Werte innerhalb der normalen vorzeichenbehafteten 32-Bit-Ganzzahlgrenzen liegen und dass diese aXkleiner oder gleich sindbX für alle Indizes sind X. Die Intervalle können in beliebiger Reihenfolge sein und müssen nicht immer größer sein. Sie müssen als Zeichenfolge im obigen Format angegeben werden. Die Zeichenfolge kann leer sein. In diesem Fall lautet die Antwort 0.

Die kürzeste Übermittlung in Bytes gewinnt.

Beispiel

Wenn die Eingabe [-3,0],[1,2],[4,9]wäre, wäre die Ausgabe 22. Das mittlere Intervall hat keinen Raum, um sich in irgendeiner Weise auszudehnen, so dass es unverändert bleiben muss. Die linke und rechte Intervalle können sowohl erweitert werden [-7,0]und [4,15]jeweils. Die Vereinigung von [-7,0]und [1,2]und [4,15]enthält alle Werte von -7 bis 15, mit Ausnahme von 3. Das sind 22 Werte.

code-golf set-theory Calvins Hobbys
quelle
3
Können wir die native Zeichenfolgendarstellung der Arrays unserer Sprache für die Eingabe verwenden, oder muss es genau dieses Format haben?
Martin Ender
@ MartinBüttner Nein. Sie müssen genau dieses Format verwenden. (Ich weiß, das ist eine Art zweischneidiges Schwert, aber so geht es.)
Calvins Hobbys
Können Sie ein bestimmtes Intervall auf beiden Seiten erweitern? Kann [5,6]zum Beispiel [3,8](für eine Antwort von 6) werden, oder kann es einfach sein [5,8]oder [3,6](für eine Antwort von 4)?
MtnViewMark
@MtnViewMark Nein. Sie können nur von einer Seite (oder gar nicht) verlängert werden
Calvins Hobbys

Antworten:

4

Haskell, 145 Bytes

import Data.List
x=maximum.map length.filter(nub>>=(==)).map concat.sequence.map(\[a,b]->[[2*a-b-1..b],[a..b],[a..2*b-a+1]]).read.('[':).(++"]")

Probeläufe:

λ: x ""
0

λ: x "[5,6]"
4

λ: x "[-3,0],[1,2],[4,9]"
22
MtnViewMark
quelle
1

R 282 278 269 247

Dies wurde sehr schnell zu einem großen Problem bei der Eingabe von Zeichenfolgen. Ich vermute, ich kann das besser spielen, aber im Moment ist mir die Zeit ausgegangen.

f=function(s){i=matrix(strtoi(strsplit(gsub('[^0-9,-]','',s),',')[[1]]),nrow=2);l=0;if((a<-length(b<-order(i[1,])))>0){if(a>1)i=i[,b];l=diff(i[,1:a])+1;x=c(t(i));for(n in 1:a)if(n==1|n==a|x[n]-l[n]>x[n+a-1]|x[n+a]+l[n]<x[n+1])l[n]=l[n]*2;};sum(l)}

Im Wesentlichen ist die Idee

  • Nehmen Sie die Zeichenfolge auf und verwandeln Sie sie in eine Matrix mit zwei Zeilen
  • Stellen Sie sicher, dass es in der richtigen Reihenfolge ist
  • Berechnen Sie die Unterschiede für jede Spalte
  • Verdoppeln Sie den ersten und den letzten Unterschied
  • Verdoppeln Sie die mittleren Unterschiede, wenn sie eine Lücke zum vorherigen oder nächsten haben, die groß genug ist
  • Gibt die Summe der Differenzen zurück

Edit: erkannte, dass ich die Zeichen ursprünglich falsch gezählt und dann ein paar Dinge neu angeordnet habe, um ein paar zu rasieren.

MickyT
quelle