Kone

Koneessa on näyttöruutu, jossa on alussa luku $1$. Lisäksi koneessa on kaksi nappia: vasen nappi lisää lukuun $3$ ja oikea nappi kertoo luvun $2$:lla.

Tavoitteesi on saada aikaan luku $x$ nappeja painamalla. Mikä on pienin mahdollinen painallusten määrä?

Esimerkiksi kun $x=17$, paras ratkaisu on seuraava:

• Luku on alussa $1$.
• Painat vasenta nappia, jolloin luvusta tulee $4$.
• Painat vasenta nappia, jolloin luvusta tulee $7$.
• Painat oikeaa nappia, jolloin luvusta tulee $14$.
• Painat vasenta nappia, jolloin luvusta tulee $17$.

Tässä tapauksessa pienin mahdollinen painallusten määrä on $4$.

Toteuta tiedostoon machine.py funktio min_steps, joka etsii pienimmän painallusten määrän luvulle $x$. Jos ratkaisua ei ole olemassa, funktion tulee palauttaa $-1$.

Funktion tulee toimia tehokkaasti, kun $x$ on välillä $1 \dots 1000$.

def min_steps(x):
    # TODO

if __name__ == "__main__":
    print(min_steps(1)) # 0
    print(min_steps(2)) # 1
    print(min_steps(3)) # -1
    print(min_steps(4)) # 1
    print(min_steps(5)) # 2
    print(min_steps(17)) # 4
    print(min_steps(42)) # -1
    print(min_steps(100)) # 7
    print(min_steps(1000)) # 13