Planet Scheme

December 15, 2017

Programming Praxis

Rotated Palindrome

Today’s exercise provides simple finger exercise for a Friday morning:

A palindrome is a string that reads the same forward and backward; for instance “abcdedcba” is a palindrome. A rotated palindrome is a string that reads the same forward and backward, either directly or in any rotation of the string; for instance, “dedcbaabc” is a rotated palindrome, because if the last three letters at the end of the string are rotated to the beginning of the string, it becomes “abcdedcba” which is a palindrome.

Your task is to write a program to determine if a string is a rotated 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 December 15, 2017 10:00 AM

December 12, 2017

Programming Praxis

Jane’s Homework

Today’s exercise is from user Jane, who needs homework help:

Consider all partitionings of a list of positive integers into two partitions. For each partitioning, compute the sums of the two partitions, then compute the least common multiple of the two sums. Report the maximum of all possible least common multiples. For example, given the list (2 3 4 6), the possible partitionings, the associated sums, and the least common multiples, are:

    () (2 3 4 6) -  0 15 -  0
    (2)  (3 4 6) -  2 13 - 26
    (3)  (2 4 6) -  3 12 - 12
    (2 3)  (4 6) -  5 10 - 10
    (4)  (2 3 6) -  4 11 - 44
    (2 4)  (3 6) -  6  9 - 18
    (3 4)  (2 6) -  7  8 - 56
    (2 3 4)  (6) -  9  6 - 18
    (6)  (2 3 4) -  6  9 - 18
    (2 6)  (3 4) -  8  7 - 56
    (3 6)  (2 4) -  9  6 - 18
    (2 3 6)  (4) - 11  4 - 44
    (4 6)  (2 3) - 10  5 - 10
    (2 4 6)  (3) - 12  3 - 12
    (3 4 6)  (2) - 13  2 - 26
    (2 3 4 6) () - 15  0 -  0

Thus, the maximum least common multiple is 56.

Jane writes that she wants to be able to recursively find all partitions given a list, and she thinks she will have to use lambda in her program.

Your task is to write a program that finds the maximum least common multiple of the part-sums of all possible 2-partitionings of a list of positive integers. 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 December 12, 2017 10:00 AM

December 08, 2017

Programming Praxis

Deletion From A Cyclical List

A cyclical list has no beginning and no end; Chez Scheme writes it like this:

#0=(1 2 3 . #0#)

Your task is to write a program that removes an item from a cyclical list; if the item is not present in the cyclical list, it should remain unchanged. 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 December 08, 2017 10:00 AM

December 07, 2017

GNU Guix

GNU Guix and GuixSD 0.14.0 released

We are pleased to announce the new release of GNU Guix and GuixSD, version 0.14.0! The release comes with GuixSD ISO-9660 installation images , a virtual machine image of GuixSD , and with tarballs to install the package manager on top of your GNU/Linux distro, either from source or from binaries . It’s been 6 months since the previous release, during which 88 people contributed code and packages. The highlights include: The GuixSD installation image is now available as an ISO-9660 image , which can either be written to a USB stick or burnt on a DVD. Previously we would only…

by Ludovic Courtès at December 07, 2017 01:00 PM

December 05, 2017

Programming Praxis

Recursion And Iteration

Today’s exercise is about basic programming techniques.

Your task is to pick a function and write two versions of it, one recursive, the other iterative; compare the two versions on readability, programming ease, speed, and any other criteria that are important 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.


by programmingpraxis at December 05, 2017 02:00 PM

December 01, 2017

Programming Praxis

Replace Exceptions With Defaults

All programming languages provide ways to handle exceptions, and all programs should be careful to handle exceptions properly; it’s good programming practice to keep exceptions from interfering with the normal conduct of your program, and courteous to your users. A good way to handle exceptions is to replace them with default values. Consider this:

> (car '())
Exception in car: () is not a pair
> (try (car '()) #f)
#f

The first exception is unhandled, and displays an error to the user. The second exception is handled, and converts the error to a default value. Replacing exceptions with defaults makes programs more robust.

Your task is to devise a simple system of replacing exceptions with defaults in your favorite 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 December 01, 2017 10:00 AM

November 28, 2017

Programming Praxis

Mirror, Mirror On The Wall

I’m back home from visiting my out-of-town daughter over Thanksgiving. I ate too much. And I am already thinking of Christmas. I intend to give each of my daughters a Magic Mirror built from a Raspberry Pi computer (don’t tell them). I’ve got the electronics working, now I just need to build the frames (it’s harder than I thought it would be). The links above show you what you need to know; here’s another look at a Magic Mirror.

Little computers like the Raspberry Pi are becoming extremely versatile. If you haven’t decided on Christmas presents yet, you might want to look at what a Raspberry Pi can do, and build something fun or useful for someone special to you.

Your task is to tell us about your Raspberry Pi project, or an Arduino project if you prefer. Or you can read about another project I built.


by programmingpraxis at November 28, 2017 10:00 AM

November 21, 2017

Programming Praxis

Floor And Ceiling In An Array

We looked at variants of binary search in two recent exercises. Today we look at a third variant.

Your task is to write a variant of binary search in a sorted array without duplicates that returns the index of the two elements immediately below and above a target; if the target is in the array, both return values should point to the target value. 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 November 21, 2017 10:00 AM

November 17, 2017

Programming Praxis

Casting Out Nines

It doesn’t seem to be taught any more (neither of my daughters have ever heard of it), but casting out nines is a useful computational trick for verifying manual arithmetic calculations. Consider the sum below:

 3074
 6017
13814
 1810
   27
 3611
-----
28353

 

The sum of the digits of 3074 is 14, and the sum of the digits of 14 is 5, so the result of casting out nines from 3074 is 5. The sum of the digits of 6017 is 14, and the sum of the digits of 14 is 5, so the result of casting out nines from 6107 is 5. The number 13814 includes digits 1 and 8, which sum to 9, so we can ignore them and sum the digits 3, 1 and 4, so the result of casting out nines from 13814 is 8. Likewise, the 1 and 8 of 1810 sum to 9, so we ignore them, and the result of casting nines out of 1810 is 1. The digits of the 27 sum to 9, which we cast out, so the result of casting nines out of 27 is 0. Finally, we can cast out the 3 and 6 from 3611, so the result of casting nines out of 3611 is 2. Now the nines results of the six numbers are 5, 5, 8, 1, 0 and 2, and again we cast out the 8 and 1, leaving 12. The sum of the digits of 12 is 3, which is the final result of casting out nines from the addends.

The sum of the digits of 28353 is 21, and the sum of the digits of 21 is 3, so the result of casting nines out of 28353 is 3. Since the addends and the sum have the same result when casting out nines, it is plausible that the sum is correct. If the process of casting out nines yielded different results from the addends and the sum, we could be sure that the sum was incorrect.

Although that formulation sounds complicated, in practice this goes faster than you can think. Consider 28353. The first two digits sum to 10, so cast out a nine and count 1. Then add 3, giving a running nine-sum of 4, and add 5, giving a running nine-sum of 9, which can be cast out. The only remaining digit is 3, which is the result of casting out nines from the sum.

Casting out nines from the addends is even easier, because there are more ways to make nine. From the first two addends, cast out the 3 and 6, then cast out the 7, 4, and 7, leaving 1. Adding the third number gives 0; cast out the 1 and 8 immediately, leaving the 1 carried from the first two numbers, plus 3, 1 and 4, which sums to 9, which is equivalent to 0. Cast out 1 and 8 from the fourth number, leaving 1, cast out the fifth number entirely, and cast out 3 and 6 from the sixth number, leaving the carry of 1 plus the two 1s at the end of the sixth number, for a total of 3.

With a little bit of practice, this becomes ridiculously fast. Your friends will be amazed when you quickly tell them their sum is wrong; they will also hate you.

Mathematically, casting out nines is the same as addition modulo 9. MathWorld gives a good explanation. The process of casting out nines works for multiplication and exponentiation as well as addition.

Your task is to write a program to cast out nines; avoid the temptation to simply take the remainder on division by 9 and do the actual work of summing the digits and casting out nines. 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 November 17, 2017 10:00 AM

November 14, 2017

Programming Praxis

Odd Appearances

Today’s exercise is the kind of interview question that I don’t like. If you know the trick, you look like a genius, and if you don’t know the trick, you don’t get the job:

In an unsorted array of integers, find the one integer that appears an odd number of times. You may use O(n) time and O(1) space. For instance, in the array [4, 3, 6, 2, 6, 4, 2, 3, 4, 3, 3], the number 2 appears 2 times, the number 3 appears 4 times, the number 4 appears 3 times, and the number 6 appears 2 times, so the correct answer is 4.

Your task is to write a program to find the integer that appears an odd number of times. 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 November 14, 2017 10:00 AM

November 13, 2017

Ben Simon

Hop to it - Counting Jumps using a cell phone accelerometer

Last week I was harshly schooled in the difference between theoretical physics and the reality of cell phone hardware. While it may be true that you can calculate distance from acceleration, the hardware on the LG G6 isn't precise enough to do so. But I remain undeterred!

I return instead, to my original and simpler problem: can I use my phone's sensors to determine many jumps have I done in a jump rope session? The accelerometer is clearly one way to approximate this. Just check out the graph below. It shows three bursts of me jumping, with each set of jumps followed by a pause:

The simplest strategy here is to count the peaks of the graph. Swapping out the code to calculate distance with code to do this counting was simple enough. All the code can be found here, but the relevant lines as follows:

;; Counting the peaks in a given accelerometer stream.  This should
;; give us a rough approximation of jumps
(define (count-peaks accum data)
  (let ((lower 0)
 (upper 10)
 (verbose? #t)
 (a-now (+ (data 1) (data 2) (data 3)))
 (rising? (accum 0))
 (num-peaks (accum 1)))
    (cond ((and rising? (>= a-now upper))
    (if verbose?
        (show "peak discovered: " a-now))
    (list #f (+ 1 num-peaks)))
   ((and (not rising?) (<= a-now lower))
    (list #t num-peaks))
   (else
    (list rising? num-peaks)))))

For now, a peak is defined as having total acceleration over 10m/s2. I arrived at this number the way all important mathematical constants are: I stood in my living room and jumped up and down. Set the peak height too low, and simple movements are marked as jump. Set it too high, and not all the jumps are counted.

A smarter approach would be to make this number adaptive, making it somehow dependent on the data set itself. But for now, a constant of 10 seems to work OK.

With this code change, I was able to record a 10 jump data file and run it through tinyscheme:

While this was functional, I was curious if I could streamline running this script. Switching to Termux, then entering the right filename in emacs, and then evaluating the code in the *scheme* buffer was all a bit much.

Fortunately, Termux has the answer: Termux:Task. This is an add on for Tasker that allows you to kick off shell scripts under Termux. The first order of business was to wrap up the scheme code as a shell script. That wasn't hard:

#!/data/data/com.termux/files/usr/bin/sh

SRC_DIR=$HOME/dt/i2x/code/android-accelerometer-playtime/
MAIN_SCM=$SRC_DIR/main.scm

usage () {
    echo "Usage: `basename $0` /path/to/data.csv"
    exit
}

if [ -f "$1" ] ; then
    exec tinyscheme -c "(define *src-dir* \"$SRC_DIR\") (load \"$MAIN_SCM\") (show (count-jumps \"$1\"))"
else
    usage
fi

tinyscheme can be invoked with -c which allows for running arbitrary scheme expressions. I'm using this to initialize and run parameterized code.

From there, I soft linked this script under $HOME/.termux/tasker. This allowed the script to be visible inside of Tasker:

Note the use of %asfile1. This variable is set by AutoShare, a Tasker plugin that lets you kick off actions based on the system sharing menu.

With the Tasker code in place, I can record data in the Physics Toolbox Sensor Suite app, then share that data with the Count Jumps AutoShare command. This kicks off the count_jumps shell script, which invokes tinyscheme and runs my code above. Simple, right? It may be a virtual Rube Goldberg, but it does work, and successfully demonstrates how you can get from an Android App to scheme code with very little effort.

As a final test, here's me knocking out 30 test jumps:

And there you have it, 31 jumps. As approximations go, I'll take it.

by Ben Simon (noreply@blogger.com) at November 13, 2017 07:21 PM

November 10, 2017

Programming Praxis

Ternary Search

We looked at binary search in the previous exercise. Today we look at ternary search. Instead of one mid at the middle of the array, ternary search has two mids a third of the way from each end; two-thirds of the array is discarded at each recursive step.

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


by programmingpraxis at November 10, 2017 10:00 AM

November 07, 2017

Programming Praxis

Binary Search With Duplicates

Most implementations of binary search assume that the target array has no duplicates. But sometimes there are duplicates, and in that case you want to find the first occurrence of an item, not just any one of several occurrences. For instance, in the array [1,2,2,3,4,4,4,4,6,6,6,6,6,6,7] the first occurrence of 4 is at element 4 (counting from 0), the first occurrence of 6 is at element 8, and 5 does not appear in the array.

Your task is to write a binary search that finds the first occurrance of a set of duplicate items in a sorted array. 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 November 07, 2017 10:00 AM

November 03, 2017

Programming Praxis

GCD By Factoring

Regular readers of this blog know that Euclid’s algorithm, dating to 300 B.C., is the standard algorithm for computing the greatest common divisor of two numbers. But middle school teachers have their students calculate the greatest common divisor by factoring the two numbers and taking the product of the prime factors they have in common, being careful to count multiplicities correctly.

Your task is to write a program that calculates greatest common divisors by factoring. 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 November 03, 2017 11:30 AM

November 01, 2017

GNU Guix

Back from GPCE

Last week, I was at GPCE 2017 , an academic conference focused on generative programming techniques. I presented Code Staging in GNU Guix , a paper that discusses the motivation for and genesis of G-expressions as well as recent improvements. The slides are available here . …

by Ludovic Courtès at November 01, 2017 11:00 AM