-
Notifications
You must be signed in to change notification settings - Fork 0
/
climbing-stairs-problem.py
119 lines (99 loc) · 3.68 KB
/
climbing-stairs-problem.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
"""
To run python linter pylint on this file, run this in the CLI:
pylint pylint_example.py
Or even better, pip3 install rerun and then run this in the CLI:
rerun "pylint pylint_example.py; python3 pylint_example.py"
I use pyright to do static type checking in VSCode
"""
# pylint: disable = too-few-public-methods, invalid-name
# learn unit testing in python later: https://www.youtube.com/watch?v=6baJ5t83820
from math import sqrt
class Solution_Number_Pattern_DO_NOT_USE: # really slow (the other solution is better)
"""
Solution using number pattern for:
https://leetcode.com/explore/interview/card/top-interview-questions-easy/97/dynamic-programming/569/
"""
def __init__(self):
self.list = set('1')
def climbStairs(self, number: int) -> int:
"""get answer"""
if number == 1:
return 1
# otherwise
self.__init__()
for _ in range(number-1):
self.list = self.get_next_level()
options_count = len(self.list)
return options_count
def get_next_level(self) -> set:
"""get next level up by replacing self.list with new list"""
new_list = set()
for i in self.list:
for index in range(len(i)):
temporary_string = i[:index] + '1' + i[index:]
new_list.add(temporary_string)
new_list_with_2s = new_list.copy()
for i in new_list:
for index in range(len(i)):
if i[index:index+2] == '11':
temporary_string = i[:index] + '2' + i[index+2:]
new_list_with_2s.add(temporary_string)
return new_list_with_2s
class Solution_previous_2_steps: # faster solution
"""
Solution using previous 2 numbers of steps for:
https://leetcode.com/explore/interview/card/top-interview-questions-easy/97/dynamic-programming/569/
"""
def __init__(self):
self.memo = {0:0, 1:1, 2:2}
def climbStairs(self, number: int) -> int:
"""get answer"""
if number in self.memo:
return self.memo[number]
# otherwise
self.memo[number] = self.climbStairs(number - 1) + self.climbStairs(number - 2)
return self.memo[number]
def solution_with_fibonacci_formula(number: int) -> int: # even faster solution
"""Solution using Fibonacci formula"""
sqrt5 = sqrt(5)
answer = (pow((1 + sqrt5)/2, number + 1) - pow((1 - sqrt5)/2, number + 1)) / sqrt5
answer = round(answer)
return answer
s1 = Solution_Number_Pattern_DO_NOT_USE()
s2 = Solution_previous_2_steps()
s3 = solution_with_fibonacci_formula
print(1)
assert s1.climbStairs(1) == 1
assert s2.climbStairs(1) == 1
assert s3(1) == 1
print('method 1 works: ', s1.climbStairs(1) == 1)
print('method 2 works: ', s2.climbStairs(1) == 1)
print('method 3 works: ', s3(1) == 1)
print(2)
assert s1.climbStairs(2) == 2
assert s2.climbStairs(2) == 2
assert s3(2) == 2
print('method 1 works: ', s1.climbStairs(2) == 2)
print('method 2 works: ', s2.climbStairs(2) == 2)
print('method 3 works: ', s3(2) == 2)
print(3)
assert s1.climbStairs(3) == 3
assert s2.climbStairs(3) == 3
assert s3(3) == 3
print('method 1 works: ', s1.climbStairs(3) == 3)
print('method 2 works: ', s2.climbStairs(3) == 3)
print('method 3 works: ', s3(3) == 3)
print(4)
assert s1.climbStairs(4) == 5
assert s2.climbStairs(4) == 5
assert s3(4) == 5
print('method 1 works: ', s1.climbStairs(4) == 5)
print('method 2 works: ', s2.climbStairs(4) == 5)
print('method 3 works: ', s3(4) == 5)
print(5)
assert s1.climbStairs(5) == 8
assert s2.climbStairs(5) == 8
assert s3(5) == 8
print('method 1 works: ', s1.climbStairs(5) == 8)
print('method 2 works: ', s2.climbStairs(5) == 8)
print('method 3 works: ', s3(5) == 8)