I can't understand the wording

[Winsu]

This is the wording of a problem...I understand the target, what I have to do is count the possible ways to climb a ladder having the option of walking just one step or two step(the decision is new each time)...anyway that part the wording explain properly...the trouble comes from the way to output the amount of ways to climb a ladder..it is referenced to a result module of 2^p but it is not clear.....Initially we get two vectors...the vector A is the amount of rungs at a concrete ladder(each element of array A is a different ladder) and vector B is used to expressed in a more compressed way the amount of way to climb a ladder....what I think is returned is the amount of ways of climb a ladder(it is obtained from a fibonacci secuence being N rungs in a ladder then fibonacci(N+1) ways to climb a ladder...example a ladder with 4 rung the fifth number in the fibonacci secuence is the amount of ways) module of 2^B[i]....so with A[i] = 4 and B[i] = 2 it will be...fibonacci(4+1) % (2^2)...this is what I understand but there is an example on the wording and it doesn't match with what I'm thinking....anyone has any different idea??...I guess I must be wrong with the concept of what is a module here or something but I'm not sure....I have pasted the wording in case my explanation is not very accurate...thanks!!!!



You have to climb up a ladder. The ladder has exactly N rungs, numbered from 1 to N. With each step, you can ascend by one or two rungs. More precisely:

with your first step you can stand on rung 1 or 2,
if you are on rung K, you can move to rungs K + 1 or K + 2,
finally you have to stand on rung N.

Your task is to count the number of different ways of climbing to the top of the ladder.

For example, given N = 4, you have five different ways of climbing, ascending by:

1, 1, 1 and 1 rung,
1, 1 and 2 rungs,
1, 2 and 1 rung,
2, 1 and 1 rungs, and
2 and 2 rungs.

Given N = 5, you have eight different ways of climbing, ascending by:

1, 1, 1, 1 and 1 rung,
1, 1, 1 and 2 rungs,
1, 1, 2 and 1 rung,
1, 2, 1 and 1 rung,
1, 2 and 2 rungs,
2, 1, 1 and 1 rungs,
2, 1 and 2 rungs, and
2, 2 and 1 rung.

The number of different ways can be very large, so it is sufficient to return the result modulo 2P, for a given integer P.

Write a function:

vector<int> solution(vector<int> &A, vector<int> &B);

that, given two non-empty zero-indexed arrays A and B of L integers, returns an array consisting of L integers specifying the consecutive answers; position I should contain the number of different ways of climbing the ladder with A[I] rungs modulo 2B[I].

For example, given L = 5 and:
A[0] = 4 B[0] = 3
A[1] = 4 B[1] = 2
A[2] = 5 B[2] = 4
A[3] = 5 B[3] = 3
A[4] = 1 B[4] = 1

the function should return the sequence [5, 1, 8, 0, 1], as explained above.

[dhayden]

there is an example on the wording and it doesn't match with what I'm thinking

Please be specific. Which example doesn't match your thinking? It seems to me that you understand it perfectly.

[Winsu]

The example that is written on the wording...It doesn't match with what I understand...this has been extracted from the wording....
***********************************************************************
For example, given L = 5 and:
A[0] = 4 B[0] = 3
A[1] = 4 B[1] = 2
A[2] = 5 B[2] = 4
A[3] = 5 B[3] = 3
A[4] = 1 B[4] = 1

the function should return the sequence [5, 1, 8, 0, 1], as explained above.
***********************************************************************
This is how I would do this according what I understand

for example fibonacci serie is. [0,1,1,2,3,5,8,13,21....]

so A[0] and B[0] would be 5%2^3 ->5/8 = 0,625 being its module 6
A[1] and B[1] would be 5%2^2-> 5/4 = 1,25 being its module 2
A[2] and B[2] would be 8%2^4-> 8/16 = 0,5 being its module 5
A[3] and B[3] would be 8%2^3-> 8/8 = 1 being its module 0
A[4] and B[4] would be 1%2^1-> 1/2 = 0,5 being its module 5

My resulting vector is [6,2,5,0,5] and the resulting vector according to the wording is [5,1,8,0,1]so they don't match......that's why I know I'm doing something wrong...

[TheIdeasMan]

Hi,

so A[0] and B[0] would be 5%2^3 ->5/8 = 0,625 being its module 6

A couple of things here:

1. I interpret it as being 2 * B[I] , but you have 2^B[I]
2. You are doing division instead of modulus, mod is remainder.

So I interpret them as being :

A[0] and B[0] 5 % (2 * 3) == 5
A[1] and B[1] 5 % (2 * 2) == 1
A[2] and B[2] 8 % (2 * 4) == 0
A[3] and B[3] 8 % (2 * 3) == 2
A[4] and B[4] 1 % (2 * 1) == 1

Edit:
So I get a different answer for A[2] and A[3], the others I agree


So I had [5 1 0 2 1], but they had [5,1,8,0,1] so my 3rd and 4th were different.

Hope all is well :+)

[Winsu]

Thanks...the point is while I don't know what they do...I can't start coding the solution that I think it would not be so difficult....thanks but I think it is neither 2 * B[I] nor 2B[I]...

[TheIdeasMan]

but I think it is neither 2 * B[I] nor 2B[I]...

But those are equivalent. In the second one the multiplication is implied - like in math 2B means 2 * B.

so it is sufficient to return the result modulo 2P, for a given integer P.

This is the same. Unless we are missing some formatting?

Can you provide a link to the website which has the actual question. Just to be sure, to be sure :+)

[Winsu]

ehhehe, that's true, it was a formatting problem I meant this... 2 * B[I] and 2^B[i]....yes ofcourse...here is the link https://codility.com/programmers/task/ladder

[TheIdeasMan]

Ok

Going back and doing modulus not division, we have :

A[0] and B[0] 5 % (2³) == 5
A[1] and B[1] 5 % (2²) == 1
A[2] and B[2] 8 % (2⁴) == 8
A[3] and B[3] 8 % (2³) == 0
A[4] and B[4] 1 % (2¹) == 1 // excellent, there is 1 rung, so 1 way to do it !!

So this gives the same answers as what they had :+)

L is an integer within the range [1..30,000];

As is always the way with these, brute force doesn't work, one has to come up with some other cunning plan :+)

The problem here is the 30000 fib number is way too huge, even using a big number library the cost of calculating it would be ridiculous. There is probably some other particularly clever and elegant way of doing this.

There is probably some sort of pattern, or way of using the previous result to calc the next one. So my instinct would be to get it working for some small numbers, then look for patterns.

It is not clear as to where to get the arrays A and B from.

[Winsu]

Could you explain in detail what you understand for modulus...because I was doing what you, but I have been getting other result???....and yes...I can say to you in advance I have been looking for solution and the trouble is that power operation apparently cost a lot so the code must avoid use that operation...for that reason the use shift operator...I'm not sure why yet...but the code that I have seen use that......


going back to the modulus...for me a modulus is for example 3/2....1,5 is the normal division...and 5 is its modulus.....i think I'm doing bad this....but operator % brings that.......

[Winsu]

I have just got it...oh my god...sometimes the easiest things are the hardest things....it's the remainder...and just that...it's not the right part of the result after the coma as I was thinking....now I can code,ehhehehe

[TheIdeasMan]

now I can code,ehhehehe

What did you think of my earlier comments?

TheIdeasMan wrote:

The problem here is the 30000 fib number is way too huge, even using a big number library the cost of calculating it would be ridiculous. There is probably some other particularly clever and elegant way of doing this.

There is probably some sort of pattern, or way of using the previous result to calc the next one. So my instinct would be to get it working for some small numbers, then look for patterns.

So I noticed that array A could go from 1 to 30000, and array B might be always 1 or 2 less than the number in A.

Also, look at what the effect of incrementing (by one) the number of rungs is.

the trouble is that power operation apparently cost a lot so the code must avoid use that operation.

I am not sure whether c++11 pow function overloads are smart enough to do multiplication when the argument is an int, as opposed to doing a binomial expansion. Might pay to ask someone about that, I am not sure. Actually I will ask myself :+)

Good Luck !!

[Winsu]

I don't know what I was thinking before...i guess I was a bit blunt...

Any element from vector B can be from 1 to 30....and pow function doesn't get int..i have already checked it...but we can always cast a double to a int...in this concrete case there won't be lose of information....I'm getting a trouble with operator %.....for the rest I think It will work , not with a good performance but It's a beggining...

#include <stdio.h>
#include <vector>
#include <iostream>
#include <cmath>

using namespace std;


vector<int> solution(vector<int> &A, vector<int> &B){
	vector<int>::iterator itA;
	vector<int>::iterator itB;
	vector<int> fibo;
	vector<int> myvector;
	for(itA = A.begin(),itB = B.begin();itA != A.end();itA++,itB++){
		if(*itA == 0) myvector.push_back(0);
		 else if(*itA == 1)myvector.push_back(1);
		 else{
			fibo.push_back(0);
			fibo.push_back(1); 
			for(int i = 2;i != *itA + 1;i++){
			fibo[i] = fibo[i-1]+ fibo[i-2];
			}
		 }
		
		myvector.push_back(fibo.back() % pow(2,*itB));
		fibo.erase(fibo.begin(),fibo.end());
	}
	
	return myvector;
}

[TheIdeasMan]

and pow function doesn't get int..i have already checked it

The pow function does take an int as the exponent, but you are right - it is immediately cast to double.

http://en.cppreference.com/w/cpp/numeric/math/pow

So no need to worry about casting anything, and you probably should use your own power function with the shift operator. Sorry for the confusion there.

[Winsu]

This code works at 75% pf correctness and 0% of performance...

#include <stdio.h>
#include <vector>
#include <iostream>
#include <cmath>

using namespace std;


vector<int> solution(vector<int> &A, vector<int> &B){
	vector<int>::iterator itA;
	vector<int>::iterator itB;
	vector<int> fibo;
	vector<int> myvector;
	for(itA = A.begin(),itB = B.begin();itA != A.end();itA++,itB++){
		if(*itA == 0) myvector.push_back(0);
		 else if(*itA == 1)myvector.push_back(1);
		 else{
			fibo.push_back(0);
			fibo.push_back(1); 
				for(int i = 2;i <= *itA + 1;i++){
				fibo.push_back(fibo[i-1]+ fibo[i-2]);
				}
				int hold = pow(2,*itB);
				
				myvector.push_back(fibo.back() % hold);
				fibo.erase(fibo.begin(),fibo.end());
			}
	}
		 
		
	
	return myvector;
}

I don't know how to use the shift operator to save time in the pow operation...

[TheIdeasMan]

I don't know how to use the shift operator to save time in the pow operation...

You can use the << operator to shift the bits of an int a number of places to the left, this is the same as multiplying by a power of 2.

int mult_by_pow_2(int number, int power)
{
    return number<<power;
}

http://www.cprogramming.com/tutorial/bitwise_operators.html

I would calc all the fib numbers in a separate function, rather than doing it inside you other loops. That nested loop takes the complexity to O(N²)

The basic problem is still going to be that your numbers will exceed the size that the built in integral types can handle.

Any way , it's late for me at this end (07:30am) need to stack ZZzzzzz's

[Winsu]

yes, I got that, the shift operator does the pow operation because the binary code is base 2...it's simple and efficient......by the way, are you from Australia or about??

[TheIdeasMan]

by the way, are you from Australia or about??

Yes, from NZ originally but have been here in Oz for 18 years now, so am happy with results of the Rugby :+)

With your code, how are you getting on?

I was thinking about writing some code myself, just to demonstrate the concept of separation of the Fib numbers from the rest of the code.

Was also going to only process the first 40, to see if there is a pattern of some sort.

[Winsu]

About the Rugby...I'm a Spanish living in London, so maybe I 'll have a paint tomorrow watching the match...they are really surprised ( and upset too) about the final...congratulations then!!!

well this is the best I have got...

#include <stdio.h>
#include <vector>
#include <iostream>
#include <cmath>
//not 100/100
using namespace std;


vector<int> solution(vector<int> &A, vector<int> &B){
	vector<int>::iterator itA;
	vector<int>::iterator itB;
	vector<int> fibo;
	vector<int> myvector;
	for(itA = A.begin(),itB = B.begin();itA != A.end();itA++,itB++){
		if(*itA == 0) myvector.push_back(0);
		 else if(*itA == 1)myvector.push_back(1);
		 else{
			fibo.push_back(0);
			fibo.push_back(1); 
				for(int i = 2;i <= *itA + 1;i++){
				fibo.push_back(fibo[i-1]+ fibo[i-2]);
				}
				long hold = 1<<*itB;
				
				myvector.push_back(fibo.back() % hold);
				fibo.erase(fibo.begin(),fibo.end());
			}
	}
		 
		
	
	return myvector;
}

Normally I try to get 100% in performance and 100% in correctness but this case is beating me up, I don't know how to improve it....You said about creating a independent function for get the fibonacci numbers..but I will have the same complexity I guess...or maybe I don't see it like you do...


I think is a good idea, or why not try to get the wording done.....and get 100% in both targets, it's quite addictive

[TheIdeasMan]

but I will have the same complexity I guess...or maybe I don't see it like you do...

No you won't, at the moment you have a for loop for the fib numbers inside the other for loop. So that makes it at least O(N²)

By separating them and assuming they both run N times, then it will be O(2N)

Calculating the fib numbers only needs to be done once, as does the initialisation of the A and B vectors. After that just do a "LookUp" of the value required.

At the moment you are unnecessarily recalculating the fib numbers N times.

I suggested only do a small number first, then look for patterns. It is the nature of these problems, brute force doesn't work - one has to come up with a clever plan.

Also with your code:

Don't have unneeded includes, particularly avoid mixing c and C++ style - you have stdio.h

Don't have using namespace std; it defeats the purpose of having namespaces. Google to read up about namespaces. The easiest thing to do is put std:: before each std thing, that is what all the expert coders do. Ideally ones own code should go into it own namespace/s

I would avoid having those vectors as local variables, pass them by reference into the functions instead.

You can avoid using the iterators, by employing a range based for loop instead - this is suitable because you are processing the whole container.

Always use braces for statements inside an if or loop or whatever, even if there is only 1 statement. This will save you one day when you add more code.

[ne555]

> The problem here is the 30000 fib number is way too huge, even using a big number library the cost of calculating it would be ridiculous. There is probably some other particularly clever and elegant way of doing this.

(a + b) mod m = (a mod m + b mod m) mod m
you need to store all the fib sequence for each possible modulo.


> Always use braces for statements inside an if or loop or whatever, even if there is only 1 statement. This will save you one day when you add more code.
I'd rather learn to indent.