Beefy Boxes and Bandwidth Generously Provided by pair Networks
There's more than one way to do things
 
PerlMonks  

A Semi-automatic word search solver

by The Hindmost (Scribe)
on Sep 25, 2009 at 13:47 UTC ( [id://797510]=CUFP: print w/replies, xml ) Need Help??

Note: The program described below has been updated since this version was released, the newer version can be found here: The update, as promised, or alternatively below.

Description:

The code below is for a semi-automatic word search solver, that uses a recursive function to search a multi-dimension array containing the puzzle for the word that the user asks for.

The program is semi-autonomous, in that the search itself is carried out automatically, but the puzzle is (for the moment) hard-coded, and the user must enter each word that they want to search for one-by-one.

Interface

The interface is a simplistic text-based one, the user enters the word that they want to search for, and the program responds with a set of coordinates for the start and end positions of the word being searched for, or 'NO RESULT' if the word can't be found.

The only command available to the user apart from the search ability is the '#quit' command which exits the program.

Considerations:

The program relies on the assumption that the dimensions of the grid to be searched are equivalent, i.e. rows == cols

Planned Improvements:

1.) The option for the user to enter in the puzzle data 'on the fly'

2.) Removal of the final global variable '@end'

3.) The ability for the user to define a list of values to search for

Program Code:

#!/usr/bin/perl # wordSearchSolve.pl # Program to solve a word search puzzle semi-automatically. # Define the puzzle to be searched as '@puzzle', see the example below +. # # Christopher Dykes (2009-09-25) - (v1.0) #Enable the following packages: use strict; #Enable strict syntax checking use warnings; #Enable diagnostic warnings #Declare global variables: our @end = undef; #The location of the end of the word #Declare local variables: my $done = 0; #Whether we're finished or not my @start = undef; #The location of the start of the puzzle my @puzzle = ( ['r','e','l','a','e','d','b','y'], ['e','s','c','r','e','e','n','t'], ['m','i','o','e','i','s','h','l'], ['i','s','l','a','t','e','r','a'], ['t','n','u','r','c','n','n','u'], ['r','g','m','u','a','i','h','s'], ['o','u','b','m','t','h','a','a'], ['m','e','o','a','n','c','c','c'] ); #Display the header: print "Wordsearch Solver:\n\n"; print "Enter the term to search for, enter '#quit' to exit\n\n"; #Allow the user to search while(!$done) { my($word, $found); @end = undef; #Get the word from the user: print "> "; chomp($word = <STDIN>); $done++ if($word eq "#quit"); unless($done) { my($i, $j, $k); print $word, "\t= "; my @word = split(//, $word); for($i = 0, $found = 0; $i <= $#puzzle && !$found; $i++) #R +ow loop { for($j = 0; $j <= $#puzzle && !$found; $j++) #Col l +oop { for(my $k = 0; $k < 8 && !$found; $k++) #Dir lo +op { my @gen = (""); $found = &search($k, $i, $j, \@puzzle, \@word, @ge +n); } } } print "($i,$j) - ($end[0],$end[1])\n" if($found); print "NO RESULT\n" if(!$found); } } #Subroutines begin here: sub search ($ $ $ $ $ @) #Performs a recursive search across the pu +zzle { #Declare local variables: my($dir, $row, $col, $puzRef, $wrdRef, @gen) = @_; my @puzzle = @{$puzRef}; my @word = @{$wrdRef}; ($end[0], $end[1]) = (($row + 1), ($col + 1)); #Set our end loc +ation return 0 if($puzzle[$row][$col] ne $word[$#gen]); return 1 if($#word == $#gen); #Decide what to do: $row++ if(($dir == 0 || $dir == 4 || $dir == 5) && $row < $#puzzle +); $row-- if(($dir == 1 || $dir == 6 || $dir == 7) && $row > 0); $col++ if(($dir == 3 || $dir == 5 || $dir == 7) && $col < $#puzzle +); $col-- if(($dir == 2 || $dir == 4 || $dir == 6) && $col > 0); #Do the useful stuff: push(@gen, $puzzle[$row][$col]); return 1 if(&search($dir, $row, $col, \@puzzle, \@word, @gen)) || +return 0; }

Replies are listed 'Best First'.
Re: A Semi-automatic word search solver
by toolic (Bishop) on Sep 25, 2009 at 14:21 UTC
    fun++

    You could use qw to cut down on typing and reduce clutter:

    my @puzzle = ( [qw(r e l a e d b y)], [qw(e s c r e e n t)], [qw(m i o e i s h l)], [qw(i s l a t e r a)], [qw(t n u r c n n u)], [qw(r g m u a i h s)], [qw(o u b m t h a a)], [qw(m e o a n c c c)] );
    our @end = undef;
    In this case, you could use my instead of our, and there is no need for undef
    my @end;
      Glad you liked it, and thanks for those bits of advice.
Re: A Semi-automatic word search solver
by Limbic~Region (Chancellor) on Sep 25, 2009 at 16:35 UTC
    The Hindmost,
    You could easily remove the hard coded puzzle by reading from a file or by using the __DATA__ section. I might be inclined to write my own take on the problem if you are interested??? One thing you should consider is offering command line options. Not all word search puzzles are created equal. For instance - some only have words going in straight lines while others allow snakes. Also consider that a word may be contained within a longer word - most puzzles that I have seen disallow this.

    Cheers - L~R

      Hey, thanks for the comments, naturally I'd be interested in seeing another take at handling the problem, after all TIMTOWTDI. I'm working on an update for the program at the moment, and using a file to load the puzzle, and having command line options are both ideas that will make it in.
Re: A Semi-automatic word search solver
by CountZero (Bishop) on Sep 26, 2009 at 07:03 UTC
    Here is a small subroutine (really only one line long) to make the building of your @puzzle array even easier.
    use strict; use warnings; use Data::Dumper; my @puzzle = qw/abcde fghij klmno pqrst uvwxy/; @puzzle = make_puzzle(@puzzle); print Dumper(\@puzzle); sub make_puzzle{ return map{[split //, $_]} @_; }
    One question if I may: Why are you using subroutine prototypes in your search subroutine?

    CountZero

    A program should be light and agile, its subroutines connected like a string of pearls. The spirit and intent of the program should be retained throughout. There should be neither too little or too much, neither needless loops nor useless variables, neither lack of structure nor overwhelming rigidity." - The Tao of Programming, 4.1 - Geoffrey James

      Thanks for the subroutine, I think I will use that as part of the update I'm planning. As for using a prototype on the subroutine, I've always done it that way, but if this is considered incorrect or foolish, please do tell me.
        Prototypes in Perl are very special. They are not --as many people expect-- a tool to check at compile-time or even run-time wether the parameters of your subroutine call are correct. Have a look at Gratuitous use of Perl Prototypes, it explains clearly why Perl "prototypes" are totally different from (for example) C "prototypes".

        CountZero

        A program should be light and agile, its subroutines connected like a string of pearls. The spirit and intent of the program should be retained throughout. There should be neither too little or too much, neither needless loops nor useless variables, neither lack of structure nor overwhelming rigidity." - The Tao of Programming, 4.1 - Geoffrey James

The update, as promised
by The Hindmost (Scribe) on Oct 19, 2009 at 20:37 UTC
    Sorry about the massive delay in finishing and uploading the revised version, University work and finding a place to live next year caught up with me.

    Description:

    The major update to the program is the use of an external file to load the puzzle to be searched, in addition to this many of the improvements suggested in the other comments have been included. An additional change is the ability to load a puzzle file from inside the program and to access internal help from the program.

    Interface:

    The interface remains essentially the same as before, with only the addition of several new commands outlined below:
    #help - displays the list of internal commands and what they do<
    #newpuzzle FILENAME - loads a new puzzle from the file
    #quit - Same as in the previous version.

    In addition, the program now accepts arguments from the command line, the most important of these (and the only required one) is -f to load the file to be searched.

    Note: if this is forgotten, the program will prompt the user to supply a file.

    Planned Improvements:

    1.) Moving the help data over to POD as suggested in the Getopt::Long documentation,

    2.) Allowing the program to remember the location of previously searched for words, to cut down on search time (possibly using Memoization),

    3.) Allowing the user to supply a list of the words in the word search, possibly combining this with the puzzle data file

    Program Code:

    #!/usr/bin/perl # wordSearchSolve.pl # Program to solve a word search puzzle semi-automatically. # # With thanks to toolic, Limbic~Region and Count Zero of perlmonks.org + for # suggesting several improvements. # # Christopher Dykes (2009-10-19) - (v2.2) #Enable the following packages: use strict; #Enable strict syntax checking use warnings; #Enable diagnostic warnings use Getopt::Long; #Enable command line option parsing #Define constants: use constant 'VERSION' => 2.2; #Declare local variables: my($i, $j, $k, $word, $found); #Various control variables my $done = 0; #Whether we're finished or not my(@start, @end); #The start and end locations of the word my @puzzle; #The puzzle to be searched #Parse command line options: my($file, $help, $version); #Available command line options GetOptions('file=s' => \$file, 'help' => \$help, 'version' => \$versio +n); &help if($help); #Display the help message &version if($version); #Display the version details @puzzle = @{&puzzleGet($file)} if($file); #Open our file if we h +ave one exit if($help || $version); if(!$file) #Get a file from the user if they haven't supplied one { my $check = " "; while($check ne "y") { print "WARNING: No File supplied, supply now? (y/n) "; $check = lc(<STDIN>); chomp $check; exit if($check eq "n"); } print "Enter file name:\t"; $file = <STDIN>; @puzzle = @{&puzzleGet($file)}; } #Display the header: print "Wordsearch Solver (v", VERSION, "):\n\n"; print "Enter the term to search for, enter '#quit' to exit "; print "and #help for assistance\n\n"; #Allow the user to search: while(!$done) { print "> "; chomp($word = <STDIN>); #Get the word from the u +ser my @chars = split(//, $word); my @words = split(/ /, $word); if($chars[0] eq "#") { $done++ if($word eq "#quit"); &internalHelp if($word eq "#help"); if($words[0] eq "#newpuzzle") { @puzzle = @{&getPuzzle($words[1])}; } } else { print $word, "\t= "; my @word = split(//, $word); for($i = 0, $found = 0; $i < @puzzle && !$found; $i++) #Row + loop { for($j = 0; $j < @puzzle && !$found; $j++) #Col loop { for($k = 0; $k < 8 && !$found; $k++) #Dir loop { my @gen = (""); $found = &search($k, $i, $j, \@puzzle, \@word, @ge +n); } } } print "($i,$j) - ($end[0],$end[1])\n" if($found); print "NO RESULT\n" if(!$found); } } #Subroutines begin here: sub search #Performs a recursive search across the puzzle { #Declare local variables: my($dir, $row, $col, $puzRef, $wrdRef, @gen) = @_; my @puzzle = @{$puzRef}; my @word = @{$wrdRef}; ($end[0], $end[1]) = (($row + 1), ($col + 1)); #Set our end loc +ation return 0 if($puzzle[$row][$col] ne $word[$#gen]); return 1 if($#word == $#gen); #Decide what to do: $row++ if(($dir == 0 || $dir == 4 || $dir == 5) && $row < $#puzzle +); $row-- if(($dir == 1 || $dir == 6 || $dir == 7) && $row > 0); $col++ if(($dir == 3 || $dir == 5 || $dir == 7) && $col < $#puzzle +); $col-- if(($dir == 2 || $dir == 4 || $dir == 6) && $col > 0); #Do the useful stuff: push(@gen, $puzzle[$row][$col]); return 1 if(&search($dir, $row, $col, \@puzzle, \@word, @gen)) || +return 0; } sub puzzleGet { my @puzzle; open(FILEIN, "$_[0]") || die("Couldn't open file $_[0]"); while(<FILEIN>) { chomp($_); my @line = split(/ /, $_); push(@puzzle, \@line); } return \@puzzle; } sub help { print "Usage: wordSearchSolve.pl [OPTION] -f [FILENAME]\n"; print "A program to solve a word search automatically\n\n"; print "-f\t--file\t\tLoad the puzzle from this file\n"; print "-h\t--help\t\tDisplay this message\n"; print "-v\t--version\tDisplay version information\n\n"; print "Report bugs to <dykes.chris\@gmail.com>.\n"; } sub version { print "wordSearchSolve (v", VERSION, ")\n"; print "Copyright (C) 2009 Christopher Dykes.\n"; print "License GPLv3+: GNU GPL Version 3 or later <http://gnu.org/ +licenses/gpl.html>\n"; print "This is free software: you are free to change and redistrib +ute it.\n"; print "There is NO WARRANTY, to the extent permitted by law.\n\n"; print "Written by Christopher Dykes.\n"; print "With thanks to toolic, Limbic~Region and Count Zero of perl +monks.org\n"; print "for suggesting several improvements.\n"; } sub internalHelp { print "\nAvailable commands are:\n"; print "\t#help\t\tDisplay this message\n"; print "\t#newpuzzle\tLoad a new puzzle from a file\n"; print "\t#quit\t\tExit the program\n"; print "\n"; }

    The puzzle data file:

    This can be any plain text file laid out like the one below:

    r e l a e d b y e s c r e e n t m i o e i s h l i s l a t e r a t n u r c n n u r g m u a i h s o u b m t h a a m e o a n c c c
    I.e. a space between each column, and a newline between each row.
    NB: make sure there are no trailing new lines in the file.

Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: CUFP [id://797510]
Approved by toolic
Front-paged by Arunbear
help
Chatterbox?
and the web crawler heard nothing...

How do I use this?Last hourOther CB clients
Other Users?
Others learning in the Monastery: (6)
As of 2024-04-20 02:30 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found