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 pancakescreate 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 = 0order by newid()print 'You have a pile with 25 different sized pancakes, and 1 spatulaYou 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 pancakesfrom #pancakes order by place/* Calculate the flipping sequence, How many flips will You need ?*/drop table #pancakesrockmoose |
|
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 #pancakesGOIf Object_ID('tempdb.dbo.#temp') is NULL Create Table #temp (place int, newPlace int identity)GOset nocount on-- create table with a pile of 25 different sized pancakescreate 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 = 0order by newid()print 'You have a pile with 25 different sized pancakes, and 1 spatulaYou 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, cakesizefrom #pancakes order by placeGOalter table #pancakes Add newPlace int nullGOUpdate #pancakes set newPlace = placedeclare @lastmax int ,@flips intselect @lastmax = max(cakesize) ,@flips = 0from #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 NULLBegin --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.seqEndselect place,replicate(' ',(49-cakesize)/2)+replicate('*',cakesize) as pancakes, cakesizefrom #pancakes order by newPlaceSelect @flips TotalFlipsIf Object_id('tempdb.dbo.#pancakes') > 0 drop table #pancakesIf Object_ID('tempdb.dbo.#temp') > 0 drop Table #temp max flips are 50average seems to be around 44Be One with the OptimizerTG |
|
|
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 neededDon't know if it can be optimized actually...Here is fix data to test on:truncate table #pancakesinsert #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 |
|
|
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 Oncreate 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 spatulaYou 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 pancakesfrom #pancakes order by place/* Calculate the flipping sequence, How many flips will You need ?*/--Select * From #pancakesDeclare @flips int, @goodTo int, @msg nvarchar(1000)Set @flips=0While @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 = nullEndSet @Msg = 'flips: ' + convert(varchar,@flips)RaisError(@Msg,0,1) With NOWAITSet @Msg = ''RaisError(@Msg,0,1) With NOWAITselect place,replicate(' ',(49-cakesize)/2)+replicate('*',cakesize) as pancakesfrom #pancakes order by placedrop table #pancakesSet NoCount Off Corey"If the only tool you have is a hammer, the whole world looks like a nail." - Mark Twain |
|
|
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 pancakescreate 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 = 0order by newid()select cakesize,place,replicate(' ',(49-cakesize)/2)+replicate('*',cakesize) as pancakesfrom #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.placeselect len(flipsequence)-len(replace(flipsequence,',','')) as flips, flipsequence as flipsequencefrom #pancakes where place = 1select cakesize,place,replicate(' ',(49-cakesize)/2)+replicate('*',cakesize) as pancakesfrom #pancakes order by placedrop table #pancakes rockmoose |
|
|
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 Oncreate 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 spatulaYou 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 pancakesfrom #pancakes order by place/* Calculate the flipping sequence, How many flips will You need ?*/--Select * From #pancakes Order By placeDeclare @flips int, @goodTo int, @swapNum int, @maxCake int, @pass int, @msg nvarchar(1000), @history varchar(1000)Set @flips=0Set @pass = 0While (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 nullBegin 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 + 1EndSet @Msg = 'flip Cnt: ' + convert(varchar,@flips)RaisError(@Msg,0,1) With NOWAITSet @Msg = 'flips: ' + @historyRaisError(@Msg,0,1) With NOWAITSet @Msg = ''RaisError(@Msg,0,1) With NOWAITselect place,replicate(' ',(49-cakesize)/2)+replicate('*',cakesize) as pancakesfrom #pancakes order by placedrop table #pancakesSet NoCount Off Results:flip Cnt: 34flips: 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 |
|
|
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,428 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,428 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,428 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,428 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,428 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,428 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,428 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,428 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,428 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,428 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,428 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,428 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,428 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,428 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,428 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,428 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,428 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,428 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,428 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 |
|
|
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,428 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,428 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,428 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,428 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,428 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 |
|
|
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,428 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 |
|
|
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 |
|
|
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 |
|
|
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] |
|
|
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 secdeclare @nopancakes smallintset @nopancakes = 25-- create table with a pile of different sized pancakescreate 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 = 0order by newid()/* display pile from start */select cakesize,place,replicate(' ',((select max(cakesize) from #pancakes)-cakesize)/2)+replicate('*',cakesize) as pancakesfrom #pancakes order by place-- Add flipsequence column to #pancakes tablealter table #pancakes add flipsequence varchar(8000) not null default('')GO-- Create auxiliary table which will hold sequences of sorted pancakes in the pilecreate table #sequences(fromplace tinyint, toplace tinyint, check(fromplace<toplace))-- start workingdeclare @flipplace tinyint, @sequence char(1), @i tinyint, @fromplace tinyint, @toplace tinyintwhile 1=1begin /* 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.placeend/* display results of the flipping */select len(flipsequence)-len(replace(flipsequence,',','')) as flips, flipsequence as flipsequencefrom #pancakes where place = 1/* display pile when finished flipping */select cakesize,place,replicate(' ',((select max(cakesize) from #pancakes)-cakesize)/2)+replicate('*',cakesize) as pancakesfrom #pancakes order by placedrop table #pancakesdrop table #sequences rockmoose |
|
|
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 |
|
|
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 |
|
|
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 cakeb) 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 Oncreate 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 = 0Select @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' --31Create 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 Endif @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 Endif @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 Endif @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 Endif @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 Endif @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 Endif @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 Endif @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 Endif @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 Endif @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 Endif @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 Endif @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 Endif @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 Endif @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 Endif @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 Endif @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 Endif @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 Endif @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 Endif @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 Endif @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 Endif @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 Endif @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 Endif @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 Endif @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 Endif @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 Endif @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 Endif @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 Endif @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 Endif @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 Endif @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 Endif @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 Endif @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 Endif @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 Endif @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 Endif @lastpos>=0 Begin Update #pancakesHistory Set flip35=#pancakes.cakesize From #pancakesHistory inner Join #pancakes On #pancakesHistory.place = #pancakes.place EndSelect * From #pancakesHistorydrop Table #pancakesdrop Table #pancakesHistorySet NoCount Off Corey"If the only tool you have is a hammer, the whole world looks like a nail." - Mark Twain |
|
|
rockmoose
SQL Natt Alfen
3279 Posts |
Posted - 2005-03-02 : 16:48:52
|
We have basically the same algorithms:A1a) flip the pile so that the top cake is ordered directly on top of the next largest cakeb) flip the pile so that the largest unordered cake is brought to the top.*) the choice of a or b is not static ?A2choice1) 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 |
|
|
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,3this seems to point towards a forward looking algorithm.there are really three options:a) sort the top cakeb) bring the largest unsorted to the topc) 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 |
|
|
rockmoose
SQL Natt Alfen
3279 Posts |
Posted - 2005-03-02 : 18:16:00
|
Forward looking algorithms are a bit more difficult.. heOne 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 |
|
|
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 OptimizerTG |
|
|
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 |
|
|
Next Page
|
|
|