Planet Scheme

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

August 04, 2017

Programming Praxis

Last Name Comma First Name

Today’s task is simple:

You are given a file containing one name per line in the format last name comma first name, optionally followed by another comma and a numeral (like Sr., or Jr., or IV), and are convert it to a file containing the names, one name per line, in the format first name, last name and numeral with no commas. You may assume the input is correctly formatted, with optional spaces after each of the two commas.

Your task is to convert a file of names to the correct format. When you are finished, you are welcome to read a suggested solution, or to post your own solution or discuss the exercise in the comments below.


by programmingpraxis at August 04, 2017 09:00 AM

August 01, 2017

Programming Praxis

Find Target In A Matrix

Consider a two-dimensional matrix containing integer entries in which all rows and all columns are sorted in ascending order; for example:

 1 12 43 87
 9 25 47 88
17 38 48 92
45 49 74 95

Your task is to write a program that takes a matrix as describe above, and a target integer, and determines if the target integer is present in the matrix. 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 01, 2017 09:00 AM

July 28, 2017

Programming Praxis

Rerooting A Binary Search Tree

We’ve written about binary search trees on several occasions, most recently here. Binary search trees are a fruitful source of exercises, and we have another one today:

Write a program that takes a binary search tree and a given node of the tree and returns a new binary search tree with the given node at its root, changing as few nodes within the tree as necessary.

Your task is to write a program to reroot a binary search tree. 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 28, 2017 09:00 AM

July 25, 2017

Programming Praxis

Ladder Range

Once a year, or thereabouts, I pick up Jon Bentley’s book Programming Pearls and read a random chapter; even though I’ve read it before, re-reading always makes the material seem fresh. Today’s exercise is Exercise 7 from Chapter 4 about binary search:

A colleague faced the following problem in a program to draw lines on a bit-mapped display. An array of n pairs of reals (ai, bi) defined the n lines y = mi x +
bi. The lines were ordered in the x-interval [0, 1] in the sense that yi < yi+1 for all values of i between 0 and n − 2 and all values of x in [0, 1].

[ Here Bentley has a picture of a ladder with rungs at various angles to the horizontal. We won’t reproduce it here; get the book if you want to see it. ]

Less formally, the lines don’t touch in the vertical slab. Given a point (x, y), where 0 ≤ x ≤ 1, he wanted to determine the two lines that bracket the point. How could he solve the problem quickly?

Your task is to write a program to solve Bentley’s exercise. 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 25, 2017 09:00 AM

July 24, 2017

GNU Guix

State of aarch64 on Guix

Since the recent 0.13.0 release, Guix supports building software for aarch64 (64-bit ARM architecture). Here’s the current status.

Currently aarch64 support in Guix is pretty good, as long as you don&apost mind compiling for yourself :). Potential downfalls are too little RAM (I limited my boards to 2GB minimum) and using an SD card. For building packages I made sure that between RAM and swap I have at least 6 GB, which I don&apost recall giving me any issues.

There were problems with actually building the Guix binary in time for the 0.13 release. It has since been fixed and I have an unoffical aarch64 binary install tarball at http://flashner.co.il/~efraim/. Also there is the signing key for my odroid running guix publish. The URL of my guix publish server is http://git.flashner.co.il:8181.

General problem points/packages:

  • Java is currently out, sablevm-classpath doesn&apost compile, so currently there is no path for Java. A quick check showed about 140 packages depend on sablevm-classpath.
  • Go: go-1.4.x doesn&apost support aarch64 (or mips). I have a patch against our GCC to build gccgo, and it produces a go binary, but it fails to actually build anything. When I checked Debian I saw they cross-compile their arm64 go binary from amd64. I believe there may be an issue with using gccgo and linking against glibc.
  • OCaml 4.01.0: Doesn&apost build on aarch64, haven&apost investigated.
  • Julia: aarch64 is officially supported, but it has only been tested on superpowerful boards, like the ThunderX. I haven&apost gotten it to build yet. The issue is related to __fp16.
  • clisp: our current version doesn&apost build on aarch64, there isn&apost support yet. There are newer builds but no offical release yet, and I haven&apost tested those yet.
  • gprolog: No upstream support and AFAICT no one is working on it.
  • LDC: 1.x is supposed to support aarch64, 0.17.x, aka ldc-bootstrap, doesn&apost, it fails while compiling phobos, which has no aarch64 support in that version.
  • Rust: Has upstream support, our package uses the i686 version as a bootstrap, so only i686 and x86_64 have support in guix ATM.
  • Haskell: There is no upstream aarch64 binary to use for bootstrapping. I&aposm thinking of trying to use qemu-system-x86_64 as the shell and emulate x86_64 on my aarch64 board to cross-compile it to aarch64. guix package -A ghc | wc -l shows 293 packages.
  • Qt 4: does not build, I&aposve hardly put any time into it.
  • Gnucash: The ancient WebKit version they use didn&apost build on aarch64, I haven&apost tried to fix it.
  • Linux-libre: While many boards do require specific patches and versions of the kernel, there have been great increases in recent kernel versions for many ARM boards. It remains to be seen how much support these boards have after the kernel has been deblobbed.

It sounds like its all doom and gloom, but its not too bad. guix package -A | wc -l shows me 5,341 (5,208 without sablevm-classpath), compared with ~5,600 on x86_64. Most of the difference is Haskell. In addition, I personally believe that aarch64 actually has fewer packages that fail to build than armhf.

Currently the project’s build farm lacks aarch64 build machines. If you would like to help, please get in touch with us!

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 Efraim Flashner (guix-devel@gnu.org) at July 24, 2017 01:30 PM

July 21, 2017

Programming Praxis

Length Of A Cycle

Our exercise today is about finding cycles in a linked list. We’ve seen algorithms due to Robert Floyd (the tortoise-and-hare algorithm) and Richard Brent (the power-of-two algorithm) in previous exercises, but in those cases all we were interested in doing was in finding a cycle if it existed. In today’s exercise we want to find the length of the cycle and the list item that begins the cycle (the list item that has two inward pointers).

Your task is to modify both Floyd’s and Brent’s algorithms to find the length and location of a cycle. 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 21, 2017 09:00 AM

July 18, 2017

Programming Praxis

Most Common Item In A Binary Search Tree

Today’s exercise is an interview question:

You are given a binary search tree in which all keys in the left child of a node are less than or equal to the key of the current node and all keys in the right child of a node are greater than or equal to the key of the current node. Find the most common key in the binary search tree. You may use O(n) time and O(1) space.

Your task is to write a program to find the most common node in a binary search tree, subject to the given constraints. 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 18, 2017 09:00 AM

July 14, 2017

Programming Praxis

Nuts And Bolts

Today’s exercise is an interview question from Microsoft:

You are given two bags, one containing bolts and the other containing nuts, and you need to find the biggest bolt.. You may compare bolts to nuts, to see which is larger, but you may not compare bolts to bolts or nuts to nuts. Write a program to find the biggest bolt.

Your task is to write a program to find the biggest bolt. 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 14, 2017 02:00 PM

July 11, 2017

Programming Praxis

My New Programming Environment

I recently purchasd a Lenovo TAB2 A10 tablet computer (who thinks up these horrible names?) with 2GB RAM and a gorgeous 1920 × 1280 screen; the tablet has been on the market for about two years, so it’s no longer cutting edge, but the software is upt to date and the beautiful screen makes up for any deficiency. I bought it as a poor-man’s laptop, intending to carry it with me pretty much everywhere. I’m writing this exercise on my new tablet.

One of the programs I installed from the Google Play Store is GNUroot, which despite its name doesn’t root the tablet; it installs a Unix-like system within the sandbox of a normal Android application. It provides a console that looks like an ordinary Unix console. The sole user is root, with no password; a VNC server is provided if you want to use a graphics screen. The root directory has the normal Unix file structure, with /bin, /usr, /lib, /var, /etc, /home and all the others, and all the normal Unix utilities are present, including apt-get, which lets you install most of the GNU programs.

A simple apt-get install guile-2.0 gave me Guile, the GNU Scheme interpreter, which I’ve been playing with for the last few days. Guile is aggressively R5RS, with lots of extensions and libraries that are inconsistent with R6RS and R7RS; for instance, the module system is completely different. My first impression is good, even though the arguments to (sort list-or-vector lt?) are in the wrong order, and I’ll be exploring the library for the next few days. My .guile initialization file appears on the next page.

So there is no exercise today. You might wish to tell us about your computing environment or ask questions about GNUroot in the comments below.


by programmingpraxis at July 11, 2017 09:00 AM

July 07, 2017

Programming Praxis

Random Number Test

We’ve built several random number generators: [1], [2], [3], [4], [5], [6], [7], [8], [9] (I didn’t realize it was so many until I went back and looked). In today’s exercise we look at a way to test them. There are several well-known random-number testers, including Donald Knuth’s spectral test and George Marsaglia’s diehard test, but our test will be much simpler. Specifically, we test two things:

1) The numbers generated have an equal number of 0-bits and 1-bits.

2) The maximum run of consecutive 1-bits is consistent with probability theory.

Your task is to write a simple random number tester. 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 07, 2017 09:00 AM

July 04, 2017

Programming Praxis

Prime Chains

We studied word chains in a previous exercise; for instance, you can convert HEAD to TAIL by the word chain HEAD, HEAL, TEAL, TELL, TALL, TAIL in which each word differs from its predecessor by a single letter. Today’s exercise is similar, but asks you to find the chain from one prime number to another, with all intermediate numbers also prime, by changing one digit at a time; for instance, the chain 71549, 71569, 71069, 11069, 10069, 10067 converts 71549 to 10067.

Your task is to write a program to find prime chains. 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 04, 2017 07:21 PM