Pokemon Name Ladder

Given a list of Pokemon names, what is the longest sequence of names which can be obtained by creating a name ladder where the first letter of a name is the same letter as the name preceding it? Turns out to be 105 characters long, according to the method I used.

The Code

How it works

The names are read in, they are held in the scripts __DATA__ section for convenience, and added to a Graph. Each vertex is a Pokemon name and the (directed) edges are created by the name ladder rule. The edge weight is the negative of the length of the vertex's successor. The Floyd-Warshall All Pairs Shortest Path algorithm is run on the resulting graph and the returned paths are reviewed to see which one is the longest in terms of overall character length. By using the negative of the weight the paths found are actually the longest, not shortest. The result is printed along with the length.

The full number of Pokemon as of this writing is 809! Here I am just using a sampling of the complete set.

Sample Run

$ perl perl5/
machamp-petilil-lunatone-exeggcute-emboar-registeel-loudred-darmanitan-nosepass-simisear-rufflet-tyrogue-emolga-audino 105

Comments for this post were locked by the author