Next Greater Permutation Of Digits
February 28, 2012
We have another interview question today:
Given a number, find the next higher number that uses the same set of digits. For instance, given the number 38276, the next higher number that uses the digits 2 3 6 7 8 is 38627.
Your task is to write a function to find the next greater permutation of digits. 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.
Remove characters from a string
February 24, 2012
The other day I needed a function to remove characters from a string, and was annoyed when neither R5RS nor the Standard Prelude provided one. Today’s exercise asks you to write that function:
Write a function that takes two strings and removes from the first string any character that appears in the second string. For instance, if the first string is “Programming Praxis” and the second string is “aeiou” the result is “Prgrmmng Prxs”.
Your task is to write the function described 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.
Learn A New Language
February 21, 2012
We’ve done this before, and had some fun, so we’ll do it again.
There are hundreds, probably thousands, of programming language. Some are general-purpose, others are intended for a limited domain. Some are useful, most get in your way. Some are just weird. We programmers frequently have to learn a new language, or re-learn an old one, or adapt to improvements from the vendor.
A good way to learn a new language is to write in the new language a familiar program from an old language with which you are experienced. Many people have written that they use the exercises at Programming Praxis as a way to get started with a new language.
Your task is to write a program that solves the Programming Praxis exercise of your choice in a programming language in which you are not proficient. 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.
Hailstones
February 17, 2012
We have an easy exercise for a Friday afternoon.
Consider the sequence of positive integers for which xn+1 = xn / 2 when x is even and 3·xn + 1 when xn is odd; this is known colloquially as “half or triple plus one.” For instance, starting from x0 = 13 the sequence is 13, 40, 20, 10, 5, 16, 8, 4, 2, 1, whence it loops through 4, 2, 1, …. This is called a hailstone sequence because it tends to go up and down and up and down much like hailstones in a thundercloud. Lothar Collatz conjectured in 1937 that every starting number eventually reaches 1; the conjecture is widely believed to be true, but has never been proven or disproven.
Your task is to write a function that computes hailstone sequences; you may wish to have some fun with your function by searching the internet for interesting tidbits about hailstone sequences and the Collatz conjecture. 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.
Divisors
February 14, 2012
We discussed divisors in a previous exercise. There, we factored a number and applied various loops to list the divisors of the number, their count, and their sum. That works fine for one or a few numbers. But if you have to find the divisors of a lot of numbers, it makes sense to compute the solutions all at once using a sieve. Start with an empty array d of the desired size n; then, for each i from 1 to n, mark i as a divisor of each multiple of i. For instance, with an array of 12:
1: 1
2: 1 2
3: 1 3
4: 1 2 4
5: 1 5
6: 1 2 3 6
7: 1 7
8: 1 2 4 8
9: 1 3 9
10: 1 2 5 10
11: 1 11
12: 1 2 3 4 6 12
Depending on your needs, you can make a list of the divisors, or count them, or compute their sum as you go along.
Your task is to write a function that builds a table of divisors as in the sample. Use it to find the perfect numbers and amicable pairs less than 10000, where perfect numbers are those whose divisors sum to twice the number and amicable pairs are those numbers whose sum of divisors (excluding the number itself) are the other number of the pair. 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.
Search In An Ascending Matrix
February 10, 2012
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 21the 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.
Solar Compass
February 7, 2012
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 = 360/365 (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 1st = 1, January 2nd = 2, and so on, and 81 is the day number of March 22nd, 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−1(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−1((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 7th is the 38th 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−1(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−1((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.
Roman Numeral Puzzle
February 3, 2012
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.
Programming Praxis 