Kaupat

Annettuna on merkkijono, joka kuvaa kadulla vierekkäin olevia rakennuksia. Jokainen merkki on joko 0 (asuintalo) tai 1 (kauppa).

Tehtäväsi on muodostaa lista, joka kertoo kullekin rakennukselle lyhimmän etäisyyden kauppaan. Jos rakennus on kauppa, etäisyys on $0$. Muuten etäisyys on askelten määrä lähimpään kauppaan.

Esimerkiksi jos rakennukset ovat 00100010, haluttu lista on $[2,1,0,1,2,1,0,1]$. Jos taas rakennukset ovat 00100000, haluttu lista on $[2,1,0,1,2,3,4,5]$. Voit olettaa, että ainakin yksi rakennuksista on kauppa.

Toteuta tiedostoon shops.py funktio find_distances, jolle annetaan parametrina rakennukset kuvaava merkkijono. Funktion tulee palauttaa yllä olevan kuvauksen mukainen lista etäisyyksistä.

Sinun tulee toteuttaa tehokas ratkaisu, jonka aikavaativuus on $O(n)$. Ratkaisun tulee käsitellä tehokkaasti myös tehtäväpohjan viimeinen suuri syöte.

def find_distances(street):
    # TODO

if __name__ == "__main__":
    print(find_distances("00100010")) # [2, 1, 0, 1, 2, 1, 0, 1]
    print(find_distances("00100000")) # [2, 1, 0, 1, 2, 3, 4, 5]
    print(find_distances("11111111")) # [0, 0, 0, 0, 0, 0, 0, 0]
    print(find_distances("01010101")) # [1, 0, 1, 0, 1, 0, 1, 0]
    print(find_distances("10000000")) # [0, 1, 2, 3, 4, 5, 6, 7]
    print(find_distances("00000001")) # [7, 6, 5, 4, 3, 2, 1, 0]

    n = 10**5
    street = "0"*n + "1" + "0"*n
    distances = find_distances(street)
    print(distances[1337]) # 98663