Programming Praxis

We have today another question from our never-ending supply of interview questions:

Write a function that takes two input strings and determines if one is a rotation of the other. For instance, “ProgrammingPraxis” and “PraxisProgramming” are rotations of each other, but “ProgrammingPrasix” is not a rotation of “ProgrammingPraxis” because the last three letters are out of order.

Your task is to write the requested 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

Words that are formed from the same set of letters are anagrams of each other. For instance, pots, post, stop, spot, opts, and tops are anagrams. We studied anagrams in a previous exercise.

Anagrams can be extended from single words to phrases. For instance, “gin grammar prop six” and “maxim prong rasp rig” are anagrams for “programming praxis.”

Your task is to write a program to find all the anagram phrases for an input phrase that are present in a given dictionary; show only one permutation of each set of unique words. 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 task will require your imagination and creativity.

A high-school programming teacher recently asked for examples of short programs with a high “cool” factor, the idea being to get his students interested in programming computers. I’m not sure the suggestions would work; today’s high-school students have been surrounded by computers their entire lives, and it takes a lot to make them think a program is cool. Being from a different generation, I can remember when I thought it was cool that a program properly skipped over the perforation on a stack of green-bar paper — many programs didn’t!

Your task is to write a cool program in a dozen lines of code. You can define cool in any way that you wish. Try not to abuse the definition of “line of code,” at least not too badly; to be concrete, we will say that your solution must not exceed 12 lines, and each line must not exceed 80 characters including white 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

Today’s exercise is an interview question that appeared on Stack Overflow a few years ago:

The numbers on a telephone keypad are arranged thus:

1 2 3
4 5 6
7 8 9
  0

Starting from the digit 1, and choosing successive digits as a knight moves in chess, determine how many different paths can be formed of length n. There is no need to make a list of the paths, only to count them.

A knight moves two steps either horizontally or vertically followed by one step in the perpendicular direction; thus, from the digit 1 on the keypad a knight can move to digits 6 or 8, and from the digit 4 on the keypad a knight can move to digits 3, 9 or 0. A path may visit the same digit more than once.

Your task is to write a function that determines the number of paths of length n that a knight can trace on a keyboard starting from digit 1. 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 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