3
\$\begingroup\$

I have implemented a dynamic programming solution of the egg-dropping problem (this problem, but generalized for any number of eggs and floors):

#include <iostream>
#include <limits.h>

//Optimal sub-structure
//We have K floor and N eggs
//Case1: If egg break of X floor then we have x - 1 floor and N - 1 egg
//Case2: If egg doesn't break at X floor then we have K - X floor and N eggs
//Base Case1: we have 1 egg then answer is K floor
//Base Case2: we have 0 or 1 floor then 0 or 1 is answer

int cache[1234][1234];

int solve(int egg, int floor) {

    if(floor == 0 || floor == 1 || egg == 1)
        return floor;

    if(cache[egg][floor])
        return cache[egg][floor];

    int result = INT_MAX;
    for(int current_floor = 1; current_floor <= floor; ++current_floor) {
        int local = std::max(solve(egg - 1, current_floor - 1), solve(egg, floor - current_floor));
        if(local < result)
            result = local;
    }

    cache[egg][floor] = 1 + result;
    return cache[egg][floor];
}

int main(void) {

    int egg = 0, floor = 0;
    //egg = 2, floor = 10 result = 4
    std::cin >> egg >> floor;
    std::cout << "result is: " << solve(egg, floor) << '\n';

    return 0;
}

Now I want to implement this solution in C++ template meta-programming, but I am really not getting how I can use the result variable from the solve function to the loop function.

#include <iostream>
#include <climits>

template<int egg, int floor>
struct solve;

template<int current_floor, int egg, int floor>
struct loop {
    static const int r1 = solve<egg - 1, current_floor - 1>::result;
    static const int r2 = solve<egg, floor - current_floor>::result;
    static const int local = r1 > r2 ? r1 : r2;
    //Here I have to compare this local variable to result variable of the
    //solve class and store?
    //In other words I have to implement
    //if(local < result)
    //  result = local 
    loop<current_floor + 1, egg, floor> l;
};

template<int current_floor, int egg>
struct loop<current_floor, current_floor, egg> {
    static const int r1 = solve<egg - 1, current_floor - 1>::result;
    static const int r2 = solve<egg, floor - current_floor>::result;
    static const int local = r1 > r2 ? r1 : r2;
};

template<int egg, int floor>
struct solve {
    static const int result = loop<1, egg, floor>::result + 1;
};

template<int egg>
struct solve<egg, 0> {
    static const int result = 0;
};

template<int floor>
struct solve<1, floor> {
    static const int result = floor;
};

int main(int argc, char** argv) {
    //main function to check program
    return 0;
}
\$\endgroup\$

closed as off-topic by Jamal May 15 '16 at 21:01

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "Questions containing broken code or asking for advice about code not yet written are off-topic, as the code is not ready for review. After the question has been edited to contain working code, we will consider reopening it." – Jamal
If this question can be reworded to fit the rules in the help center, please edit the question.

1
\$\begingroup\$

Template metaprogramming is all about rewriting your program to be functional instead of imperative, and then not worrying about caching since the compiler takes care of that for you. The other important guideline is that the return of a metafunction is a type named type. Template metaprogramming is about types - anything that isn't a type is just really annoying to have to deal with, so stay in the type world for as long as possible.

So how do we write this functionally? Let's look at the loop - which is the only really interesting part of the code:

int result = INT_MAX;
for(int current_floor = 1; current_floor <= floor; ++current_floor) {
    int local = std::max(solve(egg - 1, current_floor - 1), solve(egg, floor - current_floor));
    if(local < result)
        result = local;
}

Rewriting this in Python as a generator comprehension (even if you don't know Python, hopefully this is clear):

result = 1 + min(
           max(solve(egg-1, current-1), solve(egg, floor-current))
           for current in range(1, floor+1)
           )

Going from 1 to floor is a little more awkward than going from 0 to floor-1, so let's just subtract 1 from current everywhere:

result = 1 + min(
           max(solve(egg-1, current), solve(egg, floor-current-1))
           for current in range(floor)
           )

Now, this is the right form for template metaprogramming! So what tools do we need to build this up?

  1. A way to iterate from 0 to floor-1
  2. A way to take the min and max of lots of things at compile time
  3. A way to add one to a type

For the former, we have std::make_index_sequence and the latter two I will leave as an exercise.

Once we have these things though, we directly translate the generator comprehension into actual template code thanks to the power of unpacking variadic templates:

template <int Egg, int Floor, typename = std::make_index_sequence<Floor>>
struct SolveImpl;

template <int Egg, int Floor, size_t... Current>
struct SolveImpl<Egg, Floor, std::index_sequence<Current...>>
{
    using type = add1<                            // result = 1 +
        min<                                      //   min(
            max<                                  //     max(
                Solve<Egg-1, Current>,            //        solve(egg-1, current),
                Solve<Egg, Floor - Current - 1>   //        solve(egg, floor-current-1)
            >...                                  //     ) for current in range(floor)
        >                                         //  )
    >;
};

Dealing with the base cases is just a matter of wrapping with std::conditional:

template <int Egg, int Floor>
struct Solve;

/* the SolveImpl code goes here */

template <int Egg, int Floor>
struct Solve
    : std::conditional_t<
            (Floor == 0 || Floor == 1 || Egg == 1),
            int_<Floor>,
            SolveImpl<Egg, Floor>
            >::type
{ };

Again, leaving out the base case details where Floor == 0, Floor == 1, or Egg == 1 since those are less interesting. As always, with template metaprograms, static_assert is your friend:

static_assert(Solve<2, 10>::value == 4, "!");

Check!

\$\endgroup\$

Not the answer you're looking for? Browse other questions tagged or ask your own question.