Tower of happiness(Beginner Level)

[Tahir33]

Hi,here is another interesting problem that will make you think.
The tower of happiness is located in the garden of effort.Happiness is waiting for you in the top chamber of the tower.The stairs that lead you to the chamber has N steps and you are allowed to climb up one or two steps from your current location. The door of the chamber will open only if you could climb secrt combination. Of course, finding this secret combination is a matter of chance. For instance, you may choose one of three step stairs: 0 1 2 3,or 0 2 3 or 0 1 3.
sample input: 3
sample output: 3

[firstPerson]

Ok, does the tower of happiness has all the happiness that I need ? Does it include megan fox in there? How about the best food in the world? How about a infinite power machine? So seriously, whats your problem?

[stevanity]

I really don't understand the statement of the problem

[Tahir33]

Ok for example you have 3 step ladder how can you climb it?
If N=3 you can climb it 3 ways 0 1 2 3,or 0 2 3 or 0 1 3.
you enter a number in input and then you have to find by how many ways you can reach it. Is it clear?

[Tahir33]

but you can only climb ladders by 1 or 2.

[stevanity]

Oh the objective is just to find out the ways in which we can climb N steps?

[Tahir33]

Oh the objective is just to find out the ways in which we can climb N steps?

yeah you just have to find how many different ways you can climb the ladder OK?
:yawn:

[kes166]

yeah you just have to find how many different ways you can climb the ladder OK?
:yawn:

It's multi sets of the number of steps available. If there are 10 steps, the shortest distance you can get to the top is 5. If there's 11 steps, the shortest distance is 6 rounded up from 5.5. If there's 12, the shortest distance is also 6. Odd steps round up. You would then need to divide that number by 2, and it would give you the amount of possible solutions without repitition.

You'd then need to eliminate the illegal moves. Lets assume 4 steps, 1, 2, 3, 4 (excluding the 0 to make the math easier).
possible moves in 2 steps are:
1,2 2,3 3,4
1,3 2,4
1,4

Send that entire structure to a function to eliminate illegal moves and you are left with
2,4

All other moves are illegal, either taking more than 2 steps or not ending on 4 which are easy conditions to test for.

You then need to repeat the initial function which finds all possible moves, but in 3 steps instead of 4, then again to find all possible moves in 4 steps. Place all legal moves in a structure and throw out all the illegal moves.

[Tahir33]

it isn't right.
your way is not correct
what's 2,4? you have to find how many steps you should do. and 4 is illegal move.

[kes166]

It is correct ... if the steps are 1, 2, 3, 4 then 2 (taking 2 steps) then 4 (taking 2 steps) is a legal move.

1,3 is illegal because you don't end on 4.
3,4 is illegal because to get to step 3 is to many steps.

Anything that doesn't end on 4 is illegal.
If you have 5 steps, anything that doesn't end on 5 is illegal.
etc ....

[Tahir33]

no there's no such condition that allows you move only oe or only two you can use both of them

[kes166]

no there's no such condition that allows you move only oe or only two you can use both of them

If you reread the post, I account for all possible moves either taking 1 step or 2 steps. I did make one mistake in saying divide by 2, but you actually need to divide by k! to find the correct number of permutations where steps aren't reused. (n!/(n-k)!)/k!

In the 4 step example, the least amount of steps you can take is 2, for which there is only one viable solution: 2,4 add to legal struct.

you then find all solutions for taking 3 steps:
1, 2, 3 2, 3, 4
1, 2, 4
1, 3, 4

eliminate illegal moves and you are left with
1,2,4 2,3,4
1,3,4

add them to legal struct

Then all solutions for 4 stps
1,2,3,4

Eliminate illegal moves and you have
1,2,3,4

So you are left with
2,4
1,2,4
1,3,4
2,3,4
1,2,3,4

Only 5 possible solutions for a 4 step tower. It may actually be easier to just generate the entire (n!/(n-k)!) and eliminate redundant moves or back stepping in the elimination function.

[Tahir33]

no youcan do 1,3,4 it's not illegal

[Tahir33]

no there're 7 [possible steps for 4 step tower.

[rpdm]

no there're 7 [possible steps for 4 step tower.

The problem definition is vague, but let's say the rules are like this:

• Step 0 can't be skipped
• At any step, the next step can skipped
• Only one step can be skipped at a time
• The last step can't be skipped

Any list of numbers can be reduced to a binary tree of skip or no skip for each step. If you do that, it's easy to see that the answer is the fibonacci sequence. I even wrote a program to make it apparent. Behold:

#include <iostream>
#include <iomanip>

using namespace std;

struct node
{
    int value;
    node* left;
    node* right;
    node(int value, node* left, node* right)
        : value(value), left(left), right(right) {}
};

void pretty_print(node* root, int level=0)
{
    if (!root)
        return;
    pretty_print(root->right, level + 1);
    cout << setw(level * 4) << "";
    if (root->value != -1)
        cout << root->value << endl;
    else
        cout << "*" << endl;
    pretty_print(root->left, level + 1);
}

void create_tower(node*& root, int step, int max)
{
    if (step >= max)
        return;
    if (!root)
        root = new node(-1, 0, new node(step + 1, 0, 0));
    else
    {
        root->right = new node(step + 1, 0, 0);
        create_tower(root->left, step + 1, max);
    }
    create_tower(root->right, step + 1, max);
}

void print_combinations(node*& root, int path[], int depth)
{
    if (!root)
        return;
    if (root->value != -1)
        path[depth++] = root->value;
    if (!root->left && !root->right)
    {
        for (int x = 0; x < depth; ++x)
            cout << path[x] << " ";
        cout << endl;
    }
    else
    {
        print_combinations(root->right, path, depth);
        print_combinations(root->left, path, depth);
    }
}

int tower_solution(node* root)
{
    if (!root)
        return 0;
    if (!root->left && !root->right)
        return 1;
    return tower_solution(root->left) +
           tower_solution(root->right);
}

int main()
{
    int steps;
    while (cout << "Enter steps> ", cin >> steps)
    {
        node* root = new node(0, 0, 0);
        int path[1024];
        create_tower(root, 0, steps);
        pretty_print(root);
        cout << "Step combinations: " << tower_solution(root) << endl;
        print_combinations(root, path, 0);
    }
}

QED. :)

[Tahir33]

I didn't look yo tour prog you're right answer is fibonacci sequences but it's too long let me show you easier solution:

#include<iostream>
using namespace std;

int main()
{
int n; //the ladder
int currentNum=1;
int previousNum=0;
cout<<"enter the ladders:";
cin>>n;
cout<<endl<<previousNum<<" ";

for(int i=1;i<n;i++)
{
cout<<currentNum<<" ";
currentNum+=previousNum;
previousNum=currentNum-previousNum;
}
system("pause");
return 0;

}

you won't add step in input you just going to find the number of possible combinations.
That's all thanks!!!
Think simpler.
Your computer is too heavy tou are confused.
BE SIMPLER.:)))

[rpdm]

I didn't look yo tour prog you're right answer is fibonacci sequences but it's too long let me show you easier solution:

#include<iostream>
using namespace std;

int main()
{
int n; //the ladder
int currentNum=1;
int previousNum=0;
cout<<"enter the ladders:";
cin>>n;
cout<<endl<<previousNum<<" ";

for(int i=1;i<n;i++)
{
cout<<currentNum<<" ";
currentNum+=previousNum;
previousNum=currentNum-previousNum;
}
system("pause");
return 0;

}

you won't add step in input you just going to find the number of possible combinations.
That's all thanks!!!
Think simpler.
Your computer is too heavy tou are confused.
BE SIMPLER.:)))

Any moron can print the fibonacci sequence. My program does a *lot* more than just solve the problem, and I did it intentionally to show why the fibonacci sequence is the answer. So take your "think simpler" and shove it. :@

[kes166]

I didn't look yo tour prog you're right answer is fibonacci sequences but it's too long let me show you easier solution:

#include<iostream>
using namespace std;

int main()
{
int n; //the ladder
int currentNum=1;
int previousNum=0;
cout<<"enter the ladders:";
cin>>n;
cout<<endl<<previousNum<<" ";

for(int i=1;i<n;i++)
{
cout<<currentNum<<" ";
currentNum+=previousNum;
previousNum=currentNum-previousNum;
}
system("pause");
return 0;

}

you won't add step in input you just going to find the number of possible combinations.
That's all thanks!!!
Think simpler.
Your computer is too heavy tou are confused.
BE SIMPLER.:)))

I don't think the output of the program is going to be what you think it will be. If you are going to turn that in as a homework assingment, you are better off copy and pasting rdpm. A 4 step ladder will output:

enter the ladders: 4

0 1 1 2

According to the Op, outputting the fibonacci numbers is not the solution.

[Tahir33]

how can it be 0 1 1 2 you have to move forward and that's why it can't stay 1 1 and no I din't copy past it if there were a notebook I could explain you by the easier way why it's fibonacci sequences