Given an initial population x, what is the least steps to get to desired population y

Question

Given an initial population x and an exact desired population y, what is the least number of steps to get to y using three functions A{x+1}, B{x+2}, C{x+x}

My approach

#include<iostream>
using namespace std;

int fA (int x)
{
    return x+1;
}
int fB(int x)
{
    return x+2;
}
int fC(int x)
{
    return x+x;
}

int main()
{
    int s, n;
    cin>>s>>n;

    int counter=0;

    while(fC(s)<=n)
    {
        s=fC(s);
        counter++;
    }

    while(fB(s)<=n)
    {
        s=fB(s);
        counter++;
    }

    while(fA(s)<=n)
    {
        s=fA(s);
        counter++;
    }

    cout<<counter;

    return 0;
}

My assumption of starting with the fastest growing function first and the others after that is wrong,

any help would be welcome.

Answer 1

One problem is that what is the "fastest" depends on x. For example with x=0 initially then x+x is not going to grow much, and also with x=1 the fastest is x+2, not x+x.

I'd use a direct full-search approach:

int min_steps(int x, int y) {
    std::set<int> active, seen;
    active.insert(x); seen.insert(x);
    int steps = 0;
    while (active.size() && active.find(y) == active.end()) {
        // `active` is the set of all populations that we can
        // reach in `steps` number of steps or less not greater
        // than the target value `y`.
        // The next set is computed by starting from every value
        // and applying every possible growth function.
        // `seen` is the set of all values we saw before to avoid
        // adding a value that has been checked before.
        steps++;
        std::set<int> new_active;
        for (std::set<int>::iterator i=active.begin(),e=active.end();
             i!=e; ++i) {
            for (int f=0; f<3; f++) {
                int z;
                switch(f) {
                    case 0: z = *i + 1; break;
                    case 1: z = *i + 2; break;
                    case 2: z = *i + *i; break;
                }
                if (z <= y && seen.find(z) == seen.end()) {
                    new_active.insert(z);
                    seen.insert(z);
                }
            }
        }
        active = new_active;
    }
    return active.size() ? steps : -1;
}

Given the look of the graph of the number of steps to get from 1 to x with x <= 1000 my wild guess is however that there's a closed form for the solution: looks not obvious but not totally random...

Answer 2

I'll describe a general strategy with an expectation of the maximum number of function applications. There are 3 cases. Assume x < y in all cases. Consider the source population and the target population numbers as bit strings X and Y.

Case 1 If X and Y bit-by-bit agree in the most significant bits.

A(x) = x + 1 ----> if least significant bit is 0, changes it to a 1. C(x) = x + x = 2*x ----> shifts x bit string left by 1

For example

x = 9 and y = 37, so 
X = 1001, Y= 100101

Thus from above you can shift X left by 2 using C twice 9+9 ---> 18 + 18 ---> 36 or X = 10010 (18) and then 100100 (36) and then add 1 to give 37.

X = {1001,10010,100100,100101}

So 3 applications. So in case 1, the strategy will be to apply C and A repeatedly and build up X to match Y bitwise. This will take 1 C operation for each shift and 1 A operation for making a 1. So in case 1 it will take Length(Y) - Length(X) (the number of C operations) + number of 1's in the least significant significant bits of Y (A operations). In the worst case it's will be all 1s or 2*(Length(Y) - Length(X)). In this case using B doesn't help. The worst case will be O(Length(Y)) = O(log(y))

Case 2 (x < 2)

In this case, using B adds to X faster than C, and in some cases (like described above) using B instead of the general strategy for case 1 will be 1 better.

So if x = 1 and y = 7, instead of

X = {1, 10, 11, 110, 111}, you can skip one step by using B
X = {1, 11, 110, 111}

Case 3. X and Y incompatible.

If X and Y don't agree in the most significant bits, then you need to fix X by applying B and A.

example

X = 110 (6) Y = 101011 (43)

strat  X = {110,1000,1010,10100,10101,101010,101011}

Above, X is fixed to agree with Y in the top 4 significant bits and then once that is accomplished, use strat for case 1. A loose upper bound will be x/2 (applying B x/2 times = x).

Overall the complexity would be predicted to be O(x) + O(log(y)) which appears to generally agree with the accepted answer's graph.