Talk:Last letter-first letter

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²⁸ or about 3×10⁴⁰ 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)

OK, the PicoLisp solution is correct either way. Dkf complained that the name appeared twice, but this happends because PicoLisp correctly distinguishes between these two symbols. The code is the same anyway, just the input data changed.--Abu 13:18, 7 June 2011 (UTC)

I complained because it flatly wasn't obeying the rules of the game. The rules relate to letters of words, not random extra obscure marks. Right is right! –Donal Fellows 14:45, 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 72 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.

audino bagon baltoybanette 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
mienshao milotic moltres monferno munna murkrow musharna nidoking noctowl
nosepass petilil pidgeotto pikachu pinsir poliwrath poochyena porygon2
porygonz registeel relicanth remoraid rufflet sableye scolipede scrafty seaking
sealeo silcoon simisear snivysnorlax spoink starly tirtouga trapinch treecko
tyrogue vigoroth vulpix wailord wartortle whismur wingull yamask

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

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

Did you mean to leave the ♀ on nidoran? It'd be hard to match that with anything :) MagiMaster 11:16, 7 June 2011 (UTC)

New list above - thanks. --Paddy3118 12:51, 7 June 2011 (UTC)

72 works for me. Depth first traversal gave me a path of 24 in about 2 seconds. —Sonia 14:40, 7 June 2011 (UTC)

I just noticed that several of the names lost the space between them. I've added it back, but someone should double check that I didn't mess something up or miss something. MagiMaster 21:23, 7 June 2011 (UTC)