# Planet Scheme

## May 29, 2015

### Programming Praxis

#### Perrin Pseudoprimes

The Perrin Numbers Pn are defined as P0 = 3, P1 = 0, P2 = 2, and Pn+3 = Pn+1 + Pn for n > 2. If Pn (mod n) ≡ 0, then n is most likely prime. Perrin’s formula always reports that a prime number is prime, but sometimes reports a composite number is prime, though seldom: there are only two pseudoprimes, 271441 and 904631, less than a million.

The Perrin sequence A001608 is computed by sequential addition. An individual member of the Perrin sequence can be computed by matrix exponentiation followed by matrix multiplication:

$P_n = \left[ \begin{array}{ccc} 0 & 1 & 0 \\ 0 & 0 & 1 \\ 1 & 1 & 0 \end{array} \right] ^n \left[ \begin{array}{c} 3 \\ 0 \\ 2 \end{array} \right]$

The terms of the Perrin sequence grow exponentially at a rate of 1.32471795, which is known at the plastic number.

The Perrin pseudoprimality test can be implemented using matrix exponentiation followed by matrix multiplication with all operations performed modulo n. Sloane gives a list of Perrin pseudoprimes at A013998.

Your task is to write a function to determine if a number is a Perrin pseudoprime and to find all Perrin pseudoprimes less than a million. 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.

## May 26, 2015

### Programming Praxis

#### Vietnam Snake

Today’s task is to solve a current exercise in recreational mathematics.

The Guardian recently published a math puzzle that is apparently given to third-grade students (eight-year old children) in Vietnam. The puzzle is a graphic in the form of a snake, and the digits 1 through 9 are to be inserted in the nine empty boxes in such a way as to make the formula correct. Although it may not be clear, the colon symbol is used for division, and the normal order of operations is to be preserved, so the formula becomes A + ((13 * B) / C) + D + (12 * E) − F − 11 + ((G * H) / I) − 10 = 66.

Your task is to write a program that generates all possible solutions to the problem. 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.

## May 22, 2015

### Programming Praxis

#### String-Replace

In the previous exercise I needed a string-replace function, and was surprised not to find one in my code library. I quickly wrote a very simple function, noting that it was “awful” because it had quadratic performance.

Your task is to write a string-replace function that has linear time instead of quadratic. 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.

## May 19, 2015

### Programming Praxis

#### Baseball Scores

There is a lot of information available on the Internet, and a lot of APIs that make it readily accessible. Today’s exercise is intended to remind you of that, and to spur you to find out something interesting for yourself.

Your task is to write a program that fetches and displays information from the Internet; I chose to get baseball scores for my beloved Cardinals, but you are welcome to pick some other topic of interest to you. 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.

## May 15, 2015

### Programming Praxis

#### Convert Ratio To Decimal

Our exercise today is an interview question. Like all of our interview questions, it works better if you put some pressure on yourself to simulate the pressure of an interview; so, for today’s exercise you must complete your solution in fifteen minutes:

Given two positive integers, a numerator and a denominator, and a third positive integer, the number of digits, write the decimal ratio of numerator to denominator to the requested number of digits. For instance, given a numerator of 3227, a denominator of 557, and a number of digits of 30, the correct output is 5.793536804308797127468581687612.

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

## May 14, 2015

### GNU Guix

#### GNU Guix 0.8.2 released

We are pleased to announce the next alpha release of GNU Guix, version 0.8.2.

The release comes both with tarballs, which allow you to install it on top of a running GNU/Linux system, either from source or from a binaries, and a USB installation image to install the standalone Guix System Distribution (GuixSD).

The highlights for this release include:

Special thanks go to Luis Felipe López Acevedo, the incredible designer of the new web site and GuixSD logo!

GNU Guix is a functional 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.

## May 12, 2015

### Programming Praxis

#### Fibonacci Search

An interesting variant on binary search is Fibonacci search. Invented by Jack Kiefer in 1953 to find the zeros of a function, and first applied to searching in an array by David Ferguson in 1960, its initial appeal was to improve locality when searching for a record on magnetic tape. It was later applied to searching on paged memory when it was expensive to read a segment of an array from disk, and it is now used to improve locality of cache memory; a good idea never goes away! Here is a description of Fibonacci search, taken from Wikipedia:

Let Fk represent the k-th Fibonacci number where Fk+2=Fk+1 + Fk for k>=0 and F0 = 0, F1 = 1. To test whether an item is in a list of n ordered numbers, proceed as follows:

1) Set k = m, where Fm is the smallest Fibonacci number greater than or equal to n.
2) If k = 0, halt and report failure.
3) Test item against entry in position Fk-1.
4) If match, halt and report success.
5) If item is less than entry Fk-1, discard entries from positions Fk-1 + 1 to n. Set k = k – 1 and go to 2.
6) If item is greater than entry Fk-1, discard entries from positions 1 to Fk-1. Renumber remaining entries from 1 to Fk-2, set k = k – 2 and go to 2.

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

### GNU Guix

#### GNU Guix talk at OpenTechSummit, Berlin, May 14th

Ricardo Wurmus will be giving a talk about GNU Guix and GuixSD at the OpenTechSummit in Berlin, Germany, on May 14th. The talk will take place at 3:15pm in track 2 and covers topics such as the fundamentals of functional package management, software management features with GNU Guix, and system description in GuixSD.

Ricardo has been making major contributions to Guix over the last year and is a long-time free software contributor. If you are in Berlin area, do not miss the talk!

GNU Guix is a functional package manager for the GNU system. The Guix System Distribution (GuixSD) is an advanced distribution of the GNU system that relies on GNU Guix.

In addition to standard package management features, Guix supports transactional upgrades and roll-backs, unprivileged package management, per-user profiles, and garbage collection. It also offers a declarative approach to operating system configuration management. 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.

At this stage the Guix System Distribution 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.

## May 08, 2015

### Programming Praxis

#### Monkeys And Coconuts

We have today a famous puzzle:

Five sailors are shipwrecked on a desert island. They quickly determine that the only other inhabitant of the island is a monkey and that the only food is coconuts. They set about collecting as many coconuts as they can and put them all in a pile. By nightfall they are too tired to divide the harvest; so they agree to go to sleep and divvy up the coconuts the next morning.

During the night one sailor awakens, suspicious that the others might try to cheat him, and desides to take his portion then and there and not wait until morning. He divides the coconuts into five piles and finds there is one coconut left over, which he gives to the monkey. He hides one of the five piles, then puts the rest of the nuts together and returns to sleep. About an hour later a second sailor awakens with the same suspicions and does the same thing: He divides the coconuts into five piles, leaving one extra, which he gives to the monkey. Then he hides what he thinks is his share and goes back to sleep.

One after another the rest of the sailors do the same: they each take one fifth of the coconuts in the pile (after giving the extra one to the monkey) and then return to sleep.

When the sailors awaken the next morning they all notice the coconut pile is much smaller than it was the night before, but since each man is as guilty as the others, no one says anything. They divide the coconuts (for the sixth time), but this time there is no coconut left for the monkey.

How many coconuts were in the original pile?

Your task is to determine how many coconuts were in the original pile; first solve the problem for 5 sailors, then again for 6 sailors, and finally for 30 sailors. 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.

## May 05, 2015

### Programming Praxis

#### Degrees To Radians To Degrees

I saw this question on a beginning programmer’s forum a couple of weeks ago. There were several answers, some of them wrong. So we’ll do it right:

Given an angle expressed in degrees, minutes, and seconds, convert it to radians. Given an angle in radians, convert it to degrees, minutes and seconds.

Your task is to write programs that perform the two conversions. 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.

# Racket is “King of the Hill” on Rosetta Code

This announcement is a follow up to “800!”.
In it I said we’d "[S]ee you at 1000!"; but you’ll understand why we stopped at this milestone.
Please read that article if you need an introduction to Rosetta Code, and the efforts being made to implement Racket tasks there, and more detail on how you can help. It is more instructive and less braggart than this post.

On Rosetta Code (RC), early in the morning on April 29th, Racket drew level with Tcl in the number of tasks that had been implemented for it. Shortly after that we could announce that:

Racket has the Most Tasks Implemented in Any Language on Rosetta Code!

Before I go into too much detail, it must be said that this is another amazing achievement. I, and I’m sure the rest of the Racket community, want to thank and congratulate everyone who has contributed to this effort.

## How Did This Happen?

On the front page of RC’s site, it states its goal as:

.. to present solutions to the same task in as many different languages as possible, to demonstrate how languages are similar and different, and to aid a person with a grounding in one approach to a problem in learning another.

As well as achieving these comparative goals, implementing tasks also provides a useful library of tools, applications and examples for Racket users themselves. Therefore, doing so is a laudable activity in its own right. The persistent effort and progress have been made by Racketeers on RC, both before and since the “800!” tasks post has been (mostly) performed in that spirit. And that should be plenty enough incentive for you to do so, too.

But I admit, there is a competitive element that creeps in (affecting some more than others). After having passed the 800 task mark… after spending so much time in second place… to get past the current leader, Tcl… to stay ahead of Python1… these, too, provide plenty of motivation to implement tasks. And if winning isn’t important, why, then, do we keep score?

And in that spirit, early in the morning on April 29th, I was busily cherry-picking2 tasks on Rosetta Code to help close the gap with Tcl; when I thought I would take a quick check on Tcl’s and Racket’s task counts3. From what I could see, both had a task count of 845! Racket had drawn level with, Tcl as the Joint Most Popular Programming Language on RC.

I got the independent verification of this from the #racket IRC Channel4. It was true! But Racket was only joint first. This point was not lost on the denizens of IRC (zedoary being one); who posted two more tasks in very quick succession, bringing Racket up to 847 — two clear of the previous leader!

## How does this Help Racket?

### Plenty of Examples

Look back at the intentions of Rosetta Code itself. It is expected that users of other languages can come and compare what they know with what Racket provides. Strictly speaking, of course, in a lot of cases they won’t be able to compare since the other language won’t be represented whereas Racket will.

There is also, now, a large collection of Racket examples, which Racketeers themselves can use to improve their understanding of Racket. Strangely, this is not actually one of the stated objectives of RC; it is a welcome side-effect of the work.

Advocates of Racket can use this position on Rosetta Code to show that Racket is as, if not more, capable than any language. Especially for general purpose computing.

Additionally, I would like to point out that whatever any of the other languages (or tasks) seem to throw at it, there is something in Racket that allows it to take it in its stride. Sometimes the implementations have had high line counts5; but they rarely, if ever, seem contrived.

If you need to provide reasons for tasks not being implemented in Racket, here are a few you can use:

• Nobody has implemented them “yet”: let it be known that we’ve done the best part of 850 tasks, and there are only so many hours in the day.
• Someone has written an FFI for Tcl to an obscure library: The task for Tcl has then simply been to load the FFI. The task for Racket is either to a) implement the library, which is much more effort than Tcl put in or b) to produce FFI bindings itself, which after the first time doesn’t bring much to the party. The same holds true for tasks written for languages which are basically DSLs, showing off how they work in domain for which they are specific.
• The task is written and documented entirely in Russian: This makes translating it an “exercise.”

## Is it Time to Rest on our Laurels?

That was a rhetorical question.

There are many reasons to continue to work on Rosetta Code.

### We Haven’t Finished

There are 922 tasks on Rosetta Code. 849 are implemented in Racket (more have been added as we speak)! Even excluding the impossible and Russian tasks, that’s still many more tasks to implement.

Some tasks are old, and lack style. Some may even be re-branded Scheme tasks. Anyone can edit these tasks. Add style to them. Tasks can then not only be an example of how to use the syntax and features of Racket, but also exemplars of well-written code.

There are things that Racket and other Lisps do well that haven’t been illustrated on RC. How about the fancier macro facilities that Racket provides?

I’m sure you can think of something. Might you suggest something involving anaphoric macros?

Oh, and if you do suggest something, maybe you can implement it, too!

### They Haven’t Finished

#### New Tasks are Being Invented!

Tasks are being added to Rosetta Code constantly. Keep an eye out, some of these are really quite interesting.

Tcl and Python (and maybe others in the future) will want what we have earned here, and they are going to continue to propose and implement tasks. “King of the Hill” is a precarious place. The more clear blue water between us and them… Just do it!… Buy glucose sports drinks…

Maybe I am getting too competitive.

## Finally

Once again, many thanks to the people who have contributed to Racket on Rosetta Code. Including those who have answered questions on the mailing list or IRC. Your help has been invaluable even if the questions made you wonder “why on earth does he or she want to do that?

Finally, but certainly not least: Thanks to the folk at Rosetta Code. They’ve provided a site and experience which have been instructive, educational and fun; and without whom none of this would have been possible.

1. Python, is also doing magnificently well, to be sure. It even had the audacity to draw level with Racket according to the FUPPLR a couple of times.

2. A good way to start on Rosetta Code is to find tasks that are easy to implement. In order to find easy tasks you will need to browse the unimplemented tasks (and maybe some implemented ones, too) and decide what you could either implement and/or translate without breaking too much of a sweat. In the process you will also develop a sense of what tasks are out there ready to be implemented. A good example of an easy task would have been Pentagram

3. There is a Frequently Updated Popular Programming Languages Report, which I refer to but recently it has been miscounting tasks, and needs a bit of a look at.

4. The #racket IRC channel is a fantastic community if you need support with your Racket issues

5. Remember that Rosetta Code is not a Golf site. If it were, J’s weird 20-character-strings-that-do-anything (if only you could remember what they do 30 seconds after you’ve written them) would win hands down. Keep to the Style Guide as best you can. And since RC is a wiki, if you’re not perfect, others can improve the style of your code.

## May 02, 2015

### GNU Guix

#### GNU Guix welcomes three students for GSoC

GNU Guix got 3 slots for the Google Summer of Code (GSoC), as part of GNU, which participates as an organization. So we are pleased to welcome three students this summer:

All three projects have very exciting prospects and we are thrilled to get them started! We are also glad that this allows us to strengthen ties with several other GNU packages.

GNU Guix is a functional package manager for the GNU system. The Guix System Distribution (GuixSD) is an advanced distribution of the GNU system that relies on GNU Guix.

In addition to standard package management features, Guix supports transactional upgrades and roll-backs, unprivileged package management, per-user profiles, and garbage collection. It also offers a declarative approach to operating system configuration management. 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.

At this stage the Guix System Distribution 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.

## May 01, 2015

### Programming Praxis

#### Collatz Primes

Today’s exercise comes from the world of recreational mathematics; I found it at Stack Overflow:

The Collatz sequence starting at n continues with n / 2, if n is even, and 3 n + 1 if n is odd. For instance, the Collatz sequence that starts from 19 is 19, 58, 29, 88, 44, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1. It is conjectured that all Collatz sequences eventually end at 1, but has never been proven. The Collatz sequence that starts from 19 contains 7 prime numbers: 19, 29, 11, 17, 13, 5 and 2. Find the smallest starting number for a Collatz sequence that contains 65 or more primes.

Your task is to find the requested Collatz sequence. 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.

## April 28, 2015

### Programming Praxis

#### Identifying Anagrams

Two words are anagrams if they consist of the same letters, with the same number of occurrences, in a different order. For instance, DEPOSIT and DOPIEST are anagrams (aren’t you glad you know that), and OPTS, POTS, TOPS and STOP form an anagram class.

Your task is to write a program that takes two strings as input and determines whether or not they are anagrams; you may assume that the strings consist of only the letters A through Z in upper case. You must provide at least two different algorithms that work in fundamentally different ways. 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.

## April 24, 2015

### Programming Praxis

#### Minimum Impossible Sum

We have today another from our inexhaustible list of interview questions:

Given a list of positive integers, find the smallest number that cannot be calculated as the sum of the integers in the list. For instance, given the integers 4, 13, 2, 3 and 1, the smallest number that cannot be calculated as the sum of the integers in the list is 11.

Your task is to write a program that solves the interview question. 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.