Module assignment: Library desk toolkit

The brief

A small town library has a front desk with one tired computer and a list of jobs that staff currently do by hand. The head librarian has asked you for three small tools. She does not want a polished app. She wants designs she can read and programs she can trust, so that her volunteers can check the rules against what the programs do.

For each of the three tools you will go through the whole method from this module:

1. Restate the problem and list the inputs and outputs.
2. Draw a flowchart (in a text block, using the symbols from Lesson 2).
3. Write pseudocode (using the conventions from Lesson 3).
4. Translate it into a Python program that reads from the Input box and prints to the screen.
5. Trace one example by hand with a trace table (Lesson 4), and check that the program prints the same values.
6. Choose test inputs on purpose and record the expected and actual output in a test table.

The three tools are the late-fee calculator, the second-highest-rating finder and the number guessing referee. They use decisions, loops, early exits and binary search, which is everything in this module.

Tool A: the late-fee calculator

Specification

A borrower returns a book d days late. The fee is worked out day by day, using these rules:

• Days 1 to 3 are a grace period and cost nothing.
• Days 4 to 14 cost 2 per day.
• Day 15 and every later day cost 5 per day.
• The fee never goes above 100.

So a book that is 4 days late costs 2 (only day 4 is charged). A book that is 14 days late costs 11 charged days at 2 each, which is 22. A book that is 15 days late costs 22 plus 5, which is 27.

Input: one line holding a whole number d with d >= 0.

Output: one line holding the fee, as a whole number.

Examples

Type the input into the Input box of your program. For example, type 15 and the program should print 27.

Tool B: the second-highest rating

Specification

Readers rate a book from 1 to 5 stars, but the librarian wants a general tool for any list of whole numbers. The tool reports the second largest distinct value. "Distinct" means equal values count once, so in 9 9 4 the largest is 9 and the second largest is 4. If the list has fewer than two different values, there is no answer, and the program prints none.

Input: the first line holds n, the number of values (n >= 1). The second line holds the n whole numbers separated by spaces. Values can be negative.

Output: one line with the second largest distinct value, or the word none.

Examples

This is the problem that broke in Lesson 4, so use what you learned there.

Tool C: the number guessing referee

Specification

At the library's children's day, a volunteer thinks of a secret number between 1 and N, and a computer plays the guesser. The computer must always guess the middle of the range that is still possible (the lower middle when the range has an even count), and the referee program must print each guess with the verdict, and finally how many guesses were needed.

Input: the first line holds N. The second line holds the secret number s, with 1 <= s <= N.

Output: one line per guess, in the form guess G: too low, guess G: too high or guess G: correct, followed by a final line guesses: K.

"Too low" means the guess is smaller than the secret. Use (low + high) // 2 for the middle.

Examples

Input:

15
11

Output:

guess 8: too low
guess 12: too high
guess 10: too low
guess 11: correct
guesses: 4

Input 100 then 1 gives six guesses (50, 25, 12, 6, 3, 1) and ends with guesses: 6. Input 1 then 1 gives guess 1: correct and guesses: 1.

Requirements checklist

Copy this list and tick each item when you are sure it is true.

• For each tool, I wrote the inputs and outputs before anything else.
• For each tool, I drew a flowchart in a text block with correct symbols, and every diamond has a Yes and a No exit.
• For each tool, I wrote pseudocode with <- for assignment, == for comparison, indented blocks and a contract comment.
• Each loop has a stated initialization, condition and update, and I can say why it ends.
• Tool A gives 0 for 0 and 3 days, 2 for 4 days, 22 for 14 days, 27 for 15 days and 100 for 30 days.
• Tool A never prints a fee above 100, including for very large inputs such as 200.
• Tool B prints none for 5 5 5 and for a single value, and treats a repeated maximum correctly.
• Tool B works for all-negative numbers and does not start its variables at 0.
• Tool C halves the range every guess and stops the moment the guess is correct.
• Tool C works when N = 1, and when the secret is 1 or N.
• I traced one example per tool by hand, and the program printed the same values.
• I wrote a test table with at least 5 inputs per tool, including a boundary or edge case, and I ran every one.
• Every program runs in the run box without errors and reads its input with input().

What to hand in

Write your answer as one document with three sections, one per tool. Each section has these parts in this order: the restated problem, the flowchart, the pseudocode, the Python program, one trace table and a test table. A test table has three columns: input, expected output (worked out by hand before you run anything), and actual output.

Working out the expected output first is the whole point. If you copy the expected output from the program's answer, you are checking the program against itself, and the check proves nothing.

Grading rubric

Use this to mark your own work, or to ask a friend to mark it.

Step-by-step hints

Try each tool on your own first. Open a hint only when you are stuck, and open one at a time.

Reference solution

Do not open this until you have your own answer for all three tools. Compare it with yours.

 ( Start ) -> /read d/
                  |
          < d <= 3 ? >--Yes--> [ fee = 0 ] ------------------+
                  | No                                        |
          < d <= 14 ? >--Yes--> [ fee = (d - 3) * 2 ] --------+
                  | No                                        |
          [ fee = 11 * 2 + (d - 14) * 5 ] --------------------+
                                                              |
                                                  < fee > 100 ? >--Yes--> [ fee = 100 ]
                                                              | No             |
                                                              +<---------------+
                                                              |
                                                        /print fee/ -> ( End )

// Input:  d, the number of days late (whole number, d >= 0)
// Output: the fee
FUNCTION lateFee(d)
    IF d <= 3 THEN
        fee <- 0
    ELSE IF d <= 14 THEN
        fee <- (d - 3) * 2
    ELSE
        fee <- 11 * 2 + (d - 14) * 5
    END IF
    IF fee > 100 THEN
        fee <- 100
    END IF
    RETURN fee
END FUNCTION

27

// Input:  array A with at least one number
// Output: the second largest distinct value, or "none"
FUNCTION secondDistinct(A)
    first <- none
    second <- none
    FOR i FROM 0 TO LENGTH(A) - 1
        x <- A[i]
        IF first == none OR x > first THEN
            second <- first
            first <- x
        ELSE IF x != first AND (second == none OR x > second) THEN
            second <- x
        END IF
    END FOR
    RETURN second
END FUNCTION

4

// Input:  N, the top of the range; s, the secret (1 <= s <= N)
// Output: each guess with its verdict, then the number of guesses
PROCEDURE referee(N, s)
    low <- 1
    high <- N
    count <- 0
    WHILE low <= high
        guess <- (low + high) DIV 2
        count <- count + 1
        IF guess == s THEN
            PRINT "guess", guess, "correct"
            PRINT "guesses", count
            RETURN
        ELSE IF guess < s THEN
            PRINT "guess", guess, "too low"
            low <- guess + 1
        ELSE
            PRINT "guess", guess, "too high"
            high <- guess - 1
        END IF
    END WHILE
END PROCEDURE

guess 8: too low
guess 12: too high
guess 10: too low
guess 11: correct
guesses: 4

Stretch tasks

If you finished early, try one of these. Each uses only what is in this module.

1. Add a fourth tool, a "renewal limit" counter. A reader may renew a book at most 3 times. Read renewal requests, one per line, until a line holds 0. Print Renewed for each of the first 3 requests and Limit reached for later ones. Draw the sentinel-loop flowchart first.
2. Change Tool C so that the guesser has only 7 guesses, and print Out of guesses if it fails. Is 7 enough for N = 100? Prove it with the halving count, then check with a program that tries every secret from 1 to 100.
3. Change Tool B so that it reports the second largest value without the word "distinct", so 9 9 4 gives 9. Which single condition do you remove, and which test row in your table changes?

What this module covered

• An algorithm is a finite, precise list of steps from input to output, and it needs input, output, definiteness, finiteness and effectiveness.
• Every algorithm is built from sequence, selection and iteration, and the same steps solve every valid input.
• A flowchart uses the oval, rectangle, parallelogram, diamond and arrow; a decision has two labelled exits and a loop is an arrow back.
• Pseudocode uses <-, ==, FOR, WHILE, IF, FUNCTION and RETURN, indented, with loop bounds stated and arrays counted from 0.
• A pseudocode FOR includes its last value, so translate it to range(first, last + 1) and check the first and last counter values.
• A trace table has a column per variable and a row per step or pass; do what the code says, and check the loop condition one last time.
• Choose test inputs on purpose: smallest case, ties, negatives, boundaries, ordered and reversed lists.
• Binary search keeps a range that always contains the answer and halves it every guess, so it needs about ten guesses for 1000 values.