Prolonger au maximum les intervalles entiers

14

Supposons que l'on vous donne un ensemble d' intervalles non entrecroisés d'entiers [a1,b1],[a2,b2],[a3,b3],...,[aN,bN]. (Où [a,b]est l'ensemble d'entiers supérieur ou égal à aet inférieur ou égal à b.)

L'intervalle à l'index Xcouvre les bX - aX + 1valeurs. Nous appellerons ce numéro cX.

Étant donné que chaque intervalle peut être soit ...

  • inchangé (reste inchangé [aX,bX]),
  • étendu vers la droite vers le +côté du numéro de la ligne en cX(devenant [aX,bX + cX]),
  • ou étendu vers la gauche vers le -côté du numéro de la ligne en cX(devenant [aX - cX,bX]),

quel est le nombre maximum de valeurs qui peuvent être couvertes par l'union de tous les intervalles mis à jour, étant donné qu'ils sont toujours tous sans intersection?

Écrivez une fonction ou un programme qui prend une chaîne du formulaire [a1,b1],[a2,b2],[a3,b3],...,[aN,bN]et calcule ce maximum. Si vous écrivez une fonction, renvoyez la valeur. Si vous écrivez un programme complet, utilisez stdin pour la saisie et imprimez la valeur sur stdout (ou utilisez les alternatives les plus proches).

Vous pouvez supposer que toutes les valeurs se situent bien dans les limites entières de 32 bits signées normales et qui aXest inférieure ou égale à bXpour tous les indices X. Les intervalles peuvent être dans n'importe quel ordre, ils n'augmentent pas nécessairement toujours. Ils doivent être donnés sous forme de chaîne dans le format ci-dessus. La chaîne peut être vide, auquel cas la réponse sera 0.

La soumission la plus courte en octets l' emporte.

Exemple

Si l'entrée était [-3,0],[1,2],[4,9]la sortie serait 22. L'intervalle intermédiaire n'a pas de place pour s'étendre dans un sens ou dans l'autre et doit donc rester inchangé. Les intervalles gauche et droit peuvent être étendus à [-7,0]et [4,15]respectivement. L'union de [-7,0]et [1,2]et [4,15]contient toutes les valeurs de -7 à 15, sauf 3. C'est 22 valeurs.

code-golf set-theory Loisirs de Calvin
la source
3
Pouvons-nous utiliser la représentation des chaînes natives des tableaux de notre langue pour l'entrée, ou doit-il être exactement ce format?
Martin Ender
@ MartinBüttner No. Vous devez utiliser ce format exact. (Je sais que c'est une sorte d'épée à double tranchant, mais c'est comme ça que ça se passe.)
Calvin's Hobbies
Pouvez-vous étendre un intervalle donné des deux côtés? Par exemple, peut [5,6]devenir [3,8](pour une réponse de 6), ou peut-il être juste [5,8]ou [3,6](pour une réponse de 4)?
MtnViewMark
@MtnViewMark Non. Ils ne peuvent être étendus que d'un côté (ou pas du tout)
Calvin's Hobbies

Réponses:

4

Haskell, 145 octets

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.('[':).(++"]")

Exemples de cycles:

λ: x ""
0

λ: x "[5,6]"
4

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

R, 282 278 269 247

Cela a pris de l'ampleur très rapidement en traitant l'entrée de chaîne. Je pense que je peux mieux jouer au golf, mais je n'ai plus de temps pour le moment.

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

L'idée est essentiellement

  • Prenez la chaîne et transformez-la en une matrice à 2 rangées
  • Assurez-vous qu'il est dans le bon ordre
  • Calculez les différences pour chaque colonne
  • Doublez la première et la dernière différence
  • Doublez les différences moyennes si elles ont un écart par rapport au précédent ou au suivant qui est suffisamment grand
  • Renvoie la somme des différences

Edit: réalisé que j'avais mal compté les caractères à l'origine, puis réarrangé quelques choses pour en raser quelques-unes.

MickyT
la source