0

This is an interesting question which has been discussed in Japan, so I wonder if there are more efficient way.

Pokémon is one of the most famous game all over the word, and there are 898 Pokémon in all so far.So there are 898 names.What you need to do is try to find the longest word chain of Pokémon. Suppose each pokemon name can only be used once. For example,if you start with Pikachu (maybe the most famous Pokémon), Pikachu ends with the letter "u",so you need to find another Pokémon name starting with "u",such as Unown whose ending letter is "n". Next,you need to find another Pokémon name starting with "n".

Obviously there must exist a longest word chain. So how to find the longest word chain of Pokémon efficiently? And how to prove it is the longest one?

In essence, this is a mathematical problem that has nothing to do with Pokémon, but sucht word chain is used in the song of pokemon cartoon, so I connect the two sides.

Calvin Khor
  • 34,903
ArosDong
  • 87
  • "so I wonder if there are more efficient way." more efficient than what? can you describe what people have already done? By efficient, do you mean an algorithm in computer code? (I made some minor english changes, but note that although there must exist a longest word chain, it is not clear if there is a unique longest word chain, so one may not necessarily speak of "the" longest word chain) – Calvin Khor Sep 27 '21 at 07:22
  • 2
    @postmortes my graph theory is incredibly rusty; isn't Dijkstra for shortest paths though? I found this "longest path problem" instead. So each pokemon is a vertex, with a directed edge corresponding to the rule of the game. That the path must be simple corresponds to each pokemon can only be used once. So I think this is a good match – Calvin Khor Sep 27 '21 at 07:36
  • In fact, a Japanese mathematics student discussed this problem in his graduation thesis a few years ago. It is said that he gave the proof of the longest word chain (there were fewer pokemon at that time). Unfortunately, this thesis was not published, so I don't know what method he used to prove it(written in japanese). For this problem, many fans in Japan wrote code for calculation, and gave examples of the longest chain.Here is an example, but I can't program, so I don't understand it.URL:https://github.com/maraigue/rglpk_shiritori – ArosDong Sep 27 '21 at 16:07
  • 1
    @ArosDong It seems to me that the linked code uses integer linear programming to solve the longest path problem. You cannot do this "fast" (in polynomial time), unless the graph is a special case of some sort (for example, if the graph were a tree, then we are looking for diameter which is linear time). – Vepir Sep 28 '21 at 13:05

0 Answers0