Extienda al máximo los intervalos enteros

14

Supongamos que se le da un conjunto de que no se cortan intervalos de números enteros [a1,b1],[a2,b2],[a3,b3],...,[aN,bN]. (¿Dónde [a,b]es el conjunto de enteros mayor o igual que ay menor que o igual a b?)

El intervalo en el índice Xcubre bX - aX + 1valores. Llamaremos a este número cX.

Dado que cada intervalo puede ser ...

  • sin cambios (permanece como [aX,bX]),
  • extendido a la derecha hacia el +lado del número de la línea cX(convirtiéndose [aX,bX + cX]),
  • o extendido a la izquierda hacia el -lado del número de la línea cX(convirtiéndose [aX - cX,bX]),

¿Cuál es el número máximo de valores que puede cubrir la unión de todos los intervalos actualizados, dado que todavía no se cruzan?

Escriba una función o programa que tome una cadena de la forma [a1,b1],[a2,b2],[a3,b3],...,[aN,bN]y calcule este máximo. Si escribe una función, devuelva el valor. Si escribe un programa completo, use stdin para la entrada e imprima el valor en stdout (o use las alternativas más cercanas).

Puede suponer que todos los valores están dentro de los límites enteros normales de 32 bits con signo y que aXes menor o igual que bXpara todos los índices X. Los intervalos pueden estar en cualquier orden, no necesariamente siempre están aumentando. Deben darse como una cadena en el formato anterior. La cadena puede estar vacía, en cuyo caso la respuesta será 0.

La presentación más corta en bytes gana.

Ejemplo

Si la entrada fuera [-3,0],[1,2],[4,9]la salida sería 22. El intervalo medio no tiene espacio para expandirse de ninguna manera, por lo que debe permanecer sin cambios. Los intervalos izquierdo y derecho se pueden extender a [-7,0]y [4,15]respectivamente. La unión de [-7,0]y [1,2]y [4,15]contiene todos los valores desde -7 a 15, excepto 3. Eso es 22 valores.

code-golf set-theory Pasatiempos de Calvin
fuente
3
¿Podemos usar la representación de cadena nativa de las matrices de nuestro idioma para la entrada, o tiene que ser exactamente este formato?
Martin Ender
@ MartinBüttner No. Debe usar este formato exacto. (Sé que es una especie de espada de doble filo, pero así son las cosas.)
Calvin's Hobbies
¿Se puede ampliar un intervalo dado en ambos lados? Por ejemplo, puede [5,6]convertirse [3,8](para una respuesta de 6), o puede ser justo [5,8]o [3,6](para una respuesta de 4)?
MtnViewMark
@MtnViewMark No. Solo pueden extenderse desde un lado (o nada)
Calvin's Hobbies

Respuestas:

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

Ejecuciones de muestra:

λ: x ""
0

λ: x "[5,6]"
4

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

R, 282 278 269 247

Esto se hizo grande realmente rápido tratando con la entrada de cadena. Sospecho que puedo jugar golf mejor, pero en este momento se me acabó el tiempo.

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

Esencialmente la idea es

  • Tome la cuerda y conviértala en una matriz de 2 filas
  • Asegúrese de que esté en el orden correcto
  • Resolver las diferencias para cada columna.
  • Duplica la primera y la última diferencia
  • Duplique las diferencias medias si tienen una brecha con la anterior o la siguiente que sea lo suficientemente grande
  • Devuelve la suma de las diferencias.

Editar: me di cuenta de que originalmente contaba mal los caracteres, luego reorganicé algunas cosas para afeitarme algunas.

MickyT
fuente