I’m working on an MIT open courseware problem. It’s described in full detail here: http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-00-introduction-to-computer-science-and-programming-fall-2008/assignments/pset2.pdf
But, here’ the jist. You can buy Chicken McNuggets in packs of 6, 9, or 20. Using different combinations of these packs you can buy exact amounts of McNuggets. If fact beyond a certain amount, you can buy any amount of McNuggets. The challenge is to write an algorithm that pin points that amount (The largest number that cannot be matched exactly with combinations of 6, 9, and 20).
I believe this is a quadratic algorithm or a linear one. I’d love to know if someone could tell me that as well.
Here’s the code so far:
function mcFinder()
{
$total;
$save;
$count = 0;
for ($n=1;$n<1000;$n++)
{
for ($a=0;$a<10;$a++)
{
for($b=0;$b<10;$b++)
{
for($c=0;$c<10;$c++)
{
$total = $a*6 + $b*9 + $c*20;
if ($total == $n)
{
echo $n . "<br />"; //This is just so I know what matches it's finding.
$count++;
if ($count == 6)
{
echo "The largest number of McNuggest that cannot be bought in exact quantity is " . $save;
return $save;
}
}
else
{
$save = $n;
}
}
}
}
}
}
mcFinder();
Here’s the logic: Hypothesize amounts ($n). If for a given $n there is no combination, save that $n. If there is a match, increment a counter. If we get 6 matches in a row, then all remaining values can be matched, so return the most recently saved $n.
Two bugs: 1) It’s making double matches. For instance it’s returning 18 twice because there are two different ways to reach that total. This messes up the counter. 2) I don’t know how to tell php “for those $n’s where there is no match…”
Would love some help.