Talk:Last letter-first letter

From Rosetta Code

Number of names

This is equivalent to asking for the longest path in a directed graph, which is an NP-complete problem. That doesn't rule it out as a task, but running it on a graph with 646 nodes might take too long. Also, since it seems to be rare to use external files to store the data (or at least I haven't seen many tasks that call for that) having all the names in each example would get really cluttered. MagiMaster 20:52, 5 June 2011 (UTC)

Re input data; I can always host input data if that makes it convenient to work on appropriate data. --Michael Mol 23:12, 5 June 2011 (UTC)
That's not really the problem. A quick breadth first search implementation gave me 646 pokemon names, 1793 pokemon name pairs, 518546 pokemon name triples, 14745709 pokemon name quadruples, and I had to reboot my machine to recover from my attempt to represent all pokemon name quintuples. Inspecting this sequence suggests a search space on the order of 28^28 or about 3e40 sequences to investigate. That exceeds the storage capacity of my laptop. (Not to mention, exceeds my patience). Note that finding a long sequence is not very hard, it's finding the longest that makes this task hard. --Rdm 20:08, 6 June 2011 (UTC)
If the part about using all the pokemon names was changed, it'd be an interesting task. 20 or so names/words/nodes should demonstrate the process well enough without being too slow. MagiMaster 21:37, 6 June 2011 (UTC)

Re problems with PicoLisp version, Nidoran can be male or female, and this is marked in the list with male and female (mars and venus) symbols. I'd suggest spelling out "Male" and "Female". Axtens 10:10, 7 June 2011 (UTC)

Unless someone has a reasonable algorithm that makes this doable then it should be deleted or modified. --Paddy3118 07:00, 7 June 2011 (UTC)

Okay, have allowed for limiting the list to the first 151 Pokemon. Extra points for using the full 646. Axtens 07:29, 7 June 2011 (UTC)
If you can't do the full task then maybe you should leave it out?
Have you done the 151? --Paddy3118 07:49, 7 June 2011 (UTC)

Task description change proposal:

A certain childrens game involves starting with a word in a particular category. Each participant in turn says a word, but that word must begin with the final letter of the previous word. Once a word has been given, it cannot be repeated. If an opponent cannot give a word in the category, they fall out of the game. For example, with "animals" as the category, 

Child 1: dog 
Child 2: goldfish
Child 1: hippopotamus
Child 2: snake
...
Task Description

Take the following selection of 75 English Pokemon names (extracted from Wikipedia's list of Pokemon) and generate the longest possible combination of Pokemon where the subsequent starts with the final letter of the preceding. No Pokemon name is to be repeated. 

articuno baltoy bellsprout cherrim claydol cloyster crobat croconaw deino diglett
dragonair drilbur dunsparce exeggcute exeggutor farfetch'd finneon foongus gligar golduck
grovyle happiny hoppip ivysaur jellicent jolteon kabutops kakuna lanturn lopunny
lunatone magmortar magnemite mantine mareep marshtomp mightyena misdreavus munna murkrow
nidoran♀ noctowl onix oshawott porygon purrloin quilava qwilfish rufflet sandslash
sharpedo shellos simisear skiploom slaking snivy snorlax staravia starmie stunky
swellow tangela tangrowth teddiursa tentacool tranquill tynamo vaporeon venipede vespiquen
vigoroth vulpix weezing wurmple zekrom

Extra brownie points for dealing with the full list of 646 names.

--Paddy3118 10:29, 7 June 2011 (UTC)

Retrieved from "https://rosettacode.org/wiki/Talk:Last_letter-first_letter?oldid=186730"