A method for generating item recommendations based on user preference for a particular item

Question : If you happen to like a particular Movie A, what is the probability you will also like Movie B ?

I’ll try to describe a simple rudimentary system that will try to answer that question. Lets make the following assumptions :

• We have an online community of users that we can collect information on whether they liked a particular movie and store those answers in a database.
• The end user can can make 3 distinct choices for each movie, they can either like it, dislike it or not care for it.

Setting up the Environment

Our database schema is represented by the following three tables.

The Users table contain information about our users. The Ratings table contain the actual votes cast for a particular RatingDefition and the RatingDefinition table contains the Movie names we’ll use for this example.

You can use the following scripts to create the database objects and populate with relevant data. For this particular case we have a total of 50 movies with 10000 users and a total of 500000 like/dislike/neutral votes. For this reason the populate script may take a while to complete.

The basic algorithm of calculating the probability of liking a Movie B given that you like Movie A is implemented as a User Defined Function that takes 2 parameters. First the movie that we liked and the second is the movie that we want to test.

CREATE FUNCTION [dbo].[fnGetProbabilityOfLikingItem] 
(
    @ItemAlreadyLiked UNIQUEIDENTIFIER,
    @ItemToBeTested UNIQUEIDENTIFIER
)
RETURNS FLOAT 
AS
BEGIN
RETURN ( 
 
        SELECT  (SUM(CASE WHEN r.Rating >0 THEN 1.0 ELSE 0.0 END)/SUM(CASE WHEN r.Rating !=0 THEN 1.0 ELSE 0.0 END)) * 100
        FROM    Ratings r
        WHERE   r.UserId IN 
                    (
                    -- all the users that liked that item
                    SELECT UserId 
                    FROM dbo.Ratings 
                    WHERE RatingDefinitionId = @ItemAlreadyLiked AND rating > 0
                    )
                    AND r.RatingDefinitionId = @ItemToBeTested
        )
END

This UDF determines the universe of users that had a favorable review of Movie A and then gathers all the other movies that they' have also liked and tabulates them based on the number of votes cast allowing us to do pair-wise comparisons like this :

DECLARE @ItemAlreadyLiked UNIQUEIDENTIFIER
DECLARE @ItemToBeTested UNIQUEIDENTIFIER
    
SELECT  @ItemAlreadyLiked = Id 
FROM    dbo.RatingDefinition
WHERE   Name = 'Titanic'
 
SELECT  @ItemToBeTested = Id
FROM    dbo.RatingDefinition
WHERE   Name = 'The Dark Knight'
 
SELECT  ProbabilityOfLiking = dbo.fnGetProbabilityOfLikingItem(@ItemAlreadyLiked, @ItemToBeTested)
 
RESULT : 
 
ProbabilityOfLiking
----------------------
50.9977
 
(1 row(s) affected)

Since the function is written as a scalar UDF we can also to things like :

This maybe useful to present a list to the user that they may also be interested in viewing the other movies listed. One thing to note here is the calculated probability numbers appear to be constrained within close proximity of each other. This is due to the fact the algorithm used to generate the votes relies on a random number generator which yields a uniform distribution of votes (ie. there a roughly equivalent number of like, dislike and neutral votes) resulting in this tight spread.

In closing the method outlined here is a much simplified version of what actually might be used in a real world application where the business logic will typically require analysis across several dimensions of varying numbers and their effects on each other rather than the single dimension that we have chosen to take a look at here.

Continue Reading »

An article by ehosca No Comments

AspDotNetStoreFront sales tax integration with CertiTAX

During a recent freelance engagement I stumbled upon an interesting challenge:

This was for an eCommerce website based on the popular AspDotNetStorefront package. ASPDNSF is a capable piece of software that allows for a multitude of customization options to tailor the website to operator needs. This particular eCommerce operation was based out of New York state and their requirements were the accurate calculation of sales tax for all orders that are to be shipped to NY. The ASPDNSF package allows for customization of tax rates at various geographical levels such as State, Region and ZipCode. For New York State however the zipcode is not granular enough to guarantee an uniform tax rate for all adresses that fall within. So 2 different addresses that happen to be in the same zipcode can possibly fall under different tax jurisdictions with different applicable rates.

Fortunately there are online vendors that exist that do precisely this sort of thing (for a fee of course). One such vendor is CCH. CCH publishes a webservice that makes it possible to perform various tax calculations based on specific adress information.

I'll describe a way to integrate an online realtime tax rate lookup system with no code changes to the ASPDNSF package. This solution will work for those installations that use Sql Server 2005/2008 as their data store.

We begin by creating a new DLL project in Visual Studio 2008 (the C# Express 2008 version works just fine as well) and call it CCHTaxRateLookup.

Add a Web Reference to https://webservices.esalestax.net/CertiTAX.NET/CertiCalc.asmx?WSDL and rename the Web reference name to : CertiTAX.NET.SalesTaxOnlineCalc

add the following code

using System; 

using System.Data.SqlTypes; 

using CCHTaxRateLookup.CertiTAX.NET.SalesTaxOnlineCalc; 

using Microsoft.SqlServer.Server; 

public class UserDefinedFunctions 

{ 

    [SqlFunction(DataAccess = DataAccessKind.Read, IsDeterministic = true)]

    public static SqlDouble CCHTaxRateLookup(string address1, string address2, 

                                             string city, string zipCode, 

                                             string merchantKey, string sku) 

    { 

        var address = new Address 

                          { 

                              Street1 = address1, 

                              Street2 = address2, 

                              City = city, 

                              PostalCode = zipCode, 

                              Nation = "USA" 

                          }; 

        var order = new Order 

                        { 

                            Address = address, 

                            Nexus = "POSH", 

                            SerialNumber = merchantKey, 

                            CalculateTax = true, 

                            ConfirmAddress = false, 

                            LineItems = new OrderLineItem[1] 

                        }; 

        var li = new OrderLineItem 

                     { 

                         ItemId = "Item1", 

                         Quantity = 1, 

                         ExtendedPrice = Decimal.Parse("10000.00"), 

                         StockingUnit = sku 

                     }; 

        order.LineItems[0] = li; 

        try 

        { 

            var calc = new CertiCalc(); 

            TaxTransaction tx = calc.Calculate(order); 

            return new SqlDouble(Convert.ToDouble(tx.TotalTax)/100); 

        } 

        catch 

        { 

            return new SqlDouble(0.00); 

        } 

    } 

}

This little snippet creates a “dummy” order with a single line item and submits it to the webservice for determining the proper tax rate. The price for the item is set to $10000.00 which will give us a 3 digit accuracy for expressing the resulting tax rate. You may want to setup a dummy taxable SKU with the web service before hand to ensure the item will get taxed. This particular eCommerce site had a very small number of SKU’s they sell online making it easier to setup a single rate lookup and use the built-in tax calculation functionality in ASPDNSF.

Compile the DLL and register the assembly with Sql Server. Since we have a Web Reference there will also be a CCHTaxRateLookup.XmlSerializers.dll located in the build directory, this DLL will also be required registered with Sql Server.

Note:  you may also need to set the ‘clr enabled’ option on the server and mark your ASPDNSF database as TRUSTWORTHY if your database is not setup to host assemblies.

Now that we have the assembly registered we need to create a function that points to our SQLCLR so that we can call it using T-SQL.

USE [ASPDNSFDatabase] 

GO 

CREATE FUNCTION [dbo].[CCHTaxRateLookup](@address1 [nvarchar](200), @address2 [nvarchar](200), @city [nvarchar](50), @zipCode [nvarchar](10), @merchantKey [nvarchar](50), @sku [nvarchar](30)) 

RETURNS [float] WITH EXECUTE AS CALLER 

AS 

: none; padding: 0px;">EXTERNAL NAME [CCHTaxRateLookup].[UserDefinedFunctions].[CCHTaxRateLookup] 

 0px;">GO

--------

At this point you should be able to test the function using Query Analyzer.

Notice the 2 different tax rates returned for 2 addresses that happen to be in the same zipcode.

With all this plumbing in place we are now ready to inject our enhanced sales tax rate information directly into ASPDNSF. The key point of injection is a stored procedure called aspdnsf_GetCartSubTotalAndTax. Before we move forward with this its useful to remember that this stored proc gets called an awful lot and reaching out to a webservice from SQLCLR for each call can be a rather costly operation. One solution to speed up the lookups is to create a separate lookup table that associates a particular AddressId with the proper taxrate.

CREATE TABLE [dbo].[AddressTaxRate](

    [AddressID] [int] NOT NULL,

    [TaxRate] [float] NOT NULL

) ON [PRIMARY]

GO

This will allow us to cache the taxrate lookups for a given address and not hit the expensive web service everytime the procedure is called. ( and it gets called a lot ).

With all this in place we are ready to modify the stored aspdnsf_GetCartSubTotalAndTax procedure as follows :

{...}

-- Calculate item Tax 

declare @vatroundingmethod int

select @vatroundingmethod = case configvalue when 'true' then 1 else 0 end from dbo.appconfig with (nolock) where [name] = 'VAT.RoundPerItem'

-- these are the variables we'll need to populate

DECLARE @TAXRATE FLOAT;

DECLARE @address1 VARCHAR(200);

DECLARE @address2 VARCHAR(200);

DECLARE @state2 VARCHAR(20);

DECLARE @city VARCHAR(50);

DECLARE @zip VARCHAR(10);

DECLARE @ShipAddressID INT;

-- lookup the shipping address and initialize the variables

SELECT @address1 = a.Address1, @address2 = a.Address2, @city = a.City, @zip = a.Zip, @state2 = a.State,

        @ShipAddressID = a.AddressID

FROM Customer c JOIN Address a ON c.ShippingAddressID = a.AddressID 

WHERE c.CustomerID = @customerid

-- we only do this for NY

IF @state2 = 'NY'

    BEGIN

        -- have we seen this address before ?

        IF EXISTS (SELECT TaxRate FROM AddressTaxRate WHERE AddressId = @ShipAddressID)

        BEGIN

            SELECT @TAXRATE = TaxRate FROM AddressTaxRate WHERE AddressId = @ShipAddressID

        END

        ELSE

        BEGIN

            -- no, make the webservice call and find the tax rate

            SELECT @TAXRATE = dbo.CCHTaxRateLookup(@address1, @address2, @city, @zip, 'YOUR_KEY_HERE', 'SKU2')

            -- make a note of it for subsequent calls

            INSERT INTO AddressTaxRate (AddressId, TaxRate) VALUES (@ShipAddressID, @TAXRATE)

        END

    END

ELSE

    BEGIN

        SELECT @TAXRATE = 0

    END

-- apply the taxrate on all taxable items in shopping cart

UPDATE @tblsubtotal

SET Tax = CASE sc.IsTaxable  

            WHEN 1 THEN 

                case @vatroundingmethod     

                  when 1 then round(FinalDiscountedPrice*((isnull(cr.taxrate, 0)+isnull(sr.taxrate, 0)+isnull(zr.taxrate, 0))/100), 2)*Qty    

                   else round((FinalDiscountedPrice*Qty)*(@TAXRATE/100), 2)                      

                   end 

            ELSE 0 

           END

{...}

You may also wish to move the webservice call out of the proc altogether and place it inside an UPDATE/INSERT trigger on the Address table as a further optimization.

Useful links : The New York State Department of Taxation and Finance makes available this particular page to perform address based sales tax rate lookups on an ad-hoc basis.

Continue Reading »

An article by ehosca No Comments

US States Puzzle

Originally taken from

http://interviewpattern.com/post/Puzzles-and-Riddles-on-the-interview-(Part-e28093-I).aspx

Take the names of two U.S. States, mix them all together, then rearrange the letters to form the names of two other U.S. States.

What states are these?

using our Combinatorics library 

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

namespace StatePuzzle
{
internal class Program
{
    private static void Main(string[] args)
    {
        var listStates = new List
            {
            "Alabama","Alaska","AmericanSamoa","Arizona","Arkansas","California",
            "Colorado","Connecticut","Delaware","DistrictofColumbia","Florida",
            "Georgia","Guam","Hawaii","Idaho","Illinois","Indiana","Iowa",
            "Kansas","Kentucky","Louisiana","Maine","Maryland","Massachusetts",
            "Michigan","Minnesota","Mississippi","Missouri","Montana","Nebraska",
            "Nevada","NewHampshire","NewJersey","NewMexico","NewYork","NorthCarolina",
            "NorthDakota","Ohio","Oklahoma","Oregon","Pennsylvania",
            "PuertoRico","RhodeIsland","SouthCarolina","SouthDakota","Tennessee",
            "Texas","Utah","Vermont","Virginia","VirginIslands","Washington",
            "WestVirginia","Wisconsin","Wyoming"
            };

        foreach (var statePair in Combinatorics.Combinations(listStates, 2))
        {

            var chars = string.Join(string.Empty, statePair.ToArray())
                        .ToLower()
                        .ToCharArray()
                        .OrderBy(c => c);

            var toSearch = listStates.Except(statePair).ToList();

            foreach (var statePairSeach in Combinatorics.Combinations(toSearch, 2))
            {

                var charsSearch = string.Join(string.Empty, statePairSeach.ToArray())
                                .ToLower()
                                .ToCharArray()
                                .OrderBy(c => c);
                if( chars.Count() == charsSearch.Count() && 
                    chars.SequenceEqual(charsSearch))
                {
                    Console.Write("Letters that make up the States :");
                    Console.Write(string.Join(",", statePair.ToArray()));
                    Console.WriteLine("");
                    Console.Write("Can be re-arranged to read :");
                    Console.Write(string.Join(",", statePairSeach.ToArray()));
                    Console.WriteLine("");
                    Console.WriteLine("");
                }
            }
        }

        Console.ReadLine();
    }
}
}

Continue Reading »

An article by ehosca No Comments

Google Latitude widget for BlogEngine.Net

I’ve created a widget that enables you to share your Google Public Location Badge directly in your BlogEngine.Net powered blog.

Just drop the contents of the attached file into the \widgets folder.

Continue Reading »

An article by ehosca No Comments

Generating C# classes from FpML Schema

This problem recently came up while discussing a project that will use FpML documents. FpML is an evolving standard that aims to be the industry standard protocol for complex financial products. Its an extensive project with a good deal of support from major players and a sharp talent pool behind it.

I’ll try to explain how code generation facilities built into the .Net framework can provide us with a basic usable class library that encapsulates the FpML protocol.

We begin by downloading the relevant schemas from the FpML website (requires free registration) and extracting them to a local folder (C:\FpML).

Then we fire up Visual Studio and create a new Console Application. At this point you maybe wondering if it wouldn’t be simpler to just use XSD.EXE for the code generation. Unfortunately XSD.EXE has difficulty resolving external schemas.

using System;
using System.CodeDom;
using System.CodeDom.Compiler;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Xml.Schema;
using System.Xml.Serialization;
using Microsoft.CSharp;

namespace ConsoleApplication1
{
    internal class Program
    {
        public const string rootFolder = @"C:\FpML\xml\";

        private static void Main(string[] args)
        {
            XmlSchema rootSchema = GetSchemaFromFile("fpml-main-4-2.xsd");

            var schemaSet = new List<XmlSchemaExternal>();

            ExtractIncludes(rootSchema, ref schemaSet);

            var schemas = new XmlSchemas { rootSchema };

            schemaSet.ForEach(schemaExternal => schemas.Add(GetSchemaFromFile(schemaExternal.SchemaLocation)));

            schemas.Compile(null, true);

            var xmlSchemaImporter = new XmlSchemaImporter(schemas);

            var codeNamespace = new CodeNamespace("Hosca.FpML4_2");
            var xmlCodeExporter = new XmlCodeExporter(codeNamespace);

            var xmlTypeMappings = new List<XmlTypeMapping>();

            foreach (XmlSchemaType schemaType in rootSchema.SchemaTypes.Values)
                xmlTypeMappings.Add(xmlSchemaImporter.ImportSchemaType(schemaType.QualifiedName));
            foreach (XmlSchemaElement schemaElement in rootSchema.Elements.Values)
                xmlTypeMappings.Add(xmlSchemaImporter.ImportTypeMapping(schemaElement.QualifiedName));

            xmlTypeMappings.ForEach(xmlCodeExporter.ExportTypeMapping);

            CodeGenerator.ValidateIdentifiers(codeNamespace);

            foreach (CodeTypeDeclaration codeTypeDeclaration in codeNamespace.Types)
            {
                for (int i = codeTypeDeclaration.CustomAttributes.Count - 1; i >= 0; i--)
                {
                    CodeAttributeDeclaration cad = codeTypeDeclaration.CustomAttributes[i];
                    if (cad.Name == "System.CodeDom.Compiler.GeneratedCodeAttribute")
                        codeTypeDeclaration.CustomAttributes.RemoveAt(i);
                }
            }

            using (var writer = new StringWriter())
            {
                new CSharpCodeProvider().GenerateCodeFromNamespace(codeNamespace, writer, new CodeGeneratorOptions());

                //Console.WriteLine(writer.GetStringBuilder().ToString());

                File.WriteAllText(Path.Combine(rootFolder, "FpML4_2.Generated.cs"), writer.GetStringBuilder().ToString());
            }

            Console.ReadLine();
        }

        private static XmlSchema GetSchemaFromFile(string fileName)
        {
            using (var fs = new FileStream(Path.Combine(rootFolder, fileName), FileMode.Open))
                return XmlSchema.Read(fs, null);
        }

        private static void ExtractIncludes(XmlSchema xmlSchema, ref List<XmlSchemaExternal> schemaList)
        {
            foreach (XmlSchemaExternal include in xmlSchema.Includes)
            {
                if (!schemaList.Select(s => s.SchemaLocation).Contains(include.SchemaLocation))
                    schemaList.Add(include);

                if (include.Schema == null)
                {
                    XmlSchema schema = GetSchemaFromFile(include.SchemaLocation);

                    ExtractIncludes(schema, ref schemaList);
                }
                else
                    ExtractIncludes(include.Schema, ref schemaList);
            }
        }
    }
}

Running this generates the following code:

FpML4_2.Generated.cs (1.10 mb)

Continue Reading »

An article by ehosca No Comments

Script to drop and re-create all foreign keys

------------
-- Generate Drop Disable.sql

SET NOCOUNT ON

print 'USE ' + DB_NAME() 
print ''

-- Generate Drops for All Foreign Keys in Database
print '-- Drop Foreign Keys'
print ''


select distinct 'ALTER TABLE ['+ SCHEMA_NAME(CAST(OBJECTPROPERTYEX(tbl.id , 'SchemaId') AS INT)) +'].[' + object_name(fkeyid) + 

'] DROP CONSTRAINT ' + object_name(constid) + 

CHAR(13) + CHAR(10) + 'go' 

from sysforeignkeys 

JOIN sysobjects ON sysobjects.id = constid 
JOIN sysobjects tbl ON tbl.id = fkeyid 

JOIN syscolumns col ON col.id = fkeyid AND col.colid = fkey 
JOIN sysobjects ltbl ON ltbl.id = rkeyid 

JOIN syscolumns lcol ON lcol.id = rkeyid AND lcol.colid = rkey 


go 


-- Generate Disable all triggers
print ''
print '-- Disable Triggers'
print ''

select distinct 'ALTER TABLE [dbo].[' + OBJECT_NAME(parent_obj) +
    '] DISABLE TRIGGER ALL ' + 
    CHAR(13) + CHAR(10) + 'go'
FROM sysobjects
WHERE OBJECTPROPERTY(id, 'IsTrigger') = 1 and parent_obj in
    (select id from sysobjects where xtype = 'U')
go

-----------------------------------------------------------
-- Generate Add Enable.sql

SET NOCOUNT ON

print 'USE ' + DB_NAME() 
print ''

-- Generate Adds for All Foreign Keys in Database
print '-- Add Foreign Keys'
print ''

DECLARE @fkName varchar(800),@schema VARCHAR(800), @tabName varchar(800), @refName varchar(800)
DECLARE @isDel int, @isUpd int, @fkCol varchar(8000), @refCol varchar(8000)
DECLARE @pline varchar(8000)

DECLARE fkCursor CURSOR FOR

    SELECT
     SCHEMA_NAME(CAST(OBJECTPROPERTYEX(tbl.id , 'SchemaId') AS INT)),
     sysobjects.name,
     tbl.name,
     ltbl.name,
    OBJECTPROPERTY ( constid , 'CnstIsDeleteCascade' ),
    OBJECTPROPERTY ( constid , 'CnstIsUpdateCascade' )
    FROM
     sysforeignkeys
     JOIN sysobjects ON sysobjects.id = constid
     JOIN sysobjects tbl ON tbl.id = fkeyid
     JOIN syscolumns col ON col.id = fkeyid AND col.colid = fkey
     JOIN sysobjects ltbl ON ltbl.id = rkeyid
     JOIN syscolumns lcol ON lcol.id = rkeyid AND lcol.colid = rkey    
    ORDER BY sysobjects.name    

OPEN fkCursor

FETCH NEXT FROM fkCursor 
    INTO @schema, @fkName, @tabName, @refName, @isDel, @isUpd

WHILE @@FETCH_STATUS = 0
BEGIN
    select @fkCol = NULL
    SELECT @fkCol = ISNULL(@fkCol + ', ','') + '[' + col_name(fkeyid, fkey) + ']'
    from sysforeignkeys 
    where object_name(constid) = @fkName 
    order by keyno

    select @refCol = NULL
    SELECT @refCol = ISNULL(@refCol + ', ','') + '[' + col_name(rkeyid, rkey) + ']'
    from sysforeignkeys 
    where object_name(constid) = @fkName 
    order by keyno

    select @pline = 'ALTER TABLE [' + @schema + '].[' + @tabName + '] ADD CONSTRAINT [' + @fkName + ']' +
    CHAR(13) + CHAR(10) + '   FOREIGN KEY (' + @fkCol + ') REFERENCES [' + @schema + '].[' + @refName +
    '] (' + @refCol + ')'
    
    if @isDel = 1 
        select @pline = @pline + CHAR(13) + CHAR(10) + 
            '     ON DELETE CASCADE'
    if @isUpd = 1 
        select @pline = @pline + CHAR(13) + CHAR(10) + 
            '     ON UPDATE CASCADE'
    select @pline = @pline + CHAR(13) + CHAR(10) + 'go'
    print @pline
    FETCH NEXT FROM fkCursor 
        INTO @schema, @fkName, @tabName, @refName, @isDel, @isUpd
END

CLOSE fkCursor
DEALLOCATE fkCursor
GO

-- Generate Enable all triggers
print ''
print '-- Enable Triggers'
print ''

select distinct 'ALTER TABLE [dbo].[' + OBJECT_NAME(parent_obj) +
    '] ENABLE TRIGGER ALL ' + 
    CHAR(13) + CHAR(10) + 'go'
FROM sysobjects
WHERE OBJECTPROPERTY(id, 'IsTrigger') = 1 and parent_obj in
    (select id from sysobjects where xtype = 'U')
go

Continue Reading »

An article by ehosca No Comments

Gently killing the explorer.exe process

Go to Start > Shutdown. When the dialog appears, hold CTRL+ALT+SHIFT and press Cancel. Explorer will cleanly unload all of it’s resources and shutdown. To start it back up, open Task Manager (CTRL+SHIFT+ESC is one way) and go to File > New Task and run ‘explorer’.

This method was designed for people writing plugins and handlers for Explorer who needed to be able to unload it all and start fresh without rebooting or uncleanly killing Explorer’s process.

Continue Reading »

An article by ehosca No Comments

2008 Coding Challenge II

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

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

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

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

Continue Reading »

An article by ehosca No Comments

Number Puzzle

The answer is (select the text below to reveal the answer )

---------------------------------------------------------------------------

The answer is 16 ... The cube is filled with numbers from 1 to 16  in no particular order ... The diagonal highlight is nothing more than a distraction ...

---------------------------------------------------------------------------

Continue Reading »

An article by ehosca No Comments