Posts Tagged ‘largest’

Problem 11 of PE’s website says:

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

img1

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 
of your computer. */


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);
    
    if ((adjacent > width) && (adjacent > height)){
		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){
		escape = doTheStuff (temp_file, adjacent);
    } 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);
    }
    
    result = openFileForGrid (adjacent);
    
    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

Examples of bad inputs:

$ (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

This is the requested answer.

Advertisements

Problem 8 of PE’s website says:

Find the greatest product of five consecutive digits in the 1000-digit number:

73167176531330624919225119674426574742355349194934\\  96983520312774506326239578318016984801869478851843\\  85861560789112949495459501737958331952853208805511\\  12540698747158523863050715693290963295227443043557\\  66896648950445244523161731856403098711121722383113\\  62229893423380308135336276614282806444486645238749\\  30358907296290491560440772390713810515859307960866\\  70172427121883998797908792274921901699720888093776\\  65727333001053367881220235421809751254540594752243\\  52584907711670556013604839586446706324415722155397\\  53697817977846174064955149290862569321978468622482\\  83972241375657056057490261407972968652414535100474\\  82166370484403199890008895243450658541227588666881\\  16427171479924442928230863465674813919123162824586\\  17866458359124566529476545682848912883142607690042\\  24219022671055626321111109370544217506941658960408\\  07198403850962455444362981230987879927244284909188\\  84580156166097919133875499200524063689912560717606\\  05886116467109405077541002256983155200055935729725\\  71636269561882670428252483600823257530420752963450\\

This problem can only be done by using brute force, so here we go.
I provided a general solution in C. My program waits an entering number from the standard input, and then it performs the task. The user also provides as parameters the number of digits of its entering number and the N consecutive digits he/she wants the program to use (in this case it will be 5), in this right order.

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

void charArrToIntArr (char from[], int to[], int length){

    int i = 0;

    for (i = 0; i < length; i++){
      	to[i] = from[i] - 48;
      	/* "ASCII value of a number" - 48 = "the number itself" */
    }
}

int findLargestProduct (int big_number[], int size, int n_consecutive){
    
    int i = 0, j = 0;
    int product = 1;
    int largest_product = 1;

    while (n_consecutive <= size){
      	for (j = i; j < n_consecutive; j++){
         	product *= big_number[j];
      	}
      	n_consecutive++;
      	if (largest_product <= product){
         	largest_product = product;
      	}
     	product = 1; i++;
    }

    return largest_product;
}

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

    const unsigned int size_max = (unsigned int) atoi (argv[1]);
    int n_consecutive = atoi (argv[2]);

    char * big_number_temp = malloc (size_max * sizeof (char));
    int big_number[size_max];

    int i = 0;
    
    while (!feof (stdin)){
      	scanf ("%c", &big_number_temp[i]);
      	if (!feof (stdin)){	    
         	if (big_number_temp[i] == '\n'){
            	i--;
         	}
            i++;

         	if (i == size_max){
            	fprintf (stderr, "\nWarning: Array's limit reached (at %d).\n", i);
            	break;
         	}
    	}
    } 

    charArrToIntArr (big_number_temp, big_number, i);
    free (big_number_temp);

    printf ("%d\n", findLargestProduct (big_number, i, n_consecutive));

    return 0;
}

Finally,

$ (gcc -Wall -Wconversion prob8.c) && ./a.out 1000 5
# (Ctrl + Shift + v)
40824

I’m actually working out the problems proposed in Project Euler’s website and I thought that it could be useful for many people if I post here my solutions for some of them. 

The problem 4 says: 

A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 x 99.

Find the largest palindrome made from the product of two 3-digit numbers.

I just generalized this problem by writing out a modular program, in C, that finds the largest Palindrome for any number of digits given in the command line.

The program may seem larger than necessary, but that’s because I used some general functions I defined a while ago for other purposes, so they work fine with any (valid) input (so at the far end that made me easier to structure the program 🙂 ).

#include <stdio.h>
#include <stdlib.h>
 
double exponenciar (double base, int exponent); 
/* Returns the result of (base ^ exponent) */
 
int calculaXifres (int n);
/* Returns the number of digits of the number "n". */
 
long int aIntegerstoInteger (long int array_de_integers[], 
                             int longitud); 
/* Maps each element of the array of integers
 "array_de_integers", of "longitud" elements, 
to each digit of an integer, and returns it back. 
For instance,
 
aIntegerstoInteger ({2, 1, 5}, 3) 
 
will return 215. I will only use this function once, 
just for making easier the inversion of a number. */
 
long int invertirNumero (long int num); 
/* Returns the number "num" inverted */
 
long int maxValueNdigits (int num_digits); 
/* Returns the maximum value that a number with 
"num_digits" digits can reach. For example, 
maxValueNdigits (4) would return 9999. */
 
long int largestPalindrome (int num_digits); 
/* Returns the answer of this problem when 
num_digits = 3. */
 
 
double exponenciar (double base, int exponent){
 
    double retorna;
 
    if (exponent == 0){
      retorna = 1;
    } else {
      retorna = base * exponenciar (base, exponent - 1);
    }
 
    return retorna;
}
 
int calculaXifres (int n){
 
    int quocient = n;
    int comptador = 0;
 
    while (quocient > 0){
      quocient = quocient / 10;
      comptador++;
    }
 
    return comptador;
}
 
long int aIntegerstoInteger (long int array_de_integers[], 
                             int longitud){
     
    int num_elements = longitud;
    int i = 0;
    long int integer = 0;
 
    for (i = 0; i < num_elements; i++){
      integer += array_de_integers[i] * 
                 (int) exponenciar (10, num_elements - (i + 1));
    }
 
    return integer;
}
 
long int invertirNumero (long int num){
     
    int longitud = calculaXifres (num);
    long int num_invertit[longitud];
    long int numero_invertit;
    int i = 0;
     
    for (i = 0; i < longitud; i++){
      num_invertit[i] = num % 10;
      num = num / 10;
    }
 
    numero_invertit = aIntegerstoInteger (num_invertit, longitud);
 
    return numero_invertit;
}
 
 
long int maxValueNdigits (int num_digits){
     
    int i = 0;
    long int max_value = 0;
 
    for (i = 0; i < num_digits; i++){
       max_value = max_value + (int) exponenciar (10, i);
    }
 
    max_value = 9*max_value;
 
    return max_value;
}
 
 
long int largestPalindrome (int num_digits){
     
    long int starting = (long int) exponenciar (10, num_digits - 1);
    long int ending = maxValueNdigits(num_digits);
    long int i = starting;
    long int j = i;
    long int largest_palindrome = 0L;
 
    for (i = starting; i <= ending; i++){
      for (j = starting; j <= ending; j++){
         if (i * j == invertirNumero (i * j) &&
            i * j >= largest_palindrome){
            largest_palindrome = i * j;
         }
      }
    }
 
    return largest_palindrome;
}
 
 
int main (int argc, char *argv[]){
 
    int num_digits = atoi (argv[1]);
 
    printf ("%ld\n", largestPalindrome (num_digits));
     
    return 0;
}

Time to compile and to execute the program:

$ (gcc -Wall -Wconversion prob4.c) && ./a.out 3
906609

And the three-digit factors are 993 and 913, it is to say, 993 \times 913 = 906609.