Staredit Network > Forums > Null > Topic: Help!
Help!
This topic is locked. You can no longer write replies here.
Feb 20 2008, 5:47 pm
By: InsolubleFluff
Pages: 1 2 3 >
 

Feb 20 2008, 5:47 pm InsolubleFluff Post #1



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!?



None.

Feb 20 2008, 6:44 pm JaFF Post #2



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

Post has been edited 1 time(s), last time on Feb 20 2008, 7:02 pm by JaFF.



None.

Feb 20 2008, 10:41 pm InsolubleFluff Post #3



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.



None.

Feb 20 2008, 10:47 pm Forsaken Archer Post #4



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.



None.

Feb 20 2008, 11:11 pm Forsaken Archer Post #5



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);
    }
}

?>


Post has been edited 2 time(s), last time on Feb 20 2008, 11:35 pm by isolatedpurity.



None.

Feb 20 2008, 11:22 pm cheeze Post #6



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



None.

Feb 20 2008, 11:24 pm InsolubleFluff Post #7



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?



None.

Feb 20 2008, 11:26 pm InsolubleFluff Post #8



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? :O
he specifically said 1 method should of mentioned that I suppose.



None.

Feb 20 2008, 11:27 pm cheeze Post #9



you can't even use helper functions? lame.



None.

Feb 20 2008, 11:29 pm InsolubleFluff Post #10



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



None.

Feb 20 2008, 11:36 pm Forsaken Archer Post #11



edited post...



None.

Feb 21 2008, 5:20 am InsolubleFluff Post #12



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...



None.

Feb 21 2008, 6:01 am Forsaken Archer Post #13



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



None.

Feb 21 2008, 6:11 am Forsaken Archer Post #14



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



None.

Feb 21 2008, 6:40 am cheeze Post #15



ip. you totally copied my algorithm. :(



None.

Feb 21 2008, 7:29 am DT_Battlekruser Post #16



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.



None.

Feb 21 2008, 7:38 am Forsaken Archer Post #17



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



None.

Feb 21 2008, 8:24 am DT_Battlekruser Post #18



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 has 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.


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;
        }
    }

}




None.

Feb 21 2008, 8:36 am Forsaken Archer Post #19



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.



None.

Feb 21 2008, 12:34 pm InsolubleFluff Post #20



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.



None.

Options
Pages: 1 2 3 >
  Back to forum
Please log in to reply to this topic or to report it.
Members in this topic: None.
[2024-5-12. : 8:51 pm]
l)ark_ssj9kevin -- Are you excited for Homeworld 3?
[2024-5-12. : 8:44 pm]
l)ark_ssj9kevin -- Hi Brusilov
[2024-5-12. : 4:35 pm]
O)FaRTy1billion[MM] -- Brusilov
Brusilov shouted: Hey, what happened to EUDDB? Is there a mirror for it somewhere? Need to do a little research.
my server that was hosting it died
[2024-5-10. : 8:46 pm]
NudeRaider -- Brusilov
Brusilov shouted: Hey, what happened to EUDDB? Is there a mirror for it somewhere? Need to do a little research.
https://armoha.github.io/eud-book/
[2024-5-10. : 8:36 am]
Brusilov -- Hey, what happened to EUDDB? Is there a mirror for it somewhere? Need to do a little research.
[2024-5-09. : 11:31 pm]
Vrael -- :wob:
[2024-5-09. : 8:42 pm]
Ultraviolet -- :wob:
[2024-5-08. : 10:09 pm]
Ultraviolet -- let's fucking go on a madmen rage bruh
[2024-5-08. : 10:01 pm]
Vrael -- Alright fucks its time for cake and violence
[2024-5-07. : 7:47 pm]
Ultraviolet -- Yeah, I suppose there's something to that
Please log in to shout.


Members Online: genevaexpression