## Fetch OEIS Sequences

### May 21, 2019

I needed to fetch several sequences from the OEIS the other day. We’ve done that in a previous exercise, in Scheme, but I wanted something I could run from the command line. So I wrote a program.

Your task is to write a program, called from a normal shell command line, that fetches a sequence from OEIS. 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.

## Is This Insane?

### May 17, 2019

[ I’ve been very busy at work this week, and don’t have time to write a proper exercise. My apologies. ]

I stumbled across Twitter account ed1conf that included this method of collaborating with another user on an `ed(1)`

session:

Have two ed(1) sessions open concurrently and want to easily transfer lines between them? $ ed -p"a)" a.txt in another shell $ mkfifo fifo $ ed -p"b)" b.txt then a) 15,21 w fifo then b) 13r fifo Can reuse the same fifo bidirectionally. Finally !rm fifo

I’m not sure if that’s brilliant or insane! Actually, I’m not even sure if a whole Twitter account devoted to `ed(1)`

is brilliant or insane.

Perhaps you would like to share with us some other examples of brilliant insanity.

## The Rat Eats The Cheese

### May 14, 2019

A square maze contains cheese wedges on some of its squares:

· · · 🧀 · · · · · · · 🧀 · 🧀 🧀 · · 🧀 · 🧀 · · · · ·

[ Did you know there is a cheese-wedge character in Unicode? I didn’t. The center-dot is & # 183 ;, the cheese is & # 129472 ;, and I had to sprinkle in a few & thinsp ; characters to line things up. And of course to type those I had to add extra spaces, because WordPress is aggressive about turning them into characters. ]

A rat, starting at the lower left-hand corner of the maze, can move only up or right. What is the maximum amount of cheese the rat can eat?

Your task is to write a program to determine how much cheese the rat can eat. 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.

## Common Characters

### May 14, 2019

Today’s exercise comes from a coding challenge site:

Given a list of words containing only lower-case letters, return a list of characters that appear in all the words, with multiplicity. For instance, given the words BELLA, LABEL and ROLLER, the characters E, L and L appear in all three words.

Your task is to return a list of characters that appear in all words of an input 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.

## The Recamán Sequence

### May 10, 2019

I’ve been watching Numberphile again, specifically their episode about the Recamán sequence 0, 1, 3, 6, 2, 7, 13, 20, 12, 21, 11, … A005132, defined as follows:

The Recamán sequence is an integer sequence

RwithR_{0}= 0 andR_{n}=R_{n−1}−nifR_{n}=R_{n−1}−nis positive and not already in the sequence andR_{n−1}+notherwise.

Your task is to write a program that generates the Recamán sequence; use your program to compute *R*_{1000000} (the one-million-and-first element). 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.

## Identifying Squares, Revisited

### May 7, 2019

Some algorithms require the ability to rapidly identify numbers such as 36 and 121 that are squares; for instance, in Fermat’s factoring algorithm, and variants derived from it, identifiying squares is the performance bottleneck of the procedure. A naive program computes the integer square root of the target number, squares it, and reports a square if it is equal to the original target:

def isqrt(n): if n < 1: return 0 u, s = n, n+1 while u < s: s = u t = s + n // s u = t // 2 return s

def isSquare(n): # naive s = isqrt(n); return s*s == n

(We are using Python instead of Scheme for this exercise because bit-operators like `&`

are easier to type than functions like `bitwise-and`

.)

This is very slow because the calculation to compute the integer square root takes a long time. In a previous exercise, we looked at a method for reducing the number of integer square roots that need to be computed:

def isSquare(n): # fenderbender m = n & 127 if ((m*0x8bc40d7d) & (m*0xa1e2f5d1) & 0x14020a): return False largeMod = n % (63*25*11*17*19*23*31) m = largeMod % 63 if ((m*0x3d491df7) & (m*0xc824a9f9) & 0x10f14008): return False m = largeMod % 25 if ((m*0x1929fc1b) & (m*0x4c9ea3b2) & 0x51001005): return False m = 0xd10d829a * (largeMod % 31) if (m & (m+0x672a5354) & 0x21025115): return False m = largeMod % 23 if ((m*0x7bd28629) & (m*0xe7180889) & 0xf8300): return False m = largeMod % 19 if ((m*0x1b8bead3) & (m*0x4d75a124) & 0x4280082b): return False m = largeMod % 17 if ((m*0x6736f323) & (m*0x9b1d499) & 0xc0000300): return False m = largeMod % 11 if ((m*0xabf1a3a7) & (m*0x2612bf93) & 0x45854000): return False s = isqrt(n); return s*s == n

This is wicked fast because it computes residue classes based on small primes and quickly identifies numbers that cannot possibly be a square; fenderbender eliminates the expensive square root calculation in 99.92% of cases. But all those magic numbers make the function wicked, as well as wicked fast, and it is easy to make an editing error when copying the function to a new program (you will quickly and accurately guess how I know that).

Your task is to write a program that quickly identifies squares without all the magic numbers. 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.

## Three Homework Problems

### May 3, 2019

The end of the school year is approaching in many places, and students are submitting their final homework assignment, so they ask questions on the internet. Here are three questions I have seen recently:

- Write a function
`adjoin-set`

that given a set of integers stored in a linked list in increasing order, and an integer to be inserted in the set, adjoins the integer to the set if it is not already in the set and returns the updated set. - Write a function
`list-index`

that finds the index within a list where a given item occurs, or returns -1 if the item is not in the list. - Write a function
`update-count`

that takes a list of key/count pairs and a key and increments the count of the given key, or adds a new key/count pair with count = 1 if the key is not present in the list.

Your task is to solve the three problems posed 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.

## Hash Tables With Open Addressing

### April 30, 2019

We have studied hash tables in several previous exercises, most of them of the “chaining” variety, where collisions are resolved by inserting each item in a linked list in the bucket to which it hashes. Today’s exercise looks at two different varieties of hash tables that use “open addressing,” in which all keys are stored in the buckets themselves, one key per bucket, with collisions resolved by moving them to a different bucket. We studied one type of open addressing in the exercise on cuckoo hashing, today we will see two others: linear probing and double hashing. Our hash tables consist of *M* memory addresses that hold *N* keys (or key/value pairs). Obviously, *N* must be less than *M*, and the load factor *N* *M* is critical to the performance of the algorithm; if the table becomes too loaded, search times increase dramatically. Open address hash tables work best when *N* can be predicted with some reliability, so an appropriate *M* can be chosen.

The linear probing algorithm hashes the key onto the range 0 .. *M*−1 and looks first in the indicated bucket. If the key is there, it is returned. If the bucket is empty, the key is not present in the table. If the bucket is non-empty, but the key doesn’t match, the search goes to the next bucket in order, wrapping around at the end of the table. Double hashing is similar, except that a second hash function determines the increment between probes. When double hashing, we must arrange that the increment is non-zero (otherwise the search will never visit any bucket except the first) and is co-prime to *M* (otherwise some buckets will never be visited), which is most easily arranged by making *M* prime.

Deletions require some care. We can’t just mark a bucket available when its key is deleted, because subsequent searches will miss keys that are beyond the newly-empty bucket. Instead, we mark the bucket with a special value showing that it is deleted, and consider that bucket to be non-empty but with a key that never matches.

Your task is to implement hash tables using linear probing and double hashing. 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.

## Common Words

### April 26, 2019

Today’s exercise comes from Stack Overflow:

Given a text file like:

word1 word2 word3 word4 word4 word5 word6 word7 word6 word7 word8 word9 word9 word6 word8 word3 word1 word4 word5 word4Write a program that returns those lines that have

nwords in common with the previous line. For instance, given the input above, the only output line would be:word9 word6 word8 word3

The original question requested a solution in sed or awk, but you are free to use any language.

Your task is to write a program to extract lines from a text file that have *n* words in common with the previous line. 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.

## Triperfect Numbers

### April 23, 2019

We have another exercise today based on a Numberphile video:

A perfect number is a number

nthat is equal to the sum of its divisors, excluding itself; in other words, a perfect numbernsatisfies the equation σn= 2n, where σ is the divisor-sum function. A triperfect number is a numbernsuch that σn= 3n. It is believed that there are six, and only six, triperfect numbers.

Your task is to compute the six triperfect numbers. 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.