Temukan Persimpangan 2 Set dalam Notasi Interval Terpadu

10

Temukan Persimpangan 2 Set dalam Notasi Interval Terpadu

Diberikan dua set bilangan real yang digambarkan sebagai gabungan interval, menampilkan deskripsi persimpangan dua set ini sebagai gabungan dari tipe interval yang sama.

Set input akan selalu terdiri dari serikat interval sehingga setiap interval dimulai dan berakhir pada bilangan bulat yang berbeda (yaitu tidak ada interval yang mengukur nol). Namun, interval yang berbeda dalam set yang sama dapat dimulai atau berakhir pada integer atau tumpang tindih yang sama.

Set output juga harus merupakan gabungan interval yang dimulai dan diakhiri pada bilangan bulat, tetapi tidak ada interval dalam output yang mungkin tumpang tindih dengan yang lain bahkan pada bilangan bulat tunggal.

Input dapat berupa apa saja yang cocok untuk bahasa pilihan Anda, asalkan terdiri dari dua daftar bilangan bulat.

Misalnya, Anda dapat mewakili set persamaansebagai:

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

Atau sebagai:

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

Atau sebagai:

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

Representasi output Anda harus identik dengan representasi input Anda (kecuali bahwa itu hanya satu daftar interval, bukan dua).

Contoh / Uji kasus:

Memasukkan:

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

Keluaran:

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

Dengan kata lain, kita memotong set yang berisi semua bilangan real antara -90 dan -4 dan semua bilangan real antara 4 dan 90 dengan set yang berisi semua bilangan real antara -50 dan 50. Persimpangan adalah set yang berisi semua bilangan real antara -50 dan -4 dan semua bilangan real antara 4 dan 50. Penjelasan lebih visual:

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

Memasukkan:

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

Keluaran:

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

Memasukkan:

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

Keluaran:

[-8,0]

Output Tidak Valid (meskipun mewakili set yang sama):

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

Mencetak:

Ini adalah sehingga sumber terpendek dalam byte menang, karena berpotensi dimodifikasi oleh bonus berikut.

Bonus:

-15% jika Anda juga mendukung infinity positif dan negatif sebagai batasan interval. Anda dapat memilih token apa yang mewakili angka-angka ini. (Dan ya, infinity adalah angka di hyperreals; P)

kuintopia
sumber
Bisakah kita mengasumsikan berbagai set gabungan dalam setiap puncak persimpangan ditulis dalam urutan yang meningkat? Dengan kata lain (tetapi sebaliknya), apakah input berikut ini valid? [[[4,90],[-90,-4]],[[-50,50]]]
msh210
2
@ msh210 contoh ketiga harus menjawab pertanyaan ini. (Tidak. Urutkan sendiri.)
quintopia
@nimi kamu benar. fixed
quintopia

Jawaban:

3

Mathematica, 41 byte - 15% = 34,85

Mathematica memiliki fungsi bawaan untuk persimpangan interval.

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

Contoh:

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

Out[1]= {{-50, -4}, {4, Infinity}}
alephalpha
sumber
2
Wow ... Saya baru saja datang dengan solusi yang sama persis tanpa membaca ini. +1
LegionMammal978
Harus menyukai penyatuan otomatis Mathematica Interval.
mbomb007
3

Haskell, 145 byte

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=[]

Contoh penggunaan: [(-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)].

Bagaimana itu bekerja:

                 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 

Saya menempatkan "setengah" -values x.5dalam daftar, karena saya perlu untuk membedakan (1,2),(3,4)dari (1,4). Tanpa x.5, keduanya akan menjadi [1,2,3,4], tetapi dengan x.5yang pertama menjadi [1,1.5,2,3,3.5,4](yang kurang 2.5) dan yang kedua [1,1.5,2,2.5,3,3.5,4].

nimi
sumber
Output harus identik dengan input. ... jadi katakan saja bahwa input Anda perlu .0 setelah setiap bilangan bulat juga;)
quintopia
@quintopia: ya, terima kasih.
nimi
2

Ruby, 90 byte

Memetakan masing-masing dari dua set ke array datar, mendapatkan persimpangan set array tersebut, lalu mengiris hasilnya menjadi potongan-potongan yang berkesinambungan dan memetakan setiap potongan ke dalam elemen pertama dan terakhir. Peasy mudah.

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

Pemakaian:

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
sumber
Untuk apa output program Anda s = [[[1,2],[3,4]], [[1,2],[3,4]]]? (Versi ruby ​​saya tidak punya slice_when, jadi saya tidak bisa menguji diri saya)
nimi
@mimi itu memberi [[1, 4]]. The slice_whenMetode ditambahkan suatu tempat sekitar Ruby 2.2 saya pikir.
daniero
... tetapi seharusnya [[1,2], [3,4]]
nimi
Set lebih dari bilangan real, hanya batas interval bilangan bulat, jadi 2.2bukan di input s = [[[1,2],[3,4]], [[1,2],[3,4]]], tetapi di output Anda [[1, 4]].
nimi
Hmm, kamu benar. Itu bisa diklarifikasi / ditekankan sedikit untuk yang secara matematis tertantang seperti saya ..
daniero