Editing 2527 - Hanoi


== Enunț ==
Turnurile din Hanoi este un joc matematic sau, dacă vreți, un puzzle. Este format din trei tije <code>A</code>, <code>B</code> și <code>C</code> și un număr variabil de discuri, de diferite diametre. Inițial discurile sunt așezate în ordine descrescătoare a diametrelor pe tija <code>A</code>, de la vârf către bază, astfel încât să formeze un turn.

Scopul jocului este acela de a muta toate discurile de pe tija <code>A</code> pe tija <code>C</code> folosind ca tijă intermediară tija <code>B</code>, respectând următoarele reguli:

* la un moment dat doar un singur disc poate fi mutat
* fiecare mutare constă în luarea celui mai de sus disc de pe o tija și mutarea acestuia pe o altă tijă
* un disc cu diametrul mai mare nu poate fi poziționat deasupra unui disc cu diametrul mai mic.

= Cerința =
Dacă se cunoaște numărul <code>n</code> de discuri aflate pe tija <code>A</code>, să se determine șirul mutărilor necesare pentru ca toate discurile să fie mutate pe tija <code>C</code>.

= Date de intrare =
Fișierul de intrare <code>hanoiIN.txt</code> conține pe prima linie numărul natural nenul <code>n</code>, ce reprezintă numărul de discuri aflat pe tija <code>A</code>.

= Date de ieșire =
Fișierul de ieșire <code>hanoiOUT.txt</code> va conține pe prima linie numărul <code>m</code>, ce reprezintă numărul minim de mutări ce se efectuează. Pe următoarele <code>m</code> linii vor fi scrise mutările sub forma: ''tija sursă->tija destinație''.

= Restricții și precizări =

* <code>1 ≤ n ≤ 15</code>
* mutările vor fi scrise câte una pe linie, fără spații

= Exemplul 1 =
<code>hanoiIN.txt</code>
 2
<code>hanoiOUt.txt</code>
 3
 A->B
 A->C
 B->C

== Exemplul 2 ==
<code>hanoiIN.txt</code>
 16
<code>hanoiOUt.txt</code>
 Restrictii neindeplinite.

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
def verifica_restrictii(n):
    return 1 <= n <= 15

def hanoi(n, sursa, intermediar, destinatie, mutari):
    if n == 1:
        mutari.append(f"{sursa}->{destinatie}")
    else:
        hanoi(n-1, sursa, destinatie, intermediar, mutari)
        mutari.append(f"{sursa}->{destinatie}")
        hanoi(n-1, intermediar, sursa, destinatie, mutari)

def main():
    with open("hanoiIN.txt", "r") as f_input, open("hanoiOUT.txt", "w") as f_output:
        n = int(f_input.readline().strip())

        if not verifica_restrictii(n):
            f_output.write("Restrictii neindeplinite.\n")
            return

        mutari = []
        hanoi(n, 'A', 'B', 'C', mutari)

        f_output.write(str(len(mutari)) + "\n")
        for mutare in mutari:
            f_output.write(mutare + "\n")

if __name__ == "__main__":
    main()
</syntaxhighlight>