@eddie - Thanks, that's what I figured out last night, not obvious but makes sense when I stop to think about it. I'll bear this in mind when I'm dealing with long strings in the future.
@celko - Your solution will get the correct answer, however there are two problems in Project Euler that are two variants of the same problem. The first is a triangle of numbers with 15 rows to it, equating to 16,384 paths to be evaluated. Your solution will get the answer within the desired one minute of execution (it was similar to my first attempt).
The second is a triangle of numbers with 100 rows, giving a total number of POWER(2, 99) paths to evaluate. That might take some time to work though from the top down!
Instead, I went with this:
DECLARE @TriangleTable TABLE
RowId INT NOT NULL,
CellId INT NOT NULL,
CellValue INT NOT NULL,
PRIMARY KEY (RowId, CellId)
INSERT INTO @TriangleTable (RowId, CellId, CellValue)
SELECT[Rows].Position AS RowId,
Cells.Position AS CellId,
CONVERT(INT, Cells.Value) AS CellValue
FROMdbo.InlineCTE_StringSplitter(@TriangleString, NCHAR(9)) AS [Rows]
CROSS APPLYdbo.InlineCTE_StringSplitter([Rows].Value, N' ') AS Cells
OPTION (MAXRECURSION 0);
DECLARE @Row INT = (SELECT MAX(RowId) FROM @TriangleTable);
WHILE @Row > 1
WITH RolledUpRows AS
MAX(NextRow.CellValue + CurrentRow.CellValue) AS CellValue
FROM@TriangleTable AS CurrentRow
INNER JOIN@TriangleTable AS NextRow
ONNextRow.RowId = CurrentRow.RowId - 1
NextRow.CellId = CurrentRow.CellId
ORNextRow.CellId = CurrentRow.CellId - 1
WHERECurrentRow.RowId = @Row
SETCellValue = RolledUpRows.CellValue
FROM@TriangleTable AS TriangleTable
ONTriangleTable.CellId = RolledUpRows.CellId
ANDTriangleTable.RowId = RolledUpRows.RowId;
SET @Row -= 1;
SELECTCellValue AS Result
WHERERowId = 1;
Where @TriangleString is the rows of numbers where each row is separated by a tab character and each number is separated by a space.
As you can see, it's taking each row from the bottom up and adding each cell in the row above with the one cell in the previous row that gives the highest sum, all the way to the top of the triangle.