Beefy Boxes and Bandwidth Generously Provided by pair Networks
Perl Monk, Perl Meditation
 
PerlMonks  

comment on

( [id://3333]=superdoc: print w/replies, xml ) Need Help??
My fellow monks,
I know this smells like homework, but I assure you, it is not.

First, as to what prompts my question: My 7 year old daughter has been turned on to the old Parker Brothers game 'Boggle'. She absolutely LOVES it. For those of you who don't know the game, its quite simple: 16 cubes with letters on each side are arranged into a 4x4 grid of letters from which you need to find words. You have 3 minutes to find as many 3 to 6 letter words of as you can. The rules are simple: 1) the words are created from sequences of adjacent letters (including diagonal), 2) the same position cannot be used more than once in the same word.

So, being the wonderful father that I try to be, I thought 'hmm, I'll program it so she can play it on the computer.' Generating the 16 letters from the actual cube values and arranging them into a 4x4 grid was trivially easy. It took like 5 minutes.

Now, for the vocabulary-building value of the game, I thought it would be cool to list all the words that actually exist. That is where I am stuck. In order to do this I need to generate all paths of lengths 3 to 6 starting with each cube position. I have the grid represented as an adjacency list and I know how to use depth first search to find paths from one node to another, but I am struggling to find a way to use DFS to generate all valid paths of length n, regardless of what the final node is. I would show you what I have but it is less than useful. It doesn't even come close to working.

The numbered grid looks like this:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
The list looks like this:
my %adjacency_list = ( 1 => [2,5,6], 2 => [1,3,5,6,7], 3 => [2,4,6,7,8], 4 => [3,7,8], 5 => [1,2,6,9,10], 6 => [1,2,3,5,7,9,10,11], 7 => [2,3,4,6,8,10,11,12], 8 => [3,4,7,11,12], 9 => [5,6,10,13,14], 10 => [5,6,7,9,11,13,14,15], 11 => [6,7,8,10,12,14,15,16], 12 => [7,8,11,15,16], 13 => [9,10,14], 14 => [9,10,11,13,15], 15 => [10,11,12,14,16], 16 => [11,12,15] );
what I need is the list of paths of length 3 to 6
1,2,3 1,2,5 1,2,6 1,2,7 1,5,2 1,5,6 ... 16,15,14,13,10,11


After I have the list of paths generated it will be trivial to substitute the appropriate letters and check the possiblities against a a database of age appropriate words.

As always any assistance you can provide will be greatly appreciated by me and my daughter.

davidj

In reply to find all paths of length n in a graph by davidj

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post; it's "PerlMonks-approved HTML":



  • Are you posting in the right place? Check out Where do I post X? to know for sure.
  • Posts may use any of the Perl Monks Approved HTML tags. Currently these include the following:
    <code> <a> <b> <big> <blockquote> <br /> <dd> <dl> <dt> <em> <font> <h1> <h2> <h3> <h4> <h5> <h6> <hr /> <i> <li> <nbsp> <ol> <p> <small> <strike> <strong> <sub> <sup> <table> <td> <th> <tr> <tt> <u> <ul>
  • Snippets of code should be wrapped in <code> tags not <pre> tags. In fact, <pre> tags should generally be avoided. If they must be used, extreme care should be taken to ensure that their contents do not have long lines (<70 chars), in order to prevent horizontal scrolling (and possible janitor intervention).
  • Want more info? How to link or How to display code and escape characters are good places to start.
Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?
Chatterbox?
and the web crawler heard nothing...

How do I use this?Last hourOther CB clients
Other Users?
Others drinking their drinks and smoking their pipes about the Monastery: (3)
As of 2024-03-29 06:52 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found