Dodatne ovire

Oddelek za gozdarske dejavnosti in motorni promet nam je tokrat nakopal težko nalogo. Najboljše, da narišem.

Recimo, da imamo ovire, ki so postavljene takole (številke služijo za pomoč pri razbiranju koordinat):

         1         2         3         4         5         6         7         8
123456789012345678901234567890123456789012345678901234567890123456789012345678901
  ###   ##  ###   ###### ##     ### ##      ### ##  ###    # # ###  # # #  ##

Ali, v notaciji iz naših davnih nalog:

obstojece = [(3, 5), (9, 10), (13, 15), (19, 24), (26, 27), (33, 35), (37, 38), (45, 47), (49, 50), (53, 55), (60, 60), (62, 62), (64, 66), (69, 69), (71, 71), (73, 73), (76, 77)]

Pa so se odločili, da postavijo nekaj novih ovir. Predvidene nove ovire so:

         1         2         3         4         5         6         7         8
123456789012345678901234567890123456789012345678901234567890123456789012345678901
      ###     ##   #   ##    ####  #    ##     #          #######   ####      ###

torej

nove = [(7, 9), (15, 16), (20, 20), (24, 25), (30, 33), (36, 36), (41, 42), (48, 48), (59, 65), (69, 72), (79, 81)]

Postavimo to reč skupaj:

         1         2         3         4         5         6         7         8
123456789012345678901234567890123456789012345678901234567890123456789012345678901
  ###   ##  ###   ###### ##     ### ##      ### ##  ###    # # ###  # # #  ##
      ###     ##   #   ##    ####  #    ##     #          #######   ####      ###

Dela se bodo lotili tako, da bodo najprej odstranili vse obstoječe ovire, ki bi ovirale postavite novih. Tako dobijo

         1         2         3         4         5         6         7         8
123456789012345678901234567890123456789012345678901234567890123456789012345678901
  ###                    ##         ##      ### ##  ###                 #  ##
      ###     ##   #   ##    ####  #    ##     #          #######   ####      ###

Od obstoječih ovir torej ostane samo

[(3, 5), (26, 27), (37, 38), (45, 47), (49, 50), (53, 55), (73, 73), (76, 77)]

Nato postavijo nove ovire:

         1         2         3         4         5         6         7         8    
123456789012345678901234567890123456789012345678901234567890123456789012345678901
  ### ###     ##   #   ####  ####  ###  ##  ######  ###   ########  #####  ## 

Rezultat je torej:

[(3, 5), (7, 9), (15, 16), (20, 20),(24, 27), (30, 33), (36, 38), (41, 42), (45, 50), (53, 55), (59, 65), (69, 73), (76, 77), (79, 81)]

Obvezni del

Napišite funkcijo odstrani_odvecne(obstojece, dodatne), ki kot argumenta sprejme dva seznama ovir v zgornji notaciji. Predpostaviti smete, da so ovire urejene od leve proti desni in se (znotraj posamičnega seznama) ne prekrivajo. Funkcija ne vrne ničesar, temveč spremeni seznam obstojece tako, da iz nje odstrani vse ovire, ki se prekrivajo z vsaj eno oviro iz množice dodatne.

Nato napišite funkcijo zlite_ovire(obstojece, dodatne), ki prejme enaka argumenta kot prva funkcija in vrne nov seznam ovir, ki nastane z združitvijo obeh seznamov. Pri tem naj bodo vse ovire urejene od leve proti desni. Upoštevajte tudi, da se nekatere nove in stare ovire združijo v eno samo oviro.

Funkcija zlite_ovire ne sme spreminjati vhodnih seznamov!

Nasvet: če ne želite izgubiti živcev, pripravite niz z novimi ovirami in jih podajte funkciji, ki pretvarja niz v seznam ovir. Napisali smo jo v eni od prejšnjih nalog.

Pomoč: tule je funkcija, ki ji podamo dve oviri in vrne True, če se prekrivata, sicer pa False.

def sovpad(ovira1, ovira2):
    return ovira2[0] <= ovira1[0] <= ovira2[1] or ovira1[0] <= ovira2[0] <= ovira1[1]

Dodatni del

Napišite funkcijo zlite_ovire(obstojece, dodatne), ki je podobna prejšnji, vendar ne vrne ničesar, temveč spremeni seznam obstojece, da vsebuje združene ovire. Pri reševanju bi seveda lahko samo spretno uporabili prejšnjo funkcijo, vendar za izziv poskusite to delati na mestu.

Pa še nekaj: ker gre za dodatno nalogo, bodo testi napisani nekoliko hudobneje (= vse ovire so 10000000000000000000000-krat daljše, toliko pomnilnika pa nima niti OpenAI) in trik s pretvarjanjem v niz ne bo deloval. Srečno! :)

Testi