Post date: Oct 02, 2016 2:32:15 PM
Oh no, another matrix problem.
"In an 80x80 matrix, contained in a comma-delimited text file, find the path from the top left to the bottom right, moving left, right, up, or down, with the smallest sum of all numbers crossed."
Again, this is even more complicated. We still avoid recursion (and with an 80x80 matrix, we definitely want to avoid recursion), but this time it's by hitting the entire data set, at once, repeatedly. There are no very clean way to do it. I can't just step backward like in the previous 2, because all 4 directions need to be considered.
In the start, I won't know the ideal scores for upper and left values. But when I do, I might have to reconsider everything down and to the right of it. At the start, most of the best values will be NULL. We slowly fill them in as their neighbors are filled in. Hit everything, over and over, until nothing can be improved.
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
-- Populate the matrix table
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
UPDATE #Matrix
SET best = value
WHERE c = 80 AND r = 80
WHILE 1 = 1 BEGIN
; WITH BestScores AS
(
SELECT m.c, m.r,
best = m.value + CASE
WHEN r.best <= ISNULL(l.best,999999999)
AND r.best <= ISNULL(u.best,999999999)
AND r.best <= ISNULL(d.best,999999999)
THEN r.best
WHEN l.best <= ISNULL(r.best,999999999)
AND l.best <= ISNULL(u.best,999999999)
AND l.best <= ISNULL(d.best,999999999)
THEN l.best
WHEN u.best <= ISNULL(r.best,999999999)
AND u.best <= ISNULL(l.best,999999999)
AND u.best <= ISNULL(d.best,999999999)
THEN u.best
WHEN d.best <= ISNULL(r.best,999999999)
AND d.best <= ISNULL(l.best,999999999)
AND d.best <= ISNULL(u.best,999999999)
THEN d.best
ELSE NULL END
FROM #Matrix m
LEFT OUTER JOIN #Matrix r
ON r.r = m.r AND r.c = m.c + 1
LEFT OUTER JOIN #Matrix l
ON l.r = m.r AND l.c = m.c - 1
LEFT OUTER JOIN #Matrix u
ON u.r = m.r - 1 AND u.c = m.c
LEFT OUTER JOIN #Matrix d
ON d.r = m.r + 1 AND d.c = m.c
)
UPDATE m
SET best = s.best
FROM BestScores s
INNER JOIN #Matrix m
ON m.c = s.c
AND m.r = s.r
WHERE s.best < ISNULL(m.best,999999999)
IF @@ROWCOUNT = 0 BREAK
END -- Best scores loop
SELECT best
FROM #Matrix
WHERE c = 1 AND r = 1
DROP TABLE #Matrix