90 lines
3.1 KiB
Markdown
90 lines
3.1 KiB
Markdown
# The Collatz conjecture
|
|
|
|
Original assessment brief: https://github.com/turner-townsend/backend-assessment/blob/master/README.md#the-collatz-conjecture
|
|
|
|
A Python program that calculates the number of steps in the Collatz sequence (3n + 1 problem) needed to reach 1.
|
|
|
|
## What is the Collatz conjecture?
|
|
|
|
The Collatz conjecture is an unsolved mathematical problem that defines a sequence:
|
|
|
|
- Start with any positive integer n
|
|
- If n is even: divide by 2
|
|
- If n is odd: multiply by 3 and add 1
|
|
- Repeat until n reaches 1
|
|
|
|
The conjecture states that this sequence will always eventually reach 1, regardless of the starting number.
|
|
|
|
## Requirements
|
|
|
|
- Python 3.9+
|
|
- pytest (for running tests)
|
|
|
|
## Usage
|
|
|
|
```bash
|
|
python collatz.py
|
|
```
|
|
|
|
### Examples
|
|
|
|
```
|
|
Please enter a whole number: 1
|
|
Result: 0 steps needed to reach 1
|
|
Please enter a whole number: 3
|
|
Step #1: odd, multiply by 3 and add 1 -> 10
|
|
Step #2: even, divide by 2 -> 5
|
|
Step #3: odd, multiply by 3 and add 1 -> 16
|
|
Step #4: even, divide by 2 -> 8
|
|
Step #5: even, divide by 2 -> 4
|
|
Step #6: even, divide by 2 -> 2
|
|
Step #7: even, divide by 2 -> 1
|
|
Result: 8 steps needed to reach 3
|
|
Please enter a whole number: 0
|
|
Result: 0 steps needed to reach 0
|
|
Please enter a whole number: !£$
|
|
ERROR: integer required
|
|
```
|
|
|
|
## Features
|
|
|
|
- **Step-by-step output**: Shows each transformation in the sequence
|
|
- **Interactive**: Continuous input until Ctrl+C
|
|
- **Input validation**: Handles invalid input gracefully
|
|
- **Edge cases**: Handles 1, 0, and negative numbers by returning 0 steps
|
|
|
|
## Tests
|
|
|
|
```bash
|
|
pytest -v
|
|
```
|
|
|
|
Example output:
|
|
|
|
```
|
|
➜ collatz git:(main) ✗ pytest -v
|
|
============================================== test session starts ==============================================
|
|
platform linux -- Python 3.12.2, pytest-8.3.4, pluggy-1.5.0 -- /home/jamey/.venv/bin/python
|
|
cachedir: .pytest_cache
|
|
rootdir: /home/jamey/Projects/turner-townsend-backend-assessment/collatz
|
|
plugins: mock-3.14.0, asyncio-0.21.2
|
|
asyncio: mode=Mode.STRICT
|
|
collected 6 items
|
|
|
|
test_collatz.py::test_calculate_steps_for_1 PASSED [ 16%]
|
|
test_collatz.py::test_calculate_steps_for_2 PASSED [ 33%]
|
|
test_collatz.py::test_calculate_steps_for_3 PASSED [ 50%]
|
|
test_collatz.py::test_calculate_steps_for_6 PASSED [ 66%]
|
|
test_collatz.py::test_calculate_steps_for_large_number PASSED [ 83%]
|
|
test_collatz.py::test_calculate_steps_for_zero_and_negative PASSED [100%]
|
|
|
|
=============================================== 6 passed in 0.01s ===============================================
|
|
```
|
|
|
|
## Design notes
|
|
|
|
- **Class-based structure**: Encapsulates the calculation logic for easy testing and reuse
|
|
- **Combined calculation and display**: The calculation method handles both computing steps and showing progress
|
|
- **Edge case handling**: Returns 0 steps for numbers ≤ 1
|
|
- **User-friendly**: Clear step-by-step output shows the mathematical process as it happens
|