Assignment 4

Due Tues, Sep 25

Please create a single zip file named <userid>-hw4.zip (i.e. kay-hw4.zip) that contains these files:
hw4-1a.py (the solution of question 1a)
hw4-1b.py (the solution of question 1b)
hw4-2.py (the solution of question 2)
hw4-2bonus.py (Optional: the solution to the bonus in question 2)

Email your solutions to kay <at> ischool. Include comments in each script stating your name, the name of any collaborators, and approximate time it took you to complete the exercise.

1. More Phone Number Tricks

Write a function, last_digit, that returns the last digit of an integer. Write a second function, first_part, that returns the integer with the last digit removed. For example, last_digit(1234567) should give 7, while first_part(1234567) should give 123456. Make sure both functions return ints.

a) Using the above functions, write a function, minus_last, that takes a number and subtracts the last digit from the rest of the number. For example, minus_last(1234567) should give 123456 – 7 = 123449.

Now write a script that asks the user for their phone number. Add minus_last of the phone number to the phone number itself. Display the number you compute in this step.

Next, replace the result with minus_last of the result. Repeat this step as long as the result has more than one digit. Display the final result. What digit do you get? Please note your answer in the program comments.

b) Using the above functions, write a function, double_plus_last, that takes a number, doubles first_part of the number and adds the last digit. For example, double_plus_last(1234567) should give 2 * 123456 + 7 = 246919.

Next, write a script that asks the user for their phone number. Subtract double_plus_last of the number from the phone number itself. Display the number you compute in this step.

Replace the result with double_plus_last of the result. Repeat this step as long as the result has more than one digit. Display the final result. What digit do you get? Please note your answer in the program comments.

2. Winning Strategies

In many simple two-player games, one the players can learn to win the game every single time. The most familiar example may be tic-tac-toe. In this game, the first player can play in such a way that she always wins, no matter what moves the second player makes. We say that the first player has a Winning Strategy.

To write a winning strategy for tic-tac-toe, we can’t just list a sequence of moves, as in center square, upper-right, etc. The moves have to change depending on what the opponent plays. So a winning strategy specifies a next move for every possible state of the tic-tac-toe board. You can think of it as a function from the state of the game to a next move.

In fact, many more complicated games have winning strategies: checkers, chess (assuming there are rules to break draws). This means that if the players are perfect, and always choose the best move, the player with the winning strategy will always win. These games are still fun to play, though, because they have so many states that no human can remember a winning strategy.

Perhaps the easiest way to think about winning strategies is recursively. Let’s call a state of the game “hot” if the current player to move has a winning strategy to finish the game – this is the state that you want to be in. Otherwise, let’s cold it cold. Clearly, if a player can win in one move, the state of the game is hot. If the current player loses immediately for any available move, the state of the game is cold.

If the game is not about to end, the best strategy is to “play not to lose.” That is, the state of the game is hot if the current player has a move that puts the game in a cold state for the next player. Otherwise the state of the game is cold – whatever move the current player makes, the state of the game will be hot for the next player.

If the starting state for the whole game is hot, the first player has a winning strategy. If the stating state for the whole game is cold, the second player has a winning strategy.

For this problem, let’s consider a two-player version of the decreasing number game from class. The game begins with a number N – this is the state of the game. Two players take turns decreasing the number. Each player has two moves available: they can subtract 1 from the number, or divide it in half (not integer division - use floats for this!). The player that decreases the number below 1 is the loser.

Write a script to prompt the user for the starting state of the game, N. Compute which player has a winning strategy. If it's the first player, print "The first player has a winning strategy." If it's the second player, print "The second player has a winning strategy."

Hint: Write a recursive function, is_hot, to check whether a state of the game is hot. For a base case, note that any game state less than 2 is cold – no matter which move a player makes, the number will drop below 1 and the player loses.

Optional Bonus: Write a program that actually plays the decreasing number game against the user, and follows a winning strategy whenever one is available. In other words, when it is the computer’s turn to move, it selects a move that places the game in a cold state, if such a move is available.