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.
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;
/// tally statistics
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, 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.
This is the same program, with some low-level optimizations: <lang d>import std.stdio, std.algorithm, std.string, std.range,
std.typecons, std.exception;
struct Ref {
ushort index; char lastChar, firstChar;
}
__gshared int nSolutions; __gshared Ref[] refs, longestPathRefs;
/// tally statistics void search(in size_t currLen) {
if (currLen == longestPathRefs.length) {
nSolutions++;
} else if (currLen > longestPathRefs.length) {
nSolutions = 1;
longestPathRefs = refs[0 .. currLen].dup;
}
// recursive search
const dchar lastChar = refs[currLen - 1].lastChar;
foreach (i; currLen .. refs.length)
if (refs[i].firstChar == lastChar) {
const aux = refs[currLen];
refs[currLen] = refs[i];
refs[i] = aux;
search(currLen + 1);
refs[i] = refs[currLen];
refs[currLen] = aux;
}
}
Tuple!(string[], int) findLongestChain(in string[] items) {
foreach (item; items)
enforce(item.length > 1);
foreach (ushort i, item; items)
refs ~= Ref(i, item[0], item[$-1]);
// try each item as possible start
foreach (i; 0 .. refs.length) {
const aux = refs[0];
refs[0] = refs[i];
refs[i] = aux;
search(1);
refs[i] = refs[0];
refs[0] = aux;
}
string[] longestPath;
foreach (r; longestPathRefs)
longestPath ~= items[r.index];
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, sol_nsol[0].length, 7))
writeln(" ", sol_nsol[0][i .. min(i+7, $)].join(" "));
}</lang> Runtime: about 0.67 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>
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
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