Post date: Sep 25, 2016 2:6:30 PM
"In an 80x80 matrix, contained in a comma-delimited text file, find the path from any cell in the left column to the right column, moving only right, up, and down, with the smallest sum of all numbers crossed."
Again, this is slightly more complicated, but we avoid recursion by working backward from the end. Two things limit the results: While you can go either up or down, once you have chosen a direction, you won't go back on that row, and hitting the same block more than once is not the best path.
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
CREATE TABLE #Matrix (c INT NOT NULL, r INT NOT NULL, value INT NOT NULL, bestu INT NULL, bestd 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 = 1
-- Go down from the top (this is the Down -> Up path)
WHILE @row <= 80
BEGIN
SET @val1 = 999999999 -- This is chosen if there is nothing there
SET @val2 = 999999999
-- Check up
SELECT @val1 = bestu
FROM #Matrix
WHERE c = @col
AND r = @row - 1
-- Check right
SELECT @val2 = CASE WHEN bestu <= bestd THEN bestu ELSE bestd END
FROM #Matrix
WHERE c = @col + 1
AND r = @row
-- On the right column, it is the value of the cell. There is no need to go up/down and increase your score.
-- On the left column, it is the right value. There is no need to go up/down and increase your score.
-- Otherwise, it is the best up-path score.
UPDATE #Matrix
SET bestu = value + CASE
WHEN @col = 80 THEN 0
WHEN @col = 1 THEN @val2
WHEN @val1 <= @val2 THEN @val1
ELSE @val2 END
WHERE c = @col
AND r = @row
SET @row = @row + 1
END -- Loop back through rows
SET @row = 80
-- Go up from the bottom (this is the Up -> Down path)
WHILE @row > 0
BEGIN
SET @val1 = 999999999 -- This is chosen if there is nothing there
SET @val2 = 999999999
-- Check down
SELECT @val1 = bestd
FROM #Matrix
WHERE c = @col
AND r = @row + 1
-- Check right
SELECT @val2 = CASE WHEN bestu <= bestd THEN bestu ELSE bestd END
FROM #Matrix
WHERE c = @col + 1
AND r = @row
-- On the right, it is the value of the cell. There is no need to go up/down and increase your score.
-- On the left, it is the right value. There is no need to go up/down and increase your score.
-- Otherwise, it is the best down-path score.
UPDATE #Matrix
SET bestd = value + CASE
WHEN @col = 80 THEN 0
WHEN @col = 1 THEN @val2
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 TOP 1 CASE WHEN bestu <= bestd THEN bestu ELSE bestd END
FROM #Matrix
WHERE c = 1
ORDER BY 1
DROP TABLE #Matrix