blob: 6633e8d2661864f04ac9759dbaeafaefc0f816ec (
plain) (
blame)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
|
#!/usr/bin/env perl
#
# Generate a longest sequence of the following “English Pokemon” names where
# each name starts with the last letter of previous name.
#
# audino bagon baltoy banette bidoof braviary bronzor carracosta charmeleon
# cresselia croagunk darmanitan deino emboar emolga exeggcute gabite girafarig
# gulpin haxorus heatmor heatran ivysaur jellicent jumpluff kangaskhan
# kricketune landorus ledyba loudred lumineon lunatone machamp magnezone
# mamoswine nosepass petilil pidgeotto pikachu pinsir poliwrath poochyena
# porygon2 porygonz registeel relicanth remoraid rufflet sableye scolipede
# scrafty seaking sealeo silcoon simisear snivy snorlax spoink starly tirtouga
# trapinch treecko tyrogue vigoroth vulpix wailord wartortle whismur wingull
# yamask
################################################################################
use strict;
use warnings;
use Memoize;
my @POKEMON = qw<audino bagon baltoy banette bidoof braviary bronzor carracosta
charmeleon cresselia croagunk darmanitan deino emboar emolga exeggcute
gabite girafarig gulpin haxorus heatmor heatran ivysaur jellicent jumpluff
kangaskhan kricketune landorus ledyba loudred lumineon lunatone machamp
magnezone mamoswine nosepass petilil pidgeotto pikachu pinsir poliwrath
poochyena porygon2 porygonz registeel relicanth remoraid rufflet sableye
scolipede scrafty seaking sealeo silcoon simisear snivy snorlax spoink
starly tirtouga trapinch treecko tyrogue vigoroth vulpix wailord wartortle
whismur wingull yamask>;
memoize('longest_starting_from');
sub longest_starting_from {
my ($first, @pokemon) = @_;
my @candidates = grep { substr($_, 0, 1) eq $first } @pokemon;
my @longest_path;
foreach my $candidate (@candidates) {
my @path = longest_starting_from(substr($candidate, -1),
grep { $_ ne $candidate} @pokemon);
@longest_path = ($candidate, @path) if @path+1 > @longest_path;
}
return @longest_path;
}
sub longest {
my @list = @_;
my @longest_path;
foreach my $letter ('a' .. 'z') {
print "Trying letter $letter...\n";
my @path = longest_starting_from($letter, @list);
@longest_path = @path if @path > @longest_path;
print "Longest so far: @longest_path\n";
}
return @longest_path;
}
print longest(@POKEMON);
|
