Reaching the number 42 by recursion

Question

I am trying to create a bear game where the user enters a number (n), and the program will see if it can reach the number 42 by doing some specified steps. If it can't, then it notifies the user that number can't reach the goal.

These are the rules:

1. If n is even, then you may give back exactly n/2 bears.
2. If n is divisible by 3 or 4, then you may multiply the last two digits of n and give back this many bears.
3. If n is divisible by 5, then you may give back exactly 42 bears.

Here's an example:

• Start with 250 bears
• Since 250 is divisible by 5, you may return 42 of the bears, leaving you with 208 bears.
• Since 208 is even, you may return half of the bears, leaving you with 104 bears.
• Since 104 is even, you may return half of the bears, leaving you with 52 bears.
• Since 52 is divisible by 4, you may multiply the last two digits (resulting in 10) and return these 10 bears. This leaves you with 42 bears.
• You have reached the goal!

Here's what I have so far:

#include <iostream>

using namespace std;

bool bears(int n);

int main(){
    int number;

    do{
        cout<<"enter the amount of bears (press 0 to stop the program): ";
        cin>>number;
        if (bears(number)){
            cout<<"you have reached the goal!"<<endl;
        }

        else{
            cout<<"sorry, you have not reached the goal."<<endl;
        }

    }while(number != 0);
}

bool bears(int n){
    if (n < 42){
        return false;
    }

    else if (n == 42){
        return true;
    }

    else{
        if (n % 5 == 0){
            return bears(n - 42);
        }

        else if(n % 2 == 0){
            return bears(n / 2);
        }

         else if(n % 4 == 0|| n % 3 == 0)
        {
            int one;
            int two;
            one=n%10;
            two=(n%100)/10;
            return bears(n - one * two);
        }  
    }
}

My program has the basic rules, but when I type in 250 bears it says it can't reach the goal. I understand what's happening in the code and why it can't reach the specified goal, but how do I make it universal so it'll work not just for the number 250, but for other numbers like: 84.

Answer 1

@Corristo's answer is good, but a similar depth first search algorithm can be used with minimal changes to your code. I've removed the redundant ifs and elses (since we're returning in every condition).

What this function does is instead of using a greedy approach like your solution does, it tests all cases till it finds an answer. Your code tests the second condition only if the first condition (divisibility by 5) is not satisfied, and so on.

bool bears(int n){
    if (n < 42)
        return false;

    if (n == 42)
        return true;

    // Moves on if condition isn't satisfied
    if ((n % 5 == 0) && bears(n - 42)) return true;

    if ((n % 2 == 0) && bears(n / 2)) return true;

    if(n % 4 == 0|| n % 3 == 0)
    {
        int one;
        int two;
        one=n%10;
        two=(n%100)/10;
        return one * two != 0 && bears(n - one * two);
    }  

    return false;
}

You can try optimizing it further by using a cache (std::map) where you store the results and return the stored result if you have computed it before, but it'll only help in very few cases.

Answer 2

Since we don't have any a priori knowledge about which rule we need to choose for a particular number, the easiest way is to try all of them by exploring the entire state space. You can think of it as a reachability problem in an implicitly given graph.

One way to solve such a reachability problem is by using breath-first or depth-first search, which can be implemented recursively.

For your game this can be done by modifying your bears function to take a std::vector of integers for which it checks if it contains at least one number from which 42 can be reached.

With a depth-first search it might look as follows:

bool bears(std::vector<int> ns) {
    // first remove all numbers < 42 since the goal cannot be reached from them
    ns.erase(std::remove_if(std::begin(ns), std::end(ns),
                            [] (auto const& n) { return n < 42; }),
             std::end(ns));

    if (ns.empty()) {
        return false;
    } else  if (std::any_of(std::cbegin(ns),
                            std::cend(ns),
                            [] (auto const& n) { return n == 42; })) {
        return true;
    } else {
       auto possible_number_of_bears = std::vector<std::vector<int>>{};
       std::transform(std::cbegin(ns),
                      std::cend(ns),
                      std::back_inserter(possible_number_of_bears),
                      [] (auto const& n) {
                            auto after_possible_rules = std::vector<int>{};
                            if (n % 5 == 0) {
                                after_possible_rules.emplace_back(n - 42);
                            }

                            if (n % 2 == 0) {
                                after_possible_rules.emplace_back(n / 2);
                            }

                            if (n % 4 == 0 || n % 3 == 0) {
                                int one;
                                int two;
                                one = n % 10;
                                two = (n % 100) / 10;
                                // avoid infinite recursion by only adding
                                // the new number if it is different from n
                                if (one * two != 0) {
                                    after_possible_rules.emplace_back(n - one * two);
                                }
                            }
                            return after_possible_rules; });
        return std::any_of(std::cbegin(possible_number_of_bears),
                           std::cend(possible_number_of_bears),
                           bears);
    }
}

Now you only need to adjust the calling code to

 if (bears({number})) {
     std::cout << "you have reached the goal!" << std::endl;
 } else {
     std::cout << "sorry, you have not reached the goal." << std::endl;
 }

and modify the forward declaration of bears accordingly.