We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. All Contests
  2. ProjectEuler+
  3. Project Euler #11: Largest product in a grid
  4. Discussions

Project Euler #11: Largest product in a grid

Sort by

recency

|

114 Discussions

|

  • yonahel
     + 0 comments

    Haskell. Not pretty

    import Control.Applicative
import Control.Monad
import System.IO
import Data.List

down_check :: [[Int]] -> Int -> Int -> Int -> Int
right_check :: [[Int]] -> Int -> Int -> Int -> Int
diag_check :: [[Int]] -> Int -> Int -> Int -> Int
ldiag_check :: [[Int]] -> Int -> Int -> Int 
rdiag_check :: [[Int]] -> Int -> Int -> Int 

down_check gridL max x y
    | x > 16 = max
    | y > 19 = down_check gridL max (x+1) 0
    | product [gridL !! x !! y, gridL !! (x+1) !! y, 
               gridL !! (x+2) !! y, gridL !! (x+3) !! y] 
      > max = 
            down_check 
                gridL 
                (product [gridL !! x !! y, gridL !! (x+1) !! y, 
                          gridL !! (x+2) !! y, gridL !! (x+3) !! y]) 
                x (y+1)
    | otherwise = down_check gridL max x (y+1)

right_check gridL max x y
    | x > 19 = max
    | y > 16 = right_check gridL max (x+1) 0
    | product [gridL !! x !! y, gridL !! x !! (y+1), 
               gridL !! x !! (y+2), gridL !! x !! (y+3)] 
      > max = 
            right_check 
                gridL 
                (product [gridL !! x !! y, gridL !! x !! (y+1), 
                          gridL !! x !! (y+2), gridL !! x !! (y+3)]) 
                x (y+1)
    | otherwise = right_check gridL max x (y+1)
    
diag_check gridL max x y
    | x > 16 = max
    | y > 19 = diag_check gridL max (x+1) 0
    | maximum [ldiag_check gridL x y, rdiag_check gridL x y] > max = 
            diag_check 
                gridL 
                (maximum [ldiag_check gridL x y, rdiag_check gridL x y]) 
                x 
                (y+1)
    | otherwise = diag_check gridL max x (y+1)
    
ldiag_check gridL x 0 = 0
ldiag_check gridL x 1 = 0
ldiag_check gridL x 2 = 0
ldiag_check gridL x 3 = 0
ldiag_check gridL x y = product [gridL !! x !! y, gridL !! (x+1) !! (y-1),
                                 gridL !! (x+2) !! (y-2), gridL !! (x+3) !! (y-3)]

rdiag_check gridL x 16 = 0
rdiag_check gridL x 17 = 0
rdiag_check gridL x 18 = 0
rdiag_check gridL x 19 = 0
rdiag_check gridL x y = product [gridL !! x !! y, gridL !! (x+1) !! (y+1),
                                 gridL !! (x+2) !! (y+2), gridL !! (x+3) !! (y+3)]

main :: IO ()
main = do
    grid_temp <- getMultipleLines 20
    let grid = map ( map ( read :: String -> Int ) . words ) grid_temp
    let down_max = down_check grid 0 0 0
    let right_max = right_check grid 0 0 0
    let diag_max = diag_check grid 0 0 0
    print (maximum [down_max, right_max, diag_max])

getMultipleLines :: Int -> IO [String]

getMultipleLines n
    | n <= 0 = return []
    | otherwise = do          
        x <- getLine         
        xs <- getMultipleLines (n-1)    
        let ret = (x:xs)    
        return ret

  • andreveyccan
     + 1 comment
    import java.util.*;
class Solution
{
    static int[][] mat= new int[20][20];
    static int greatestone=0;
    static void checkVerticalFwd(int x, int y)
    {
        if((x+3)>=20)
        {
            return;
        }
        int temp= mat[x][y];
        temp*=mat[x+1][y];
        temp*=mat[x+2][y];
        temp*=mat[x+3][y];
        if(temp>greatestone)
        {
            greatestone=temp;
        }
    }
     static void checkHorizontalFwd(int x, int y)
    {
        if((y+3)>=20)
        {
            return;
        }
        int temp= mat[x][y];
        temp*=mat[x][y+1];
        temp*=mat[x][y+2];
        temp*=mat[x][y+3];
        if(temp>greatestone)
        {
            greatestone=temp;
        }
    }
     static void DiagRight(int x, int y)
    {
        if((x+3)>=20|| y + 3 >=20)
        {
            return;
        }
        int temp= mat[x][y];
        temp*=mat[x+1][y+1];
        temp*=mat[x+2][y+2];
        temp*=mat[x+3][y+3];
        if(temp>greatestone)
        {
            greatestone=temp;
        }
    }
    static void DiagLeft(int x, int y)
    {
        if((x+3)>=20||(y - 3) < 0)
        {
            return;
        }
        int temp= mat[x][y];
        temp*=mat[x+1][y-1];
        temp*=mat[x+2][y-2];
        temp*=mat[x+3][y-3];
        if(temp>greatestone)
        {
            greatestone=temp;
        }
    }
    public static void main(String[] args)
    {
        Scanner scn = new Scanner(System.in);
        
         for(int x = 0; x < 20; x++){
                for(int y = 0; y < 20; y++){
                    mat[x][y] = scn.nextInt();
                }
            }
        
            for(int x = 0; x < 20; x++) {
                for(int y = 0; y < 20; y++) {
                    checkVerticalFwd(x, y);
                    checkHorizontalFwd(x,y);
                    DiagRight(x,y);
                    DiagLeft(x,y) ;
                }
								System.out.println(greatestone);

            }
        System.out.println(greatestone);
}

    }

  • alex_fuehrs1
     + 0 comments
    grid = []
for grid_i in range(20):
	grid_t = [int(grid_temp) for grid_temp in input().strip().split(' ')]
	grid.append(grid_t)

len_g = len(grid)
numbers = []
    
for i in range(len_g):
    for j in range(len_g):
        #UP
        if (i-3 >= 0):
            number = grid[i][j] * grid[i-1][j] * grid[i-2][j] * grid[i-3][j]
            numbers.append(number)
        #DOWN
        if (i+3 < len_g):
            number = grid[i][j] * grid[i+1][j] * grid[i+2][j] * grid[i+3][j]
            numbers.append(number)
        #LEFT
        if (j-3 >= 0):
            number = grid[i][j] * grid[i][j-1] * grid[i][j-2] * grid[i][j-3]
            numbers.append(number)
        #RIGHT
        if (j+3 < len_g):
            number = grid[i][j] * grid[i][j+1] * grid[i][j+2] * grid[i][j+3]
            numbers.append(number)
        #DIAGONAL
        #DOWN RIGHT
        if (j+3 < len_g and i+3 < len_g):
            number = grid[i][j] * grid[i+1][j+1] * grid[i+2][j+2] * grid[i+3][j+3]
            numbers.append(number)
        #DOWN LEFT
        if (j-3 >= 0 and i+3 < len_g):
            number = grid[i][j] * grid[i+1][j-1] * grid[i+2][j-2] * grid[i+3][j-3]
            numbers.append(number)
        #UP LEFT
        if (j-3 >= 0 and i-3 >= 0):
            number = grid[i][j] * grid[i-1][j-1] * grid[i-2][j-2] * grid[i-3][j-3]
            numbers.append(number)
        #UP RIGHT
        if (j+3 < len_g and i-3 >= 0):
            number = grid[i][j] * grid[i-1][j+1] * grid[i-2][j+2] * grid[i-3][j+3]
            numbers.append(number)
        
print(max(numbers))

  • _qazi_
     + 0 comments
    vector<vector<int>> vd = {{0,0},{1,1},{2,2},{3,3}};
vector<vector<int>> vd2 = {{0,0},{1,-1},{2,-2},{3,-3}};
vector<vector<int>> vlr = {{0,0},{0,1},{0,2},{0,3}};
vector<vector<int>> vtb = {{0,0},{1,0},{2,0},{3,0}};
ll getD(vector<vector<int>> &v,int i,int j)
{
    vector<vector<vector<int>>> vList = {vd,vd2,vlr,vtb};
    ll mx = 0;
    for(int m = 0;m<vList.size();m++)
    {
            ll prod = 1;
            for(int k = 0;k<4;k++)
            {
                int fi = i+vList[m][k][0];
                int fj = j+vList[m][k][1];
                if(fi<20 && fj<20 && fj>=0) 
                prod = prod * (ll)v[fi][fj];
                else 
                {
                    prod = 0; break;
                }
            }
            mx = max(mx,prod); 
    }
    return mx;
}
ll greatestProd(vector<vector<int>> &v)
{
    ll mx = 0;
    for(int i = 0;i<20;i++)
    {
        for(int j = 0;j<20;j++)
        {
            mx = max(mx,getD(v, i, j));
        }
    }
    return mx;
}

  • sane_kiran
     + 0 comments

    using System;

    class Solution { static void Main() { int[,] grid = ParseInputGrid();

        int maxProduct = FindMaxProduct(grid);
    Console.WriteLine(maxProduct);
}

static int[,] ParseInputGrid()
{
    int[,] grid = new int[20, 20];

    for (int i = 0; i < 20; i++)
    {
        string[] row = Console.ReadLine().Split(' ');

        for (int j = 0; j < 20; j++)
        {
            grid[i, j] = int.Parse(row[j]);
        }
    }

    return grid;
}

static int FindMaxProduct(int[,] grid)
{
    int maxProduct = 0;

    // Check horizontally
    for (int i = 0; i < 20; i++)
    {
        for (int j = 0; j <= 16; j++)
        {
            int product = grid[i, j] * grid[i, j + 1] * grid[i, j + 2] * grid[i, j + 3];
            maxProduct = Math.Max(maxProduct, product);
        }
    }

    // Check vertically
    for (int i = 0; i <= 16; i++)
    {
        for (int j = 0; j < 20; j++)
        {
            int product = grid[i, j] * grid[i + 1, j] * grid[i + 2, j] * grid[i + 3, j];
            maxProduct = Math.Max(maxProduct, product);
        }
    }

    // Check diagonally (top-left to bottom-right)
    for (int i = 0; i <= 16; i++)
    {
        for (int j = 0; j <= 16; j++)
        {
            int product = grid[i, j] * grid[i + 1, j + 1] * grid[i + 2, j + 2] * grid[i + 3, j + 3];
            maxProduct = Math.Max(maxProduct, product);
        }
    }

    // Check diagonally (top-right to bottom-left)
    for (int i = 0; i <= 16; i++)
    {
        for (int j = 3; j < 20; j++)
        {
            int product = grid[i, j] * grid[i + 1, j - 1] * grid[i + 2, j - 2] * grid[i + 3, j - 3];
            maxProduct = Math.Max(maxProduct, product);
        }
    }

    return maxProduct;
}

    }