You are given a score

`$S`

.You can win basketball points e.g. 1 point, 2 points and 3 points.

Write a script to find out the different ways you can score

`$S`

.

`Input: $S = 4 Output: 1 1 1 1 1 1 2 1 2 1 1 3 2 1 1 2 2 3 1 Input: $S = 5 Output: 1 1 1 1 1 1 1 1 2 1 1 2 1 1 1 3 1 2 1 1 1 2 2 1 3 1 2 1 1 1 2 1 2 2 2 1 2 3 3 1 1 3 2`

The Tribonacci Numbers are defined as follows:

\[ \mathcal{T}(n) = \begin{cases} 0 & \text{if } n \leq 1 \\ 1 & \text{if } n = 2 \\ \mathcal{T}(n - 3) + \mathcal{T}(n - 2) + \mathcal{T}(n - 1) & \text{if } n > 2 \end{cases} \]

This sequence is found at the OEIS as A000073.

There is a formula to calculate \(\mathcal{T}(n)\) directly, in a similar was there is one for the Fibonacci numbers:

\[ \mathcal{T}(n) = \left\lfloor \frac{3 \left(\sqrt[3]{586 + 102\sqrt{33}}\right) \left(\frac{1}{3}(\sqrt[3]{19 + 3\sqrt{33}} + \sqrt[3]{19 - 3\sqrt{33}} + 1)\right)^n} {\left(\sqrt[3]{586 + 102\sqrt{33}}\right)^2 - 2\sqrt[3]{586 + 102\sqrt{33}} + 4} \right\rceil \]

Now, the number of ways to decompose a non-negative integer \(N\) as a sum
of `1`

s, `2`

s, and `3`

s, is equal to \(\mathcal{T}(N + 2)\).

But we don't have to calculate the number of ways to decompose a score, we actually have to calculate all the different ways to decompose a given score.

The definition of the Tribonacci Numbers gives us a way to calculate the all the different decompositions. Let \(\mathcal{S}(n)\) be the set of all decompositions of a score of \(n - 2\). Then

\[ \mathcal{S}(n) = \begin{cases} \emptyset & \text{if } n \leq 1, \\ \{ \text{""} \} & \text{if } n = 2 \\ \{ \forall x \in \mathcal{S}(n - 1): \text{"1"} \odot x \} \; \cup & \\ \{ \forall x \in \mathcal{S}(n - 2): \text{"2"} \odot x \} \; \cup & \text{if } n > 2 \\ \{ \forall x \in \mathcal{S}(n - 3): \text{"3"} \odot x \} & \end{cases} \]

where \(\odot\) is the concatenation operator.

That is, we can decompose a score of \(n\) by either first scoring a \(1\) and then decomposing a score of \(n - 1\), or first scoring a \(2\) and then decomposing a score of \(n - 2\), or first scoring a \(3\) and then decomposing a score of \(n - 3\).

The definition given above suggests using a recursive solution. This is possible, but instead, we will be using an iterative solution.

We will reading the `n`

from standard input.

We start off by initializing the first three sets, \(\mathcal{S}(0), \mathcal{S}(1), \mathcal{S}(2)\):

```
my @s = ([], [], [""]);
```

Thus two empty sets, and a set consisting of an empty string.

We now repeatedly (`n`

times) add a next set, using the last three
sets:

```
map {push @s => [map {my $s = $_; map {"$s $_"} @{$s [-$s]}} 1 .. 3]} 1 .. <>;
```

We can rewrite this using nested `for`

loops instead of `map`

s to make
it clear what is happening:

```
for (1 .. <>) {
my @new;
for my $s (1 .. 3) {
for my $decomposition (@{$s [-$s]}) {
push @new => "$s $decomposition";
}
}
push @s => \@new;
}
```

A new set is created by taking all the decompositions for the last
three sets, and prepending them with `1`

, `2`

, or `3`

.

At the end, we have to print the elements of the last set:

```
say for @{$s [-1]}
```

Find the full program on GitHub.

We will be using two arrays, `c`

, and `s`

. `s [i]`

will contain
all the decompositions of a score of `i`

, while `c [i]`

will contain
the number of decompositions of a score of `i`

.

First, the initialization:

```
c [0] = 0
c [1] = 0
c [2] = 1
s [2, 0] = ""
```

We can now repeatedly add new entries to `s`

and `c`

. Note that we have
`n`

in `$1`

:

```
for (i = 3; i < $1 + 3; i ++) {
c [i] = 0
for (j = 1; j <= 3; j ++) {
for (k = 0; k < c [i - j]; k ++) {
s [i, c [i]] = j " " s [i - j, k]
c [i] ++
}
}
}
```

Finally, we print the result:

```
for (k = 0; k < c [$1 + 2]; k ++) {
print s [$1 + 2, k]
}
```

Find the full program on GitHub.

For our Bash solution, we need a trick. Bash doesn't have multidimensional arrays. We could have used a concatenated key, and an associative array, but we do something else instead. Instead of having an array of sets, we use an array of strings; each string has all the decompositions concatenated together; and each decomposition starts with a newline. (So, the newline acts as a separator, but there is an extra newline at the beginning).

The initialization:

```
declare scores
l=$'\n'
scores[2]=$l
```

`l=$'\n'`

is a little trick to get a string consisting of just a newline
into a variable.

We can now repeatedly add a new entry to `scores`

:

```
for ((i = 3; i < n + 3; i ++))
do for ((j = 1; j <= 3; j ++))
do scores[$i]=${scores[$i]}${scores[$((i - j))]//$l/$l$j }
done
done
```

The interesting part is: `${scores[$((i - j))]//$l/$l$j }`

. `i`

is the
index of new entry, and `j`

is `1`

, `2`

, or `3`

, so `${scores[$((i - j))]}`

is one of the last three entries. We then use a regular expression to
prepend `j`

to each of the decompositions. The general syntax is:
`${word//pattern/replacement}`

. This takes `$word`

, and replaces each
non-overlapping occurance of `pattern`

with `replacement`

, returning
the result. The Perl equivalent would be: `$word =~ s/pattern/replacement/gr`

.

Printing the result is now simply — we don't have to loop as the decompositions are already separated by newlines. But we have to remove the first newline:

```
echo "${scores[$((n + 2))]/$l/}"
```

Note that we have only a single slash before the pattern; this means we only replace the first occurance.

Find the full program on GitHub.

In C, we have to work hard! Since C doesn't have a way of find out the size of an array, nor an efficient method to find the length of a string, we will be using three arrays:

`scores`

, a two dimensional array of strings (which are pointers to`char`

)`count`

, which counts the number of decompositions for a specific score`lengths`

, a two dimensional array, with the length of each of the strings in`scores`

.

We'll declare this as:

```
typedef long long number;
char *** scores;
number * count;
size_t ** lengths;
```

Then we read our number `n`

, and allocate space for the arrays:

```
int n;
if (scanf ("%d", &n) != 1) {
perror ("Unexpected input");
exit (1);
}
if ((scores = (char ***) malloc ((n + 3) * sizeof (char **))) == NULL) {
perror ("Malloc scores failed");
exit (1);
}
if ((count = (number *) malloc ((n + 3) * sizeof (number))) == NULL) {
perror ("Malloc count failed");
exit (1);
}
if ((lengths = (size_t **) malloc ((n + 3) * sizeof (size_t *))) == NULL) {
perror ("Malloc lengths failed");
exit (1);
}
```

We can now initialize the first three entries, which requires more allocating of memory:

```
count [0] = 0;
count [1] = 0;
count [2] = 1;
if ((scores [2] = (char **) malloc (sizeof (char *))) == NULL) {
perror ("Malloc failed");
exit (1);
}
if ((scores [2] [0] = (char *) malloc (sizeof (char))) == NULL) {
perror ("Malloc failed");
exit (1);
}
if ((lengths [2] = (size_t *) malloc (sizeof (size_t))) == NULL) {
perror ("Malloc failed");
exit (1);
}
scores [2] [0] [0] = '\0';
lengths [2] [0] = 0;
```

We now start the loop in which we add new sets to `scores`

:

```
for (int i = 3; i < n + 3; i ++) {
```

We start with calculating how many entries there will be in that
set (which is the sum of the sizes of the previous three sets),
and allocate memory for `scores [i]`

and `lengths [i]`

:

```
count [i] = count [i - 1] + count [i - 2] + count [i - 3];
if ((scores [i] = (char **) malloc (count [i] * sizeof (char *)))
== NULL) {
perror ("Malloc failed");
exit (1);
}
if ((lengths [i] = (size_t *) malloc (count [i] * sizeof (size_t)))
== NULL) {
perror ("Malloc failed");
exit (1);
}
```

It's only now that we can create the entries in the set. Each entry is
two character longer than the its "*parent*" entry: first a `1`

, `2`

,
or `3`

, then a space, then a copy of an entry from one of the three
previous sets.

```
number l = 0;
for (int j = 1; j <= 3; j ++) {
for (int k = 0; k < count [i - j]; k ++) {
lengths [i] [l] = 2 + lengths [i - j] [k];
if ((scores [i] [l] = (char *) malloc
((lengths [i] [l] + 1) * sizeof (char))) == NULL) {
perror ("Malloc failed");
exit (1);
}
scores [i] [l] [0] = j + '0';
scores [i] [l] [1] = ' ';
strncpy (scores [i] [l] + 2, scores [i - j] [k],
lengths [i - j] [k]);
scores [i] [l] [lengths [i] [l]] = '\0';
l ++;
}
}
```

At the end of the loop, we can release some memory — we don't need the entry three steps back anymore:

```
if (i - 3 > 1) {
for (int k = 0; k < count [i - 3]; k ++) {
free (scores [i - 3] [k]);
}
free (scores [i - 3]);
free (lengths [i - 3]);
}
```

After we have created the final set, we can print its entries:

```
for (int i = 0; i < count [n + 2]; i ++) {
printf ("%s\n", scores [n + 2] [i]);
}
```

All what now needs to be done, is freeing memory:

```
for (int i = n; i <= n + 2; i ++) {
for (int k = 0; k < count [i]; k ++) {
free (scores [i] [k]);
}
free (scores [i]);
free (lengths [i]);
}
free (scores);
free (lengths);
free (count);
```

Find the full program on GitHub.

We have also solutions in Lua, Node.js, Python and Ruby, which are all similar to our Perl solution.