Aug
7
2008
Coding Challenge // Puzzles

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

 

Continue Reading »
An article by ehosca No Comments
Jan
30
2008
Coding Challenge

2008 Coding Challenge I

The United States Postal Service currently sells stamps in the following denominations :

$0.01, $0.02, $0.03, $0.04, $0.05, $0.10, $0.24, $0.37, $0.39, $0.41, $0.48, $0.60, $0.63, $0.70,$0.75, $0.80, $0.83, $0.84, $0.87, $1.00, $3.85, $4.05, $4.60, $5.00, $14.40

James is preparing a small package to send out to his friend. The particular box that James has chosen has only enough room for 10 stamps after the address label is affixed.

What is the *minimum* amount of postage that cannot be placed on the box assuming James has an infinite number of stamps in each denomination ?

 

its : $89.96 which would require 11 stamp from the given denominations ...

 

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

namespace PostOfficePuzzle
{
    internal static class Program
    {
        /// 
        /// The main entry point for the application.
        /// 
        [STAThread]
        private static void Main()
        {
            var denominations =
                new List{1,2,3,4,5,10,24,37,39,41,48,60,63,70,
                              75,80,83,84,87,100,385,405,460,500,1440};
            // list of stamps
            List postage;

            // list of list of stamps 
            var solutions = new List>();

            // init single stamp solutions 
            foreach (int i in denominations)
                solutions.Add(new List(new[] {i}));

            for (int targetPostage = 0; targetPostage < int.MaxValue; targetPostage++)
            {
                postage = (from d in denominations
                           from s in solutions
                           where (d + s.Sum(i => i)).Equals(targetPostage)
                           orderby s.Count descending
                           select (new List(new[] {d}.Concat(s)))).LastOrDefault();

                if (postage != null)
                {
                    solutions.Add(postage);
                    WritePostage(postage);

                    // exit condition
                    if (postage.Count > 10)
                        Console.ReadLine();
                }
            }
        }

        private static void WritePostage(List postage)
        {
            string stampsList = string.Join(" , "
                                            , postage.ConvertAll(s => string.Format("{0:C}"
                                                                , (double) s/100)).ToArray());

            Console.WriteLine(string.Format("Postage = {0:C} Count = {1} Stamps = {2}"
                                            , (double) postage.Sum(i => i)/100
                                            , postage.Count
                                            , stampsList));
        }
    }
}

 

Continue Reading »
An article by ehosca No Comments

Month List