I was a judge for uca’s annual alar’s programming contest years 2008 - 2010. It was a pretty fun experience, we got to spend the day judging other’s code and lots of free food.
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.
Dr. Bob’s Crazy-People Party (2008)
{% blockquote %}This problem is a good example of where we should transform divide and conquer into dynamic programming or implement a top down memory function.{% endblockquote %}
**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
Fn(x) = Fn(x-1) + Fn(x-2) + … + Fn(x-n)
Assume that if x <= 0 then Fn(x) = 0, also don’t worry about x > n, Bob isn’t that crazy
Some Examples
F3(10) = F3(9) + F3(8) + F3(7)
= 81 + 44 + 24 # Notice, to find F3(9) we need to know F3(8) + F3(7) + F3(6)
= 149 # And likewise for F3(8), F3(7), F3(6), …, F3(1)
(Hint: 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.
Input/Output Examples
n=7 n=5 n=10 n=30 n=2 n=3
x=10 x=20 x=12 x=41 x=8 x=5
ans=149 ans=203513 ans=1023 ans=549755811072 ans=21 ans=7
Here is the gist of it:
$F1 = array(0 => 0, 1 => 1, 2 => 1);
$Fn = array(1 => $F1);
function Fn($step, $x)
{
global $Fn;
if (!isset($Fn[$step][$x])) SeiveFn($step, $x);
return $Fn[$step][$x];
}
echo Fn($n = 10, $x = 12); // 1023
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 $n and $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)
{
global $Fn;
if(!isset($Fn[$step]))
{
if(!isset($Fn[$step - 1])) SeiveFn($step - 1, $x);
$Fn[$step] = $Fn[$step - 1];
}
for($i = $step + 1; $i <= $x; $i++)
{
$sum = 0;
for($n = $i - 1; $n >= $i - $step; $n--) $sum = $sum + $Fn[$step][$n];
$Fn[$step][$i] = $sum;
}
}
You can see answer source code here in php.
Emperor Palpatine’s Florist (2009)
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:
Windu Mundi
Yoda Yaddle
Yoda Poof
Windu Obi-wan
Yaddle Poof
Obi-wan Skywalker
Yoda Windu
Yaddle Obi-wan
Mundi Yaddle
Yoda Skywalker
Skywalker Poof
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)
{
# get a list of people that are better than me then print my name
foreach ($keys as $name) { whoIsBetter($name, $list); printJedi($name); }
# get a list of people worse than me
foreach ($keys as $name) { whoIsWorse($name, $list); }
}
$p = array(); # global variable to keep up with Jedi names we have printed
function printJedi($name)
{
if($GLOBALS['p'][$name] != 1) print "$name\n";
$GLOBALS['p'][$name] = 1;
}
function whoIsBetter($name, $list)
{
foreach ($list as $key => $value)
{
if($key != $name)
{
foreach ($value as $item) { if($item == $name) printJedi("$key"); }
}
}
}
function whoIsWorse($name, $list)
{
foreach ($list[$name] as $value){ printJedi($value); }
}
Modular Primes (2010)
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:
Answer: 5039
-> 2 (2519) + 1 = 5039
-> 3 (1679) + 2 = 5039
-> 4 (1259) + 3 = 5039
-> 5 (1007) + 4 = 5039
-> 6 (839) + 5 = 5039
-> 7 (719) + 6 = 5039
-> 8 (629) + 7 = 5039
-> 9 (559) + 8 = 5039
-> 10 (503) + 9 = 5039
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
* 2(p2) + 1 = P
* 3(p3) + 2 = P
* 4(p4) + 3 = P
* ...
* N(pN) + (N-1) = P
*
* This is a variation of Wilson's theorem for a prime number 'n'
* (n-1)! = -1 mod n
*/
function main()
{
$max = 10; # check mod 2 - 10
$i = 5000; # start iterator at 5000 (I already know the answer and it is greater than 5000)
$count = 2; # how many primes should we find with this pattern?
while ($count != 0)
{
# find a possible answer
$answer = $i;
for($n=2; $n<=$max; $n++)
{
if ($i % $n != ($n-1)) { $answer = 0; break; }
}
# check to see if this is an answer and also primality
if($answer == $i && isPrime($answer))
{
print "Answer: $answer\n";
for($n=2; $n<=$max; $n++)
{
$mod = $answer % $n;
$divisor=($answer - $mod)/$n;
print " -> $n ($divisor) + $mod = " . $answer ;
print "\n";
}
print "\n";
$count--;
}
$i++;
}
}
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.