YouTube

Got a YouTube account?

New: enable viewer-created translations and captions on your YouTube channel!

English subtitles

← 02-27 Eliminating Redundancy

Get Embed Code
1 Language

Showing Revision 1 created 04/23/2012 by Amara Bot.

  1. [Norvig] I wrote this version of the function,
  2. and as soon as I wrote it, as I was recording this video I set it running.
  3. And you know what? It's still running. It hasn't completed yet.
  4. I've got to admit I've done this before, so I have an idea of how long it's going to take.
  5. But we're in a race with it.
  6. Let's see if before it completes--
  7. we know it's going to take on the order of an hour or so--
  8. can we write a program that's better and faster
  9. and maybe even though that program's got a head start,
  10. we can catch up with it and finish first?
  11. The problem with this program is it goes through all this work
  12. to try all the 5 factorial to the 5th combinations
  13. and then they get ruled out really early.
  14. And some of the combinations, it seems silly that we're bothering with them.
  15. So if the Englishman is not red, we should know that
  16. by the time we've got through the second set of assignments here.
  17. Here we've assigned red to some house and Englishman to some house.
  18. If we didn't assign them to the same house,
  19. why are we bothering to go through all the possibilities for the other properties?
  20. And so what we could do is move this constraint up to the earliest time
  21. in which both Englishman and red are defined, so there.
  22. Now I've moved it up, and now if Englishman is red is false,
  23. then we don't even have to bother to go through all 3 of these loops.
  24. So we're going to eliminate a lot of work in just that 1 clause.
  25. Now let's consider another of the constraints.
  26. Let's look at immediate right of green and ivory.
  27. Can we move that up? And where can we move it up to?
  28. Can we move imright(green, ivory) up to here, here, here, or here?