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