Coverage for blog/dsa/stack/__init__.py: 66%
80 statements
« prev ^ index » next coverage.py v7.6.12, created at 2025-02-20 16:23 +0000
« prev ^ index » next coverage.py v7.6.12, created at 2025-02-20 16:23 +0000
1import secrets
2from collections.abc import Iterable
3from typing import Generator, Generic, TypeVar
5from typing_extensions import Self
7T_Stack = TypeVar("T_Stack")
10class Stack(Generic[T_Stack]):
12 identity: str
13 memory: list[T_Stack]
14 index: int
16 def __init__(self, identity: str | None = None):
17 # NOTE: In ``C``, this is just an array for which some resizing may
18 # have to occur.
19 self.identity = identity if identity is not None else secrets.token_hex(8)
20 self.memory = list()
21 self.index = -1
23 @classmethod
24 def fromIterable(cls, items: Iterable[T_Stack], **kwargs) -> Self:
25 self = cls(**kwargs)
26 for item in items:
27 self.push(item)
29 return self
31 def push(self, item: T_Stack) -> None:
32 self.index += 1
33 self.memory.append(item) # Yes, append is bad.
35 def pop(self) -> T_Stack:
36 if self.index == -1:
37 raise ValueError(f"Stack `{self.identity}` is empty.")
39 top = self.memory.pop(self.index)
40 self.index -= 1
41 return top
43 @property
44 def top(self) -> T_Stack:
45 if self.index == -1:
46 raise ValueError(f"Stack `{self.identity}` is empty.")
48 return self.memory[self.index]
51def hanoi_turn(s: Stack[int], t: Stack[int]):
53 if s.index == -1:
54 s.push(t.pop())
55 return
56 elif t.index == -1:
57 t.push(s.pop())
58 return
60 bigger, smaller = (s, t) if s.top > t.top else (t, s)
61 bigger.push(smaller.pop())
64def hanoi(a: Stack[int], b: Stack[int], c: Stack[int]) -> Generator[None, None, None]:
66 n = len(a.memory)
67 pairs = (a, b), (c, a), (b, c)
68 if not all(p > q for p, q in zip(a.memory[:-1], a.memory[1:])):
69 raise ValueError("`a` must be sorted from greatest to least value.")
71 turn = 0
72 while len(c.memory) != n and len(b.memory) != n:
74 yield
75 s, t = pairs[turn % 3]
76 hanoi_turn(s, t)
77 turn += 1
80def main():
81 size = 25
83 a = Stack[int](identity="a")
84 for k in range(size):
85 a.push(size - k)
87 turns = 0
88 n = 0
89 for _ in hanoi(a, b := Stack[int](identity="b"), c := Stack[int](identity="c")):
91 if not n:
92 _n = input("Enter the number of turns to execute: ")
93 print()
94 n = 1 if not _n.isnumeric() else int(_n)
95 print(n)
97 elif n == 1:
98 print(a.identity, a.memory)
99 print(b.identity, b.memory)
100 print(c.identity, c.memory)
101 print()
103 turns += 1
104 n -= 1
106 print(f"Completed after `{turns}` turns!")
107 print()
108 print(a.identity, a.memory)
109 print(b.identity, b.memory)
110 print(c.identity, c.memory)
113if __name__ == "__main__":
114 main()