Keyboard shortcuts

Press ← or → to navigate between chapters

Press S or / to search in the book

Press ? to show this help

Press Esc to hide this help

Project 1: Guessing Game

Welcome to your first project!

Here's a game that is probably familiar. Somebody picks a number and will not tell you what it is. You can ask questions, and only two kinds are allowed: is it exactly this? and is it bigger than this? How can you find the number using as few questions as possible?

It's a simple game, but it captures some of what you'll face throughout your career: a search space larger than you can reasonably check one at a time, and rewards for being clever and thrifty.

Over three weeks you will implement several strategies for playing this game, run all of them thousands of times, and make an argument about which method is best.

You will also practice with the software development tools you're learning while you're at it. You will make your own copy of a repository, clone it, commit as you go, and at one point in the middle we will change the code underneath you and you will have to merge our changes into yours. You will practice working at the command line, first in a toy exercise, and then as a way of navigating git and doing your development work on the rest of the project.

So... Checkpoint 1 is not actually about the guessing game. It is a shell-based role-playing dungeon (!), and it is here to give you practice moving around on your computer at the command line before taking on the full project. It shares the repo so that you only set things up once, but it's really separate work, and you can finish it before you write any real Rust.

What is due when

  • Checkpoint 1, Friday September 18. The dungeon only
  • Checkpoint 2, Friday September 25. Implementing four guessing strategies
  • The project, Friday October 2. Everything else, and the writeup
  • Code review, in discussion the week of October 6.

Meet your project repo

Your starting point is https://github.com/rust4ds/ds210-fa26-project-1.

On GitHub, click Use this template, then Create a new repository. Name it ds210-fa26-project-1, the same as ours, and set it to Private. Then clone it. Work in your copy and push to it. That repo is what you submit at each checkpoint.

The template repo arrives in two pieces. To start, what you clone has checkpoint 1 in it. The guessing game itself, and the tests for it, come in an update you will merge around September 21. Files marked (Sep 21) below are not in your clone at first.

src/
  dungeon.rs        your answers from checkpoint 1
  game.rs           play a game yourself against the computer
  measure.rs        run many games and report what happened (Sep 21)
  plot.rs           run every strategy, draw the plot, print the table            (Sep 21)
  secret_keeper.rs  the other side of the game: who knows the number, and answers (Sep 21)
  strategies.rs     every guessing strategy, examples plus ones you write         (Sep 21)
  tests.rs          every test in the project
  version.rs        which release of the base repo you have
dungeon_transcript.txt   your bashcrawl session from checkpoint 1 goes in here
.gitignore          a gitignore file that already takes out `target` and some cruft
Cargo.lock          for now, you can ignore - it's about dependencies
Cargo.toml          for now, you can ignore - it's about dependencies
README.md           it starts as some instructions, and is where you'll put your write-up

From checkpoint 2 onward, everywhere you have to write code is marked todo! and the program will stop there if it reaches one. Only change the functions marked todo!. Checkpoint 1 has no todo!s: there, the things you change are the constants in dungeon.rs, your session in dungeon_transcript.txt, and the Author line of README.md.

Getting the update

The rest of the project arrives as a second commit on our template repo, and you pull it into your own copy. You'll do this once, the first time you start working towards checkpoint 2.

First, tell git where our repo is. origin is already your copy; upstream will be ours. From your repo, you can paste this into the terminal:

git remote add upstream https://github.com/rust4ds/ds210-fa26-project-1.git
git fetch upstream --tags

Becuase your repo was made with Use this template, you started with a clean history of your own. That means git doesn't know your repo and ours are related, and it will refuse to merge two histories it thinks are strangers. This next command tells git how they are related, by matching up the beginning of your repo with the beginning of the template. You can also paste this in exactly:

git merge -s ours --allow-unrelated-histories phase1 -m "connect this repo to the template"

Now you're ready for the merge itself:

git merge upstream/main

Expect one conflict, in src/dungeon.rs. We changed a line that you also changed to pass checkpoint 1, and git will refuse to guess which version you meant. Run git status to see it, then open the file. Like we practiced in Discussion 2, the two versions are marked off like this:

<<<<<<< HEAD
what your copy says
=======
what our copy says
>>>>>>> upstream/main

Your job is to decide how to combine those versions and delete all the marker lines. (This might take a second to think about - try to figure out why each side made a change, and whether you want to take one version, the other, or a hybrid of the two.) When it looks right:

cargo test --bin game cp1

should all pass again. And then you save as usual:

git add src/dungeon.rs
git commit -m "merge the project update"
git push

Then run cargo test --bin game cp2. It should run and fail, because you have not started the checkpoint 2 work yet! If it says there are no tests to run, you didn't successfully merge the update yet.

Running your project

cargo run --bin game -- --strategy random          # play a game yourself
cargo run --bin game -- --strategy bad --min 2 --max 6
cargo run --bin game -- --help                     # every option
cargo run --bin plot                               # writes plot.png and prints the table

Playing against your own strategy is the fastest way to see what it does. Use a small range and you can follow every question.

None of these work until the September 21 update arrives. For checkpoint 1 the only command you need is cargo test --bin game cp1.

Running the tests

cargo test --bin game cp1     # your dungeon answers
cargo test --bin game cp2     # do your strategies work, and work as asked?
cargo test --bin game cp3     # everything else
cargo test --bin game         # all the tests at once

Each test is named for a single function and a single thing that can go wrong with it, so a failing test can point you specifically to what's broken. The filter is a substring of the test's name, so cargo test --bin game cp2::binary and cargo test --bin game shifted both work if you want to just run individual or a small set of tests.

When you first clone your repo, every test will fail and you'll see a lot of warnings, and that's to be expected until you start writing your code.

Things you will see before we teach them

A couple things in this repo come from lectures you haven't had yet, and you don't need to understand them fully.

&mut in front of the secret keeper. Every strategy is handed keeper: &mut SecretKeeper. The &mut says the function is allowed to change the keeper, which it does. We will cover this properly in October.

The tests themselves. src/tests.rs uses #[test] and assert_eq!, neither of which you have seen. You are not writing any tests in this project, so you only need to be able to read them, and you can probably get the gist of them without knowing exactly how testing works in Rust. We'll learn how to write tests in November.

There is also a lot of Rust in secret_keeper.rs and plot.rs which will look unfamiliar, but you'll never modify these and aren't responsible for understanding their details.

Submitting

To submit a checkpoint and your final project, see the appropriate Gradescope assignment which will prompt you to log into GitHub and then point to your project repo. That's it! Your repo can stay private, you are just granting Gradescope permission to read it.

There is one Gradescope assignment per checkpoint. Push your work to GitHub before you submit, because Gradescope reads your GitHub repo and not your local copy.

Checkpoint 1: the dungeon

Before you can write Rust you have to be able to get around a computer without a mouse. Bashcrawl is a dungeon you explore from the command line. Rooms are directories, and you navigate with cd, look around with ls and read files with cat. There are no graphics and nothing to install beyond the game itself.

Play the game, answer the questions it raises, and keep a record of what you typed.

Getting the dungeon

Clone our copy, not the one you might find by searching:

git clone https://github.com/rust4ds/bashcrawl.git
cd bashcrawl
cat README.md

Ours has a few fixes in it, and the answers the tests expect are the ones our copy gives.

Recording your session

You have to hand in a transcript of everything you typed. Don't tidy it up, since wrong turns, typos and dead ends are all fine, and demonstrate your process. Save the transcript to a file called dungeon_transcript.txt in your project repo (outside of src).

On Mac, press command-S and save the window's contents to a file.

On Git Bash (Windows), right-click inside the terminal window and choose Select All from the menu, then right-click again and choose Copy. (Dragging to highlight the whole window works too.)

Either way, paste what you get below the line in dungeon_transcript.txt.

Whatever you do, do not close the terminal until you have saved. There is no way to get the session back afterwards. If you are playing in more than one sitting, save at the end of each one and paste them in one after the other in the transcript.

Explore and take notes!

Look at src/dungeon.rs for the questions you're trying to answer as you go to guide your exploration. Take notes on your answers as you go and enter them as values in dungeon.rs. Once you get to the last answer you've gone far enough, but as a bonus (and maybe for bonus credit on a secret test...) try to beat the game completely.

A few hints for if you get stuck (try first on your own!):

  • Take the treasure in the cellar. If you are back at the entrance and there is nothing new to see, you may have missed this.
  • Quick portal to the pit. Once you have taken the treasure, a scrap of paper turns up back at the entrance describing how to summon a portal. A portal is a symbolic link, which is a shortcut from one place to another (like an alias). The spell written on the scrap only works from one particular room deep in the dungeon, so if you would rather not go hunting for that room, run this from entrance instead:
ln -s ./.rift portal
cd portal
  • The robot is optional. In the satellite there are four pieces of a robot and a notebook explaining how to put them back together. There's a right way to check, but you can also just try both remaining options to see which one works. Moreover, none of the graded answers are behind the robot, so this is just for fun.
  • The graveyard is also optional. There is nothing you need for the answers in there, so visit it if you are interested and otherwise skip it.
  • Winning the game depends on decisions you made earlier and a bit of luck, and is not required for passing the checkpoint tests.

Checklist

  • Make your own private copy of the Project 1 repository with Use this template, then clone it to your own machine (done in Lecture 4's Activity)
  • Put your name on the Author line of README.md
  • Clone bashcrawl and start recording your session
  • Play bashcrawl through to answer the questions
  • Fill in the constants in src/dungeon.rs with what you found
  • Check dungeon_transcript.txt has your session in it
  • Check that cargo test --bin game cp1 passes
  • Commit, push, and submit your repo on Gradescope

Hints and tips

  • cd .. goes back up one room
  • ls does not show you everything. ls -a also shows hidden files, the ones starting with .
  • Read every file you find with cat
  • If you get lost, pwd tells you where you are
  • Try tab-completing to speed things up and prevent typos
  • Use the up arrow to bring back previous commands, and down to go the other way
  • If you get stuck mid-command (like in a dquote!) control-c is your friend

Checkpoint 2: four strategies

Somebody picks a number and writes it down. You do not get to see it. All you can do is ask them questions, and only two kinds are allowed:

  • "Is it exactly 7?" They answer yes or no.
  • "Is it bigger than 7?" They answer yes or no.

A strategy is a plan for which questions to ask, and in what order, so that you end up knowing the number. You write it as a function. It plays one whole game, from the first question to the answer:

#![allow(unused)]
fn main() {
pub fn binary(keeper: &mut SecretKeeper, min: u32, max: u32) -> u32
}
  • keeper is the person who knows the number. You ask them things
  • min and max are the range the number is somewhere inside, min included and max not
  • the u32 you return is the number you have worked out

Two things about that signature:

  • Each question comes back as a bool, but the strategy returns a number.
  • The whole game happens inside one function call. You don't call your function once per question, but once per game.

All four strategies will get the right answer, but what separates them is how many questions that takes, and in checkpoint 3 you will be able to measure how much it matters.

What you are writing

You'll complete most of the functions in src/strategies.rs for this checkpoint. Read bad and random at the top first which can serve as templates. The four functions in Search strategies and the constant are yours to edit at this point. More about each:

linear. Try min, then min + 1, upward, asking ask_if_equal each time.

binary. Ask ask_if_greater about the midpoint and throw away the half that cannot contain the number. Narrow until one number is left, and do not spend a question confirming it.

jump. Step forward STRIDE at a time with ask_if_greater until the number is behind you, then go back to the stretch you jumped over and check the numbers in it one at a time with ask_if_equal, working upward from the bottom of that stretch. STRIDE comes set at 1, which works and is the worst possible choice. Pick something better and be ready to explain why.

lucky. Binary search, but before narrowing, spend one question asking outright whether the midpoint is the number. Sometimes that wins the game on the spot. Whether it is a good trade overall is a checkpoint 3 question, so do not decide yet.

What if you run out of numbers? Every strategy assumes the answers it gets are honest, and if they are, linear and jump will always find the right answer before the end of their loops. The compiler can't know that, though, so needs to be told what to do if the loops finish without encountering a yes answer, and what it does has to be compatible with the function's return type. You have a couple valid options here - how you handle it matters less than that you handle it so the code compiles.

The tests ask two things. Eight tests check that a strategy finds the secret number. The other four count how many questions it spent doing it to make sure you're writing the right strategy for each. For example, if binary passes binary_finds_every_number and fails binary_costs_log_of_the_range, it is finding the number, just not guessing the numbers in the correct order for the binary strategy.

Checklist

  • linear works. cargo test --bin game cp2::linear
  • binary works. cargo test --bin game cp2::binary
  • jump works, and STRIDE is something better than 1. cargo test --bin game cp2::jump
  • lucky works. cargo test --bin game cp2::lucky
  • cargo test --bin game cp2 is entirely green, twelve tests
  • Commit, push, and submit your repo on Gradescope

Hints and tips

Here is an example run of binary finding the number 73 on the range [0, 100):

Q1: is it greater than 49? -> YES
Q2: is it greater than 74? -> no
Q3: is it greater than 62? -> YES
Q4: is it greater than 68? -> YES
Q5: is it greater than 71? -> YES
Q6: is it greater than 73? -> no
Q7: is it greater than 72? -> YES
returns 73, after 7 questions

Notice that it never asks whether the number is 73.

Here is jump on the same number, with STRIDE set to 10:

Q1: is it greater than 0?  -> YES     jump forward to 10
Q2: is it greater than 10? -> YES     jump forward to 20
Q3: is it greater than 20? -> YES     jump forward to 30
...
Q9: is it greater than 80? -> no      stop: it is somewhere in 71..80
Q10: is it exactly 71? -> no
Q11: is it exactly 72? -> no
Q12: is it exactly 73? -> YES
returns 73, after 12 questions

More tips:

  • Play against your own code to watch it run: cargo run --bin game -- --strategy binary --min 0 --max 16. Sixteen numbers is small enough to follow every question and check the answers yourself
  • Remember that some of the final tests are not in this file, they're "secret". The final autograder runs your strategies on ranges you have not seen: bigger ones, smaller ones, and ones somewhere else on the number line. Make sure your functions don't just pass the tests, but are correct for any inputs we could give.
  • Commit each strategy as you finish it. It will give you a checkpoint to come back to if you get lost, and it will help tell your development story when it comes time for code review.
  • Read your compiler errors. Remember that even if you know your function is exhaustive and will hit a return inside a loop, the compiler doesn't know that and you may need to return at the end of your functions even if that is never reached. The error you might encounter for this though is a bit obscure - it will look like mismatched types: expected u32, found () or similar (you'll understand more about why it looks like that later!)

Checkpoint 3: measuring, and one more strategy

You have four strategies that work, now you'll find out which one is the best (if you haven't already guessed).

In this checkpoint you will write the thing that runs thousands of games and reports what happened, and then one last strategy that beats binary search by noticing something about the game the other four have so far ignored.

What the other four ignore. The dealer never uses the same secret twice until it has used them all (have you noticed?). So by the 50th game of 100, half the numbers cannot possibly be the answer, and that gives you an advantage. Binary searches all 100 anyway, but you can do better. We won't guide you to the optimal strategy (though you should think about it!) but we'll make a clever little improvement with this information to create a strategy called... clever (clever name, huh?).

To use clever you need to be able to ask two things about a range of numbers: how many numbers in it could still be the secret, and which is the first one that could. These are both calculations based on the historical games you've seen so don't "cost a question". So you'll write those two helpers first and then clever on top of them.

What you are writing

Six things, in three files.

1. measure and is_better_than, in src/measure.rs. Play rounds games of one strategy and report the best, the mean, the worst and the standard deviation across them. match on approach to decide which strategy plays. Read the doc comment above the function before you start: it says where the games come from. Decide what to return when rounds is 0, and be ready to explain why.

Underneath it, is_better_than compares two of those reports and says which strategy you would rather use. The signature is written for you, so you only write the body, and you decide what better means: a lower mean, a better worst case, some combination, etc. Many rules will pass as long as they're reasonable, and you'll just have to defend your decision if asked at code review.

2. possible_count and first_possible, in src/strategies.rs. The two questions described above, as functions. One counts how many numbers in a range could still be the secret; the other finds the first of them.

first_possible returns an Option<u32> rather than a plain u32, because there is a case where it has no answer to give, and a function forced to return something ends up returning a number it does not mean. Work out when that case happens, and what you want the None arm to do about it.

3. clever, in src/strategies.rs.

We're not going to rework the whole algorithm, just the end. Binary keeps going until one number is left between min and max. You can stop as soon as one possible number is left, because at that point there is nothing else it could be. You'll need to change two things from the code for binary and can use first_possible and possible_count to get there.

4. Refactor jump. Look at the second half of the jump you wrote for checkpoint 2. It walks the numbers it skipped, one at a time, asking ask_if_equal about each. That is basically your linear strategy! So just make jump call linear instead.

One thing does have to change under the hood. linear counts upward, so the walk has to run upward too: from the bottom of the stretch you jumped over, not backward from the number you overshot. But nothing in the statistics or tests changes when you do this (do you know why?). Your Checkpoint 2 tests should still pass after this!

5. Fix your midpoint, in src/strategies.rs. binary and lucky both work out a midpoint. If you wrote yours as (lo + hi) / 2 in CP2 it passed then but now fails the new test binary_survives_the_top_of_u32. Figure out what the issue is and find a way to reach the same midpoint without computing (lo + hi) to pass the test.

6. The writeup, in the README of your repo. Copy over the questions at the end of this page into your README and answer them. They ask you to explain your own numbers, so you cannot answer them until your code runs and plot.png exists. This counts towards the first part of your code review grade.

Checklist

  • measure reports all four numbers. cargo test --bin game cp3::measure
  • is_better_than picks a winner. cargo test --bin game cp3::is_better_than
  • possible_count and first_possible work. cargo test --bin game cp3::possible and cp3::first_possible
  • clever works and beats binary over a sweep. cargo test --bin game cp3::clever
  • jump calls linear. cargo test --bin game cp3::jump_calls_linear
  • binary survives a range at the top of u32, and you fixed lucky the same way. cargo test --bin game cp3::binary_survives
  • cargo run --bin plot produces plot.png, and you have committed it
  • cargo test --bin game is entirely green
  • The writeup is answered in your README
  • Commit, push, and submit your repo on Gradescope

Hints and tips

  • Read the cp3 tests before you start writing. They make it clear how long each strategy is supposed to take
  • measure needs the mean before it can work out the standard deviation, and you cannot replay the games for a second look, because the dealer has moved on. Keep running totals instead: the counts, and their squares. Variance is the mean of the squares minus the square of the mean.
  • If clever returns the wrong number, the bug is probably in what you return at the end rather than in when you stop
  • Run cargo run --bin plot early, even with strategies half finished to get a feel for what's happening

The writeup

Your writeup goes in the README of your repo, under the headings that are already there. Leave the rest of that file alone.

You can write 2-3 sentences per question unless it says otherwise.

Reading the plot

Look at plot.png. The X axis is max, the range the strategy had to search. The Y axis is how many questions it needed.

1. Which strategy is best according to plot.png? Refer to the curve and define what you mean by "best". Then look at the ranking printed under the table, which is your own is_better_than putting the same strategies in order: what rule did you give it, and does the order it produced agree with what you just said about the plot? If they disagree, which one do you believe, and why?

2. Look at linear. If max = 110, how many questions will it ask? What about max = 120? Now write it as a function of n.

3. Look at binary. Many values of max give the same number of questions, and then it steps up. Where do the steps happen? Counting max = 1, there are seven of them on this plot. Is there a pattern? Predict where the next one is, then write binary's cost as a function of n. Hint: it has something to do with powers of 2.

4. Jump search sits between the other two. Its curve is neither flat like binary's nor straight like linear's. What shape is it, and why? What stride did you pick, and what happened when you tried a different one?

Reading the table

5. The lucky strategy can find the number in one question where binary needs six, and yet lucky's mean is much higher. Explain why the extra question costs more than it gains, in terms of what each of the two questions tells you when the answer is no.

6. Now look at the best column of your table. Linear, lucky, and random can all find the number in a single question if they get lucky. Binary never can (but it beats the rest four on average anyway). Jump can't get it in one step either. Explain why.

Going further

7. Suppose we gave you a third question, ask_if_even, costing one question like the others. Could you use it to beat binary search? Say why or why not.

8. plot.png does not have a curve for clever. Why do you think it was excluded, and if we did include it, what do you think it would show? Hint: Take a look at the plot.rs code and investigate the role of the dealer and history there.

Process

9. What's something you tried that failed at first on this project, and how did you adapt?

10. Before checkpoint 2 we changed the base repo underneath you and you had to merge it. How did you decide what to keep when the changes conflicted, and how did you check that you were right?

Your AI citation. Who and what you used, and how. Course policy is in the syllabus.