1 Attachment(s)
Increment or double problem
Hello everyone,
I have a problem with an assignment. In this assignment I had to create a program which needs to calculate how many different possibilities are there to get from number a to b. To get from a to b you can only D(double) the value or I(increment) the value.
For example a=3 & b=14 you will get:
Code:
DII = 3*2*2+2 = 14
DID = ((3*2)+1)*2 =14
DIIIIIIII = 3*2+8 =14
IDIIIIII=(3+1)*2+6=14
IIDIIII =(3+2)*2+4=14
IIIDII =(3+3)*2+2=14
IIIID =(3+4)*2+0=14
IIIIIIIIIII=3+11=14
This will give me 8 possibilities.
In my current solution I'm using a breadth-first search (BFS) to calculate all the possibilities only this is very slow, because sometimes there are many possibilities and with BFS you will go through all of them. So for example if want to calculate a=10 and b=1000, this will give me 74,116,423 possibilities.
I know a better solution, because people who also did this exercise told me their solution, but I do not understand it.
They used a counting solution. :
Count: (a,b) = (a+1,b) + (2a,b)
Store in table/dictionary
I also asked it in stackoverflow, where I got the same answer:
Attachment 33537
What I understand of this solution is as follows:
Code:
a=3 and b=14
So a[3] += a[3+1] + a[3*2]; will give 2
a[4] += a[4+1] + a[4*2]; will give 2
a[5] += a[5+1] + a[5*2]; will give 2
a[6] += a[6+1] + a[6*2]; will give 3
a[7] += a[7+1] + a[7*2]; will give 2
But the sum of the a's is 11. So I'm doing something wrong, but I can’t figure out what it is.
I hope that someone could tell me what I'm doing wrong.
With kind regards,
Danique
Re: Increment or double problem
Quote:
Originally Posted by
danique
They used a counting solution. :
Count: (a,b) = (a+1,b) + (2a,b)
That is a recursive formulation of the problem. In code it would look like this,
Code:
int count(int a, int b) {
if (a>b) return 0; // no solution
else if (a==b) return 1; // one solution
else return count(a+1,b) + count(2*a,b); // recursively explore all possible combinations of incrementing and
// doubling, and add up all solutions during recursion unwinding
}
Re: Increment or double problem
Thank you for the tip!:)
I've tried your solution and I think it's faster than mine, thanks:).
But I still think this is not the best solution, because with your solution the program still needs to calculate all the possibilties. In the solution they explained to me they explicitly told me to store it in array/dictonary. But I can't figure out how.
To make lesser calculation with your solution you can also only count the b/2 elements, because if you have b/2 you can never double the value, so you will only have to return 1.
Quote:
int count(long a, long b)
{
if (a > (b/2)) return 1; // one solution
else return count(a + 1, b) + count(2 * a, b); // recursively explore all possible combinations of incrementing and
// doubling, and add up all solutions when recursion is unwinding
}
Re: Increment or double problem
Quote:
Originally Posted by
danique
But I still think this is not the best solution,
Well, my intention was just to clarify the recursive solution in principle.
Optimization is another story.
The dictionary strategy they suggested probably was a memoization attempt to avoid repeated calls of the same (expensive) recursive formula. In this case you have this formula (function),
int val = count(a + 1, b) + count(2 * a, b); // pure function - always returns the same val for every specific a (and b)
If a is in the dictionary already you pick val from the dictionary. Otherwise you use the formula to calculate val and afterwards you enter a into the dictionary together with its associated val. The next time a is encountered the a/val combination will be in the dictionary and the formula will never have to be used again for that a. That's memoization.
That's one optimization step you can take. You can also try to use some math result from combinatorics to reduce the whole problem. Maybe there's some symmetry or even a closed formula for your problem.
Re: Increment or double problem
Ah, thank you for the help:).
I always had a hard time understanding the idea of recursive programming/dynamic programming. I'm going to study a bit more on this topic.
Re: Increment or double problem
Quote:
Originally Posted by
danique
I always had a hard time understanding the idea of recursive programming/dynamic programming. I'm going to study a bit more on this topic.
Recursive problem formulations are often succinct and elegant but they have their fair share of problems in practice. One is the risk of running out of stack space, another is the relative slowness of recursive calls. To improve the situation so called tail recursion is often used. Many compilers today can optimize tail recursion into iteration.
In your problem the recursion traverses an imaginary binary tree to generate all combinations. But the left and right branches grow to different depths. One branch (a+1) grows linearly whereas the other (2*a) grows logarithmically. So there is a risk of stack overflow (at the a+1 branch when b is much bigger than a). It would be beneficial if that branch could be turned into tail recursion (and the compiler would optimize it into iteration).
For a recursive call to be in tail position it must be the very last thing that happens before the recursive function is left. This is the original function (slightly modified from my first version).
Code:
int count(int a, int b) { // ordinary recursion
if (a>b) return 0;
if (a==b) return 1;
int tmp = count(2*a,b);
return tmp + count(a+1,b); // count is not in tail position
}
Here when the count call (on the last line) returns, tmp (which has been kept on stack) is added. So count is not in tail position. This can be fixed by way of an accumulator parameter like this (a standard transformation really),
Code:
int count1(int a, int b, int acc=0) { // tail recursion
if (a>b) return acc;
if (a==b) return 1+acc;
int tmp = count1(2*a,b);
return count1(a+1,b,tmp+acc); // count1 is in tail position
}
Now the addition of tmp takes place before the count1 call and the result is passed as a parameter (tmp no longer needs to be kept on stack). This maneuver puts count1 in tail position and we have tail recursion.
I tested this using Visual C++ 2013 Community Edition in release mode with full optimization. With a=10 and b=1000 I got 74,116,423 possibilities as you suggested there should be. The original took 51 seconds and the tail recursive version took 34 seconds. This is a 33% speed increase and it indicates the compiler is performing tail call optimizations indeed.
So with tail recursion the solution became faster (since many recursive calls have been replaced by iteration) and the risk of stack overflow was reduced (since the stack growth is now logarithmically bound rather than linearly).
Re: Increment or double problem
Wow, Thank you for the great explaination! I really appreciate your help.
