Post date: Sep 18, 2016 2:7:41 PM
"In an 80x80 matrix, contained in a comma-delimited text file, find the path from the top left to the bottom right, moving only right and down, with the smallest sum of all numbers crossed."
This problem is easier if you move backward from the end to the beginning, because at the end, the best path is obvious. Then we can just work step by step, making sure always to take the best of the two obvious paths.
-- I could create a table with 80 columns. But that would be pointless because I'm going to be throwing away the table in a moment.
-- This is just a temp table used for import.
CREATE TABLE #File (line varchar(500))
BULK INSERT #File FROM 'D:\matrix.txt' WITH (ROWTERMINATOR = '0x0a')
-- A couple things that will make it easier to process the table
ALTER TABLE #File ADD id INT NOT NULL IDENTITY(1,1)
UPDATE #File SET line = line + ','
DECLARE @col int = 1, @row int = 1, @val1 int, @val2 int
-- Populate the matrix table
-- There are different ways to do this. For example, I could have used a cursor.
-- Each row has a column to store the best path back to that point from the end.
CREATE TABLE #Matrix (c INT NOT NULL, r INT NOT NULL, value INT NOT NULL, best INT NULL, PRIMARY KEY (c, r))
WHILE @row <= 80
BEGIN
SET @col = 1
WHILE @col <= 80
BEGIN
INSERT INTO #Matrix (c, r, value)
SELECT @col, @row, LEFT(line,CHARINDEX(',', line) - 1)
FROM #File
WHERE id = @row
UPDATE #File
SET line = SUBSTRING(line,CHARINDEX(',', line) + 1, 500)
WHERE id = @row
SET @col = @col + 1
END -- Each column
SET @row = @row + 1
END -- Each row
DROP TABLE #File
/* Working from the end backward to the beginning, find out the best cost for each path. */
SET @col = 80
WHILE @col > 0
BEGIN
SET @row = 80
WHILE @row > 0
BEGIN
SET @val1 = 999999999 -- This is chosen if there is nothing there
SET @val2 = 999999999
-- Check down
SELECT @val1 = best
FROM #Matrix
WHERE c = @col
AND r = @row + 1
-- Check right
SELECT @val2 = best
FROM #Matrix
WHERE c = @col + 1
AND r = @row
-- Update the best score for this record.
-- In the bottom right corner, this is the value of the corner.
-- Otherwise, it is whatever path is cheaper.
UPDATE #Matrix
SET best = value + CASE
WHEN @col = 80 AND @row = 80 THEN 0
WHEN @val1 <= @val2 THEN @val1
ELSE @val2 END
WHERE c = @col
AND r = @row
SET @row = @row - 1
END -- Loop back through rows
SET @col = @col - 1
END -- Loop back through columns
SELECT best
FROM #Matrix
WHERE c = 1 AND r = 1
DROP TABLE #Matrix