P1 - naloga Dovoljena stevila

• intervali.txt

# -*- coding: utf-8 -*-
"""
Nadaljuj [staro domačo nalogo Prepovedani intervali](https://github.com/janezd/predavanja/blob/master/p1/domace-naloge/2020/03%20prepovedani%20intervali/resitev.ipynb)
takole: napiši program, ki pove, koliko je vseh dovoljenih števil med 0 in največjo
zgornjo mejo, če so prepovedana vsa števila, ki se nahajajo v naslednjih intervalih
(par predstavlja zgornjo in spodnjo mejo; (12, 18), pomeni, da so prepovedana vsa
števila od 12 do, vključno, 18).

prepovedani = [
    (12, 18),
    (2, 5),
    (3, 8),
    (0, 4),
    (15, 19),
    (6, 9),
    (13, 17),
    (4, 8)
]

V gornjem primeru mora izpisati 2, saj sta dovoljeni dve števili, 10 in 11.
"""
from time import time
import numpy as np

timeStart = time()

prepovedani = [
    (12, 18),
    (2, 5),
    (3, 8),
    (0, 4),
    (15, 19),
    (6, 9),
    (13, 17),
    (4, 8),
]

for checkIndex in range(np.max(prepovedani) + 1):
    for rStart, rEnd in prepovedani:
        if (rStart <= checkIndex <= rEnd):
            print('%s je v prepovedanem rangu [%s, %s]' % (checkIndex, rStart, rEnd))
            break
    else:
        print('%s je dovoljen' % checkIndex)

print("Finished in ", time() - timeStart, "\n\n\n")

"""
Potem pa se spopadi z intervali iz datoteke intervali.txt, ki je pripeta k nalogi.

Branja datotek se še nismo učili. Lahko se potrudiš sam(a), lahko pa uporabiš naslednjo vrstico:
intervali = [tuple(int(x) for x in vrstica.split("-")) for vrstica in open("intervali.txt")]

Še en zanimiv izziv je naslednji: recimo, da tvoj računalnik ne bi imel niti toliko pomnilnika,
da bi lahko shranil celotno tabelo intervalov. Če hočeš večkrat prek tabele, moraš večkrat odpreti
datoteko in jo brati. Z drugimi besedami: nimamo seznamov (ali terk, slovarjev, množic ...), le
posamične int-e in datoteke (ter, očitno, niz s posamično vrstico, ki jo dobiš iz datoteke, ter
seznam z dvema nizoma, ki ga vrne split te vrstice). Napiši program, ki kljub tem omejitvam v
doglednem času reši nalogo. Recimo tako, da čim manjkrat prebere datoteko.
"""
import os

print("Starting 'dodatna':")
timeStart = time()
intervali = [tuple(int(x) for x in vrstica.split("-")) for vrstica in open(os.path.dirname(__file__) + "/intervali.txt")]
# intervali = [(0, 10), (2, 5), (9, 20), (15, 19), (12, 40), (32, 50), (19, 30)]
intervali = sorted(intervali)


allowedCount = 0
allowedSum = 0

endingMax = 0
for (_, intAb), (intBa, _) in zip(intervali, intervali[1:]):
    endingMax = max(intAb, endingMax)

    if intBa <= endingMax:
        print(".", end="")
        continue
    else:
        newCount = intBa - intAb - 1
        newSum = (intBa * (intBa+1) - (intAb-1) * intAb) / 2
        allowedCount += newCount
        allowedSum += newSum
        print("+", end="")

print("\n")
print("%-20s %s" % ("Allowed numbers", allowedCount))
print("%-20s %s" % ("Out of", np.max(intervali) - np.min(intervali)))
print("%-20s %s" % ("Sum of all allowed", allowedSum))
print("%-20s %s" % ("Finished in", time() - timeStart))

---

Zadnja posodobitev: February 27, 2022