Return to Video

06ps-06 Boggle Solution

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

English subtitles

Revisions