Perl Weekly Challenge 122: Basketball Points

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 1s, 2s, and 3s, 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 maps 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.