Programming Praxis

Merry Christmas to all my readers, and thank you for staying with me for another year.

Your task is to turn off your computer and spend a week with family and friends.

I’ll see you in 2017!

You all know the old song:

On the first day of Christmas my true love gave to me a partridge in a pear tree.

On the second day of Christmas my true love gave to me two turtle doves and a partridge in a pear tree.

On the third day of Christmas my true love gave to me three French hens, two turtle doves and a partridge in a pear tree.

On the fourth day of Christmas my true love gave to me four calling birds, three French hens, two turtle doves and a partridge in a pear tree.

On the fifth day of Christmas my true love gave to me five golden rings, four calling birds, three French hens, two turtle doves and a partridge in a pear tree.

On the sixth day of Christmas my true love gave to me six geese a-laying, five golden rings, four calling birds, three French hens, two turtle doves and a partridge in a pear tree.

On the seventh day of Christmas my true love gave to me seven swans a-swimming, six geese a-laying, five golden rings, four calling birds, three French hens, two turtle doves and a partridge in a pear tree.

On the eighth day of Christmas my true love gave to me eight maids a-milking, seven swans a-swimming, six geese a-laying, five golden rings, four calling birds, three French hens, two turtle doves and a partridge in a pear tree.

On the ninth day of Christmas my true love gave to me nine ladies dancing, eight maids a-milking, seven swans a-swimming, six geese a-laying, five golden rings, four calling birds, three French hens, two turtle doves and a partridge in a pear tree.

On the tenth day of Christmas my true love gave to me ten lords a-leaping, nine ladies dancing, eight maids a-milking, seven swans a-swimming, six geese a-laying, five golden rings, four calling birds, three French hens, two turtle doves and a partridge in a pear tree.

On the eleventh day of Christmas my true love gave to me eleven pipers piping, ten lords a-leaping, nine ladies dancing, eight maids a-milking, seven swans a-swimming, six geese a-laying, five golden rings, four calling birds, three French hens, two turtle doves and a partridge in a pear tree.

On the twelfth day of Christmas my true love gave to me twelve drummers drumming, eleven pipers piping, ten lords a-leaping, nine ladies dancing, eight maids a-milking, seven swans a-swimming, six geese a-laying, five golden rings, four calling birds, three French hens, two turtle doves and a partridge in a pear tree.

Your task is to write a program that prints the words of the song, as economically as possible. 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 studied highly composite numbers in a series of several previous exercises, and had a lot of fun. In today’s exercise we look at a related concept: highly abundant numbers (A002093).

Highly abundant numbers are those numbers n such that sigma(m) < sigma(n) for all m < n, where m and n are positive integers and sigma(n) is the sum of the divisors of n. For instance, 12 is a highly abundant number since the sum of its divisors is 1 + 2 + 3 + 4 + 6 + 12 = 28, and no number less than 12 has a greater sum of divisors.

Your task is to compute the sequence of highly abundant numbers. 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

When I’m not writing exercises for Programming Praxis, my day job has me writing SQL and PL/SQL code for a large Oracle database. One task I frequently perform is inserting records into a table, using the following syntax:

insert into tablename (
    field_1,
    field_2,
    field_3,
    ...)
values (
    value_1,
    value_2,
    value_3,
    ...)

Here, tablename is replaced by the name of the database table into which records are being inserted, each field is the name of a field in the table, and each value is the value to be inserted. The correspondence between field name and value is positional.

I can’t tell you how many times over the years I wrote that wrong. When I inadvertently skip a field, an error message politely tells me of my mistake. But when I transpose two fields, both of the same type, there is no error message, and I happily go on my way with bad data in the database.

I finally decided to do something about the situation; I wrote a program that converts the syntax shown below, which makes it easy to see the correspondence between fields and values, to the Oracle syntax shown above:

insert into tablename (
    field_1 => value_1,
    field_2 => value_2,
    field_3 => value_3,
    ...)

That’s much better: Easy to get right, much harder to get wrong. A significant payback on a few minutes of effort. Why didn’t I do this years ago!?

Your task is to find something annoying in your programming environment, and fix it; you can borrow my annoyance in the unlikely event you have none of your own. 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 exercise for students who work with linked lists:

Given a linked list and an integer k, swap the two list items that are at distance k from the beginning of the list and distance k from the end of the list. Be sure to consider the case where the k cross, so that the item k from the beginning of the list is after the item k from the end of the list. For instance, given the list (1 2 3 4 5 6 7) and k = 2, you should return the list (1 6 3 4 5 2 7), and likewise if k = 6. The solution must run in O(n) time, where n is the length of the list.

Your task is to write the list-swapping code 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

Given an array of positive integers in ascending order, of infinite size, find the index of an integer k in the array, or determine that it does not exist. Your solution must work in time logarithmic in the index of the requested integer.

Your task is to write a program that finds the requested integer. 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

Regular readers know that I sometimes find inspiration for these exercises at Career Cup:

Given two sorted arrays, efficiently find the median of the combined array.

Your task is to write the indicated program. 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 early 1800, Thomas J. Beale mined a large quantity of gold and silver, secretly, some place in the American West, and brought the gold, silver, and some jewels purchased with the treasur to Virginia, where he buried it. He wrote three coded documents that described the location of the buried treasure, the nature of the treasure, and the names of the owners. He never came back to retrieve the treasure. Only the second of those documents has been decoded, and many people, even today, are scouring Bedford County, Virginia, looking for buried treasure. Or so the story goes.

Beale used a variant of a book cipher. He chose a long text as a key, numbered each of the words in the text sequentially, starting from 1, and formed a message by choosing from the key text a word for each character of plain text having the same initial letter as the plain text; the cipher text consists of a list of the sequence numbers of the chosen words. For instance, if the key text is “now is the time” and the plain text is “tin”, then either (3 2 1) or (4 2 1) are valid encipherments. If the key text is long, there will be many duplicates, as we saw with the letter “t”, and the resulting cipher will be reasonably secure. Beale used the 1322 words of the Declaration of Independence as the key text for the second document; the key texts associated with the first and third documents are unknown.

Your task is to write programs that encipher and decipher messages using the Beale cipher; use it to decode the second document. 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