Please start any new threads on our new site at https://forums.sqlteam.com. We've got lots of great SQL Server experts to answer whatever question you can come up with.

 All Forums
 Site Related Forums
 The Yak Corral
 Pancake Challenge

Author  Topic 

rockmoose
SQL Natt Alfen

3279 Posts
Posted - 2005-02-27 : 15:31:36
This could be a problem to sink one's teeth into ;)

You have to order a pile of different sized pancakes, with one spatula.
so that no pancake has a bigger one above it.

set nocount on
-- create table with a pile of 25 different sized pancakes
create table #pancakes(place tinyint identity(1,1) unique, cakesize smallint not null unique)
insert #pancakes(cakesize)
select number*2+1 from master.dbo.spt_values where type = 'P' and number/25 = 0
order by newid()

print 'You have a pile with 25 different sized pancakes, and 1 spatula
You may insert the spatula into the pile and flip the lifted pancakes.
Your job is to order the pancakes so that the biggest one is at the bottom and the smallest at the top of the pile.
(Calculate the flipping sequence, How many flips will You need ?)
This is how the pile looks like when You start:' + char(10)
select place,replicate(' ',(49-cakesize)/2)+replicate('*',cakesize) as pancakes
from #pancakes order by place

/* Calculate the flipping sequence, How many flips will You need ?*/

drop table #pancakes

rockmoose

TG
Master Smack Fu Yak Hacker

6065 Posts
Posted - 2005-02-27 : 20:12:54
Ok Ok, I'll be the first to throw something out here to get showed up everyone else. The maximum total flips this sequece needs given worst possible ordering is at the end of this post. I'll try to think of a way to reduce the total flips needed.

If Object_id('tempdb.dbo.#pancakes') > 0
	drop table #pancakes
GO
If Object_ID('tempdb.dbo.#temp') is NULL
	Create Table #temp (place int, newPlace int identity)
GO

set nocount on
-- create table with a pile of 25 different sized pancakes
create table #pancakes(place tinyint identity(1,1) unique, cakesize smallint not null unique)
insert #pancakes(cakesize)
select number*2+1 from master.dbo.spt_values where type = 'P' and number/25 = 0
order by newid()

print 'You have a pile with 25 different sized pancakes, and 1 spatula
You may insert the spatula into the pile and flip the lifted pancakes.
Your job is to order the pancakes so that the biggest one is at the bottom and the smallest at the top of the pile.
(Calculate the flipping sequence, How many flips will You need ?)
This is how the pile looks like when You start:' + char(10)

PRINT 'Calculate the flipping sequence, How many flips will You need'

select place,replicate(' ',(49-cakesize)/2)+replicate('*',cakesize) as pancakes, cakesize
from #pancakes order by place


GO
alter table #pancakes Add newPlace int null
GO
Update #pancakes set newPlace = place

declare @lastmax int
	,@flips int

select	@lastmax = max(cakesize)
	,@flips = 0
from #pancakes

--Flips are in a series of 2.
	--First flip starts just below the largest pancake that hasn't been flipped yet, and flips the stack (putting largest on top)
	--Second flip flips the entire stack (excluding results of all previous flip series)
While @lastmax is NOT NULL
Begin
	--quit if the order is correct
	if NOT Exists
		(Select	*
		From	#pancakes a 
		Where	(Select count(*) from #pancakes where cakesize <= a.cakesize) < newPlace)
	Begin
		break
	End

	--First flip of series
	insert #temp (place)
	Select	place 
	from	#pancakes 
	where	newPlace <= (Select newPlace from #pancakes where cakesize = @lastMax)
	Order by newPlace desc
	Update p Set 
		p.newPlace = v.newPlace
	From	#pancakes p
	JOIN	#temp v ON p.place = v.place
	truncate table #temp

	--second flip of series
	insert #temp (place)
	Select	place
	from	#pancakes 
	where	newPlace <= (Select max(newPlace) from #pancakes where cakesize < @lastmax)
	Order by NewPlace desc
	Update p Set 
		p.newPlace = v.newPlace
	From	#pancakes p
	JOIN	#temp v ON p.place = v.place
	truncate table #temp

	--get the next flip place and increment flip count	
	Select	@lastmax = max(a.cakesize) 
		,@flips = @flips + 2
	From	#pancakes a
	JOIN	(
		Select	a.cakesize
			,a.newPlace
			,seq = (select count(*) from #pancakes where cakesize <= a.cakesize)
		From	#pancakes a
		) as seq
			ON a.cakesize = seq.cakesize
	where	a.cakesize < @lastMax
	And	a.newPlace <> seq.seq
End

select place,replicate(' ',(49-cakesize)/2)+replicate('*',cakesize) as pancakes, cakesize
from #pancakes order by newPlace

Select @flips TotalFlips


If Object_id('tempdb.dbo.#pancakes') > 0
	drop table #pancakes
If Object_ID('tempdb.dbo.#temp') > 0
	drop Table #temp


max flips are 50
average seems to be around 44


Be One with the Optimizer
TG
Go to Top of Page

rockmoose
SQL Natt Alfen

3279 Posts
Posted - 2005-02-28 : 04:18:13
Well done TG, implementation of pancakeflip algorithm works !
The flipcount does not seem to work for odd # of flips, and will add additional 2 flips at the end.
(I have not dissected the code further...)

>> I'll try to think of a way to reduce the total flips needed
Don't know if it can be optimized actually...


Here is fix data to test on:
truncate table #pancakes
insert #pancakes(cakesize) values(27)
insert #pancakes(cakesize) values(33)
insert #pancakes(cakesize) values(45)
insert #pancakes(cakesize) values(15)
insert #pancakes(cakesize) values(13)
insert #pancakes(cakesize) values(35)
insert #pancakes(cakesize) values(21)
insert #pancakes(cakesize) values(49)
insert #pancakes(cakesize) values(11)
insert #pancakes(cakesize) values(41)
insert #pancakes(cakesize) values(17)
insert #pancakes(cakesize) values(9)
insert #pancakes(cakesize) values(1)
insert #pancakes(cakesize) values(7)
insert #pancakes(cakesize) values(19)
insert #pancakes(cakesize) values(29)
insert #pancakes(cakesize) values(25)
insert #pancakes(cakesize) values(5)
insert #pancakes(cakesize) values(39)
insert #pancakes(cakesize) values(47)
insert #pancakes(cakesize) values(43)
insert #pancakes(cakesize) values(31)
insert #pancakes(cakesize) values(3)
insert #pancakes(cakesize) values(37)
insert #pancakes(cakesize) values(23)

flips       flipsequence
----------- ---------------------------------------------------------------------------------------
35          8,25,6,24,5,23,22,8,21,5,20,18,19,6,18,16,17,3,16,11,15,5,14,8,12,2,11,7,10,6,9,3,5,3,4



rockmoose
Go to Top of Page

Seventhnight
Master Smack Fu Yak Hacker

2878 Posts
Posted - 2005-02-28 : 14:51:18
i tried a different approach, but it isn't quite as efficient apparently... will have to think about it a little more later. Here it is though:


Set NoCount On

create table #pancakes(place tinyint, cakesize smallint not null unique)
insert #pancakes(place,cakesize) values(1,27)
insert #pancakes(place,cakesize) values(2,33)
insert #pancakes(place,cakesize) values(3,45)
insert #pancakes(place,cakesize) values(4,15)
insert #pancakes(place,cakesize) values(5,13)
insert #pancakes(place,cakesize) values(6,35)
insert #pancakes(place,cakesize) values(7,21)
insert #pancakes(place,cakesize) values(8,49)
insert #pancakes(place,cakesize) values(9,11)
insert #pancakes(place,cakesize) values(10,41)
insert #pancakes(place,cakesize) values(11,17)
insert #pancakes(place,cakesize) values(12,9)
insert #pancakes(place,cakesize) values(13,1)
insert #pancakes(place,cakesize) values(14,7)
insert #pancakes(place,cakesize) values(15,19)
insert #pancakes(place,cakesize) values(16,29)
insert #pancakes(place,cakesize) values(17,25)
insert #pancakes(place,cakesize) values(18,5)
insert #pancakes(place,cakesize) values(19,39)
insert #pancakes(place,cakesize) values(20,47)
insert #pancakes(place,cakesize) values(21,43)
insert #pancakes(place,cakesize) values(22,31)
insert #pancakes(place,cakesize) values(23,3)
insert #pancakes(place,cakesize) values(24,37)
insert #pancakes(place,cakesize) values(25,23)

print 'You have a pile with 25 different sized pancakes, and 1 spatula
You may insert the spatula into the pile and flip the lifted pancakes.
Your job is to order the pancakes so that the biggest one is at the bottom and the smallest at the top of the pile.
(Calculate the flipping sequence, How many flips will You need ?)
This is how the pile looks like when You start:' + char(10)
select place,replicate(' ',(49-cakesize)/2)+replicate('*',cakesize) as pancakes
from #pancakes order by place

/* Calculate the flipping sequence, How many flips will You need ?*/

--Select * From #pancakes

Declare @flips int,
	@goodTo int,
	@msg nvarchar(1000)

Set @flips=0

While @flips < 100 and 24 > isnull((Select count(*) From (Select A.place From #pancakes A Inner Join #pancakes B On A.place > B.place Group By A.place Having (A.place-1)*(A.place) = sum(abs(A.cakesize-B.cakesize)) and (A.place-1)*(A.place) = sum(A.cakesize)-sum(B.cakesize)) Z),1)
Begin
	--determins if any of the top cakes are in the correct order
	if exists(Select A.place From #pancakes A Inner Join #pancakes B On A.place > B.place Group By A.place Having A.place=2 and (A.place-1)*(A.place) = sum(abs(A.cakesize-B.cakesize)) and (A.place-1)*(A.place) = sum(A.cakesize)-sum(B.cakesize))
	Begin
		--Identifies the point to which the stack is in the correct order (from the top)
		Select @goodTo = min(Z.place)-1
		From #pancakes Z
		Left Join
			(
			Select A.place--, sum(A.cakesize)-sum(B.cakesize), sum(abs(A.cakesize-B.cakesize)), (A.place-1)*(A.place)
			From #pancakes A
			Inner Join #pancakes B
			On A.place > B.place
			Group By A.place
			Having (A.place-1)*(A.place) = sum(abs(A.cakesize-B.cakesize)) and (A.place-1)*(A.place) = sum(A.cakesize)-sum(B.cakesize)
			) Y
		On Z.place = Y.place
		Where Y.place is null
		and Z.place>1
	End

	--if none are in the correct order, default to 1 cake
	Select @goodTo = isnull(@goodTo,1)

	if (@goodTo>1)
	Begin
		--if more than once cake is correct, flip these to reverse order
		Update #pancakes
		Set place = @goodTo - place + 1
		From #pancakes 
		Where place between 1 and @goodTo

		--increment
		Set @flips = @flips + 1
	End

	--flip to correctly order top cake
	Update #pancakes
	Set place = isnull((Select place-1 From #pancakes A Where cakesize = (Select cakesize+2 From #pancakes B Where place=1)),25) - place + 1
	From #pancakes 
	Where place between 1 and isnull((Select place-1 From #pancakes A Where cakesize = (Select cakesize+2 From #pancakes B Where place=1)),25)

	--increment
	Set @flips = @flips + 1

	Set @goodTo = null
End

Set @Msg = 'flips: ' + convert(varchar,@flips)
RaisError(@Msg,0,1) With NOWAIT
Set @Msg = ''
RaisError(@Msg,0,1) With NOWAIT


select place,replicate(' ',(49-cakesize)/2)+replicate('*',cakesize) as pancakes
from #pancakes order by place

drop table #pancakes

Set NoCount Off


Corey

"If the only tool you have is a hammer, the whole world looks like a nail." - Mark Twain
Go to Top of Page

rockmoose
SQL Natt Alfen

3279 Posts
Posted - 2005-02-28 : 15:19:56
If ever there was a challenge with completely UNREADABLE code this is it...

This is the same algorithm as TG's,
Corey, I have absolutely no idea how your's work, pretty impressive!

Enjoy: 1 update clause...
----------------------------------------------------------------------
set nocount on
-- create table with a pile of 25 different sized pancakes
create table #pancakes(place tinyint identity(1,1) unique, cakesize smallint not null unique)
insert #pancakes(cakesize)
select number*2+1 from master.dbo.spt_values where type = 'P' and number/25 = 0
order by newid()

select cakesize,place,replicate(' ',(49-cakesize)/2)+replicate('*',cakesize) as pancakes
from #pancakes order by place

/* Calculate the flipping sequence, How many flips will You need ?*/
alter table #pancakes add flipsequence varchar(8000) not null default('')
GO

-- start flipping the pile of pancakes....
while @@rowcount > 0
	update #pancakes set
		cakesize = flippedcakes.cakesize
		,flipsequence = #pancakes.flipsequence + ltrim(flipplace.place) + ','
	from
		#pancakes
		join #pancakes flippedcakes
		join	(
				select case when biggestcake.place = 1 then biggestunorderedplace.place else biggestcake.place end as place
				from
					(
						select max(place) as place from #pancakes p1
						where exists(	select * from #pancakes p2
								where p1.place > p2.place
								and p1.cakesize < p2.cakesize )
					) as biggestunorderedplace
					cross join
					(
						select place, cakesize from #pancakes
					) as biggestcake
					join
					(
						select max(cakesize) as cakesize from #pancakes p1
						where exists( 	select * from #pancakes p2
								where p1.place < p2.place
								and p1.cakesize > p2.cakesize )
					) as biggestunorderedcake
						on biggestcake.cakesize = biggestunorderedcake.cakesize
			) as flipplace
		on flippedcakes.place <= flipplace.place
		on #pancakes.place = 1+flipplace.place-flippedcakes.place


select len(flipsequence)-len(replace(flipsequence,',','')) as flips, flipsequence as flipsequence
from #pancakes where place = 1

select cakesize,place,replicate(' ',(49-cakesize)/2)+replicate('*',cakesize) as pancakes
from #pancakes order by place

drop table #pancakes



rockmoose
Go to Top of Page

Seventhnight
Master Smack Fu Yak Hacker

2878 Posts
Posted - 2005-02-28 : 17:30:32
For the static stack, this does it in 34 flips:


Set NoCount On

create table #pancakes(place tinyint, cakesize smallint not null unique)
insert #pancakes(place,cakesize) values(1,27)
insert #pancakes(place,cakesize) values(2,33)
insert #pancakes(place,cakesize) values(3,45)
insert #pancakes(place,cakesize) values(4,15)
insert #pancakes(place,cakesize) values(5,13)
insert #pancakes(place,cakesize) values(6,35)
insert #pancakes(place,cakesize) values(7,21)
insert #pancakes(place,cakesize) values(8,49)
insert #pancakes(place,cakesize) values(9,11)
insert #pancakes(place,cakesize) values(10,41)
insert #pancakes(place,cakesize) values(11,17)
insert #pancakes(place,cakesize) values(12,9)
insert #pancakes(place,cakesize) values(13,1)
insert #pancakes(place,cakesize) values(14,7)
insert #pancakes(place,cakesize) values(15,19)
insert #pancakes(place,cakesize) values(16,29)
insert #pancakes(place,cakesize) values(17,25)
insert #pancakes(place,cakesize) values(18,5)
insert #pancakes(place,cakesize) values(19,39)
insert #pancakes(place,cakesize) values(20,47)
insert #pancakes(place,cakesize) values(21,43)
insert #pancakes(place,cakesize) values(22,31)
insert #pancakes(place,cakesize) values(23,3)
insert #pancakes(place,cakesize) values(24,37)
insert #pancakes(place,cakesize) values(25,23)


print 'You have a pile with 25 different sized pancakes, and 1 spatula
You may insert the spatula into the pile and flip the lifted pancakes.
Your job is to order the pancakes so that the biggest one is at the bottom and the smallest at the top of the pile.
(Calculate the flipping sequence, How many flips will You need ?)
This is how the pile looks like when You start:' + char(10)
select place,replicate(' ',(49-cakesize)/2)+replicate('*',cakesize) as pancakes
from #pancakes order by place


/* Calculate the flipping sequence, How many flips will You need ?*/

--Select * From #pancakes Order By place

Declare @flips int,
	@goodTo int,
	@swapNum int,
	@maxCake int,
	@pass int,
	@msg nvarchar(1000),
	@history varchar(1000)

Set @flips=0
Set @pass = 0

While (Select max(Z.place) From #pancakes Z Left Join (Select A.place From #pancakes A Left Join #pancakes B On A.cakesize = B.place*2-1 Where A.place = B.place) Y On Z.place = Y.place Where Y.place is null) is not null
Begin
	Select @maxCake = isnull(
				(Select max(Z.place) 
				From #pancakes Z 
				Left Join 
					(
					Select A.place 
					From #pancakes A 
					Left Join #pancakes B 
					On A.cakesize = B.place*2-1 
					Where A.place = B.place
					) Y 
				On Z.place = Y.place 
				Where Y.place is null)
			,25)

	if (@pass%5<>0)
	Begin
		Set @swapNum = (Select place From #pancakes Where cakesize = (@maxCake*2)-1)
		if (@swapNum>1)
		Begin 
			Update #pancakes Set place = @swapNum-place + 1 From #pancakes Where place between 1 and @swapNum
			Set @flips = @flips + 1
			Set @history = isnull(@history+',','')+convert(varchar,@swapNum)
		End
	
	
		Set @swapNum = ((Select cakesize From #pancakes where place=1)+1)/2
		Update #pancakes Set place = @swapNum-place + 1 From #pancakes Where place between 1 and @swapNum
		Set @flips = @flips + 1
		Set @history = isnull(@history+',','')+convert(varchar,@swapNum)
	End
	Else
	Begin
		Set @swapNum = (Select place-1 From #pancakes Where cakesize=(Select cakesize+2 From #pancakes where place=1))
		Update #pancakes Set place = @swapNum-place + 1 From #pancakes Where place between 1 and @swapNum
		Set @flips = @flips + 1
		Set @history = isnull(@history+',','')+convert(varchar,@swapNum)
	End
	
	Set @pass = @pass + 1
End


Set @Msg = 'flip Cnt: ' + convert(varchar,@flips)
RaisError(@Msg,0,1) With NOWAIT
Set @Msg = 'flips: ' + @history
RaisError(@Msg,0,1) With NOWAIT
Set @Msg = ''
RaisError(@Msg,0,1) With NOWAIT


select place,replicate(' ',(49-cakesize)/2)+replicate('*',cakesize) as pancakes
from #pancakes order by place

drop table #pancakes

Set NoCount Off

Results:

flip Cnt: 34
flips: 15,8,25,6,24,12,23,22,8,10,21,5,20,18,19,5,18,2,7,17,11,16,2,15,7,12,8,4,9,5,8,6,3,4


Corey

"If the only tool you have is a hammer, the whole world looks like a nail." - Mark Twain
Go to Top of Page

Seventhnight
Master Smack Fu Yak Hacker

2878 Posts
Posted - 2005-02-28 : 22:57:19
As a point of interest, here are 20 different solutions that solve it in 28 flips. Thats the best I've found so far 


flipCnt     flips                                                                   
----------- --------------------------------------------------------------------------
28          15,8,25,6,24,9,12,23,22,4,21,5,20,18,19,14,16,9,17,3,5,18,9,13,11,4,9,4
28          15,8,25,6,24,9,12,23,22,4,21,5,20,18,19,14,16,9,17,3,5,18,9,13,11,4,9,4
28          15,8,25,6,24,9,12,23,22,4,21,5,20,18,19,14,16,9,17,3,5,18,9,13,11,4,9,4
28          15,8,25,6,24,9,12,23,22,4,21,5,20,18,19,14,16,9,17,3,5,18,9,13,11,4,9,4
28          15,8,25,6,24,9,12,23,22,4,21,5,20,18,19,14,16,9,17,3,5,18,9,13,11,4,9,4
28          15,8,25,6,24,9,12,23,22,4,21,5,20,18,19,14,16,9,17,3,5,18,9,13,11,4,9,4
28          15,8,25,8,3,24,9,12,23,18,4,16,22,9,6,21,3,19,11,18,7,17,12,16,2,15,3,4
28          15,8,25,8,3,24,9,12,23,18,4,16,22,9,6,21,3,19,11,18,7,17,12,16,2,15,3,4
28          15,8,25,8,3,24,9,12,23,18,4,16,22,9,6,21,3,19,11,18,7,17,12,16,2,15,3,4
28          15,8,25,8,3,24,9,12,23,18,4,16,22,9,6,21,3,19,11,18,7,17,12,16,2,15,3,4
28          15,8,25,8,3,24,9,12,23,18,4,16,22,9,6,21,3,19,11,18,7,17,12,16,2,15,3,4
28          15,8,25,8,3,24,9,12,23,18,4,16,22,9,6,21,3,19,11,18,7,17,12,16,2,15,3,4
28          15,8,25,8,3,24,9,12,23,18,4,16,22,9,6,21,3,19,11,18,7,17,12,16,2,15,3,4
28          15,8,25,8,3,24,9,12,23,18,4,16,22,9,6,21,3,19,11,18,7,17,12,16,2,15,3,4
28          15,8,25,6,24,9,12,23,22,4,21,5,20,18,19,14,16,9,17,3,5,18,9,13,11,4,9,4
28          15,8,25,6,24,9,12,23,22,4,21,5,20,18,19,14,16,9,17,3,5,18,9,13,11,4,9,4
28          15,8,25,8,3,24,9,12,23,18,4,16,22,9,6,21,3,19,11,18,7,17,12,16,2,15,3,4
28          15,8,25,8,3,24,9,12,23,18,4,16,22,9,6,21,3,19,11,18,7,17,12,16,2,15,3,4
28          15,8,25,8,3,24,9,12,23,18,4,16,22,9,6,21,3,19,11,18,7,17,12,16,2,15,3,4
28          15,8,25,8,3,24,9,12,23,18,4,16,22,9,6,21,3,19,11,18,7,17,12,16,2,15,3,4


Corey

"If the only tool you have is a hammer, the whole world looks like a nail." - Mark Twain
Go to Top of Page

AndrewMurphy
Master Smack Fu Yak Hacker

2916 Posts
Posted - 2005-03-01 : 09:07:40
very interesting.......
but the results of this look like it's the same strategy repeated 6 times!!!!

28 15,8,25,6,24,9,12,23,22,4,21,5,20,18,19,14,16,9,17,3,5,18,9,13,11,4,9,4
28 15,8,25,6,24,9,12,23,22,4,21,5,20,18,19,14,16,9,17,3,5,18,9,13,11,4,9,4
28 15,8,25,6,24,9,12,23,22,4,21,5,20,18,19,14,16,9,17,3,5,18,9,13,11,4,9,4
28 15,8,25,6,24,9,12,23,22,4,21,5,20,18,19,14,16,9,17,3,5,18,9,13,11,4,9,4
28 15,8,25,6,24,9,12,23,22,4,21,5,20,18,19,14,16,9,17,3,5,18,9,13,11,4,9,4
28 15,8,25,6,24,9,12,23,22,4,21,5,20,18,19,14,16,9,17,3,5,18,9,13,11,4,9,4
Go to Top of Page

Seventhnight
Master Smack Fu Yak Hacker

2878 Posts
Posted - 2005-03-01 : 09:14:47
oops... didn't really check it very hard

so condensed its only two solutions :

flipCnt     flips                                                                   
----------- --------------------------------------------------------------------------
28          15,8,25,6,24,9,12,23,22,4,21,5,20,18,19,14,16,9,17,3,5,18,9,13,11,4,9,4
28          15,8,25,8,3,24,9,12,23,18,4,16,22,9,6,21,3,19,11,18,7,17,12,16,2,15,3,4


Corey

"If the only tool you have is a hammer, the whole world looks like a nail." - Mark Twain
Go to Top of Page

rockmoose
SQL Natt Alfen

3279 Posts
Posted - 2005-03-01 : 16:12:23
Ok, I can get it down to 29...
Interestingly the algorithm's are probably not the same, as hinted by the sequence.
Anyway I am not 100% sure mine will terminate. (although it has always so far)

flips       flipsequence
----------- ---------------------------------------------------------------------------------
29          16,21,14,16,19,13,24,17,2,25,23,16,19,10,24,10,6,4,19,20,16,23,20,13,3,19,16,18,2


Coming up with a bigger stack....


rockmoose
Go to Top of Page

rockmoose
SQL Natt Alfen

3279 Posts
Posted - 2005-03-01 : 16:22:35
This proved harder than I thought, when I first posted the challenge.
Anyway WELL DONE! TG and Corey !

I will post my algorithm after proper formatting for readability.
, I need it!

flips       flipsequence
----------- ---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
128         43,100,93,83,94,10,72,82,96,58,51,69,80,22,44,61,29,44,52,83,84,35,94,78,99,59,49,94,80,49,95,21,5,101,42,100,98,17,16,83,72,30,54,58,70,25,49,46,56,85,45,50,35,52,86,90,99,67,59,98,44,97,70,18,42,39,10,34,91,8,64,96,47,93,78,95,43,67,83,85,67,91,82,34,90,66,12,18,19,11,89,44,85,53,82,31,16,55,66,79,39,32,6,78,72,76,22,20,63,35,61,36,43,7,42,17,37,23,32,18,29,22,2,12,28,16,27,11


101 stack:
create table #pancakes(place tinyint, cakesize smallint not null unique)
insert #pancakes(place,cakesize) values(1,115)
insert #pancakes(place,cakesize) values(2,173)
insert #pancakes(place,cakesize) values(3,185)
insert #pancakes(place,cakesize) values(4,135)
insert #pancakes(place,cakesize) values(5,3)
insert #pancakes(place,cakesize) values(6,87)
insert #pancakes(place,cakesize) values(7,97)
insert #pancakes(place,cakesize) values(8,57)
insert #pancakes(place,cakesize) values(9,189)
insert #pancakes(place,cakesize) values(10,143)
insert #pancakes(place,cakesize) values(11,25)
insert #pancakes(place,cakesize) values(12,125)
insert #pancakes(place,cakesize) values(13,179)
insert #pancakes(place,cakesize) values(14,59)
insert #pancakes(place,cakesize) values(15,13)
insert #pancakes(place,cakesize) values(16,39)
insert #pancakes(place,cakesize) values(17,55)
insert #pancakes(place,cakesize) values(18,95)
insert #pancakes(place,cakesize) values(19,113)
insert #pancakes(place,cakesize) values(20,53)
insert #pancakes(place,cakesize) values(21,69)
insert #pancakes(place,cakesize) values(22,159)
insert #pancakes(place,cakesize) values(23,91)
insert #pancakes(place,cakesize) values(24,89)
insert #pancakes(place,cakesize) values(25,47)
insert #pancakes(place,cakesize) values(26,67)
insert #pancakes(place,cakesize) values(27,199)
insert #pancakes(place,cakesize) values(28,81)
insert #pancakes(place,cakesize) values(29,109)
insert #pancakes(place,cakesize) values(30,85)
insert #pancakes(place,cakesize) values(31,19)
insert #pancakes(place,cakesize) values(32,93)
insert #pancakes(place,cakesize) values(33,79)
insert #pancakes(place,cakesize) values(34,41)
insert #pancakes(place,cakesize) values(35,183)
insert #pancakes(place,cakesize) values(36,107)
insert #pancakes(place,cakesize) values(37,103)
insert #pancakes(place,cakesize) values(38,151)
insert #pancakes(place,cakesize) values(39,51)
insert #pancakes(place,cakesize) values(40,129)
insert #pancakes(place,cakesize) values(41,63)
insert #pancakes(place,cakesize) values(42,131)
insert #pancakes(place,cakesize) values(43,167)
insert #pancakes(place,cakesize) values(44,117)
insert #pancakes(place,cakesize) values(45,49)
insert #pancakes(place,cakesize) values(46,45)
insert #pancakes(place,cakesize) values(47,181)
insert #pancakes(place,cakesize) values(48,23)
insert #pancakes(place,cakesize) values(49,133)
insert #pancakes(place,cakesize) values(50,33)
insert #pancakes(place,cakesize) values(51,157)
insert #pancakes(place,cakesize) values(52,35)
insert #pancakes(place,cakesize) values(53,77)
insert #pancakes(place,cakesize) values(54,123)
insert #pancakes(place,cakesize) values(55,191)
insert #pancakes(place,cakesize) values(56,1)
insert #pancakes(place,cakesize) values(57,75)
insert #pancakes(place,cakesize) values(58,147)
insert #pancakes(place,cakesize) values(59,17)
insert #pancakes(place,cakesize) values(60,155)
insert #pancakes(place,cakesize) values(61,9)
insert #pancakes(place,cakesize) values(62,61)
insert #pancakes(place,cakesize) values(63,31)
insert #pancakes(place,cakesize) values(64,141)
insert #pancakes(place,cakesize) values(65,171)
insert #pancakes(place,cakesize) values(66,197)
insert #pancakes(place,cakesize) values(67,169)
insert #pancakes(place,cakesize) values(68,73)
insert #pancakes(place,cakesize) values(69,7)
insert #pancakes(place,cakesize) values(70,43)
insert #pancakes(place,cakesize) values(71,29)
insert #pancakes(place,cakesize) values(72,187)
insert #pancakes(place,cakesize) values(73,11)
insert #pancakes(place,cakesize) values(74,161)
insert #pancakes(place,cakesize) values(75,27)
insert #pancakes(place,cakesize) values(76,195)
insert #pancakes(place,cakesize) values(77,15)
insert #pancakes(place,cakesize) values(78,127)
insert #pancakes(place,cakesize) values(79,71)
insert #pancakes(place,cakesize) values(80,153)
insert #pancakes(place,cakesize) values(81,145)
insert #pancakes(place,cakesize) values(82,163)
insert #pancakes(place,cakesize) values(83,201)
insert #pancakes(place,cakesize) values(84,65)
insert #pancakes(place,cakesize) values(85,21)
insert #pancakes(place,cakesize) values(86,111)
insert #pancakes(place,cakesize) values(87,99)
insert #pancakes(place,cakesize) values(88,121)
insert #pancakes(place,cakesize) values(89,193)
insert #pancakes(place,cakesize) values(90,149)
insert #pancakes(place,cakesize) values(91,105)
insert #pancakes(place,cakesize) values(92,5)
insert #pancakes(place,cakesize) values(93,177)
insert #pancakes(place,cakesize) values(94,37)
insert #pancakes(place,cakesize) values(95,175)
insert #pancakes(place,cakesize) values(96,119)
insert #pancakes(place,cakesize) values(97,83)
insert #pancakes(place,cakesize) values(98,139)
insert #pancakes(place,cakesize) values(99,137)
insert #pancakes(place,cakesize) values(100,101)
insert #pancakes(place,cakesize) values(101,165)


rockmoose
Go to Top of Page

jhermiz

3564 Posts
Posted - 2005-03-01 : 17:54:01
Heres my algo:

20x faster than all of yours:


INSERT INTO MyMouth(Pancakes, Syrup) VALUES(@Pancakes, @Syrup)


All it took was one line of code...where do you people come up with these :).



Keeping the web experience alive -- [url]http://www.web-impulse.com[/url]
Imperfection living for perfection -- [url]http://jhermiz.blogspot.com/[/url]
Go to Top of Page

rockmoose
SQL Natt Alfen

3279 Posts
Posted - 2005-03-02 : 04:40:01
Here is the code I used,
I can't beat Corey's 28 flips of the static 25 pancake pile ( does it in 29 )
What is thee optimal algorithm ???
Apart from Jon Jhermiz optimal solution of course 
set nocount on

-- The number of pancakes, set this variable to whatever
-- 201 pancakes approx 20-30 sec
declare @nopancakes smallint
set @nopancakes = 25

-- create table with a pile of different sized pancakes
create table #pancakes(place tinyint identity(1,1) unique, cakesize smallint not null unique)
insert #pancakes(cakesize)
select number*2+1 from master.dbo.spt_values where type = 'P' and number/@nopancakes = 0
order by newid()

/* display pile from start */
select cakesize,place,replicate(' ',((select max(cakesize) from #pancakes)-cakesize)/2)+replicate('*',cakesize) as pancakes
from #pancakes order by place

-- Add flipsequence column to #pancakes table
alter table #pancakes add flipsequence varchar(8000) not null default('')
GO

-- Create auxiliary table which will hold sequences of sorted pancakes in the pile
create table #sequences(fromplace tinyint, toplace tinyint, check(fromplace<toplace))

-- start working
declare @flipplace tinyint, @sequence char(1), @i tinyint, @fromplace tinyint, @toplace tinyint
while 1=1
begin
	/* calculate auxiliary #sequence table */
	truncate table #sequences
	select @i = 0, @fromplace = 1, @toplace = null, @flipplace = null
	while @i < (select max(place)-1 from #pancakes)
	begin
		set @i = @i + 1
		if @sequence is null
			select @sequence = case when p1.cakesize < p2.cakesize then 'a' else 'd' end from #pancakes p1, #pancakes p2 where p1.place = @i and p2.place = @i + 1
		if exists(	select cakesize from #pancakes where place = @i + 1
				and cakesize = case @sequence when 'a' then 2 when 'd' then -2 end + (select cakesize from #pancakes where place = @i) )
			set @toplace = @i + 1
		else
		begin
			insert #sequences(fromplace, toplace) select @fromplace, @toplace where @fromplace < @toplace
			select @sequence = null, @fromplace = @i + 1, @toplace = null
		end
		if @i = (select max(place)-1 from #pancakes)
			insert #sequences(fromplace, toplace) select @fromplace, @toplace where @fromplace < @toplace
	end

	/* Start to calculate the place to insert the spatula and flip the pile */
	
	-- Special case: if the largest pancake is on top of pile just flip the pile
	if (select cakesize from #pancakes where place = 1) = (select max(cakesize) from #pancakes)
	set @flipplace = (select max(place) from #pancakes)

	-- Find "highest" flipplace that doesn't break a sequence and will order the cake at the top of the pile
	if @flipplace is null
	select @flipplace = (	select max(p2.place-1) from #pancakes p1 join #pancakes p2
				on p1.place = 1 and abs(p2.cakesize-p1.cakesize) = 2 and p2.place-1 > 1
				where not exists( select * from #sequences s where (p2.place-1) between s.fromplace and (s.toplace-1) ) )

	-- We did not find a flipplace that will not break a sequence, we must determine another flipplace
	if @flipplace is null
	begin
		-- Special case: If the biggest cake is not at bottom of pile, bring biggest cake to top.
		if (select cakesize from #pancakes where place = (select max(place) from #pancakes)) <> (select max(cakesize) from #pancakes)
			select @flipplace = (select place from #pancakes where cakesize = (select max(cakesize) from #pancakes))
		-- Otherwise bring the largest cake that is unsorted from bottom of pile to the top
		if @flipplace is null
		begin
			declare @p tinyint
			set @p = (select max(place) from #pancakes)
			while exists(select * from #pancakes where place = @p-1 and cakesize+2 = (select cakesize from #pancakes where place = @p))
				set @p = @p - 1
			select @flipplace = place from #pancakes where cakesize+2 = (select cakesize from #pancakes where place = @p)
		end
	end

	-- No place to flip, means pile is sorted, hopefully
	if @flipplace is null or (select count(*) from #pancakes) = 1
		break
	
	-- Flip the pancakes at the flipplace, this does the actual flip at the flipplace
	update #pancakes set cakesize = flippedcakes.cakesize ,flipsequence = #pancakes.flipsequence + ltrim(@flipplace) + ','
	from #pancakes join #pancakes flippedcakes on flippedcakes.place <= @flipplace and #pancakes.place = 1+@flipplace-flippedcakes.place
end


/* display results of the flipping */
select len(flipsequence)-len(replace(flipsequence,',','')) as flips, flipsequence as flipsequence
from #pancakes where place = 1

/* display pile when finished flipping */
select cakesize,place,replicate(' ',((select max(cakesize) from #pancakes)-cakesize)/2)+replicate('*',cakesize) as pancakes
from #pancakes order by place

drop table #pancakes
drop table #sequences


rockmoose
Go to Top of Page

Seventhnight
Master Smack Fu Yak Hacker

2878 Posts
Posted - 2005-03-02 : 08:24:55
Looks pretty cool Rock...I'll have to study it more a bit later.

I printed out the 28 flip solution (the stack at each step), and I am going to look at that today while I'm in class.

I'll let you know if I come up with anything.

Corey

"If the only tool you have is a hammer, the whole world looks like a nail." - Mark Twain
Go to Top of Page

rockmoose
SQL Natt Alfen

3279 Posts
Posted - 2005-03-02 : 09:34:10
What's the class, cooking?
You could post the 28 flip solution when You have time.

The way I see it, a flip can at best order 1 cake, and it might disorder another one.
So the thing is to find a sequence of flips that does the least unordering of the pile.
It's a pretty easy problem to solve, but difficult to find an optimal solution.

Have a good day in class :)

rockmoose
Go to Top of Page

Seventhnight
Master Smack Fu Yak Hacker

2878 Posts
Posted - 2005-03-02 : 15:14:36
EDIT: class was Adv. Calc II & West Civ. (loads of fun )

My algorithm uses two different methods:

a) flip the pile so that the top cake is ordered directly on top of the next largest cake
b) flip the pile so that the largest unordered cake is brought to the top.

The 28 flip solution is not a built by an optimal algorithm, just a combination of these two methods. I have been trying to determine a method of producing this solution from a static algorithm, but I haven't so far.

This is what I have been using to study the flips, hope you have better luck than me :

Set NoCount On

create table #pancakes(place tinyint, cakesize smallint not null unique)
insert #pancakes(place,cakesize) values(1,27)
insert #pancakes(place,cakesize) values(2,33)
insert #pancakes(place,cakesize) values(3,45)
insert #pancakes(place,cakesize) values(4,15)
insert #pancakes(place,cakesize) values(5,13)
insert #pancakes(place,cakesize) values(6,35)
insert #pancakes(place,cakesize) values(7,21)
insert #pancakes(place,cakesize) values(8,49)
insert #pancakes(place,cakesize) values(9,11)
insert #pancakes(place,cakesize) values(10,41)
insert #pancakes(place,cakesize) values(11,17)
insert #pancakes(place,cakesize) values(12,9)
insert #pancakes(place,cakesize) values(13,1)
insert #pancakes(place,cakesize) values(14,7)
insert #pancakes(place,cakesize) values(15,19)
insert #pancakes(place,cakesize) values(16,29)
insert #pancakes(place,cakesize) values(17,25)
insert #pancakes(place,cakesize) values(18,5)
insert #pancakes(place,cakesize) values(19,39)
insert #pancakes(place,cakesize) values(20,47)
insert #pancakes(place,cakesize) values(21,43)
insert #pancakes(place,cakesize) values(22,31)
insert #pancakes(place,cakesize) values(23,3)
insert #pancakes(place,cakesize) values(24,37)
insert #pancakes(place,cakesize) values(25,23)

Declare @swapNum int,
	@lastpos int,
	@history varchar(1000)
Select @lastpos = 0
Select @history = '15,8,25,8,3,24,9,12,23,18,4,16,22,9,6,21,3,19,11,18,7,17,12,16,2,15,3,4' --28
--Select @history = '16,15,4,7,25,8,5,21,19,24,14,2,20,7,12,23,7,11,10,7,21,4,8,4,9,10,9,19,3' --29
--Select @history = '15,8,25,16,4,11,24,3,6,5,12,14,23,20,9,19,6,18,13,8,16,2,11,4,2,12,16,3,6,4' --30
--Select @history = '15,8,25,16,4,11,24,3,6,2,14,23,13,14,21,3,19,4,2,16,13,3,18,16,3,7,5,15,16,2,3' --31


Create Table #pancakesHistory (place tinyint, cakesize int, flip1 int, flip2 int, flip3 int, flip4 int, flip5 int, flip6 int, flip7 int, flip8 int, flip9 int, flip10 int, flip11 int, flip12 int, flip13 int, flip14 int, flip15 int, flip16 int, flip17 int, flip18 int, flip19 int, flip20 int, flip21 int, flip22 int, flip23 int, flip24 int, flip25 int, flip26 int, flip27 int, flip28 int, flip29 int, flip30 int, flip31 int, flip32 int, flip33 int, flip34 int, flip35 int)
Insert Into #pancakesHistory (place,cakesize) Select * From #pancakes Select @swapNum = substring(@history,@lastPos+1,isnull(nullif(charindex(',',@history,@lastpos+1),0),len(@history)+1)-@lastPos-1), @lastpos = charindex(',',@history,@lastpos+1) Update #pancakes Set place = @swapNum-place + 1 From #pancakes Where place between 1 and @swapNum 

if @lastpos>=0 Begin Update #pancakesHistory Set flip1=#pancakes.cakesize From #pancakesHistory inner Join #pancakes On #pancakesHistory.place = #pancakes.place Select @swapNum = substring(@history,@lastPos+1,isnull(nullif(charindex(',',@history,@lastpos+1),0),len(@history)+1)-@lastPos-1), @lastpos = case when @lastPos=0 then -1 else charindex(',',@history,@lastpos+1) end Update #pancakes Set place = @swapNum-place + 1 From #pancakes Where place between 1 and @swapNum End
if @lastpos>=0 Begin Update #pancakesHistory Set flip2=#pancakes.cakesize From #pancakesHistory inner Join #pancakes On #pancakesHistory.place = #pancakes.place Select @swapNum = substring(@history,@lastPos+1,isnull(nullif(charindex(',',@history,@lastpos+1),0),len(@history)+1)-@lastPos-1), @lastpos = case when @lastPos=0 then -1 else charindex(',',@history,@lastpos+1) end Update #pancakes Set place = @swapNum-place + 1 From #pancakes Where place between 1 and @swapNum End
if @lastpos>=0 Begin Update #pancakesHistory Set flip3=#pancakes.cakesize From #pancakesHistory inner Join #pancakes On #pancakesHistory.place = #pancakes.place Select @swapNum = substring(@history,@lastPos+1,isnull(nullif(charindex(',',@history,@lastpos+1),0),len(@history)+1)-@lastPos-1), @lastpos = case when @lastPos=0 then -1 else charindex(',',@history,@lastpos+1) end Update #pancakes Set place = @swapNum-place + 1 From #pancakes Where place between 1 and @swapNum End
if @lastpos>=0 Begin Update #pancakesHistory Set flip4=#pancakes.cakesize From #pancakesHistory inner Join #pancakes On #pancakesHistory.place = #pancakes.place Select @swapNum = substring(@history,@lastPos+1,isnull(nullif(charindex(',',@history,@lastpos+1),0),len(@history)+1)-@lastPos-1), @lastpos = case when @lastPos=0 then -1 else charindex(',',@history,@lastpos+1) end Update #pancakes Set place = @swapNum-place + 1 From #pancakes Where place between 1 and @swapNum End
if @lastpos>=0 Begin Update #pancakesHistory Set flip5=#pancakes.cakesize From #pancakesHistory inner Join #pancakes On #pancakesHistory.place = #pancakes.place Select @swapNum = substring(@history,@lastPos+1,isnull(nullif(charindex(',',@history,@lastpos+1),0),len(@history)+1)-@lastPos-1), @lastpos = case when @lastPos=0 then -1 else charindex(',',@history,@lastpos+1) end Update #pancakes Set place = @swapNum-place + 1 From #pancakes Where place between 1 and @swapNum End
if @lastpos>=0 Begin Update #pancakesHistory Set flip6=#pancakes.cakesize From #pancakesHistory inner Join #pancakes On #pancakesHistory.place = #pancakes.place Select @swapNum = substring(@history,@lastPos+1,isnull(nullif(charindex(',',@history,@lastpos+1),0),len(@history)+1)-@lastPos-1), @lastpos = case when @lastPos=0 then -1 else charindex(',',@history,@lastpos+1) end Update #pancakes Set place = @swapNum-place + 1 From #pancakes Where place between 1 and @swapNum End
if @lastpos>=0 Begin Update #pancakesHistory Set flip7=#pancakes.cakesize From #pancakesHistory inner Join #pancakes On #pancakesHistory.place = #pancakes.place Select @swapNum = substring(@history,@lastPos+1,isnull(nullif(charindex(',',@history,@lastpos+1),0),len(@history)+1)-@lastPos-1), @lastpos = case when @lastPos=0 then -1 else charindex(',',@history,@lastpos+1) end Update #pancakes Set place = @swapNum-place + 1 From #pancakes Where place between 1 and @swapNum End
if @lastpos>=0 Begin Update #pancakesHistory Set flip8=#pancakes.cakesize From #pancakesHistory inner Join #pancakes On #pancakesHistory.place = #pancakes.place Select @swapNum = substring(@history,@lastPos+1,isnull(nullif(charindex(',',@history,@lastpos+1),0),len(@history)+1)-@lastPos-1), @lastpos = case when @lastPos=0 then -1 else charindex(',',@history,@lastpos+1) end Update #pancakes Set place = @swapNum-place + 1 From #pancakes Where place between 1 and @swapNum End
if @lastpos>=0 Begin Update #pancakesHistory Set flip9=#pancakes.cakesize From #pancakesHistory inner Join #pancakes On #pancakesHistory.place = #pancakes.place Select @swapNum = substring(@history,@lastPos+1,isnull(nullif(charindex(',',@history,@lastpos+1),0),len(@history)+1)-@lastPos-1), @lastpos = case when @lastPos=0 then -1 else charindex(',',@history,@lastpos+1) end Update #pancakes Set place = @swapNum-place + 1 From #pancakes Where place between 1 and @swapNum End
if @lastpos>=0 Begin Update #pancakesHistory Set flip10=#pancakes.cakesize From #pancakesHistory inner Join #pancakes On #pancakesHistory.place = #pancakes.place Select @swapNum = substring(@history,@lastPos+1,isnull(nullif(charindex(',',@history,@lastpos+1),0),len(@history)+1)-@lastPos-1), @lastpos = case when @lastPos=0 then -1 else charindex(',',@history,@lastpos+1) end Update #pancakes Set place = @swapNum-place + 1 From #pancakes Where place between 1 and @swapNum End
if @lastpos>=0 Begin Update #pancakesHistory Set flip11=#pancakes.cakesize From #pancakesHistory inner Join #pancakes On #pancakesHistory.place = #pancakes.place Select @swapNum = substring(@history,@lastPos+1,isnull(nullif(charindex(',',@history,@lastpos+1),0),len(@history)+1)-@lastPos-1), @lastpos = case when @lastPos=0 then -1 else charindex(',',@history,@lastpos+1) end Update #pancakes Set place = @swapNum-place + 1 From #pancakes Where place between 1 and @swapNum End
if @lastpos>=0 Begin Update #pancakesHistory Set flip12=#pancakes.cakesize From #pancakesHistory inner Join #pancakes On #pancakesHistory.place = #pancakes.place Select @swapNum = substring(@history,@lastPos+1,isnull(nullif(charindex(',',@history,@lastpos+1),0),len(@history)+1)-@lastPos-1), @lastpos = case when @lastPos=0 then -1 else charindex(',',@history,@lastpos+1) end Update #pancakes Set place = @swapNum-place + 1 From #pancakes Where place between 1 and @swapNum End
if @lastpos>=0 Begin Update #pancakesHistory Set flip13=#pancakes.cakesize From #pancakesHistory inner Join #pancakes On #pancakesHistory.place = #pancakes.place Select @swapNum = substring(@history,@lastPos+1,isnull(nullif(charindex(',',@history,@lastpos+1),0),len(@history)+1)-@lastPos-1), @lastpos = case when @lastPos=0 then -1 else charindex(',',@history,@lastpos+1) end Update #pancakes Set place = @swapNum-place + 1 From #pancakes Where place between 1 and @swapNum End
if @lastpos>=0 Begin Update #pancakesHistory Set flip14=#pancakes.cakesize From #pancakesHistory inner Join #pancakes On #pancakesHistory.place = #pancakes.place Select @swapNum = substring(@history,@lastPos+1,isnull(nullif(charindex(',',@history,@lastpos+1),0),len(@history)+1)-@lastPos-1), @lastpos = case when @lastPos=0 then -1 else charindex(',',@history,@lastpos+1) end Update #pancakes Set place = @swapNum-place + 1 From #pancakes Where place between 1 and @swapNum End
if @lastpos>=0 Begin Update #pancakesHistory Set flip15=#pancakes.cakesize From #pancakesHistory inner Join #pancakes On #pancakesHistory.place = #pancakes.place Select @swapNum = substring(@history,@lastPos+1,isnull(nullif(charindex(',',@history,@lastpos+1),0),len(@history)+1)-@lastPos-1), @lastpos = case when @lastPos=0 then -1 else charindex(',',@history,@lastpos+1) end Update #pancakes Set place = @swapNum-place + 1 From #pancakes Where place between 1 and @swapNum End
if @lastpos>=0 Begin Update #pancakesHistory Set flip16=#pancakes.cakesize From #pancakesHistory inner Join #pancakes On #pancakesHistory.place = #pancakes.place Select @swapNum = substring(@history,@lastPos+1,isnull(nullif(charindex(',',@history,@lastpos+1),0),len(@history)+1)-@lastPos-1), @lastpos = case when @lastPos=0 then -1 else charindex(',',@history,@lastpos+1) end Update #pancakes Set place = @swapNum-place + 1 From #pancakes Where place between 1 and @swapNum End
if @lastpos>=0 Begin Update #pancakesHistory Set flip17=#pancakes.cakesize From #pancakesHistory inner Join #pancakes On #pancakesHistory.place = #pancakes.place Select @swapNum = substring(@history,@lastPos+1,isnull(nullif(charindex(',',@history,@lastpos+1),0),len(@history)+1)-@lastPos-1), @lastpos = case when @lastPos=0 then -1 else charindex(',',@history,@lastpos+1) end Update #pancakes Set place = @swapNum-place + 1 From #pancakes Where place between 1 and @swapNum End
if @lastpos>=0 Begin Update #pancakesHistory Set flip18=#pancakes.cakesize From #pancakesHistory inner Join #pancakes On #pancakesHistory.place = #pancakes.place Select @swapNum = substring(@history,@lastPos+1,isnull(nullif(charindex(',',@history,@lastpos+1),0),len(@history)+1)-@lastPos-1), @lastpos = case when @lastPos=0 then -1 else charindex(',',@history,@lastpos+1) end Update #pancakes Set place = @swapNum-place + 1 From #pancakes Where place between 1 and @swapNum End
if @lastpos>=0 Begin Update #pancakesHistory Set flip19=#pancakes.cakesize From #pancakesHistory inner Join #pancakes On #pancakesHistory.place = #pancakes.place Select @swapNum = substring(@history,@lastPos+1,isnull(nullif(charindex(',',@history,@lastpos+1),0),len(@history)+1)-@lastPos-1), @lastpos = case when @lastPos=0 then -1 else charindex(',',@history,@lastpos+1) end Update #pancakes Set place = @swapNum-place + 1 From #pancakes Where place between 1 and @swapNum End
if @lastpos>=0 Begin Update #pancakesHistory Set flip20=#pancakes.cakesize From #pancakesHistory inner Join #pancakes On #pancakesHistory.place = #pancakes.place Select @swapNum = substring(@history,@lastPos+1,isnull(nullif(charindex(',',@history,@lastpos+1),0),len(@history)+1)-@lastPos-1), @lastpos = case when @lastPos=0 then -1 else charindex(',',@history,@lastpos+1) end Update #pancakes Set place = @swapNum-place + 1 From #pancakes Where place between 1 and @swapNum End
if @lastpos>=0 Begin Update #pancakesHistory Set flip21=#pancakes.cakesize From #pancakesHistory inner Join #pancakes On #pancakesHistory.place = #pancakes.place Select @swapNum = substring(@history,@lastPos+1,isnull(nullif(charindex(',',@history,@lastpos+1),0),len(@history)+1)-@lastPos-1), @lastpos = case when @lastPos=0 then -1 else charindex(',',@history,@lastpos+1) end Update #pancakes Set place = @swapNum-place + 1 From #pancakes Where place between 1 and @swapNum End
if @lastpos>=0 Begin Update #pancakesHistory Set flip22=#pancakes.cakesize From #pancakesHistory inner Join #pancakes On #pancakesHistory.place = #pancakes.place Select @swapNum = substring(@history,@lastPos+1,isnull(nullif(charindex(',',@history,@lastpos+1),0),len(@history)+1)-@lastPos-1), @lastpos = case when @lastPos=0 then -1 else charindex(',',@history,@lastpos+1) end Update #pancakes Set place = @swapNum-place + 1 From #pancakes Where place between 1 and @swapNum End
if @lastpos>=0 Begin Update #pancakesHistory Set flip23=#pancakes.cakesize From #pancakesHistory inner Join #pancakes On #pancakesHistory.place = #pancakes.place Select @swapNum = substring(@history,@lastPos+1,isnull(nullif(charindex(',',@history,@lastpos+1),0),len(@history)+1)-@lastPos-1), @lastpos = case when @lastPos=0 then -1 else charindex(',',@history,@lastpos+1) end Update #pancakes Set place = @swapNum-place + 1 From #pancakes Where place between 1 and @swapNum End
if @lastpos>=0 Begin Update #pancakesHistory Set flip24=#pancakes.cakesize From #pancakesHistory inner Join #pancakes On #pancakesHistory.place = #pancakes.place Select @swapNum = substring(@history,@lastPos+1,isnull(nullif(charindex(',',@history,@lastpos+1),0),len(@history)+1)-@lastPos-1), @lastpos = case when @lastPos=0 then -1 else charindex(',',@history,@lastpos+1) end Update #pancakes Set place = @swapNum-place + 1 From #pancakes Where place between 1 and @swapNum End
if @lastpos>=0 Begin Update #pancakesHistory Set flip25=#pancakes.cakesize From #pancakesHistory inner Join #pancakes On #pancakesHistory.place = #pancakes.place Select @swapNum = substring(@history,@lastPos+1,isnull(nullif(charindex(',',@history,@lastpos+1),0),len(@history)+1)-@lastPos-1), @lastpos = case when @lastPos=0 then -1 else charindex(',',@history,@lastpos+1) end Update #pancakes Set place = @swapNum-place + 1 From #pancakes Where place between 1 and @swapNum End
if @lastpos>=0 Begin Update #pancakesHistory Set flip26=#pancakes.cakesize From #pancakesHistory inner Join #pancakes On #pancakesHistory.place = #pancakes.place Select @swapNum = substring(@history,@lastPos+1,isnull(nullif(charindex(',',@history,@lastpos+1),0),len(@history)+1)-@lastPos-1), @lastpos = case when @lastPos=0 then -1 else charindex(',',@history,@lastpos+1) end Update #pancakes Set place = @swapNum-place + 1 From #pancakes Where place between 1 and @swapNum End
if @lastpos>=0 Begin Update #pancakesHistory Set flip27=#pancakes.cakesize From #pancakesHistory inner Join #pancakes On #pancakesHistory.place = #pancakes.place Select @swapNum = substring(@history,@lastPos+1,isnull(nullif(charindex(',',@history,@lastpos+1),0),len(@history)+1)-@lastPos-1), @lastpos = case when @lastPos=0 then -1 else charindex(',',@history,@lastpos+1) end Update #pancakes Set place = @swapNum-place + 1 From #pancakes Where place between 1 and @swapNum End
if @lastpos>=0 Begin Update #pancakesHistory Set flip28=#pancakes.cakesize From #pancakesHistory inner Join #pancakes On #pancakesHistory.place = #pancakes.place Select @swapNum = substring(@history,@lastPos+1,isnull(nullif(charindex(',',@history,@lastpos+1),0),len(@history)+1)-@lastPos-1), @lastpos = case when @lastPos=0 then -1 else charindex(',',@history,@lastpos+1) end Update #pancakes Set place = @swapNum-place + 1 From #pancakes Where place between 1 and @swapNum End
if @lastpos>=0 Begin Update #pancakesHistory Set flip29=#pancakes.cakesize From #pancakesHistory inner Join #pancakes On #pancakesHistory.place = #pancakes.place Select @swapNum = substring(@history,@lastPos+1,isnull(nullif(charindex(',',@history,@lastpos+1),0),len(@history)+1)-@lastPos-1), @lastpos = case when @lastPos=0 then -1 else charindex(',',@history,@lastpos+1) end Update #pancakes Set place = @swapNum-place + 1 From #pancakes Where place between 1 and @swapNum End
if @lastpos>=0 Begin Update #pancakesHistory Set flip30=#pancakes.cakesize From #pancakesHistory inner Join #pancakes On #pancakesHistory.place = #pancakes.place Select @swapNum = substring(@history,@lastPos+1,isnull(nullif(charindex(',',@history,@lastpos+1),0),len(@history)+1)-@lastPos-1), @lastpos = case when @lastPos=0 then -1 else charindex(',',@history,@lastpos+1) end Update #pancakes Set place = @swapNum-place + 1 From #pancakes Where place between 1 and @swapNum End
if @lastpos>=0 Begin Update #pancakesHistory Set flip31=#pancakes.cakesize From #pancakesHistory inner Join #pancakes On #pancakesHistory.place = #pancakes.place Select @swapNum = substring(@history,@lastPos+1,isnull(nullif(charindex(',',@history,@lastpos+1),0),len(@history)+1)-@lastPos-1), @lastpos = case when @lastPos=0 then -1 else charindex(',',@history,@lastpos+1) end Update #pancakes Set place = @swapNum-place + 1 From #pancakes Where place between 1 and @swapNum End
if @lastpos>=0 Begin Update #pancakesHistory Set flip32=#pancakes.cakesize From #pancakesHistory inner Join #pancakes On #pancakesHistory.place = #pancakes.place Select @swapNum = substring(@history,@lastPos+1,isnull(nullif(charindex(',',@history,@lastpos+1),0),len(@history)+1)-@lastPos-1), @lastpos = case when @lastPos=0 then -1 else charindex(',',@history,@lastpos+1) end Update #pancakes Set place = @swapNum-place + 1 From #pancakes Where place between 1 and @swapNum End
if @lastpos>=0 Begin Update #pancakesHistory Set flip33=#pancakes.cakesize From #pancakesHistory inner Join #pancakes On #pancakesHistory.place = #pancakes.place Select @swapNum = substring(@history,@lastPos+1,isnull(nullif(charindex(',',@history,@lastpos+1),0),len(@history)+1)-@lastPos-1), @lastpos = case when @lastPos=0 then -1 else charindex(',',@history,@lastpos+1) end Update #pancakes Set place = @swapNum-place + 1 From #pancakes Where place between 1 and @swapNum End
if @lastpos>=0 Begin Update #pancakesHistory Set flip34=#pancakes.cakesize From #pancakesHistory inner Join #pancakes On #pancakesHistory.place = #pancakes.place Select @swapNum = substring(@history,@lastPos+1,isnull(nullif(charindex(',',@history,@lastpos+1),0),len(@history)+1)-@lastPos-1), @lastpos = case when @lastPos=0 then -1 else charindex(',',@history,@lastpos+1) end Update #pancakes Set place = @swapNum-place + 1 From #pancakes Where place between 1 and @swapNum End
if @lastpos>=0 Begin Update #pancakesHistory Set flip35=#pancakes.cakesize From #pancakesHistory inner Join #pancakes On #pancakesHistory.place = #pancakes.place End

Select * From #pancakesHistory

drop Table #pancakes
drop Table #pancakesHistory

Set NoCount Off


Corey

"If the only tool you have is a hammer, the whole world looks like a nail." - Mark Twain
Go to Top of Page

rockmoose
SQL Natt Alfen

3279 Posts
Posted - 2005-03-02 : 16:48:52
We have basically the same algorithms:

A1
a) flip the pile so that the top cake is ordered directly on top of the next largest cake
b) flip the pile so that the largest unordered cake is brought to the top.
*) the choice of a or b is not static ?

A2
choice1) flip the pile so that the top cake is "ordered"(asc/desc) on top of a cake adjacent to it's size,
(without breaking a sequence of "ordered"(asc/desc) cakes in the process). If there are > 1 possible places, choose the "highest".
choice2) flip the pile so that the largest unordered cake is brought to the top.


Not many takers on this challenge, but it probably did not have much "real world" applicability.
We'll see what comes up next



rockmoose
Go to Top of Page

Seventhnight
Master Smack Fu Yak Hacker

2878 Posts
Posted - 2005-03-02 : 17:38:47
I don't think our algorithms have a chance. As in the Sliding Tiles Puzzle we discovered that
sometimes the best move doesn't seem like a forward step.

I came up with this 26 flip solution (solving by hand rather than query)
15,8,25,2,6,24,9,12,23,22,4,21,9,2,8,4,20,4,7,2,18,9,18,10,12,3

this seems to point towards a forward looking algorithm.

there are really three options:
a) sort the top cake
b) bring the largest unsorted to the top
c) flip with neither A or B occuring.

You ask... "Why would you ever choose 'C'?"
Well when I was solving this, in atleast one of my moves i moved to
position the cakes so that the next move would not be A or B, but A and B. There
were actually 9 flips where A & B were
satisfied. I believe this is where the few
extra flips were saved.

Now the question is can we automate it??


Corey

"If the only tool you have is a hammer, the whole world looks like a nail." - Mark Twain
Go to Top of Page

rockmoose
SQL Natt Alfen

3279 Posts
Posted - 2005-03-02 : 18:16:00
Forward looking algorithms are a bit more difficult.. he
One must find a way to "quantify the quality" of any given move/status of the pile.
This problem is probably much easier than the sliding tiles one, (I remember... all too well).

Yes of course we don't have much chance,
we make arbitrary decisions in the algorithms based on "this is probably best" assumptions,
and immediately throwing away possibly better solutions.

But I will not dig further into this particular problem

rockmoose
Go to Top of Page

TG
Master Smack Fu Yak Hacker

6065 Posts
Posted - 2005-03-02 : 19:01:27
How about this as a future challenge: Pose a very simple problem, then each of us code a solution in the style of a sql team member other than ourselves. The challenge is to guess who's style everyone emulated.

Be One with the Optimizer
TG
Go to Top of Page

rockmoose
SQL Natt Alfen

3279 Posts
Posted - 2005-03-02 : 19:26:24
quote:
Originally posted by TG

How about this as a future challenge: Pose a very simple problem, then each of us code a solution in the style of a sql team member other than ourselves. The challenge is to guess who's style everyone emulated.


nice one TG,
some get seaSick with the camelCasing,
other really_dizzy with the lower_case stuff,
and others just PRINT it OUT FOR readability,
And Some Think Each Word Is A New Sentence !
And that's just the layout...

rockmoose
Go to Top of Page
    Next Page

Subscribe to SQLTeam.com

SQLTeam.com Articles via RSS

SQLTeam.com Weblog via RSS

- Advertisement -

Resources

Articles

Forums

Blogs

Contact Us

About the Site