Puzzles with iPython
Tip

Ctrl+Q and then Ctrl+J is shortcut to go to next line with iPython

Smallest Missing Positive Integer
Q. Find the smallest missing number from the given list

From the given list of integers find the smallest positive integer number that is missing.
If the given list is `[1, 2, 4, 5, 0, 1]` and function should return `3` which is smallest positive missing number.
smallest_missing_number.python
In [2]: def smallest_missing_number(lst):
...: n = 1 # Smallest positive number is 1
...: given_set = set(lst) # make a unique elements set
...: # Verify number starting with 1 in given_set
...: # Return first missing number from the given_set
...: # Which is our desire result
...: while n in given_set:
...: n +=1
...: return n
...:
In [3]: smallest_missing_number([1, 0, 3, 5, 8, 9])
Out[3]: 2
Staircase Problem
Q. For given n
stairs, find the number of ways a person can climb to reach top. he can climb 1 or 2 steps at a time

Consider a scenario with 3 stairs with [1, 2] possible ways to climb.
One possibility is he can climb 1 step at a time, {1, 1, 1}
Second Possibility is { 1, 2} or {2, 1}
Total = 3 Possibilities
staircase.python
In [5]: def staircase(n , X): # n is total stairs, X possible ways he can climb at a time
...: # Using DP to solve this problem
...: memo = [0 for _ in range(n+1)]
...: memo[0] = 1 # For 0 steps there is 1 possibility
...:
...: for i in range(1, n + 1):
...: for x in X:
...: if i  x >= 0:
...: memo[i] += memo[i  x]
...: return memo[n]
...:
In [6]: staircase(3, [1])
Out[6]: 1
In [7]: staircase(3, [1, 2])
Out[7]: 3
staircase_list_comphrehension.python
In [35]: def staircase(n, X):
...: memo = [0 for _ in range(n+1)]#n+1 as we are ignoring 0 location
...: memo[0] = 1
...: for i in range(n+1):
...: memo[i] += sum(memo[i x] for x in X if i  x >=0)
...: return memo[n]
Fibonacci With Memoization and DP
Print fibonacci series with Memoization technique/Dynamic Programming
fibo_memo.python
In [15]: def fibo_memo(n, memo):
...:
...: if memo[n] != 0:
...: return memo[n]
...:
...: if n == 1:
...: return 1
...: if n == 2:
...: return 1
...:
...: memo[n] = fibo_memo(n 1 , memo) + fibo_memo(n 2, memo)
...: return memo[n]
print_fibo.python
In [22]: def print_fibo(n):
...: memo = [0 for _ in range( n + 1)]
...: memo[1] = 1
...: memo[2] = 1
...: fibo_memo(n, memo)
...: print(memo)
No comments:
Post a Comment