Return to Video

04-43 Writing Reductions Solution

  • 0:00 - 0:02
    Let's go through one way to do this.
  • 0:02 - 0:08
    Hopefully what we're currently looking at is x goes to ab dot nothing come from j.
  • 0:08 - 0:13
    Hopefully then, if we look back to chart j where we originally came from,
  • 0:13 - 0:19
    it will have some rule something go to blah, blah, blah dot x.
  • 0:19 - 0:21
    This is the important part.
  • 0:21 - 0:27
    We're reducing goes to ab, so I really hope somebody was looking for an x.
  • 0:27 - 0:30
    If they were, then that can be one of our reductions.
  • 0:30 - 0:35
    Once again, we're going to use the phenomenal cosmic power of Python list comprehensions.
  • 0:35 - 0:41
    In general, we're going to take all of these states that were already in chart j
  • 0:41 - 0:43
    and just modify them a bit.
  • 0:43 - 0:47
    Let's call each one of those states in chart j jstate.
  • 0:47 - 0:51
    Conceptually, what we're going to do is move the red dot over one.
  • 0:51 - 0:58
    Our return value, the new state we're returning, is going to have this same y that we saw from jstate.
  • 0:58 - 1:01
    Whatever that is that's still going to be our left-hand side.
  • 1:01 - 1:05
    Then we want to take whatever jstate had before the dot,
  • 1:05 - 1:09
    and that corresponds to all of this stuff that I've sort of left out here,
  • 1:09 - 1:15
    but then add on x, because we're shifting over x, conceptually, as we do the reduction.
  • 1:15 - 1:20
    Now we want to take everything jstate had after the dot, except we want to remove the x,
  • 1:20 - 1:23
    because we shifted the red dot over it.
  • 1:23 - 1:27
    Everything jstate had after the dot was j-state bracket 2.
  • 1:27 - 1:30
    and we're going to do range selection on that to get rid of the first element.
  • 1:30 - 1:33
    Then it looks like I can't preplan.
  • 1:33 - 1:37
    Whatever this k value was, we're just going to leave it alone.
  • 1:37 - 1:40
    Jstate 3 corresponds to k.
  • 1:40 - 1:45
    However, we only want to do this if certain conditions hold.
  • 1:45 - 1:48
    First, cd has to be the empty list which corresponds
  • 1:48 - 1:51
    to this red dot being as far to the right as possible.
  • 1:51 - 1:56
    The second thing we have to check for is that this x and that one match exactly.
  • 1:56 - 2:03
    This x was the first element of jstate 0 1 2, so I'll check to make sure that jstate 2 is not empty.
  • 2:03 - 2:07
    If this red dot were all the way to the right, there would be nothing there to check for.
  • 2:07 - 2:13
    If it's not empty, I'm going to check its first character and make sure that matches up with our x.
  • 2:13 -
    Those are all of the states we bring in as part of doing reductions.
Title:
04-43 Writing Reductions Solution
Description:

dummy description

more » « less
Video Language:
English
Team:
Udacity
Project:
CS262 - Programming Languages
Duration:
02:17
Amara Bot added a translation

English subtitles

Revisions