Naloga iz 2020/21: Srečanja

Dva tipa. Bluzita po New Yorku, v času viška korone. Zelo pametno. No, vsaj sledilno aplikacijo sta imela. Vsaj to.

Prvi je šel tako: 
^2 >6 ^6 <1 v3 <6 v4
 Drugi - tako: 
>4 ^3 >4 ^3 <6 v8 >1 ^5
 Če narišemo oba skupaj, je to videti tako.

Vse ulice so pravokotne, vse razdalje so pozitivna cela števila. (Ker Manhattan.)

Aplikacija za sledenje je zaznala, da sta se vsaj enkrat srečala. Fun fact: nikoli nista šla po isti poti: njune poti so se le križale. Less fun fact: aplikacija ne beleži ne koordinat ne časa, zato nimamo pojma, kje sta se srečala.

Obvezni del

  • Za začetek napiši funkcijo v_pot(s), ki prejme niz, kot so gornji, in ga razbije v seznam terk: prvi element terke je smer, drugi razdalja. Klic v_pot(">100 ^42 <13") vrne [(">", 100), ("^", 42), ("<", 13)].

  • Napiši funkcijo odsek(x, y, smer, razdalja), ki prejme (celoštevilski) koordinati (x, y), smer ("<", ">", "^" ali "v") in dolžino odseka (pozitivno celo število). Vrniti mora seznam terk, ki predstavljajo vse celoštevilske koordinate na tem odseku. Klic odsek(2, 5, "^", 3) vrne [(2, 5), (2, 6), (2, 7), (2, 8)].

  • Nato napiši funkcijo tocke(s), ki prejme gornji seznam terk in sestavi seznam vseh celoštevilskih koordinat, prek katerih gre pot. Klic tocke([(">", 3), ("v", 2), (">", 2)]) vrne [(0, 0), (1, 0), (2, 0), (3, 0), (3, -1), (3, -2), (4, -2), (5, -2)]. Pot se vedno začne na koordinatah (0, 0).

  • Končno, napiši funkcijo presecisca(s, t), ki prejme dve poti kot niz in vrne seznam njunih presečišč, torej vseh točk potencialnih srečanj teh dveh ljudi. Upoštevaj, da so črte lahko tudi zelo dolge, veliko daljše kot v tem primeru. (Spet pa ne tako dolge, da seznam koordinat ne bi šel v pomnilnik.) Funkcija mora delo vseeno opraviti v nekaj sekundah. Če bo zahtevala več časa, ni pravilno napisana. (Ne boj se: če bo počasna, bo res počasna in boš vedel(a), da ni OK.)

Dodatna naloga

Izkazalo se je, da tole pravzaprav ni pot, ki sta jo prehodila, temveč pot, ki jo nameravata prehoditi. Poleg tega sta se dogovorila, da se morata nujno vsaj enkrat srečati.

Da prehodita razdaljo dolžine 1, potrebujeta vsaj 1 minuto.

Recimo, da bi se zmenila, da se bosta srečala na najbolj zgornji desni točki na sliki. Modri sicer lahko pride tja v 12 minutah, vendar bo moral tam počakati do rdečega, ki bo do tja potreboval 16 minut. Če se torej dogovorita za srečanje v oni točki, se bosta dobila čez 16 minut.

Ker bi se rada srečala čimprej, si bosta raje izbrala kakšno točko, do katere lahko prideta ob čimprej -- pa čeprav ne nujno ob istem času. No, v primeru na sliki je to točka (4, 2), do katere slučajno prideta ob hkrati, v šestih minutah.

V splošnem pa točka srečanja ni točka, do katere potrebujeta enako časa, temveč točka, na kateri sta čimprej lahko oba.

Napiši funkcijo prvo_srecanje(s, t), ki prejme poti (kot niza) in vrne najkrajši možni čas do prvega srečanja in koordinati točke tega srečanja. V gornjem primeru vrne (6, (4, 2)).

Začetna točka, (0, 0) ne šteje. Tam se ne smeta srečati, ker bi ju vsi videli.

Nasvet: funkcija tocke(s) vrne le seznam točk. Ne pa tudi razdalj do njih. To ni dobro. Potrebno bo napisati kaj podobnega, a uporabnejšega.

Testi