Programming Praxis

Today’s exercise is our five hundredth! It’s hard to believe. I remember writing the fiftieth exercise and thinking I would never get to a hundred. Even after all this practice it is hard to write two exercises every week, but your comments and private emails and referrals from other web sites sustain me. Many thanks to all my readers.

Our tradition for these milestone exercises is to have a party, which means we need a game: so we write one. Today’s exercise is to write an interactive rock-paper-scissors game: rock blunts scissors, paper wraps rock, scissors cut paper.

Your task is to write a program to play rock-paper-scissors with a human player, keeping score as you go. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

On a standard English keyboard, the letters that a touch-typist strikes with the fingers of the left hand are Q, W, E, R, T on the top row, A, S, D, F, G on the home row, and Z, X, C, V, B on the bottom row. For instance, words like FAST and ZEBRAS are left-handed words; PACKAGE and SOUTH are not.

Your task is to write a program that finds words that can be spelled using only letters that are struck with the fingers of the left hand; perhaps you are writing an exercise for a typing book. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

This exercise is intended for beginning programmers who need to strengthen their understanding of linked lists. It comes in three parts:

First, write a function that reverses the elements of a linked list pairwise; for instance, given the list (1 2 3 4 5 6) the pairwise reversal is (2 1 4 3 6 5). If the list has an odd number of elements, keep the last element at the end of the list; for instance, given the list (1 2 3 4 5) the pairwise reversal is (2 1 4 3 5).

Second, write a function the reverses the elements of a linked list k-wise; for instance, given the list (1 2 3 4 5 6) the 3-wise reversal is (3 2 1 6 5 4) and the 4-wise reversal is (4 3 2 1 6 5).

Third, write a function that reverses the elements of a linked list by halves; for instance, given the list (1 2 3 4 5 6) the half-wise reversal is (3 2 1 6 5 4), with each half reversed independently. If the list has an odd number of elements, the middle element may be assigned to either half at the discretion of the programmer.

Your task is to write the three functions given above. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

School children learning to spell English words are taught a series of rules. One of them is:

I before E except after C, or when sounded as AY as in NEIGHBOR and WEIGH.

Your task is to write a program that finds exceptions to that rule; you may want to look at the pronouncing dictionary at http://svn.code.sf.net/p/cmusphinx/code/trunk/cmudict/cmudict.0.6d. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2 3

In many voting systems, when there are more than two candidates and the rules require a majority of the votes to win, if no candidate receives a majority a runoff election is held between the two candidates who finished with the two highest vote totals. Some voting systems, instead of asking each voter to vote for a single candidate, instead ask voters to rank the candidates, which permits a runoff to be held instantly as follows: the votes are tallied, and a winner is declared if one of the candidates receives more than half the votes; otherwise, the candidate with the fewest votes is removed from all ballots and the votes are tallied again, the process repeating until some candidate has more than half the votes. This process is used in some political elections, and is often used in voting for awards such as the Hugo awards for science fiction writing and the Oscars for motion pictures.

Your task is to write a program that determines a winner in an instant-runoff voting system. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercises in the comments below.

Pages: 1 2

We have seen the SYSV and BSD checksum algorithms in previous exercises. In today’s exercise we look at another checksum algorithm developed by John Fletcher at Lawrence Livermore Labs in the late 1970s.

Fletcher’s original algorithm reads a file one byte at a time and computes a 16-bit checksum. Each byte is added to an accumulating sum, mod 255; to detect transposition errors, each accumulating sum is itself added to a second accumulating sum, mod 255. When the input is exhausted, the second sum is multiplied by 256 and added to the first sum, giving the checksum. Variants of Fletcher’s algorithm read a file two bytes at a time and compute a 32-bit checksum (the modulus is 65535), or read a file four bytes at a time and compute a 64-bit checksum (the modulus is 4294967295).

Your task is to write the three checksum programs described above. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

Today’s exercise is my reminder to myself to do a better job of testing. I was porting some prime-number code to Python, one of several preliminary steps to writing a new essay. I am comfortable enough with Python (mostly), and there is nothing particularly tricky about the code, so I wrote the code, tested it quickly, and went on. Later, a different part of the code was failing, and I couldn’t find the problem. Of course, the problem was in the earlier code that I had quickly tested, and therefore hard to spot, since I was looking in the wrong place. The failing code is shown below.

def primes(n):
    ps, sieve = [], [True] * (n + 1)
    for p in range(2, n + 1):
        if sieve[p]:
            ps.append(p)
            for i in range(p * p, n + 1, p):
                sieve[i] = False
    return ps

def isPrime(n):
    if n % 2 == 0:
        return n == 2
    d = 3
    while d * d <= n:
        if n % d == 0:
            return False
        d = d + 2
    return True

def inverse(x, m):
    a, b, u = 0, m, 1
    while x > 0:
        q = b // x
        x, a, b, u = b % x, u, x, a - q * u
    if b == 1: return a % m
    raise ArithmeticError("must be coprime")

def jacobi(a, p):
    a = a % p; t = 1
    while a != 0:
        while a % 2 == 0:
            a = a / 2
            if p % 8 in [3, 5]:
                t = -t
        a, p = p, a
        if a % 4 == 3 and p % 4 == 3:
            t = -t
        a = a % p
    return t if p == 1 else 0

def modSqrt(a, p):
    a = a % p
    if p % 4 == 3:
        x = pow(a, (p+1)/4, p)
        return x, p-x
    if p % 8 == 5:
        x = pow(a, (p+3)/8, p)
        c = pow(x, 2, p)
        if a != c:
            x = (x * pow(2, (p-1)/4, p)) % p
        return x, p-x
    d = 2
    while jacobi(d, p) != -1:
        d += 1
    t, s = p-1, 0
    while t % 2 == 0:
        t, s = t / 2, s + 1
    at, dt, m = pow(a, t, p), pow(d, t, p), 0
    for i in range(0, s):
        if pow(at * pow(dt, m), pow(2, s-i-1), p) == p - 1:
            m = m + pow(2, i)
    x = (pow(dt, m) * pow(a, (t+1)/2, p)) % p
    return x, p-x

Your task is to write a proper test suite, discover the bug in the code shown above, and fix it. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

We have today an interview question from Twitter:

Consider the following picture:

In this picture we have walls of different heights. This picture is represented by an array of integers, where the value at each index is the height of the wall. The picture above is represented with an array as [2,5,1,2,3,4,7,7,6].

Now imagine it rains. How much water is going to be accumulated in puddles between walls?

We count volume in square blocks of 1X1. So in the picture above, everything to the left of index 1 spills out. Water to the right of index 7 also spills out. We are left with a puddle between 1 and 6 and the volume is 10.

Your task is to write a program to compute the volume of water in the puddle; you should strive for an algorithm that completes the task in a single pass. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

Every autumn, a month or two after the start of a new academic year, I receive a handful of emails from students who expect me to help them with their homework. I never respond. Some of the requests are polite — “Dear Kind Sir;” most of them are demanding — “It has to be in C# and cannot exceed 200 lines;” all of them have spelling and grammar mistakes. Today’s exercise is from an email that demanded a response by midnight (the writer didn’t say what time zone), but that was a few weeks ago, and the homework deadline is well past, and at least the question is entertaining.

The Hamming distance between two numbers is the number of bits that must be changed to make the bit representations of the two numbers equal. For instance, the number 79 is represented as 1001111 in binary, the number 83 is represented as 1010011 in binary, and the Hamming distance between them is 3, as the second, third and fourth bits (counting from the right, starting with zero) differ. The assignment was to read a list of numbers and find the two with the minimum Hamming distance between them.

Your task is to write somebody’s homework assignment, as described above — you must finish it before midnight! When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

In the previous exercise we used two queues to make a stack. In today’s exercise, we do the opposite: use two stacks to make a queue. This is exercise 10.1-6 from CLRS. In addition to solving the exercise, you should also create functions to implement a stack.

Show how to implement a queue using two stacks. Analyze the running time of the queue operations.

Your task is to write functions that use two stacks to implement a queue. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2