# LebGeeks

A community for technology geeks in Lebanon.

You are not logged in.

## #1 December 2 2013

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

## #2 December 2 2013

yasamoka
Member

``````#include <iostream>
using namespace std;

int main()
{
int n;
cout << "Enter n: ";
cin >> n;
return 0;
}

{
int ways=0;
for(int i=1; i<=3; i++)

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;
}
i-= 3;
}``````

Some recursion.

## #3 December 2 2013

Ra8
Member

yasamoka wrote:
``````#include <iostream>
using namespace std;

int main()
{
int n;
cout << "Enter n: ";
cin >> n;
return 0;
}

{
int ways=0;
for(int i=1; i<=3; i++)

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;
}
i-= 3;
}``````

Some recursion.

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

## #4 December 2 2013

yasamoka
Member

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

## #5 December 2 2013

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;
}``````

## #6 December 2 2013

yasamoka
Member

Can you please explain what that code does?

## #7 December 2 2013

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

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

## #8 December 3 2013

yasamoka
Member

Understood. Thanks for the explanation!

## #9 December 3 2013

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]);``````

## #10 December 3 2013

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.

## #11 December 9 2013

rolf
Member

rahmu wrote:

It's a sequence that can be defined as:

``````basketball 0 = 1

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

## #12 December 9 2013

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.

## #13 December 9 2013

arithma
Member

WTF are you guys talking about?
Have you seen Ra8's explanation?

## #14 December 9 2013

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)

## #15 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)

## #16 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!)

## #17 December 9 2013

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