The cornerstone of my investment portfolio is playing the lottery. Each week I purchase some tickets, each of which has six numbers from 1-60 on them (without repeats). I have no delusions about particularly lucky numbers or trends in independently random events.
My problem is with the feasibility of checking all of these tickets. At the end of the week, I'll have a stack of tickets and the correct numbers, and I need to look through them all to see if I've won. The problem is to design such a system where either by purchasing particular numbers and/or by storing the tickets in a particular way, I reduce the difficulty in determining if there's a winner and finding it. I expect to purchase a very large number of tickets.
The following constraints apply:
-Since the jackpot pool is finite, having two identical tickets earns me less than two different tickets unless a third ticket splits a win with me. I prefer that none of the tickets are duplicates (which can be assumed given pseudorandom generation or specifically controlled for).
-The lottery I play in gives awards for matching 4, 5, or all 6 of the numbers. The system must provide the information for all of them.
-I have a large area to store the tickets, but it's not infinite.
-I do not have the time to linearly look through all the tickets after learning the winning numbers.
-If there's a computer used in the solution, take data entry errors into account.
Wednesday, January 28, 2009
Friday, January 9, 2009
Cannibals and Missionaries
An old puzzle turned into a little runtime analysis programming project:
You're given a number c cannibals and m missionaries on one side of a river. In the river is a boat that can carry b people at a time. Your task is to move all the missionaries from one side of the river to the other. A valid state is one in which there are no more cannibals than missionaries on either side of the river or in the boat unless there are 0 missionaries there (on the fear that the missionaries will be overpowered and eaten). The boat must have at least one person in it to move across the river.
For instance, for [m=1, c=1, b=2] a solution is for both people to take the boat across. For [m=2, c=2, b=2] a solution is for both cannibals to take the boat, one to return, both missionaries to take the boat and have one return, then the remaining cannibal and missionary to take the boat across. For [m+c>1 and b <= 1] there is no solution.
1) Write an algorithm to quickly find any solution. What is its complexity?
2) Write an algorithm to find the fastest (fewest steps) solution. What is its complexity?
3) Write an algorithm to determine whether the state is solvable. What is its complexity?
4) Write an algorithm to find the number of steps in the fastest solution, without it being necessary to produce the solution. Is it faster than #2?
5) Write a heuristic which would provide a number of steps such that if a solution was found to use that many steps, it would be the known fastest solution. (A heuristic that satisfied this problem could simply return 1)
You're given a number c cannibals and m missionaries on one side of a river. In the river is a boat that can carry b people at a time. Your task is to move all the missionaries from one side of the river to the other. A valid state is one in which there are no more cannibals than missionaries on either side of the river or in the boat unless there are 0 missionaries there (on the fear that the missionaries will be overpowered and eaten). The boat must have at least one person in it to move across the river.
For instance, for [m=1, c=1, b=2] a solution is for both people to take the boat across. For [m=2, c=2, b=2] a solution is for both cannibals to take the boat, one to return, both missionaries to take the boat and have one return, then the remaining cannibal and missionary to take the boat across. For [m+c>1 and b <= 1] there is no solution.
1) Write an algorithm to quickly find any solution. What is its complexity?
2) Write an algorithm to find the fastest (fewest steps) solution. What is its complexity?
3) Write an algorithm to determine whether the state is solvable. What is its complexity?
4) Write an algorithm to find the number of steps in the fastest solution, without it being necessary to produce the solution. Is it faster than #2?
5) Write a heuristic which would provide a number of steps such that if a solution was found to use that many steps, it would be the known fastest solution. (A heuristic that satisfied this problem could simply return 1)
Subscribe to:
Posts (Atom)