[Exercise] Basket Ball

Ra8

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

#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

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

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

Ra8

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

Can you please explain what that code does?

Joe

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

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++ :p
The Haskell Wiki has a paragraph on the generalization of the Fibonacci sequence to n steps.

yasamoka

Understood. Thanks for the explanation!

Ra8

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 :P 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

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

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

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

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

rolf

rahmu wroteRolf,

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 wroteWTF are you guys talking about?
Have you seen Ra8's explanation?

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

Ra8

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.

rolf

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

@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

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.