Collect Sets Of Ranges

August 25, 2015

A frequent idiom in data processing is the control-break idiom, where some processing must be done every time there is a change in some value. A simple example comes from collecting ranges, for instance, converting the sequence 0, 1, 2, 7, 21, 22, 108, 109 to the ranges 0-2, 7, 21-22, 108-109, where a break occurs whenever two numbers aren’t consecutive.

Writing control-break programs can be difficult, for two reasons. First, you don’t know there is a break until you see the next record after the break, so you either need to look ahead in the input or keep track of what you have seen. Second, there is an implied break at the end of the input, which occurs when there is no record at all. Depending on the situation, either or both of those can be tricky.

Your task is to write a program that converts a sequence to a set of ranges, as shown 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

Two Homework Problems

August 21, 2015

I can see from my statistics that the new academic year is beginning. Again, as in a previous exercise, in the spirit of helping programming students who are just starting a new school year, we have two typical homework problems:

1. Given an array of positive integers, find the inflection point where the total of the integers before the inflection point and the total of the integers after the inflection point are least different. For instance, given the array [3, 7, 9, 8, 2, 5, 6], the inflection point is between the 9 and 8, which leaves a total of 19 before the inflection point and 21 after, a difference of 2.

2. Write a program that reads a file from disk and writes the last n lines of the file, where n is an input parameter.

Your task is to write programs to solve these problems. 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

K-Factorials And Factorions

August 18, 2015

We study today a topic from recreational mathematics. Factorions are numbers that are equal to the sum of the factorials of their digits. For instance, 145 is a factorion because 1! + 4! + 5! = 1 + 24 + 120 = 145. There are four factorions to base 10: 1, 2, 145 and 40585.

A double factorial, written n!!, is the product of all integers less than or equal to n that are congruent to n (mod 2). A triple factorial, written n!!!, is the product of all integers less than or equal to n that are congruent to n (mod 3). And so on for higher factorials. Thus, a double factorion is a number that is equal to the sum of the double factorials if its digits, a triple factorion is a number that is equal to the sum of the triple factorials of its digits, and so on. As an example, 81 is a triple factorion because 8!!! + 1!!! = 8*5*2 + 1 = 80 + 1 = 81.

It is also possible to consider factorions to bases other than 10. For instance, there are four factorions to base 6: 1, 2, 25, 26.

Your task is to write functions that allow you to explore the strange world of k-factorials and factorions; use your imagination to think of tasks that interest you. 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

File Bundles

August 14, 2015

It is sometimes convenient to package a group of files into a bundle, for transmission to a different computer or for archiving. Nowadays the most likely method involves tar and gzip, but in the past a “shell archive” was frequently used; the files, which are assumed to include only printable ascii characters, are collected into a single program file that can be executed to self-extract the included files.

Your task is to write a program that creates file bundles. 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

Bridge Hands

August 11, 2015

[ Thanks to all who wrote with good wishes after my post last Friday. I am fully recovered and back at work. ]

Newspapers and textbooks often print bridge hands in the format shown below, then discuss the proper playing of the hand:

                    NORTH
                    S: A Q J 10 8
                    H: 5 4 2
                    D: 9
                    C: 10 7 6 2
WEST                                    EAST
S: 7                                    S: 6
H: Q J 7 6 3                            H: K 10 8
D: J 10 6 4 3                           D: A K Q 5
C: A 8                                  C: K 9 5 4 3
                    SOUTH
                    S: K 9 5 4 3 2
                    H: A 9
                    D: 8 7 2
                    C: Q J

Your task is to write a program to generate random bridge hands and print them in the format shown 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 3

Long-time readers of this blog will remember that five years ago I suffered a bi-lateral pulmonary embolism that nearly killed me; my right lung was 100% blocked, my left lung 60%. This past Tuesday evening I suffered a second pulmonary embolism. It was not nearly as serious as the first, I even went to work as normal on Wednesday, but with growing pain during the day I went to the hospital on Wednesday evening, was diagnosed, received medication to break up the clots — two shots in the belly, twelve hours apart, no fun I assure you — and came home Thursday afternoon.

Broadly speaking, there are two contributing factors to pulmonary embolism. The primary factor is blood chemistry, and that’s genetic; there’s nothing you can do about it, though if you know you are predisposed to blood clots, as I am, there is medication that can attenuate the risk — I’ll be talking to a hematologist in about two weeks. The secondary factor is lifestyle: smoking and obesity are both contra-indicated, as is a sedentary lifestyle. Sedentary in this context doesn’t mean sitting in front of a computer monitor for hours a day — recall that Serena Williams, one of the greatest tennis players of all time, had a pulmonary embolism a few years ago — it just means that you spend a few or several hours a day sitting still.

I assume that most of my readers are computer programmers, as I am, and spend much time sitting still. I urge you to get out of your chair every forty-five minutes or so and walk around for five or ten minutes to get your blood moving. It may save your life.

I’ll have another exercise for you next Tuesday.

Three Homework Problems

August 4, 2015

I get lots of emails, and even some comment postings, from students whe want help with their homework. I never respond, even to offer a hint or a simple word of encouragement. Sorry, but that’s not what I do. But many of my exercises are based on typical homework problems for programming students, and with a new academic year about to start, I figure now is a good time to write some typical homework exercises.

1. Write a function that takes as input three positive integers and finds the sum of the squares of the two largest of the three.

2. Write a function that takes a positive integer as input and determines if it is a base-10 palindrome.

3. Write a function that takes a positive integer as input and determines the number of trailing zeroes in the output of that number’s factorial.

Your task is to write the three requested functions in the manner of a beginning programming student. 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

The standard Sieve of Eratosthenes requires that you specify an upper bound before you start. But often, programs that use prime numbers don’t know the upper bound in advance, or don’t want to pre-compute and store all of the primes up to their bound. In those cases, an incremental Sieve of Eratosthenes can be used:

Algorithm PRIMEGEN: Create a generating function that returns the next prime number each time it is called, starting from zero.
1. [Prime the pump] Yield 2, then yield 3.
2. [Initialization] Set ps ← PRIMEGEN, D ← {}, p ← next(ps), p ← next(ps) again, qp × p, and cp.
3. [Next candidate] Set cc + 2.
4. [Composite candidate] If cD, skip to Step 5. Otherwise, set sD{c}, mc + s. Remove c from D. While mD, set mm + s. Set D{m} ← s. Go to Step 3.
5. [Prime candidate] If c = q, skip to Step 6. Otherwise, yield c and go to Step 3.
6. [Next sieving prime] Set sp + p, mc + s. While mD, set mm + s. Set D{m} ← s. Set p ← next(ps), qp × p. Go to Step 3.

The PRIMEGEN algorithm creates the sequence of prime numbers, returning the next prime in the sequence each time it is called; the exact mechanism to do that depends on the implementation language. The first step primes the pump (sorry!) by issuing the first two primes: 2 is a special case because it is even, and 3 is a special case because the pump only considers odd numbers as prime candidates.

The second step initializes two important data structures: ps is the list of sieving primes, which is determined by calling PRIMEGEN recursively, and D is a dictionary of composite/stride pairs, one for each sieving prime less than the square root of the current prime; the dictionary will most likely be implemented as a hash table, but other data structures such as a balanced binary tree could also be used. The other initializations are the current sieving prime p, its square q, and the initial prime candidate c.

The third step begins the main loop of the function by calculating the next prime candidate; eventually, all odd numbers starting from 5 will be prime candidates. Then there are three possibilities, each handled by a separate step.

The fourth step handles the case that the candidate c is composite, resetting the dictionary entry for the appropriate sieving prime. The fifth step handles the case that the candidate c is both composite and less than the square q of the current sieving prime, which indicates that the candidate is prime. The sixth step occurs when the candidate is composite but not in the dictionary, having reached the square of the current sieving prime, when a new sieving prime is added to the dictionary and the current sieving prime is updated in variables p and q. After the appropriate option has been processed, the algorithm returns to the top of the main loop to obtain the next prime.

In the fourth and sixth steps, the while loop calculates the new dictionary entry for the current sieving prime: the stride s = 2p is the distance between odd multiples of the sieving prime, and m is the smallest multiple of the sieving prime p greater than the current candidate c that is not already in the dictionary. The dictionary is keyed by m, which is a multiple of a sieving prime, with the corresponding stride s as its value.

There are several points to note about this algorithm. First, it is recursive, and there will eventually be a stack of sieving prime sequences, which sounds bizarre but actually makes sense. Second, by postponing the addition of new sieving primes to the dictionary until reaching their squares, only primes less than the square root of the current candidate need to be stored. And third, eliminating duplicate dictionary entries with the while loop of steps 4 and 6 keeps the size of the dictionary at exactly the number of sieving primes already processed. The whole algorithm is very efficient, making it useful whenever processing primes incrementally.

Time complexity of the algorithm is O(n log log n), the same as any other implementation of the Sieve of Eratosthenes, and space complexity is O(sqrt n) to store the dictionary of sieving primes.

Your task is to implement the incremental Sieve of Eratosthenes. 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 a reminder about the importance of writing good test code. We have two tasks. The first is to extract the next-to-last item from a linked list; for instance, given the list (1 2 3 4 5) the next-to-last item is 4. The second task is to extract the nth-from-last item from a linked last; for instance, given the same list, the second-from-last item is 4. In addition to writing the two functions, you should write test code that exercises the functions thoroughly.

Your task is to write the two functions and test code. 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

One-Swappable Array

July 24, 2015

Today’s exercise helps somebody with their homework:

Given an array of unique integers, determine if it is possible to sort the array by swapping two elements of the array. For instance, the array [1,2,6,4,5,3,7] can be sorted by swapping 3 and 6, but there is no way to sort the array [5,4,3,2,1] by swapping two of its elements. You may use O(n) time, where the array has n integers, and constant additional space.

Your task is to write a program that determines if an array can be sorted with a single swap. 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 689 other followers