Requiescat In Pace

December 20, 2013

My mother died on Tuesday, December 17th, aged eighty-eight years, after a brief illness.

Requiem aeternam dona ei, Domine, et lux perpetua luceat ei.

I’ll be taking a short break from writing exercises. The Christmas exercise for next Tuesday is already written and loaded and will appear on schedule. Then I’ll be back to the normal Tuesday/Friday schedule after the first of the year.

Remove Duplicates From A List

December 17, 2013

We have today another exercise from our infinite supply of interview questions:

Return a list containing only one copy of any duplicates in an input list, with items in the output in the same order as their first appearance in the input.

Your task is to answer the interview question given above; you must provide at least two different solutions. 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

Modular Factorial

December 13, 2013

This question appears from time to time as an interview question or on the coding-challenge web sites.

Write a function that calculates n! (mod p) when p is prime. Then extend the function to calculate n! (mod m) when m is not prime. Can you calculate the factorials using fewer than n−1 modular multiplications?

For instance, 1000000! (mod 1001001779) is 744950559.

Your task is to write the indicated functions. 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

Rock Paper Scissors

December 10, 2013

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

Left-Handed Words

December 6, 2013

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

Reversing Parts Of A List

December 3, 2013

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

I Before E

November 29, 2013

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

And The Winner Is …

November 26, 2013

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

Fletcher’s Checksum

November 22, 2013

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

Modular Testing

November 19, 2013

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

Follow

Get every new post delivered to your Inbox.

Join 576 other followers