Programming Praxis

We previously wrote a program to provide small exercises in arithmetic for children just learning their basic facts. Today’s exercise is similar; it plays a guessing game where children compete against the computer to see which can guess the number faster. Here’s a sample dialog:

Let's play Guess-The-Number!
You go first.
I am thinking of a number from 1 to 100
What is your guess? 38
My number is less than your guess.
What is your next guess? 15
Your guess is less than my number.
What is your next guess? 25
Your guess is less than my number.
What is your next guess? 33
My number is less than your guess.
What is your next guess? 28
Your guess is less than my number.
What is your next guess? 31
Your guess is less than my number.
What is your next guess? 32
You guessed my number 32 in 6 tries!
Now it's my turn.
Think of a number from 1 to 100.
Is your number less than 50? Yes
Is your number less than 25? No
Is your number less than 37? Yes
Is your number less than 31? No
Is your number less than 34? Yes
Is your number less than 32? No
Is your number less than 33? Yes
I guessed your number 32 in 7 tries.
You made less guesses than me.
You win! Congratulations!
Would you like to play again? No
Thanks for playing! Good-bye!

Your task is to write a program that plays Guess-The-Number; the maximum number in play (100 in the sample dialog) should be a parameter to the program. 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 studied numerical integration in a previous exercise. In today’s exercise we will look at the inverse operation of numerically calculating a derivative.

The function that interests us in today’s exercise is the XIRR function from Excel, which computes the internal rate of return of a series of cash flows that are not necessarily periodic. The XIRR function calculates the value of x that makes the following equation go to 0, where p_i is the ith cash flow, d_i is the date of the ith cash flow, and d₀ is the date of the first cash flow:

The method used to estimate x was devised by Sir Isaac Newton about three hundred years ago. If x_n is an approximation to a function, then a better approximation x_n+1 is given by

where f'(x_n) is the derivative of f at n. Mathematically, the derivative of a function at a given point is the slope of the tangent line at that point. Arithmetically, we calculate the slope of the tangent line by knowing the value of the function at a point x and a nearby point x+ε, then using the equation

to determine the slope of the line. Thus, to find x, pick an initial guess (0.1 or 10% works well for most interest calculations) and iterate until the difference between two successive values is close enough. For example, with payments of -10000, 2750, 4250, 3250, and 2750 on dates 1 Jan 2008, 1 March 2008, 30 October 2008, 15 February 2009, and 1 April 2009, the internal rate of return is 37.3%.

Your task is to write a function that mimics Excel’s XIRR function. 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

On December 7, 2011, Neil deGrasse Tyson tweeted:

Need a distraction today? Not only does 12+1=11+2, but the letters “twelve plus one” rearrange to give you “eleven plus two”

Mitchell Perilstein forwarded that tweet to me and suggested that it would form the basis of an exercise for Programming Praxis.

Your task is to write a program that finds equations similar to Tyson’s that form anagrams both in their symbols and in their letters. 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 seen several different sieves that enumerate the prime numbers not greater than n due to Eratosthenes, Atkin, Euler and Sundaram. In the 1980s, Paul Pritchard, an Australian mathematician, developed a family of sieve algorithms based on wheels, eventually finding an algorithm with O(n / log log n) time complexity and O(√n) space complexity. We examine a simple version of Pritchard’s wheel sieve in today’s exercise.

We begin with some definitions. M_k is the product of the first k primes; for instance, M₇= 2×3×5×7×11×13×17=510510. The totatives of M_k are those numbers from 1 to M_k that are coprime to M_k (that is, they have no factors in common). It is easy to determine the totatives of M_k by sieving: make a list of the integers from 1 to M_k, then for each of the primes that form the product M_k, strike out from the list the prime and all of its multiples; for instance, with M₃=2×3×5=30, sieving with 2 strikes out 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28 and 30, sieving with 3 strikes out 3, 6, 9, 12, 15, 18, 21, 24, 27, and 30, and sieving with 5 strikes out 5, 10, 15, 20, 25 and 30, leaving the totatives 1, 7, 11, 13, 17, 19, 23 and 29. A factoring wheel W_k contains the gaps between successive totatives, wrapping around at the end; for instance, W₃ consists of the gaps 6, 4, 2, 4, 2, 4, 6 and 2, corresponding to the gaps 7−1, 11−7, and so on, ending with 29−23 and 31−29 when the wheel wraps around at the end.

Pritchard’s wheel sieve uses wheels repeatedly to strike out composite numbers from the sieve. It operates in two phases: a setup phase and a processing loop.

The setup phase first computes a parameter k such that M_k < n / log_e n < M_k+1, then computes the wheel W_k and forms the set S from 1 to n by rolling the W_k wheel. The setup phase also computes the list of m primes not greater than the square root of n.

We compute the primes not greater than 100 as an example. We compute k=2, since 100/log(100) is 21.714724 which is between M₂=6 and M₃=30. The W₂ wheel is {4 2} and the set S is {1 5 7 11 13 17 19 23 25 29 31 35 37 41 43 47 49 53 55 59 61 65 67 71 73 77 79 83 85 89 91 95 97}; although there is only one set S, we will refer to this set as S₂, since it is the result of rolling the W₂ wheel. Finally, the square root of 100 is 10, and the m=4 primes less than 10 are {2 3 5 7}.

The processing loop iterates from k+1 to m. At each loop we will strike some of the elements of S, reducing S from S_k to S_k+1. Each time through the loop we first identify p, the smallest member of S that is greater than 1, and strike it from the set S. We also strike from S the successive multiples p(s'−s) less than n, where s'−s are the successive gaps in S. Finally, we increment k by 1 and repeat the loop as long as k≤m.

In our example computing the primes not greater than 100, i will take the values 3 and 4. The first time through the loop, p = 5, the gaps are 5−1=4, 7−5=2, 11−7=4, 13−11=2, 17−13=4 and 19−17=2, and the numbers that are stricken are 5, 5+4×5=25, 25+2×5=35, 35+4×5=55, 55+2×5=65, 65+4×5=85, and 85+2×5=95, leaving S₃ = {1 7 11 13 17 19 23 29 31 37 41 43 47 49 53 59 61 67 71 73 77 79 83 89 91 97}. The second time through the loop, p = 7, the gaps are 7−1=6, 11−7=4, 13−11=6, 17−13=4, and 19−17=2, and the numbers that are stricken are 7, 7+6×7=49, 49+4×7=77, and 77+2×7=91, leaving S₄ = {1 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97}.

Once k>m and the final S has been computed, the list of primes is returned, consisting of the primes less than the square root of n followed by the elements of S excluding 1. Thus the primes not greater than 100 are 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89 and 97.

This version of Pritchard’s sieve has time complexity and space complexity both equal to O(n), where the standard sieve of Eratosthenes has time complexity O(n log log n). The improvement comes from the fact that Pritchard’s sieve strikes each composite only once, whereas Eratosthenes’ sieve strikes each composite once for each of its distinct prime factors; for instance, Eratosthenes’ sieve strike 15 twice, one for the factor of 3 and once for the factor of 5. But despite the improvement in the asymptotic complexity, Eratosthenes’ sieve is fast because its inner loop consists only of addition, while Pritchard’s sieve is slower because its inner loop consists of a subtraction to compute the gap in the wheel, a multiplication to extend that gap by the current sieving prime, and an addition to add the gap to the previously-stricken element. Thus, in practice, Eratosthenes’ sieve is faster than Pritchard’s.

Your task is to write a program to compute the primes not greater than n using Pritchard’s wheel sieve. 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 had fun drawing a fractal snowflake last week. In today’s exercise, we will write a full library for turtle graphics. Our goal is to provide the commands described in Brian Harvey’s book about Logo. The turtle is a robotic device that moves and draws on a graphical output device (paper, screen) with a coordinate system that has x running west (negative) to east (positive) and y running south (negative) to north (positive); the ordinal compass points are 0 north, 90 east, 180 south and 270 west. Most commands ignore the global coordinate system in favor of commands from the turtle’s point of view, so instead of saying “turn to 135 degrees” a typical command is “turn right 45 degrees,” so that a shape can be drawn without knowledge of its global coordinates. The turtle commands are:

clearscreen — initialize the graphics system and place the turtle in the center of the graphical output pointing north

penup — remove the pen from the drawing surface

pendown — place the pen on the drawing surface

forward n — move the turtle forward n steps, drawing a line if the pen is down

back n — move the turtle back n steps, drawing a line if the pen is down

left n — rotate the turtle n degrees left from its current heading

right n — rotate the turtle n degrees right from its current heading

setpos x y — move the turtle from its current position to the indicated coordinates, drawing a line if the pen is down

setheading n — rotate the turtle from its current heading to the indicated heading

pos — report the current position by its x and y coordinates

heading — report the current heading in degrees

Your task is to write a turtle graphics library. 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 our file of interview questions:

Given a list, return the first half of the list as one list and the second half of the list as a second list. For instance, given the input list {1 2 3 4}, output the two lists {1 2} and {3 4}. If the input list has an odd number of items, the middle item can go to either list, so that the input list {1 2 3 4 5} can result in the output lists {1 2} and {3 4 5} or the output lists {1 2 3} and {4 5}.

Your task is to write the function that splits a list in two halves. 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 a tradition here at Programming Praxis of celebrating milestones by having a party, and parties require games. Today, for our three-hundredth exercise we will write a cheating version of the hangman from a previous exercise.

The idea is simple. Instead of choosing a single answer at the beginning of the game, choose a length, and make a list of all possible answers. Each time the player guesses a letter, delete as few words from the possible-answer list as possible consistent with the guesses the player has made; most of the time another body part will be added to the gibbet.

Your task is to write a referee for the game of cheating hangman. 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

It’s Christmas time, and that means winter, and that means snow (sometimes, but probably not this year), so today’s exercise is to draw Koch’s Snowflake. This famous fractal is built from an equilateral triangle, as shown upper left. At each step each side is modified by removing its center third and replacing it with two legs of another equilateral triangle. Thus, at upper right, each of the three legs has been replaced four line segments that form a new shape. Carrying on, the fractal becomes more and more detailed at the edges of the triangle; eventually, the perimeter of the triangle is infinite, though its area is 8/5 the area of the original triangle. Mathematically, the Koch Snowflake can be encoded as a Lindenmayer system with initial string F++F++F, rewriting rule F → F-F++F-F, and angle 60 degrees (in the Lindenmayer notation, F means move forward, + is a right turn and - is a left turn).

Your task is to write a program to draw the Koch Snowflake. 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

In today’s exercise we implement the classic Unix V7 game hangman for guessing words. The player is given a series of blanks, one per letter of a word to be guessed. At each turn the player guesses a letter; if it is in the word, all occurrences of the letter are filled in the appropriate blank, but if the guess is wrong, another body part — traditionally, the head, torso, two arms and two legs, for a total of six — is added to the gibbet. The player wins by guessing all the letters of the word before the hangman adds all the pieces of his body.

Your task is to implement the interactive game of hangman. 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

In an election, the winner is required to have the majority of the votes. For instance, with the set of votes {A A A C C B B C C C B C C}, the winner is C with 7 of 13 votes. Some elections have no winner; with the set of votes {A B C A B C A}, A gets a plurality of the votes but not a majority, so there is no winner. You can think of voting as a political election, or as redundant hardware in a critical system where a failure of one component must not lead to failure of the overall system.

Your task is to write a function that determines the winner of a vote, or indicates that no candidate reached a majority. 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