Planet Scheme

December 06, 2016

Programming Praxis

Career Cup

Regular readers know that I sometimes find inspiration for these exercises at Career Cup:

Given two sorted arrays, efficiently find the median of the combined array.

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


by programmingpraxis at December 06, 2016 09:00 AM

December 02, 2016

Programming Praxis

Beale’s Cipher

In the early 1800, Thomas J. Beale mined a large quantity of gold and silver, secretly, some place in the American West, and brought the gold, silver, and some jewels purchased with the treasur to Virginia, where he buried it. He wrote three coded documents that described the location of the buried treasure, the nature of the treasure, and the names of the owners. He never came back to retrieve the treasure. Only the second of those documents has been decoded, and many people, even today, are scouring Bedford County, Virginia, looking for buried treasure. Or so the story goes.

Beale used a variant of a book cipher. He chose a long text as a key, numbered each of the words in the text sequentially, starting from 1, and formed a message by choosing from the key text a word for each character of plain text having the same initial letter as the plain text; the cipher text consists of a list of the sequence numbers of the chosen words. For instance, if the key text is “now is the time” and the plain text is “tin”, then either (3 2 1) or (4 2 1) are valid encipherments. If the key text is long, there will be many duplicates, as we saw with the letter “t”, and the resulting cipher will be reasonably secure. Beale used the 1322 words of the Declaration of Independence as the key text for the second document; the key texts associated with the first and third documents are unknown.

Your task is to write programs that encipher and decipher messages using the Beale cipher; use it to decode the second document. 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.


by programmingpraxis at December 02, 2016 09:00 AM

November 29, 2016

Programming Praxis

Fenderbender’s Square Reckoner

In many of our programs involving prime numbers and number theory, we need to be able to determine if a number n is a perfect square. One way to do that is to determine the integer square root of the number, using Newton’s method, then multiply to determine if the original number is a square. But that’s slow. In a previous exercise, we used a method devised by Henri Cohen to calculate the quadratic residues of n to various moduli, which can quickly determine that some n cannot be perfect squares.

Over at Mersenne Forum, fenderbender extends Cohen’s idea to make a ridiculously fast square predicate: he precalculates multiple moduli to reduce the operation from big integers to 32-bit integers, chooses the moduli after extensive testing, and tests the quadratic residues using a 64-bit bloom filter. The result is impressive. Where Cohen eliminates the expensive square root calculation in 99% of cases, fenderbender eliminates the expensive square root calculation in 99.92% of cases, and does it faster than Cohen. Go read fenderbender‘s explanation to see a beautiful combination of number theory, wonky programming, and sheer artistry.

Your task is to implement fenderbender‘s square predicate. 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.


by programmingpraxis at November 29, 2016 09:00 AM

November 25, 2016

Programming Praxis

Three Amazon Interview Questions

These three questions come from Career Cup:

First: A kidnapper wants to write a ransom note by cutting characters from the text of a magazine. Given two strings containing the characters of the ransom note and the characters of the magazine, write a program to determine if the ransom note can be formed from the magazine.

Second: Write a program that operates in linear time that finds the item in a list that appears the most times consecutively.

Third: Given two finite streams of integers that are too large to fit in memory, write a program that finds the integers that appear in both streams; it must operate in time linear in the length of the longer of the two streams.

Your task is to write the three programs 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.


by programmingpraxis at November 25, 2016 09:00 AM

November 22, 2016

Programming Praxis

Missing Items

We have today a simple exercise; we’ve seen variants of it previously.

Given two lists, find all the items in the first list that are not present in the second list. For instance, if (5 15 2 20 30 40 8 1) is the first list and (2 20 15 30 1 40 0 8) is the second list, the item 5 is present in the first list but not in the second list.

Your task is to write a program to find missing items. 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.


by programmingpraxis at November 22, 2016 09:00 AM

November 18, 2016

Programming Praxis

RIP Leibniz

Gottfried Wilhelm Leibnez was a German mathematician and philosopher, and a developer, independently of Isaac Newton, of calculus; it was he who invented the d/dx notation used in writing integrals. He died three hundred years ago, on November 14, 1716, so today (a few days late, sorry) we have an exercise about calculus:

Write a program that computes the average number of comparisons required to determine if a random sequence is sorted. For instance, in the sequence 1 2 3 5 4 6, the first inversion appears between 5 and 4, so it takes four comparisons (1<2, 2<3, 3<5, 5<4) to determine that the sequence is not sorted.

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


by programmingpraxis at November 18, 2016 09:00 AM

November 15, 2016

Programming Praxis

Marzullo’s Algorithm

This one is tricky:

Given a list of events with arrival and departure times, write a program that determines the time at which the greatest number events occurred.

For instance, you may have ten employees who arrived at work and departed at the times shown below (for instance, employee 9 arrived at 12:00noon and departed at 5:00pm):

employee   1  2  3  4  5  6  7  8  9 10
          -- -- -- -- -- -- -- -- -- --
arrival   10 12 11 13 14 12  9 14 12 10
departure 15 14 17 15 15 16 13 15 17 18

Then the maximum employee count was at 2:00pm:

 9 |                    7          | 1
10 |  1                 7       10 | 3
11 |  1     3           7       10 | 4
12 |  1  2  3        6  7     9 10 | 7
13 |  1  2  3  4     6  7     9 10 | 8
14 |  1  2  3  4  5  6     8  9 10 | 9
15 |  1     3  4  5  6     8  9 10 | 8
16 |        3        6        9 10 | 4
17 |        3                 9 10 | 3
18 |                            10 | 1

There were 9 employees at work at time 14.

Your task is to write a program that determines the start and end times of the time block where the greatest number of events occurred. 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.


by programmingpraxis at November 15, 2016 09:00 AM

November 11, 2016

Programming Praxis

Introspective Sort

The sorting algorithm that we have been working up to in three previous exercises is introspective sort, or introsort, invented by David Musser in 1997 for the C++ Standard Library. Introsort is basically quicksort, with median-of-three partitioning and a switch to insertion sort when the partitions get small, but with a twist. The problem of quicksort is that some sequences have the property that most of the recursive calls don’t significantly reduce the size of the data to be sorted, causing a quadratic worst case. Introsort fixes that by switching to heapsort if the depth of recursion gets too large; since heapsort has guaranteed O(n log n) behavior, so does introsort. The changeover from quicksort to heapsort occurs after k * floor(log(length(A))) recursive calls to quicksort, where k is a tuning parameter, frequently set to 2, that can be used to adjust performance of the sorting algorithm.

Your task is to implement introsort. 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.


by programmingpraxis at November 11, 2016 09:00 AM

November 10, 2016

GNU Guix

Growing Our Build Farm

We have received our new server for continuous builds of the GNU Guix system, and are putting the finishing touches on its installation. The machine is intended as an eventual replacement for hydra.gnu.org, a virtual machine kindly hosted by the FSF. The new machine will drive our build farm, which continuously compiles the GNU system, and it will feed the mirror with binary packages, so that end users who do not wish to compile packages by themselves can easily keep up-to-date. Time to report on the adventure! This first part covers the hardware.

Buying the new machine has been made possible through a very generous donation by Igalia to Guix Europe. Igalia is a free software consultancy well known for its involvement in the development of the GNOME stack, GStreamer, the JavaScript compilers of Web browsers, and more, promoting values close to the GNU Guix project. It is heartening that the company is helping us towards our goal of creating a free system that liberates its users to take their computing and data processing needs into their own hands!

Of course, we wanted to buy the best for the money — but it turned out the best did not exist yet! Our goal was a system that would be as free as possible, starting from the BIOS, without backdoors of one kind or another; of course it also needed to be powerful enough to pilot our build farm, which is expected to grow with an ever increasing number of packages and maybe new architectures. The Libreboot project provides a free BIOS, which was in the process of being ported to the ASUS KGPE-D16 mainboard. Timothy Pearson from the Coreboot project (on which Libreboot is based) worked hard to make the port a reality. We bought the machine from Thomas Umbach, owner of VIKINGS, a company selling complete servers based on this board and planning to provide hosting services on this platform. Thomas made us a very generous offer of only billing the parts, so we are grateful to VIKINGS as a second sponsor for this machine; independently, the close interaction with Thomas and his fast and helpful replies to our questions meant a very pleasant experience for a first-time buyer of a server machine! Hopefully, this will not be the last time either.

The machine arrived carefully packaged in styrofoam and cardboard packaging with a power cable and the rails for mounting it in the rack of the hosting facility (for the time being, however, it is still sitting on a Moroccan pouffe in my living room, waiting for its installation to be finished). It is 1U high to save hosting fees. At the front, two USB ports, a power and a reset button. At the back, more USB ports, Ethernet ports, a VGA and a serial port; apart from the latter, it does not look more exotic than my laptop.

Interior of the server. The interior looks very tidy to my untrained eyes. This is not only a good sign for the vendor&aposs professionalism, but according to Thomas also a necessity for ensuring sufficient air flow in the 1U case! This air flow is created by the array of five case fans on the right, in their orange housing. At the left, one can distinguish the two processors. We opted for the AMD Opteron 6262HE, which is free of backdoors to the best of our knowledge and power saving. Each of the processors has 16 cores, which should be amply enough for our needs (remember that the compilation of packages will take place on the build farm and not on this machine). Actually, only the processor fans and their big copper heatpipes are visible. There are 16 slots for memory, of which only four are used so far, each with a 16GB module for 64GB of total RAM — I do not think we will need to make use of our extension possibilities any time soon! Two hard disks of 4TB each are hidden under the metal cover to the right.

So the hardware looks very neat, and in the next installment, we will have a look at the installation of GuixSD on it.

Thanks again to all who made this adventure possible through their hard work and dedication, in particular Igalia, Thomas of VIKINGS, and Timothy of Coreboot and Raptor Engineering!

About GNU Guix

GNU Guix is a transactional package manager for the GNU system. The Guix System Distribution or GuixSD is an advanced distribution of the GNU system that relies on GNU Guix and respects the user&aposs freedom.

In addition to standard package management features, Guix supports transactional upgrades and roll-backs, unprivileged package management, per-user profiles, and garbage collection. Guix uses low-level mechanisms from the Nix package manager, except that packages are defined as native Guile modules, using extensions to the Scheme language. GuixSD offers a declarative approach to operating system configuration management, and is highly customizable and hackable.

GuixSD can be used on an i686 or x86_64 machine. It is also possible to use Guix on top of an already installed GNU/Linux system, including on mips64el and armv7.

by Andreas Enge (guix-devel@gnu.org) at November 10, 2016 10:30 AM

November 08, 2016

Programming Praxis

A Median-Of-Three Killer Sequence

In two previous exercises we’ve been working toward a variant of quicksort that has guaranteed O(n log n) performance; there is no quadratic worst case. Before we do that, however, it is instructive to look at the case where our optimized median-of-three version of quicksort fails. Consider this sequence, due to David Musser:

1 11 3 13 5 15 7 17 9 19 2 4 6 8 10 12 14 16 18 20

At the first partitioning, the pivot element will be the median of 1, 2 and 20, which is 2, and the only two elements that change will be 2 and 11, with the partition point after the 2, indicated by the vertical bar:

1 2 | 3 13 5 15 7 17 9 19 11 4 6 8 10 12 14 16 18 20

At the next step, the pivot element will be the median of 3, 4 and 20, which is 4, and again the partition will advance only by two:

1 2 3 4 | 5 15 7 17 9 19 11 13 6 8 10 12 14 16 18 20

And so on. Each partition contributes the least possible amount toward the solution, and the time complexity becomes quadratic.

Your task is to write a program that creates a “killer sequence” for the median-of-three partition, then compare its time to the time required for sorting a random partition. 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.


by programmingpraxis at November 08, 2016 09:00 AM

November 04, 2016

Programming Praxis

Two Stacks

Different programs manage memory in different ways. One common pattern uses two stacks of variable sizes; memory is arranged so that one stack starts at the bottom of memory and grows up, the other stack starts at the top of memory and grows down.

Your task is to write a program that simulates memory management in an array, using two stacks. 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.


by programmingpraxis at November 04, 2016 09:00 AM

November 01, 2016

Programming Praxis

Hoare’s Partition, Improved

In today’s exercise we will make several improvements to the quicksort program of the previous exercise, working in small steps and measuring our progress throughout. We make the following improvements:

    1. Move the swap and comparison inline.
    2. Early cutoff and switch to insertion sort.
    3. Improved pivot with median-of-three.

All three improvements are well-known. The first improvement eliminates unneeded function-calling overhead. The second improvement reduces the number of recursive calls on very small sub-arrays, replacing them with a sorting algorithm that is well-adapted to nearly-sorted arrays. The third improvement improves the likelihood of a good partition and eliminates some cases where the algorithm performs poorly.

Your task is to write an improved quicksort and measure your improvement. 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.


by programmingpraxis at November 01, 2016 09:00 AM

October 28, 2016

Programming Praxis

Hoare’s Partition

I’ve recently rekindled my interest in sorting algorithms (it’s a fascination that never really goes away), and I’ve been looking at quick sort. The most common academic version of quick sort uses a partition due to Nick Lomuto, which takes a single pointer that scans through the arry, concludes with the partitioning element in the middle, all the less-than items to its left, and all the greater-than items to its right, then recurs on the two halves; the partitioning element is never part of any subsequent recursive call in the quick sort.

The original partitioning algorithm by C. A. R. Hoare works differently, with two pointers instead of one. One pointer starts at the left end of the array, and is advanced until it finds an item out of place. The other pointer starts at the right end of the array, and marches to the left end of the array until it finds an item out of place. Then the array items are swapped, each pointer takes one step toward the other, and the process continues, stopping when the two pointers cross, at which time there is a final swap. Hoare’s partition concludes by returning the right-side pointer; all items to the left of the pointer, plus the item at the pointer itself, are smaller than all items to the right of the pointer. The partitioning element is somewhere in the left-hand partition, but not necessarily at its end, which requires a change to the recursive call in the quick sort algorithm, which includes the partitioning element.

Your task is to implement Hoare’s partition and use it to write a quick sort 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.


by programmingpraxis at October 28, 2016 09:00 AM

October 26, 2016

The Racket Blog

Racket v6.7

Racket version 6.7 is now available from http://racket-lang.org/
  • Racket supports building graphical applications on Android through the racket-android project: https://github.com/jeapostrophe/racket-android
  • The Racket REPL comes with line-editing, command and result history, and various meta-commands out of the box, via the racket/interactive module. See the racket/interactive and xrepl documentation for details.
  • The package system supports authentication when installing packages from git, using the raco pkg config git-checkout-credentials configuration option.
  • HTTP libraries, as well as raco pkg, support proxying via HTTP CONNECT.
  • Typed Racket provides typed versions of racket/os and racket/db/sqlite.
  • The PLT_COMPILED_FILE_CHECK environment variable provides more fine-grained control over when .zo files are consulted.
  • The documentation search supports searching for #langs and #readers via the "L:" and "R:" search prefixes.
  • The file/glob module implements globbing for path-strings.
  • Optimizations in the bytecode compiler improve performance for structure, list, string, and byte-string operations.
The following people contributed to this release:
Alex Knauth, Alex Harsanyi, Alexis King, Andrew Kent, Asumu Takikawa, Ben Greenman, Brian Lachance, Chongkai Zhu, Daniel Feltey, Georges Dupéron, Gustavo Massaccesi, Jay McCarthy, John Clements, Jonathan Schuster, Leif Andersen, Marc Burns, Matthew Butterick, Matthew Flatt,
Matthias Felleisen, Mike Sperber, Robby Findler, Rohin Shah, Ryan Culpepper, Sam Tobin-Hochstadt, Spencer Florence, Stephen Chang, Stephen De Gabrielle, Tim Brown, Tony Garnock-Jones, Vincent St-Amour, WarGrey Gyoudmon Ju, and William J. Bowman.

Feedback Welcome

by Vincent St-Amour (noreply@blogger.com) at October 26, 2016 11:31 PM

October 25, 2016

Programming Praxis

Trial Division

It was a gorgeous autumn weekend: brisk mornings, warm sunny afternoons, and absolutely no reason to sit at a computer screen indoors. And even though the programming on my big project at work is finished, there are still details to be looked after, so I had no time there, either. Thus, another recycled exercise today, another one that I’ve seen on the beginning-programmer message boards recently:

Write a program that determines the prime factors of a number n.

You should write at the level of a first-year programmer, nothing sophisticated. An appropriate algorithm is trial division.

Your task is to write a program to factor integers. 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.


by programmingpraxis at October 25, 2016 09:00 AM