Not that there's anything terribly interesting in this, but I'd like to increase
the volume on this list, and try to get people in the habit of explaining what
they are doing. Here is an explanation of my boggle solution:
#!perl -p
[EMAIL PROTECTED],32|$;++/4+$;while$_=pop}
sub b{
my($p,$n,@L)[EMAIL PROTECTED];
!$n|!!grep$p!~$_&b("$_ $p",@L)&($_-$p)=~/$_|\b[1456]$/,@$n
}
$_ x=b/^|./g
I started by using -p, so I also had to destroy @ARGV. I did this in the INIT
block, also setting up the grid. For each letter, I push an incremented number
onto the array @$_, which I believe is (in this case) the same as @{"$_"} -
pretty horrible stuff.
Instead of 1..16, I get 1,2,3,4, 6,7,8,9, 11,12,13,14, 16,17,18,19. That way I
can look for adjacent letters by using the a difference in number. 8 has
neighbours 2,3,4 above, 7 and 8 on the same row, and 12,13 and 14 below. For 4
which is on an edge, I _can_ look for 5, but it will never exist. I also ended
up bit-oring this with 32 to make them all two digit integers, for better
checking later. This should all become clear.
$_ x=b/^|./g
If the sub b returns 1, the word gets printed once, and not if false. So sub b
has to test for boggleability. I think most people used a recursive sub like
this to test, and I'm sure the people who didn't understand the principle :) so
I won't get into that.
The 'three' things I extract from the arguments passed to the sub are:
$p - the list of previous letters used (empty for the first pass [match on ^])
$n - the current letter being checked (the first letter for the first pass, etc)
@L - the list of following letters.
These are all 'my'ed because it's a recursive sub, and not restricting the scope
is bad.
The big line is:
!$n|!!grep$p!~$_&b("$_ $p",@L)&($_-$p)=~/$_|\b[1456]$/,@$n
so the first thing we see is that the sub returns true if $n doesn't exist. That
means we've checked all the letters, and it works out fine.
The grep is on the array of positions for each letter. So if $n is 'j', this
greps through all the positions where 'j' occurs. There are three tests, all of
which have to be true:
$p!~$_ that the position hasn't been used previously. This is why I had bitored
with 32. First to get an integer and secondly to make it two digits. If it
wasn't two digits, I'd have had to test for /\b$_\b/, or else 10 would have
matched 1, giving me a false negative.
($_-$p)=~/$_|\b[1456]$/ that the number/letter is adjacent. If there is a $p, $_
- $p has to be -6,-5,-4,-1,1,4,5 or 6. The \b$ bit just rules out false
positives on 11, 14 or whatever, and to account for the -ve numbers. The $_ is
in there because for the first check there is no $p, so $_-$p == $_. If the
positions weren't integers, this would have been much messier.
b("$_ $p",@L) and rest of the word is boggleable by the same rules. $p is "$_
$p" for the next pass, and the first letter in @L becomes $n there. (of course
int("10 11 16") is 10, so the subtraction for the adjacent test is fine).
I had to !! the grep in case there were multiple solutions for a word, so that
it didn't get printed out multiple times.
(replacing
$p!~$_&b("$_ $p",@L)&($_-$p)=~/$_|\b[1456]$/
with
$p!~$_&($_-$p)=~/$_|\b[1456]$/&&b("$_ $p",@L)
makes the whole thing _much_ faster, but at the expense of one character - no
thanks!)
I hope that seems relatively straightforward to everyone.
I am humbled by reading ton's explanation, but not quite so humble as to not
post this ;)
Jasper
--
Kirk: Spock, the women on your planet are logical.
No other planet in the galaxy can make that claim.
