LifeFlame

I don’t have much time right now but I’ll clean up this post later. For now just enjoy the snippet.

DECLARE @Threshold int
DECLARE @input TABLE (
	ID int,
	name varchar(10),
	size int,
	groupNum int
)

SET @Threshold = 500

INSERT INTO @input (name, size)
	SELECT 'rrkedt', 67
	UNION ALL
	SELECT 'zugmto', 114
	UNION ALL
	SELECT 'jpddyv', 121
	UNION ALL
	SELECT 'lzrphx', 239
	UNION ALL
	SELECT 'jvltsm', 212
	UNION ALL
	SELECT 'yvowre', 107
	UNION ALL
	SELECT 'sxpchv', 244
	UNION ALL
	SELECT 'ighgvn', 249
	UNION ALL
	SELECT 'kgomhv', 173
	UNION ALL
	SELECT 'eshsya', 104
	UNION ALL
	SELECT 'xhqfpj', 175
	UNION ALL
	SELECT 'epptoi', 146
	UNION ALL
	SELECT 'ainkze', 218
	UNION ALL
	SELECT 'tbpukv', 148
	UNION ALL
	SELECT 'visdid', 30
	UNION ALL
	SELECT 'cpjhkn', 27
	UNION ALL
	SELECT 'rapqxl', 221
	UNION ALL
	SELECT 'fakkki', 176
	UNION ALL
	SELECT 'mgkuos', 69
	UNION ALL
	SELECT 'hlnvjc', 190
	UNION ALL
	SELECT 'yrlmfh', 244
	UNION ALL
	SELECT 'pjrnhx', 95
	UNION ALL
	SELECT 'fnggir', 11
	UNION ALL
	SELECT 'pnkxhd', 88
	UNION ALL
	SELECT 'jtmahw', 192
	UNION ALL
	SELECT 'kwapjv', 5
	UNION ALL
	SELECT 'chpsde', 30
	UNION ALL
	SELECT 'fwptfk', 96
	UNION ALL
	SELECT 'znjsiu', 228
	UNION ALL
	SELECT 'etamhm', 112
	UNION ALL
	SELECT 'tjzuhv', 219
	UNION ALL
	SELECT 'npzgdg', 107
	UNION ALL
	SELECT 'ripcml', 99
	UNION ALL
	SELECT 'rggrtk', 8
	UNION ALL
	SELECT 'momslh', 204
	UNION ALL
	SELECT 'fotckt', 142
	UNION ALL
	SELECT 'rqurdw', 155
	UNION ALL
	SELECT 'veonhb', 64
	UNION ALL
	SELECT 'rkhrjc', 146
	UNION ALL
	SELECT 'jfvxri', 241
	UNION ALL
	SELECT 'qhsdyq', 208
	UNION ALL
	SELECT 'uwndum', 15
	UNION ALL
	SELECT 'aokicj', 60
	UNION ALL
	SELECT 'iytjto', 26
	UNION ALL
	SELECT 'ovyzic', 222
	UNION ALL
	SELECT 'lpixws', 92
	UNION ALL
	SELECT 'bnhuod', 223
	UNION ALL
	SELECT 'emszvg', 248
	UNION ALL
	SELECT 'udznjm', 68
	UNION ALL
	SELECT 'kdxjql', 45
	UNION ALL
	SELECT 'biggy', 501
	UNION ALL
	SELECT 'cust1', 278
	union all
	SELECT 'a', 250
	UNION ALL
	SELECT 'b', 249
	UNION ALL
	SELECT 'c', 249
	UNION ALL
	SELECT 'd', 2
	UNION ALL
	SELECT 'e', 125
	UNION ALL
	SELECT 'f', 125
	UNION ALL
	SELECT 'g', 1
	UNION ALL
	SELECT 'h', 75
	UNION ALL
	SELECT 'i', 1
	UNION ALL
	SELECT 'j', 75

--select * from @input 



DECLARE @Concatchar char = ','
	,	@CurrentHistory varchar(max)
	,	@GroupNum int = 0
	,	@LongestPath int
DECLARE @Paths TABLE (
	length int,
	history varchar(max),
	size int
)
DECLARE @R TABLE (
	length int,
	id int,
	size int,
	history varchar(max)
)

RAISERROR('start', 0,0) WITH NOWAIT
/*
;WITH r as (
	SELECT length=1, name, size, history = cast(@Concatchar+name+@Concatchar as varchar(max))
		FROM @input
	UNION ALL
	SELECT length=r.length+1, name= i.name, size=r.size+i.size, history=r.history + i.name+@Concatchar
		FROM r
		JOIN @input i ON r.name < i.name 
			WHERE i.size + r.size <= @Threshold 
)

INSERT INTO @Paths (length, history, size)
	SELECT length, history, size
		FROM r
--3740068 rows

WHILE EXISTS(SELECT * FROM @Paths)
BEGIN
	SELECT TOP(1) @CurrentHistory = history
		FROM @Paths
	ORDER BY size desc, length, history
	
	UPDATE @input 
		SET groupNum = @GroupNum 
			WHERE @CurrentHistory LIKE '%' + @Concatchar + name + @Concatchar + '%'
			
	DELETE p
		FROM @Paths p
		JOIN @input i ON i.groupNum = @GroupNum AND p.history LIKE '%' + @Concatchar + i.name + @Concatchar + '%'
		
	SET @GroupNum = @GroupNum + 1
END
*/

--fill in ID column with unique ints

UPDATE i
	SET i.id = r.id 
	FROM (
		SELECT id=ROW_NUMBER() OVER (ORDER BY size desc), name, size
			FROM @input 
	) r
	JOIN @input i on i.name = r.name and i.size = r.size 
	
--if anything is over the threshold, put each in their own group now
UPDATE i
	SET i.groupNum = r.groupNum 
	FROM (
		SELECT groupNum=ROW_NUMBER() OVER (ORDER BY id), id
			FROM @input 
				WHERE size >= @Threshold 
	) r
	JOIN @input i on i.id = r.id

SELECT @GroupNum=ISNULL(MAX(groupNum),0)+1 FROM @input 

INSERT @R (length, id, size, history)
	SELECT 1, id, size, cast(@Concatchar + CAST(id as varchar) + @Concatchar as varchar(max))
		FROM @input 
			WHERE groupNum IS NULL
SET @LongestPath = 1
			
WHILE (SELECT SUM(size) FROM @input WHERE groupNum IS NULL) > @Threshold
BEGIN

	/*SELECT * FROM @R 
		WHERE length = @LongestPath 	
	*/
	INSERT @R (length, id, size, history)
		SELECT r.length + 1, i.id, r.size + i.size, r.history + CAST(i.id as varchar) + @Concatchar
			FROM @R r
			JOIN @input i ON r.id < i.id 
				WHERE i.groupNum IS NULL 
					AND i.size + r.size <= @Threshold
					
	--if we didn't find any new paths just quit
	IF @LongestPath = (SELECT TOP(1) length FROM @R ORDER BY length DESC)
		BREAK;
			
	SELECT TOP(1) @LongestPath = length 
		FROM @R 
	ORDER BY length DESC
	
	WHILE EXISTS(SELECT * FROM @R WHERE size = @Threshold )
	BEGIN
		SELECT TOP(1) @CurrentHistory = history
			FROM @R
				WHERE size = @Threshold
		ORDER BY length, history
		
		UPDATE @input 
			SET groupNum = @GroupNum 
				WHERE @CurrentHistory LIKE '%' + @Concatchar + CAST(id as varchar) + @Concatchar + '%'
				
		DELETE r
			FROM @R r
			JOIN @input i ON i.groupNum = @GroupNum AND r.history LIKE '%' + @Concatchar + cast(i.id as varchar) + @Concatchar + '%'
			
		RAISERROR('group found', 1, @GroupNum) WITH NOWAIT
		SET @GroupNum = @GroupNum + 1
	END
END

WHILE EXISTS(SELECT * FROM @R)
BEGIN
	SELECT TOP(1) @CurrentHistory = history
		FROM @R
	ORDER BY size desc, length, history

	RAISERROR(@CurrentHistory, 1, 0) WITH NOWAIT
		
	UPDATE @input 
		SET groupNum = @GroupNum 
			WHERE @CurrentHistory LIKE '%' + @Concatchar + cast(id as varchar) + @Concatchar + '%'
			
	DELETE r
		FROM @R r
		JOIN @input i ON i.groupNum = @GroupNum AND r.history LIKE '%' + @Concatchar + cast(i.id as varchar) + @Concatchar + '%'
			
	RAISERROR('group found', 1, @GroupNum) WITH NOWAIT
	SET @GroupNum = @GroupNum + 1
END

RAISERROR('end', 0,0) WITH NOWAIT

select * from @input 
order by groupNum 

select groupNum, SUM(Size)
	from @input 
GROUP BY groupNum