Programming Praxis

A person’s body mass index is a simple calculation based on height and weight that classifies the person as underweight, overweight, or normal. The formulas, for imperial and metric units, are:

BMI (imperial) = weight in pounds / (height in inches)² * 703

BMI (metric) = weight in kilograms / (height in meters)²

The usual categories are:

BMI <= 18.5: underweight

18.5 < BMI < 25: normal

25 <= BMI < 30: overweight

30 <= BMI < 40: obese

40 <= BMI: morbidly obese

For example, the BMI of a person who is 5′ 4″ and 125 pounds is 21.5 (normal) and the BMI of a person who is 190 centimeters and 95 kilograms is 26.3 (overweight).

Your task is to write a program that calculates the BMI and category given a person’s height and weight. 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 two exercises devoted to enumerating prime numbers:

1) How many prime numbers are there between 10⁵⁰ and 10⁵⁰ + 10⁶?

2) How many prime numbers between 1,000,000 and 2,000,000 are congruent to 1 (mod 4)?

Your task is to write programs that answer the two questions given above; you might note the hint in the title of the exercise. 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 have three simple interview questions today:

1) Verify that a binary tree is a binary search tree. In a binary search tree, all nodes to the left of the current node have values less than the value of the current node, all nodes to the right of the current node have values greater than the value of the current node, and those two rules hold for all nodes in the tree.

2) Remove duplicates from a list.

3) A girl counts on her fingers by counting 1 on her thumb, 2 on her index finger, 3 on her middle finge, 4 on her ring finger, and 5 on her pinkie. Then she continues the other way, counting 6 on her ring finger, 7 on her middle finger, 8 on her index finger, and 9 on her thumb. Then she continues the other other way, counting 10 on her index finger, 11 on her middle finger, 12 on her ring finger, and 13 on her pinkie. She continues in this way indefinitely. Write a program that, given n, determines which finger she will be on when her count reaches n.

Your task is to write programs that solve the three interview questions 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

We studied three bit hacks in a previous exercise. In today’s exercise we look at three more:

1) Compute the minimum (or maximum) of two integers without branching.

2) Determine if an integer is a power of two.

3) Swap the values of two variables without using any extra space.

Your task is to write bit hacks for the three tasks noted above; you may want to find multiple solutions for some of them. 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’m not sure of the original source of this fun little puzzle:

There is a monkey which can walk around on a planar grid. The monkey can move one space at a time left, right, up or down. That is, from (x, y) the monkey can go to (x+1, y), (x-1, y), (x, y+1), and (x, y-1). Points where the sum of the digits of the absolute value of the x coordinate plus the sum of the digits of the absolute value of the y coordinate are lesser than or equal to 19 are accessible to the monkey. For example, the point (59, 79) is inaccessible because 5 + 9 + 7 + 9 = 30, which is greater than 19. Another example: the point (-5, -7) is accessible because abs(-5) + abs(-7) = 5 + 7 = 12, which is less than 19. How many points can the monkey access if it starts at (0, 0), including (0, 0) itself?

Your task is to write a program that counts the number of available points. 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 was written by guest author Robert Fisher. Having worked on shrinkwrapped consumer software, e-commerce web apps, embedded systems, and insurance OLTP systems, Robert currently writes C/C++ and Javascript for HP Tippingpoint and writes Scheme whenever he can. Suggestions for exercises are always welcome, or you may wish to contribute your own exercise; feel free to contact me if you are interested. ]

Under Unix, files are identified by paths. These are strings of directory names separated by slash characters followed by the name of the file. Paths starting with a slash are absolute, but paths that don’t start with a slash are relative to the current directory. Relative paths may include “..” elements. These represent a parent directory. Likewise, “../..” would represent a grandparent directory. For example, if the current directory is “/home/bob” then “praxis/prelude.scm” represents the file “/home/bob/praxis/prelude.scm” and “../tom/bin/scheme” represents “/home/tom/bin/scheme”.

Your task is to write a function that takes the current directory path and a target path and returns an absolute and minimal path equivalent to the target path. 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

A time-honored tradition among programmers is to hack a program to reduce the number of operations it takes, and a major component of that effort goes in to bit hacks, which we can define as dealing with data structures smaller than a single byte. Embedded systems programmers use bit hacks all of the time, as do game programmers and many others. We have three tasks today:

1) Determine the sign of an integer.

2) Determine if two integers have the same sign.

3) Determine the absolute value of an integer without branching.

Your task is to write bit hacks for the three tasks noted above; you may want to find multiple solutions for some of them. 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

A prime number p is a Sophie Germain prime if 2p+1 is also prime. The list of Sophie Germain primes begins 2, 3, 5, 11, 23, 29, 41, 53, 83, 89, 113, 131, (A005384); it is not known if the list is infinite. Sophie Germain primes are named after the French mathematician Marie-Sophie Germain, who in 1825 proved Fermat’s last theorem for such primes; thus, if p is a Sophie Germain prime, then there do not exist integers x, y and z not equal to zero and not a multiple of p such that x^p + y^p = z^p.

One way to find Sophie Germain primes is to enumerate the primes p and check the primality of each 2p+1. That works fine for relatively small p. For larger p, amateur mathematician Harvey Dubner developed a sieve that speeds finding Sophie Germain primes:

Define the three polynomials f_p(c) = c * 3003 * 10^b – 1, f_q(c) = 2 f_p(c) + 1, and f_r(c) = (f_p(c) – 1) / 2. Choose b which is the approximate number of digits for the range of Sophie Germain primes you are searching.

Sieve each of the polynomials over the range 1 ≤ c ≤ m for some suitable m. Use as sieving primes the primes greater than 13 but less than some suitable f which is conveniently large but much less than the square root of f_p(1). All three polynomials are sieved over the same sieving array. Sieving is done in a similar manner to sieving the polynomials in the multiple polynomial quadratic sieve.

After sieving is complete, apply a primality test to each f_p(c) that survived all three sievings. If it is prime, check both f_q(c) and f_r(c) for primality. If f_q(c) is prime, then f_p(c) is a Sophie Germain prime. If f_r(c), then f_r(c) is a Sophie Germain prime.

Your task is to write a sieve that finds Sophie Germain primes as 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

In a normal hash table, a key is hashed then linear search is performed in the bucket where the key will be found if it exists in the hash table. A successful search terminates as soon as the key is found, on average half-way through the bucket, but an unsuccessful search requires that every item in the bucket be examined.

Donald Knuth proposed that instead of keeping keys in a bucket in random order they be kept in increasing order, so that a search can stop as soon as the search passes the value of the key. That means inserts take longer; you have to find the right place in the bucket to put the key instead of just putting it at the beginning of the bucket. But lookups are quicker, as an unsuccessful search can terminate half-way through the bucket, on average. This change also means that the data type of the hash table changes, as now the comparison function is less-than rather than equal-to.

Your task is to write a small library of ordered hash tables; you should provide lookup, insert and delete functions, at least. 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