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
About these ads

1 Comment »


RSS feed for comments on this post. TrackBack URI

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

The WordPress Classic Theme. Create a free website or blog at WordPress.com.

Follow

Get every new post delivered to your Inbox.

Join 648 other followers

%d bloggers like this: