CS#61B#Data#Structures#and#Programming#Methodology##July#31,#2008#David#Sun#Announcements#• Midterm#II#results#available#on#glookup.##– Mean#37.3#/#50#– Std#Dev:#9##• Midterm#II#papers#will#be#returned#to#you#during#discussion#secMons.##• Same#re‐grading#policies#as#last#Mme.#– Write#a#note#and#tell#us#what##you#think#was#incorrectly#graded.#Hand#it#to#me#or#one#of#the#t.a.s.#Check#you#soluMon#against#the#soluMon#online#to#make#sure#you#won’t#loose#more#points#than#you’d#gain.##– Best#to#get#it#to#us#before#the#end#of#next#week.##Project#3#• Sliding#block#puzzle:#– A#tray#stores#of#a#number#of#rectangular#blocks,#the#game#is#to#slide#the#pieces#without#liVing#any#out#of#the#tray,#unMl#achieving#a#certain#configuraMon.#• Write#a#program#that#solves#a#sliding#block#puzzle#in#as#liXle#execu%on(%me(as#possible.#– Need#not#find#the#shortest#possible#sequence#of#move.#IniMal#ConfiguraMon • Input:#a#file#containing#an#encoding(of#the#ini%al#tray#configuraMon.#5""4""2""1""0""0""2""1""0""3""2""1""2""0""2""1""2""3""2""2""1""1""1""2""3""1""1""1""4""0""1""1""4""1""1""1""4""2""1""1""4""3"542#1#(0,"0)#Goal#ConfiguraMon#• Input:#a#file#that#specifies#an#encoding(of#the#final#or#goal#configuraMon.##– This#file#does#not#contain#entries#for#all#blocks#in#the#tray.##– Blocks#may#appear#in#any#order#in#this#file.#2""2""3""1#1"1"3"1""1"1"4"2""1"1"3"2""SoluMon#• A#sequence#of#moves#of#blocks#that#turns#the#iniMal#configuraMon#to#the#in#the#goal.##• Legal#moves:##– Slide#block#horizontally#or#verMcally#into#adjacent#empty#space.##– Blocks#may#only#be#moved#an#integer#number#of#spaces.#– Either#the#row#or#the#column#will#be#the#same#in#the#start#posiMon#as#in#the#end#posiMon#for#each#move.##Format#of#SoluMon#• Sequence(of#block#movements#that#lead#to#a#soluMon.(• Each#such#line#will#contain#four#integers:#the#starMng#row#and#column#of#the#upper#leV#corner#of#the#moving#block,#followed#by#the#upper#leV#corner's#updated#coordinates.##1#1#0#1###move#the#2x2#block#up##3#1#2#1###move#the#1x2#block#up##4#1#3#1###move#a#1x1#block#up##4#2#3#2###move#another#1x1#block#up##4#0#4#2###move#the#leVmost#1x1#block#two#spaces#over#The#Game#• Your#program#will#search#the#tree#of#possible#move#sequences#to#find#a#soluMon#to#the#puzzle.#• Top#level#algorithm:#0.(((Ini%aliza%on(–(read(in(the(init(and(goal(configura%ons.(1. Generate(moves(from(the(current(configura%on(2. Pick(a(move(3. Update(the(current(configura%on(4. Con%nue(if(the(current(configura%on(does(not(match(the(end(configura%on(Key#Design#Designs#• Should#I#traverse#the#possible#configuraMons#breadth#first#or#depth#first?#– Either#way,#you’ll#likely#hit#some#resource#limit.##• DFS:#– If#you#find#a#soluMon#you#don't#know#whether#it#is#the#best#soluMon#or#not.##– You#can#run#into#a#very#deep#branch#in#the#search#tree#before#hieng#the#soluMon#or#the#stack#may#over#flow#– Can#try#bounding#the#search#at#some#fixed#depth,#and#do#iteraMve#deepening#if#soluMon#doesn’t#exist.##• BFS##– First#soluMon#is#the#most#opMmal#soluMon,#i.e.#minimal#number#of#steps#– If#there#are#many#empty#spaces#in#a#configuraMon,#the#set#of#possible#moves#from#any#given#configuraMon#can#be#huge.#Your#search#tree#will#be#very#wide,#and#the#queue#will#run#out#of#memory#before#you#hit#a#soluMon.##PrevenMng#Cycles#• How#do#I#prevent#cycles?#– Some#way#of#remembering#the#search#path#I’ve#taken#or#the#configuraMons#I’ve#seen.#– Maybe#use#a#hash#tables#–#O(1)#lookup#Mme#if#designed#well.##– Not#just#look#up#Mme#though,#how#long#does#it#take#to#compute#the#hash#code?#Key#Data#Structure#• Tray:#representaMon#of#the#current#configuraMon#of#the#board.##– How#do#I#represent#the#blocks?#– How#do#I#represent#the#empty#spaces?#– Should#I#represent#the#empty#spaces#explicitly?#– Should#I#represent#the#blocks#explicitly?#• Tray#representaMon#will#affect:#– How(you(read(in(the(configura%on(files(– How(you(find(the(moves(to(generate(from(the(current(configura%on(– How(you(update(a(configura%ons.(– How(you(hash(the(configura%ons.(– How(you(compare(configura%ons.(– How(long(you(can(grow(the(stack(or(queue(before(the(it(explodes.(One#Design#class Tray { //unsorted, added in the order specified in the //init config file ArrayList<Blocks> config; . . . class Blocks { int row; int col; int length; int width; . . . } What#are#some#of#the#issues#with#this#design?#ImplementaMon#Advice#• Think#carefully#about#how#the#tray#should#be#represented#but#do#not#dwell#on#it#for#too#long.#• Get#the#brute‐force#(exhausMve#search)#working#on#the#easy#puzzles#before#start#tuning.##• Don’t#waste#your#Mme#on#finding#an#op%mal(soluMon.#Test#your#algorithm#on#the#input#and#output#files#and#see#if#it#works#reasonably#well!#• Time#the#modules#in#your#code#to#find#where#the#boXle#necks#are!##– May#yield#surprises…#– There#are#many#Mming#faciliMes#in#Java#that#let’s#you#do#this.#Main#Modules?#TesMng#• Checker#program#that#checks#whether#a#given#sequence#of#moves#solves#a#given#puzzle.##– Takes#an#iniMal#configuraMon#and#a#goal#configuraMon#in#the#same#format#as#those#for#Solver.java.##– Takes#a#sequence#of#moves,#in#the#format#to#be#produced#by#Solver.java,#as#standard#input.##– Its#output#indicates#whether#the#moves#solve#the#puzzle,#and#if#not,#why#not.##• 3#sets#of#tesMng#files:#– Easy:#50#points#if#you#solve#almost#all#of#them.#– Medium:#get#no#points#for#solving#these.##– Hard:#2#points#for#each#hard#puzzle#you#solve#under#2#minutes.#Debug#Info#• An#opMonal#first#argument#will#be#a#string#whose#first#two#characters#are#"–o"#and#whose#remaining#characters#specify#informaMon#about#what#debugging#output#the#program#should#produce.##• You#may#choose#the#format#of#this#informaMon.#• You#may#choose#any#debugging#informaMon#to#output#– Doesn’t#need#to#a#whole#lot#– Demonstrates#to#us#that#you#used#some#form#of#debugging#output#to#help#you#verifying#the#result.#Useful#Debugging#Info?#HW#for#next#Monday#•
View Full Document