Module assignment: Python number lab

The brief

You have spent four lessons learning the operators one family at a time. Arithmetic gave you /, // and %. Assignment gave you += and the walrus operator. Comparisons and logic gave you and, or and short-circuiting. Bit operators gave you masks and shifts. This assignment asks you to use all four families in one program.

You will build a number lab. The lab reads a list of commands from the terminal. Each command names a small calculation and gives one number to run it on. The program prints one answer per command. A real tool like this is what a test engineer or a teacher might write to check a batch of values quickly, and each command in it is a single operator idea from this module.

Work through the brief in order. Start with the checklist, because it tells you exactly what to build. Use the rubric to judge your own work, and open the hints only when you are stuck. Open the reference solution only after you have a version of your own, and compare the two carefully rather than copying.

The lab reads its input with input(), so its programs are not input-free and are not marked to run on this page. Save a program as a file such as lab.py, then run it with python3 lab.py, typing the input lines, or with python3 lab.py < input.txt to read them from a file.

The input and the output

The first line of input is a whole number n, the number of commands. Each of the next n lines holds two things separated by a space: a command name and one number. The command name is one of six words, written in lower case:

Print exactly one line for each command, in the same order as the input. Do not print anything else.

The commands accept different ranges of numbers, and the checklist below spells them out. For now, notice that digits, reverse and ones only receive numbers that are zero or more. pow2 and odd may receive negative numbers. gray receives numbers from 0 up to any size, because Python integers have no size limit.

Example one

Input:

6
digits 4825
reverse 1200
ones 1023
pow2 1024
gray 3
odd -7

Output:

19
21
10
YES
2
YES

Check each line by hand before you trust the program. The digits of 4825 are 4, 8, 2 and 5, and they add to 19. Reversing 1200 gives 0021, which is 21, because the leading zeros disappear. The number 1023 is ten 1 bits in a row. The number 1024 is a power of two. The Gray code of 3 is 011 ^ 001, which is 010, or 2. The number -7 is odd, and the test must say YES for it.

Example two

Input:

4
reverse 9000
pow2 0
gray 0
odd 0

Output:

9
NO
0
NO

Two details matter here. Reversing 9000 gives 9, because the three trailing zeros in the input become leading zeros in the answer, and leading zeros have no value. And zero is not a power of two, even though 0 & (0 - 1) is zero, so the test must reject it.

The requirements checklist

Tick each item when your program does it. The checklist is also the way the grader checks your work, so every item must hold for every valid input.

• The program reads n and then exactly n commands from the input.
• digits x prints the sum of the decimal digits of x, for every x from 0 up to any size.
• digits 0 prints 0, not an empty line.
• reverse x prints the digits reversed as a number, so reverse 1200 prints 21.
• reverse 1534236469 prints 9646324351, a value bigger than the largest 32-bit integer.
• ones x counts the 1 bits of x with the loop x & (x - 1), which runs once per set bit.
• pow2 x prints YES for 1, 2, 4, 8 and larger powers of two, and NO for 0, for negative numbers and for numbers that are not powers of two.
• gray x prints x ^ (x >> 1) as a decimal number.
• odd x prints YES for negative odd numbers such as -7, and NO for 0.
• Every command prints exactly one line, in input order, with nothing else printed.
• The program uses the bit and remainder tests the lessons taught, and it uses brackets in every expression that mixes bit operators with others.
• The program does not use any fixed-size type, so large inputs cannot wrap around.

The grading rubric

Your grade depends on how many commands you get right and how carefully you handle the edge cases. Use this rubric to judge a draft before you submit it.

A 60% solution is a working start. An 80% solution proves that you understand the operators. A 100% solution shows that you test the edges, and edge testing is the skill that interviewers and senior engineers look for most.

Step one: read the input

Start with the input, and make sure the commands arrive correctly. Before you write any arithmetic, copy a small program that reads n, then reads each command name and value, and prints them back. That proves your input handling works. The program below is a skeleton for your lab.

n = int(input())
for i in range(n):
    command, text = input().split()
    value = int(text)
    print(f"line {i + 1}: {command} with {value}")

Save it as skeleton.py, then give it this input, one command per line:

2
digits 4825
odd -7

The output is:

line 1: digits with 4825
line 2: odd with -7

The for loop repeats the reading n times. The loops module explains loops in full. For this assignment, copy the loop shape and change only what is inside it. The line command, text = input().split() reads one line and splits it at the space into two pieces. The function int(text) turns the second piece into a whole number. The range(n) call gives the numbers 0 up to n - 1, which is why the program prints line 1 first.

Step two: the digit commands

The digits and reverse commands both work on the decimal digits of a number. Each digit is found with % 10, and each one is removed with // 10. Write the two functions by hand and test them on fixed numbers before you connect them to the input. The program below does exactly that for four values.

The output is:

19
21
9646324351
0

Read the reverse function line by line. Each pass takes the last digit with x % 10 and adds it to the result after shifting the result one place left in decimal, which is result * 10. For 1200 the digits come off in the order 0, 0, 2, 1. The result goes 0, 0, 2, then 21. The leading zeros never add anything, which is why reverse 1200 is 21. The value 9646324351 is bigger than the largest 32-bit integer, and Python stores it without any special type.

The digit_sum function returns 0 for input 0, because the loop never starts. That answer is correct, and it is the first edge case to test.

Step three: the bit commands

The ones and pow2 commands use the bit tricks from the bitwise lesson. The first removes the lowest 1 bit each time, using x & (x - 1). The second checks that exactly one bit is set, and it also requires the number to be positive. The program below tests both on fixed values, including the tricky cases.

The output is:

10
0
YES
NO
NO

Look at the last two results. For 0, the expression x & (x - 1) is 0 & -1, which is 0, so without the check x > 0 the function would wrongly say YES. For -8, the bit trick alone gives a nonzero result, so the answer is NO even without the check. The check x > 0 is still short, and it is not optional. It states the rule directly, and it is an edge case the grader will test.

The loop in count_ones runs once for each 1 bit, not once for each column of the number. For 1023 it runs ten times. For 0 it does not run at all.

Step four: the Gray code and the odd test

The last two commands are the shortest. A Gray code is a way of writing numbers so that consecutive values differ in exactly one bit. The Gray code of x is x ^ (x >> 1), which shifts right by one and then XORs. The odd test uses the remainder rule from the arithmetic lesson, x % 2 != 0, which works for negative numbers because -7 % 2 is 1 in Python. Test both on fixed values first.

The output is:

2
6
YES
NO

Check the Gray code by hand. For 3, which is 011, the shifted value is 001, and the XOR is 010, which is 2. For 4, which is 100, the shifted value is 010, and the XOR is 110, which is 6. The codes 2 and 6 differ in exactly one bit, which is the property that makes Gray codes useful. You do not need to prove it in the assignment. Write the brackets anyway, as x ^ (x >> 1), so a reader sees the shift happen first without having to remember the precedence table.

The odd test returns NO for zero, because 0 % 2 is 0, and the != check fails. It returns YES for -7, because -7 % 2 is 1, which is not zero. The test x % 2 == 1 would give the wrong answer for negative odd numbers in some other languages, so != 0 is the form to use.

Step five: the full lab

Now combine the pieces. The full program reads the commands, decides which function each command needs, and prints one line for each. Try the lab yourself first. The hints below give a plan if you get stuck.

Hint 1: the shape of the program

Read n first, then loop n times. Inside the loop, read the command word and the number. Every command prints exactly one line, so every branch of your decision must print.

Hint 2: deciding which command ran

Use if and elif with command == "digits" and so on. In Python, == compares the letters of two strings, so it is the right test for command names. Put the six commands in six branches, and add an else only if you are sure the input is valid.

Hint 3: where the answers come from

Copy the helper functions from the step programs above into your file, above the main part. You do not need to write new arithmetic. The digits branch prints digit_sum, the reverse branch prints reverse, and the other branches print count_ones, is_power_of_two, gray and is_odd. The two YES and NO answers use the form "YES" if condition else "NO".

Hint 4: testing before you submit

Run example one, then example two, then the edge cases listed in the next section. If one line is wrong, find its command, run that helper alone on the same value, and compare with the table in the brief. Do not change more than one thing at a time.

Reference solution

Try the lab yourself before you read this. Save the reference as lab.py, then check it with example one. The output must match example one exactly.

def digit_sum(x):
    total = 0
    while x > 0:
        total += x % 10
        x //= 10
    return total
 
def reverse(x):
    result = 0
    while x > 0:
        result = result * 10 + x % 10
        x //= 10
    return result
 
def count_ones(x):
    count = 0
    while x != 0:
        x = x & (x - 1)
        count += 1
    return count
 
def is_power_of_two(x):
    return x > 0 and (x & (x - 1)) == 0
 
def gray(x):
    return x ^ (x >> 1)
 
def is_odd(x):
    return x % 2 != 0
 
n = int(input())
for _ in range(n):
    command, text = input().split()
    value = int(text)
    if command == "digits":
        print(digit_sum(value))
    elif command == "reverse":
        print(reverse(value))
    elif command == "ones":
        print(count_ones(value))
    elif command == "pow2":
        print("YES" if is_power_of_two(value) else "NO")
    elif command == "gray":
        print(gray(value))
    elif command == "odd":
        print("YES" if is_odd(value) else "NO")

The reference solution runs each helper on the value from its command. The main part does nothing except read the input and choose a helper. That split is the design lesson. Each function is short, and each one can be tested alone, as you did in steps two to four. The main part has one job, which is to route commands.

Testing your lab

A program that passes the examples is not finished. Run these edge cases yourself, one at a time, and check each answer against the reasoning in the rubric. Each bullet is one complete input. Save it as edge.txt, or type it into the terminal, and run python3 lab.py < edge.txt.

• 1 then digits 0. The answer must be 0.
• 1 then reverse 0. The answer must be 0.
• 1 then reverse 100. The answer must be 1, because the zeros disappear.
• 1 then reverse 1534236469. The answer must be 9646324351, which is bigger than a 32-bit integer.
• 1 then ones 0. The answer must be 0.
• 1 then pow2 1. The answer must be YES, because 1 is 2 to the power 0.
• 1 then pow2 -8. The answer must be NO.
• 1 then pow2 4611686018427387904. The answer must be YES, because that is 2 to the power 62.
• 1 then gray 1. The answer must be 1, because the Gray code of 1 is 01 ^ 00, which is 1.
• 1 then odd -1. The answer must be YES.

If any line disagrees, the bug is in the matching helper. Read the helper, then ask whether the edge case is inside its contract. A common cause is a missing bracket, which changes the order of operations. Another is a value that is read as text and not converted with int.

Common mistakes to avoid

Students who lose marks on this assignment usually make one of these mistakes.

• Writing x ^ x >> 1 for the Gray code without brackets. It works, because >> ranks above ^ in Python, but a reader has to stop and check that. Write x ^ (x >> 1).
• Forgetting that pow2 needs x > 0. The bit trick alone accepts zero, because 0 & -1 is 0.
• Comparing a number with text. The value from input() is text. Convert it with int(text) before you use it in arithmetic. Otherwise Python raises a TypeError.
• Printing extra text. A debugging line left in the program adds an extra line and fails the grader. Remove every print that is not an answer.
• Testing for a remainder of 1 to find odd numbers. In some languages -7 % 2 is -1, so a test such as == 1 misses negative odd numbers. In Python it is 1, but != 0 works in both.

Submission

Save your final program as lab.py, and check it with example one and example two. Run it with python3 lab.py < example1.txt for each example file, so the program reads its input from the file. The program must print the answers in the order of the commands. Before you finish, run the requirements checklist one item at a time, and tick each box only after you have seen the item work on a real input.

What this module covered

• Arithmetic operators, floor division, the remainder and its sign, the lack of overflow in Python, and operator precedence
• Assignment, augmented assignment, the walrus operator and the lack of increment operators in Python
• Comparison and logical operators, short-circuit evaluation and the order of conditions
• Bitwise operators, shifts, masks and the classic tricks for counting bits, testing powers of two and finding a single value
• Putting the operators together in one program, with edge cases tested on purpose