YouTube

Got a YouTube account?

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

English subtitles

← 06ps-06 Boggle Solution

Get Embed Code
1 Language

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

  1. Here's my answer.
  2. I chose to do it as a single function, which has an embedded function that it calls.
  3. There are two parts to this. We have to first iterate over all the squares in the board.
  4. Then for each of the squares of the board, we want to find all the paths that generate words
  5. and follow all possible paths but cut them off when we have to stop.
  6. Here I said we can enumerate over the locations and the letters that are in the board,
  7. enumerate over them if the letter is not a border character,
  8. then we want to extend the path starting with that letter and that location.
  9. Extend_path says I have a prefix so far, which may or may not be a word,
  10. and I have a path where path is defined as a list of locations that I've visited so far,
  11. and I need that because I can't have a path circle back on itself.
  12. I can't use a location twice, so I need to know where I've been before.
  13. This is similar to the structure of find_words,
  14. but it's constrained to looking on the board through the neighbors.
  15. So what do I do?
  16. I say if the prefix is in the words, I've already found a word,
  17. and the length of that prefix is greater than the minimum length that I'm looking for,
  18. then I add it to the results.
  19. Here that won't have happened because I'm just looking at the first letter--
  20. say the letter P in location i.
  21. That's not going to be a word. It's not going to be greater than the min length, so I keep going.
  22. If the prefix is in my set of prefixes, then I look for every neighboring square j,
  23. which is a neighbor of the last element of my path,
  24. so my path is going to be I start in this location, go to the next location,
  25. go to the next location.
  26. The last element of the path is where I was last.
  27. I want to expand out from there to all the neighbors.
  28. If that j is not in the path, if I haven't circled back yet,
  29. and if the contents of that j is not a border square, if it is a valid letter,
  30. then I just extend the path. I add that letter onto the prefix.
  31. I add that location onto the path and continue, recursively call,
  32. and eventually I'll add all the possible words.
  33. Now, part of the Zen of Python is that flat is better than nested.
  34. Why did I nest here? Well, it's a judgement call.
  35. You certainly could have pulled this out, but if I did pull it out, I would need to pass in
  36. this parameter N, the board, and the result.
  37. There'd be three more parameters that I'd have to pass in,
  38. and I just though it seemed a little bit simpler to only have to call it with two--here and here--
  39. and only receive two here, rather than add in those three additional arguments.
  40. I guess I should say because extend_path is only seven lines long,
  41. I felt it was justified to have it be nested.
  42. If it grew much more than 10 lines, then I'd be very reluctant to have it be nested.
  43. I would probably pull it out.