Das deutsche Python-Forum • Turm von Hanoi Solver

Seite 1 von 1

Turm von Hanoi Solver

Verfasst: Freitag 29. März 2013, 13:15

von noisefloor

Hallo,

ich brauchte (für mich) einen Solver für das Spiel Turm von Hanoi, welcher den Spielstand (=die Position der Scheiben) nach einem zu definierenden Zug anzeigen kann.

Gefunden habe ich (nach sehr schneller Suche...) keinen, also habe ich ein Python-Modul dafür geschrieben. pyHanoi ist ein iterativer Solver (d.h. kein Problem mit max_recursion_depth), welcher nach eine zu definierenden Anzahl von Zügen stoppen kann und dann, auf Wunsch, dort später wieder weiter machen.

Der Code liegt bei https://launchpad.net/pyhanoi. Die Docstrings sind komplett und erklären die Nutzung von pyHanoi.

Irgendwann kommt vielleicht noch ein Logger dazu, welcher den kompletten Spielverlauf aufzeichnet und in eine Log-Datei schreibt.

Gruß, noisefloor

Re: Turm von Hanoi Solver

Verfasst: Freitag 29. März 2013, 15:49

von EyDu

Vielleicht noch ein paar kleine Anmerkungen:

Code: Alles auswählen

[x for x in range(self.discs, 0, -1)]

ist das selbe wie

Code: Alles auswählen

list(range(self.discs, 0, -1))

Für 'start_final', 'start_aux' und 'aux_final' solltest du Konstanten verwenden, dann musst du die Strings nicht über den Code verstreuen. Auch würde ich als Werte keine Strings nehmen, sondern Integer.

Code: Alles auswählen

if self.discs % 2 != 0:
    self._moves = cycle(['start_final',
                        'start_aux',
                        'aux_final'])
else:
    self._moves = cycle(['start_aux',
                        'start_final',
                        'aux_final'])

solltest du zusammenfassen und die Bedingung vereinfachen.

Code: Alles auswählen

if self.discs % 2:
    params = ['start_final', 'start_aux', 'aux_final']
else:
    params = ['start_aux', 'start_final', 'aux_final']
self._moves = cycle(params)

Code: Alles auswählen

not self.start and not self.aux

kannst du zusammenfassen. Ob man das macht hängt natürlich davon ab, was du besser lesen kannst:

Code: Alles auswählen

not (self.start or self.aux)

Statt

Code: Alles auswählen

type(steps) is not int

solltest du isinstance verwenden:

Code: Alles auswählen

not isinstance(steps, int)

Dann kommt dein Code auch mit Vererbung zurecht.

Code: Alles auswählen

if steps == 0 or until_move == 0:
    keep_moving = False
else:
    keep_moving = True

ist das selbe wie

Code: Alles auswählen

keep_moving = not (steps==0 or unitl_move==0)

Hängt vom Wertebereich ab, aber unter Umständen geht auch:

Code: Alles auswählen

keep_moving = steps and until_move

_make_move sieht sehr symmetrisch aus. Auf den ersten Blick würde ich sagen, dass man die drei Zweige zusammenfassen kann:

Code: Alles auswählen

moves = {'start_aux': (self.start, self.aux),
         'start_final': (self,start, self.final),
         'aux_final': (self.aux, self.final)}

if move in moves:
    a, b = moves[move]

    if a and (not b or a[-1] < b[-1]):
        a, b = b, a

    a.append(b.pop())
    self.movecount += 1

oder

Code: Alles auswählen

try:
    a, b = moves[move]
except KeyError:
    pass
else:
    if a and (not b or a[-1] < b[-1]):
        a, b = b, a

    a.append(b.pop())
    self.movecount += 1

Ich bin mir nicht sicher, ob es so stimmt, da ich nur kurz drüber gegangen bin ohne es zu testen. Am besten probierst du selber mal eine schrittweise Vereinfachung. Wahrscheinlich habe ich irgendwo auf dem Weg den Überblick über die boolschen Ausdrücke verloren.

Code: Alles auswählen

else:
    pass

ist überflüssig.

Re: Turm von Hanoi Solver

Verfasst: Freitag 29. März 2013, 16:18

von Sirius3

Ich hab noch ein paar zusätzliche Änderungen:

Code: Alles auswählen

from itertools import cycle, count

class NoMovesLeftError(Exception):
    def __init__(self):
        Exception.__init__(self,'No moves left, final peg is already full')

class Hanoi(object):
    def __init__(self, discs, quiet=False):
        self.discs = discs
        self.movecount = 0
        self.start = list(reversed(range(self.discs)))
        self.aux = []
        self.final = []
        self.quiet = quiet
        if self.discs % 2 != 0:
            moves = ['start_final', 'start_aux', 'aux_final']
        else:
            moves = ['start_aux', 'start_final', 'aux_final']
        self._moves = cycle(moves)

    @property
    def total(self):
        return 2**self.discs-1

    @property
    def finished(self):
        return not self.start and not self.aux

    def run(self, steps=None, until_move=None):
        if self.finished:
            raise NoMovesLeftError()
        conditions = [lambda: not self.finished]

        if steps:
            if not steps >= 0:
                raise ValueError('Value given for steps must be an positive integer')
            conditions.append(lambda x=count(steps,-1).next: x()>0)
        if until_move:
            if not until_move >= 0:
                raise ValueError('Value given for until_move must be an positive integer')
            conditions.append(lambda: self.movecount<=until_move)
                
        if not self.quiet:
            print('Moves made so far: {0}'.format(self.movecount))
            print('Moving discs...')

        while all(cond() for cond in conditions):
            self._make_move(next(self._moves))

        if not self.quiet:
            print('Stopped moving...')
            if not self.finished:
                print('...but not finished yet.')
            else:
                print('...and finished')

    def show_state(self):
        print('''number of discs: {discs}
total number of moves necessary: {total}
number of moves made: {movecount}
start peg: {start}
aux peg: {aux}
final peg: {final}'''.format(total=self.total, **self.__dict__))

    def _make_move(self, move):
        pegA, pegB = [ getattr(self, peg) for peg in move.split('_') ]
        if not pegA or (pegB and pegB[-1]<pegA[-1]):
            pegA.append(pegB.pop())
        else:
            pegB.append(pegA.pop())
        self.movecount += 1

Re: Turm von Hanoi Solver

Verfasst: Freitag 29. März 2013, 20:08

von noisefloor

Hallo,

Danke schon mal für die Antowrten

Werde ich demnächst mal schrittweise einbauen.

Code: Alles auswählen

else:
    pass

verwende ich manchmal, um alle Bedingungen explizit sichtbar zu haben (während der Entwicklung). Aus dem Produktivcode sollte ich es vielleicht dann raus nehmen

EyDu schrieb:

_make_move sieht sehr symmetrisch aus.

Ja, ist es auch - nur ist mir seinerzeit keine bessere Lösung eingefallen...

Gruß, noisefloor

Re: Turm von Hanoi Solver

Verfasst: Freitag 29. März 2013, 20:31

von BlackJack

@noisefloor: In Fällen wie dem wo Du das ``else: pass`` verwendet hast schreibe ich anstelle des ``pass`` immer ein ``assert False, 'grund warum das nicht passieren darf'``. Manchmal passiert es ja doch das eine Variable einen Wert annimmt, den sie eigentlich an der Stelle niemals annehmen dürfte. Das ist ein sinnvolleres Verhalten als ``pass`` oder das ``else`` ganz weg zu lassen.

Re: Turm von Hanoi Solver

Verfasst: Freitag 29. März 2013, 20:57

von noisefloor

Hallo,

ah, ok - macht Sinn. Habe ich so noch nicht gesehen. Danke für den Tipp

Gruß, noisefloor