YouTube

Got a YouTube account?

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

English subtitles

← 03x-02 Maximum Solution

dummy description

Get Embed Code
3 Languages

Showing Revision 2 created 10/24/2012 by Amara Bot.

  1. So here, our goal is to find the element of the non-empty list "l" that maximizes
  2. the return value of f.
  3. and I'm just going to call this function findmax f of l.
  4. Conceptually, one way to do this is to keep track of the best thing you've seen so far,
  5. and then just walk over the list and notice if you ever see anything better.
  6. I'm going to make 2 descriptive variable names--the best element I've seen so far
  7. and the best f value I've seen so far,
  8. and then what I want to do is iterate over all the possible elements in the list
  9. without walking off the end,
  10. and I'll pull out that element and call the function f on it.
  11. If we either haven't seen anything good yet, or what we just saw is better than
  12. the best thing we've seen previously, congratulations!
  13. You, the current element, are promoted to the new champion,
  14. and then eventually when we're done,
  15. we just return the best element so far.
  16. Now I personally recommend making small test cases at the beginning,
  17. just so that we can get a feel for how it's going before we move to that big
  18. Barbara Kingsolver thing.
  19. Well, let's see if I managed to write this Python program without any mistakes.
  20. This is actually not obvious.
  21. Oh! There is a mistake.
  22. It returned bestelementsofar.
  23. Here's the error at the bottom--unindent does not match any outer indentation level.
  24. This is on line 13.
  25. Let's scroll back up and actually, I think, they are right.
  26. I needed 1 more space there.
  27. I don't know if you could see this before.
  28. For some reason, it hadn't tabbed over the whole way, but now I've made it tab
  29. over the whole way. So let's try again.
  30. Ah! And now it returns "quick," which is what we expected.
  31. That's the element of this list with the greatest length.
  32. Let's try another test.
  33. Try 5, -6, 3, and 2, and this time we want to find the element with the greatest absolute value.
  34. That should be -6.
  35. And it is! Wow!
  36. Looks like findmax is really working out well, except that it's totally not.
  37. There's actually a bug in this implementation.
  38. So the test that I've been making--they're all in sort of random order.
  39. You really want to try all the corner cases, and for something that takes a list as input,
  40. corner cases to consider are in order, in reverse order, and random.
  41. But we tried 2 tests, but they were both sort of in random order,
  42. and when you're testing a program that involves lists,
  43. you want to try in order, reverse order, and also random.
  44. So let's try this on reverse order, and see if it gets the right answer.
  45. Should be 4, and in fact, it is! Excellent.
  46. Now let's try it on in order and see if it gets the right answer.
  47. Should be -4--oh! It is -3. That's not the right answer. Hmm. What do we do?
  48. There's a bug in our code somewhere, and we may not know where.
  49. One of the first approaches to figuring out what's going on is called
  50. print statement debugging.
  51. So here what I'm doing is changing my program so that everytime we enter this loop,
  52. we print out what the value of "i" is just to make sure that things are on track.
  53. Here we're trying to print out the element and the f_value.
  54. Let's go see if I can even add print debugging without something going wrong.
  55. Alright, this looks pretty good.
  56. So we start out when i is 0 and the element there is 1 and the f_value is 1. Looking good.
  57. Then i is 1, the element is 2, f_value is 2. Good.
  58. And then i is 2, the element is 3, the f_value is 3.
  59. Well, this convinces me that we're actually calling the absolute value,
  60. but the thing I was expecting to see was -4, and we never seem to get there.
  61. So this suggests to me that i isn't getting high enough.
  62. Well, we know that i is going over every element in this range,
  63. so let's print that out to gain some understanding--
  64. range(len(l)-1).
  65. So now here at the beginning, it tells us that i is only ranging over 0, 1, and 2,
  66. but we really want it to range over 0, 1, 2, 3,
  67. and in fact, we can make this even super obvious.
  68. Let's make an even simpler list that we're going to fail at.
  69. Now the list and the element indices are the same.
  70. We really want to get out the answer 3,
  71. but if we look down here,
  72. i only ranges over 0, 1, 2. 0, 0, 0. 1, 1, 1. 2, 2, 2.
  73. 2 is the best so we return it.
  74. So we're not getting to this last element.
  75. So there must be something wrong with this set,
  76. and I'm guessing, since we're missing the last element,
  77. that this -1--we don't really need to be subtracting 1.
  78. Now many people are often tempted to subtract 1 because Python lists start at 0,
  79. and you don't want to walk over the end.
  80. You will just print out range 4 to satisfy ourselves that it's 0, 1, 2, 3.
  81. Yep, so range(4)--0, 1, 2, 3.
  82. Now i ranges over 0, 1, 2, 3, and now we're getting the answer we expect.
  83. So now let's go back to the problem we were actually given,
  84. ["Barbara", "Kingsolver", "Wrote", "The", "Poisonwood", "Bible"],
  85. and hopefully, will get either Kingsolver or Poisonwood out,
  86. assuming I can count.
  87. Barbara is 7. Kingsolver is 10. Wrote is 5. The is 3. Poisonwood is 10.
  88. We end up with Kingsolver at the end of the day, which is a perfectly acceptable answer.
  89. But we've got all of this print debugging, and if the problem doesn't call for that,
  90. we should typically remove it before submitting, lest it be counted as part of our output
  91. and cause us to get the problem wrong.
  92. Now we just return Kingsolver.