The Collatz conjecture (https://en.wikipedia.org/wiki/Collatz_conjecture) is an unproven mathematical rule that says the following:

Take any positive integer n. If n is even, divide it by 2 to get n / 2 (use integer division so that you dont end up with floating point numbers). If n is odd, multiply it by 3 and add 1 to obtain 3n + 1. Repeat the process indefinitely, and eventually you will reach 1.

Write a recursive function called collatz that takes in a single positive integer argument n and returns the list of numbers in the collatz sequence from n to 1, inclusive. For example, suppose your initial number was 5. Then the collatz sequence would be the following:

The initial number is 5.

5 is odd, so the next number is 5*3 + 1 = 16

16 is even, so the next number is 16//2 = 8

8 is even, so the next number is 8//2 = 4

4 is even, so the next number is 4//2 = 2

2 is even, so the next number is 2//2 = 1

We have reached 1, so the sequence is complete, and the function would return the list _{[5,16,8,4,2,1]}

Hints:

• This function returns a list, so both your base case and your recursive case(s) need to return a list. You will need to add elements to the front of the list in this problem.
• .append doesnt add things to the front of a list, so put the element you want to add in brackets to turn it into a list and then use list addition. To put element x at the front of the list ls, youd use [x] + ls. For example, note that:

collatz(5) = [5]+collatz(16) = [5]+[16,8,4,2,1] = [5,16,8,4,2,1]

Constraints:

• The collatz function must be implemented using only recursion. Do not use any loop constructs (while or for).
• Do not import any modules (except random, for problem C).
• You may assume that your function will only be called with positive integers.
• Dont use the input() function, as this will break our grading scripts.
• Your submission should have no code outside of function definitions (comments are fine).

Examples:

>>> collatz(5)

[5, 16, 8, 4, 2, 1]

>>> collatz(1)

[1]

>>> collatz(123)

[123, 370, 185, 556, 278, 139, 418, 209, 628, 314, 157, 472, 236, 118, 59, 178, 89, 268, 134, 67, 202, 101, 304, 152, 76, 38, 19, 58, 29, 88,

44, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1]

Image source: https://xkcd.com/710/

Problem B. (10 points) Finding the Minimum

Write a recursive function find_min that takes in one argument, a list of integers num_list, and returns the minimum value in that list. You may assume that num_list contains at least one element. Note that even if there is a tie, there should still only be one minimum value (it just appears more than once in the list).

Constraints:

• The find_min function must be implemented using only recursion. Do not use any loop constructs (while or for).
• Built-in functions like min and sorted that trivialize the problem are banned, for obvious reasons.
• Do not import any modules (except random, for problem C).
• Dont use the input() function, as this will break our grading scripts.
• Your submission should have no code outside of function definitions (comments are fine).

Examples:

>>> find_min([8])

8

>>> find_min([0, 2, -5, -2, 5, -1, 4, 0, -5, -1])

-5

>>> find_min([20, 34, 32, 34, 48, 43, 21])

20

Problem C. Playing Tic-Tac-Toe Perfectly

In Homework 5, we created a program to play tic-tac-toe by choosing an empty spot at random. This is generally a very bad strategy: most preschoolers can beat it more than half the time (even when they dont cheat). But, with the power of recursion, we can make a much better tic-tac-toe AI: in fact, we can make one that never loses. To do this, our AI will look at every possible sequence of moves and try to find a strategy that forces a win, or at least forces a draw if thats not possible.

Creating a tic-tac-toe AI that cant lose will require a few steps. Youll want to start by copying in all of your tic-tac-toe code from Homework 5: most of the functions there will be useful for this problem as well. We will post a solution to Homework 5 for those of you who didnt get all of the functions working.

Write a recursive function called force_win(board), which takes in one argument: board is a list representation of a tic-tac-toe board (see Homework 5). force_win should return an integer that represents the current state of the board. Board state can be one of three values:

• 1 means that X has won, or can force a win: that is, there are moves that X can make so that no matter what O does, X will win
• -1 means that O has won, or can force a win: that is, there are moves that O can make so that no matter what X does, O will win
• 0 means that neither of the above is true: if both players play perfectly, the game will end in a draw

This means that when looking at potential next moves, X will attempt to find moves that leave the board in the highest value for board state possible (because X would prefer to win (state 1), over a draw (state 0), over losing to O (state -1)).

Whereas O will attempt to find moves that leave the board in as low of a board state as possible (because O would prefer to win (state -1), over a draw (state 0), over losing to X (state 1)).

The general approach is as follows:

1. Figure out whose turn it is using the open_slots function. Since we start with 9 open spots and alternate turns, if there are an odd number of open slots its Xs turn, otherwise its Os.
2. As your base cases, use the winner function and determine whether the game is already over. If it is, return the appropriate board state (1 for X winning, 0 for a draw, -1 for O winning).
3. If it is currently Xs turn, then we want to find the move that would result in the highest possible value for the board state. So loop through the possible moves (that is, loop through the open slots in the board), and keep track of the board state you get back for each move: we will return the highest one. In particular, do the following for each possible move:
   1. Create a copy of the current board (you can use board[:] for this).
   2. Place the potential move on the copied board (put an X in that slot).
   3. Recursively call force_win on that board to see what the board state would be (think about why this is guaranteed to move towards a base case).
4. At the end of the loop, return the highest board state value that you found.
5. If it is Os turn, do the opposite: return the lowest possible board state you could get from any of Os potential moves.

Test this function using the examples below: only go on to the next part after you are sure that force_win works.

Finally, you will alter the tic_tac_toe function from Homework 5 to use your AI to decide moves for player O (X should still move randomly).

Each time O moves, you should loop through the possible moves (using the open_slots function), and call force_win on each of them, then choose the move that resulted in the lowest board state. Note that this is a little more complex than the loop within force_win, because you have to keep track of not only the lowest board state you have found, but also what move (i.e. what index in the board) got you that result.

Use the play_games function (also from Homework 5) to test the win rate of your AI. O should never lose.

Hints:

• Unlike the previous problem, you will need both a loop AND recursion in this function.

Constraints:

• force_win must use recursion (in addition to a loop).
• You may assume that your function will only be called with valid board states (you wont be given boards where both X and O have won).
• Dont use the input() function, as this will break our grading scripts.
• Your submission should have no code outside of function definitions (comments are fine).
• Calling force_win on an empty board will probably take some time, since there are something like 300,000 possible board states to analyze, but it should still run in under a minute on any lab machine.

Examples (shown below each example is the board it represents, with the optimal move highlighted, if applicable):

>>> force_win([O, X, O, X, X, O, X, O, X])

0

>>> force_win([X, X, O, O, X, X, O, X, O])

1

>>> force_win([X, -, O, X, O, -, O, -, X])

-1

>>> force_win([X, O, X, X, O, X, -, -, O])

-1

>>> force_win([X, O, X, X, O, -, -, X, O])

0

>>> force_win([X, O, X, X, O, -, -, -, O])

1

(Note: with the next three tests, the upper left corner is only one of multiple optimal moves in each case)

>>> force_win([-, O, -, -, X, X, -, O, X])

1

>>> force_win([-, O, -, -, X, -, -, -, -])

1

>>> force_win([-, -, -, -, -, -, -, -, -])

0

(Note: This may take a while: 100 games can take several minutes to complete. Your number of draws vs.

O wins will vary, but you should have zero X wins)

>>> play_games(1)

X wins: 0

O wins: 1

Draws: 0

>>> play_games(100)

X wins: 0

O wins: 73

Draws: 27