Programming Praxis

Today’s problem must be someone’s homework from an algorithms course; it makes a fine opportunity for some code golfing:

An array of positive integers represents the heights of a series of buildings; for instance, the array [1, 4, 3, 2, 3, 1] represents the six buildings that, placed in a row, look like this:

     XXX
     XXX  XXX       XXX
     XXX  XXX  XXX  XXX
XXX  XXX  XXX  XXX  XXX  XXX

A painter drawing a picture of the buildings paints the buildings by making a single horizontal brush stroke from left to right as far as possible, working from bottom to top. The first stroke covers the first floor of all six buildings. The second stroke covers the second floor of four buildings. The third stroke covers the third floor of two buildings, and the fourth stroke covers the third floor of one building. Finally, the fifth stroke covers the fourth floor of one building. The painter requires five brush strokes to cover all six buildings.

Your task is to write a program that takes an input array representing building heights and calculates the number of horizontal brush strokes required to cover all floors on all buildings. 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.

Pages: 1 2

[ I apologize for posting this exercise on Wednesday morning instead of Tuesday morning. I got mixed up because of the three-day holiday weekend. ]

I recently came across the logistic map which is an example of how complex, chaotic behavior can arise from simple non-linear equations. The logistic map is written

x_n+1 = rx_n (1 − x_n

where 0 < x_n < 1 represents the ratio of the existing population to the maximum possible and 0 < r < 4 represents the stability in the model of population density. I can't do the logistic map justice here; look at the Wikipedia page and follow the references it gives for a fascinating introduction to chaos theory.

Your task is to write a program that computes sequences of the logistic map, and experiment with it. 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.

Pages: 1 2

A few days ago I answered this question on Stack Overflow:

Divisors of 42 are : 1, 2, 3, 6, 7, 14, 21, 42. These divisors squared are: 1, 4, 9, 36, 49, 196, 441, 1764. The sum of the squared divisors is 2500 which is 50 * 50, a square!

Given two integers m, n (1 ≤ m ≤ n) we want to find all integers between m and n whose sum of squared divisors is itself a square. 42 is such a number.

The result will be an array of arrays, each subarray having two elements, first the number whose squared divisors is a square and then the sum of the squared divisors.

Your task is to solve MrOldSir’s problem; he asked for a solution in Python, but you are free to use any 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.

Pages: 1 2

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.

Pages: 1 2

[ 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.

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.

Pages: 1 2

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.

Pages: 1 2

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 R with R₀ = 0 and R_n = R_n−1 − n if R_n = R_n−1 − n is positive and not already in the sequence and R_n−1 + n otherwise.

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.

Pages: 1 2

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.

Pages: 1 2

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:

1. 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.
2. 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.
3. 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.

Pages: 1 2