Estender ao máximo intervalos inteiros

14

Suponha que você receba um conjunto de intervalos sem interseção de números inteiros [a1,b1],[a2,b2],[a3,b3],...,[aN,bN]. (Onde [a,b]é o conjunto de números inteiros maior ou igual a ae menor ou igual a b.)

O intervalo no índice Xcobre bX - aX + 1valores. Ligaremos para este número cX.

Dado que cada intervalo pode ser ...

  • inalterado (permanece como [aX,bX]),
  • estendido para a direita em direção ao +lado do número da linha cX(tornando-se [aX,bX + cX]),
  • ou estendido para a esquerda em direção ao -lado do número da linha cX(tornando-se [aX - cX,bX]),

qual é o número máximo de valores que podem ser cobertos pela união de todos os intervalos atualizados, considerando que eles ainda são todos sem interseção?

Escreva uma função ou programa que use uma string do formulário [a1,b1],[a2,b2],[a3,b3],...,[aN,bN]e calcule esse máximo. Se estiver escrevendo uma função, retorne o valor. Se estiver escrevendo um programa completo, use stdin para entrada e imprima o valor em stdout (ou use as alternativas mais próximas).

Você pode assumir que todos os valores estão dentro dos limites inteiros de 32 bits com sinal normal e que aXsão menores ou iguais a bXtodos os índices X. Os intervalos podem estar em qualquer ordem, nem sempre estão aumentando. Eles devem ser dados como uma string no formato acima. A cadeia pode estar vazia; nesse caso, a resposta será 0.

O menor envio em bytes vence.

Exemplo

Se a entrada fosse [-3,0],[1,2],[4,9]a saída, seria 22. O intervalo do meio não tem espaço para expandir de qualquer maneira, portanto deve permanecer inalterado. Os intervalos esquerdo e direito podem ser estendidos para [-7,0]e [4,15]respectivamente. A união de [-7,0]e [1,2]e [4,15]contém todos os valores de -7 a 15, exceto 3. Isso é 22 valores.

code-golf set-theory Passatempos de Calvin
fonte
3
Podemos usar a representação de string nativa das matrizes de nossa linguagem para entrada ou precisa ser exatamente esse formato?
Martin Ender
@ MartinBüttner Não. Você precisa usar este formato exato. (Eu sei que isso é uma espécie de faca de dois gumes, mas isso é a maneira que vai.)
Passatempo de Calvino
Você pode expandir um determinado intervalo de ambos os lados? Por exemplo, pode [5,6]se tornar [3,8](para uma resposta de 6), ou pode ser justo [5,8]ou [3,6](para uma resposta de 4)?
MtnViewMark
@MtnViewMark Não. Eles só pode ser estendida de um lado (ou não)
de Calvino Passatempos

Respostas:

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

Amostras de execuções:

λ: x ""
0

λ: x "[5,6]"
4

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

R, 282 278 269 247

Isso aumentou muito rapidamente, lidando com a entrada de string. Suspeito que posso jogar melhor assim, mas o tempo está acabando.

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

Essencialmente, a ideia é

  • Pegue a corda e transforme-a em uma matriz de 2 linhas
  • Verifique se está na ordem certa
  • Calcule as diferenças para cada coluna
  • Dobrar a primeira e a última diferença
  • Duplique as diferenças médias, se houver uma lacuna em relação à anterior ou à seguinte, que seja grande o suficiente
  • Retorna a soma das diferenças

Edit: percebi que eu desconectei os caracteres originalmente, então reorganizei algumas coisas para fazer a barba.

MickyT
fonte