# Developer42

## 2013-07-28

### Countdown Numbers Round Solver in T-SQL

Filed under: Microsoft, SQL Server, Technology — Tags: , , , , , , , — Developer42 @ 14:00

Every now and then I try to create programs to solve puzzles as a way to introduce myself to new ideas & test my coding skills. My latest self-challenge was to write SQL code to solve the Countdown Numbers Round. The idea is; given 6 random numbers (each of which may be used at most once) and using only basic arithmetic (i.e. addition, subtraction, multiplication and division) to get to a randomly generated target number. e.g. Given the numbers 3, 7, 9, 10, 50 & 75, and the target 396 one solution would be: 3 * (75 + 50 + 7).

Here’s how I approached it in T-SQL:
Run this solution at SQL Fiddle

```create procedure dbo.CountdownNumberSolver
(
@target int output --output used to allow these to be referenced outside of the proc if rnd numbers are generated
, @number1 int output
, @number2 int output
, @number3 int output
, @number4 int output
, @number5 int output
, @number6 int output
) as
begin

--if the user didn't specify values randomly pick some.
--   Small Number (1-10):			1 + 10 * rand()
--   Large Number (25,50,75,100):	floor(1 + 4 * rand()) * 25
--   Target (1-999):				1 + (999 * rand())
select @target = ISNULL(@target, 1 + (999 * rand())) --I assume 0 isn't a valid solution in countdown?
, @number1 = ISNULL(@number1,1 + 10 * rand())
, @number2 = ISNULL(@number2,1 + 10 * rand())
, @number3 = ISNULL(@number3,1 + 10 * rand())
, @number4 = ISNULL(@number4,1 + 10 * rand())
, @number5 = ISNULL(@number5,floor(1 + 4 * rand()) * 25)
, @number6 = ISNULL(@number6,floor(1 + 4 * rand()) * 25)

--output question
/* commented out as sql fiddle only returns first result set
select @target [target]
, @number1 [#1]
, @number2 [#2]
, @number3 [#3]
, @number4 [#4]
, @number5 [#5]
, @number6 [#6]
*/
--records combinations tried so far / partial equations
create table #solutions
(
id bigint not null identity(1,1) primary key clustered
, binaryFlags tinyint not null
, number float not null
, equation nvarchar(256) not null
)
create index ix_solutions_number on #solutions(number)

--start with the given values - the id stuff is just to make it easy to reuse this procedure should we want a different # of source numbers
insert #solutions
select power(2,id)
, number
, CAST(number as nvarchar(3))
from
(values
(0,@number1)
,(1,@number2)
,(2,@number3)
,(3,@number4)
,(4,@number5)
,(5,@number6)
)x(id, number)

declare @previousCount bigint = 0
, @newCount bigint = (select COUNT(1) from #solutions)
, @tempCount bigint

while @previousCount < @newCount --repeat whilst there are still untried combos
and not exists (select top 1 1 from #solutions where number=@target) --and we're still looking for a solution
begin

set @tempCount = @newCount

insert #solutions
select a.binaryFlags | b.binaryFlags
, case x.o
when '+' then a.number + b.number
when '-' then a.number - b.number
when '*' then a.number * b.number
when '/' then a.number / b.number
end
, '(' + a.equation + ' ' + x.o + ' ' + b.equation + ')'
from #solutions a
inner join #solutions b
on a.binaryFlags & b.binaryFlags = 0 --ensure we're not reusing source numbers
and a.id != b.id --minor (potential) optimisation
and --no point comparing things we've already checked (this may allow for some performance improvement- it doesn't affect the logic)
(
a.id > @previousCount
or b.id > @previousCount
)
inner join --doing things this way means we only need to find the new combinations from a&b once, not 4 times
(
values ('+'), ('-'), ('*'), ('/')
) x(o)
on  not(x.o = '/' and b.number = 0) --avoid div 0 errors
and not(x.o = '-' and a.number - b.number = 0) --don't create 0 value entries (if 0's not an allowed solution this result just adds overhead without value)
and not(x.o = '+' and a.number + b.number = 0) --don't create 0 value entries (if 0's not an allowed solution this result just adds overhead without value)
and not(x.o = '+' and a.id > b.id) --commutative function optimisation
and not(x.o = '*' and a.id > b.id) --commutative function optimisation

set @previousCount = @tempCount
select @newCount = COUNT(1) from #solutions

end

--limited to one answer to fit with the game / avoid the assumption that all possible solutions would be listed
--(since we exit the above loop the moment we have an answer rather than continuing to check all combos)
select top 1
@number1 [#1]
, @number2 [#2]
, @number3 [#3]
, @number4 [#4]
, @number5 [#5]
, @number6 [#6]
, @target  [target]
, equation [solution]
from #solutions
where number = @target
order by len(equation) --show the shortest equation as that's probably simplest
option (fast 1)

if object_id('tempdb..#solutions','U') is not null drop table #solutions

return 0
end
```

Here’s an example of how to run it:

```--run the proc using random numbers (the proc replaces nulls with random #s)
exec dbo.CountdownNumberSolver null, null, null, null, null, null, null

--run the proc on user defined values
exec dbo.CountdownNumberSolver 396, 7, 3, 10, 9, 50, 75
```