Check every rugby for a recursive path without repetition

Question

Just for fun, I created an algorithm that calculates all possible combinations from a given rugby score (3, 5, or 7 points). I found two methods: the first of them is brute force, 3 are impenetrable for loops. Another is recursion.

The problem is that some combinations appear several times. How can i avoid this?

My code is:

 #include <iostream> using namespace std; void computeScore( int score, int nbTryC, int nbTryNC, int nbPenalties ); int main() { int score = 0; while (true) { cout << "Enter score : "; cin >> score; cout << "---------------" << endl << "SCORE = " << score << endl << "---------------" << endl; // Recursive call computeScore(score, 0, 0, 0); } return 0; } void computeScore( int score, int nbTryC, int nbTryNC, int nbPenalties ) { const int tryC = 7; const int tryNC = 5; const int penalty = 3; if (score == 0) { cout << "* Tries: " << nbTryC << " | Tries NT: " << nbTryNC << " | Penal/Drops: " << nbPenalties << endl; cout << "---------------" << endl; } else if (score < penalty) { // Invalid combination } else { computeScore(score - tryC, nbTryC+1, nbTryNC, nbPenalties); computeScore(score - tryNC, nbTryC, nbTryNC+1, nbPenalties); computeScore(score - penalty, nbTryC, nbTryNC, nbPenalties+1); } } 

Answer 1

One way to think about it is to understand that whenever you have a sum, you can put it in some kind of “canonical” form, sorting all the values. For example, given

 20 = 5 + 7 + 3 + 5 

You can also write this as

 20 = 7 + 5 + 5 + 3 

This gives you several different solutions to your problem. Firstly, you can always sort and record all the amounts that you make, never displaying the same amount twice. You have a problem, namely, that you will consistently generate the same amounts several times, which is extremely inefficient.

Another (and much better) way to do this is to update the recursion to work a little differently. Right now, your recursion is working, always adding 3, 5, and 7 at every step. This is what makes everything fail first. An alternative approach would be to think of adding to all 7s that you are going to add, then all 5, and then all 3. In other words, your recursion will work something like this:

  Let kValues = {7, 5, 3} function RecursivelyMakeTarget(target, values, index) { // Here, target is the target to make, values are the number of 7's, // 5's, and 3 you've used, and index is the index of the number you're // allowed to add. // Base case: If we overshot the target, we're done. if (target < 0) return; // Base case: If we've used each number but didn't make it, we're done. if (index == length(kValues)) return; // Base case: If we made the target, we're done. if (target == 0) print values; return; // Otherwise, we have two options: // 1. Add the current number into the target. // 2. Say that we're done using the current number. // Case one values[index]++; RecursivelyMakeTarget(target - kValues[index], values, index); values[index]--; // Case two RecursivelyMakeTarget(target, values, index + 1); } function MakeTarget(target) { RecursivelyMakeTarget(target, [0, 0, 0], 0); } 

The idea here is to add all 7 that you are going to use before adding them to any 5, and add all 5 before you add them to any 3. If you look at the shape of the recursion tree that was made in this way, you will find that no two paths end up trying the same amount, because when the path forks or another number is added, or the recursion decided to start using the next number in the series. Therefore, each amount is generated exactly once, and no duplicates will be used.

In addition, this approach above scales to work with any number of possible values ​​to add, so if rugby introduces a new SUPER GOAL that costs 15 points, you can just update the kValues array and everything will work fine.

Hope this helps!

Answer 2

Each time you find a solution, you can save it in a dictionary (for example, a set of lines with lines similar to "TC-TNT-P")

Before printing the solution, you will make sure that it is not in the dictionary.

Answer 3

A nested for loop is a natural way to do this. Using recursion is just plain stupid (as you seem to have discovered).