topbanner_forum
  *

avatar image

Welcome, Guest. Please login or register.
Did you miss your activation email?

Login with username, password and session length
  • Friday March 29, 2024, 5:30 am
  • Proudly celebrating 15+ years online.
  • Donate now to become a lifetime supporting member of the site and get a non-expiring license key for all of our programs.
  • donate

Author Topic: Need help in creating an algorithm that calculates rugby scores  (Read 6806 times)

bgd77

  • Supporting Member
  • Joined in 2007
  • **
  • Posts: 203
    • View Profile
    • Donate to Member
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

  • First Author
  • Administrator
  • Joined in 2005
  • *****
  • Posts: 40,896
    • View Profile
    • Mouser's Software Zone on DonationCoder.com
    • Read more about this member.
    • Donate to Member
Re: Need help in creating an algorithm that calculates rugby scores
« Reply #1 on: March 11, 2009, 03:02 AM »
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"
       }
     }
  }


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

  • First Author
  • Administrator
  • Joined in 2005
  • *****
  • Posts: 40,896
    • View Profile
    • Mouser's Software Zone on DonationCoder.com
    • Read more about this member.
    • Donate to Member
Re: Need help in creating an algorithm that calculates rugby scores
« Reply #2 on: March 11, 2009, 03:08 AM »
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

  • Supporting Member
  • Joined in 2007
  • **
  • Posts: 203
    • View Profile
    • Donate to Member
Re: Need help in creating an algorithm that calculates rugby scores
« Reply #3 on: March 11, 2009, 03:57 AM »
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.