Courses‎ > ‎AP Computer Science 2‎ > ‎konstantinovich‎ > ‎

2018-05-02 Maze Frontier

posted May 2, 2018, 10:20 AM by Konstantinovich Samuel
Reminder:
Practice Exam 2, bring in on Monday.

Exam next week (Friday):
  multiple choice only
  general java stuff (studied already for the AP)
  Stacks, Queues, Trees, Heaps  

Goal: Frontier Based Maze Solver

Frontier: a list of yet-to-be-explored locations. 
  You can add to the frontier, or get (and remove) the next element. 

Q
How does the frontier grow in the maze solver we wrote before?
What locations are added to this frontier, and what order are they processed?

Example:

s _ _ _ _

_ # # # e

_ _ _ # _

_ # _ # _

_ _ # # _

_ A B C D

E # # # F

G H I # J

K # L # M

N O # # P

Our frontier was treated like a ______.




How does a frontier solver work?

done = false
Initialize your frontier with the starting node
while not done and not empty:
   get next node from the frontier
   if you found the end:
       done = true
   else: 
       process that node (which adds new nodes to the frontier)
if done:
   you solved it
else:
   no solution



Q
How can we change the way the frontier is processed?
Instead of a ____ we can use a ____

What would happen if we did this?
Draw the sample maze:

_ A B C D

E # # # F

G H I # J

K # L # M

N O # # P

Try the alternate form of the frontier. What is the resulting pattern?

Now we must design a data structure to have the ability to process nodes in 2 different ways.
What java construct allows a single set of methods to behave in different ways?

HW: Design the UML diagram for this maze solver.







Preliminary Results up to 8:
Lab 8: less than 8 with no fails means your add end / beginning was non-constant.

OSIS PASS / 46 FAIL / 46 05PASS 05FAIL 05#lin 06PASS 06FAIL 06#lin 07PASS 07FAIL 07#lin 08PASS 08FAIL 08#lin
208652602 46 0 20 0 23 10 0 11 10 0 11 6 0 7
208824680 46 0 20 0 23 10 0 11 10 0 11 6 0 7
208817148 46 0 20 0 23 10 0 11 10 0 11 6 0 7
211521372 46 0 20 0 23 10 0 11 10 0 11 6 0 7
213149834 46 0 20 0 23 10 0 11 10 0 11 6 0 7
209314327 46 0 20 0 23 10 0 11 10 0 11 6 0 7
214700411 46 0 20 0 23 10 0 11 10 0 11 6 0 7
214586992 46 0 20 0 23 10 0 11 10 0 11 6 0 7
214269698 46 0 20 0 23 10 0 11 10 0 11 6 0 7
209062025 46 0 20 0 23 10 0 11 10 0 11 6 0 7
209180272 46 0 20 0 23 10 0 11 10 0 11 6 0 7
208974055 46 0 20 0 23 10 0 11 10 0 11 6 0 7
209563600 46 0 20 0 23 10 0 11 10 0 11 6 0 7
208979344 46 0 20 0 23 10 0 11 10 0 11 6 0 7
236729943 46 0 20 0 23 10 0 11 10 0 11 6 0 7
236929352 46 0 20 0 23 10 0 11 10 0 11 6 0 7
219403144 46 0 20 0 23 10 0 11 10 0 11 6 0 7
209343813 46 0 20 0 23 10 0 11 10 0 11 6 0 7
241802008 46 0 20 0 23 10 0 11 10 0 11 6 0 7
209908870 46 0 20 0 23 10 0 11 10 0 11 6 0 7
209152545 46 0 20 0 23 10 0 11 10 0 11 6 0 7
231851098 46 0 20 0 23 10 0 11 10 0 11 6 0 7
209767730 46 0 20 0 23 10 0 11 10 0 11 6 0 7
208891606 46 0 20 0 23 10 0 11 10 0 11 6 0 7
214521304 46 0 20 0 23 10 0 11 10 0 11 6 0 7
209729425 46 0 20 0 23 10 0 11 10 0 11 6 0 7
215543406 46 0 20 0 23 10 0 11 10 0 11 6 0 7
208313379 44 0 20 0 4077 8 0 9 10 0 11 6 0 7
208393082 44 0 20 0 23 10 0 11 10 0 11 4 0 5
209381243 44 0 20 0 23 8 0 9 10 0 11 6 0 7
209319474 44 0 20 0 23 8 0 9 10 0 11 6 0 7
208544494 43 0 20 0 23 10 0 11 10 0 11 3 0 4
209167725 43 0 19 0 22 8 0 9 10 0 11 6 0 7
207695149 43 1 20 0 23 8 0 9 10 0 11 5 1 7
209489475 42 2 18 2 23 10 0 11 10 0 11 4 0 5
208992594 41 0 15 0 18 10 0 11 10 0 11 6 0 7
233536242 40 2 19 1 23 10 0 11 10 0 11 1 1 4
208709410 40 0 20 0 23 10 0 11 10 0 11 0 0 1
207519570 38 0 20 0 23 8 0 9 10 0 11 0 0 1
209262609 38 6 14 6 23 8 0 9 10 0 11 6 0 7
209725308 36 4 16 4 23 10 0 11 4 0 5 6 0 7
214592685 36 0 20 0 23 10 0 11 0 0 1 6 0 7
209682293 36 0 20 0 33 10 0 11 0 0 1 6 0 7
215062944 33 3 10 0 13 10 0 11 10 0 11 3 3 7
208719062 31 13 10 10 23 8 0 9 10 0 11 3 3 7
209343888 31 4 16 4 23 10 0 11 0 0 1 5 0 6
211671136 30 0 20 0 23 2 0 3 2 0 3 6 0 7
208942532 26 0 0 0 3 10 0 11 10 0 11 6 0 7
209322718 22 22 2 18 23 10 0 11 4 4 9 6 0 7
209180512 19 9 11 9 23 2 0 3 0 0 1 6 0 7
207142159 12 4 0 0 3 4 4 9 2 0 3 6 0 7
214466500 12 17 2 17 22 0 0 316 10 0 11 0 0 1
208356410 10 20 1 19 23 0 0 1 8 0 9 1 1 4
213463227 10 0 0 0 3 10 0 11 0 0 1 0 0 1
208781666 3 0 0 0 3 0 0 1 2 0 3 1 0 2
209028257 3 0 0 0 3 0 0 1 2 0 3 1 0 2
209046838 1 0 0 0 3 0 0 1 0 0 1 1 0 2
206939092 0 0 0 0 3 0 0 1 0 0 1 0 0 1
208791855 0 0 0 0 3 0 0 1 0 0 1 0 0 1
214377137 0 0 0 0 3 0 0 1 0 0 1 0 0 1
Comments