March 8, 2013
[ Today’s exercise comes from "Learn You a Haskell for Great Good" written by Miran Lipovača; the solution was written by Kyle Ilantzis. Guest authors are always welcome; if you are interested, contact me at the email address on the menu bar. By the way, that's a fine place to start if you want to learn about Haskell. ]
This exercise comes from “Learn You a Haskell for Great Good!” by Miran Lipovača. Lipovača demonstrates a solution to find out if a single knight piece on a chessboard can reach a position in three moves. As an exercise he suggests that we try to find out if that knight can reach a position on the board in n moves and if so, what are the moves that the knight should make.
Your task is to write a function that given a starting position, ending position, and n number of moves to take, returns a list of all possible paths that that knight piece could take to reach the goal. If some input has no solution then simply return an empty list. 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.
March 5, 2013
A famous problem given by Edsgar Dijkstra is to sort an array of red, white and blue symbols so that all reds come together, followed by all whites, followed finally by all blues; it’s called the Dutch National Flag problem because the Dutch flag consists of three stripes with red at the top, blue at the bottom, and white in the middle. You are allowed to scan through the array only once, and the only operations permitted are to examine the color of the symbol at a given array location and to swap the symbols at two locations.
Your task is to write a program to perform the sort given above. When you are finished, you are welcome to read or run a suggested solution, or to post your solution or discuss the exercise in the comments below.
March 1, 2013
We examined the Baillie-Wagstaff probabilistic primality checker based on Lucas pseudoprimes in a previous exercise, where we got it wrong; among other things it incorrectly reported that 3825123056546413051 = 149491 × 747451 × 34233211 was prime. We’ll fix that today. Robert Baillie and Samuel Wagstaff Jr. describe the test in their article “Lucas Pseudoprimes” in Mathematics of Computation, Volume 35, Number 152, pages 1391-1417, October 1980; see also Thomas Nicely’s web page devoted to the test. This is the same algorithm used in the
PrimeQ function in Mathematica. If at any point the math gets daunting, feel free to skip ahead to the code, which is short and simple.
Lucas numbers are defined by a recurrence formula similar to Fibonacci numbers, where Ln = Ln−1 + Ln−2 with L1 = 1 and L2 = 3; the Lucas numbers are 1, 3, 4, 7, 11, 18, 29, 47, 76, 123, … (Sloane’s A000204). Lucas numbers have the rather startling property that, if n is prime, Ln ≡ 1 (mod n). But the converse is not true, and composite numbers n such that Ln ≡ 1 (mod n) are known as Lucas pseudoprimes; the first few Lucas pseudoprimes are 705, 2465, 2737, 3745, 4171, … (Sloane’s A005845).
Lucas numbers are a special case of Lucas sequences. If P and Q are integers such that the discriminant D = P2 − 4Q, then the roots of x2 − Px + Q = 0 are a = (P + √D) / 2 and b = (P − √D) / 2 (that’s the quadratic equation you learned in middle school). There are two Lucas sequences Un(P,Q) = (an − bn) / (a − b) and Vn(P,Q) = an + an for n ≥ 0, which can be computed by the recurrence equations Um(P,Q) = PUm−1(P,Q) − QUm−2(P,Q) and Vm(P,Q) = PVm−1(P,Q) − QVm−2(P,Q). The Lucas numbers are given by the sequence V(1, -1) and the Fibonacci numbers are given by the sequence U(1, -1).
It is possible to compute the nth element of a Lucas sequence in logarithmic time rather than linear time using a double-and-add algorithm similar to the peasant algorithm for multiplication; such a computation is known as a Lucas chain. The rules are U2n = Un Vn, U2n+1 = Un+1 Vn − Qn, V2n = Vn2 − 2 Qn, and V2n+1 = Vn+1 Vn − P Qn. For our purposes, we will be making all computations mod n.
Thus we have a method to determine if a number n is a Lucas pseudoprime. Choose a suitable P and Q, use a Lucas chain to compute Un(P,Q), and declare n either prime or a Lucas pseudoprime if Un(P,Q) ≡ 0 (mod n). There are several methods to compute suitable P and Q, of which the most commonly-used is due to John Selfridge: choose D as the smallest number in the sequence 5, -7, 9, -11, 13, -15, 17, … for which the Jacobi symbol (D / n) = -1, then set P = 1 and Q = (1 – D) / 4.
There is a strong version of the Lucas pseudoprimality test that bears the same relationship to the standard version of the Lucas pseudoprimality test described above as Gary Miller’s strong Fermat pseudoprimality test bears to the standard Fermat pseudoprimality test. Represent n as d · 2s + 1, then compute Ud(P,Q) and Vd(P,Q). Then n is either prime or a Lucas pseudoprime if Ud(P,Q) ≡ 0 (mod n) or if Vd 2r(P,Q) ≡ 0 (mod n) for any r with 0 ≤ r < s.
Finally, the Baillie-Wagstaff test of the primality of n consists of the following steps: 1) if n is not an integer, report a domain error; 2) if n < 2, report n is not prime; 3) if n is a square, report n is not prime; 4) if n is divisible by any primes less than some convenient limit (e.g. 100 or 1000), report n is not prime; 5) if n is not a strong Fermat pseudoprime to base 2, report n is not prime; 6) (optional, added by Mathematica) if n is not a strong Fermat pseudoprime to base 3, report n is not prime; 7) if n is not a Lucas pseudoprime (standard or strong), report n is not prime; 8) otherwise, report n is prime.
The Baillie-Wagstaff pseudoprimality test, whether or not the base-3 test is included and whether the standard or strong Lucas test is chosen, is extremely strong: there are no known errors. Exhaustive checks have been performed to 1017, and the test has been used for years in several high-quality primality proving programs that would have found an error if one occurred. There is a $620 reward for a counter-example to the test ($500 from Selfridge, $100 from Wagstaff, and $20 from Carl Pomerance), plus the certain fame that will accrue to the finder.
Your task is to write a Baillie-Wagstaff primality checker as 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.
February 26, 2013
I’m not sure where this comes from; it could be an interview question, or some kind of programming puzzle:
Write a function that takes a positive integer n and returns n-squared. You may use addition and subtraction but not multiplication or exponentiation.
Your task is to write the squaring 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.
February 22, 2013
[ Today's exercise was contributed by Tom Rusting, who worked as a programmer until the mid 70’s. Being retired, he has now taken up programming again as a hobby. Suggestions for exercises are always welcome, or you may wish to contribute your own exercise; feel free to contact me if you are interested.
Floup is an island-country in the South Pacific with a currency known as the floupia; coins are denominated in units of 1, 3, 7, 31 and 153 floupias. Merchants and customers engage in a curious transaction when it comes time to pay the bill; they exchange the smallest number of coins necessary to complete the payment. For instance, to pay a bill of 17 floupia, a customer could pay three 7-floupia coins and receive single 1-floupia and 3-floupia coins in exchange, a total of five coins, but it is more efficient for the customer to pay a single 31-floupia coin and receive two 7-floupia coins in exchange.
Your task is to write a program that determines the most efficient set of coins needed to make a payment, generalized for any set of coins, not just the set 1, 3, 7, 31 and 153 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.
February 19, 2013
[ Today is the fourth anniversary of Programming Praxis, which published five exercises on February 19, 2009. I remember getting 6 hits that day, all of them from one friend that I told about the blog. I get a few more hits now. Many thanks to all of my readers, whose comments and emails inspire me to continue. — Phil ]
We haven’t done a word puzzle for a while. Here is one from the NPR Sunday Puzzle:
Think of two familiar, unhyphenated, eight-letter words that contain the letters A, B, C, D, E and F, plus two others, in any order. What words are these?
Your task is to write a program to find the two 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.
February 15, 2013
Round 1 of the Facebook Hacker Cup 2013 is now complete. In today’s exercise we look at Problem 1:
CARD GAME (20 points)
John is playing a game with his friends. The game’s rules are as follows: There is deck of N cards from which each person is dealt a hand of K cards. Each card has an integer value representing its strength. A hand’s strength is determined by the value of the highest card in the hand. The person with the strongest hand wins the round. Bets are placed before each player reveals the strength of their hand.
John needs your help to decide when to bet. He decides he wants to bet when the strength of his hand is higher than the average hand strength. Hence John wants to calculate the average strength of ALL possible sets of hands. John is very good at division, but he needs your help in calculating the sum of the strengths of all possible hands.
You are given an array a with N ≤ 10000 different integer numbers and a number, K, where 1 ≤ K ≤ N. For all possible subsets of a of size K find the sum of their maximal elements modulo 1000000007.
The first line contains the number of test cases T, where 1 ≤ T ≤ 25
Each case begins with a line containing integers N and K. The next line contains N space-separated numbers 0 ≤ a [i] ≤ 2000000000, which describe the array a.
For test case i, numbered from 1 to T, output "Case #i: ", followed by a single integer, the sum of maximal elements for all subsets of size K modulo 1000000007.
For a = [3, 6, 2, 8] and N = 4 and K = 3, the maximal numbers among all triples are 6, 8, 8, 8 and the sum is 30.
3 6 2 8
10 20 30 40 50
0 1 2 3 5 8
10386 10257 10432 10087 10381 10035 10167 10206 10347 10088
Case #1: 30
Case #2: 400
Case #3: 103
Case #4: 1122
Case #5: 2621483
Your task is to write a program that solves the Facebook problem 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.
February 12, 2013
We have seen several flavors of binary search trees, including classic bsts, treaps, red/black trees, and avl trees. For all of them we provided a
lookup function that returned a requested key/value pair. In today’s exercise we write functions that return the predecessor and successor of a requested key, allowing a program to walk the tree in order. There are two common variants of these functions, one using parent pointers and one without; our exercise will use the variant without parent pointers, which is generally more useful.
We give the basic logic for the
successor function; the
predecessor function is similar, but reversed. A recursive function descends the tree searching for the requested key, keeping track of the current tree as the possible successor every time if follows the left sub-tree. If it finds the key, its successor is the minimum element of the right sub-tree, found by chasing left sub-trees until reaching a null node. If the search reaches a null node and hence fails to find the key, the next largest key in the tree is the successor, found in the possible successor that was saved at each recursive call.
Your task is to write
successor functions for binary search trees. 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.
February 8, 2013
It has been widely reported that a new “biggest prime” was found two weeks ago. The prime, which has 17,425,170 digits, is:
257,885,161 − 1
Your task is to write a program that displays all seventeen million digits of the biggest prime. 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.
February 5, 2013
Today’s exercise comes to us from the world of recreational mathematics:
Find all possible solutions to the equation 1/a + 1/b + 1/c + 1/d + 1/e = 1 where all of a, b, c, d and e are positive integers.
One solution is the trivial 1/5 + 1/5 + 1/5 + 1/5 + 1/5. Another solution, based on the perfect number 1 + 2 + 4 + 7 + 14 = 28, is 1/2 + 1/4 + 1/7 + 1/14 + 1/28. The minimum distinct solution is 1/3 + 1/4 + 1/5 + 1/6 + 1/20, where all the denominators are distinct and the sum of the denominators 3 + 4 + 5 + 6 + 20 = 38 is minimum over all solutions.
Your task is to write a program to enumerate all possible solutions to the equation. 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.