A community for technology geeks in Lebanon.

You are not logged in.

- Topics: Active • Unanswered

Pages: **1**

**Ra8****Member**

In Basket Ball you can score 1 point, 2 points or 3 points in 1 shot. In you many ways can your score 50 points (or more generally n points) points?

1 point: 1 way (1)

2 points: 2 ways (2; 1-1)

3 points: 4 ways (3; 2-1; 1-2; 1-1-1)

4 points: 7 ways:

3-1

1-3

2-2

2-1-1

1-1-2

1-2-1

1-1-1-1

You just need to return the number of ways, you don't need the different ways.

I will post my solution in a few hours...

**yasamoka****Member**

```
#include <iostream>
using namespace std;
int basketball(int);
void basketball_child(int&,int&,int&);
int main()
{
int n;
cout << "Enter n: ";
cin >> n;
cout << basketball(n) << endl;
return 0;
}
int basketball(int n)
{
int ways=0;
for(int i=1; i<=3; i++)
basketball_child(n,i,ways);
return ways;
}
void basketball_child(int &n, int &i, int &ways)
{
if(i == n) {
ways++;
return;
}
else if(i > n)
return;
for(int j=1; j<=3; j++) {
i+= 1;
basketball_child(n,i,ways);
}
i-= 3;
}
```

Some recursion.

**Ra8****Member**

yasamoka wrote:

`#include <iostream> using namespace std; int basketball(int); void basketball_child(int&,int&,int&); int main() { int n; cout << "Enter n: "; cin >> n; cout << basketball(n) << endl; return 0; } int basketball(int n) { int ways=0; for(int i=1; i<=3; i++) basketball_child(n,i,ways); return ways; } void basketball_child(int &n, int &i, int &ways) { if(i == n) { ways++; return; } else if(i > n) return; for(int j=1; j<=3; j++) { i+= 1; basketball_child(n,i,ways); } i-= 3; }`

Some recursion.

I think it's correct, but slow, try making it run for n=50 in less than a second.

**yasamoka****Member**

30 and it threw up. Never thought recursion would have *that* much overhead.

**Ra8****Member**

Here's my solution, I can't think of any shorter one..

```
#include <iostream>
using namespace std;
long long T[100]={0,1,2,4};
long long f(long long n)
{
if(n<=0)return 0;
return T[n]=(T[n]!=0)?T[n]:f(n-1)+f(n-2)+f(n-3);
}
int main()
{
cout << f(50) << endl;
return 0;
}
```

**yasamoka****Member**

Can you please explain what that code does?

**Joe****Member**

If you list the first few numbers of the sequence, here's what you get:

```
| n | basketball(n) |
|----+---------------|
| 0 | 1 |
| 1 | 1 |
| 2 | 2 |
| 3 | 4 |
| 4 | 7 |
| 5 | 13 |
| 6 | 24 |
| 7 | 44 |
| 8 | 81 |
| 9 | 149 |
| 10 | 274 |
|----+---------------|
```

It's a sequence that can be defined as:

```
basketball 0 = 1
basketball 1 = 1
basketball 2 = 2
basketball n = basketball (n-1) + basketball (n-2) + basketball (n-3)
```

This sequence is similar to the Fibonacci sequence so it's easily implemented. Fwiw, this definition is executable Haskell code.

This can be easily proven by Mathematical induction.

yasamoka, it's not the recursion that introduced overhead. It's your all-out brute force algo. Look how Ra8's solution takes advantage of recursion in C++ very elegantly (albeit a bit cryptic).

Ra8: You can do shorter, by switching from C++

The Haskell Wiki has a paragraph on the generalization of the Fibonacci sequence to n steps.

**yasamoka****Member**

Understood. Thanks for the explanation!

**Ra8****Member**

Well to explain a little bit more:

To score n points, it's like to score

n-3 points + 1 shot of 3 point, OR

n-2 points + 1 shot of 2 points, OR

n-1 points + 1 shot of 1 point.

@rahmu this is shorter using JS

```
T=[0,1,2,4];
n=5;
for(i=4;i<=n;i++)
T[i]=T[i-1]+T[i-2]+T[i-3];
console.log(T[n]);
```

**arithma****Member**

```
import math
from operator import mul
from functools import reduce
def unique_perms(xs):
s = sum(xs)
return math.factorial(s) / reduce(mul, [math.factorial(x) for x in xs])
def f(n):
result = 0
threes = n/3
for n3 in range(threes+1):
remain3 = n-n3*3
twos = remain3/2
for n2 in range(twos+1):
ones = remain3-n2*2
l = [n3, n2, ones]
result = result + unique_perms(l)
return result
for n in range(100):
print f(n)
```

This generates the different possible arrays of(threes, twos, ones) and then calculates how many unique orderings each has, and sums them up. I should generalise it, but bus coding hurts my head.

**rolf****Member**

rahmu wrote:

It's a sequence that can be defined as:

`basketball 0 = 1 basketball 1 = 1 basketball 2 = 2 basketball n = basketball (n-1) + basketball (n-2) + basketball (n-3)`

Great.

Is there any known procedure or method that describes how to obtain this definition from the given problem data?

**Joe****Member**

Rolf,

Unfortunately none that I know of. To me it's always been calculating a few first values and printing the results until I can find a pattern.

AFAIK, I don't think you can find a generic method that would work on every case.

**arithma****Member**

WTF are you guys talking about?

Have you seen Ra8's explanation?

**rolf****Member**

rahmu wrote:

Rolf,

Unfortunately none that I know of. To me it's always been calculating a few first values and printing the results until I can find a pattern.

AFAIK, I don't think you can find a generic method that would work on every case.

OK thanks :) I tried to find a pattern myself, but maybe I didn't have enough data - I was just looking at the 4 first numbers given by Ra8, and was wondering if math had an answer. Thanks for the tip!

arithma wrote:

WTF are you guys talking about?

Have you seen Ra8's explanation?

I'm afraid I don't understand his code...

*Last edited by rolf (December 9 2013)*

**Ra8****Member**

Let me clarify:

To score 1 point, there is 1 way, 2 points 2 ways and 3 points 4 ways (as I explained in the very first post).

This is the base case of the problem, you have to do these calculations by hand or brute force.

After that, to score 4 points for example:

it is the same as scoring 1 point + 1 shot of 3 points which makes it 1 way ( (1) + 3)

And also you can score 2 points + 1 shot of 2 points which makes them 2 ways ( (2,1-1) +2)

You can also score 3 points +1 shot of 1 point which makes them 4 ways: ( (3,2-1,1-2,1-1-1) +1)

So the total ways of score 4 points is 1+2+4=7

More generally to score n points:

let A1 bet the array of all the different ways you can score n-3 points, append the value 3 to each entry, you have now the first set to get n points

let A2 bet the array of all the different ways you can score n-2 points, append the value 2 to each entry, you have now the second set to get n points

let A3 bet the array of all the different ways you can score n-1 points, append the value 1 to each entry, you have now the third set to get n points

The total is sizeOf(A1) + sizeOf(A2) + sizeOf(A3)

Which then gives the recurrence f(n)=f(n-1)+f(n-2)+f(n-3) with base case 1,2,4 for n=1,2,3

By the way those are the Tribonacci numbers with a different base case.

*Last edited by Ra8 (December 9 2013)*

**rolf****Member**

I think I am starting to get it.

So the core idea, is that you take X (the score) which is bigger than 3, and see all the different ways to reach X+1 (remove 1 point and add 2 points, add one point, remove 3 points and add 2+1 points, etc.) and add the sum of these possibilities to the possibilities of X. It is true that it looks a bit like the Fibonacci algorithm, structurally.

Wait, that doesn't really add up... but well at least I'm halfway there!

(Thanks!)

**arithma****Member**

@rolf: If basketball had four different ways to score for every basket: 1, 2, 4 and 8 then the formula would become:

NumberOfWaysToScore(N) = NumberOfWaysToScore(N-1) + NumberOfWaysToScore(N-2) + NumberOfWaysToScore(N-4) + NumberOfWaysToScore(N-8)

**Joe****Member**

This same method is used in this book to solve another problem. I find it's very well written, maybe it'll help understanding what Ra8 posted.

Pages: **1**