Pff, they kept pushing me to write an explanation. Ok. Here you go.
This challenge basically asked for backtracking, and perl already has
a backtracking system: the regex engine. So my idea was to take the
boggle board as a string to match on, and rewrite the target word as a
regex and then see if it matches.
The first problem is that on the board you sometimes have to go
backward, and regexes only go forward (I really wish perl would get
variable length lookbehind). So instead I'll take repeated copies
of the board as string to match on, and jump from board to board
during the match.
The second problem is the edges. if you write a board like
a b c d
e f g h
i j k l
m n o p
as the string "abcdefghijklmnop" (x repeater), you can see that e.g.
you can move one right from c to get to d as wanted, but you also can
move one right from d to e, which is NOT a valid boggle move. So i need
to introduce extra invalid characters in between the edges. Since I'm
going to repeat the board string, it also needs an edge at the bottom
or top, otherwise you can still wrap vertically. E.g. putting the extra
protection at the front the minimum string I can use is:
XXXXXabcdXefghXijklXmnop
where the X's must be characters that can't appear in a target word.
For the front string I decided to use $~ (STDOUT) which is a bit too
long, but that's no problem, we'll just skip a bit extra when moving
from board to board. So building the string becomes:
map$~.=$_%5&&pop,0..19
which gives:
STDOUT0ponm0lkji0hgfe0dcba
notice the string is backward, but that doesn't matter, since the boggle
rules are symmetric in all directions. The extra 0 after STDOUT is again
no poblem, just a bit of extra shifting. Also notice we can play with
that 19 to make it bigger. It will just cause extra 0's at the end, which
we can again compensate for when skipping from board to board. If we make
it big enough, there will even be enough extra 0's at the end that we
don't need to use $~, since these extra end 0's already protect against
edge skips. (Unfortunately I see no way to use that fact).
Next comes building the regex. Basically we want to make a sequence
AB into:
A
(skip to the next boards left up position relative to A)
(choose to go 0, 1 or 2 steps forward)
(choose to go 0, 1 or 2 steps downward)
B
Where the () pieces can be in any order. For the given board string, that
would be:
A.{19}.{0,2}(.{5}){0,2}B
So the first (naive) version of constructing the regex if the target
string (without \n) is in $_ would be:
s/\B/.{19}.{0,2}(.{5}){0,2}/g
after which we can check if it can be made from the board is:
($~ x 16) =~ $_
We need at least as many copies of the board as there are letters in
the target string, which can have a size up to 16. I tried to use
the previous regex construction s/// as the multiplier in my final
solution, but it always turned out to be one too short, and adding 1
looses more strokes than just using a constant like 16. It would be
faster in the failure case though, since now the failing case tries
all possible starting positions).
The main problem left now is that the current method is wrong. It will
happily reuse positions already visited before, even staying put if
it likes to. Bummer.
But wait ! We can use @+ or @- to collect the positions where we matched
a letter. If we take these modulo boardstring length, we have absolute
positions on the board. So we are going to demand no repeating there.
We can use the (??{}) regex construct to conditionally construct a
regex piece that allows regex to progress beyond it or not.
The shortest way would likely be to after each matched letter in the
target word to check the current pos versus the old positions in @+ or
@-. Unfortunately I never got that working properly since there's a bug
in backtracking over (??{}) in that you get spurious undef entries which
take too much work too ignore them.
So instead i decided to only check at the total end, using this construct:
.*(??{grep$c{$_%26}++,[EMAIL PROTECTED]
For the moment assuming %c is empty, this will count how many times a
certain spot is used, and the grep will match if any spot is ever used
more than once. So you get 0 if every spot is used only once, 1 or more
otherwise. If we make sure there is a 0 somewhere after the last match
position, that will mean further match is possible and the whole regex
will match. And since 1-9 don't appear in the string, if a spot is
double used, it will not match, and the backtracking will resume. We can
get that 0 by adding an extra board or by increasing the 19 in the map
that constructs the board string.
However, %c is NOT empty. It's initialized with @+, so it actually has
all kinds of values already. We don't actually care about these unless
some keys are smaller than 26 however, since otherwise they don't
cause fake counts in $c{$_%26}++. If some positions ARE below 26, this
can however cause a spurious backtrack. But again this is no problem if
we attach an extra board. If there *is* a solution, then there will now
also be a solution starting at board 2, and in that case all values in
@+ (or @-) will be biger than 26. So everything works out.
The next problem is that now we have a runtime constructed regex
containing (??{}), which is actually not allowed unless you do
use re "eval";
which is pretty long. Checking in the source of the re pragma, we see
that what it reall does is effectively:
BEGIN { $^H |= 0x00200000 }
That's good ! We wanted a BEGIN{} or INIT{} block anyways so that we
can use the perl -p/-n option to loop over STDIN, which needs us to
empty @ARGV first. So we want that board construction map inside a
BEGIN/INIT anyways. INIT comes too late for $^H, so BEGIN it is.
And we need to set $^H to 2**21. mmm. Hey, that map returns at least 20,
so we can use things like:
BEGIN{$^H=2<<map$~.=$_%5&&pop,0..19}
Still a pity we need that constant 2. So let's abuse the fact that
a << b is the same as a << (b % int_size) on modern CPU's:
perl -wle 'print 1 << 65'
2
Perl uses C to implement <<, and C normally maps it directly to some
hardware shift instruction. These nowadays ignore all bits beyond
sizeof(int). Still, this depends on if all cpu's on which an official
perl 5.8.0 exists behave like this. It's ok for every CPU I've been able
to test it on, but I don't know if it's always so (the main missing
CPU in my survey is the M68000 family. Anyone has such a perl ?)
Since $^H actually is initialized with 256 (2**8), if we shift left by
77, we get $^H = 2**21 as it should be (the loss of the 2**8 bit seems
to cause no problems). That gives:
BEGIN{$<<=map$~.=$_%5&&pop,0..76}
The board string is now a lot longer, but that's ok, just properly
increase all later constants.
All that's left now is someminor tricks:
- We need to parenthesis so that positions are actually filled in in
@+/@-. We already need a (.{5}){0,2} construct though. We can in
fact use these parenthesis, but we will only get the end of the last
match in the repeat, so we actually should use @+ and not @-
- s/\B//g only works properly if we have a -l option. But that means we
can't handle the failing strings by printing "", we must then do a
conditional print. Too long. Instead let's set $_ to either the
original string or "". But that means that /\B/ would also match
between the \n and end of string, so we get an extra spurious ()
at the end. And if we just spiralled on the boggle board to the
center of a 3x3 block, no position of that tail () is actually valid,
so this is unacceptable. So instead go to s/./ $& /g style
constructor. It means we get an extra \n in the result though. We
can ignore that by using the x modifier to the regex.
It also means we get some extra match stuff in front of the first
letter. But that's no problem. The position of that start doesn't
get into @+, and we had an extra board in front anyways which provides
enough characters for the match.
- At the end we need to print the original string in case of a match.
But we destroyed $_ ! Fortunately after the regex constructor, it's
in $` (that's actually a perl bug). We need to be careful though
since the final match will destroy it again. That's why you will see
it quoted.
- things like .{19} can be written as (.{5}){3}.{4}, and the multiples
of 5 and one can be absorbed in the (.{5}){0,2}.{0,2} we already have.
So in the end this gives this 114:
-p
BEGIN{$<<=map$~.=$_%5&&pop,0..76}s/./.{1,3}(.{5}){6,8}$&/g;$_="$`"x($~x17)=~/$_.*(??{grep$c{$_%38}++,[EMAIL
PROTECTED])/x
