Shoretst Sequence of Operations

[alex067]

Hey everyone. Just for fun I am doing this problem:

Consider this puzzle: by starting from the number 1 and repeatedly either adding 5 or multiplying by 3, an infinite set of numbers can be produced. How would you write a function that, given a number, tries to find a sequence of such additions and multiplications that produces that number?

So for example, if the target was 24, the output should be a string:
(((1 * 3) + 5) * 3)

It doesn't have to necessarily be the shortest sequence.


My current code solves this, however the output of the string is causing me an issue. It's outputting the whole iteration, instead of the actual path.

So current, it outputs:
1 +5 +5 +5 +5 +5 *3 *3 *3 *3 +5 +5 *3 *3 *3 +5 +5 +5 +5 +5 *3 *3 *3 *3

It's not removing the false iterations.

My code:

bool find(int current, string &history, int target){
	if (current == target){
		return true;
	}
	else if (current > target){
		return false;
	}
	else{
		return find(current + 5, history = history + " +5 ", target) || find(current * 3, history = history + " *3 " , target);
	}
}

void sequence(int target){
	string history = "1";
	if (find(1, history, target)){
		cout << history << endl;
	}
	else{
		cout << "No Possible Solution" << endl;
	}

}

[toad]

Here's a possible solution:

bool find(int current, string currentHistory, int target, string & targetHistory){
    if (current == target){
        targetHistory = currentHistory;
        return true;
    }
    else if (current > target){
        return false;
    }
    else{
        return 
            find(current + 5, "(" + currentHistory + " + 5)", target, targetHistory) || 
            find(current * 3, "(" + currentHistory + " * 3)", target, targetHistory);
    }
}

void sequence(int target){
    
    string history;

    if (find(1, "1", target, history)){
        cout << history << endl;
    }
    else{
        cout << "No Possible Solution" << endl;
    }

}

[alex067]

I would like to avoid the possibility of 4 parameters in a function, it's just way too much for my liking

[JLBorges]

bool can_reach( int target )
{
    if( target == 1 ) std::cout << "1\n" ;
    else if( target%3 == 0 && can_reach(target/3) ) std::cout << target/3 << " * 3 == " << target << '\n' ;
    else if( target>5 && can_reach(target-5) ) std::cout << target-5 << " + 5 == " << target << '\n' ;
    else return false ;

    return true ;
}

http://coliru.stacked-crooked.com/a/af5069e9ce5a808a

[alex067]

^ very cool! I like the recursive calls in the conditional statements, I am not used to that and haven't seen that syntax before

[toad]

Except, it doesn't satisfy the specification w.r.t. the output. Doing cool stuff that don't satisfy the specification can get you fired in the real world :) The original approach also has the advantage of the find function being side-effect free (if you omit the minimal mutation for returning the path, which can easily be avoided), which is essential for building reusable and composable blocks of computation. If you want to hide the implementation details and provide a better API for the caller, there are ways to do that as well:

#include <iostream>
#include <string>
#include <functional>

using namespace std;


bool find(int target, string & expression) {

    function<bool(int, string)>
    loop = [&](int current, string curExpr) {

        if (current == target){

            expression = curExpr;
            return true;

        } else if (current > target) {
            
            return false;

        } else {
            
            return 
                loop(current + 5, "(" + curExpr + " + 5)") || 
                loop(current * 3, "(" + curExpr + " * 3)");
        }
    };

    return loop(1, "1");
}


int main() {

    string expression;

    if (find(24, expression)) {
        cout << expression << endl;
    } else {
        cout << "No Possible Solution" << endl;
    }
}