Chapter 11

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

1. Let’s call our function character_count. The first step is to pretend that the character_count function has already been implemented.

   Next, we need to identify the subproblem. If our problem is the array ["ab", "c", "def", "ghij"], then our subproblem can be the same array missing one string. Let’s specifically say that our subproblem is the array minus the first string, which would be ["c", "def", "ghij"].

   Now, let’s see what happens when we apply the “already-implemented” function on the subproblem. If we were to call character_count(["c", "def", "ghij"]), we’d get a return value of 8, since there are eight characters in total.

   So to solve our original problem, all we have to do is add the length of the first string ("ab") to the result of calling the character_count function on the subproblem.

   Here’s one possible implementation:

   ​	​def​ ​character_count​(array):
   ​	​# Base case: when the array is empty:​
   ​	​if​ ​not​ array:
   ​	​return​ 0
   ​
   ​	​return​ len(array[0]) + character_count(array[1:])

   Note that our base case is an empty array, in which case there are zero characters to count.

2. First, let’s pretend the select_even function already works. Next, let’s identify the subproblem. If we try to select all the even numbers in the example array [1, 2, 3, 4, 5], we could say that the subproblem is all the numbers in the array besides the first one. So let’s imagine select_even([2, 3, 4, 5]) already works and returns [2, 4].

   Since the first number in the array is 1, we don’t want to do anything other than return the [2, 4]. However, if the first number in the array was a 0, we’d want to return the [2, 4] with the 0 added to it.

   Our base case is an empty array.

   Here’s one possible implementation:

   ​	​def​ ​select_even​(array):
   ​	​if​ ​not​ array:
   ​	​return​ []
   ​
   ​	​if​ array[0] % 2 == 0:
   ​	​return​ [array[0]] + select_even(array[1:])
   ​	​else​:
   ​	​return​ select_even(array[1:])

3. The definition of a triangular number is n plus the previous number from the sequence, with n referring to the place where the number falls in the pattern. (For example, if we’re computing the sequence’s seventh number, then n is 7.) If the name of our function is triangle, we can express this simply as n + triangle(n - 1). The base case is when n is 1.

   ​	​def​ ​triangle​(n):
   ​	​if​ n == 1:
   ​	​return​ 1
   ​
   ​	​return​ n + triangle(n - 1)

4. Let’s pretend that our function, index_of_x, has already been implemented. Next, let’s say the subproblem is our string minus its first character. For example, if our input string is "hex", the subproblem is "ex".

   Now, index_of_x("ex") would return 1. To calculate the index of the "x" for the original string, we would add 1 to this since the additional "h" at the front of the string moves the "x" down one index. Here’s our code:

   ​	​def​ ​index_of_x​(string):
   ​	​if​ string[0] == ​"x"​:
   ​	​return​ 0
   ​
   ​	​return​ index_of_x(string[1:]) + 1

5. This exercise is similar to the staircase problem. Let’s break this down:

   From the starting position, we have only two choices of movement. We can either move one space to the right or one space downward.

   What this means is that the total number of unique shortest paths will be the number of paths from the space to the right of S + the number of paths from the space below S.

   The number of paths from the space to the right of S is the same as calculating the paths in a grid of six columns and three rows, as you can see here:

   

   The number of paths from the space below the S is the equivalent of the paths in a grid of seven columns and two rows:

   

   Recursion allows us to express this beautifully:

   ​	​return​ unique_paths(rows - 1, columns) + unique_paths(rows, columns - 1)

   All we need to do now is add the base case. Possible base cases include when we have just one row or one column, since in such cases, there’s only one path available to us.

   Here’s the complete function:

   ​	​def​ ​unique_paths​(rows, columns):
   ​	​if​ rows == 1 ​or​ columns == 1:
   ​	​return​ 1
   ​
   ​	​return​ unique_paths(rows - 1, columns) + unique_paths(rows, columns - 1)