## Element Words

### April 14, 2017

Today’s exercise is either an interview question or somebody’s homework, I’m not sure:

Given a list of all the symbols of the chemicals in the periodic table, and a list of all the words in the English language, find the longest word that can be made using symbols of the chemicals in the periodic table.

Your task is to write a program to find the longest word that can be formed from the periodic table. 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.

## Sort Four

### April 11, 2017

Today’s exercise involves sorting:

Write a program that takes exactly four items as input and returns them in sorted order.

Your task is to write a program that sorts exactly four items; can you do it using only five comparisons? 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.

## Edit Files In A REPL

### April 7, 2017

Many programming languages are interactive, with their primary interface a read-eval-print loop. Scheme is like that, so is Python, and so is the primary language I use in my day job, Oracle SQL*Plus, and so too are many other languages.

One feature many of those languages share is a way to edit files from the REPL. For instance, in SQL*Plus, the most recently-entered command is available in a buffer, and if you say “edit” the buffer will be loaded into whatever $EDITOR you specified, so you can modify the command as needed; when the editor returns, the modified buffer is then executed.

Although Scheme doesn’t provide such an editing feature, I have been using my own for years. It’s very simple, less than a dozen lines of code, and greatly enhances my productivity.

Your task is to write an editing interface for your favorite REPL. 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.

## Double Space

### April 4, 2017

Today’s exercise is simple, but some languages make it hard:

Write a program that returns an input string with each space character in the string doubled. For instance, the string “hello hello” (with one space between the two words) is transformed to “hello hello” (with two spaces between the two words).

That may not come out right in all browsers; here is the transformation again, with space characters replaced by plus signs for visibility, using a constant-space font:

"hello+hello" => "hello++hello"

Depending on your language, that might be an easy task, or a hard one. You may have to deal with memory allocation, or non-mutable strings, or appends that blow up to quadratic time.

Your task is to write a program that doubles the space characters in its input. 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.

## Generating Random Large Primes

### March 31, 2017

Sometimes you need to have a large prime, for testing, cryptography, or some other purpose. I’m talking about primes of several hundred to a few thousand digits that are *certified* — proven to be prime — rather than *probable* primes according to a Miller-Rabin or other probabilistic test. Henry Pocklington’s Criterion, which dates to 1914, gives us a way to find such primes quickly. Paulo Ribenboim explains it thus:

Let

pbe an odd prime, and letkbe a positive integer, such thatpdoes not dividekand 1 <k< 2(p+ 1). LetN= 2kp+ 1. Then the following conditions are equivalent:

Nis a prime.- There exists an integer
a, 1 <a<N, such thata^{(N−1)/2}≡ −1 (modN) and gcd(a+ 1,^{k}N) = 1.

This gives us an algorithm for generating large certified primes. Choose *p* a certified prime. Choose 1 ≤ k < 2 × *p* at random; we ignore the last two possibilities for *k*, so we don’t have to worry about *k* being a multiple of *p*. Compute *N*. For each *a* ∈ {2, 3}, test the conditions for primality. If you don’t find a prime, go back and choose a different random *k*. Once you have a prime *N*, “ratchet up” and restart the process with the new certified prime *N* as the *p* of the next step. Continue until *N* is big enough.

Your task is to write a program that generates random large primes. 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.

## RNG147

### March 28, 2017

We have looked at random number generators in several previous exercises, but most of them returned integers. In today’s exercise we look at a simple random number generator that returns floating-point numbers. The generator is simple: Given a seed between zero and one, the next number in the sequence is the fractional portion of 147 times the seed.

Your task is to implement the random number generator described above, and to assess its suitability. 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.

## Symbolic Differentiation

### March 24, 2017

One of the original motivations for the Lisp language was to write a program that performed symbolic differentiation. In this exercise we look at the symbolic differentiator in Section 2.3.2 of SICP, which handles expressions containing only addition and multiplication according to the following rules:

, with ,

,

, and

.

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

## Word Sets, Solved

### March 21, 2017

I completed the solution to the previous exercise, which you can look at if you wish. We’ll have a new exercise on Friday.

## Word Sets

### March 17, 2017

Today’s exercise is an interview question;

Given a list of words and a set of characters, determine which words in the list can be formed from the given characters. For instance, given the characters

a,candt, the wordsactandcatcan be formed, but not the wordstop.

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

## Square Pyramidal Numbers

### March 14, 2017

Cannonballs are traditionally stacked in a pyramid with a square base. A stack with a square base of 15 cannonballs has 15 × 15 = 225 on the bottom level, 14 × 14 = 196 on the level above that, and so on, a total of 1240 cannonballs.

Your task is to write a program to compute the number of cannonballs in a stack; use it to compute the number of cannonballs in a stack with a base of 1,000,000 cannonballs on a side. 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.