<< Number Puzzle | Gently killing the explorer.exe process >>

2008 Coding Challenge II

By at August 07, 2008 08:44
Filed Under: Coding Challenge, Puzzles

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 :

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; }
    }
}

Download Project Files

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

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

Download Excel Sheet

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

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

Tags:

Comments (7) E-mail Kick it! DZone it! del.icio.us Permalink Post RSS

Comments

3/20/2010 11:38:54 PM #

nice post!

cheap prom Dresses | Reply

4/22/2010 11:48:25 AM #

Wow that is tricky. You guys are really smart. I will have to give this to some friends of mine to see if they can figure this out. Thanks for putting this out there.

Cloud Hosting | Reply

5/19/2010 5:49:38 AM #

I am having some troubles trying to load your blog. I have been read it many times before and never gotten something like this, but now when I try 2 load something it just takes a little while (4-11 minutes) and then just stop. I have tried with "www." or not. Does anyone know what the trouble could be? Ask your support at hosting..And, yes, thanks a lot for your post!

Shirley Tagaca | Reply

5/21/2010 4:25:47 AM #

I'm a big fan music! Check my website, I'm take music there!
-----------------------------
Regards,
<A href="http://dailyfreshmp3.com/">http://dailyfreshmp3.com/</A>

Latricia Hakeem | Reply

5/27/2010 11:26:40 AM #

I am a big fan of your blog! Check out my website, You can check your site there!

Tama Phinney | Reply

5/29/2010 8:33:31 AM #

I'm a big fan of your blog! Check out my website, You can analyze your weblog here!

www.bulkdomainnews.com | Reply

5/30/2010 11:35:34 AM #

I'm a huge fan of your weblog! Check out my website, You can analyze your blog there!

www.proverkadomenov.ru | Reply

Add comment

Name*
E-mail* (Will show your Gravatar icon)
Website
Country Country flag

b i u quote

Comment
Preview

Notify me when new comments are added

Erhan's Blog

its all just a bunch of pixels

2008 Coding Challenge II

Google Latitude Widget

Recent posts

Disclaimer

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

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

Erhan's Blog

its all just a bunch of pixels

2008 Coding Challenge II

Google Latitude Widget

Recent posts

Categories

Blogroll

Disclaimer

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