September 16, 2016
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.
September 13, 2016
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
- 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.
September 9, 2016
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.
September 6, 2016
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(n2n/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 =  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:
September 2, 2016
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.
August 30, 2016
Today’s exercise is to write a program that, given n integers, outputs the list of k integers whose sum is maximum. That looks easy, but there is a catch: You must provide three solutions, one that runs in O(n log n) time, one that runs in O(n log k) time, and one that runs in O(n) time.
Your task is to write three programs 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.
August 26, 2016
Today’s exercise is to write a program that provides queues using a circular array. You should provide operations to make a new queue with a user-specified maximum size, determine if a queue is empty, add new elements to the end of the queue, and remove elements from the beginning of the queue.
Your task is to implement a queue 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.
August 23, 2016
In a recent exercise, we discussed the problem of computing the nearly square divisors of a composite number n = a · b, with a ≥ b, such that the difference a − b is as small as possible. We gave two solutions: The first solution enumerated the divisors one-by-one, by trial division counting from 1, until reaching the square root, which is fast if n is small but slow in general. The second solution factored n, computed the divisors, the picked the two divisors in the middle of the list, which is fast in general but slow if n is highly composite and thus has a large number of divisors.
In a comment on that exercise, Matthew Arcus, who is a regular reader and commentor at Programming Praxis, gave a splendid answer to the problem; it relies on factoring n, but is fast even if n has a large number of divisors. His algorithm reduces the multiplication of the factors to addition of their logarithms, which means that the knapsack algorithm can be used to find the greatest sum less than the logarithm of the square root.
Your task is to implement Matthew’s algorithm to find the nearly-square divisors of a number. 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.
August 19, 2016
Today’s exercise comes from my friend Dan:
I don’t have time to think about this now (very busy these days), so I’m just throwing the idea at you. I’m sure there’s some sort of mathematical theorem that relates, but I’m sure you’ll probably know off the top of your head.
I was fascinated not too long ago by the consulting firm we’ve hired to re-vamp our website. I think they were given a tip-off that the color selection for the website theme could be a sticky wicket. So their plan was to pull the colors dynamically from the main picture selected on the home page (and/or departmental pages), which could be changed easily or automatically. They were going to develop something that would pick out the most prominent 6 to 10 colors — even if there wasn’t much contrast (and even black & white photos would supposedly work) — which would be then used for the menus and general color scheme.
Anyway, all this got me thinking about sorting a list of numbers (if these were color codes, there could be lots) such that the greatest gaps would float to the top. I’m sure you get the idea, but I’ll give an example anyway — which I figured out in Excel (below):
Given a number set of 5, 12, 14, 15, 80, 121, 134, 144, 256 the descending-by-highest-difference sort would yield: 256, 80, 121, 134, 144, 12, 14, 15, 5. So in this case, the top 3 biggest gaps would be between 80, 121, and 256.Num Diff Num Diff ---- ---- ---- ---- 256 112 256 112 144 10 80 65 134 13 121 41 121 41 134 13 80 65 144 10 15 1 12 7 14 2 5 5 12 7 14 2 5 5 15 1
I have no idea if this makes sense for the colors thing — it just seemed like the type of problem you frequently do on Programming Praxis.
Hope all is well with you and your family!
Your task is to write a program that sorts a set of points in order by the diminishing gaps between 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.
August 16, 2016
In a recent exercise, we used a priority queue to calculate highly composite numbers. That worked, but it was too slow and required too much memory to compute very large highly composite numbers. In today’s exercise we will use the same algorithm but a new data structure that permits us to compute very large highly composite numbers.
We make two changes. First, we record both highly composite numbers and candidates that are being considered as new highly composite numbers in a data structure called number-divisors-exponents, or ndxs for short, which has a number n in its
car, the number of divisors d of n in its
cadr, and the exponents of the prime factors of n in its
cddr; carrying those numbers around rather than recomputing them as needed saves a little bit of time. The second change is more important; we use the distinct priority queue of a previous exercise to eliminate duplicate candidates, which greatly reduced the amount of computation needed to find highly composite numbers (since each candidate is considered only once) and the amount of memory require to store the candidates (because duplicates are not stored).
Your task is to write a program to compute highly composite numbers, 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.