Okay, so this is a math problem that I am doing in computer information science. The idea is that the user inputs how many "McFuPucks" they wish to buy, then you must call a method that will find out if they can buy that number of McFuPucks. The McFuPucks come in boxes of 6,9 and 20. So for examples: Example1: Input number of pucks you would like to purchase: 15 That's Buyable. Example2: Input number of pucks you would like to purchase: 70 That's Buyable. Example3: Input number of pucks you would like to purchase: 31 That's not Buyable. Solutions: Example1: 1*6 + 1*9 = 15. Example2: 2*6 + 2*9 + 2*20 = 70. Example3: There is no combination of 6,9 or 20 packs that will yield 31 pucks. Help!?

Okay, so this is a math problem that I am doing in computer information science.

The idea is that the user inputs how many "McFuPucks" they wish to buy, then you must call a method that will find out if they can buy that number of McFuPucks. The McFuPucks come in boxes of 6,9 and 20. So for examples:

Example1:
Input number of pucks you would like to purchase: 15
That's Buyable.
Example2:
Input number of pucks you would like to purchase: 70
That's Buyable.
Example3:
Input number of pucks you would like to purchase: 31
That's not Buyable.

Solutions:
Example1: 1*6 + 1*9 = 15.
Example2: 2*6 + 2*9 + 2*20 = 70.
Example3: There is no combination of 6,9 or 20 packs that will yield 31 pucks.

Help!?

Though my knoweledge of programming is limited... here's my suggestion: -Add the maximum number of biggest boxes possible that were not used. This means that if you need 19 pucks, you take 3 boxes with 9 pucks in each. If you need 21 pucks, you take one 20-puck box -Subtract the resulting number of pucks from the needed -Repeat until you get a situation where the number of pucks left to provide is smaller than the capacity of the smallest box OR until you win. If it's the first scenario, you subtract one from the last box type which you added and repeat again (if the last box type you added was the smallest one, you subtract from the pre-last type; i). In toher words, if you need 42, your actions are the following: 2*20 + 0*9 + 0*6 - fail (40) 1*20 + 2*9 + 0*6 - fail (38) 1*20 + 1*9 + 2*6 - fail (41) 1*20 + 0*9 + 3*6 - fail (38) 0*20 + 4*9 + 1*6 - win Yeah, it's probably the dumbest method possible, but it should work. :P

Though my knoweledge of programming is limited... here's my suggestion:
-Add the maximum number of biggest boxes possible that were not used. This means that if you need 19 pucks, you take 3 boxes with 9 pucks in each. If you need 21 pucks, you take one 20-puck box
-Subtract the resulting number of pucks from the needed
-Repeat until you get a situation where the number of pucks left to provide is smaller than the capacity of the smallest box OR until you win. If it's the first scenario, you subtract one from the last box type which you added and repeat again (if the last box type you added was the smallest one, you subtract from the pre-last type; i). In toher words, if you need 42, your actions are the following:
2*20 + 0*9 + 0*6 - fail (40)
1*20 + 2*9 + 0*6 - fail (38)
1*20 + 1*9 + 2*6 - fail (41)
1*20 + 0*9 + 3*6 - fail (38)
0*20 + 4*9 + 1*6 - win

Yeah, it's probably the dumbest method possible, but it should work.

well im sure your method works i don't think it's quite practical for programming, the hint that he gave us was how to solve for just 6. if(n == 0) { return true; } else if(n < 0) { return false; } else { return buyables(n - 6) } this piece of code works for all the multiples of 6, before anyone suggests repeating that code, that will only get multiples of 6 9 and 20, i still need the combinations. He also hinted that the code is not very practical in the sense that it finds every single possible answer because of the recursion, however since a computer works fast, it wont matter because it should only take a split second. So i am thinking that buy making some kind of equations to solve every single number from 6 to the user inputted number (inclusive) then I can say either yes it is or no it is not. In that case, it shouldn't be too hard to solve, if that is not the case, then I could be screwed xD I think I have all of tomorrow and maybe the day after to solve this, so help is appreciated.

well im sure your method works i don't think it's quite practical for programming, the hint that he gave us was how to solve for just 6.

if(n == 0)
{
return true;
}
else if(n < 0)
{
return false;
}
else
{
return buyables(n - 6)
}

this piece of code works for all the multiples of 6, before anyone suggests repeating that code, that will only get multiples of 6 9 and 20, i still need the combinations.

He also hinted that the code is not very practical in the sense that it finds every single possible answer because of the recursion, however since a computer works fast, it wont matter because it should only take a split second.

So i am thinking that buy making some kind of equations to solve every single number from 6 to the user inputted number (inclusive) then I can say either yes it is or no it is not. In that case, it shouldn't be too hard to solve, if that is not the case, then I could be screwed xD

I think I have all of tomorrow and maybe the day after to solve this, so help is appreciated.

Does it have to be good code or can it be hacked to just that specific situation? You will never need more than 2 boxes of 6, because 3 pairs = 2 pairs of 9.

Does it have to be good code or can it be hacked to just that specific situation?
You will never need more than 2 boxes of 6, because 3 pairs = 2 pairs of 9.

http://www.staredit.net/pucks.php it doesn't give the puck make up though... yet [code]<?php echo <<< EOF input pucks: <br /> <form method="post" action="?pucks.php"> <input name="pucks" value="{$_POST['pucks']}" type="text" /> <input name="submit" value="submit" type="submit" /> </form> EOF; if ($_POST['pucks'] && ctype_digit($_POST['pucks']) && $_POST['pucks'] > 0) { $p = $_POST['pucks']; $valid = array(6, 9, 20); array_walk($valid, 'walk', $p); echo "lose";exit; } function win() { echo "win"; exit; } function walk($v, $k, $p) { echo $p . "<br />"; if ($p - $v === 0) { win(); } else { $p -= $v; $valid = array(6, 9, 20); foreach($valid as $a => $b) if ($p < $b) unset($valid[$a]); if (count($valid)) array_walk($valid, 'walk', $p); } } ?>[/code]

http://www.staredit.net/pucks.php
it doesn't give the puck make up though... yet

Use recursion. Have a method that takes the input. Then have three methods that checks 6, 9 and 20. Have each method call each other recursively and return the boolean through the OR statement. ..does that make sense? :o

Use recursion. Have a method that takes the input. Then have three methods that checks 6, 9 and 20. Have each method call each other recursively and return the boolean through the OR statement.

..does that make sense?

that works fantastically, I don't think it actually need to say the puck make up, just needs to return true or false (true saying that you can buy that many, false saying you cannot) wanna explain how you did it so I can try to do it in java?

that works fantastically, I don't think it actually need to say the puck make up, just needs to return true or false (true saying that you can buy that many, false saying you cannot)

wanna explain how you did it so I can try to do it in java?

[quote=cheeze]Use recursion. Have a method that takes the input. Then have three methods that checks 6, 9 and 20. Have each method call each other recursively and return the boolean through the OR statement. ..does that make sense? :o[/quote] he specifically said 1 method should of mentioned that I suppose.

Quote from cheeze

Use recursion. Have a method that takes the input. Then have three methods that checks 6, 9 and 20. Have each method call each other recursively and return the boolean through the OR statement.

..does that make sense?

he specifically said 1 method should of mentioned that I suppose.

you can't even use helper functions? lame.

you can't even use helper functions? lame.

we're allowed a main method to call the "buyables" method, from then on buyables has to call upon itself.

we're allowed a main method to call the "buyables" method, from then on buyables has to call upon itself.

edited post...

edited post...

thanks, sorry was at work. Do you think you could try explaining the code or something, I understand a little bit of PHP but I can't really understand everything that's going on...

thanks, sorry was at work.
Do you think you could try explaining the code or something, I understand a little bit of PHP but I can't really understand everything that's going on...

my shitty variable names probably don't help if ($_POST['pucks'] && ctype_digit($_POST['pucks']) && $_POST['pucks'] > 0) { $p = $_POST['pucks']; // $p = input from form $valid = array(6, 9, 20); // simple array of what's a valid purchase count array_walk($valid, 'walk', $p); // array_walk (for each member of array, do this function) so for each value in $valid, call function 'walk' with variable $p echo "lose";exit; // we didn't achieve win, so we must have achieved lose } function win() { echo "win"; exit; } function walk($v, $k, $p) { echo $p . "<br />"; if ($p - $v === 0) // if p - current value from valid equals 0, we won { win(); } else { $p -= $v; // p equals p minus current value from valid array $valid = array(6, 9, 20); // redclared valid array for this scope // lazy foreach($valid as $a => $b) // for each member in array $valid, use $a as array key, $b as array value if ($p < $b) // attempt to save unncessary calls, not entirely sure if this works... but if $p is less than any one value in the valid array, unset that value so we don't call walk on it again unset($valid[$a]); // cont from above if (count($valid)) // // cont from above -- if we still have valid values, array walk them again array_walk($valid, 'walk', $p); } } so basically, it takes the inputed value, x, and subtracts 6, 9, and 20 from it if x is still above 6, 9, 20, subtract appropiate numbers again repeat as necessary (the recursive part of it) eventually, we get to a point where if 6, 9, or 20 doesn't fit into x, we lost if we get a 0, we won

my shitty variable names probably don't help

if ($_POST['pucks'] && ctype_digit($_POST['pucks']) && $_POST['pucks'] > 0)
{
$p = $_POST['pucks']; // $p = input from form
$valid = array(6, 9, 20); // simple array of what's a valid purchase count
array_walk($valid, 'walk', $p); // array_walk (for each member of array, do this function) so for each value in $valid, call function 'walk' with variable $p
echo "lose";exit; // we didn't achieve win, so we must have achieved lose

}

function win()
{ echo "win"; exit; }

function walk($v, $k, $p)
{
echo $p . "<br />";
if ($p - $v === 0) // if p - current value from valid equals 0, we won
{
win();
}
else
{
$p -= $v; // p equals p minus current value from valid array
$valid = array(6, 9, 20); // redclared valid array for this scope // lazy
foreach($valid as $a => $b) // for each member in array $valid, use $a as array key, $b as array value
if ($p < $b) // attempt to save unncessary calls, not entirely sure if this works... but if $p is less than any one value in the valid array, unset that value so we don't call walk on it again
unset($valid[$a]); // cont from above
if (count($valid)) // // cont from above -- if we still have valid values, array walk them again
array_walk($valid, 'walk', $p);
}
}


so basically, it takes the inputed value, x, and subtracts 6, 9, and 20 from it
if x is still above 6, 9, 20, subtract appropiate numbers again
repeat as necessary (the recursive part of it)
eventually, we get to a point where if 6, 9, or 20 doesn't fit into x, we lost
if we get a 0, we won

replacing array_walk in both instances with something like foreach($i = 0; $i < array_length($valid), $i++) { walk($valid[i]); } would probably be a lot more java-like ;o

replacing array_walk in both instances with something like
foreach($i = 0; $i < array_length($valid), $i++)
{
walk($valid[i]);
}

would probably be a lot more java-like ;o

ip. you totally copied my algorithm. :(

ip. you totally copied my algorithm.

[color=#b5b5ff]I spent 20 minutes trying and failing to come up with a better way to do this so any of the brute-forcing algorithms given would work.[/color]

[quote=cheeze]ip. you totally copied my algorithm. :([/quote] eh... even though i had it hosted on sen, working, 11 minutes before you even posted? ;o

Quote from cheeze

ip. you totally copied my algorithm.

eh... even though i had it hosted on sen, working, 11 minutes before you even posted? ;o

[color=#b5b5ff]Here's an algorithm I wrote in Java. Too lazy to actually see if this is less or more cycles than IP's algorithm - they both suffer from the fact that it takes forever long to calculate huge numbers. I am still thinking there [i]has[/i] to be a faster way than bruteforcing this. Actually, on second thought, what this really is is prime factorization, and according to my cryptography book on RSA/PGP, there isn't a known better way to factor than by guess-and check. If it wasn't so damn late I would write an array-expansive modulus stringing algorithm, but I really need to sleep. Maybe tomorrow, if I'm bored.[/color] [code]import java.util.Scanner; public class IntCombiner { public static void main(String[] args) { Scanner in = new Scanner(System.in); while (true) { System.out.print("Number: "); int i = in.nextInt(); int[] boxSizes = {6,9,20}; if (i == 0) break; System.out.println(doableWithArray(i, boxSizes)); } } private static boolean doableWithArray(int target, int[] array) { int n = 0; while (true) { if (n == target) return true; if (array.length > 1) { int[] shortArray = new int[array.length - 1]; // Too lazy to use ArrayList for (int i = 1; i < array.length; i++) { shortArray[i - 1] = array[i]; } if (doableWithArray(target - n, shortArray)) return true; } n += array[0]; if (n > target) return false; } } }[/code]

I think, for really huge numbers, it might be better to reorganize the array as 20, 9, 6... Or at least, 9, 6, 20 as 6 + 9 combine at a very low multiple. Something I don't care to try. I did get puck output working though... however, because I didn't think of this earlier, I got 6*10 + 1*20 and was like wtf, I quit.

I think, for really huge numbers, it might be better to reorganize the array as 20, 9, 6...
Or at least, 9, 6, 20 as 6 + 9 combine at a very low multiple. Something I don't care to try. I did get puck output working though... however, because I didn't think of this earlier, I got 6*10 + 1*20 and was like wtf, I quit.

Wow you guys have been fantastically helpful, thank you so much, now in class all I have to really do is re-write it to make it look like my own (copyright is bad kids :P) and then actually re-read and fully understand, for in a couple of weeks we're supposed to be getting one that is a lot harder then this one, which sucks seeing as I was away for 2 lessons on recursion / working on a recursive problem. Anyways, once again, thank you.

Wow you guys have been fantastically helpful, thank you so much, now in class all I have to really do is re-write it to make it look like my own (copyright is bad kids ) and then actually re-read and fully understand, for in a couple of weeks we're supposed to be getting one that is a lot harder then this one, which sucks seeing as I was away for 2 lessons on recursion / working on a recursive problem. Anyways, once again, thank you.