Programming Praxis

Today’s exercise is taken from our inexhaustible list of interview questions:

Given an m by n matrix of integers with each row and column in ascending order, search the matrix and find the row and column where a key k appears, or report that k is not in the matrix. For instance, in the matrix

 1  5  7  9
 4  6 10 15
 8 11 12 19
14 16 18 21

the key 11 appears in row 2, column 1 (indexing from 0) and the key 13 is not present in the matrix. The obvious algorithm takes time O(m × n) to search the matrix row-by-row, but you must exploit the order in the matrix to find an algorithm that takes time O(m + n).

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

In 1836, a surveyor named William Burt invented a solar compass that determined true north from the Sun; he needed it because iron-bearing rock made his magnetic compass give inaccurate readings. His device was levelled on top of a tripod, then one scale was set to the Sun’s declination (Burt used a table, which repeated each year), a second scale at an angle to the first was set to the latitude, a third scale was set to the current time, and then the Sun was sighted through a pinhole to set a third scale; with the compass set up, any compass point could be determined through the sights of the instrument. Surveyors still use Burt’s compass today.

Nowadays, smart phones and tablet computers have built-in clocks to tell the time and GPS devices to give the latitude and longitude, and they even have magnetic compasses so you know which direction is north. If the Sun is shining, such devices could be made into a solar compass, so you could determine true north; the device could display a compass rose with an indication of the Sun’s azimuth, the user lays the device flat and points the azimuth indicator to the Sun, and the compass rose indicates true north.

In today’s exercise we will write a function to compute the Sun’s elevation (angle above the horizon) and azimuth (compass direction); you’ll have to draw the compass rose yourself. We’ll use as an example the site of the Gateway Arch in Saint Louis, Missouri, located at 38.6N, 90.2W, and find the Sun’s elevation and azimuth at 7:00am on February 7, 2012.

The first calculation is the Sun’s declination, which varies through the year as the sun’s daily high point moves north and south of the equator due to the tilt of the Earth’s axis; Burt looked up the declination in an almanac, but we can make the calculation ourselves. Declination is always between 23.45° north of the equator (the Tropic of Cancer) and 23.45° south of the equator (the Tropic of Capricorn), and is the same at all points on the globe; it is 0° at the spring and autumn equinoxes, 23.45° north at the summer solstice, and 23.45° south at the winter solstice. The formula is 23.45 sin(B), where B = ³⁶⁰/₃₆₅ (d − 81); in this calculation, 360 is the number of degrees in a circle, 365 is the number of days in the year (use 366 in leap years), d is the day number with January 1^st = 1, January 2^nd = 2, and so on, and 81 is the day number of March 22^nd, which is the spring equinox.

The second calculation is the local solar time. Burt used the latitude scale on his device to build a sundial that gave the local solar time directly, but we must calculate the difference between the local clock time and the local solar time. We begin with a calculation called the equation of time, which corrects for (“equates”) the eccentricity of the Earth’s orbit around the Sun and the tilt of the Earth on its axis; like the declination, the equation of time repeats each year, and is based on the number of days since the beginning of the year. The formula is 9.87 sin(2B) − 7.53 cos(B) − 1.5 sin(B), where B is the same calculation we made to compute the declination. The equation of time is given in minutes.

Given the equation of time, we can calculate the time correction factor that adjusts between local clock time and local sun time, which adjusts for variation within a time zone due to longitude and also incorporates the equation of time. The formula is 4(long − 15t) + eot, where 4 = 24 × 60 ÷ 360 is the number of minutes it takes the Earth to spin 1 degree, 15 = 360 ÷ 24 is the number of degrees the Earth spins in one hour, long is the longitude of the current location, t is the number of hours east (positive) or west (negative) the local time zone is from the Greenwich meridian (remember to add 1 hour if daylight saving time is in effect), and eot is the equation of time. The time correction is given in minutes. Then, the local solar time is just the local time plus the time correction factor divided by 60; the local solar time is measured in hours, with a fractional part indicating the minutes after the hour.

Burt’s third scale, sighting the sun through the pinhole, calculated the solar hour angle, which is 0° at local solar noon, negative in the solar morning and positive in the solar afternoon. The solar hour angle changes by 15° every hour as the Earth spins, so the calculation is 15(lst − 12), where lst is the local solar time.

Now the elevation is easy to calculate by the formula sin⁻¹(sin(dec) sin(lat) + cos(dec) cos(lat) cos(hra)) where dec is the declination, lat is the latitude of the current location, and hra is the solar hour angle. The azimuth is equally easy to calculate by the formula cos⁻¹((sin(dec) cos(lat) − cos(dec) sin(lat) cos(hra)) ÷ cos(α)) where α, which is the elevation angle at solar noon, is 90 − lat + dec in the northern hemisphere and 90 + lat − dec in the southern hemisphere.

Let’s make some calculations. February 7^th is the 38^th day of the year, b = 360 ÷ 366 × (38 − 81) = −42.3°, the declination is 23.45° × sin(−42.3°) = −15.8° and the equation of time is 9.87 sin(−84.6°) − 7.53 cos(−42.3°) − 1.5 sin(−42.3°) = −14.4 minutes. Saint Louis is 6 hours west of Greenwich, and daylight savings time is not in effect, so the time correction is 4(−90.2 − −90) − 14.4 = −15.2 minutes, the local solar time is 7 + 0/60 − 15.2/60 = 6.75 hours (that’s 6:45am), and the solar hour angle is 15(6.75 − 12) = −78.8°. The elevation is sin⁻¹(sin(−15.8°) sin(38.6°) − cos(-15.8°) cos(38.6°) cos(−78.8°)) = −1.3°, so the Sun has not yet risen. Now α = 90° − 38.6° − 15.8° = 35.6° and the azimuth is cos⁻¹((sin(−15.8°) cos(38.6°) − cos(−15.8°) sin(38.6°) cos(−78.8°)) ÷ cos(35.6°))= 113.9°. I was at the Gateway Arch this morning at 7:00am (I attend Mass every morning at the Basilica of Saint Louis, King of France (the Old Cathedral), which is just a few hundred feet from the Arch), and can testify that the Sun was just about to rise over the Mississippi River a little bit south of due East.

Your task is to write a function that returns the Sun’s elevation and azimuth given latitude, longitude and the current date and time. 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 Super Bowl is the championship game of the American league of professional football teams — and an annual cultural event. The first Super Bowl, won by the Green Bay Packers under head coach Vince Lombardi, was in 1967, and wasn’t even called “Super Bowl” at the time; the name didn’t attach to the game until Super Bowl III, when Joe Namath of the New York Jets guaranteed a victory. Roman numerals have been used to designate the Super Bowl ever since. The game this year, between the Boston Patriots and New York Giants, is Super Bowl XLVI; you can solve today’s exercise while you watch the game on Sunday evening.

John D. Cook turned the wacky roman numerals of the Super Bowl into an exercise at his blog; he was inspired by an advertisement for Super Bowl XLVI on a pizza box. Cook asked his readers to compute how many numbers can be expressed as roman numerals without duplicating any of the symbols I, V, X, L, C, D or M.

Your task is to compute the number of roman numerals that have no duplicate characters. 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 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