Encontre a interseção de 2 conjuntos na notação de intervalo unido

10

Encontre a interseção de 2 conjuntos na notação de intervalo unido

Dados dois conjuntos de números reais descritos como a união de intervalos, produza uma descrição da interseção desses dois conjuntos como uma união do mesmo tipo de intervalo.

Os conjuntos de entrada sempre consistem em uniões de intervalos, de modo que cada intervalo comece e termine em um número inteiro diferente (ou seja, nenhum intervalo tem a medida zero). No entanto, diferentes intervalos no mesmo conjunto podem começar ou terminar no mesmo número inteiro ou se sobrepor.

O conjunto de saída também deve ser uma união de intervalos que começam e terminam em números inteiros, mas nenhum intervalo na saída pode se sobrepor a nenhum outro mesmo em um único número inteiro.

A entrada pode assumir qualquer formato que seja adequado ao seu idioma de escolha, contanto que consista em duas listas de pares de números inteiros.

Por exemplo, você pode representar o conjunto equaçãocomo:

[-10,-4]u[1,5]u[19,20]

Ou como:

[[-10,-4],[1,5],[19,20]]

Ou como:

[-10,-4;1,5;19,20]

Sua representação de saída deve ser idêntica à sua representação de entrada (exceto que é apenas uma lista de intervalos em vez de dois).

Exemplos / casos de teste:

Entrada:

[[[-90,-4],[4,90]],[[-50,50]]]

Resultado:

[[-50,-4],[4,50]]

Em outras palavras, estamos cruzando o conjunto que contém todos os números reais entre -90 e -4 e todos os números reais entre 4 e 90 com o conjunto que contém todos os números reais entre -50 e 50. A interseção é o conjunto que contém todos números reais entre -50 e -4 e todos os números reais entre 4 e 50. Uma explicação mais visual:

-90~~~~~-4  4~~~~~90   intersected with
    -50~~~~~~~~50        yields:
    -50~-4  4~~50

Entrada:

"[-2,0]u[2,4]u[6,8]
[-1,1]u[3,5]u[5,9]"

Resultado:

"[-1,0]u[3,4]u[6,8]"

Entrada:

[-9,-8;-8,0;-7,-6;-5,-4]
[-7,-5;-1,0;-8,-1]

Resultado:

[-8,0]

Saída inválida (mesmo que represente o mesmo conjunto):

[-8,0;-7,-5;-5,0]

Pontuação:

Isso é pelo que a fonte mais curta em bytes vence, potencialmente modificada pelo seguinte bônus.

Bônus:

-15% se você também suporta infinito positivo e negativo como limites de intervalos. Você pode escolher quais tokens representam esses números. (E sim, infinito é um número nos hiperreais; P)

quintopia
fonte
Podemos supor que os vários conjuntos sindicais em cada soma de interseção sejam escritos em ordem crescente? Em outras palavras (mas inversamente), a entrada a seguir é válida? [[[4,90],[-90,-4]],[[-50,50]]]
Msh210
2
@ msh210 o terceiro exemplo deve responder a esta pergunta. (Não. Classifique você mesmo.)
quintopia
@nimi você está certo. fixo
quintopia 09/12/19

Respostas:

3

Mathematica, 41 bytes - 15% = 34,85

O Mathematica possui uma função interna para interseção de intervalos.

List@@IntervalIntersection@@Interval@@@#&

Exemplo:

In[1]:= List@@IntervalIntersection@@Interval@@@#&[{{{-90, -4}, {4, Infinity}}, {{-50,Infinity}}}]

Out[1]= {{-50, -4}, {4, Infinity}}
alefalpha
fonte
2
Uau ... eu apenas vim com exatamente a mesma solução sem ler isso. 1)
LegionMammal978
Tem que amar o auto-união do Mathematica Interval.
mbomb007
3

Haskell, 145 bytes

import Data.List
q(a,b)=[a,a+0.5..b]
p@(a,b)%(h:t)|h==b+0.5=(a,h)%t|1<2=p:(h,h)%t
p%_=[p]
a#b|h:t<-nub$sort$intersect(q=<<a)$q=<<b=(h,h)%t|1<2=[]

Exemplo de uso: [(-2.0,0.0),(2.0,4.0),(5.0,6.0),(6.0,8.0)] # [(-1.0,1.0),(3.0,5.0),(5.0,9.0)]-> [(-1.0,0.0),(3.0,4.0),(5.0,8.0)].

Como funciona:

                 q=<<a            -- turn each pair in the 1st input list into
                                  -- lists with halves in between (e.g. (1,4) ->
                                  -- [1,1.5,2,2.5,3,3.5,4]) and concatenate them
                                  -- to a single list
                      q=<<b       -- same for the second input list
    nub$sort$intersect            -- sort the intersection of those lists
                                  -- and remove duplicates
h:t<-                             -- call the first element h and the rest t
                       (h,h)%t    -- start rebuilding the intervals
                          |1<2=[] -- if there's no first element h, one of the
                                  -- input lists is empty, so the output is also
                                  -- empty


p@(a,b)%(h:t)                     -- an interval p = (a,b), build from a list (h:t)
             =(a,h)%t             -- becomes (a,h)
      |h==b+1                     --   if h equals b+0.5
                    p:(h,h)%t     -- or is put in the output list, followed by
                                  --       a new interval starting with (h,h)
      |1<2                        --   otherwise
p%_=[p]                           -- base case of the interval rebuilding function 

Estou colocando os valores A "meia" x.5na lista, porque eu preciso distinguir (1,2),(3,4)a partir (1,4). Sem x.5, ambos se tornariam [1,2,3,4], mas com x.5o primeiro se torna [1,1.5,2,3,3.5,4](o que falta 2.5) e o segundo [1,1.5,2,2.5,3,3.5,4].

nimi
fonte
A saída deve ser idêntica à entrada. ... então diga que sua entrada precisa de .0 após cada número inteiro também;)
quintopia
@ Quintopia: Sim, obrigado.
nimi
2

Ruby, 90 bytes

Mapeia cada um dos dois conjuntos para uma matriz plana, obtém a interseção do conjunto dessas matrizes e, em seguida, divide o resultado em partes contínuas e mapeia cada parte no primeiro e no último elemento. Mole-mole.

->s{a,b=s.map{|y|y.flat_map{|f,l|[*f..l]}.sort}
(a&b).slice_when{|a,b|b-a>1}.map &:minmax}

Uso:

f=->s{a,b=s.map{|y|y.flat_map{|f,l|[*f..l]}.sort}
(a&b).slice_when{|a,b|b-a>1}.map &:minmax}

s = [[[-90,-4],[4,90]], [[-50,50]]]
p f[s] # => [[-50, -4], [4, 50]]

s = [[[-2,0],[2,4],[6,8]], [[-1,1],[3,5],[5,9]]]
p f[s] # => [[-1, 0], [3, 4], [6, 8]]

s = [[[-9,-8],[-8,0],[-7,-6],[-5,-4]],[[-7,-5],[-1,0],[-8,-1]]]
p f[s] # => [[-8, 0]]
daniero
fonte
Para que serve o seu programa s = [[[1,2],[3,4]], [[1,2],[3,4]]]? (Minha versão rubi não tem slice_when, por isso não posso me testar)
nimi
@mimi dá [[1, 4]]. O slice_whenmétodo foi adicionado em torno do Ruby 2.2, eu acho.
Daniero
... mas deve ser [[1,2], [3,4]]
nimi
Os conjuntos estão acima de números reais, apenas os limites do intervalo são inteiros; portanto, 2.2não está na entrada s = [[[1,2],[3,4]], [[1,2],[3,4]]], mas na sua saída [[1, 4]].
nimi
Hmm, você está certo. Isso poderia ter sido clearified / emphized um pouco para o matematicamente desafiado como eu ..
daniero