Beefy Boxes and Bandwidth Generously Provided by pair Networks
Problems? Is your data what you think it is?
 
PerlMonks  

Re^2: Improve My FaceBook Scramble Solver

by Limbic~Region (Chancellor)
on Aug 18, 2009 at 13:02 UTC ( #789449=note: print w/ replies, xml ) Need Help??


in reply to Re: Improve My FaceBook Scramble Solver
in thread Improve My FaceBook Scramble Solver

tilly,
Thank you for your feedback. You ask a number of questions and the answer to them is almost all of them is the same. I was lazy and in a hurry.

Why do you have the ability to store multiple words with the exact same characters?

Primarily because I was lazy and copied my own code from Re^3: One for the weekend: challenge. There it made sense and here it doesn't. While it is a cardinal sin to assume your input will be what you expect, the %seen hash should prevent duplicate solutions.

A stylistic issue. I'd recursively traverse the character to add words. Using eval there is an error-prone sledgehammer. What happens with words that include single quotes? You're trusting your input in a way that I avoid.

Well, we have had this conversation in the past. My brain just doesn't seem to think recursively without a lot of effort on my part. Even if I hadn't borrowed from a previous solution and avoided the evil eval, I still would have iterated. Regarding the evil eval sledgehammer: Any word containing anything other than lower case chars is skipped but I realize that it makes the code fragile and prone to breaking if requirements change. The real reason is laziness again. In the original solution, as with this solution, runtime speed was an issue and it took longer without the evil eval. In this case it is a moot point because build_db.pl runs independently of the main program so speed was not a factor and could have been avoided.

One minor note. Instead of a breadth-first search, my natural inclination would be a depth-first recursive search...

Yes, but my natural inclination is to avoid anything recursive with a very long pole. I have done a DFS iteratively and it is ugly. I was more interested in the results than in maintainable robust code. I spent far more time trying to compile a word list than the few minutes it took me to update a previous solution.

Thank you again for your feedback. I was able to buy an eBook containing the TWL ($0.99 + $0.40 tax) and have the solution I want without needing to change the algorithm. Currently, I am eating 12 seconds of the 3 minutes. This includes:

  1. Switching from the browser window to the command window
  2. Typing the 25 letters in the grid and hitting return
  3. Switching back to the browser window
The majority of that time is spent correctly typing the 25 letters and the artificial 1 second sleep delay to ensure I can switch to the browser window before the code starts generating results.

Cheers - L~R


Comment on Re^2: Improve My FaceBook Scramble Solver
Re^3: Improve My FaceBook Scramble Solver
by tilly (Archbishop) on Aug 18, 2009 at 19:27 UTC
    I'm puzzled by your comment that DFS iteratively is ugly. The only difference between a DFS and BFS written iteratively is whether you push/shift to @work or push/pop. In fact now that I read more carefully you actually did a DFS, not a BFS, and I'm embarrassed to have not noticed it. (I got it wrong because I was skimming the first time, and I only write the iterative form for a BFS.)

    I'd also recommend that you put some work pushing past your recursion block. Recursion is a very useful tool, and you're shortchanging yourself by not having it in your toolbox. It is a different mode of thinking, but it isn't particularly hard. However you'll need to force yourself to find opportunities to try it until it kind of "clicks". After it clicks, then you'll have a new tool in your toolbox. :-)

    To write a recursive function I follow the following steps:

    1. Write a function name that says it will solve the problem that I want solved.
    2. Write the main recursive step where I somehow reduce the problem to a simpler problem.
    3. Think through all of the possible "simplest problems" that I could run into and write code for those cases. At this stage I'll add dispatch logic if I need to.
    4. Test my solution. Oversights are easy, and so it is worth testing when the code is fresh in my mind and fixes are easiest to make.

    About the rest, I well understand reusing snippets you have lying around. For quick one-off programs that is a good approach. But if the one-off starts to become regularly used or to grow, then be aggressive on making it maintainable. The benefits of being maintainable tend to be so lopsided that it becomes a reflex for good programmers. But still there is an appropriate balance to maintain, and I think you're maintaining it.

      tilly,
      I'm puzzled by your comment that DFS iteratively is ugly.

      Which was made in reference to my comment "I have done a DFS iteratively and it is ugly." That should probably have been two distinct statements. "What I have done is a DFS." and "I think it is ugly compared to the recursive alternatives". In my opinion, the situation is reversed in a BFS (recursive being the ugly one). I go on to indicate that my motivation was producing results rather than maintainable code. Perhaps it is just personal aesthetics but I don't find while (@work) { ... } very beautiful. It is just more natural to me.

      I'd also recommend that you put some work pushing past your recursion block.

      I agree and have dabbled with it off and on. I don't have any problem understanding other people's recursive routines but producing them myself doesn't seem natural. I recently wrote a recursive sub to find the root node of child in a tree by following the parent all the way to the top. Believe it or not, it was harder for me to write something that simple than it was for me to think about the iterative form. Again, thank you for the feedback and encouragement. I will continue to plug away at it.

      Cheers - L~R

      Check out following code ( this removes the problem of slowing down)
      #open(F,"C:\\Users\\awanchoo\\Documents\\web2.txt"); open(F,"D:\\DICT.txt"); my %dict; my %check_2; my %check_3; my %check_6; my %check_9; my %FOUND; my $startx,$starty; my $size =5; my $MAX=15; my @found_sizes; my @found_ref; while(<F>) { my $c1,$c2,$c3; #$c1=substr($_,0,1); #$c2=substr($_,1,1); #$c3=substr($_,2,1); chomp($_); #my $len=length($_); #print $_." ".$len." ".$c1.$c2.$c3."\n"; $dict{$_}="Y"; $check_2{substr($_,0,2)}=Y; $check_3{substr($_,0,3)}=Y; $check_6{substr($_,0,6)}=Y; $check_9{substr($_,0,9)}=Y; #push(dict{$c1}{$c2}{$c3}; } #foreach my $temp ( keys %full) #{ print $temp."\n"; #} while (<STDIN>) { for (my $i=0;$i<20;$i++) { $found_sizes[$i]=0; } my @arr,@bin; my $i=0,$j=0; #Reading input letters open(ip,"d:/ip.txt"); open(op,">d:/op.txt"); while(<ip>) { chomp($_); $arr[$i][0]=substr($_,0,1); $arr[$i][1]=substr($_,1,1); $arr[$i][2]=substr($_,2,1); $arr[$i][3]=substr($_,3,1); $arr[$i][4]=substr($_,4,1); $i++; #print $_." ".$i." ".$arr[$i-1][3]."\n"; } #Reset the bin reset_bin(\@bin,$size); # Start the process with each letter as starting of a string $i=0;$j=0; while($i<$size) { $j=0; while($j<$size) { $startx=$i; $starty=$j; #print " \n Starting word with $arr[$i][$j] ($i,$j) "; $bin[$i][$j]="1"; move(\@arr,$i,$j,$arr[$i][$j],\@bin); # start maing word +from arr(i,j) #print_array(\@bin,$size); $bin[$i][$j]="0";#reset_bin(\@bin,$size); $j++; } print "\n"; $i++; } foreach my $word (keys %FOUND) { my $len=length($word); $found_ref[$len]->[$found_sizes[$len]]=$word; #print "\n:".$found_ref[$len]->[$found_sizes[$len]].":".$word. +" l; $found_sizes[$len]++; } for(my $i=19;$i>=0;$i--) { print op "\n Word length $i "; for (my $j=0;$j <$found_sizes[$i];$j++) { print op "\n".$found_ref[$i]->[$j]; } } close(ip); close(op); } print %check; sub move { my $arr_ref=$_[0]; my $row=$_[1]; my $col=$_[2]; my $str=$_[3]; my $bin_ref=$_[4]; #print "\n In Move str= $str"; my $str_len=length($str); if($startx==1 && $starty==3 ) { #print "\n Word NOT found : $str $dict{$str}; ". $dict{"t +iles"}." ".$check_3{"til"}."($startx,$starty) to ($row,$col)"; } if($str_len==2 && !exists($check_2{$str})) { #print "\n Word doest exist starting with $str "; return ; # word doest exist starting with these first two +letters } if($str_len==3 && !exists($check_3{$str}) ) { #print "\n Word doest exist starting with $str "; return ; # word doest exist starting with these first thre +e letters } if($str_len==6 && !exists($check_6{$str})) { #print "\n Word doest exist starting with $str "; return ; # word doest exist starting with these first two +letters } if($str_len==9 && !exists($check_9{$str}) ) { #print "\n Word doest exist starting with $str "; return ; # word doest exist starting with these first thre +e letters } if($str_len >=3 && exists($dict{$str})) { #print "\n Word found : $str $dict{$str}; ". $dict{"tiles"}." + ".$check_3{"til"}."($startx,$starty) to ($row,$col) : $arr_ref->[$st +artx][$starty]"; $FOUND{$str}="1";#push(@FOUND,$str); # word found in dict #print_array($bin_ref,$size); } if($str_len > $MAX) { return ; } my $i=$row-1; my $j=$col-1; #print_array($bin_ref,$size); # scanning through neighbours while($i < $row+2) { #print " i=$i "; $j=$col-1; if($i >=0 && $i < $size) { while($j <$col+2) { #print " j=$j "; if($j>=0 && $j <$size) { if($bin_ref->[$i][$j]=='0') { my $temp_str; $temp_str=$str; $bin_ref->[$i][$j]="1"; $str=$str.$arr_ref->[$i][$j]; ###a +dding new elemet to string move($arr_ref,$i,$j,$str,$bin_ref) +; $bin_ref->[$i][$j]="0"; $str=$temp_str; } } $j++; } } $i++; } return 0; } sub reset_bin { $bin_ref=$_[0]; $s=$_[1]; for(my $i=0;$i<$s;$i++) { for(my $j=0;$j<$s;$j++) { $bin_ref->[$i][$j]="0"; } } } sub copy_array { $src=$_[1]; $des=$_[0]; $s=$_[2]; for(my $i=0;$i<$s;$i++) { for(my $j=0;$j<$s;$j++) { $des->[$i][$j]=$src->[$i][$j]; } } } sub print_array { print "\n Print Array : "; $arr=$_[0]; $s=$_[1]; for(my $i=0;$i<$s;$i++) { print("\n"); for(my $j=0;$j<$s;$j++) { print $arr->[$i][$j]."."; } } }

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://789449]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others meditating upon the Monastery: (3)
As of 2014-12-29 01:05 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    Is guessing a good strategy for surviving in the IT business?





    Results (183 votes), past polls