2008 Coding Challenge II

In the 20 by 20 grid below, five numbers along a diagonal line have been marked in bold.

47 90 41 82 1 96 95 27 50 91 97 65 49 38 96 90 90 90 84 27
6 35 42 36 25 31 20 57 86 61 34 6 73 13 59 72 55 51 72 53
20 2 44 25 28 57 5 29 21 12 12 30 20 72 40 33 32 14 93 24
95 3 96 2 77 77 96 16 9 92 85 36 18 52 5 49 70 39 62 53
33 1 47 74 50 5 65 84 57 60 64 80 13 40 74 90 33 82 49 49
10 61 2 69 70 71 45 43 33 83 8 56 9 69 86 67 80 17 65 76
23 31 36 20 81 60 53 36 64 86 68 94 2 68 73 14 50 37 21 49
4 60 79 87 2 28 58 58 49 59 19 50 74 83 52 18 61 2 93 88
98 52 76 5 30 34 32 85 3 10 39 60 26 51 50 69 36 21 48 99
5 85 47 66 69 27 83 5 34 79 28 59 32 68 5 84 15 58 54 25
13 13 18 80 92 33 88 7 61 63 93 39 33 67 15 24 6 8 18 97
60 19 98 51 98 71 65 23 39 18 90 26 59 90 90 2 4 31 34 59
31 56 94 13 12 37 71 88 19 97 79 70 51 95 54 67 55 16 80 81
64 92 17 24 51 48 87 36 82 63 41 50 25 56 84 94 13 34 86 82
5 51 11 83 78 91 88 99 61 84 54 91 77 25 44 75 79 46 6 6
31 38 58 16 36 46 66 57 24 77 16 61 23 88 79 79 19 82 31 37
98 86 7 15 69 50 90 77 32 65 84 1 36 44 57 66 38 11 68 45
32 38 96 61 47 36 43 70 32 36 15 34 7 90 70 96 95 7 29 11
27 29 4 44 41 89 30 65 50 14 60 37 49 6 69 17 22 23 32 95
93 62 98 22 20 33 27 1 97 17 93 92 8 38 9 78 20 51 13 18

 

The product of these numbers is 85 * 34 * 63 * 90 * 70 = 1147041000

What is the smallest product of five adjacent numbers in any direction (up, down, left, right, or diagonally) in this grid of numbers ?

 

Here’s one solution using LINQ :

 image

source code:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace _2008_2_CodingChallenge
{
    class Program
    {
        static void Main(string[] args)
        {
            long currentProduct = long.MaxValue;

            List<CellItem> currentList = new List<CellItem>();

            int[,] numbers = {
                                {47,90,41,82,1,96,95,27,50,91,97,65,49,38,96,90,90,90,84,27 },
                                {6,35,42,36,25,31,20,57,86,61,34,6,73,13,59,72,55,51,72,53  },
                                {20,2,44,25,28,57,5,29,21,12,12,30,20,72,40,33,32,14,93,24  },
                                {95,3,96,2,77,77,96,16,9,92,85,36,18,52,5,49,70,39,62,53    },
                                {33,1,47,74,50,5,65,84,57,60,64,80,13,40,74,90,33,82,49,49  },
                                {10,61,2,69,70,71,45,43,33,83,8,56,9,69,86,67,80,17,65,76   },
                                {23,31,36,20,81,60,53,36,64,86,68,94,2,68,73,14,50,37,21,49 },
                                {4,60,79,87,2,28,58,58,49,59,19,50,74,83,52,18,61,2,93,88   },
                                {98,52,76,5,30,34,32,85,3,10,39,60,26,51,50,69,36,21,48,99  },
                                {5,85,47,66,69,27,83,5,34,79,28,59,32,68,5,84,15,58,54,25   },
                                {13,13,18,80,92,33,88,7,61,63,93,39,33,67,15,24,6,8,18,97   },
                                {60,19,98,51,98,71,65,23,39,18,90,26,59,90,90,2,4,31,34,59  },
                                {31,56,94,13,12,37,71,88,19,97,79,70,51,95,54,67,55,16,80,81},
                                {64,92,17,24,51,48,87,36,82,63,41,50,25,56,84,94,13,34,86,82},
                                {5,51,11,83,78,91,88,99,61,84,54,91,77,25,44,75,79,46,6,6   },
                                {31,38,58,16,36,46,66,57,24,77,16,61,23,88,79,79,19,82,31,37},
                                {98,86,7,15,69,50,90,77,32,65,84,1,36,44,57,66,38,11,68,45  },
                                {32,38,96,61,47,36,43,70,32,36,15,34,7,90,70,96,95,7,29,11  },
                                {27,29,4,44,41,89,30,65,50,14,60,37,49,6,69,17,22,23,32,95  },
                                {93,62,98,22,20,33,27,1,97,17,93,92,8,38,9,78,20,51,13,18   }
                             };

            List<CellItem> cellItems = new List<CellItem>();

            for (int i = 0; i < numbers.GetLength(0); i++)
                for (int j = 0; j < numbers.GetLength(1); j++)
                    cellItems.Add(new CellItem { Row = i, Col = j, Value = numbers[i, j] });


            var down =
              from row in Enumerable.Range(0, 15)
              from col in Enumerable.Range(0, 19)
              select (from offset in Enumerable.Range(0, 5)
                      from ci in cellItems
                      where ci.Row == row + offset && ci.Col == col 
                      select ci );

            var left =
              from row in Enumerable.Range(0, 19)
              from col in Enumerable.Range(0, 15)
              select (from offset in Enumerable.Range(0, 5)
                      from ci in cellItems
                      where ci.Row == row && ci.Col == col + offset 
                      select ci);

            var diag =
              from row in Enumerable.Range(0, 15)
              from col in Enumerable.Range(0, 15)
              select (from offset in Enumerable.Range(0, 5)
                      from ci in cellItems
                      where ci.Row == row + offset && ci.Col == col + offset
                      select ci);

            var combined = down.Concat(left).Concat(diag);

            combined.ToList().ForEach(delegate(IEnumerable<CellItem> items)
                                {
                                    if (currentProduct > items.CalculateProduct())
                                    {
                                        currentProduct = items.CalculateProduct();
                                        currentList = items.ToList();
                                    }
                                });

            currentList.ConsoleDump();

            Console.ReadKey();
        }

    }

    public static class Extensions
    {
        public static long CalculateProduct(this IEnumerable<CellItem> items)
        {
            long product = 1;
            foreach (CellItem item in items)
                product *=  item.Value;

            return product;
        }


        public static void ConsoleDump(this IEnumerable<CellItem> items)
        {
            foreach (CellItem item in items)
                Console.WriteLine(string.Format("row = {0} col = {1} value = {2}", 
                                                item.Row, item.Col, item.Value));
            
            Console.Write(string.Format("product = {0}", items.CalculateProduct()));
            Console.WriteLine();
        }
    }

    public class CellItem
    {
        public int Row   { get; set; }
        public int Col   { get; set; }
        public int Value { get; set; }
    }
}

 

 

Here’s another solution using good old Excel VBA submitted by Jerry …

image

source code:

 

Sub FindMin()
    Dim i As Integer
    Dim j As Integer
    Dim sht As Worksheet
    Dim rng As Range
    Dim val1 As Double
    Dim val2 As Double
    Dim val3 As Double
    Dim val4 As Double
    Dim val5 As Double

    Dim prod As Double
    Dim direction As Integer
    Dim minProd As Double
    Dim minProdFirstCellRowNo As Integer
    Dim minProdFirstCellColNo As Integer
    Dim minProdDirection As Integer
    
    Dim directionDesc As String
    
    minProd = 10000000000#
    Set sht = Worksheets("Sheet1")
    
    'across rows
    direction = 1
    For i = 1 To 20
        For j = 1 To 16
            val1 = sht.Cells(i, j)
            val2 = sht.Cells(i, j + 1)
            val3 = sht.Cells(i, j + 2)
            val4 = sht.Cells(i, j + 3)
            val5 = sht.Cells(i, j + 4)
            prod = val1 * val2 * val3 * val4 * val5
            If prod < minProd Then
                minProdDirection = direction
                minProd = prod
                minProdFirstCellRowNo = i
                minProdFirstCellColNo = j
            End If
        Next j
    Next i
    
    'down cols
    direction = 2
    For i = 1 To 16
        For j = 1 To 20
            val1 = sht.Cells(i, j)
            val2 = sht.Cells(i + 1, j)
            val3 = sht.Cells(i + 2, j)
            val4 = sht.Cells(i + 3, j)
            val5 = sht.Cells(i + 4, j)
            prod = val1 * val2 * val3 * val4 * val5
            If prod > minProd Then
                minProdDirection = direction
                minProd = prod
                minProdFirstCellRowNo = i
                minProdFirstCellColNo = j
            End If
        Next j
    Next i
    
    'northwest to southeast
    direction = 3
    For i = 1 To 16
        For j = 1 To 16
            val1 = sht.Cells(i, j)
            val2 = sht.Cells(i + 1, j + 1)
            val3 = sht.Cells(i + 2, j + 2)
            val4 = sht.Cells(i + 3, j + 3)
            val5 = sht.Cells(i + 4, j + 4)
            prod = val1 * val2 * val3 * val4 * val5
            If prod < minProd Then
                minProdDirection = direction
                minProd = prod
                minProdFirstCellRowNo = i
                minProdFirstCellColNo = j
            End If
        Next j
    Next i
    
    'northeast to southwest
    direction = 4
    For i = 1 To 16
        For j = 20 To 5 Step -1
            val1 = sht.Cells(i, j)
            val2 = sht.Cells(i + 1, j - 1)
            val3 = sht.Cells(i + 2, j - 2)
            val4 = sht.Cells(i + 3, j - 3)
            val5 = sht.Cells(i + 4, j - 4)
            prod = val1 * val2 * val3 * val4 * val5
            If prod < minProd Then
                minProdDirection = direction
                minProd = prod
                minProdFirstCellRowNo = i
                minProdFirstCellColNo = j
            End If
        Next j
    Next i
    
    Select Case minProdDirection
        Case 1: directionDesc = "Left To Right"
        Case 2: directionDesc = "Top To Bottom"
        Case 3: directionDesc = "TopLeft To BottomRight"
        Case 4: directionDesc = "TopRight To BottomLeft"
        Case Else: directionDesc = "Error"
    End Select
    
    MsgBox "Solution:" & vbCrLf & _
        vbCrLf & vbTab & "Min Product : " & minProd & _
        vbCrLf & vbTab & "Direction : " & directionDesc & _
        vbCrLf & vbTab & "Starting Cell Row No: " & minProdFirstCellRowNo & _
        vbCrLf & vbTab & "Starting Cell Col No: " & minProdFirstCellColNo
        
    
End Sub

 

 

 

 

Yair submitted another Excel VBA solution with added flexibility for defining the problem matrix size and simpler looping.

image

source code :

 

Private Sub CalcButton_Click()

Dim matrixSizeX As Long, matrixSizeY As Long
matrixSizeX = Range("matrix_size_x").Value
matrixSizeY = Range("matrix_size_y").Value

Set numberMatrix = Range("number_matrix")

Dim adjCount As Long
' Can ignore row/column transposition as product sum will remain the same
adjCount = Range("adj_count").Value

'Dim directionArray As Range
Set directionArray = Range("direction_array")

Dim modifierCount As Long
modifierCount = UBound(directionArray.Value2, 1)

Dim minProduct As Double, tempProduct As Double
minProduct = 100000000000#

Dim minProductModifier As Long, minProductX As Long, minProductY As Long
minProductModifier = minProductX = minProductY = 0

Dim modifierX As Long, modifierY As Long, x As Long, y As Long, i As Long

For modifierIndex = 1 To modifierCount
    modifierX = directionArray(modifierIndex, 2).Value
    modifierY = directionArray(modifierIndex, 3).Value
    
    For x = Application.WorksheetFunction.Max(1, -(adjCount * modifierX)) To Application.WorksheetFunction.Min(matrixSizeX, matrixSizeX - (adjCount * modifierX) + 1)
        For y = 1 To Application.WorksheetFunction.Min(matrixSizeY, matrixSizeY - (adjCount * Abs(modifierY)) + 1)
            tempProduct = 1
        
            For i = 0 To adjCount - 1
                tempProduct = tempProduct * numberMatrix(y + (i * modifierY), x + (i * modifierX)).Value
            Next i
            
            If tempProduct < minProduct Then
                minProduct = tempProduct
                minProductModifier = modifierIndex
                minProductX = x
                minProductY = y
            End If
        Next y
    Next x
Next modifierIndex

Range("min_product").Value = minProduct
Range("min_product_modifier").Value = directionArray(minProductModifier, 1)
Range("min_product_x").Value = minProductX
Range("min_product_y").Value = minProductY

End Sub

Download Excel Sheet