Post date: Jan 07, 2018 6:9:32 PM
"Find the set of four distinct positive single digit integers that can be used, along with plus, minus, multiply, divide (and parentheses), to produce every integer from 1 to n, without a gap, where n is the highest possible. Return those four numbers as a string."
Happy new year. This one is a bear. It would not be bad if not for random positioning of parentheses, but with them, it's a complete mess. Rather than building this as a table of elements, I'll just do each possible order of calcluations. There are only 3 operations with 4 digits. Faster than a doing lot of table operations. It has a lot of repetition but it didn't take a long time to code because I have copy and paste. It takes a bit over 2 minutes, which is faster than I prefer, to run, but it's not terrible.
There is probably a proper mathematical solution to this. I'm not a mathematician, so this is the naive solution plus some optimization.
CREATE PROCEDURE dbo.DoFormula
@a money, @b money, @oper char(1), @result money OUTPUT
AS
BEGIN
SET @result = NULL
-- Avoid divide by zero
IF @oper = '/' AND @b = 0
RETURN
IF @oper = '*'
SET @result = @a * @b
ELSE IF @oper = '/'
SET @result = @a / @b
ELSE IF @oper = '+'
SET @result = @a + @b
ELSE IF @oper = '-'
SET @result = @a - @b
END
GO
CREATE PROCEDURE dbo.DoFormulaXYZ
@a money, @b money, @c money, @d money, @x char(1), @y char(1), @z char(1), @result money OUTPUT
AS
BEGIN
SET @result = NULL
EXEC dbo.DoFormula @a, @b, @x, @result OUTPUT
EXEC dbo.DoFormula @result, @c, @y, @result OUTPUT
EXEC dbo.DoFormula @result, @d, @z, @result OUTPUT
-- We are only interested in integer results
IF CEILING(@result) <> FLOOR(@result)
SET @result = NULL
END
GO
-- We need all these different versions because when you have a mix of add and multiply, (a*b) + c is different from a*(b+c), etc. All options must be tested.
CREATE PROCEDURE dbo.DoFormulaXZY -- This also covers ZXY; it doesn't matter which end gets done first, just that they are done before they are combined
@a money, @b money, @c money, @d money, @x char(1), @y char(1), @z char(1), @result money OUTPUT
AS
BEGIN
SET @result = NULL
DECLARE @result2 money
EXEC dbo.DoFormula @a, @b, @x, @result OUTPUT
EXEC dbo.DoFormula @c, @d, @z, @result2 OUTPUT
EXEC dbo.DoFormula @result, @result2, @y, @result OUTPUT
-- We are only interested in integer results
IF CEILING(@result) <> FLOOR(@result)
SET @result = NULL
END
GO
CREATE PROCEDURE dbo.DoFormulaYXZ
@a money, @b money, @c money, @d money, @x char(1), @y char(1), @z char(1), @result money OUTPUT
AS
BEGIN
SET @result = NULL
EXEC dbo.DoFormula @b, @c, @y, @result OUTPUT
EXEC dbo.DoFormula @a, @result, @x, @result OUTPUT
EXEC dbo.DoFormula @result, @d, @z, @result OUTPUT
-- We are only interested in integer results
IF CEILING(@result) <> FLOOR(@result)
SET @result = NULL
END
GO
CREATE PROCEDURE dbo.DoFormulaYZX
@a money, @b money, @c money, @d money, @x char(1), @y char(1), @z char(1), @result money OUTPUT
AS
BEGIN
SET @result = NULL
EXEC dbo.DoFormula @b, @c, @y, @result OUTPUT
EXEC dbo.DoFormula @result, @d, @z, @result OUTPUT
EXEC dbo.DoFormula @a, @result, @x, @result OUTPUT
-- We are only interested in integer results
IF CEILING(@result) <> FLOOR(@result)
SET @result = NULL
END
GO
CREATE PROCEDURE dbo.DoFormulaZYX
@a money, @b money, @c money, @d money, @x char(1), @y char(1), @z char(1), @result money OUTPUT
AS
BEGIN
SET @result = NULL
EXEC dbo.DoFormula @c, @d, @z, @result OUTPUT
EXEC dbo.DoFormula @b, @result, @y, @result OUTPUT
EXEC dbo.DoFormula @a, @result, @x, @result OUTPUT
-- We are only interested in integer results
IF CEILING(@result) <> FLOOR(@result)
SET @result = NULL
END
GO
CREATE PROCEDURE dbo.WriteResult
@set char(4), @result int
AS
BEGIN
-- We don't write NULL (divide by zero or non-integer) or negative.
IF @result IS NULL OR @result <= 0
RETURN
INSERT INTO #Results ([set], result)
SELECT @set, @result
WHERE NOT EXISTS (SELECT 1 FROM #Results WHERE [set] = @set AND result = @result)
END
GO
CREATE PROCEDURE dbo.DoFormulaAndWriteResults
@set char(4), @a money, @b money, @c money, @d money, @x char(1), @y char(1), @z char(1)
AS
BEGIN
DECLARE @result money
-- Parentheses only matter if we have a mix of multiply/divide and add/subtract.
-- No mix, then no point in worrying about the order.
IF (@x IN ('*','/') AND @y IN ('*','/') AND @z IN ('*','/'))
OR (@x IN ('+','-') AND @y IN ('+','-') AND @z IN ('+','-'))
BEGIN
EXEC dbo.DoFormulaXYZ @a, @b, @c, @d, @x, @y, @z, @result OUTPUT
EXEC dbo.WriteResult @set, @result
RETURN
END -- No add/multiply mix
-- If we do have an add/multiply mix, we'll try all 5 cases of different orders. This will be very repetitive.
SET @result = NULL
EXEC dbo.DoFormulaXYZ @a, @b, @c, @d, @x, @y, @z, @result OUTPUT
EXEC dbo.WriteResult @set, @result
SET @result = NULL
EXEC dbo.DoFormulaXZY @a, @b, @c, @d, @x, @y, @z, @result OUTPUT
EXEC dbo.WriteResult @set, @result
SET @result = NULL
EXEC dbo.DoFormulaYXZ @a, @b, @c, @d, @x, @y, @z, @result OUTPUT
EXEC dbo.WriteResult @set, @result
SET @result = NULL
EXEC dbo.DoFormulaYZX @a, @b, @c, @d, @x, @y, @z, @result OUTPUT
EXEC dbo.WriteResult @set, @result
SET @result = NULL
EXEC dbo.DoFormulaZYX @a, @b, @c, @d, @x, @y, @z, @result OUTPUT
EXEC dbo.WriteResult @set, @result
END
GO
CREATE TABLE #Digits (i int PRIMARY KEY NOT NULL)
INSERT INTO #Digits VALUES (0), (1), (2), (3), (4), (5), (6), (7), (8), (9)
CREATE TABLE #Operators (o char(1) PRIMARY KEY NOT NULL)
INSERT INTO #Operators VALUES ('*'), ('/'), ('+'), ('-')
CREATE TABLE #Results ([set] char(4) NOT NULL, result int NOT NULL, PRIMARY KEY ([set], result))
DECLARE @set char(4), @a money, @b money, @c money, @d money, @x char(1), @y char(1), @z char(1)
DECLARE EulerCursor CURSOR LOCAL FOR
WITH Numbers (a, b, c, d) AS
(
SELECT a.i, b.i, c.i, d.i
FROM #Digits a
INNER JOIN #Digits b
ON b.i <> a.i
INNER JOIN #Digits c
ON c.i NOT IN (b.i, a.i)
INNER JOIN #Digits d
ON d.i NOT IN (c.i, b.i, a.i)
),
Operators (x, y, z) AS
(
SELECT o1.o, o2.o, o3.o
FROM #Operators o1
CROSS JOIN #Operators o2
CROSS JOIN #Operators o3
)
SELECT a, b, c, d, x, y, z
, (SELECT N'' + i FROM #Digits d WHERE d.i IN (n.a, n.b, n.c, n.d) ORDER BY d.i FOR XML PATH(''), TYPE).value('text()[1]','nvarchar(max)') AS [set]
FROM Numbers n
CROSS JOIN Operators o
ORDER BY 8
OPEN EulerCursor
WHILE 1 = 1
BEGIN
FETCH NEXT FROM EulerCursor INTO @a, @b, @c, @d, @x, @y, @z, @set
IF @@FETCH_STATUS <> 0 BREAK
EXEC dbo.DoFormulaAndWriteResults @set, @a, @b, @c, @d, @x, @y, @z
END -- Cursor
CLOSE EulerCursor
DEALLOCATE EulerCursor
; WITH Consecutive ([set], result, c) AS
(
SELECT [set], result, ROW_NUMBER() OVER (PARTITION BY [set] ORDER BY result)
FROM #Results
)
SELECT TOP 1 [set]
FROM Consecutive
WHERE result = c
GROUP BY [set]
ORDER BY MAX(result) DESC
DROP TABLE #Digits
DROP TABLE #Operators
DROP TABLE #Results
GO
DROP PROCEDURE dbo.DoFormula
GO
DROP PROCEDURE dbo.DoFormulaXYZ
GO
DROP PROCEDURE dbo.DoFormulaXZY
GO
DROP PROCEDURE dbo.DoFormulaYXZ
GO
DROP PROCEDURE dbo.DoFormulaYZX
GO
DROP PROCEDURE dbo.DoFormulaZYX
GO
DROP PROCEDURE dbo.WriteResult
GO
DROP PROCEDURE dbo.DoFormulaAndWriteResults
GO