Largest product in a grid : Problem 11 Euler Project

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

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

The product of these numbers is 26 × 63 × 78 × 14 = 1788696.
What is the greatest product of four adjacent numbers in the same direction (up, down, left, right, or diagonally) in the 20×20 grid?

Largest product in a grid : Problem 11 Source: Euler Project
I have saved the matrix in a file "11.txt"

C Code:

#include<stdio.h>
#include<malloc.h>
int main()
{
int **matrix,row,col,maxProduct=1;
int i,j;
int s1,s2,s3,s4,s5,s6,s7,s8;
FILE *fp;
matrix = (int **)malloc(20*sizeof(int*));
for(i=0;i<20;i++)
    matrix[i]=(int *)malloc(20*sizeof(int));
fp = fopen("11.txt","r");
while(!feof(fp)) {
    for(row=0;row<20;row++) {
        for(col=0;col<20;col++) {
        fscanf(fp,"%d",&matrix[row][col]);
            }
        }
    }
for(i=0;i<20;i++) {
    s1=s2=s3=s4=s5=s6=s7=s8=1;
    for(j=0;j<20;j++) {
        // left-sum
        if(j-3 < 0)
            s1 = 1;
        else
            s1 = matrix[i][j]*matrix[i][j-1]*matrix[i][j-2]*matrix[i][j-3];
        if (maxProduct < s1)   
            maxProduct =s1;
        // right-sum   
        if(j+3 >= 20)
            s2 = 1;
        else
            s2 = matrix[i][j]*matrix[i][j+1]*matrix[i][j+2]*matrix[i][j+3];   
        if (maxProduct < s2)   
            maxProduct =s2;   
        // up-sum
        if(i-3 <0)
            s3 = 1;
        else
            s3 = matrix[i][j]*matrix[i-1][j]*matrix[i-2][j]*matrix[i-3][j];   
        if (maxProduct < s3)   
            maxProduct =s3;           
        // down-sum
        if(i+3 >= 20)
            s4 = 1;
        else
            s4 = matrix[i][j]*matrix[i+1][j]*matrix[i+2][j]*matrix[i+3][j];   
        if (maxProduct < s4)   
            maxProduct =s4;   
        // diag-up-left
        if(j-3 < 0 || i - 3 < 0)
            s5 = 1;
        else
            s5 = matrix[i][j]*matrix[i-1][j-1]*matrix[i-2][j-2]*matrix[i-3][j-3];   
        if (maxProduct < s5)   
            maxProduct =s5;   
        // diag-up-right
        if(i-3 < 0 || j + 3 >= 20)
            s6 = 1;
        else
            s6 = matrix[i][j]*matrix[i-1][j+1]*matrix[i-2][j+2]*matrix[i-3][j+3];
        if (maxProduct < s6)   
            maxProduct =s6;   
        // diag-down-left       
        if(i+3 >= 20 || j-3 < 0)
            s7 = 1;
        else
            s7 = matrix[i][j]*matrix[i+1][j-1]*matrix[i+2][j-2]*matrix[i+3][j-3];
        if (maxProduct < s7)   
            maxProduct =s7;   
        // diag-down-right       
        if(i+3 >= 20 || j+3 >=20)
            s8 = 1;
        else
            s8 = matrix[i][j]*matrix[i+1][j+1]*matrix[i+2][j+2]*matrix[i+3][j+3];   
        if (maxProduct < s8)   
            maxProduct =s8;           
        }
       
    }   
printf("\nLargest Product is %d",maxProduct);   
fclose(fp);           
return 0;   
}

ISC COMPUTER SCIENCE PRACTICAL 1998 SPIRAL MATRIX using recursion in JAVA, Python and C++

Spiral Matrix

Write a program which takes N as input, where N is the order of an square matrix. Generate the spiral matrix of order N.

INPUT:

N = 1

OUTPUT:

1

INPUT:

N=2

OUTPUT

1 2

4 3

INPUT:

N=3

OUTPUT

1 2 3

8 9 4

7 6 5

INPUT:

N=4

OUTPUT

1     2    3    4

12  13  14   5

11  16  15   6

10  9    8     7

INPUT:

N=7

OUTPUT

1   2    3   4  5   6   7

24 25 26 27 28 29 8

23 40 41 42 43 30 9

22 39 48 49 44 31 10

21 38 47 46 45 32 11

20 37 36 35 34 33 12

19 18 17 16 15 14 13

Logic: Go through the code!!!!!! All the best!

JAVA CODE

import java.util.*;

public class ISC1998Spiral {

    public static void main(String[] args) {

        int N, val = 0, row, col, ri, ci;

        int i, j;

        int[][] matrix;

        Scanner in = new Scanner(System.in);

        System.out.println("Enter the order of the matrix:");

        N = in.nextInt();

        matrix = new int[N + 1][N + 1];

        for (i = 1; i <= N; i++) {

            for (j = 1; j <= N; j++) {

                matrix[i][j] = 1;

            }

        }

        row = col = 1;

        ri = (N - (N - 2));

        ci = (N - (N - 1));

        SpiralGeneration sp = new SpiralGeneration();

        System.out.println("OUTPUT:");

        sp.spiral(matrix, N, row, col, val, ri, ci);

        for (i = 1; i <= N; i++) {

            for (j = 1; j <= N; j++) {

                String s = String.valueOf(matrix[i][j]);

                while (s.length() < 4) {

                    s += " ";

                }

                System.out.print(s);

            }

            System.out.println();

        }

    }

}

class SpiralGeneration {

    public void spiral(int[][] matrix, int N, int row, int col, int val, int ri, int ci) {

        int a, b, tmp, i, j, l = 0;

        a = row;

        b = col;

        tmp = val + 1;

        if (N == 1 || N == 2) // stopping condition

        {

            if (N == 1) {

                matrix[row][col] = tmp;

            } else {

                matrix[row][col] = tmp;

                matrix[row][col + 1] = tmp + 1;

                matrix[row + 1][col + 1] = tmp + 2;

                matrix[row + 1][col] = tmp + 3;

            }

        } else {

            for (b = 1; b <= N; b++) {

                matrix[row][b - 1 + col] = tmp++;

                if (row != b - 1 + col)

                    matrix[b - 1 + col][row] = (4 * N - 2) - (matrix[row][b - 1 + col] - val) + val;

            }

            b--;

            for (a = 1; a <= N - 1; a++) {

                matrix[a + row][b - 1 + col] = tmp++;

                if (a + row != b - 1 + col)

                    matrix[b - 1 + col][a + row] = (4 * N - 2) - (matrix[a + row][b - 1 + col] - val) + val;

            }

            val = matrix[ri][ci];

            spiral(matrix, N - 2, ++row, ++col, val, ++ri, ++ci);

        }

    }

}

C code

#include<stdio.h>
#include<malloc.h>
void spiral(int **matrix,int N, int row, int col, int val,int ri,int ci);
int main() {
    int N,val=0,row,col,ri,ci;
    int i,j;
    int **matrix;
    printf("\n Enter the order of the matrix:");
    scanf("%d",&N);
    matrix=(int **)malloc((N+1)*sizeof(int*));
        for(i=0;i<=N;i++)
            matrix[i]=(int *)malloc((N+1)*sizeof(double));
    for(i=1;i<=N;i++) {
        for(j=1;j<=N;j++) {
            matrix[i][j]=1;
            }
        }   
    row=col=1;   
    ri = (N-(N-2));
    ci = (N-(N-1));
    spiral(matrix,N,row,col,val,ri,ci);
    printf("\n");
    for(i=1;i<=N;i++) {
        for(j=1;j<=N;j++) {
            if ( i== 1)
            printf("%d          ",matrix[i][j]);
            else
            printf("%d         ",matrix[i][j]);
            }
        printf("\n");
        }
    return 0;
}
void spiral(int **matrix,int N,int row,int col,int val,int ri,int ci) {
    int a,b,tmp,i,j,l=0;
    a = row;
    b = col;
    tmp = val +1;
    if (N== 1 || N==2 ) // stopping condition
        {
            if ( N == 1) {
            matrix[row][col] = tmp;
            }
            else {
            matrix[row][col] = tmp;
            matrix[row][col+1] = tmp+1;
            matrix[row+1][col+1] = tmp+2;
            matrix[row+1][col] = tmp+3;
            }
        }
    else    {       
        for( b = 1 ; b <= N ; b++) {
            matrix[row][b-1+col] = tmp++;
            if( row!=b-1+col )
            matrix[b-1+col][row]  = (4*N-2)-(matrix[row][b-1+col]-val) + val ;
            }
        b--;
        for( a = 1 ; a <= N-1; a++) {
            matrix[a+row][b-1+col] = tmp++;
            if( a+row!=b-1+col)
            matrix[b-1+col][a+row]  = (4*N-2)-(matrix[a+row][b-1+col]-val) +val;
            }
        val = matrix[ri][ci];   
        spiral(matrix,N-2,++row,++col,val,++ri,++ci);   
    }   
}


Python Code

Passing List to function, recursion in python

def SpiralMatrix():

    N = int(input("Enter the order of the Magic Square (odd):"))

    matrix=[[ 0 for row in range(N+2)]for col in range(N+2)]

    for i in range (N+2):

        for j in range (N+2):

            matrix[i][j]=1

    row=col=1  

    val = 0

    ri = (N-(N-2))

    ci = (N-(N-1))  

    def spiral(matrix,N,row,col,val,ri,ci):

        a = row

        b = col

        tmp = val +1

        #print a,b,tmp

        if N== 1 or N==2:

            if N == 1:

                matrix[row][col] = tmp;

            else:

                matrix[row][col] = tmp

                matrix[row][col+1] = tmp+1

                matrix[row+1][col+1] = tmp+2

                matrix[row+1][col] = tmp+3

           

        else:      

            for b in range(N):

                b = b+1

                matrix[row][b-1+col] = tmp

                tmp = tmp+1

                if row != b-1+col:

                    matrix[b-1+col][row]  = (4*N-2)-(matrix[row][b-1+col]-val) + val

               

            for a in range(N-1):

                a = a+1

                matrix[a+row][b-1+col] = tmp

                tmp = tmp+1

                if a+row != b-1+col:

                    matrix[b-1+col][a+row]  = (4*N-2)-(matrix[a+row][b-1+col]-val) +val

            val = matrix[ri][ci]

            row = row+1

            col = col+1

            ri = ri+1

            ci = ci+1    

            spiral(matrix,N-2,row,col,val,ri,ci)

    spiral(matrix,N,row,col,val,ri,ci)      

    print ("OUTPUT~~ SPIRAL MATRIX:")

    for i in range (N):

        for j in range (N):

            print (matrix[i+1][j+1],end =' ')

        print()

SpiralMatrix()      

ISC Computer Science Practicals: Solved

Write a program to declare a matrix A [][] of order (MXN)

where 'M' is the number of rows and 'N' is the number of

columns such that both M and N must be greater than 2 and

less than 20. Allow the user to input integers into this matrix.

Perform the following tasks on the matrix:

1. Display the input matrix

2. Find the maximum and minimum value in the matrix and display

them along with their position.

3. Sort the elements of the matrix in ascending order using any

standard sorting technique and rearrange them in the matrix.

Output the rearranged matrix.

Sample input Output

INPUT:

M=3

N=4

Entered values: 8,7,9,3,-2,0,4,5,1,3,6,-4

Original matrix:

8 7 9 3

-2 0 4 5

1 3 6 -4

Largest Number: 9

Row: 0

Column: 2

Smallest Number: -4

Row=2

Column=3

Rearranged matrix:

-4 -2 0 1

3 3 4 5

6 7 8 9

ISC COMPUTER SCIENCE PRACTICALS, 2013

/*

Write a program to declare a square matrix A[][] of order (M X M) where 'M'

is the number of rows and the number of columns such that M must be greater

than 2 and less than 20. Allow the user to input integers into this matrix.

Display appropriate error message for an invalid input.

Perform the following tasks:

(a) Display the input matrix.

(b) Create a mirror image of the inputted matrix.

(c) Display the mirror image matrix.

Test your program for the following data and some random data:

Example 1

INPUT : M = 3

4 16 12

8 2 14

6 1 3

OUTPUT :

ORIGINAL MATRIX

4 16 12

8 2 14

6 1 3

MIRROR IMAGE MATRIX

12 16 4

14 2 8

3 1 6

Example 2

INPUT : M = 22

OUTPUT : SIZE OUT OF RANGE

*/

/* ISC COMPUTER SCIENCE PRACTICALS, 2013 */

Matrix Inversion

To find the inverse of the matrix if it exists by elementary row operations

#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
int main()
{
double *coeff[15],*I[15],temp,temp1,str,str1;
int i,j,ROW,k,nz,p,q;
printf("\n Enter the value of row OR coloumn:");
scanf("%d",&ROW);
for(i=0;i<ROW;i++)
    {
    coeff[i]=(double *)malloc(ROW*sizeof(double));
    I[i]=(double *)malloc(ROW*sizeof(double));
    }
printf("\n Enter the elements of the matrix(A)");
for(i=0;i<ROW;i++)
    {
    for(j=0;j<ROW;j++)
          scanf("%lf",(coeff[i]+j));
    }
for(i=0;i<ROW;i++)
    {
    for(j=0;j<ROW;j++)
          {
          if(i==j)
          I[i][j]=1.0;
          else
          I[i][j]=0.0;
          }
    }
printf("\n The Matrix A is:\n");
for(i=0;i<ROW;i++)
    {
    for(j=0;j<ROW;j++)
        {
        printf("%lf ",*(coeff[i]+j));
        }
    printf("\n");
        }

for(i=0;i<ROW-1;i++)
    {
    nz=i;
    if(*(coeff[i]+i)==0.0)
        {   
        do
             {
              nz++;
              if(nz>=ROW)
                  {
                  printf("\n Not invertible:\n");
                  exit(1);
                  }
              }while(*(coeff[nz]+i)==0.0);
             //printf("\nnz=%d",nz);
    for(k=0;k<ROW;k++)
        {
        temp=*(coeff[nz]+k); temp1=*(I[nz]+k);
        *(coeff[nz]+k)=*(coeff[i]+k); *(I[nz]+k)=*(I[i]+k);
        *(coeff[i]+k)=temp; *(I[i]+k)=temp1;
            }
             }
           /* printf("\n \n The Augumented (A|b) matrix after Row operations is:\n");
        for(p=0;p<ROW;p++)
            {
            for(q=0;q<ROW;q++)
                printf("%lf ",*(coeff[p]+q));
            printf("\n");
                }*/
        for(k=0;k<ROW-i-1;k++)
            {
            temp=0.0;
            temp1=0.0;
                  str=coeff[i+1+k][i];
                  //printf("\n str=%lf",str);
                  //printf("\n pivot=%lf",coeff[i][i]);
                  for(j=0;j<ROW;j++)
                {
                       temp=coeff[i+k+1][j]; temp1=I[i+k+1][j];
                       //printf(" temp=%lf ",temp);
                       if(str==0.0)
                           continue;
                //temp=temp-((str/coeff[i][i])*coeff[i][j]); temp1=temp1-((str/coeff[i][i])*I[i][j]);
                temp=temp/str; temp1=temp1/str;
                //temp=temp-((temp/str)*coeff[i][i]); temp1=temp1-((str/coeff[i][i])*I[i][j]);
                temp=temp*coeff[i][i]; temp1=temp1*coeff[i][i];
                temp=temp-coeff[i][j]; temp1=temp1-I[i][j];
                //printf(" [temp=%lf] ",temp);
                 coeff[i+k+1][j]=temp; I[i+k+1][j]=temp1;
                          }
                   }
        
            
    }
/*printf("\n \n The Augumented (A|b) matrix after Row operations is:\n");
for(i=0;i<ROW;i++)
    {
    for(j=0;j<ROW;j++)
        printf("%lf ",*(coeff[i]+j));
    printf("\n");
        }
printf("\n \n The Inverse of the matrix is:\n");
for(i=0;i<ROW;i++)
    {
    for(j=0;j<ROW;j++)
        printf("%lf ",*(I[i]+j));
    printf("\n");
        }*/
for(i=ROW-1;i>0;i--)
    {
    temp=0.0;
    temp1=0.0;
   
    for(k=i-1;k>=0;k--)
        {   
            str=coeff[k][i];
            //printf("\n str1=%lf",str1);
            //printf("\n str=%lf\n",str);
            for(j=0;j<ROW;j++)
            {
            if(str==0.0)
                continue;
           
            temp=coeff[k][j]/str; temp1=I[k][j]/str;
            //printf(" temp1=%lf",temp1);
            temp= temp*coeff[i][i]; temp1=temp1*coeff[i][i];
            //printf("\n temp=%lf",temp);
            temp=temp-coeff[i][j];  temp1=temp1-I[i][j];
            coeff[k][j]=temp;       I[k][j]=temp1;
            }
        }
       
    }
/*printf("\n \n The Augumented (A|b) matrix after Row operations is:\n");
for(i=0;i<ROW;i++)
    {
    for(j=0;j<ROW;j++)
        {
        //if(i==j)
        //    printf("%lf ",*(coeff[i]+j)/coeff[i][i]);
        //else
        printf("%lf ",*(coeff[i]+j));
        }
   
    printf("\n");
        }*/
printf("\n \n The Inverse of the matrix is:\n");
for(i=0;i<ROW;i++)
    {
    for(j=0;j<ROW;j++)
        {
        if(coeff[i][i]==0.0)
            printf("%lf ",*(I[i]+j));
        else
        printf("%lf ",*(I[i]+j)/coeff[i][i]);
        }
    printf("\n");
        }

return 0;
}