**CS 1109: Fundamental Programming Concepts (Summer 2023)**
[Home](../index.md.html) • [Schedule](../schedule.md.html) • [Syllabus](../syllabus.md.html) • [Assignments](../assignments.md.html) • [Labs](../labs.md.html)
(#) Lab 5: Indefinite Iteration
In this lab, you will implement a series of functions which will require you to use `while`-loops.
!!! note: Due Date
This lab is due **Thursday, July 13th, 2023 at 11:30am EDT**.
(##) Exercise 1: The Collatz Conjecture
The [Collatz Conjecture](https://en.wikipedia.org/wiki/Collatz_conjecture), sometimes referred to as the $3x+1$ problem, is one of the most famous **unsolved** problems in mathematics. Perhaps the primary reason driving its popularity is how simple the problem statement is.
Let $f(n)$ be a function that takes as input an arbitrary *positive* integer $n$ and is defined as:
\begin{equation}
f(n) = \begin{cases}
n/2 & \text{if $n$ is even} \\
3n + 1 & \text{if $n$ is odd}
\end{cases}
\end{equation}
In English, if $n$ is even $f$ divides $n$ by 2, and if $n$ is odd $f$ triples $n$ and adds 1.
We can use $f$ to form a *sequence* of integers by calling $f$ repeatedly, starting with any positive integer $n$, and using the result of the last call to $f$ as the input to the next. Informally, this sequence looks like:
\[
n, f(n), f(f(n)), f(f(f(n))), f(f(f(f(n)))), \ldots
\]
For example, if $n = 12$, then we get the sequence
\[
12, 6, 3, 10, 5, 16, 8, 4, 2, 1.
\]
We can now state the Collatz Conjecture:
!!! note: **The Collatz Conjecture**
For every positive integer $n$, the sequence
\[
n, f(n), f(f(n)), \ldots
\]
will eventually reach 1.
As mentioned previously, the Collatz Conjecture is still unproven for all positive integers $n$. However, as of 2020, the conjecture has been proven to hold for all integers up to $2^{68}$ by using a computer to construct each sequence.
(###) Your Task
Your task for this exercise is to write a function `collatz(n)` that takes as a parameter a positive `int` `n` and generates the Collatz sequence and returns the number of steps it takes to reach 1 as an `int`.
For example, in the case where `n = 12`, `collatz(12)` would return 9 as $f$ had to be called 9 times to reach 1 whereas `collatz(2)` would return 1 as $f$ only needed to be called once to reach 1 (i.e., $f(2) = 1$).
1. Create a new Python script called `collatz.py` in your `cs1109` workspace in VSCode.
2. Define a function `collatz(n)` that takes a single parameter `n` that is a positive `int`.
3. Implement `collatz(n)` according to the above description.
4. Test `collatz(n)` either by calling the `collatz` function in your script after the definition and running the script or by importing the function into the REPL.
(##) Exercise 2: Number Guessing Game
In this exercise you will finish writing a script to play a number guessing game against the computer.
Download the starter code for this exercise here: Click here to download `lab5_guess.py`.
!!! Tip: `random.randint(a,b)` function
For both Part A and Part B, you will need to use the `randint(a,b)` function from Python's `random` module. `randint(a,b)` returns a random integer `N` such that `a <= N <= b`. The function has already been imported for you in the `lab5_guess.py` script.
(###) Part A: User Guesses
For Part A, you will write a function that randomly selects a number between 1 and 100 and repeatedly prompts the user for a number to guess until the user guesses the number correctly. Each time the user guesses the function should `print` a message to the user informing them whether the guess was too high, too low, or correct. Once the correct guess is made, a victory message should also be printed along with the **number of guesses the user made**.
(####) Instructions
1. Open `lab5_guess.py` in your `cs1109` workspace in VSCode.
2. Find the function header for the `user_guess()` function. Implement the function according to the above specification. Note that this function does not accept any parameters and should not return any value (i.e., it is a void function).
3. Play the game by running the script and following the included prompt.
(###) Part B: Machine Guesses
For Part B, you will write a similar function to part A, except this time the computer will make the guesses.
The `machine_guess()` function first prompts the user for a number between 1 and 100 to serve as the "secret" number. Until the "secret" number is guessed correctly, repeatedly do the following:
- Generate a random number between the best lower bound guessed so far (initially 1) and the best upper bound so far (initially 100) and `print` it to the user. For example, if the "secret" number is 50, and the machine has already guessed 25 and 75, then a random number should be generated between 26 and 74 (both inclusive).
- Prompt the user to enter `'H'` if the guessed number is too high, `'L'` if the guessed number is too low, or `'C'` if the guessed number is correct.
- If `'C'` is entered, a victory message and the total **number of gusses made** should be printed and then the function should terminate.
(####) Instructions
1. Find the function header for the `machine_guess()` function. Implement the function according to the above specification. Note that this is also a void fucntion.
2. Play the game by running the script and following the included prmpt.
(#) Turning it in
Upload your `collatz.py` and `lab5_guess.py` files to Gradescope.
-------------------------------------------------------------------------------
Copyright © [Zachary J. Susag](https://zacharysusag.net)
Unless specified elsewhere on this page, this work is licensed under a [Creative Commons Attribution-ShareAlike 4.0 International License](http://creativecommons.org/licenses/by-sa/4.0/).
-------------------------------------------------------------------------------