dcsimg
CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 7 of 7

Thread: Increment or double problem

  1. #1
    Join Date
    May 2015
    Posts
    5

    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:
    Name:  Answer.jpg
Views: 267
Size:  16.9 KB

    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

  2. #2
    Join Date
    Jul 2013
    Posts
    576

    Re: Increment or double problem

    Quote Originally Posted by danique View Post
    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
    }
    Last edited by razzle; May 2nd, 2015 at 07:04 AM.

  3. #3
    Join Date
    May 2015
    Posts
    5

    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.
    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
    }

  4. #4
    Join Date
    Jul 2013
    Posts
    576

    Re: Increment or double problem

    Quote Originally Posted by danique View Post
    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.
    Last edited by razzle; May 2nd, 2015 at 11:55 AM.

  5. #5
    Join Date
    May 2015
    Posts
    5

    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.

  6. #6
    Join Date
    Jul 2013
    Posts
    576

    Re: Increment or double problem

    Quote Originally Posted by danique View Post
    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).
    Last edited by razzle; May 6th, 2015 at 02:31 AM.

  7. #7
    Join Date
    May 2015
    Posts
    5

    Re: Increment or double problem

    Wow, Thank you for the great explaination! I really appreciate your help.

Tags for this Thread

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  


Windows Mobile Development Center


Click Here to Expand Forum to Full Width




On-Demand Webinars (sponsored)