Programming Praxis

We have a simple task today, a function that formats a number in dollar format. A number like 1234567.8912 should be rounded to two positions after the decimal point, have commas inserted every three positions before the decimal point, and have a dollar sign prepended; thus, the function should format 1234567.8912 as $1,234,567.89.

Your task is to write a function that returns numbers in dollar format; if your language provides such a facility natively, you are not permitted to use 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

Today’s exercise comes from the end-of-chapter exercises in the sorting chapter of a programming textbook:

Write a program that finds the maximum product of three numbers in a given array of integers.

Your task is to write the desired 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

There are various puzzles in which water is poured from one jug to another to reach a desired amount of water. In the version we consider today, we have two jugs, an unlimited amount of water to fill them, and a drain into which we can pour an unlimited amount of water. The two jugs have known capacities, but it is not possible to accurately measure portions of a jug.

As an example, we wish to obtain four gallons of water, using jugs of capacities three and five gallons. Starting with two empty jugs, it is possible to obtain four gallons of water using the following six steps:

1. Fill the five-gallon jug.
2. Pour three gallons from the five-gallon jug to the three-gallon jug, leaving two gallons in the five-gallon jug.
3. Empty the three-gallon jug.
4. Pour two gallons from the five-gallon jug to the three-gallon jug, leaving the five-gallon jug empty and two gallons in the three-gallon jug.
5. Fill the five-gallon jug.
6. Pour one gallon from the five-gallon jug into the three-gallon jug, filling it, leaving the desired four gallons in the five-gallon jug.

Bruce Willis figured that out once; so too do thousands of school children every year.

Your task is to write a program that solves this kind of water-jug problem using the minimum number of steps (filling a jug, emptying a jug, or pouring one jug into the other). 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 recent post at Reddit asked for a way to encrypt two plaintexts to the same ciphertext; the application was in geocaching, where a series of caches leads to two different locations depending on the decoded message. That’s an interesting question, and the responses there got it wrong. Fortunately, the poster also asked at the crypto reddit, and the people there were more helpful.

Your task is to write a program that decrypts two different plaintexts from the same ciphertext, given two different keys. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution in the comments below.

Pages: 1 2

During the development of Algol 60, Donald Knuth devised a nasty test of recursion:

There are quite a few ALGOL60 translators in existence which have been designed to handle recursion and non-local references properly, and I thought perhaps a little test-program may be of value. Hence I have written the following simple routine, which may separate the man-compilers from the boy-compilers:

begin 
 real procedure A(k, x1, x2, x3, x4, x5);
 value k; integer k;
 begin
  real procedure B;
  begin 
   k := k - 1; 
   B := A := A(k, B, x1, x2, x3, x4)
  end;
  if k ≤ then A : = x4 + x5 else B
 end
 outreal(A(10, 1, -1, -1, 1, 0))
end

This uses nothing known to be tricky or ambiguous. My question is: What should the answer be? Unfortunately, I don’t have to a man-compiler myself, and so I was forced to try hand calculations. My conjecture (probably wrong) is that the answer will be:

73 - 119 - 177 + 102 = - 121

I’d be very glad to know the right answer.

Your task is to write a program that computes the right answer. 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’ve seen this question two or three times recently on message boards that provide interview questions, so I guess we ought to add it to our collection:

Create and implement a data structure that provides

• insert
• delete
• find min
• find max
• delete min
• delete max

 

all in O(1) time, regardless of the type of the underlying data.

Your task is to create and implement that data structure. When you are finished, you are welcome to read a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

Today’s exercise is an apology from me, for writing an absolutely horrible piece of code.

While working on the nearly square divisors series of exercises, I discovered that the divisors function that I normally use is extremely slow when the number of divisors is large.

Your task is to write a function that returns the list of divisors of a number, and works with reasonable efficiency. 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 nearly square divisors exercise has generated a considerable amount of interest, and several excellent solutions in the comments. We looked previously at Matthew Arcus’ solution using a knapsack algorithm, with logarithms to reduce the problem from multiplication to addition, thus allowing languages like C to solve the problem using their native data types instead of switching to big integers.

The knapsack solution works like this: To find the nearly square divisor of n, factor n and form the list of divisors ds. Then use the subset sum algorithm of a previous exercise (a variant of knapsack), taking products rather than sums, to find the maximal product of divisors less than the square root of n. There are several ways to solve the subset sum problem. The standard solution uses dynamic programming. Another solution splits the problem space into two parts. Both solutions require exponential time, though the meet-in-the-middle solution has better asymptotic time of O(n2^n/2). We also studied a solution that takes polynomial time to produce an approximate answer to the subset sum problem, although that solution is not helpful to us because it already takes exponential time to calculate all the divisors.

Today we look at another solution buried in the comments, this one from Paul Hofstra. Here is his solution:

def divisors(facs):
    factors = [(1,) + tuple(accumulate(g, mul)) for _, g in groupby(facs)]
    div = [1]
    for g in factors:
        div = [d * f for d in div for f in g]
    return div
 
def nsd5(number):
    """ output: nearly square divisor
        method: split factors in 2 equal parts
                create divisors with small factors and sort (descending)
                create divisors with large factors (<= ulimit) and sort
                loop over large divisors and small divisors and search
                   for highest product <= ulimit
    """
    ulimit = isqrt(number)
    facs = rho_factors(number)
    mid = len(facs) // 2
    descending = reversed(sorted(divisors(facs[:mid])))
    ascending = iter(sorted(divisors(facs[mid:])))
    best = 0
    desc = next(descending)
    while True:
        for asc in ascending:
            prod = asc * desc
            if prod > best:
                if prod <= ulimit:
                    best = prod
                else:
                    break
        else:
            break  # while
        for desc in descending:
            prod = asc * desc
            if prod <= ulimit:
                if prod > best:
                    best = prod
                break
        else:
            break  # while
    return best

With this solution we are back to using big integers, and we are using the meet-in-the-middle variant of the subset sum solution to calculate the answer. The solution finds the factors, splits them into two halves, calculates the divisors of each half, then uses subset sum to find the maximal divisor less than the square root. Note that we don’t have to compute all the divisors, only the divisors of each of the two halves.

Your task is to implement Hofstra’s solution to the nearly square divisor problem and use it to calculate the nearly square divisor of the product of the primes less than 190. 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 two lists, the merge point is the point after which the two lists are identical and can be merged. For instance, given the lists (a b c x y z) and (g h i x y z), the merge point is at (x y z). If the last items in the two lists differ, the merge point is null; if the two lists are the same, the entire list is the merge point.

Your task is to write a program that finds the merge point of two lists; it should return the unique prefix of the first list, the unique prefix of the second list, and the common suffix of the two lists. 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