Coverage for blog/dsa/stack/__init__.py: 66%

1import secrets 

2from collections.abc import Iterable 

3from typing import Generator, Generic, TypeVar 

4 

5from typing_extensions import Self 

6 

7T_Stack = TypeVar("T_Stack") 

8 

9 

10class Stack(Generic[T_Stack]): 

11 

12 identity: str 

13 memory: list[T_Stack] 

14 index: int 

15 

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 

22 

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) 

28 

29 return self 

30 

31 def push(self, item: T_Stack) -> None: 

32 self.index += 1 

33 self.memory.append(item) # Yes, append is bad. 

34 

35 def pop(self) -> T_Stack: 

36 if self.index == -1: 

37 raise ValueError(f"Stack `{self.identity}` is empty.") 

38 

39 top = self.memory.pop(self.index) 

40 self.index -= 1 

41 return top 

42 

43 @property 

44 def top(self) -> T_Stack: 

45 if self.index == -1: 

46 raise ValueError(f"Stack `{self.identity}` is empty.") 

47 

48 return self.memory[self.index] 

49 

50 

51def hanoi_turn(s: Stack[int], t: Stack[int]): 

52 

53 if s.index == -1: 

54 s.push(t.pop()) 

55 return 

56 elif t.index == -1: 

57 t.push(s.pop()) 

58 return 

59 

60 bigger, smaller = (s, t) if s.top > t.top else (t, s) 

61 bigger.push(smaller.pop()) 

62 

63 

64def hanoi(a: Stack[int], b: Stack[int], c: Stack[int]) -> Generator[None, None, None]: 

65 

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.") 

70 

71 turn = 0 

72 while len(c.memory) != n and len(b.memory) != n: 

73 

74 yield 

75 s, t = pairs[turn % 3] 

76 hanoi_turn(s, t) 

77 turn += 1 

78 

79 

80def main(): 

81 size = 25 

82 

83 a = Stack[int](identity="a") 

84 for k in range(size): 

85 a.push(size - k) 

86 

87 turns = 0 

88 n = 0 

89 for _ in hanoi(a, b := Stack[int](identity="b"), c := Stack[int](identity="c")): 

90 

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) 

96 

97 elif n == 1: 

98 print(a.identity, a.memory) 

99 print(b.identity, b.memory) 

100 print(c.identity, c.memory) 

101 print() 

102 

103 turns += 1 

104 n -= 1 

105 

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) 

111 

112 

113if __name__ == "__main__": 

114 main()