Programming Praxis

In their book Software Tools, Brian Kernighan and P. J. Plauger describe a simple command for encrypting files. It works by xor-ing each byte of a file with a byte of the key, extending the key cyclically until it is the same length as the text. The xor operation is symmetric, so only one program is needed to perform both encryption and decryption. This isn’t a particularly secure encryption algorithm; we showed how to break it in one of our earliest exercises.

Your task is to implement a function that takes a filename and a key and returns the encrypted/decrypted output. 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 did versions of the sum command for computing file checksums in two previous exercises, one for System V and one for Berkeley systems. Although the BSD version of the command fixes many of the problems of the SysV version, having two different versions of the sum command is inconvenient, and the solution has been to create a third (incompatible) checksum program with a new name: cksum. The algorithm used in cksum is given by the Open Group:

The cksum utility shall calculate and write to standard output a cyclic redundancy check (CRC) for each input file, and also write to standard output the number of octets in each file. The CRC used is based on the polynomial used for CRC error checking in the ISO/IEC 8802-3:1996 standard (Ethernet).

The encoding for the CRC checksum is defined by the generating polynomial:

G(x)=x³²+x²⁶+x²³+x²²+x¹⁶+x¹²+x¹¹+x¹⁰+x⁸+x⁷+x⁵+x⁴+x²+x+1

Mathematically, the CRC value corresponding to a given file shall be defined by the following procedure:

1. The n bits to be evaluated are considered to be the coefficients of a mod 2 polynomial M(x) of degree n−1. These n bits are the bits from the file, with the most significant bit being the most significant bit of the first octet of the file and the last bit being the least significant bit of the last octet, padded with zero bits (if necessary) to achieve an integral number of octets, followed by one or more octets representing the length of the file as a binary value, least significant octet first. The smallest number of octets capable of representing this integer shall be used.
2. M(x) is multiplied by x³² (that is, shifted left 32 bits) and divided by G(x) using mod 2 division, producing a remainder R(x) of degree ≤ 31.
3. The coefficients of R(x) are considered to be a 32-bit sequence.
4. The bit sequence is complemented and the result is the CRC.

The reference implementation from the Open Group is shown on the next page.

Your task is to implement the cksum algorithm. 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

We looked at the Unix SysV sum command in a previous exercise. At the time, my intention was to do the BSD version of the sum command immediately, in the next exercise, but for some reason I failed to do so. That oversight is corrected in today’s exercise.

The original SysV sum command simply calculated the sum of all the bytes in the file, modulo 2¹⁶. Thus, it failed to distinguish two files in which the order of the bytes was changed, null bytes were added, or the bytes were manipulated so that additions to one byte were subtracted from another byte. Although the BSD algorithm isn’t perfect, it identifies all those differences by summing 2-byte words, rotating the accumulating sum one bit to the right after each step.

Today’s exercise is to implement the standard Unix sum command that calculates either of these checksums:

NAME

sum -- checksum and count the blocks in a file

SYNOPSIS

sum [-r | -s] [file ...]

DESCRIPTION

Print checksum and block counts for each file. The BSD algorithm is used unless the System V algorithm is specified.

-r -- Use BSD sum algorithm with 1024-bit blocks.

-s -- Use System V sum algorithm with 512-bit blocks.

When file is - or is not given, read standard input.

Your task is to write the Unix V7 sum command as specified 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

Ray Panko gives this exercise as a test for the accuracy of spreadsheet development; in his tests he found 62 errors in 150 spreadsheet solutions (some spreadsheets contained more than one error), which he finds is typical of spreadsheet users—hopefully professional programmers make fewer errors:

You are to build a spreadsheet model to help you create a bid to build a wall. You will offer two options — lava rock or brick. Both walls will be built by crews of two. Crews will work three 8-hour days to build either type of wall. The wall will be 20 feet long, 6 feet tall, and 2 feet thick. Wages will be $10 per hour. You will have to add 20% to wages to cover fringe benefits. Lava rock will cost $3 per cubic foot. Brick will cost $2 per cubic foot. Your bid must add a profit margin of 30% to your expected cost.

Your task is to write a program that prompts the user for input of the various parameters—wall dimensions, crew days, rock cost, and so on—and prints a neat calculation of the bid price for the wall. 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 Sieve of Eratosthenes computes all primes less than some given n. But sometimes you need the opposite, the first n primes, not knowing the largest prime in the set. One method is to calculate the nth prime, using a prime-counting formula, then use the Sieve of Eratosthenes to generate the list. Or instead of calculating the nth prime directly, you can over-estimate the nth prime using the formula P_n < n log (n log n), then trim the list as needed; that’s the natural logarithm to the base e.

Another method is described by Melissa O’Neill in her article The Genuine Sieve of Eratosthenes. Her method is based on sifting each prime, and makes exactly the same sequence of calculations as the regular Sieve of Eratosthenes, but instead of marking bits in a bitarray it uses a priority queue to keep track of composites, one item in the priority queue for each prime; thus, instead of marking all the composite multiples of each sifting prime all at once, in the bitarray, O’Neill’s method keeps a priority queue of the next item in each sifting sequence, inserts a new sifting sequence in the priority queue as each new prime is encountered, and resets the next item in each sifting sequence as it is reached.

Thus, ignoring 2 and the even numbers, O’Neill’s method begins with i = 3 and an empty priority queue. Since 3 is not in the priority queue, it is prime, so it is output, the pair i×i/i×2 = 9/6 is added to the queue, and i is advanced to i + 2 = 5. Now since 5 is not in the queue, it is prime, so it is output, the pair 25/10 is added to the queue, and i is advanced to 7. Now since 7 is not in the queue, it is prime, so it is output, the pair 49/14 is added to the queue, and i is advanced to 9; at this point the queue is [9/6 25/10 49/7]. Now i = 9 is in the queue, so it is composite, and the pair 9/6 is removed from the priority queue and replaced by the pair 15/6, where 15 is calculated as the current composite 9 plus the skip value 6. And so on, until the desired number of primes has been generated. Note that in some cases a composite will be a member of multiple sifting sequences, and each must be replaced; for instance, when i reaches 45, it is a member of the sifting sequences for both 3 and 5, so the priority queue will have pairs 45/6 and 45/10, which should be replaced by 51/6 and 55/10, respectively.

Your task is to implement O’Neill’s algorithm to compute the first n primes. 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

According to legend, there is a temple in Hanoi where are located sixty-four golden rings of graduated sizes and three diamond towers. Each day, the monks of the temple move a ring from one tower to another according to the rule that only one ring may be moved each day, that a single move consists of taking the highest ring from one tower and placing it on another tower, and that no ring may be placed on top of a smaller ring. The rings and towers were placed at the beginning of the world, and the monks have toiled through the ages to move all the rings from the designated starting tower to the designated finishing tower, at each day making the move that minimizes the total number of moves required. The world will end when the monks complete their work.

Actually, there is no legend; the story was concocted as a mathematical puzzle by Edouard Lucas, whom we have met in our work on primality testing. The program that determines the sequence of moves is often used as a demonstration of recursion: to move five rings from the first tower to the second, first move four rings from the first tower to the third, then move the fifth ring from the first tower to the second, then move four rings from the third tower to the second. To move four rings from the first tower to the third, first move three rings from … There is also an iterative solution, but I can never remember it, and the recursive solution is so simple that it’s the one I always use.

Your task is to write the program that calculates the sequence of moves that solved the Tower of Hanoi using the fewest number of moves. 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 1934, an Indian math student, S. P. Sundaram, invented a new method of sieving primes:

From a list of integers from 1 to n, remove all integers of the form i + j + 2ij where integers i and j range from 1 ≤ i ≤ j and i + j + 2ij ≤ n. For each remaining integer k, the integer 2k+1 is prime, and the list gives all the odd primes (thus excluding the prime 2).

Your task is to implement the sieve of Sundaram and calculate the list of primes to a million. 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 1993, Urban Müller invented the brainfuck programming language, which is a simple-minded programming language, similar to a Turing machine, with a very terse syntax. The data store consists of 30000 cells, each a single byte initialized to 0; a data pointer points to one of the cells. Programs consist of the eight characters +-.,[] with the following meanings:

< move the data pointer one cell left
> move the data pointer one cell right
+ increment the cell at the current data pointer
- decrement the cell at the current data pointer
. output the cell at the current data pointer as a character
, input the next character to the cell at the current data pointer
[ if the cell at the current data pointer is zero, move the instruction pointer to the matching ]
] move the instruction pointer to the matching [

The brainfuck interpreter runs through a program performing each instruction as it appears, ignoring all characters other then +-.,[], advancing the instruction pointer after each instruction (including after [ and ]); a program halts by running off its end. Here’s a sample brainfuck program, which prints “Hello World!” when it is run; additional sample programs appear on the next page:

++++++++++[>+++++++>++++++++++>+++>+<
<<<-]>++.>+.+++++++..+++.>++.<<++++++
+++++++++.>.+++.------.--------.>+.>.

Your task is to write a brainfuck interpreter. 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