Логика с использованием очереди для итеративных Ханойских Башен?

Question

class Node:
    def __init__(self, value):
        self.value = value
        self.next = None

    def __str__(self):
        return "Node({})".format(self.value)

    __repr__ = __str__


class Queue:
    def __init__(self):
        #Constructor take head and tail
        self.head=None
        self.tail=None

    def __str__(self):
        #proper format
        temp=self.head
        out=[]
        while temp:
            out.append(str(temp.value))
            temp=temp.next
        out=' '.join(out)
        return ('Head:{}\nTail:{}\nQueue:{}'.format(self.head,self.tail,out))

    __repr__=__str__

    def isEmpty(self):
        #check if the queue is empty
        return (self.head == None)
    def len(self):
        #check the length of queue
        current = self.head
        len = 0
        while current != None:
            len += 1
            current = current.next

        return len

    def enqueue(self, value):
        #add a node to the end of queue
        node = Node(value)
        if self.isEmpty():
            self.head = node
            self.tail = node
        else:
            self.tail.next = node
            self.tail = node

    def dequeue(self):
        #delete a node from the beginning of queue
        if self.isEmpty():
            return 'Queue is empty'
        elif (self.head == self.tail):
            pop = self.head.value
            self.head = None
            self.tail = None
            return pop
        else:
            popped = self.head.value
            self.head = self.head.next
            return popped

    def peek(self):
        #show the first node
        return self.head.value

class QueueTower:
    def __init__(self, numDisks, A=Queue(), B=Queue(), C= Queue()):
        self.numDisks = numDisks
        self.A = Queue()
        self.B = Queue()
        self.C = Queue()
        for i in range(numDisks, 0, -1):
            self.A.enqueue(i)
            #print(i)

    def reversequeue(self, q):
        #reverse the queue without using stack
        if q.isEmpty() == False:
            data = q.peek()
            q.dequeue()
            q = self.reversequeue(q)  #recurssion
            q.enqueue(data)
            return q
        return Queue()

    def validMove(self, a, b):
        if not a.len():
            c = self.reversequeue(b)
            a.enqueue(c.dequeue())
            b.dequeue()
        elif not b.len():
            d = self.reversequeue(a)
            b.enqueue(d.dequeue())
            a.dequeue()
        elif a.peek() > b.peek():
            e = self.reversequeue(b)
            a.enqueue(e.dequeue())
            b.dequeue()
        else:
            f = self.reversequeue(a)
            b.enqueue(f.dequeue())
            a.dequeue()


    def hanoi(self, n):
        if n%2 == 0:
            self.B, self.C = self.C, self.B
        move = 2**n
        for i in range(1, move):
            if i%3==1:
                self.validMove(self.A, self.C)
            if i%3==2:
                self.validMove(self.A, self.B)
            if i%3==0:
                self.validMove(self.B, self.C)
        print("rod " + str(self.A)+ " has " + str(self.A.len()), "rod B " + str(self.B.len()), "rod C "+ str(self.C.len()))
        print("move needed is " + str(move-1))
tower1 = QueueTower(3)
tower1.hanoi(3)

В коде нет ошибок, но он не дает правильного вывода. Я записываю логику на листе бумаги, и, кажется, с этим все в порядке. Однако, когда я реализовал это, это не дало мне правильный вывод. Выходные данные показывают в конце, что у меня есть один диск в башне B и башне C, но нет ни одного в башне A. Пожалуйста, помогите мне понять проблему.

Большое спасибо за помощь!

Answer 1

Ваш метод обратной очереди метод возвращает неправильные значения.

 class Node:
    def __init__(self, value):
        self.value = value
        self.next = None

    def __str__(self):
        return "Disc({})".format(self.value)


class Queue:
    def __init__(self, name):
        self.name = name
        self.head = None
        self.tail = None

    def is_empty(self):
        return self.head is None

    def len(self):
        current = self.head
        len = 0
        while current is not None:
            len += 1
            current = current.next
        return len

    def enqueue(self, value):
        node = Node(value)
        if self.is_empty():
            self.head = node
            self.tail = node
        else:
            self.tail.next = node
            self.tail = node

    def dequeue(self):
        if self.is_empty():
            return "EMPTY"
        elif self.head == self.tail:
            help = self.head.value
            self.head = None
            self.tail = None
            return help
        else:
            jump = self.head.value
            self.head = self.head.next
            return jump

    def peek(self):
        return self.head.value


class QueueTower:
    def __init__(self, number_of_discs):
        self.number_of_discs = number_of_discs
        self.A, self.B, self.C = Queue("A"), Queue("B"), Queue("C")

        for i in range(number_of_discs, 0, -1):
            self.A.enqueue(i)

    def reverse_queue(self, q):
        if not q.is_empty():
            if q.head != q.tail:
                data = q.peek()
                q.dequeue()
                self.reverse_queue(q)  # recursion
                q.enqueue(data)
                return q
            else:
                data = q.peek()
                q.dequeue()
                q.enqueue(data)
                return q
        return Queue(q.name)

    def valid_move(self, a, b):
        if not a.len():
            a.enqueue(b.dequeue())
        elif not b.len():
            if a.len() == self.number_of_discs:
                d = self.reverse_queue(a)
            else:
                d = a
            b.enqueue(d.dequeue())
        elif a.peek() > b.peek():
            e = b
            a = self.reverse_queue(a)
            a.enqueue(e.peek())
            self.reverse_queue(a)
            b.dequeue()
        else:
            b = self.reverse_queue(b)
            b.enqueue(a.dequeue())
            self.reverse_queue(b)

    def hanoi(self, n):
        if n % 2 == 0:
            self.B, self.C = self.C, self.B
        move = 2 ** n
        for i in range(1, move):
            if i % 3 == 1:
                self.valid_move(self.A, self.C)
            if i % 3 == 2:
                self.valid_move(self.A, self.B)
            if i % 3 == 0:
                self.valid_move(self.B, self.C)

            # Start formatting output.
            tower_a, tower_b, tower_c = self.A, self.B, self.C
            if n % 2 == 0:
                tower_b, tower_c = self.C, self.B
            for j in [tower_a, tower_b, tower_c]:
                print("\n    |", j.name, "|", end=" ")
                current = j.head
                while current:
                    print(current, "|", end=" ")
                    current = current.next
            print()
            # End formatting output.

        print("\nMove needed is: " + str(move - 1))


tower = QueueTower(3)
tower.hanoi(3)

Вывод:

| A | Disc(2) | Disc(3) | 
| B | 
| C | Disc(1) | 

| A | Disc(3) | 
| B | Disc(2) | 
| C | Disc(1) | 

| A | Disc(3) | 
| B | Disc(1) | Disc(2) | 
| C | 

| A | 
| B | Disc(1) | Disc(2) | 
| C | Disc(3) | 

| A | Disc(1) | 
| B | Disc(2) | 
| C | Disc(3) | 

| A | Disc(1) | 
| B | 
| C | Disc(2) | Disc(3) | 

| A | 
| B | 
| C | Disc(1) | Disc(2) | Disc(3) | 

Move needed is: 7