Return to Video

04-11 Bridge Successors

  • 0:00 - 0:04
    Now, out of those many choices, I made a choice to say I'm going to represent
  • 0:04 - 0:09
    as a tuple of (here, there, t),
  • 0:09 - 0:13
    where "here" represents everything that's on this side,
  • 0:13 - 0:16
    "there" represents everything that's on that side,
  • 0:16 - 0:20
    and "t" is the total elapsed time since the start.
  • 0:20 - 0:26
    I'm going to represent here and there with frozen sets, because those are hashable.
  • 0:26 - 0:33
    So this collection here would be the frozen set consisting of {1, 2, 5, 10},
  • 0:33 - 0:40
    and I'm going to just use the string "light" to represent the flashlight.
  • 0:40 - 0:44
    There would be the empty frozen set.
  • 0:44 - 0:48
    Now, consider this state here representing the start state.
  • 0:48 - 0:50
    What are the successors of that state?
  • 0:50 - 0:52
    Well, any one of the people could go across.
  • 0:52 - 0:54
    They've got to bring the light with them.
  • 0:54 - 0:58
    In the successor state, the light will definitely be there, and it will not be here.
  • 0:58 - 1:00
    It can only be in one place.
  • 1:00 - 1:03
    At least one of the people will be over there
  • 1:03 - 1:05
    and possibly two of the people,
  • 1:05 - 1:09
    so all combinations of sending either one person or two people to the other side,
  • 1:09 - 1:12
    those will each be distinct successor states.
  • 1:12 - 1:18
    Let's see--we've got 4 x 3 is 12, but order doesn't matter, so there's 6 of those.
  • 1:18 - 1:22
    Then 4 more, so it looks like there should be 10 successor states.
  • 1:22 - 1:25
    What I want you to do is write for me the successor function.
  • 1:25 - 1:29
    We're calling it bsuccessors, because we already had a and we're on to b.
  • 1:29 - 1:32
    Or b could stand for "bridge."
  • 1:32 - 1:39
    Remember that a result of the successor function is the dictionary of state action pairs.
  • 1:39 - 1:42
    A state is this (here, there, t) tuple.
  • 1:42 - 1:45
    Here and there have to be frozen sets.
  • 1:45 - 1:50
    The frozen sets contained people--1, 2, 5, and 10--
  • 1:50 - 1:55
    and/or this light, indicated by the string "light."
  • 1:55 - 1:58
    Show me the function that will generate all the successors.
  • 1:58 - 2:05
    Here I've given you a hint of here's a way to break up the state into those three variables.
  • 2:05 - 2:10
    Then put your code here.
  • 2:10 - 2:13
    Oh, one more thing I forgot is what are the actions.
  • 2:13 - 2:20
    Well, let's say that an action will be represented by the character string arrow going to the right
  • 2:20 - 2:23
    if we're moving from here to there and an arrow going to the left
  • 2:23 -
    if we're moving from there to here.
Title:
04-11 Bridge Successors
Description:

dummy description

more » « less
Team:
Udacity
Project:
CS212 - Design of Computer Programs
Duration:
02:27
Amara Bot added a translation

English subtitles

Revisions