Newer
Older
"""
class Recursion:
numbers = [9, 4, 8, 10, 2, 4, 8, 3, 14, 4, 8] #[4, 12, 3, 8, 17, 12, 1, 3, 8, 7]
def sum(self, _numbers) -> int:
"""
Return sum of numbers using recursion.
Follow steps:
1. Return 0 for an empty list of numbers.
2. Split the problem by removing the first number `n1` from the list leaving `r` as remaining list (sub-problem).
3. Invoke `sum(r)` recursively on the remaining list.
4. Combine the result for the sub-problem with the first number `n1`: `return n1 + sum(r)`.
"""
# your code
return 0
"""
Return value of n-th Fibonacci number.
- input: n=8
- output: 21
"""
# your code
return 0
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
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
"""
Return a generator object that yields two lists, one with n and the
other with corresponding fib(n).
- input: n=16
- output: generator object that produces:
([0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16],
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987])
"""
# your code
yield ([], [])
def perm(self, _numbers) -> list:
"""
Return permutation (all possible arrangements) for a given input list.
- input: [1, 2, 3]
- output: [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
"""
# your code
return []
def pset(self, _numbers) -> list:
"""
Return powerset (set of all subsets) for a given input list.
- input: [1, 2, 3]
- output: powerset, [[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]
"""
# your code
return []
def find(self, _numbers, match_func) -> list:
"""
Return list of elements n for which match_func(n) evaluates True.
"""
# your code
return []
def find_adjacent(self, pair, _numbers, _i=0) -> list:
"""
Return list of indexes of adjacent numbers in _numbers.
"""
# your code
return []
def find_pairs(self, n, _numbers) -> list:
"""
Return list of pairs from _numbers that add to n,
any pair, any order, no duplicates.
"""
# your code
return []
def find_all_sums(self, n, _numbers) -> list:
"""
Return all combinations of numbers in _numbers that add to n,
(any pair, any order, no duplicates).
"""
# your code
return []
def __init__(self, _numbers=numbers):
"""
Constructor to initialize member variables.
"""
self.numbers = _numbers
run_choices = [
1, # Challenge 1, Simple recursion: sum numbers
2, # Challenge 2, Fibonacci numbers
# 21, # Challenge 2.1, fig_gen()
# 22, # Challenge 2.2, memoization, fib(60), fib(90)
# 3, # Challenge 3, Permutation
# 4, # Challenge 4, Powerset
# 5, # Challenge 5, Finding matches, find()
# 51, # Challenge 5.1, find_adjacent() pairs
# 52, # Challenge 5.2, find_pairs() that add to n
# 6, # Challenge 6, Find all combinations that add to n
# 61, # Challenge 6.1, Find all in medium set
# 7 # Challenge 7, Hard problem finding numbers (extra points)
]
# Ignore this code that loads solution from file, if exists.
# The solution is not distributed.
try:
_from, _import = 'recursion_sol', 'Recursion'
Recursion = getattr(__import__(_from, fromlist=[_import]), _import)
#
except ImportError:
pass
if __name__ == '__main__':
"""
Main driver that runs when this file is executed by Python interpreter.
"""
run_choices = Recursion.run_choices
numbers = [9, 4, 8, 10, 2, 4, 8, 3, 14, 4, 8]
n1 = Recursion(numbers)
print(f'n1.numbers: {n1.numbers}')
# Challenge 1, Simple recursion: sum numbers
if 1 in run_choices:
s = n1.sum(n1.numbers)
print(f'sum(n1.numbers): {s}')
# Challenge 2, Fibonacci numbers
if 2 in run_choices:
n = 30
print(f'\nfib({n}): {n1.fib(n)}')
# Challenge 2.1, fig_gen()
if 21 in run_choices:
gen = n1.fib_gen(20) # yield generator object
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
n, fib = next(gen) # trigger generator
print(f'n: {n}')
print(f'fib(n): {fib}')
# Challenge 2.2, memoization, fib(60), fib(90)
if 22 in run_choices:
n = 60
print(f'fib({n}): {n1.fib(n)}') # ??
n = 90
print(f'fib({n}): {n1.fib(n)}') # ??
# Challenge 3, Permutation
if 3 in run_choices:
lst = [1, 2, 3]
perm = n1.perm(lst)
print(f'\nperm({lst}) -> {perm}')
# Challenge 4, Powerset
if 4 in run_choices:
lst = [1, 2, 3]
pset = n1.pset(lst)
print(f'\npset({lst}) -> {pset}')
lst = n1.numbers
#
# Challenge 5, Finding matches, find()
if 5 in run_choices:
div3 = n1.find(lst, match_func=lambda n : n % 3 == 0)
print(f'\nfind numbers divisible by 3: {div3}')
# Challenge 5.1, find_adjacent() pairs
if 51 in run_choices:
pair = [4, 8]
adj = n1.find_adjacent(pair, lst)
print(f'find_adjacent({pair}, list): {adj}')
# Challenge 5.2, find_pairs() that add to n
if 52 in run_choices:
n = 12
pairs = n1.find_pairs(n, lst)
print(f'find_pairs({n}, list) -> {pairs}')
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
lst = [8, 10, 2, 14, 4] # input list
#
# Challenge 6, Find all combinations that add to n
if 6 in run_choices:
print(f'\nlist: {lst}\n\\\\')
n = 14
all = n1.find_all_sums(n, lst)
print(f'find_all_sums({n}, lst) -> {all}')
#
n = 20
all = n1.find_all_sums(n, lst)
print(f' - find_all_sums({n}, lst) -> {all}')
#
n = 32
all = n1.find_all_sums(n, lst)
print(f' - find_all_sums({n}, lst) -> {all}')
lst = [ # input list
260, 720, 225, 179, 101, 767, 167, 200, 157, 289,
318, 303, 153, 290, 201, 594, 457, 607, 592, 246,
]
#
# Challenge 6.1, Find all in medium set
if 61 in run_choices:
print(f'\nlist({len(lst)}): {lst}\n\\\\')
n = 101 + 201 + 167 # 469 -> [[179, 290], [101, 167, 201]]
all = n1.find_all_sums(n, lst)
for i, s in enumerate(all):
print(f' {i+1:2}: find_all_sums({sum(s)}) -> {s}')
lst = [ # input list
260, 720, 225, 179, 101, 767, 167, 200, 157, 289,
318, 303, 153, 290, 201, 594, 457, 607, 592, 246,
132, 135, 584, 432, 591, 204, 417, 405, 362, 658,
136, 751, 583, 536, 293, 493, 431, 780, 563, 703,
400, 618, 397, 320, 513, 708, 319, 317, 685, 347,
758, 439, 145, 378, 158, 384, 551, 110, 408, 648,
847, 498, 50, 19, # 64 numbers
]
# Challenge 7, Hard problem finding numbers (extra points)
if 7 in run_choices:
print(f'\nlist({len(lst)}) with {len(lst)} numbers.\n\\\\')
n = 101 + 201 + 167 # 469
all = n1.find_all_sums(n, lst)
#
sort_cpm = lambda x, y: -1 if len(x) < len(y) else 1 if len(x) > len(y) else \
-1 if x <= y else 1 if x > y else 0
all.sort(key=cmp_to_key(sort_cpm)) # sort by len(solution)
#
for i, s in enumerate(all):
print(f' {i+1:2}: find_all_sums({sum(s)}) -> {s}')
print()
# #
# n = 899 # 720 + 179, [[720, 179], [260, 179, 157, 303], [167, 289, 153, 290], [289, 153, 457]]
# n = 6240