Programming Praxis

Three physicists recently published an article showing that an inert iron bar is capable of making decisions. They attach the bar between two slot machines, repeatedly play one of the machines, pull the bar toward the machine when it winds and push the bar away from the machine when it loses. After enough plays, the iron bar can decide whether to play one machine or the other in hopes of a better payoff. Then they say “The most important implication that we wish to claim is that the proposed scheme will provide a new perspective for understanding the information-processing principles of certain lower forms of life.” The physicists also claim the iron bar can determine the probabilities of winning on both slot machines even though it only plays one. I’m not sure I understand the article, though I will happily agree that an inert iron bar has more intelligence than the spammers that regularly bedevil my blog.

The iron bar recalls an old-time method for calculating the median of a stream; for instance, consider finding the median of a list of a thousand occurrences of the numbers 1 to 100. Initialize the median to the first number in the list. Then, at each subsequent number, increase the median by 1 if the number is higher than the current median and decrease the median by 1 if the number is lower than the current median. At the end of the list, the approximate median calculated in this way ought not to significantly differ from the actual median. This is essentially the same calculation as that of the iron bar.

Your task is to write a program that calculates approximate medians in the manner of an iron bar. 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 recent article in the Wall Street Journal discusses the “hot hand” paradox. Basketball players especially believe in the hot hand, when making a shot you can suddenly have a hot hand and make several more shots in a row. The Wall Street Journal proposes this experiment:

Toss a coin four times. Write down the percentage of heads on the flips coming immediately after heads. Repeat that process one million times. On average, what is that percentage?

The article claims that the correct percentage is 40%, not the 50% that you would expect from an unbiased coin, and that this is proof that the hot hand exists, even from such a random source as coin flips. If you’re interested, you can read the academic article that the Wall Street Journal account is based on, or see discussion of it at Hacker News.

Your task is to write a program to confirm the 40% figure. 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

We have today a small exercise in string manipulation: Given an input string, either return a string containing the same characters but arranged to form a palindrome, or indicate that no such rearrangement is possible.

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

Pages: 1 2

As regular readers know, I greatly enjoy problems at the intersection of recreational mathematics and number theory. Today’s exercise is an example of that.

As was known to the ancient Greeks, perfect numbers such as 6 and 28 are equal to the sum of their aliquot divisors (those divisors less than the number itself); for instance, 6 = 1 + 2 + 3 and 28 = 1 + 2 + 4 + 7 + 14. Mathematicians refer to these as P₂ numbers the sum of the divisors, including the number itself, is twice the number.

Multiply perfect numbers are numbers such that the sum of their divisors are some multiple of the number; perfect numbers have divisor-sums twice the number, triply perfect numbers P₃ have divisor-sums thrice, the number, and so on.

Your task is to write a program that finds multiply perfect 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

I can tell from my statistics that people like the homework problem exercises, I suppose because they are short and provide simple drill. I can also tell, from reading some of the beginning-programmer message boards, that students seem to be quicker that they used to be to post their homework problems on-line rather than figuring out the solutions themselves, either because they are lazy or because their teachers aren’t providing sufficient help. So today we have three more homework problems:

1) Given a list of integers, return a list in which all the duplicates have been removed. For instance, given the input list [3, 2, 4, 2, 7, 3, 5, 1, 3] return the output list [3, 2, 4, 7, 5, 1].

2) Given two lists of integers, each sorted in ascending order, return a list of the integers common to the two lists; the output list must also be in ascending order. For instance, give the input lists [2, 3, 5, 5, 6, 7, 8, 9] and [1, 2, 4, 5, 5, 7] return the output list [2, 5, 5, 7].

3) Given a positive integer, determine if it is a perfect cube. For instance, the integer 125 is a perfect cube, 5*5*5, but the integer 121 is not.

Your task is to write programs that solve the three homework problems. 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

We have three simple exercises today to help beginning programmers with their homework; all three exercises have appeared on beginning-programmer forums in the last week:

1) Write a recursive function to find the sum of the first n odd integers. For instance, if n = 2, the first two odd integers are 1 and 3, and their sum is 4.

2) Write a function to count the frequence of characters in a string. For instance, given the string “hello” the function should return counts of 1, 1, 2 and 1 for h, e, l and o.

3) Write functions that encrypt and decrypt messages in a Caesar cipher. Input consists of upper-case letters and spaces; the “key” is an integer giving the number of letters to shift. For instance, the message ATTACK AT DAWN with a shift of 5 is enciphered as FYYFHP FY IFBS.

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

Pages: 1 2

The Standard Prelude provides functions julian and gregorian for performing date arithmetic. In today’s exercise we will extend those functions to provide arithmetic on times as well. The parameters provided to julian will be year, month, day, hour, minute, and second, and the same parameters will be returned by gregorian.

Your task is to write the new julian and gregorian functions. 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 median of an array is the value in the middle if the array was sorted; if the array has an odd number of items n, the median is the (n+1)/2’th largest item in the array (which is also the (n+1)/2’th smallest item in the array), and if the array has an even number of items n, the median is the arithmetic average of the n/2’th smallest item in the array and the n/2’th largest item in the array. For instance, the median of the array [2,4,5,7,3,6,1] is 4 and the median of the array [5,2,1,6,3,4] is 3.5.

Your task is to write a program that takes an array of 8-bit integers (possibly but not necessarily in sort) and finds the median value in the array; you should find an algorithm that takes linear time and constant space. 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

Pierre de Fermat issued these two challenges in 1657: First, find a cube that, when increased by the sum of its aliquot divisors, becomes a square; for instance, 7³ + (1 + 7 + 7²) = 20³. Second, find a square that, when increased by the sum of its aliquot divisors, becomes a cube. I would guess that Fermat knew the answer to the first challenge but not the second.

In the days before computers, challenges such as this were frequently issued by one mathematician or group of mathematicians to their competing colleagues; for instance, the French mathematicians might challenge the German mathematicians. Once the challenge was met, the solving group would issue a new challenge to the original challengers. It was considered un-gentlemanly to issue a challenge to which you did not have a solution, though Fermat was probably respected enough to get away with it. Times have changed.

Your task is to write programs that find solutions to the two challenges. 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 3

After Tuesday’s exercise on Lychrel numbers, I answered a question about Lychrel numbers over at Stack Overflow, using a recursive function to extract and reverse the digits one-by-one. I was challenged by a reader who claimed “using int("".join(reversed(str(n)))) has got to be far more efficient than using your recursive function. Your function is clever, but clever isn’t always best.” He was wrong, of course: arithmetic on numbers is better than converting a number to a string, creating a generator to reverse the individual characters of the string, appending them one-by-one to a new string, and converting the new string back to a number, which I demonstrated to him in a timing experiment.

Your task is to find the best way to reverse the digits of a positive integer, 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.

Pages: 1 2