Post date: Dec 13, 2015 1:3:5 AM
"A file contains 50 sets of 3 random characters from a certain string (a password). What is the shortest string that contains each of the sets of 3 characters?"
It is my hope that the shortest possible code is one that includes only the numbers in the file. Because if there isn't, there are too many options for padded numbers. It is very easy to test a number for a match against the file, but it isn't so fast that you can test every number until you get it. This could easily turn into a nightmare, especially because we don't know how many digits the answer is.
CREATE TABLE #Temp (attempt char(3))
BULK INSERT #Temp FROM 'D:\keylog.txt' WITH (ROWTERMINATOR = '0x0a')
DECLARE @da int
SELECT DISTINCT attempt
INTO #Attempts
FROM #Temp
SET @da = @@ROWCOUNT
DROP TABLE #Temp
-- Collect all the possible specs for what number follows what other number.
-- In theory, we can build a string by grabbing number 1, joining on second table's a = first table's b, and concatenating the second table's b to the string.
-- Repeat forever until you get something that matches every value in the table
; WITH Combos (a, b) AS
(
SELECT LEFT(attempt,1), SUBSTRING(attempt,2,1)
FROM #Attempts
UNION
SELECT LEFT(attempt,1), RIGHT(attempt,1)
FROM #Attempts
UNION
SELECT SUBSTRING(attempt,2,1), RIGHT(attempt,1)
FROM #Attempts
)
SELECT *
INTO #Combos
FROM Combos
-- I hate dynamic SQL, but it's the only way I can write a generalized solution. Otherwise, I'd be hardcoding query after query. We don't know the length, which gives us the number of joins
-- So instead, we just make the query bigger and bigger until we get back a match.
DECLARE @result varchar(8000), @i int = 2, @SQL nvarchar(max), @SQL1 nvarchar(max), @SQL2 nvarchar(max), @SQL3 nvarchar(max), @SQL4 nvarchar(max)
-- Start for every query
SET @SQL1 = N'; WITH Passcodes (string) AS ( '
SET @SQL2 = N'SELECT DISTINCT c1.a '
SET @SQL3 = N'FROM #Combos c1 '
-- End for every query
SET @SQL4 = N') SELECT @result = string FROM Passcodes p ' +
N'INNER JOIN #Attempts a ON string LIKE ''%'' + LEFT(attempt,1) + ''%'' + SUBSTRING(attempt,2,1) + ''%'' + RIGHT(attempt,1) + ''%'' ' +
N'GROUP BY string HAVING COUNT(*) = @da '
WHILE 1 = 1
BEGIN
SET @SQL2 = CONCAT(@SQL2, N'+ c' , @i, N'.b ')
SET @SQL3 = CONCAT(@SQL3, N'INNER JOIN #Combos c', @i, N' ON c', @i, N'.a = c', @i - 1, N'.b OR c', @i, N'.a = c', @i - 1, N'.a ') -- Nice concat command, ugly lack of token replacement in T-SQL
SET @SQL = @SQL1 + @SQL2 + @SQL3 + @SQL4
EXEC sp_executesql @SQL, N'@da int, @result varchar(8000) OUTPUT', @da, @result OUTPUT
IF @result <> '' BREAK
SET @i = @i + 1
END
SELECT @result
DROP TABLE #Attempts