Planet Scheme

September 22, 2017

Programming Praxis

Comma Quibbling

Eric Lippert, at his blog Fabulous Adventures in Coding, discusses the problem of comma quibbling, which turns a list of words like (“ABC” “DEF” “G” “H”) into the string “ABC, DEF, G and H” with commas between each pair of words except the last pair, which gets the word “and” (without a comma). Here are the rules:

  1. If the input is empty, so is the output.
  2. If the input has a single word, so does the output.
  3. If the input has two words, the output is the two words separated by “and”.
  4. If the input has more than two words, the output is all the words, separated by commas, but with the last comma replaced by “and”.

A word is a maximal sequence of characters not containing a comma or a space.

Your task is to write a function that adds commas to a list of words, using the rules 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 September 22, 2017 09:00 AM

September 19, 2017

Programming Praxis

Catalan’s Triangle

Since our exercise a week ago, I’ve been reading about Catalan numbers, primarily based on the references at OEIS. Catalan’s Triangle (A009766) is a number triangle

1
1 1
1 2  2
1 3  5  5
1 4  9 14 14
1 5 14 28 42  42
1 6 20 48 90 132 132

such that each element is equal to the one above plus the one to the left.

Your task is to write a program that calculates a Catalan triangle. 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 September 19, 2017 09:00 AM

September 15, 2017

Programming Praxis

Compile Chez Scheme On Android ARM

In a recent exercise I described my new tablet computer, and talked about installing Guile Scheme because I could not get Chez Scheme to compile. I have finally been able to compile my preferred Scheme interpreter, Chez Scheme, on my Android ARM tablet. This note describes how I did it.

Chez Scheme is written partly in C and partly in Scheme; as a consequence, it requires a working Scheme compiler to be compiled. For popular platforms, such as Linux, Chez Scheme is distributed with the Scheme portion of the compiler already compiled, but for the Android ARM platform, we have to compile the Scheme portion of the compiler ourselves. The procedure is to compile Chez Scheme on some available platform (we will use Linux), cross-compile the Scheme portion of the compiler for the Android ARM platform, compile the C portion of the compiler on Android ARM, and then complete the build on Android ARM. It’s easier than it sounds. First, if you don’t already have Chez Scheme running on your Linux platform, perform the following steps to obtain and compile Chez Scheme (similar instructions apply on other platforms, go to the Chez Scheme Project Page for assistance):

cd /usr/local/src
sudo wget https://github.com/cisco/ChezScheme/archive/v9.4.tar.gz
gunzip v9.4.tar.gz
tar -xvf v9.4.tar
sudo rm v9.4.tar
cd ChezScheme-9.4
sudo ./configure
sudo make install

At this point you should have a working Chez Scheme system on the Linux computer. You might want to stop and play with it to make sure it works. Assuming that you compiled on an Intel system, the machine type was a6le, so perform the following steps to cross-compile to machine type arm32le for the Android ARM:

sudo mkdir boot/arm32le
cd a6le
sudo make -f Mf-boot arm32le.boot
cd ..
sudo ./configure -m=arm32le
sudo ./configure --workarea=arm32le
cd arm32le/s
sudo make -f Mf-cross m=a6le xm=arm32le base=../../a6le

Now the cross-compilation is complete and you are ready to work on the Android ARM system. Still on the desktop, pack up the complete Chez Scheme system:

cd /usr/local/src
sudo tar -czvf ChezScheme-9.4.tar.gz ChezScheme-9.4

We look next at the Android ARM tablet. We will be running under GnuRoot, so that must first be installed and configured. On the tablet, go to the Google Play Store and install program GnuRoot Debian; it should take only a few minutes. The environment installed by GnuRoot is minimal, so perform the following steps to install some useful software on your system:

apt-get update && apt-get -y upgrade
apt-get install build-essential ed vim m4 gawk
apt-get install ssh guile-2.0 python wget curl

Depending on your aspirations, you might want to install some other packages, or omit some of those shown above. Next, copy the .gz file to directory /usr/local/src on an Android tablet running GnuRoot; I did it by performing the following commands on the tablet, which was connected to my local network, but they are unlikely to work unmodified on your machine:

cd /usr/local/src
sftp phil@192.168.1.65
     cd /usr/local/src
     get ChezScheme-9.4.tar.gz
     quit

Once you have copied the .gz file to the tablet, perform the following steps there. It is odd to install and then uninstall X-windows, but Chez Scheme requires X-windows to compile, and doesn’t require it to run, so this sequence is correct (that was the trick that took me so long to figure out, delaying the compilation by several weeks):

apt-get install libncurses5-dev libncursesw5-dev
gunzip ChezScheme-9.4.tar.gz
tar -xvf ChezScheme-9.4.tar
rm ChezScheme-9.4.tar
cd ChezScheme-9.4
apt-get x11-common libx11-dev
cd arm32le/c
make
apt-get purge x11-common libx11-dev
cd ../s
make allx
cd ../..

At this point the program is compiled and ready to use. However, the install script doesn’t work properly, for some reason, so the program must be installed manually with the following commands:

cp arm32le/bin/scheme /usr/local/bin
cp arm32le/bin/petite /usr/local/bin
chmod +x /usr/local/bin/scheme
chmod +x /usr/local/bin/petite
mkdir /usr/local/csv9.4/arm32le
cp boot/arm32le/scheme.boot /usr/local/csv9.4/arm32le
cp boot/arm32le/petite.boot /usr/local/csv9.4/arm32le

And that’s it. To test your installation, type scheme at the command-line prompt; you should be rewarded with the Chez Scheme welcome text followed by a Scheme prompt:

Chez Scheme Version 9.4
Copyright 1984-2016 Cisco Systems, Inc.

>

Your task is to get your preferred programming environment working on your mobile device, and let us know how it works. If anyone installs Chez Scheme, I would appreciate your feedback on the instructions given above, particularly if you find any errors.


by programmingpraxis at September 15, 2017 09:00 AM

September 12, 2017

Programming Praxis

Catalan Numbers

Today’s exercise is an Amazon interview question for software engineers and developers:

How many unique binary search trees can be made from a series of numbers 1, 2, 3, 4, …, n, for any given n?

Your task is to compute the number of unique binary search trees. 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 September 12, 2017 09:00 AM

September 08, 2017

Programming Praxis

Linked List Palindrome

Today’s exercise is an Amazon interview question from Career Cup (this is the exact question asked):

There is a given linked list where each node can consist of any number of characters :- For example
a–>bcd–>ef–>g–>f–>ed–>c–>ba.
Now please write a function where the linked list will return true if it is a palindrome .
Like in above example the linked list should return true

Your task is to write a program to determine if a list of strings forms a palindrome. 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 September 08, 2017 09:00 AM

September 05, 2017

Programming Praxis

Three Bit Hacks

We have three problems today that involve twiddling bits. In all three cases you are not permitted to perform any branching operation (so no if-else statement) nor are you permitted to perform a loop; you must write a single statement that performs the requested task:

1) Determine the absolute value of an integer.

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

3) Determine the minimum and maximum of two integers.

The restrictions on branching and loops are useful for modern CPUs that have instruction caches that you want to stay inside for speed.

Your task is to write the three bit hacks 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 September 05, 2017 02:00 PM

GNU Guix

Announcing Guix-HPC

Today, Inria, the Max Delbrück Center for Molecular Medicine (MDC), and the Utrecht Bioinformatics Center (UBC) are announcing a joint effort to consolidate GNU Guix for reproducible scientific workflows in high-performance computing (HPC). The three research institutes have been using Guix and contributing to it. The new effort, dubbed Guix-HPC, hopes to extend Guix functionality to better address the needs of HPC users, as well as augmenting its package collection.

Guix was not initially designed with HPC in mind. However, we believe it has many good properties both for flexible software deployment on clusters, and as a foundation for reproducible scientific workflows. The Guix-HPC blog will regularly feature articles with HPC “howtos” and stories about our achievements. We are thrilled by the opportunities this new effort offers!

To learn more, visit the Guix-HPC Web site.

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, armv7, and aarch64.

by Ludovic Courtès, Roel Janssen, Pjotr Prins, Ricardo Wurmus (guix-devel@gnu.org) at September 05, 2017 10:00 AM

September 01, 2017

Programming Praxis

Generator Push-Back

Generators are a useful programming tool; we provide an implementation in the Standard Prelude. Here is a Python prime-number generator that we discussed in a previous exercise:

def primegen(): # http://stackoverflow.com/a/20660551
    yield 2; yield 3          # prime (!) the pump
    ps = primegen()           # sieving primes
    p = next(ps) and next(ps) # first sieving prime
    D, q, c = {}, p*p, p      # initialize
    def add(x, s):            # insert multiple/stride
        while x in D: x += s  #   find unused multiple
        D[x] = s              #   save multiple/stride
    while True:               # infinite list
        c += 2                # next odd candidate
        if c in D:            # c is composite
            s = D.pop(c)      #   fetch stride
            add(c+s, s)       #   add next multiple
        elif c < q: yield c   # c is prime; yield it
        else: # (c == q)      # add sqrt(c) to sieve
            add(c+p+p, p+p)   #   insert in sieve
            p = next(ps)      #   next sieving prime
            q = p * p         #   ... and its square

I recently needed to interrupt a prime generator, then restart it; I needed all the primes up to a limit, but of course I didn’t know I had reached the limit until the generator produced the first prime past the limit. I could have saved the too-large prime, then used it before restarting the generator, but that’s inconvenient; it needs a separate variable for the saved prime, and a test to determine if a saved prime is available each time through the restarted generator. A better solution is to push back the value onto the generator:

def pushback(val,gen):
    yield val
    while True:
        yield next(gen)

Your task is to add push-back to the generator of your favorite 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 September 01, 2017 09:00 AM

August 29, 2017

Programming Praxis

Camel Case

Some programmers write variable names in camelCase, each word starting with a capital letter, while other programmers separate words with underscores like_this.

Your task is to write programs that convert between the two forms. 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 August 29, 2017 09:00 AM

August 25, 2017

Programming Praxis

Find The Nearest Prime

I’ve seen this problem several times on Stack Overflow and other message boards:

Write a program to find the nearest prime number to a given real number. You may limit the search to the hundred smallest primes.

Your task is to write the program to find the nearest prime 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.


by programmingpraxis at August 25, 2017 04:00 AM

August 22, 2017

Programming Praxis

Lehman’s Factoring Algorithm

The oldest algorithm for factoring integers, still used today, is trial division, which takes time proportional to the square root of the number being factored. In the 17th century, Pierre de Fermat invented a different algorithm, based on finding a difference of squares, that also takes time proportional to the square root of the number being factored, but works well when a number’s two factors are both near the square root of the number; we studied Fermat’s algorithm in a previous exercise. In today’s exercise we will study a factoring algorithm due to R. Sherman Lehman that modifies Fermat’s algorithm so it takes time proportional to the cube root of the number being factored. Lehman’s algorithm suffers the same problem as Fermat’s — it is slow unless the two factors are near each other — but in cases where it is appropriate, it is much faster than Fermat’s algorithm.

Let’s begin by recapping Fermat’s algorithm. It starts by taking the smallest integer larger than the square root of the number n being factored, call that number a, then increases a by 1 until b = a2n is a square, at which point we have n = a2b2 = (ab) (a + b) = n by algebraic identity. Pomerance likes to use the example 8051 = 902 − 72 = (90 − 7) (90 + 7) = 83 × 97; he tells the story of an arithmetic contest in his school days that he lost because he didn’t recognize the difference of squares. Here is how Crandall and Pomerance give Fermat’s algorithm in their book Prime Numbers: A Computational Perspective:

Algorithm 5.1.1 (Fermat method). We are given an odd integer n > 1. This algorithm either produces a nontrivial divisor of n or proves n prime.

1. [Main loop]
    for (⌈√n⌉ ≤ a ≤ (n + 9) / 6) {
        if (b = √(a2n) is an integer) return ab
    }
    return "n is prime"

In their book, Crandall and Pomerance prove the odd termination condition of the loop.

There are tricks, both mathematical and computational, that can speed up Fermat’s algorithm, but in general you will have to accept that it is pretty slow, because no matter what you do you have to count from √n to n, which is a long way.

One useful trick is to multiply n by a multiplier. Crandall and Pomerance give the example of n = 2581. Fermat’s algorithm has us start with a = 51 and take 9 square roots, finding a difference of squares when a = 59, so that 592 − 2581 = 900 = 302 and 2581 = (59 − 30) (50 + 30) = 29 × 89. But if we take the multiplier k = 3, then kn = 3 × 2581 = 7743, Fermat’s algorithm starts with a = 88, and on the first iteration through the loop b = 882 − 7743 = 1, the factorization of kn = (88 − 1) (88 + 1) = 87 × 89, and the factorization of n = gcd(87, n) × gcd(89, n) = 29 × 89.

Of course, there is no way to know a priori that multiplier k = 3 leads to a quick factorization. Lehman’s method systematizes the search for a good multiplier. Here is how Crandall and Pomerance give Lehman’s algorithm:

Algorithm 5.1.2 (Lehman method). We are given an integer n > 21. This algorithm either provides a nontrivial factor of n or proves n prime.

1. [Trial division]
Check whether n has a nontrivial divisor dn1/3, and if so, return d.

2. [Loop]

    for (1 ≤ k ≤ ⌈n1/3) {
        for (⌈√(4kn⌉)⌉ ≤ a ≤ ⌊√(4kn) + n1/6 / (4√k)⌋) {
            if (b = √(a2 − 4kn) is an integer) return gcd(a + b, n)
        }
    }
    return "n is prime"

Again, Crandall and Pomerance prove the odd termination condition in their book, and also the odd input condition n > 21. They also prove that Lehman’s algorithm takes time proportional to the cube root of the number being factored. Lehman’s algorithm is of historical importance, as it was the first factoring algorithm to take less than time proportional to the square root of the number being factored, but it is was never used in practice, as Jon Pollard’s rho algorithm was published shortly after Lehman’s algorithm, and it has both a better time complexity, taking time proportional to the fourth root of the number being factored, and is also significantly faster in practice.

Your task is to implement the factoring algorithms of Fermat and Lehman; you might want to do some timing experiments to compare them to each other and to naive trial division. 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 August 22, 2017 04:00 AM

August 18, 2017

Programming Praxis

One Step, Two Steps

Today’s exercise is a simple matter of counting:

Suppose you can take either one or two steps at a time. How many ways can you travel a distance of n steps? For instance, there is 1 way to travel a distance of 1 step, 2 ways (1+1 and 2) to travel two steps, and 3 ways (1+1+1, 1+2 and 2+1) to travel three steps.

Your task is to write a program to count the number of ways to travel a distance of n steps, taking 1 or 2 steps at a time. 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 August 18, 2017 09:00 AM

August 15, 2017

Programming Praxis

Phone Numbers

Today’s task looks like homework:

Make a list of n-digit phone numbers according to the following rules:

1) First digit must not be zero.
2) First digit may be four, but no digits after the first may be four.
3) Any two consecutive digits must be different.
4) The user may specify any set of digits that may not appear in the phone number.

For instance, if n = 3 and the digits 1, 3, 5, 7, and 9 don’t appear in the output, the desired list of three-digit numbers starting with 2, 4, 6, or 8 followed by 0, 2, 6 or 8 without consecutive duplicates is: 202 206 208 260 262 268 280 282 286 402 406 408 420 426 428 460 462 468 480 482 486 602 606 608 620 626 628 680 682 686 802 806 808 820 826 828 860 862 868.

Your task is to write a program that generates phone numbers according to the rules 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.


by programmingpraxis at August 15, 2017 04:00 AM

August 11, 2017

Programming Praxis

Ruth-Aaron Pairs

We have an exercise today from the realm of recreational mathematics, based on a video from Numberphile. The two numbers 714 = 2 × 3 × 7 × 17 and 715 = 5 × 11 × 13 have, between them, the first seven prime numbers as their factors (baseball fans will understand the name of this exercise, others will have to watch the video). So the first exercise is to find other pairs of consecutive numbers that have as their factors all and only the first n primes, for some n.

Carl Pomerance, the speaker in the Numberphile video, credits one of his students for first noticing that the sums of the prime factors of 714 and 715 are equal: 2 + 3 + 7 + 17 = 5 + 11 + 13 = 29. So the second exercise is to find other pairs of consecutive numbers whose factors sum to the same number. This exercise can be divided into two parts: numbers where repeating factors are added in to the sum and numbers where only the distinct factors are added in to the sum.

Your task is to complete the three exercises; they will make much more sense if you watch the video. 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 August 11, 2017 09:00 AM

August 08, 2017

Programming Praxis

Move Spaces To Beginning Of String

Today’s exercise is a programming interview question from a programmer who very obviously didn’t get the job:

Given a C-style null-terminated string, move all the spaces in the string to the beginning of the string, in place, in one pass.

The candidate claimed it couldn’t be done, and apparently got into an argument with the interviewer, and took to the internet after the interview to vindicate himself about the “unfair question.”

Your task is to either write the requested program, or demonstrate that it cannot be done. 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 August 08, 2017 09:00 AM