## Largest product in a grid (problem 11)

Posted: 12/07/2013 in Project Euler
Tags: , , , , , ,

Problem 11 of PE’s website says:

`In the 20×20 grid below, four numbers along a diagonal line have been marked in red.`

`What is the greatest product of four adjacent numbers in the same direction (up, down, left, right, or diagonally) in the 20×20 grid?`

I provided a general solution in C. My program allocates dynamically any type of matrix, with any size you want, with any length of adjacent numbers you want the program to analize (this is the only extra data you provide as a parameter of the program from the CLI). It also provides some error management (i.e. if both sizes of the grid are less than the length of the adjacent numbers you want to find the product).

My program works this way:

1. Open your command line interpreter and execute the program providing the length of adjacent numbers you want to evaluate. For example, in this problem it is `4`, therefore:

`\$ name_of_program 4`

2. Now the program is waiting so that the user provides a matrix to the standard input (the program accepts any size!) and press Enter. In order that the program “catches” that you are done, it is to say, that the `EOF` of stdin is reached, press `CTRL-D` (but before of this, don’t forget to press Enter, this step is important).

3. It stores the grid in a new (temporal) file. At this point the width (= the amount of numbers of each line) and the height (= the number of lines of the file) of the grid are calculated and a new grid with that right size is created.

4. All the data stored in the file is saved in the grid.

5. All the required calculations inside the grid are performed.

6. The result is printed out on the standard output and the temporal file created by the program is removed from your computer.

Here is the C code:

```#include <stdio.h>
#include <stdlib.h>

int **newGrid (unsigned int rows, unsigned int columns);
/* It returns a pointer to a 2D (rows x columns) matrix. */

void freeGrid (int **grid, unsigned int columns);
/* It frees the memory used for grid. */

void recordStdinToFileOpen (FILE * file);
/* Entering user's input is stored in a (temporal) file. */

unsigned int countElementsForGrid (FILE * file, int index_of_array);
/* After the grid is saved in a file, this function returns the width
and the height of the matrix, depending on whether the value of the
"index_of_array" argument is 0 or 1, respectively. */

void recordFileOpenToGrid (FILE * from_file, int **grid,
unsigned int width, unsigned int height);
/* This functions enters the file we are using to allocate dinamically
the data and save it in a grid whose size has been previously calculated. */

unsigned long int getLargestProduct (int **grid, unsigned int width,
unsigned int height, unsigned int adjacent);

/* This function carries out the largest product of any "adjacent" length of adjacent
numbers of the "grid" argument, whose size is "width"x"height", and returns the result.
For this problem in particular, adjacent = 4, height = 20, width = 20. */

unsigned long int doTheStuff (FILE * file, unsigned int adjacent);

/* It gathers all the functions above and returns the return value of the
getLargestProduct() function. */

unsigned long int openFileForGrid (unsigned int adjacent);
/* It opens a temporal file, does all the stuff described above, and
returns the result of doTheSuff() function.
When all the work is done, it removes physically that temporal file

int **newGrid (unsigned int rows, unsigned int columns){

int **grid = NULL;
unsigned int j = 0;

grid = (int **) malloc (columns * sizeof (int *));

for (j = 0; j < columns; j++){
grid[j] = (int *) malloc (rows * sizeof (int));
}

return grid;
}

void freeGrid (int **grid, unsigned int columns){

int j = 0;

for (j = 0; j < columns; j++){
free (grid[j]);
}
free (grid);
}

void recordStdinToFileOpen (FILE * file){

int num;

fseek (file, 0L, SEEK_SET);

while (!feof (stdin)){
fscanf (stdin, "%d", &num);
if (!feof (stdin)){
fprintf (file, "%d ", num);
if (getchar () == '\n'){
fprintf (file, "\n");
}
}
}
}

unsigned int countElementsForGrid (FILE * file, int index_of_array){

unsigned int result = 0;
unsigned int i = 0, j = 0; /* During the execution time, press Enter
after you paste your grid */
unsigned int measures[2] = {i, j};
int first_line_done = 0;
int c;

fseek (file, 0L, SEEK_SET);

while ((c = fgetc (file)) != EOF){
if ((c == ' ') && first_line_done == 0){
i++;
}
if (c == '\n'){
j++;
first_line_done = 1;
}
else {
continue;
}
}

measures[0] = i;
measures[1] = j;

result = measures[index_of_array];

return result;
}

void recordFileOpenToGrid (FILE * from_file, int **grid,
unsigned int width, unsigned int height){

int i = 0, j = 0;

fseek (from_file, 0L, SEEK_SET);

for (j = 0; j < height; j++){
for (i = 0; i < width; i++){
fscanf (from_file, "%d", &grid[j][i]);
}
}
}

unsigned long int getLargestProduct (int **grid, unsigned int width,
unsigned int height, unsigned int adjacent){

unsigned long int result = 1L;
unsigned long int i = 0L, j = 0L, i_temp = i, j_temp = j;
unsigned long int max = 1L;

for (j = 0L; j < height; j++){
for (i = 0L; i < width; i++){
i_temp = i;
j_temp = j;

if (width - i_temp >= adjacent){  /* Move left-to-right (horitzontally) */
for (i_temp = i; i_temp < adjacent + i; i_temp++){
result *= (unsigned int) grid[j][i_temp];
}
if (result >= max) max = result;
result = 1L;
}

if (height - j >= adjacent){ /* Move up-to-down (vertically) */
for (j_temp = j; j_temp < adjacent + j; j_temp++){
result *= (unsigned int) grid[j_temp][i];
}
if (result >= max) max = result;
result = 1L;
}

if ((height - j >= adjacent) && (width - i_temp >= adjacent)){
/* Move up-to-down diagonally (\) */
for (j_temp = j, i_temp = i; (j_temp < adjacent + j)
&& (i_temp < adjacent + i); j_temp++, i_temp++){
result *= (unsigned int) grid[j_temp][i_temp];
}
if (result >= max) max = result;
result = 1L;
}

if ((height - j >= adjacent) && (i_temp >= adjacent - 1)){
/* Move up-to-down diagonally (/) */
for (j_temp = j, i_temp = i; (j_temp < adjacent + j)
&& (i_temp + 1 > i - adjacent + 1); j_temp++, i_temp--){
result *= (unsigned int) grid [j_temp][i_temp];
}
if (result >= max) max = result;
result = 1L;
}
}
}

result = max;

return result;
}

unsigned long int doTheStuff (FILE * file, unsigned int adjacent){

unsigned long int result = 1;
unsigned int width = 0, height = 0;
int **grid;

recordStdinToFileOpen (file);
width = countElementsForGrid (file, 0);
height = countElementsForGrid (file, 1);

fprintf (stderr, "Error: the parameter must be equal or less than, at least, one side of the grid.\n");
exit (1);
}

grid = newGrid (width, height);
recordFileOpenToGrid (file, grid, width, height);
result = getLargestProduct (grid, width, height, adjacent);
freeGrid (grid, height);

return result;
}

unsigned long int openFileForGrid (unsigned int adjacent){

unsigned long int escape = 0L;
FILE * temp_file;

temp_file = fopen ("temp.txt", "w+");
if (temp_file != NULL){
} else{
fprintf (stderr, "Error: There were a problem when opening a new file.\n");
exit (1);
}

fclose (temp_file);
system ("rm -r temp.txt"); /* Windows users: replace "rm -r temp.txt" by "DEL temp.txt". */

return escape;
}

int main (int argc, char *argv[]){

char * endptr;
const unsigned int adjacent = (unsigned int) strtol (argv[1], &endptr, 10);
unsigned long int result;

if (argc < 2 || (int) adjacent <= 0){
fprintf (stderr, "Error: A positive integer as parameter is required.\n");
exit (1);
}

fprintf (stdout, "\n%lu\n", result);

return 0;
}
```

I’m going to show you some examples of its use:

```\$ (gcc -Wall -Wconversion -g prob11.c) && ./a.out 2
1 2
3 4

12
\$ (gcc -Wall -Wconversion -g prob11.c) && ./a.out 3
1 2 9
1 8 4
9 3 3
7 7 7

648
\$ (gcc -Wall -Wconversion -g prob11.c) && ./a.out 2
1 6 7 2 3

42
```

```\$ (gcc -Wall -Wconversion -g prob11.c) && ./a.out 5 3 5 5 3 Error: the parameter must be equal or less than, at least, one side of the grid.```

```\$ (gcc -Wall -Wconversion -g prob11.c) && ./a.out -1 Error: A positive integer as parameter is required.```

In particular, for this problem:

```\$ (gcc -Wall -Wconversion -g prob11.c) && ./a.out 4
08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08
49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00
81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65
52 70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 36 91
22 31 16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80
24 47 32 60 99 03 45 02 44 75 33 53 78 36 84 20 35 17 12 50
32 98 81 28 64 23 67 10 26 38 40 67 59 54 70 66 18 38 64 70
67 26 20 68 02 62 12 20 95 63 94 39 63 08 40 91 66 49 94 21
24 55 58 05 66 73 99 26 97 17 78 78 96 83 14 88 34 89 63 72
21 36 23 09 75 00 76 44 20 45 35 14 00 61 33 97 34 31 33 95
78 17 53 28 22 75 31 67 15 94 03 80 04 62 16 14 09 53 56 92
16 39 05 42 96 35 31 47 55 58 88 24 00 17 54 24 36 29 85 57
86 56 00 48 35 71 89 07 05 44 44 37 44 60 21 58 51 54 17 58
19 80 81 68 05 94 47 69 28 73 92 13 86 52 17 77 04 89 55 40
04 52 08 83 97 35 99 16 07 97 57 32 16 26 26 79 33 27 98 66
88 36 68 87 57 62 20 72 03 46 33 67 46 55 12 32 63 93 53 69
04 42 16 73 38 25 39 11 24 94 72 18 08 46 29 32 40 62 76 36
20 69 36 41 72 30 23 88 34 62 99 69 82 67 59 85 74 04 36 16
20 73 35 29 78 31 90 01 74 31 49 71 48 86 81 16 23 57 05 54
01 70 54 71 83 51 54 69 16 92 33 48 61 43 52 01 89 19 67 48

70600674
```

## Some notes about dynamic memory allocation of multi-dimensional arrays

Posted: 07/07/2013 in C
Tags: , , , , , , , ,

(Note: In this post I’m assuming that you know what arrays and pointers are and that you already feel confortable working with them.)

Many programming languages such as Pascal have multi-dimensional arrays support. That is, data stored in this kind of arrays can be accessed by indicating its position in the same way we would indicate the position of a point in a geometric space, it is to say, through a $[x_{1}, ..., x_{n}]$ notation, being $n$ the number of dimensions of the space (and, analogically, the number of dimensions of the array we are working in).

The point is that, despite ANSI C specification says so (section 6.5.2.1, point 3), C language doesn’t really have multi-dimensional arrays support. Instead, it uses an array-of-arrays approach; we don’t access to an array element by just separating the indices by commas, but accessing at first one array, then accessing to a second one, which is situated in a particular index, and so on until we get to the desired element of data. In this case we use the notation $[x_1]...[x_n]$.
A picture is worth a thousand words, so let’s see graphically how can we represent a data retrieval in a 2D-array:

In this case we have a 5×4 matrix of chararacters in which we want to retrieve the character ‘h’. In this image C defines an array of columns, `a`, which has five columns, `a[0]`, `a[1]`, `a[2]`, `a[3]` and `a[4]`. For each column we have four rows: it is to say, each column is an array as well. For example, for the first column, `a[0]`, we have the elements (rows) `a[0][0]`, `a[0][1]`, `a[0][2]` and `a[0][3]`. In particular, the character ‘h’ is allocated in the second element of the array `a[2]`, it is to say, in `a[2][1]`.

The `malloc()` and `free()` functions

You need to keep in mind the C’s approach for representing multi-dimensional arrays so that you can understand how the `malloc()` function works when allocating dynamically memory for multi-dimensional arrays.

The prototype of `malloc()` function is

`void *malloc(size_t size);`

It allocates a block of memory (specifically `size_t` bytes) on the heap and it returns a pointer to the allocated memory. On error, this function returns NULL.

In order to avoid memory leaks during the execution-time of our C programs we have to free all the memory blocks we are not going to use for increasing the perfomance of our programs and even for having always available memory enough for successful calls to `malloc()`. Fortunately C standard library incorporates a function called `free()`, whose prototype is

`void free(void *ptr);`

The `free()` function frees the memory space pointed to by `ptr`, which must have been returned by a previous call to `malloc()`.
It has no return value.

Here’s a very straightforward example of a program that right after allocating dynamically a new 1D-array it frees it:

```#include <stdio.h>
#include <stdlib.h>

int main (void){

int * blocks_of_data;
int number_of_elements = 4;

blocks_of_data = (int *) malloc (number_of_elements * sizeof (int));
free (blocks_of_data);

return 0;
}
```

I will compile and execute this program using Valgrind, which is a tool for Linux that, among other things, helps to detect memory leaks. This is the output I get after the execution-time:

This is a successful result, because it says there are no memory leaks in the program. But let’s remove now the `free()` function of the previous code and let’s repeat the same step of above to see the new results of Valgrind’s diagnose. It is to say, the result of compiling and executing the program

```#include <stdio.h>
#include <stdlib.h>

int main (void){

int * blocks_of_data;
int number_of_elements = 4;

blocks_of_data = (int *) malloc (number_of_elements * sizeof (int));

/* Now the "free (blocks_of_data)" is missing here. */

return 0;
}
```

is

We have lost 16 bytes (the four integer blocks we reserved through the variable `number_of_elements = 4` multiplied by the size of every block of data of integer type, which is four bytes too per block).
This time the memory leak was very little, only 16 bytes, but it’s really important to not forget to use the `free()` function for every `malloc()` call, specially in serious programs where there is a more significant amount of data management, because although you will recover all the memory lost after the execution-time of the program, problems may arise before, for example because of your system’s memory fragmentation.

Let’s now see how to allocate dynamically a 2D-array in two different ways: the more straightforward but less efficient one, and the not so obvious but more efficient second one. Take a look at the following piece of code:

```#include <stdio.h>
#include <stdlib.h>

int main (void){

int j = 0;

int rows = 4, columns = 5;
int **grid = NULL;

/* Allocating the matrix */

grid = (int **) malloc (columns * sizeof (int *));

for (j = 0; j < columns; j++){
grid[j] = (int *) malloc (rows * sizeof (int));
}

/* Time to free the matrix */

for (j = 0; j < columns; j++){
free (grid[j]);
}
free (grid);

return 0;
}
```

It’s at this right point where the C’s approach of multi-dimensional arrays becomes really clear. If you remember the first image of this post, the first row of that 5×4 grid was the array `a`. That `a` array of that picture is what I re-called here as `grid`.
Look now at line 13 of the code: the `malloc()`‘s function usage is just the same as before, when we only had a 1D-array, but now it was obvious since we had clear that C use the concept of ‘array of arrays’.
So, after we created the first row for `grid`, we are just going to extend each element of `grid` into a new array: it is to say, `grid[0]` is going to be a new array (it will represent the first column of `grid`), `grid[1]` will be a new array as well, and so on. Thus, a for-loop for calling `malloc()` as times as elements has `grid` is needed here.

Once we understood the concept of array of arrays in C, it becomes obvious how the `free()` function should work, but be careful: the order you free the memory does matter.

Let’s see schematically what is going on there:

If you pay attention at the code above, we are calling `free (grid)` only after we have called `free ()` for every element of `grid` array, and there is an important reason to do so: if you call `free (grid)` in the first place, you are freeing only the `grid` array, it is to say, you are only freeing the element `a[0]` to element `a[4]`. What does that mean? It means that you are only freeing the first index of each `a[i]` array (being `i` a number between `0` and `4`), it is to say, you are freeing `a[0][0]`, `a[1][0]`, `a[2][0]`, `a[3][0]` and `a[4][0]`. But this has important side effects: after you free `a`, you lose each pointer that references each `a[i]` and you can’t free them later. Therefore you will have memory leaks.

Finally, here is the second more efficient method for allocating dynamically an array:

```#include <stdio.h>
#include <stdlib.h>

int main (void){

int i = 0;

int rows = 4, columns = 5;
int **grid = NULL;

/* Allocating the matrix */

grid = (int **) malloc (rows * columns * sizeof (int *));
grid[0] = (int *) malloc (rows * sizeof (int));

for (i = 1; i < rows; i++){
grid[i] = grid[i - 1] + columns;
}

/* Time to free the matrix */

free (grid[0]);
free (grid);

return 0;
}
```

This second method is more efficient because there are only two calls to `malloc()` (and, consequently, two calls to `free()`). Another issue is that we are allocating now `grid` as a large 1D-array of `rows x columns` elements; once we have done this, we just assign to `grid[j]` the memory address of the corresponding block of memory `grid[j - 1]` moved `rows` number of rows. In fact, where we write

`grid[j] = grid[j - 1] + rows`

the compiler is really performing

`* (grid + j) = * (grid + (j - 1)) + rows`.

You can see a practical application of this when I solve the problem 11 of Project Euler (probably in my next post), where I will allocate in a matrix any set of numbers given from the standard input.

References:

## Summation of primes (problem 10)

Posted: 01/07/2013 in Project Euler
Tags: , , ,

Problem 10 of PE’s website says:

`The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.`

``` ```

`Find the sum of all the primes below two million.`

Note: A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. (From Wikipedia)

And here is the C code. This time the unique remarkable fact is the fastness of the program:

```#include <stdio.h>
#include <stdlib.h>
#include <math.h>

int esPrimo (unsigned long long int num);
/* Returns 1 if "num" is a prime number.
Otherwise it returns 0 */

unsigned long long int sumPrimes (unsigned int below_n);
/* Returns the summation of all prime
numbers below the number "below_n" */

int esPrimo (unsigned long long int num){

int retorno = 1;
unsigned long long int i = 5LL;
unsigned long long int r;

if (num == 1){
retorno = 0LL; /* 1 is not considered a prime number */
} else if (num < 4) {
retorno = 1;
} else if (num % 2 == 0) {
retorno = 0;
} else if (num < 9){
retorno = 1;
} else if (num % 3 == 0) {
retorno = 0;
} else {
r = (unsigned long long int) sqrt ((double) num);
i = 5LL;
while (i <= r){
if (num % i == 0){
retorno = 0;
break;
}
if (num % (i + 2) == 0){
retorno = 0;
break;
}
i = i + 6LL;
}
}

return retorno;
}

unsigned long long int sumPrimes (unsigned int below_n){

unsigned long long int result = 0;
unsigned int i = 0;

for (i = 0; i < below_n; i++){
if (esPrimo (i)){
result += i;
}
}

return result;
}

int main (int argc, char *argv[]){

unsigned int below_number = (unsigned int) atoi (argv[1]);

printf ("%llu\n", sumPrimes (below_number));

return 0;
}
```

This time I will execute the program with the Unix `time` command, which displays the system resource usage of a program during its execution time:

```\$ (gcc -Wall -Wconversion prob10.c) && time ./a.out 2000000 142913828922```

``` ```

```real 0m1.002s user 0m1.000s sys 0m0.000s```

It took only one second to perform the summation of all prime numbers below two million! Take a moment to think about the significance of this fact. What makes this program fast is the efficiency of the algorithm that evaluates whether a number is prime.
Compare it now with the first version of the algorithm I wrote:

```int esPrimo (unsigned long long int num){

int retorno = 1;
unsigned long long int i = 2LL;

for (i = 2LL; i <= sqrt ((double) num); i++){
if (num % i == 0){
retorno = 0;
break;
}
}

if (num == 0){
retorno = 0;
}

return retorno;
}
```

This one is a more straightforward one, because it just implements the primitive definition of prime number. But this is also an inconvenience, because it doesn’t even care about some implications of the definition. For example, the fact that if 2 is not a divisor of, let’s say, $17$, implies that nor 4 neither 6 will be divisors of it, because they can be decomposed by a product where there is at least a $2$. The first algorithm just skips all the composite numbers of the ones evaluated before, and that gives its efficiency.

Let’s measure now the time which this “not optimized” version of the same program spends during its execution time:

```(gcc -Wall -Wconversion prob10.c -lm) && time ./a.out 2000000 142913828922```

``` ```

```real 0m10.278s user 0m10.269s sys 0m0.004s```

10x times slower. No more words are needed.

## Special Pythagorean triplet (problem 9)

Posted: 01/07/2013 in Project Euler
Tags: , , ,

Problem 9 of PE’s website says:

`A Pythagorean triplet is a set of three natural numbers, `$a < b < c$`, for which`

$a^{2} + b^{2} = c^{2}$

`For example, `$3^2 + 4^2 = 9 + 16 = 25 = 5^2.$

`There exists exactly one Pythagorean triplet for which `$a + b + c = 1000.$
`Find the product `$abc$

First of all, after you submit the correct answer on that website, a new forum is enabled to you so that you can post there the way you reached your solution, and there I found an elegant method that does not require code. I will just quote it:

@theopigott:
```"I decided to have a go at this one on paper. I considered Euclid's formula for generating triples (a,b,c): a = m^2 - n^2, b = 2mn, c = m^2 + n^2.```

``` The aim is that a + b + c = 1000 This implies that 2m^2 + 2mn = 1000, so m^2 + mn = m(m + n) = 500. Now 500 = 2^2 * 3^3, so the possible factorisations (values for m and (m+n)) are: 1 * 500 2 * 250 4 * 125 5 * 100 10 * 50 20 * 25 ```

```However m > n and (m+n) > m, so the only one that would work is m = 20 and m + n = 25, giving n = 5. Substituting back into Euclid's formula gives a = 375, b = 200, c = 425, and the desired product abc = 31875000."```

Isn’t that beautiful? 😀 Before of writing my C program to solve the problem, I also tried to do it by hand through Euclid’s formula, but I got stuck at $m(m + n) = 500$. There I had an equation with two variables, so I couldn’t continue (avoiding trial and error). I also tried to solve the system of equations

$a + b + c = 1000 \\ a^{2} + b^{2} = c^{2}$

and performing the change of variables $a=m^2 - n^2$ , $b=2mn$ , $c=m^2+n^2$ (because then I could have a system of two equations with only two variables), but then I got a more complex equation with square roots and everything, so it didn't help to simplify the problem, but right the opposite.

I didn't thought about factorizing 500… shame on me! So instead I wrote the following program that solves the problem by brute force:

```#include <stdio.h>
#include <stdlib.h>

double exponenciar (double base, int exponent);
/* Returns the result of (base ^ exponent) */

int findProduct (int sum_numbers);
/* Returns a number a*b*C such that (a, b, c) is a Pythagorean triplet and
a + b + c = sum_number */

double exponenciar (double base, int exponent){

double retorna;

if (exponent == 0){
retorna = 1;
} else {
retorna = base * exponenciar (base, exponent - 1);
}

return retorna;
}

int findProduct (int sum_numbers){

int a = 3, b = 4, c = sum_numbers - a - b;
int square_a = (int) exponenciar (a, 2);
int square_b = (int) exponenciar (b, 2);
int square_c = square_a + square_b;

int result = 0;

for (b = 4; b < sum_numbers; b++){
square_b = (int) exponenciar (b, 2);
for (a = 3; a < sum_numbers; a++){
square_a = (int) exponenciar (a, 2);
square_c = square_a + square_b;
c = 1000 - a - b;

if ((int) exponenciar (a + b + c, 2) == (int) exponenciar (sum_numbers, 2) &&
square_c == (int) exponenciar (c, 2)){
result = a*b*c;
break;
}
}
}

return result;
}

int main (int argc, char *argv[]){

int number = atoi (argv[1]);

printf ("%d\n", findProduct (number));

return 0;
}
```

Time to compile and to run the program:

```\$ (gcc -Wall -Wconversion prob9.c) && ./a.out 1000 31875000```