LebGeeks

A community for technology geeks in Lebanon.

You are not logged in.

#1 December 2 2013

Ra8
Member

[Exercise] Basket Ball

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

Offline

#2 December 2 2013

yasamoka
Member

Re: [Exercise] Basket Ball

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

Offline

#3 December 2 2013

Ra8
Member

Re: [Exercise] Basket Ball

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.

Offline

#4 December 2 2013

yasamoka
Member

Re: [Exercise] Basket Ball

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

Offline

#5 December 2 2013

Ra8
Member

Re: [Exercise] Basket Ball

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

Offline

#6 December 2 2013

yasamoka
Member

Re: [Exercise] Basket Ball

Can you please explain what that code does?

Offline

#7 December 2 2013

Joe
Member

Re: [Exercise] Basket Ball

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.

A few more things

Offline

#8 December 3 2013

yasamoka
Member

Re: [Exercise] Basket Ball

Understood. Thanks for the explanation!

Offline

#9 December 3 2013

Ra8
Member

Re: [Exercise] Basket Ball

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

Offline

#10 December 3 2013

arithma
Member

Re: [Exercise] Basket Ball

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.

Offline

#11 December 9 2013

rolf
Member

Re: [Exercise] Basket Ball

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?

Offline

#12 December 9 2013

Joe
Member

Re: [Exercise] Basket Ball

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.

Offline

#13 December 9 2013

arithma
Member

Re: [Exercise] Basket Ball

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

Offline

#14 December 9 2013

rolf
Member

Re: [Exercise] Basket Ball

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)

Offline

#15 December 9 2013

Ra8
Member

Re: [Exercise] Basket Ball

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)

Offline

#16 December 9 2013

rolf
Member

Re: [Exercise] Basket Ball

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

Offline

#17 December 9 2013

arithma
Member

Re: [Exercise] Basket Ball

@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)

Offline

#18 December 9 2013

Joe
Member

Re: [Exercise] Basket Ball

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.

Offline

Board footer