Planet Scheme

July 29, 2016

Programming Praxis

Gnome Sort

A garden gnome sorts flower pots by the following method:

The gnome looks at the flower pot next to him and the flower pot just behind him. If they are correctly ordered, so the flower pot just behind him is smaller than the flower pot next to him, he steps one pot forward; otherwise, he swaps the two flower pots and steps one pot backward. If there is no flower pot just behind him (thus, he is at the start of the line of flower pots), he steps forward to the next pot. If there is not flower pot next to him (thus, he is at the end of the line of flower pots), he is done.

Your task is to implement a program that sorts by the gnome method. 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 July 29, 2016 09:00 AM

July 26, 2016

Programming Praxis

Changing Gender

The culture wars have my head spinning so fast that I need a computer to help me out. One day I might say “He is my brother.” and the very next day, speaking about the same person, say “She is my sister.”

Your task is to write a program that changes the gender of the words in a string. 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 July 26, 2016 09:00 AM

July 22, 2016

The Racket Blog

Racket v6.6

Racket version 6.6 is now available from http://racket-lang.org/

  • The new Macro Profiler command-line tool (`raco macro-profiler`) shows how macros contribute to the final expanded code size of a program.
  • Typed Racket supports intersection types. This allows the type system to track more information, and for programmers to express more precise types.
  • Typed Racket produces up to 4x smaller compiled files compared with Racket 6.5, reducing the size of the Racket distribution by 50M.
  • Typed Racket issues warnings in cases where the contract generated for Any was not strict enough in the past. These warnings will become errors in a future release. Warnings are enabled via View -> Show Log in DrRacket, and shown by default on command-line Racket.
  • Typed Racket enforces uses of cast more correctly, by checking both the "casted-to" and "casted-from" types. Previously, only the former were checked. In some cases, this will produce contract errors in programs that did not have errors before.
  • syntax-parse raises an error when an ellipsis pattern has an empty match rather than diverging, and it logs a warning when it statically detects a nullable pattern, such as ((~seq) ...). In the next version of Racket, it will reject the pattern instead, and it will remove special handling that currently makes some uses of such patterns terminate.
  • htdp/dir: The create-dir function delivers data information for files in a new field. The domain of its functions are backwards compatible.

The following people contributed to this release:
Alex Knauth, Alexander Shopov, Alexis King, Andrew Kent, Asumu Takikawa,
Ben Greenman, Bernardo Sulzbach, Brian Lachance, Chris Jester-Young, Dan
Feltey, Eric Dobson, Georges Dupéron, Gustavo Massaccesi, James Bornholt,
Jay McCarthy, John Clements, Leandro Facchinetti, Leif Andersen, Maksim
Kochkin, Matthew Flatt, Matthias Felleisen, Mike Sperber, Paul Stansifer,
Pedro Caldeira, Philip McGrath, Robby Findler, Ryan Culpepper, Sam
Tobin-Hochstadt, Spencer Florence, Stephen Chang, Stephen De Gabrielle,
Tim Brown, Tony Garnock-Jones, Vincent St-Amour, WarGrey Gyoudmon Ju,
William J. Bowman, and Zeina Migeed.

Feedback Welcome

by Vincent St-Amour (noreply@blogger.com) at July 22, 2016 11:50 PM

Programming Praxis

Array Manipulation

Our task today comes from Geeks for Geeks:

Given an array of positive integers, replace every element with the least greater element to its right. If there is no greater element to its right, replace it with -1. For instance, given the array [8, 58, 71, 18, 31, 32, 63, 92, 43, 3, 91, 93, 25, 80, 28], the desired output is [18, 63, 80, 25, 32, 43, 80, 93, 80, 25, 93, -1, 28, -1, -1].

Your task is to write the program that manipulates an array 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 July 22, 2016 09:00 AM

July 19, 2016

Programming Praxis

Highly Composite Numbers, A Sieving Approach

We’ve seen programs to compute the sequence of highly composite numbers in two previous exercises. Today, we look at a third algorithm, based on the Sieve of Eratosthenes.

If you have to find a the divisors of a number, or count them, you can employ the brute-force method of testing each possible divisor from 1 to n, as in the first solution to this problem, or you can factor n and compute the divisors, as we have done in a previous exercise. But if you have to find the divisors of a bunch of numbers, in sequence, you can sieve for them; we also did that in a previous exercise. Once you know the divisor-count for each number from 1 to n, a simple sequential scan looking for successive records will create the list of highly composite numbers.

Your task is to write a program to calculate highly composite numbers less than a limit n using a sieving 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.


by programmingpraxis at July 19, 2016 09:00 AM

July 15, 2016

Programming Praxis

Highly Composite Numbers, Using Priority Queues

A different solution to the previous exercise exploits the form of highly composite numbers, which always consists of small primes to large exponents, so we can specify the highly composite number using only the exponents; for instance, 64221111 represents the number 26 · 34 · 52 · 72 · 111 · 131 · 171 · 191 = 293318625600. Since the exponents must be non-increasing, there are five possibilities for a larger highly composite numbers, represented using the power-notation as 74221111, 65221111, 64321111, 64222111, and 642211111. Thus, we find composite numbers by starting with the null power-list, which equates to the number 20 = 1, then add all possible successors to a priority queue, pop the successors in order, check each for a new record number of divisors, and push the successors of that number back on to the priority queue.

Your task is to generate the sequence of highly composite numbers using a priority queue. 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 July 15, 2016 09:00 AM

July 14, 2016

Guile News

GNU Guile 2.0.12 released

We are delighted to announce the availability of GNU Guile 2.0.12, a maintenance release in the current stable 2.0 series.

This release packages together many bug fixes that have accumulated over the last two years while the Guile team was otherwise busy working on the upcoming 2.2 series and on building the Guix package manager and GNU system distribution.

See the release notes for a list of user-visible changes in this release and a download link.

by Andy Wingo at July 14, 2016 08:36 PM

July 12, 2016

Programming Praxis

Highly Composite Numbers

[ Today’s exercise was written by Zacharias Voulgaris, based on a Numberphile video. Guest authors are always welcome; contact me if you wish to write an exercise. ]

A highly composite number, also called an anti-prime, is a number n for which d(m) < d(n) for all m < n, where d(x) is the divisor function that gives a count of the number of divisors of x; in other words, a highly composite number has more divisors than any smaller number. Thus, a highly composite number, which has many divisors, is the opposite of a prime number, which has only two divisors. The sequence of highly composite numbers, which begins 1, 2, 4, 6, 12, 24, 36, … (A002182), has been studied by Ramanujan and Erdös, among others, and is a continuing object of study by number theorists. A famous highly composite number, known to Plato, is 5040.

Your task is to write a program that returns all highly composite numbers less than a given limit. 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 July 12, 2016 09:00 AM

July 08, 2016

Programming Praxis

Greek Time

The modern day is divided into 24 hours, each with an equal number of minutes. In ancient times, before the invention of mechanical timepieces, the day was also divided into 24 hours, but not of equal length; there were 12 daytime hours, each of equal length, and 12 nighttime hours, each of equal length, but the length of a daytime hour and a nighttime hour differed, except on the two equinoxes.

For example, today, where I live, the sun will rise at 5:45 and set at 20:29, giving 884 minutes of sunlight, so there will be 73 2/3 minutes per daylight hour. Starting from sunrise at 5:45, the hours are 6:59, 8:12, 9:26, 10:40, 11:53, 13:07, 14:21, 15:34, 16:48, 18:02, and 19:15, with sunset at 20:29.

Your task is to write a program that calculates the daylight hours of the greek clock. 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 July 08, 2016 09:00 AM

July 05, 2016

Programming Praxis

Depth Charge

Creative Computing was a staple of my programming education; I remember typing in the games to run on a friend’s computer. Here’s a game from the very first issue of the magazine, written by 18-year old Dana Noftle:

In this program, you are the captain of the destroyer, USS Digital. An enemy submarine has been causing trouble and your mission is to destroy it. You may select the size of the “cube” of water you wish to search in. The computer then determines how many depth charges you get to destroy the submarine.

Each depth charge is exploded by you specifying a trio of numbers; the first two are the surface coordinates, the third is the depth. After each depth charge, your sonar observer will tell you where the explosion was relative to the submarine.

Here’s a sample game:

DEPTH CHARGE GAME

DIMENSION OF SEARCH AREA? 10

YOU ARE CAPTAIN OF THE DESTROYER USS DIGITAL.
AN ENEMY SUB HAS BEEN CAUSING YOU TROUBLE. YOUR
MISSION IS TO DESTROY IT. YOU HAVE 4 SHOTS.
SPECIFY DEPTH CHARGE EXPLOSION POINT WITH A
TRIO OF NUMBERS -- THE FIRST TWO ARE THE
SURFACE COORDINATES; THE THIRD IS THE DEPTH.

GOOD LUCK !

TRIAL # 1 ? 5,5,5
SONAR REPORTS SHOT WAS SOUTHEAST AND TOO HIGH.

TRIAL # 2 ? 3,7,7
SONAR REPORTS SHOT WAS SOUTHEAST AND DEPTH OK.

TRIAL # 3 ? 1,9,7
SONAR REPORTS SHOT WAS NORTHEAST AND DEPTH OK.

TRIAL # 4 ? 0,8,7

B O O M ! !  YOU FOUND IT IN FOUR TRIES!

The first coordinate is east/west, the second coordinate is north/south. Here is the program that appeared in Creative Computing (pages 18-19):

10 PRINT "DEPTH CHARGE GAME" \ PRINT
20 INPUT "DIMENSION OF SEARCH AREA"; G \ PRINT
30 N = INT(LOG(G)/LOG(2))+1 \ RANDOMIZE
40 PRINT "YOU ARE CAPTAIN OF THE DESTROYER USS DIGITAL."
50 PRINT "AN ENEMY SUB HAS BEEN CAUSING YOU TROUBLE. YOUR"
60 PRINT "MISSION IS TO DESTROY IT.  YOU HAVE"N"SHOTS."
70 PRINT "SPECIFY DEPTH CHARGE EXPLOSION POINT WITH A"
80 PRINT "TRIO OF NUMBERS -- THE FIRST TWO ARE THE"
90 PRINT "SURFACE COORDINATES; THE THIRD IS THE DEPTH."
100 PRINT \ PRINT "GOOD LUCK !" \ PRINT
110 A=INT(G*RND) \ B=INT(G*RND) \ C=INT(G*RND)
120 FOR D=1 TO N \ PRINT \ PRINT "TRIAL #"D, \ INPUT X,Y,Z
130 IF ABS(X-A)+ABS(Y-B)+ABS(Z-C)=0 THEN 300
140 GOSUB 500 \ PRINT \ NEXT D
200 PRINT \ PRINT "YOU HAVE BEEN TORPEDOED! ABANDON SHIP!"
210 PRINT "THE SUBMARINE WAS AT"A","B","C" \ GOTO 400
300 PRINT \ PRINT "B O O M ! !  YOU FOUND IT IN "D"TRIES!"
400 PRINT \ PRINT \ INPUT "ANOTHER GAME (Y OR N)", A$
410 IF A$="Y" THEN 100
42O PRINT "OK.  HOPE YOU ENJOYED YOURSELF." \ GOTO 600
500 PRINT "SONAR REPORTS SHOT WAS ",
510 IF Y>B THEN PRINT "NORTH",
520 IF Y<B THEN PRINT "SOUTH",
530 IF X>A THEN PRINT "EAST",
540 IF X<A THEN PRINT "WEST",
550 IF Y<>B OR X<>A THEN PRINT " AND",
560 IF Z>C THEN PRINT " TOO LOW."
570 IF Z<C THEN PRINT " TOO HIGH."
580 IF Z=C THEN PRINT " DEPTH OK."
590 RETURN
600 END

Your task is to rewrite the program in your favored programming language. 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 July 05, 2016 09:00 AM

July 01, 2016

Programming Praxis

Clock Angles

We have a fun little program for a lazy summer Friday:

Write a program that, given a time as hours and minutes (using a 12-hour clock), calculates the angle between the two hands. For instance, at 2:00 the angle is 60°.

Your task is to write a program that calculates clock angles. 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 July 01, 2016 09:00 AM

June 28, 2016

GNU Guix

GuixSD system tests

From its inception, Guix has had a thorough test suite—something that’s not only reassuring, but also the thing that allows for fearless evolution of the code. That we didn’t have this safety net when hacking on the whole operating system, GuixSD, made it uncomfortable and more risky. We are now addressing the problem with the introduction of system tests, closing one of the major roadblocks towards 1.0.

Before going into details, let me recap the sorts of testing that already occurred in Guix land.

Unit tests

Guix’s test suite currently contains almost 600 unit tests. Each one of these stresses one particular function or subset of the functionality of Guix. This covers core package management functionality such as package builds, utility modules such as monads or the public key infrastructure (PKI) used for authenticating binaries, maintenance tools such as lint and the importers, as well as the command-line interface.

Since Guix provides Scheme modules for use both in the package management front-end and on the “build side”, the latter is also tested. This includes part of the build systems, and helpers like our ELF validation module.

Package tests

Then come the software packages that Guix ships. All of the packages in the distro are under continuous integration on the 4 supported architectures (32-bit and 64-bit Intel compatible, as well as MIPS64 and ARMv7.) Our build farm serves the resulting binaries, which users can choose to download as substitutes for local builds. Our build server, which currently runs an instance of Hydra, always shows the number of succeeding/failing builds on its dashboard. That way, breakage introduced by changes in the package collection is always rapidly detected. This is a direct benefit of the functional packaging model.

Additionally, our policy is to always run each package’s test suite (typically “make check”) as part of its build process, unless there is a serious technical obstacle to doing that. That way, we can, and do catch integration issues, incompatibilities, and plain bugs before they hit users.

System tests

So far, so good. Now, what about GuixSD itself? GuixSD did not have an automated test suite until now. What it did have, though, is the ability to instantiate an operating system in a virtual machine (VM) or in a container. You would write your operating system declaration in a file, then run, say:

This gives you a script to launch a VM running an instance of the OS declared in ‘my-config.scm’. Already pretty convenient! And indeed, even more so back in the days when we were eating a fair amount of dog food. In fact, that’s how we ate our first dog food dishes, and the VM infrastructure was the fork and knife that made it more tolerable.

So what could we test exactly? Roughly, we want to test that the instantiated system behaves according to the source ‘operating-system’ declaration: that user accounts are all there, that system services are running as expected, that all of the configuration is taken into account.

To do that, we need to run the system under test in a VM, but we also need to instrument it. We use QEMU to run our VMs, and QEMU along with the Linux virtio-serial module nicely supports communication between the guest operating system and the host, a strategy also used by NixOS’ test driver. Concretely, we define a “marionette” service, which hooks a Guile read-eval-print loop (REPL) inside the guest. This allows the host to evaluate arbitrary code in the guest VM.

Now we can write build processes (aka. “derivations”) that will:

  1. instantiate an instrumented variant of the operating system configuration we want to test in a VM image;
  2. spawn the VM, run a series of tests on the guest OS, and return the test results.

Thus, a system test to make sure the ‘uname’ system call returns something that matches the OS declaration looks like this:

There are interesting things going on here. First, while this is all Scheme code, there are in fact three tiers or strata of code at play here: the code that produces the OS declaration and the derivation, the build code of that derivation—the test—embodied in a g-expression, and code sent from the host to the guest VM via ‘marionette-eval’.

Using Scheme all the way means we can share code, use the right tools such as the SRFI-64 test framework here, pass values from one tier to another, and so on. And of course, being a full-blown language rather than shell scripts or similar means we have a rich and semantically-clear interface at our fingertips: we can directly access the data structures that matter rather than grepping the output of high-level commands. As an example, we can directly query the system service manager right from Scheme, which is often useful in system tests.

Status

Guix now includes the test infrastructure described above; running “make check-system” runs all the currently defined tests. Currently we have tests for basic functionality. This includes making sure that all the system services declared are available and running. We have tests for specific system services such as the mcron job scheduling daemon—inspired by your parents’ cron, but with a powerful Scheme interface—and Avahi and its name service switch (NSS) integration.

Last but not least, we have tests of the full GuixSD installation procedure, which turned out to be more involved than the other tests. This works by running the GuixSD installation image in a VM, using another VM image as the target installation media, and finally booting the newly-installed system.

All the tests are automatically run on our build farm (see here, here, or there), which provides quick feedback. One step closer to 1.0!

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's 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 Ludovic Courtès at June 28, 2016 11:44 AM

Programming Praxis

Curious Numbers

Today’s exercise is in the style of Project Euler, so the rules are that your solution must not use more than a minute of computer time and that you can’t peek at the solution until you have the answer yourself.

Some numbers have the curious property that when they are squared, the number appears in the least-significant digits of the product. For instance, 6252 = 390625, and 71063762 = 50543227109376.

What is the sum of all numbers less than 1020 that have this curious property?

Your task is to find the sum 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 June 28, 2016 09:00 AM

June 24, 2016

Programming Praxis

Phone Numbers And Prime Factors

John Cook is a mathematician and programmer who runs a fascinating blog that I frequent.

Cook recently had an article about the prime factors of telephone numbers. He explained that, for 10-digit telephone numbers as used in the United States, the average number of distinct prime factors is 3.232 and the distribution is between 1 and 5 distinct prime factors about 73% of the time.

Your task is to write a function that determines the number of distinct prime factors of a number, and use that function to explore the distribution of the number of distinct prime factors in a range of telephone numbers. 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 June 24, 2016 09:00 AM

June 21, 2016

Programming Praxis

Two Interview Questions

I like to read a web site called Career Cup, both to enjoy solving some of the programming exercise given there and to find exercise for Programming Praxis. As I write this exercise, here are the two most recent exercises on Career Cup:

  • Given a function rand2 that returns 0 or 1 with equal probability, write a function rand3 that returns 0, 1 or 2 with equal probability, using only rand2 as a source of random numbers.
  • Given a set of characters and a dictionary of words, find the shortest word in the dictionary that contains all of the characters in the set. In case of a tie, return all the words of the same (shortest) length.

Your task is to write the two 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 June 21, 2016 09:00 AM