Chapter 12

These are the solutions to the exercises found in the section .

1. The problem here is the function recursively calls itself twice each time it runs. Let’s make it so that it only calls itself once each time:

   ​	​def​ ​add_until_100​(array):
   ​	​if​ ​not​ array:
   ​	​return​ 0
   ​
   ​	sum_of_remaining_numbers = add_until_100(array[1:])
   ​
   ​	​if​ array[0] + sum_of_remaining_numbers > 100:
   ​	​return​ sum_of_remaining_numbers
   ​	​else​:
   ​	​return​ array[0] + sum_of_remaining_numbers

2. Here is the memoized version:

   ​	​def​ ​golomb​(n, memo):
   ​	​if​ n == 1:
   ​	​return​ 1
   ​
   ​	​if​ n ​not​ ​in​ memo:
   ​	memo[n] = 1 + golomb(n - golomb(golomb(n - 1, memo), memo), memo)
   ​
   ​	​return​ memo[n]

3. To accomplish memoization here, we need to make a key that takes into account both the number of rows and the number of columns. To this end, we can make our key be based on the row and column together.

   ​	​def​ ​unique_paths​(rows, columns, memo):
   ​
   ​	​if​ rows == 1 ​or​ columns == 1:
   ​	​return​ 1
   ​
   ​	​if​ (rows, columns) ​not​ ​in​ memo:
   ​	memo[(rows, columns)] = (unique_paths(rows - 1, columns, memo)
   ​	+ unique_paths(rows, columns - 1, memo))
   ​
   ​	​return​ memo[(rows, columns)]

   Note that we use a Python tuple of (rows, columns) as our key instead of an array [rows, columns]. This is because Python doesn’t allow arrays to be used as hash table keys. We didn’t cover tuples in this book, but in short, they are immutable arrays. In other words, once a tuple is created, it can never be changed.