Post date: Jun 05, 2014 12:51:2 AM
"In triangular array, which you must travel down from the apex to the bottom like a pachinko game, what is the highest point score possible?"
This one really sucked. The calculation isn't bad (just follow the triangle from bottom to top, calculating a single row in each pass). But loading rows of numbers into a triangle is a huge pain. Their data isn't laid out for easy import.
DECLARE @NastyData varchar(2000) =
'75|' +
'95 64|' +
'17 47 82|' +
'18 35 87 10|' +
'20 04 82 47 65|' +
'19 01 23 75 03 34|' +
'88 02 77 73 07 63 67|' +
'99 65 04 28 06 16 70 92|' +
'41 41 26 56 83 40 80 70 33|' +
'41 48 72 33 47 32 37 16 94 29|' +
'53 71 44 65 25 43 91 52 97 51 14|' +
'70 11 33 28 77 73 17 78 39 68 17 57|' +
'91 71 52 38 17 14 91 43 58 50 27 29 48|' +
'63 66 04 68 89 53 67 30 73 16 69 87 40 31|' +
'04 62 98 27 23 09 70 98 73 93 38 53 60 04 23'
SET @NastyData = REPLACE(@NastyData,' ','')
DECLARE @id INT, @depth INT = 1, @width INT, @place INT
CREATE TABLE #Triangle (
id INT PRIMARY KEY NOT NULL IDENTITY(1,1),
depth INT NOT NULL,
num INT NOT NULL,
parentId1 INT NULL,
parentId2 INT NULL,
value INT NULL)
WHILE 1 = 1
BEGIN
IF @NastyData = '' BREAK
-- Look for newlines. When one is encountered, add 1 to the depth.
IF LEFT(@NastyData,1) = '|'
BEGIN
SET @depth = @depth + 1
SET @NastyData = STUFF(@NastyData,1,1,'')
END -- Newline
INSERT INTO #Triangle (depth, num)
SELECT @depth, LEFT(@NastyData,2)
SET @NastyData = STUFF(@NastyData,1,2,'')
END -- Loading triangle table
-- Set two parents for each row
DECLARE TriangleParents CURSOR LOCAL FOR
SELECT id
, depth
, COUNT(*) OVER (PARTITION BY depth)
, ROW_NUMBER() OVER (PARTITION BY depth ORDER BY id)
FROM #Triangle
WHERE depth > 1
ORDER BY id
OPEN TriangleParents
WHILE 1 = 1
BEGIN
FETCH NEXT FROM TriangleParents INTO @id, @depth, @width, @place
IF @@FETCH_STATUS <> 0 BREAK
-- Place on the row farthest to the left. One parent.
IF @place = 1
UPDATE #Triangle
SET parentId2 = (SELECT MIN(id) FROM #Triangle WHERE depth = @depth - 1)
WHERE id = @id
-- Place farthest to the right. One parent.
ELSE IF @place = @width
UPDATE #Triangle
SET parentId1 = (SELECT MAX(id) FROM #Triangle WHERE depth = @depth - 1)
WHERE id = @id
-- Place in the middle. Two parents.
ELSE BEGIN
UPDATE #Triangle
SET parentId1 = (SELECT parentId2 FROM #Triangle WHERE id = @id - 1)
WHERE id = @id
UPDATE #Triangle
SET parentId2 = parentId1 + 1
WHERE id = @id
END -- Middle
END -- TriangleParents
CLOSE TriangleParents
DEALLOCATE TriangleParents
-- Now that the table is loaded, we can finally start calculating, working up from the bottom.
-- We can do this because we don't care about what the path is. The question only asks for the total.
-- On each number, I can overwrite the value as long as the new value is higher. Thus, I only have to keep track of one number for each point.
-- I'm glad I don't need to store the path.
-- Work backward from the end
SELECT @id = MAX(id)
FROM #Triangle
WHILE 1 = 1
BEGIN
UPDATE #Triangle
SET value = num + ISNULL((SELECT MAX(value) FROM #Triangle WHERE parentId1 = @id OR parentId2 = @id),0)
WHERE id = @id
SET @id = @id - 1
IF @id = 0 BREAK
END -- id is greater than 0
SELECT value
FROM #Triangle
WHERE id = 1
DROP TABLE #Triangle
Problem 67 is the exact same problem, only with a bigger set of numbers. Only the value of @NastyData need change, or you could use some kind of bulk insert, openrowset, SSIS, or whatever you prefer. I used Notepad++ to build the set statement. Note that the number is too big to set it in a single statement, so you have to do part of the triangle and then add the rest.
I'm not going to include 50 lines of numbers here. I'll leave it as an exercise for the student.