Planet Scheme

July 20, 2018

Programming Praxis

Fenwick Trees

There are some algorithms in coding theory where cumulative frequency tables must be maintained. This requires two tasks to be performed on an array of integers:

1) Calculate the cumulative sum of the first n elements of the array.

2) Modify the value of an element of the array.

One approach is to maintain an array of the elements, so that an element can be modified in O(1) time but calculating the cumulative sum requires O(n)time. Another approach is maintain an array of the cumulative sumes, so that a cumulative sum can be calculated in O(1) time but modifying a single element of the array takes O(n) time.

A Fenwick tree performs both operations in O(log n) time. The tree is normally embedded in a 1-based array, with the children of node i at nodes 2i and 2i + 1. Each element with index i a power of 2 contains the sum of the first i elements. Each element with index i a sum of two powers of 2 contains the sum of the elements since the preceding power of 2. In general, each element contains the sum of the values since its parent in the tree, found by clearing the least-significant bit in the index. Wikipedia has a good description of Fenwick trees.

For example, to find the sum of the first 1110 = 10112 items in the array, note that 11 has three bits set, so add elements 10002, 10102, and 10112. To modify the 11th element, modify 10112, 11002, 100002, and all higher powers of 2 up to the size of the array.

Your task is to implement Fenwick 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 July 20, 2018 09:00 AM

July 17, 2018

Programming Praxis

Top Heavy Perfect Powers

Over at his blog, Ken is investigating top-heavy perfect powers to investigate increasing the breadth of the Cunningham project. He makes a list of 2413 perfect powers bn with bn in increasing order, up to a googol, omitting bases that are themselves perfect powers (for instance, 4n, 8n or 9n).

Your task is to make a list of the 2413 top-heavy perfect powers less than a googol. 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 17, 2018 09:00 AM

July 13, 2018

Programming Praxis

Data Laundry, Again

Data laundry is the act of cleaning data, as when it arrives in one format and must be translated to another, or when external data must be checked for validity. We looked at data laundry in a previous exercise. We return to it today because I have been doing data laundry all week, handling data from a new vendor. Today’s task is similar to one I have been doing this week; convert the input to the output shown below, changing all appearances of the string ABCDE to an incrementally-numbered string with a prefix:

ABCDE This is some text.
This is more text. ABCDE, ABCDE.
ABCDE And this is [ABCDE] still more text.
X1 This is some text.
This is more text. X2, X3.
X4 And this is [X5] still more text.

Your task is to write a program to perform the data laundry shown 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 July 13, 2018 09:00 AM

July 10, 2018

Programming Praxis

8/10 Palindromes

Sometimes I enjoy browsing oeis.org (I might be a little bit weird). While browsing the other day, I found A029804, the sequence of numbers that are palindromes in both decimal and octal.

Your task is to write a program that writes the sequence of numbers that are palindromes in both decimal and octal. 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 10, 2018 09:00 AM

July 06, 2018

GNU Guix

GNU Guix and GuixSD 0.15.0 released

We are pleased to announce the new release of GNU Guix and GuixSD, version 0.15.0! This release brings us close to what we wanted to have for 1.0, so it’s probably one of the last zero-dot-something releases.

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 7 months (much too long!) since the previous release, during which 100 people contributed code and packages. The highlights include:

  • The unloved guix pull command, which allows users to upgrade Guix and its package collection, has been overhauled and we hope you will like it. We’ll discuss these enhancements in another post soon but suffice to say that the new guix pull now supports rollbacks (just like guix package) and that the new --list-generations option allows you to visualize past upgrades. It’s also faster, not as fast as we’d like though, so we plan to optimize it further in the near future.
  • guix pack can now produce relocatable binaries. With -f squashfs it can now produce images stored as SquashFS file systems. These images can then be executed by Singularity, a “container engine” deployed on some high-performance computing clusters.
  • GuixSD now runs on ARMv7 and AArch64 boxes! We do not provide an installation image though because the details depend on the board you’re targeting, so you’ll have to build the image yourself following the instructions. On ARMv7 it typically uses U-Boot, while AArch64 boxes such as the OverDrive rely on the EFI-enabled GRUB. Bootloader definitions are available for many boards—Novena, A20 OLinuXino, BeagleBone, and even NES.
  • We further improved error-reporting and hints provided by guix system. For instance, it will now suggest upfront kernel modules that should be added to the initrd—previously, you could install a system that would fail to boot simply because the initrd lacked drivers for your hard disk.
  • OS configuration has been simplified with the introduction of things like the initrd-modules field and the file-system-label construct.
  • There’s a new guix system docker-image command that does exactly what you’d expect. :-)
  • There’s a dozen new GuixSD services: the Enlightenment and MATE desktops, Apache httpd, support for transparent emulation with QEMU through the qemu-binfmt service, OpenNTPD, and more.
  • There were 1,200 new packages, so we’re now close to 8,000 packages.
  • Many bug fixes!
  • The manual is now partially translated into French and you can help translate it into your native language by joining the Translation Project.

See the release announcement for details.

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'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, x86_64, ARMv7, and AArch64 machines. It is also possible to use Guix on top of an already installed GNU/Linux system, including on mips64el and aarch64.

by Ludovic Courtès at July 06, 2018 12:00 PM

July 03, 2018

Programming Praxis

Top Five Test Scores

We frequently base exercises on student assignments. Today we have something for the teachers:

A student’s final store is the average of the five best test scores the student achieved during the school term. Given a list of student name/score pairs, determine the final score for each student. You may assume each student has at least five scores.

Your task is to write a program to determine each student’s final score, as 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 July 03, 2018 09:00 AM

June 29, 2018

Programming Praxis

Length

Recently, at a beginning programmer’s forum, I saw a user asking about the function length that finds the length of a list. He gave a simple version of length, then used it find the lengths of two lists and determine which was shorter. He correctly realized that calculating the full lengths of both lists is inefficient if one list is much longer than the other, and he asked if there was a way to run through the lists simultaneously, stopping as soon as it is known which list is shorter.

Your task is to write length and a function to determine which of two lists is shorter; your solution must use recursion. 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 June 29, 2018 09:00 AM

June 26, 2018

Programming Praxis

Next Identical Popcount, Revisited

In a comment on the prior exercise, Richard A. O’Keefe said:

This is just the “next k-subset of 1..n” problem. It is possible to go fairly directly from one popc-k integer to the next. Let the least significant 1 bit be at offset p. If bit(p+1) is 0, set it to 1 and clear bit(p). If bit(p+1) is 1, clear bit(p), set bit(0), advance bits (p+1..msb) to the next integer with k-1 bits.

The algorithm at the top of the page is spectacularly inefficient. Consider the case of 32-bit integers, bit(30) is on, and all the others are off. (k=1) The (next n) algorithm loops about 2**30 times.

Dr. O’Keefe is correct. My solution isn’t very good. In fact, it’s abominable.

Your task is to write a program to solve the next-identical-popcount problem in the manner Professor O’Keefe suggests. 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 June 26, 2018 09:00 AM

June 22, 2018

Programming Praxis

Next Identical Popcount

Today’s exercise is an interview question:

The binary weight of a positive integer is the number of 1-bits in its binary representation. For example, the decimal number 7, which is 111 in binary, has a binary weight of 3. The smallest integer greater than 7 that has the same binary weight as 7 is 11, which is 1011 in binary.

Your task is to write a program that, given a positive integer, finds the next larger integer that has the same binary weight. 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 June 22, 2018 09:00 AM

June 19, 2018

Programming Praxis

Fibonacci Hash

Hash tables are ubiquitous in computing, and we’ve both used and implemented hash tables on several occasions; there is even a hash table implementation in the Standard Prelude. Most hash tables nowadays use the elements of an array as the heads of linked lists that store key/value pairs, so to access (store or fetch) a particular element the procedure is to calculate the hash value based on the key, convert the hash value to an index into the array, and scan down the appropriate linked list until you find the desired item.

The usual way to convert the hash value to an array index is to choose the array size prime, then take the hash value modulo the prime. That can be slow, because the modulo operation requires a division, which is always slow compared to other primitive arithmetic operations. Fibonacci hash replaces the division with multiplication and a shift, which often takes less than half the time.

Fibonacci hash works like this: Choose b the number of bits in an integer, usually either 32 or 64. Then compute 2b ÷ φ, where φ = (1 + √5) ÷ 2 ≈ 1.618; for b = 32 this quantity is 2654435769 and for b = 64 this quantity is 11400714819323198485. Then to compute the array index, multiply the hash value by the quantity shown above, allowing it to wrap around if the product exceeds the integer bounds, and shift right, leaving as many bits as desired. The array size should be a power of 2. Here is an implementation in C:

unsigned long long fibhash(unsigned long long h)
{
return (h * 11400714819323198485ull) >> 54
}

This returns a ten-bit value (since the 64 bit product is shifted right 54 bits) from 0 inclusive to 1024 exclusive, which is used as the index to the array. If you need more bits, just change the size of the shift.

Malte Skarupke describes the theory behind Fibonacci hash, which you should look at, because it includes some neat math; be sure not to miss the linked video from Vi Hart.

Your task is to implement Fibonacci hash in the language of your choice. 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 June 19, 2018 09:00 AM

June 15, 2018

Programming Praxis

Uncouple

Today’s exercise is from a programming textbook:

A couple is two adjacent identical items in a sequence. You are to remove all couples, then process the list recursively to remove any additional couples formed by the removal of the original couples. For instance, given the list {red blue green green blue red yellow}, first remove the green couple, leaving {red blue blue red yellow}, then remove the blue couple, leaving {red red yellow}, and finally remove the red couple, leaving {yellow}.

Your task is to write a program to uncouple a list. 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 June 15, 2018 09:00 AM

June 12, 2018

Programming Praxis

Multiples Of 5

We have today an interview question from Amazon:

Write a program to determine if an integer is a multiple of 5 in O(log n) time complexity. You cannot use the division or modulus operators.

Your task is to solve the Amazon 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.

by programmingpraxis at June 12, 2018 09:00 AM

June 08, 2018

Programming Praxis

Overlap

We have today a simple exercise to spice up your Friday lunch hour:

A range of integers is specified by its endpoints; for instance, the range [19, 25] includes the values 19, 20, 21, 22, 23, 24, and 25. The overlap of two ranges is those values that appear in both; for instance, given the ranges [19, 25] and [22, 30], the overlap is the range [22, 25]. The ranges [19, 25] and [12, 17] have no overlap.

Your task is to write a program that takes the endpoints of two ranges and returns their overlap, or reports that they have no overlap. 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 June 08, 2018 09:00 AM

June 05, 2018

Programming Praxis

Estimating Pi

There’s a nice piece of math (it was either on NumberPhile or 3brown1blue, but I can’t find it again, and in any event it is a well-known equality) that says if you pick two positive integers at random, the odds of them having no common divisors are 6 ÷ π² ≈ 0.61. Let’s test that.

Your task is to estimate π using the formula shown 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 June 05, 2018 09:00 AM

June 01, 2018

Programming Praxis

Exercise 7

This must be somebody’s homework:

You are given an input file containing lines with three pipe-separated fields; the first field is a student number (a positive integer), the second field is a class name (a string), and the third field is the grade the student received for the class (a non-negative integer, no greater than 100):

22|Data Structures|45
23|English|52
22|English|51
26|Data Structures|72
23|Data Structures|61
21|English|81

You are to output a list of class names along with the grade earned by the lowest-numbers student in each class. For instance, given the above data, the output for Data Structures is 45 corresponding to student 22 (with student number lower than 23 or 26, who also took Data Structures) and the output for English is 81 corresponding to student 21 (with student number lower than 22 or 23, who also took English).

Your task is to write a program to produce the requested output. 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 June 01, 2018 09:00 AM