challenge-025/lars-balker/perl5/ch-1.pl


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

#!/usr/bin/env perl

use v5.10;
use strict;
use warnings;

# Generate a longest sequence of the following “English Pokemon” names
# where each name starts with the last letter of previous name.

my @names = 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
/;

my $longest = [];

try([], "", @names);

say "@$longest";

# naive brute force recursion
sub try {
    my ($picks, $prefix, @rest) = @_;

    $longest = $picks if @$picks > @$longest;

    for (my $i = 0; $i < @rest; ++$i) {
        next unless $rest[$i] =~ /^$prefix/;
        try([@$picks, $rest[$i]],
            substr($rest[$i], -1),
            @rest[0..$i-1, $i+1..$#rest]);
    }
}