Last letter-first letter

Last letter-first letter
You are encouraged to solve this task according to the task description, using any language you may know.

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 70 English Pokemon names (extracted from Wikipedia's list of Pokemon) and generate the/a sequence with the highest possible number of Pokemon names where the subsequent name starts with the final letter of the preceding name. No Pokemon name is to be repeated.

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

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

C

From the D version. <lang c>#include <stdlib.h>

1. include <string.h>
2. include <stdio.h>
3. include <inttypes.h>

typedef struct {

   uint16_t index;
   char last_char, first_char;

} Ref;

Ref* longest_path_refs; size_t longest_path_refs_len;

Ref* refs; size_t refs_len;

size_t n_solutions;

char** longest_path; size_t longest_path_len;

/// tally statistics void search(const size_t curr_len) {

   if (curr_len == longest_path_refs_len) {
       n_solutions++;
   } else if (curr_len > longest_path_refs_len) {
       n_solutions = 1;
       longest_path_refs_len = curr_len;
       memcpy(longest_path_refs, refs, curr_len * sizeof(Ref));
   }

   // recursive search
   const intptr_t last_char = refs[curr_len - 1].last_char;
   for (size_t i = curr_len; i < refs_len; i++)
       if (refs[i].first_char == last_char) {
           const Ref aux = refs[curr_len];
           refs[curr_len] = refs[i];
           refs[i] = aux;
           search(curr_len + 1);
           refs[i] = refs[curr_len];
           refs[curr_len] = aux;
       }

}

void find_longest_chain(char **const items,

                       const size_t items_len) {
   refs_len = items_len;
   refs = calloc(refs_len, sizeof(Ref));

   // enough space for all items
   longest_path_refs_len = 0;
   longest_path_refs = calloc(refs_len, sizeof(Ref));

   for (size_t i = 0; i < items_len; i++) {
       const size_t itemsi_len = strlen(items[i]);
       if (itemsi_len <= 1)
           exit(1);
       refs[i].index = (uint16_t)i;
       refs[i].last_char = items[i][itemsi_len - 1];
       refs[i].first_char = items[i][0];
   }

   // try each item as possible start
   for (size_t i = 0; i < items_len; i++) {
       const Ref aux = refs[0];
       refs[0] = refs[i];
       refs[i] = aux;
       search(1);
       refs[i] = refs[0];
       refs[0] = aux;
   }

   longest_path_len = longest_path_refs_len;
   longest_path = calloc(longest_path_len, sizeof(char*));
   for (size_t i = 0; i < longest_path_len; i++)
       longest_path[i] = items[longest_path_refs[i].index];

   free(longest_path_refs);
   free(refs);

}

int main() {

   char* pokemon[] = {"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"};
   const size_t pokemon_len = sizeof(pokemon) / sizeof(pokemon[0]);

   find_longest_chain(pokemon, pokemon_len);
   printf("Maximum path length: %u\n", longest_path_len);
   printf("Paths of that length: %u\n", n_solutions);
   printf("Example path of that length:\n");
   for (size_t i = 0; i < longest_path_len; i += 7) {
       printf("  ");
       for (size_t j = i; j < (i+7) && j < longest_path_len; j++)
           printf("%s ", longest_path[j]);
       printf("\n");
   }

   free(longest_path);

   return 0;

}</lang> Output:

Maximum path length: 23
Paths of that length: 1248
Example path of that length:
  machamp petilil landorus scrafty yamask kricketune emboar
  registeel loudred darmanitan nosepass simisear relicanth heatmor
  rufflet trapinch haxorus seaking girafarig gabite exeggcute
  emolga audino

Runtime: about 0.49 seconds, gcc compiler.

D

Improved from the Go version: <lang d>import std.stdio,std.algorithm,std.string,std.range,std.typecons;

Tuple!(string[], int) findLongestChain(string[] items) {

   string[] longestPath;
   int nSolutions;

   void search(in int currLen) {
       if (currLen == longestPath.length) {
           nSolutions++;
       } else if (currLen > longestPath.length) {
           nSolutions = 1;
           longestPath = items[0 .. currLen].dup;
       }

       // recursive search
       const dchar lastChar = items[currLen - 1][$ - 1];
       foreach (i; currLen .. items.length)
           if (items[i][0] == lastChar) {
               swap(items[currLen], items[i]);
               search(currLen + 1);
               swap(items[currLen], items[i]);
           }
   }

   // try each item as possible start
   foreach (i; 0 .. items.length) {
       swap(items[0], items[i]);
       search(1);
       swap(items[0], items[i]);
   }

   return tuple(longestPath, nSolutions);

}

void main() {

   auto pokemon = "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".tolower().split();

   // remove duplicates
   pokemon.length -= copy(uniq(pokemon.sort()), pokemon).length;

   auto sol_nsol = findLongestChain(pokemon);
   writeln("Maximum path length: ", sol_nsol[0].length);
   writeln("Paths of that length: ", sol_nsol[1]);
   writeln("Example path of that length:");
   foreach (i; iota(0, cast(int)sol_nsol[0].length, 7))
       writeln("  ", sol_nsol[0][i .. min(i+7, $)].join(" "));

}</lang> Output:

Maximum path length: 23
Paths of that length: 1248
Example path of that length:
  machamp petilil landorus scrafty yamask kricketune emboar
  registeel loudred darmanitan nosepass simisear relicanth heatmor
  rufflet trapinch haxorus seaking girafarig gabite exeggcute
  emolga audino

Runtime: about 1.23 seconds, dmd compiler.

A more optimized solution (same output): <lang d>import std.stdio, std.algorithm, std.string,

      std.range, std.typecons;

alias Tuple!(string, "word", bool, "unused") Pair; int nSolutions;

void search(Pair[][] sequences, size_t minHead, string currWord,

           string[] currentPath, size_t currentPathLen,
           ref string[] longestPath) {

   currentPath[currentPathLen] = currWord;
   currentPathLen++;

   if (currentPathLen == longestPath.length) {
       nSolutions++;
   }  else if (currentPathLen > longestPath.length) {
       nSolutions = 1;
       longestPath = currentPath[0 .. currentPathLen].dup;
   }

   // recursive search
   size_t lastCharIndex = currWord[$ - 1] - minHead;
   if (lastCharIndex < sequences.length)
       foreach (ref pair; sequences[lastCharIndex])
           if (pair.unused) {
               pair.unused = false;
               search(sequences, minHead, pair.word, currentPath,
                      currentPathLen, longestPath);
               pair.unused = true;
           }

}

string[] findLongestChain(string[] words) {

   auto heads = map!q{ a[0] }(words);
   size_t minHead = reduce!min(heads);
   size_t maxHead = reduce!max(heads);
   auto sequences = new Pair[][](maxHead - minHead + 1, 0);
   foreach (word; words)
       sequences[word[0] - minHead] ~= Pair(word, true);

   auto currentPath = new string[words.length];
   string[] longestPath;

   // try each item as possible start
   foreach (seq; sequences)
       foreach (ref pair; seq) {
           pair.unused = false;
           search(sequences, minHead, pair.word,
                  currentPath, 0, longestPath);
           pair.unused = true;
      }

   return longestPath;

}

void main() {

   auto pokemon = "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".tolower().split();

   // remove duplicates
   pokemon.length -= copy(uniq(pokemon.sort()), pokemon).length;

   auto sol = findLongestChain(pokemon);
   writeln("Maximum path length: ", sol.length);
   writeln("Paths of that length: ", nSolutions);
   writeln("Example path of that length:");
   foreach (i; iota(0, cast(int)sol.length, 7))
       writeln("  ", sol[i .. min(i+7, $)].join(" "));

}</lang> Runtime: about 0.20 seconds, dmd compiler.

Go

Depth first, starting with each possible name. <lang go>package main

import (

   "fmt"
   "strings"

)

var pokemon = `audino bagon baltoy...67 names omitted...`

func main() {

   // split text into slice representing directed graph
   var d []string
   for _, l := range strings.Split(pokemon, "\n", -1) {
       d = append(d, strings.Fields(l)...)
   }
   fmt.Println("searching", len(d), "names...")
   // try each name as possible start
   for i := range d {
       d[0], d[i] = d[i], d[0]
       search(d, 1, len(d[0]))
       d[0], d[i] = d[i], d[0]
   }
   fmt.Println("maximum path length:", len(ex))
   fmt.Println("paths of that length:", nMax)
   fmt.Print("example path of that length:")
   for i, n := range ex {
       if i%6 == 0 {
           fmt.Print("\n   ")
       }
       fmt.Print(n, " ")
   }
   fmt.Println()

}

var ex []string var nMax int

func search(d []string, i, ncPath int) {

   // tally statistics
   if i == len(ex) {
       nMax++
   } else if i > len(ex) {
       nMax = 1
       ex = append(ex[:0], d[:i]...)
   }
   // recursive search
   lastName := d[i-1]
   lastChar := lastName[len(lastName)-1]
   for j := i; j < len(d); j++ {
       if d[j][0] == lastChar {
           d[i], d[j] = d[j], d[i]
           search(d, i+1, ncPath+1+len(d[i]))
           d[i], d[j] = d[j], d[i]
       }
   }

}</lang> Output:

searching 70 names...
maximum path length: 23
paths of that length: 1248
example path of that length:
   machamp petilil landorus scrafty yamask kricketune 
   emboar registeel loudred darmanitan nosepass simisear 
   relicanth heatmor rufflet trapinch haxorus seaking 
   girafarig gabite exeggcute emolga audino 

J

Here, we use a brute force breadth-first search. Unless we know ahead of time how long "longest" is, we must try all possibilities to ensure that an unchecked possibility is not longer than a possibility which we have found.

<lang j>pokenames=: ;:0 :0-.LF

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

)

seqs=: 3 :0

 links=. <@I. _1 =/&({&>&y) 0  
 next=. ,.i.#links
 while.#next do.
    r=. next
    assert. 1e9>*/8,$r
    next=. (#~ (-: ~.)"1) >;<@(] <@,"1 0 links {::~ {:)"1 r
 end.
 r

)</lang>

The line assert. 1e9>*/8,$r was added to avoid a very bad behavior from microsoft windows which appeared on different arguments, when intermediate results became too large (the machine would have to be rebooted when intermediate results became an order of magnitude larger than the available physical memory). By ensuring that the program would end before consuming that much virtual memory, this behavior from the operating system can be avoided.

With this procedure we are able to conduct the entire search for this list of names:

<lang j>$R=: seqs pokenames 1248 23</lang>

With this data set, we have 1248 sequences of names which have the longest possible length, and those sequences are 23 names long. Here's one of them:

<lang j> >pokenames {~{.R machamp petilil landorus scrafty yamask kricketune emboar registeel loudred darmanitan nosepass simisear relicanth heatmor rufflet trapinch haxorus seaking girafarig gabite exeggcute emolga audino </lang>

OpenEdge/Progress

The following gets the job done, but the time taken (40 minutes) is somewhat worrying when compared to other language solutions. So I am not going after the brownie points just yet...

<lang progress>DEFINE VARIABLE cpokemon AS CHARACTER INITIAL "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".

DEFINE TEMP-TABLE tt NO-UNDO

  FIELD cname    AS CHARACTER
  FIELD cfirst   AS CHARACTER
  FIELD clast    AS CHARACTER
  FIELD lused    AS LOGICAL
  FIELD ilength  AS INTEGER
  FIELD imax     AS INTEGER
  FIELD cchain   AS CHARACTER

INDEX ttname cname INDEX ttfirst cfirst lused INDEX ttlast clast lused .

DEFINE VARIABLE ii AS INTEGER NO-UNDO.

DO ii = 1 TO NUM-ENTRIES( cpokemon, " " ):

  CREATE tt.
  ASSIGN
     tt.cname    =  ENTRY( ii, cpokemon, " " )
     tt.cfirst   =  SUBSTRING( tt.cname, 1, 1 )
     tt.clast    =  SUBSTRING( tt.cname, LENGTH( tt.cname ), 1 )
     .

END.

FUNCTION getChain RETURNS INTEGER (

  i_cname     AS CHARACTER,
  i_clast     AS CHARACTER,
  i_ilength   AS INTEGER,
  i_cchain    AS CHARACTER

):

  DEFINE BUFFER tt FOR tt.

  DEFINE VARIABLE lend_of_chain AS LOGICAL     NO-UNDO INITIAL TRUE.

  FOR EACH tt
     WHERE tt.cfirst   =  i_clast
     AND   tt.lused    =  FALSE
     OR    i_clast     =  ""
  :
     lend_of_chain = FALSE.
     tt.lused = TRUE.
     getChain( tt.cname, tt.clast, i_ilength + 1, i_cchain + tt.cname + " " ).
     tt.lused = FALSE.
  END.
  IF lend_of_chain THEN DO:
     FIND tt WHERE tt.cname = ENTRY( 1, i_cchain, " " ).
     IF i_ilength = tt.ilength THEN
        tt.imax = tt.imax + 1.
     ELSE IF i_ilength > tt.ilength THEN
        ASSIGN
           tt.ilength  =  i_ilength
           tt.cchain   =  i_cchain
           tt.imax     =  1
           .
  END.

END FUNCTION. /* getChain */

DEFINE VARIABLE itime AS INTEGER NO-UNDO EXTENT 2. DEFINE VARIABLE lcontinue AS LOGICAL NO-UNDO.

itime[1] = ETIME. getChain( "", "", 0, "" ). itime[2] = ETIME.

FOR EACH tt BY tt.ilength DESCENDING:

  MESSAGE
     "Maximum path length:"  tt.ilength SKIP
     "Paths of that length:" tt.imax SKIP(1)
     "Example path of that length:" tt.cchain SKIP(1)
     "Time taken:" STRING( INTEGER( ( itime[2] - itime[1] ) / 1000 ), "HH:MM:SS" )
  VIEW-AS ALERT-BOX BUTTONS YES-NO TITLE tt.cname UPDATE lcontinue.
  IF lcontinue = FALSE THEN
     STOP.

END.</lang>

Output:

---------------------------
machamp
---------------------------
Maximum path length: 23 
Paths of that length: 1248 

Example path of that length: machamp petilil landorus scrafty yamask kricketune emboar registeel loudred darmanitan nosepass simisear relicanth heatmor rufflet trapinch haxorus seaking girafarig gabite exeggcute emolga audino  

Time taken: 00:40:09
---------------------------
Yes   No   
---------------------------

PicoLisp

<lang PicoLisp>(de pokemonChain (File)

  (let Names (make (in File (while (read) (link @))))
     (for Name Names
        (let C (last (chop Name))
           (set Name
              (filter '((Nm) (pre? C Nm)) Names) ) ) )
     (let Res NIL
        (for Name Names
           (let Lst NIL
              (recur (Name Lst)
                 (if (or (memq Name Lst) (not (val (push 'Lst Name))))
                    (when (> (length Lst) (length Res))
                       (setq Res Lst) )
                    (mapc recurse (val Name) (circ Lst)) ) ) ) )
        (flip Res) ) ) )</lang>

Test:

: (pokemonChain "pokemon.list")
-> (machamp petilil landorus scrafty yamask kricketune emboar registeel loudred
darmanitan nosepass simisear relicanth heatmor rufflet trapinch haxorus seaking
girafarig gabite exeggcute emolga audino)
: (length @)
-> 23

Python

<lang python>from collections import defaultdict

def order_words(words):

   byfirst = defaultdict(set)
   for word in words:
       byfirst[word[0]].add( word )
   #byfirst = dict(byfirst)
   return byfirst

def linkfirst(byfirst, sofar):

   \
   For all words matching last char of last word in sofar as FIRST char and not in sofar,
   return longest chain as sofar + chain
   

   assert sofar
   chmatch = sofar[-1][-1]
   options = byfirst[chmatch] - set(sofar)
   #print('  linkfirst options: %r %r' % (chmatch, options))
   if not options:
       return sofar
   else:
       alternatives = ( linkfirst(byfirst, list(sofar) + [word])
                        for word in options )
       mx = max( alternatives, key=len )
       #input('linkfirst: %r' % mx)
       return mx

def llfl(words):

   byfirst = order_words(words)
   return max( (linkfirst(byfirst, [word]) for word in words), key=len )

if __name__ == '__main__':

   pokemon = 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

   pokemon = pokemon.strip().lower().split()
   pokemon = sorted(set(pokemon))    
   l = llfl(pokemon)
   for i in range(0, len(l), 8): print(' '.join(l[i:i+8]))
   print(len(l))</lang>

Sample output

audino bagon baltoy banette bidoof braviary bronzor carracosta
charmeleon cresselia croagunk darmanitan deino emboar emolga exeggcute
gabite girafarig gulpin haxorus heatmor heatran ivysaur jellicent
23

Alternative version

Adapted from the D version. This uses Psyco. <lang python>import psyco

nsolutions = 0

def search(sequences, ord_minc, curr_word, current_path,

          current_path_len, longest_path):
   global nsolutions

   current_path[current_path_len] = curr_word
   current_path_len += 1

   if current_path_len == len(longest_path):
       nsolutions += 1
   elif current_path_len > len(longest_path):
       nsolutions = 1
       longest_path[:] = current_path[:current_path_len]

   # recursive search
   last_char_index = ord(curr_word[-1]) - ord_minc
   if last_char_index >= 0 and last_char_index < len(sequences):
       for pair in sequences[last_char_index]:
           if not pair[1]:
               pair[1] = True
               search(sequences, ord_minc, pair[0], current_path,
                      current_path_len, longest_path)
               pair[1] = False

def find_longest_chain(words):

   ord_minc = ord(min(word[0] for word in words))
   ord_maxc = ord(max(word[0] for word in words))
   sequences = [[] for _ in xrange(ord_maxc - ord_minc + 1)]
   for word in words:
       sequences[ord(word[0]) - ord_minc].append([word, False])

   current_path = [None] * len(words)
   longest_path = []

   # try each item as possible start
   for seq in sequences:
       for pair in seq:
           pair[1] = True
           search(sequences, ord_minc, pair[0],
                  current_path, 0, longest_path)
           pair[1] = False

   return longest_path

def main():

   global nsolutions

   pokemon = """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""".lower().split()

   # remove duplicates
   pokemon = sorted(set(pokemon))

   sol = find_longest_chain(pokemon)
   print "Maximum path length:", len(sol)
   print "Paths of that length:", nsolutions
   print "Example path of that length:"
   for i in xrange(0, len(sol), 7):
       print " ", " ".join(sol[i : i+7])

psyco.full() main()</lang> Output:

Maximum path length: 23
Paths of that length: 1248
Example path of that length:
  machamp petilil landorus scrafty yamask kricketune emboar
  registeel loudred darmanitan nosepass simisear relicanth heatmor
  rufflet trapinch haxorus seaking girafarig gabite exeggcute
  emolga audino

Run time: about 0.44 seconds with Psyco and Python 2.6.6.

Tcl

<lang tcl>proc search {path arcs} {

   set solutions {}
   set c [string index [lindex $path end] end]
   set i -1
   foreach arc $arcs {

incr i if {[string index $arc 0] ne $c} continue set soln [search [concat $path [list $arc]] [lreplace $arcs $i $i]] lappend solutions [list [llength $soln] $soln]

   }
   if {[llength $solutions]} {

return [lindex [lsort -integer -decreasing -index 0 $solutions] 0 1]

   } else {

return $path

   }

} proc firstlast names {

   set solutions {}
   set i -1
   foreach initial $names {

incr i set soln [search [list $initial] [lreplace $names $i $i]] lappend solutions [list [llength $soln] $soln]

   }
   return [lindex [lsort -integer -decreasing -index 0 $solutions] 0 1]

}

set names {

   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

} set path [firstlast $names] puts "Path (length: [llength $path]): $path"</lang> Output:

Path (length 23): machamp petilil landorus scrafty yamask kricketune emboar registeel loudred darmanitan nosepass simisear relicanth heatmor rufflet trapinch haxorus seaking girafarig gabite exeggcute emolga audino

Ursala

<lang Ursala>#import std

mon =

~&*~ sep` mat` -[

  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]-

poke = @iiDrzhK16rlXOASK24PiX ~&llrHiFPrYX^=rxS^|\~&iNCS *=+ ~&rlwNrlCQ^*D/~&+ @h

1. show+

example = ~&h poke mon</lang>output:

machamp
petilil
landorus
scrafty
yamask
kricketune
emboar
registeel
loudred
darmanitan
nosepass
simisear
relicanth
heatmor
rufflet
trapinch
haxorus
seaking
girafarig
gabite
exeggcute
emolga
audino