118 chars:
sub state {
1&index" AKALCAARAZCOCTDCDEFLGAHIIAIDILINKSKTKYLAMAMDMEMIMNNCMOMSMTOHN
+DNENHNJNMPANVNYOKORRISCSDTNTXUTVAVTWAWIWVWY",pop
}
And it's 117 chars if you replace pop with $_, as the original rules ask.
The character string was constructed to ensure that a valid state would
never match a non-valid boundary. It was easier than I thought:
#!/usr/bin/perl
use strict;
$|++;
my @states = qw(
AK AL AR AZ CA CO CT DC DE FL GA HI IA ID IL IN KS
KT KY LA MA MD ME MI MN MO MS MT NC ND NE NH NJ NM
NV NY OH OK OR PA RI SC SD TN TX UT VA VT WA WI WV
WY
);
my %states = map { $_ => 1 } @states;
try("", \@states);
sub try {
print "try: $_[0] @{$_[1]}\n";
my $prefix = shift;
my @later = @{+shift};
unless (@later) {
print "WINNER: $prefix\n";
exit;
}
for my $i (0..$#later) {
my $prefix2 = "$prefix$later[$i]";
if (length $prefix2 < 3 or not $states{substr($prefix2, -3, 2)}) {
## worth recursing
try($prefix2, [@later[0..$i-1, $i+1..$#later]]);
}
}
}
-- Randal L. Schwartz, Perl hacker