ATTENTION: You are viewing a page formatted for mobile devices; to view the full web page, click HERE.

Other Software > Developer's Corner

Need help in creating an algorithm that calculates rugby scores

(1/1)

bgd77:
I want to create a simple program in C/C++, as an exercise and for fun, that can say if an number entered by the user (a number between 0 and 250) can be a rugby score and to display all the possible combinations of points.

For those that do not know, in rugby you are awarded 5 points if you score a try, 2 points for a conversion (a conversion always follows a try) and 3 points for a goal kick (through a penalty kick or drop goal). So, for example, 5, 6, 7, 8 and 10 are valid scores, but 4 and 9 are not valid. Probably higher scores are all valid, so the most interesting part would be to display all possible combinations.

The algorithm I thought of using:
1) check if the score can be obtained only by tries or goal kicks (i.e. see if the number is divisible by 5 or 3).
2)
a) for 1 to n tries
b) in each try, for 0 to n conversions
check how many goal kicks are necessary to obtain the score (if it is possible)

Do you think it is a good algorithm? Can it be done in any other way?

If I will manage to create this I will share the program + the source code, if anyone is interested, of course.  :)

Thanks,
bgd77

mouser:
seems like a reasonable algorithm to me.

it might be worth pointing out that because in this particular problem the # of possibilities are so small (to a computer), you could also use the most brute force way of finding all possibilities, something like

for tries = 0 to maxtries
{
for conversions = 0 to maxconversions
{
for goalkicks = 0 to maxgoalkicks
{
if (conversions>tries)
{
// illegal score so skip this one
continue;
}
testscore = tries*5 + conversions*2 + goalkicks*3
if (testscore == score) print "Found a way to achieve score with \$tries , \$conversions, \$goalkicks"
}
}
}
--- End quote ---

i'm not saying to use this, your way is smarter -- just pointing out that sometimes a brute force method is the most straightforward if we are talking about a worse case runtime approaching 1 second :)

mouser:
By the way, some people hate to use brute force algorithms, and work very hard to come up with very efficient clever ways to perform calculations like this.. personally few things please me more than having a program that has to think for a few minutes (or hours or days) to come up with a solution..  ;)

it reminds me of the days when i would go have dinner while the c++ compiler was running.  plus i think it makes my computer happy and it's just a nice warm feeling to know the computer is working so hard doing what it does best.

You just have to be careful because the difference between taking an hour to compute something and taking 1 trillion years to compute it is just a couple of extra for loops, and if you aren't careful you'll find yourself having written some brute force code that is totally unusable.

bgd77:
Thanks for the answer, mouser! Your brute force method seems very interesting, it really got me thinking at the fact that there are some other methods to solving a problem besides algorithms. And in some cases those methods are better. But is it nice to stay and think about how to create a algorithm that solves a problem and then seeing that the algorithm works well (or not - and you have to fix it :)) gives you a very nice feeling.

I will probably implement both methods, to see if we can measure any difference in speed.