During my recent computer cleaning, I found a few problems I wrote for the contest. I typically had some of the easier problems at the contest
(there were about a dozen total problems).
Therefore, I decided to share with you my three programming contest questions, 1) Dr. Bob’s Crazy People Party, 2) Palpatine’s Florist and 3) Modular Primes.
This problem is a good example of where we should transform divide and conquer into dynamic programming or implement a top down memory function.
**Congratulations, you have been invited to Dr. Bob’s Crazy-People Party for Quixotic Number Crunchers! Unfortunately, in order to enter the party house you must first answer a question. Since you know Dr. Bob likes Fibonacci n-step numbers you assume that will be the question. You decide to write a program to calculate
Fn(x) for you so you won’t be stuck outside the party.
Fibonacci n-step number is defined as:
Fn(1) = 1, Fn(2) = 1
if x <= 0 then Fn(x) = 0, also don’t worry about
x > n, Bob isn’t that crazy
F3(10) = F3(9) + F3(8) + F3(7)
Fn(x) is recursive in nature; however, if you write the program recursively it will probably be too slow and you will miss the party if Dr. Bob asks for a high value of n or x)
The program should loop until it sees a non-number input for n or x. Example, in order to end the program type q for the value of n or x. See below for some input/output examples.
n=7 n=5 n=10 n=30 n=2 n=3
Here is the gist of it:
$F1 = array(0 => 0, 1 => 1, 2 => 1);
So what is this Seive? I named it this because of the Sieve of Eratosthenes. The idea is to remember the all the previous prime numbers you found in order to find the next. We aren’t dealing with prime numbers in this case but instead Fibonacci numbers but the idea is the same. This is a way to calculate the Fn for a specific
$x and store the results in a two dimensional array for next time we try to find another value for the pair ($n, $x).
function SeiveFn($step, $x)
You can see answer source code here in php.
You are a florist and you’ve received a call from Emperor Palpatine, something about executing
Order 66. Basically he wants you to deliver flowers to certain Jedi warriors. However, you must deliver the flowers in a specific order, the first bouquet should go to the highest ranking Jedi, the second bouquet to the second highest, and so on down the chain of rank until the last flowers are delivered to the lowest ranking Jedi.
In case you are unsure of rank (shame, shame), he has given you a list of Jedi names in two columns. This list compares two Jedi members and you should read this as, first Jedi rank > second Jedi rank.
Your list looks as follows:
Note: From the first line we can tell that Windu is higher rank than Mundi. Thus we should also infer that anyone lesser in rank than Mundi is also lesser rank than Windu.
Return a list of names in order of rank based on this list above so you can deliver the flowers as the Emperor wishes. Be prepared to use another list in case the Emperor wants to add additional rankings to the list (don’t just do this by hand).
You can see example solution for this in php. The trick is just to print higher in rank, yourself, then everyone lower in rank and you keep a memory array to make sure you only print yourself once.
function sortList($keys, $list)
I didn’t get very creative with this one. Essentially, I asked the teams to find the two smallest prime numbers which has a pattern found from Wilson’s theorem. See entire source code or read the code below for more details. The first answer for range 2 through 10 would be 5039 because:
The teams had to find the next prime that matches this same pattern for range 2 to 10 and I asked to be able to check for other ranges besides 2 through 10.
/* Find primes P, with following pattern
That wraps it up. It was fun being a contest judge. As I said earlier, my questions were usually among the first answered. Not having your question answered at all just means it was too complex anyway and what’s the point of that? The goal is to see how well people can program - not to attempt to baffle and frustrate a team for five hours.