Last letter-first letter: Difference between revisions
Added Easylang
(Add Clojure implementation) |
(Added Easylang) |
||
(45 intermediate revisions by 20 users not shown) | |||
Line 33:
Extra brownie points for dealing with the full list of 646 names.
<br><br>
=={{header|11l}}==
{{trans|Python}}
<syntaxhighlight lang="11l">F order_words(words)
DefaultDict[Char, Set[String]] byfirst
L(word) words
byfirst[word[0]].add(word)
R byfirst
F linkfirst(&byfirst; sofar)
assert(!sofar.empty)
V chmatch = sofar.last.last
V options = byfirst[chmatch] - Set(sofar)
I options.empty
R sofar
E
V alternatives = options.map(word -> linkfirst(&@byfirst, @sofar [+] [word]))
R max(alternatives, key' s -> s.len)
F llfl(words)
V byfirst = order_words(words)
R max((words.map(word -> linkfirst(&@byfirst, [word]))), key' s -> s.len)
V pokemon_str = ‘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’
V pokemon = pokemon_str.split((‘ ’, "\n"))
V l = llfl(pokemon)
L(i) (0 .< l.len).step(8)
print(l[i .< i + 8].join(‘ ’))
print(l.len)</syntaxhighlight>
{{out}}
<pre>
machamp petilil landorus scrafty yamask kricketune emboar registeel
loudred darmanitan nosepass simisear relicanth heatmor rufflet trapinch
haxorus seaking girafarig gabite exeggcute emolga audino
23
</pre>
=={{header|Ada}}==
<
procedure Lalefile is
Line 114 ⟶ 160:
Ada.Text_IO.Put_Line("One such path:");
Write(Best);
end Lalefile;</
Output:<pre>Processing a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p, q, r, s, t, u, v, w, x, y, z,
Line 142 ⟶ 188:
emolga
audino</pre>
=={{header|BaCon}}==
Naive implementation showing the algorithm.
<syntaxhighlight lang="freebasic">all$ = "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"
SUB check(list$, rest$)
LOCAL x
FOR x = 1 TO AMOUNT(rest$)
IF RIGHT$(list$, 1) = LEFT$(TOKEN$(rest$, x), 1) THEN check(APPEND$(list$, 0, TOKEN$(rest$, x)), DEL$(rest$, x))
NEXT
IF AMOUNT(list$) > total THEN
total = AMOUNT(list$)
result$ = list$
END IF
END SUB
FOR z = 1 TO AMOUNT(all$)
CALL check(TOKEN$(all$, z), DEL$(all$,z))
NEXT
PRINT total, ": ", result$
PRINT NL$, "Speed: ", TIMER, " msecs."</syntaxhighlight>
{{out}}
<pre>
23: machamp petilil landorus scrafty yamask kricketune emboar registeel loudred darmanitan nosepass simisear relicanth heatmor rufflet trapinch haxorus seaking girafarig gabite exeggcute emolga audino
Speed: 662734 msecs.
</pre>
Optimized implementation. The idea is to quantify the equations.
<syntaxhighlight lang="freebasic">all$ = "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"
SPLIT all$ TO name$ SIZE MaxSize
DECLARE start, end, used, result ARRAY MaxSize
FOR y = 0 TO MaxSize-1
start[y] = ASC(LEFT$(name$[y], 1))
end[y] = ASC(RIGHT$(name$[y], 1))
used[y] = -1
NEXT
FOR i = 0 TO MaxSize-1
used[i] = 0
CALL check(used, i, 1)
used[i] = -1
NEXT
PRINT maxtotal, ": ";
FOR a = 0 TO maxtotal-1
FOR y = 0 TO MaxSize-1
IF result[y] = a THEN PRINT name$[y]," ";
NEXT
NEXT
PRINT NL$, "Speed: ", TIMER, " msecs."
SUB check(ya[], ultim, nr)
LOCAL x
FOR x = 0 TO MaxSize-1
IF end[ultim] = start[x] AND ya[x] = -1 THEN
ya[x] = nr
CALL check(ya, x, nr+1)
ya[x] = -1
END IF
IF nr > maxtotal THEN
maxtotal = nr
OPTION MEMTYPE long
COPY ya TO result SIZE MaxSize
END IF
NEXT
END SUB
</syntaxhighlight>
{{out}}
<pre>
23: machamp petilil landorus scrafty yamask kricketune emboar registeel loudred darmanitan nosepass simisear relicanth heatmor rufflet trapinch haxorus seaking girafarig gabite exeggcute emolga audino
Speed: 818 msecs.
</pre>
=={{header|BASIC256}}==
<
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" }
Line 200 ⟶ 348:
index[b] = t
end subroutine
</syntaxhighlight>
Output:
Line 214 ⟶ 362:
=={{header|BBC BASIC}}==
{{works with|BBC BASIC for Windows}}
<
names$() = "audino", "bagon", "baltoy", "banette", \
\ "bidoof", "braviary", "bronzor", "carracosta", "charmeleon", \
Line 264 ⟶ 412:
ENDIF
NEXT
ENDPROC</
'''Output:'''
<pre>
Line 297 ⟶ 445:
=={{header|Bracmat}}==
===Naive===
<
carracosta charmeleon cresselia croagunk darmanitan deino
emboar emolga exeggcute gabite girafarig gulpin haxorus
Line 339 ⟶ 487:
& lalefile$(.!names)
& out$("Length:" !max "Sequence:" !sequence)
);</
Output (read from bottom to top):
<pre> Length:
Line 392 ⟶ 540:
The optimized version is about 4.5 times faster than the naive version.
<
carracosta charmeleon cresselia croagunk darmanitan deino
emboar emolga exeggcute gabite girafarig gulpin haxorus
Line 451 ⟶ 599:
& lalefile$(.!names)
& out$("Length:" !max "Sequence:" !sequence)
);</
Output (read from bottom to top):
<pre> Length:
Line 482 ⟶ 630:
=={{header|C}}==
From the D version.
<
#include <string.h>
#include <stdio.h>
Line 595 ⟶ 743:
return 0;
}</
Output:
<pre>Maximum path length: 23
Line 608 ⟶ 756:
===Approximate===
For dealing with full list (646 names), here's an approximate method. Names are restricted to begin and end with a lower case letter, so for example in my input file "porygon2" is written as "porygon-two". It finds some chains with 300-odd length for 646 names, and found a chain with 23 for the 70 names (by luck, that is), and since it's basically a one-pass method, running time is next to none. C99 code.
<
#include <stdlib.h>
#include <string.h>
Line 803 ⟶ 951:
printf("longest found: %d\n", best);
return 0;
}</
307: voltorb breloom magikarp palpito...
308: voltorb bayleef forretress swinub b...
Line 811 ⟶ 959:
322: voltorb beldum mandibuzz zekrom murk...
323: voltorb breloom mandibuzz zekr...
longest found: 323</
=={{header|C sharp}}==
<
using System.Collections.Generic;
using System.Linq;
Line 946 ⟶ 1,026:
}
}
}</
petilil
landorus
Line 967 ⟶ 1,047:
emolga
audino</pre>
=={{header|C++}}==
<syntaxhighlight lang="cpp">#include <iostream>
#include <string>
#include <vector>
struct last_letter_first_letter {
size_t max_path_length = 0;
size_t max_path_length_count = 0;
std::vector<std::string> max_path_example;
void search(std::vector<std::string>& names, size_t offset) {
if (offset > max_path_length) {
max_path_length = offset;
max_path_length_count = 1;
max_path_example.assign(names.begin(), names.begin() + offset);
} else if (offset == max_path_length) {
++max_path_length_count;
}
char last_letter = names[offset - 1].back();
for (size_t i = offset, n = names.size(); i < n; ++i) {
if (names[i][0] == last_letter) {
names[i].swap(names[offset]);
search(names, offset + 1);
names[i].swap(names[offset]);
}
}
}
void find_longest_chain(std::vector<std::string>& names) {
max_path_length = 0;
max_path_length_count = 0;
max_path_example.clear();
for (size_t i = 0, n = names.size(); i < n; ++i) {
names[i].swap(names[0]);
search(names, 1);
names[i].swap(names[0]);
}
}
};
int main() {
std::vector<std::string> 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"};
last_letter_first_letter solver;
solver.find_longest_chain(names);
std::cout << "Maximum path length: " << solver.max_path_length << '\n';
std::cout << "Paths of that length: " << solver.max_path_length_count << '\n';
std::cout << "Example path of that length:\n ";
for (size_t i = 0, n = solver.max_path_example.size(); i < n; ++i) {
if (i > 0 && i % 7 == 0)
std::cout << "\n ";
else if (i > 0)
std::cout << ' ';
std::cout << solver.max_path_example[i];
}
std::cout << '\n';
}</syntaxhighlight>
{{out}}
<pre>
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
</pre>
=={{header|Clojure}}==
<syntaxhighlight lang="clojure">(ns rosetta-code.last-letter-first-letter
(:require clojure.string))
(defn by-first-letter
"Returns a map from letters to a set of words that start with that letter"
[words]
(into {} (map (fn [[k v]]
[k (set v)]))
(group-by first words)))
(defn longest-path-from
"Find a longest path starting at word, using only words-by-first-letter for successive words.
Returns a pair of [length list-of-words] to describe the path."
[word words-by-first-letter]
(let [words-without-word (update words-by-first-letter (first word)
disj word)
next-words (words-without-word (last word))]
(if (empty? next-words)
[1 [word]]
(let [sub-paths (map #(longest-path-from % words-without-word) next-words)
[length words-of-path] (apply max-key first sub-paths)]
[(inc length) (cons word words-of-path)]))))
(defn longest-word-chain
"Find a longest path among the words in word-list, by performing a longest path search
starting at each word in the list."
[word-list]
(let [words-by-letter (by-first-letter word-list)]
(apply max-key first
(pmap #(longest-path-from % words-by-letter)
word-list))))
(defn word-list-from-file [file-name]
(let [contents (slurp file-name)
words (clojure.string/split contents #"[ \n]")]
(filter #(not (empty? %)) words)))
(time (longest-word-chain (word-list-from-file "pokemon.txt")))</syntaxhighlight>
Evaluating the last line:
<syntaxhighlight lang="clojure">"Elapsed time: 2867.337816 msecs"
[23
("machamp"
"pinsir"
"relicanth"
"heatmor"
"registeel"
"landorus"
"seaking"
"girafarig"
"gabite"
"exeggcute"
"emboar"
"rufflet"
"trapinch"
"haxorus"
"simisear"
"remoraid"
"darmanitan"
"nosepass"
"scrafty"
"yamask"
"kricketune"
"emolga"
"audino")]</syntaxhighlight>
It initially ran in about 5 seconds, then I changed <code>map</code> to <code>pmap</code> (parallel map) in <code>longest-word-chain</code>.
This gave a nice speedup for a dual core laptop; the speedup for parallel searches was over 3x on a server.
=={{header|Common Lisp}}==
Pretty brute force here. Takes a couple of seconds to run.
<
(defun filter-with-init (words init)
Line 1,087 ⟶ 1,316:
tyrogue vigoroth vulpix wailord wartortle whismur wingull yamask)))
(setf *path* (best-path *words*))</
Output:<syntaxhighlight lang="text">("MACHAMP" "PETILIL" "LANDORUS" "SCRAFTY" "YAMASK" "KRICKETUNE" "EMBOAR" "REGISTEEL"
"LOUDRED" "DARMANITAN" "NOSEPASS" "SIMISEAR" "RELICANTH" "HEATMOR" "RUFFLET"
"TRAPINCH" "HAXORUS" "SEAKING" "GIRAFARIG" "GABITE" "EXEGGCUTE" "EMOLGA" "AUDINO")</
=={{header|D}}==
===Simple Version===
Modified from the Go version:
<
void trySwap(string[] items, ref string item, in size_t len, ref string[] longest)
Line 1,130 ⟶ 1,360:
writefln("%-(%s\n%)", solution);
}</
Output:
<pre>machamp
Line 1,159 ⟶ 1,389:
===Improved Version===
With two small changes the code gets faster. Here the names are represented as in C (so swapping them means just swapping a pointer, instead of swapping a pointer+length as before), and during the computation their last char is swapped with their second char (so there's no need to keep the string lengths around or use strlen).
<
void search(immutable(char)*[] items, in int len,
Line 1,207 ⟶ 1,437:
writefln("%-(%s\n%)", solution.map!unprep);
}</
This leads to tight enough code for the foreach loop in the search function:
<
movl (%esi), %eax
movb 19(%esp), %cl
Line 1,234 ⟶ 1,464:
addl $4, %esi
decl %ebp
jne LBB0_4</
The run-time is about 0.65 seconds with LDC2 compiler. The output is similar.
===Faster Version===
<
Tuple!(uint, string[]) findLongestChain(in string[] words)
Line 1,320 ⟶ 1,550:
writeln("Example path of that length:");
writefln("%( %-(%s %)\n%)", sol[1].chunks(7));
}</
{{out}}
<pre>Maximum path length: 23
Line 1,333 ⟶ 1,563:
===Alternative Version===
{{trans|PicoLisp}}
<
std.container, std.range;
Line 1,371 ⟶ 1,601:
spoink starly tirtouga trapinch treecko tyrogue vigoroth vulpix
wailord wartortle whismur wingull yamask".split.findChain.writeln;
}</
{{out}}
<pre>["machamp", "petilil", "landorus", "scrafty", "yamask", "kricketune", "emboar", "registeel", "loudred", "darmanitan", "nosepass", "simisear", "relicanth", "heatmor", "rufflet", "trapinch", "haxorus", "seaking", "girafarig", "gabite", "exeggcute", "emolga", "audino"]</pre>
Line 1,378 ⟶ 1,608:
=={{header|Delphi}}==
Visual implementation, this unit is a VCL Form with a Memo, a Button, a Checkbox, a DataGrid, a DBMemo, a DataSource and a ClientDataSet with tree fields (length integer,count integer,list memo):
<
interface
Line 1,654 ⟶ 1,884:
end;
end.</
Runtime varies depending if you run the "optimized" version or not. Ranges from 6 to 18 seconds.
NOTE: "optimized" version is actually a different algorithm, but in most cases returns the same results.
=={{header|EasyLang}}==
<syntaxhighlight>
repeat
s$ = input
until s$ = ""
for n$ in strsplit s$ " "
pok$[] &= n$
.
.
#
chain$[] = [ ]
proc search lng . .
if lng > len chain$[]
chain$[] = [ ]
for j to lng
chain$[] &= pok$[j]
.
.
lastc$ = substr pok$[lng] len pok$[lng] 1
for i = lng + 1 to len pok$[]
if substr pok$[i] 1 1 = lastc$
swap pok$[i] pok$[lng + 1]
search lng + 1
swap pok$[i] pok$[lng + 1]
.
.
.
for i to len pok$[]
swap pok$[i] pok$[1]
search 1
swap pok$[i] pok$[1]
.
for p$ in chain$[]
write p$ & " "
.
#
input_data
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
</syntaxhighlight>
{{out}}
<pre>
machamp petilil landorus scrafty yamask kricketune emboar registeel loudred darmanitan nosepass simisear relicanth heatmor rufflet trapinch haxorus seaking girafarig gabite exeggcute emolga audino
</pre>
=={{header|Elixir}}==
{{trans|Ruby}}
<
def search(names) do
first = Enum.group_by(names, &String.first/1)
Line 1,698 ⟶ 1,979:
)
LastLetter_FirstLetter.search(names)</
{{out}}
Line 1,732 ⟶ 2,013:
=={{header|Erlang}}==
This is a parallel version. It takes 2.1 seconds. The (commented out) serial version takes 7.1 seconds. Both times measured on my (low end) Mac Mini. I thought parallel code would help in getting the brownie points. But even a small increase to 100 Pokemons makes the code run for more than the few spare hours I have in the evening.
<syntaxhighlight lang="erlang">
-module( last_letter_first_letter ).
Line 1,783 ⟶ 2,064:
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">>.
</syntaxhighlight>
{{out}}
<pre>
Line 1,797 ⟶ 2,078:
=={{header|Go}}==
Depth first, starting with each possible name.
<
import (
Line 1,852 ⟶ 2,133:
}
}
}</
Output:
<pre>
Line 1,867 ⟶ 2,148:
=={{header|Haskell}}==
Note: This takes ~80 seconds to complete on my machine.
<
import qualified Data.ByteString.Char8 as B
Line 1,889 ⟶ 2,170:
isLink pl pr = B.last pl == B.head pr
main = mapM_ B.putStrLn $ growChains $ map (\x -> [x]) allPokemon</
Output:
<pre>machamp
Line 1,915 ⟶ 2,196:
audino</pre>
A simpler version (no ByteString), about 2.4 times slower (GHC -O3), same output:
<
allPokemon = words
Line 1,935 ⟶ 2,216:
isLink pl pr = last pl == head pr
main = mapM_ putStrLn $ growChains $ map (\x -> [x]) allPokemon</
=={{header|Icon}} and {{header|Unicon}}==
Line 1,941 ⟶ 2,222:
Works in both languages (brute force):
<
procedure main()
Line 1,964 ⟶ 2,245:
while l := !f do
l ? while tab(upto(&letters)) do suspend tab(many(&letters))\1
end</
Sample run on sample data:
Line 1,977 ⟶ 2,258:
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.
<
audino bagon baltoy banette bidoof braviary bronzor carracosta charmeleon
cresselia croagunk darmanitan deino emboar emolga exeggcute gabite
Line 1,997 ⟶ 2,278:
end.
r
)</
The line <code>assert. 1e9>*/8,$r</code> 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. Note that [http://www.jsoftware.com/help/dictionary/dx009.htm 9!:21 and/or 9!:33] could also be used to prevent OS instability triggered by requesting too many resources.
Line 2,003 ⟶ 2,284:
With this procedure we are able to conduct the entire search for this list of names:
<
1248 23</
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:
<
machamp
petilil
Line 2,031 ⟶ 2,312:
exeggcute
emolga
audino </
=={{header|Java}}==
<
final class LastLetterFirstLetter {
static int maxPathLength = 0;
Line 2,094 ⟶ 2,375:
}
}
</syntaxhighlight>
Output:<pre>maximum path length : 23
Line 2,104 ⟶ 2,385:
simisear registeel landorus seaking girafarig
gabite emolga audino
</pre>
=={{header|JavaScript}}==
{{Works with|Node.js}} (Required for the ''process'' object)
<syntaxhighlight lang="javascript">/**
* Find the letter the word ends on
* @param {string} word
* @returns {string}
*/
const endsWith = word => word[word.length - 1];
/**
* Remove the used elements from the candidate elements
* @param {Array<string>} words Candidate words
* @param {Array<string>} used Used words
* @returns {*}
*/
const getCandidates = (words, used) => words.filter(e => !used.includes(e));
/**
* Build a map of letters to words that start with that letter
* @param {Array<string>} words
* @returns {Map<string, Array<string>>}
*/
const buildLookup = words => {
const lookup = new Map();
words.forEach(e => {
const start = e[0];
lookup.set(start, [...(lookup.get(start) || []), e]);
});
return lookup;
};
/**
* Main function
* @param {Array<string>} names
*/
const findPaths = names => {
const t0 = process.hrtime();
console.log('Checking:', names.length, 'names');
const lookup = buildLookup(names);
let maxNum = 0;
let maxPaths = [];
const parseResult = arr => {
if (typeof arr[0] === 'object') {
arr.forEach(el => parseResult(el))
} else {
if (arr.length > maxNum) {
maxNum = arr.length;
maxPaths = [arr];
}
if (arr.length === maxNum) {
maxPaths.push(arr)
}
}
};
const searchWords = (word, res) => {
const cs = getCandidates(lookup.get(endsWith(word)) || [], res);
return cs.length ? cs.map(e => searchWords(e, [...res, e])) : res;
};
names.forEach(word => {
const res = searchWords(word, [word]);
parseResult(res);
});
const t1 = process.hrtime(t0);
console.info('Execution time (hr): %ds %dms', t1[0], t1[1] / 1000000);
console.log('Max Path:', maxNum);
console.log('Matching Paths:', maxPaths.length);
console.log('Example Path:', maxPaths[0]);
};
const pokimon = ["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"];
findPaths(pokimon);
</syntaxhighlight>
<pre>
Checking: 70 names
Execution time (hr): 2s 121.778223ms
Max Path: 23
Matching Paths: 1249
Example Path: [
'machamp',
'petilil',
'landorus',
'scrafty',
'yamask',
'kricketune',
'emboar',
'registeel',
'loudred',
'darmanitan',
'nosepass',
'simisear',
'relicanth',
'heatmor',
'rufflet',
'trapinch',
'haxorus',
'seaking',
'girafarig',
'gabite',
'exeggcute',
'emolga',
'audino' ]
</pre>
Line 2,113 ⟶ 2,519:
'''Utility functions''':
<
def dictionary:
reduce .[] as $word ({}; .[$word[0:1]] += [$word]) ;
Line 2,119 ⟶ 2,525:
# remove "word" from the input dictionary assuming the key is already there:
def remove(word):
.[word[0:1]] -= [word];</
'''The last-letter/first-letter game''':
<
def admissible:
.[0][-1:] == .[1][0:1];
Line 2,162 ⟶ 2,568:
# If your jq does not include "debug", simply remove or comment-out the following line:
| ([$name, $ans[0]] | debug) as $debug
| if $ans[0] > .[0] then $ans else . end );</
'''Example''':
<
["audino", "bagon", "baltoy", "banette",
"bidoof", "braviary", "bronzor", "carracosta", "charmeleon",
Line 2,180 ⟶ 2,586:
"wailord", "wartortle", "whismur", "wingull", "yamask" ] ;
names | maximal</
{{out}} (scrollable)
The "DEBUG" lines are included to illustrate how progress can be monitored. They show the maximal length for the indicated initial word.
<div style="overflow:scroll; height:400px;">
<
["DEBUG:",["audino",1]]
["DEBUG:",["bagon",20]]
Line 2,283 ⟶ 2,689:
"audino"
]
]</
=={{header|Julia}}==
Line 2,289 ⟶ 2,695:
{{trans|Python}}
<
orderwords(words::Vector) = Dict(w[1][1] => Set(w) for w in groupby(first, words))
Line 2,325 ⟶ 2,731:
l = llfl(pokemon)
println("Example of longest seq.:\n", join(l, ", "))
println("Max length: ", length(l)</
{{out}}
Line 2,334 ⟶ 2,740:
=={{header|Kotlin}}==
{{trans|Java}}
<
var maxPathLength = 0
Line 2,395 ⟶ 2,801:
println("Paths of that length : $maxPathLengthCount")
println("Example path of that length : $maxPathExample")
}</
{{out}}
Line 2,408 ⟶ 2,814:
gabite emolga audino
</pre>
=={{header|Lua}}==
In lieu of the poorly-specified extra-credit portion (e.g. are the two Nidoran's to be considered same or unique?), I chose to expand on the output portion of the core task.
<syntaxhighlight lang="lua">-- BUILDING:
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]]
words, inits, succs = {}, {}, {}
for word in pokemon:gmatch("%S+") do
table.insert(words, word)
local ch = word:sub(1,1)
inits[ch] = inits[ch] or {}
table.insert(inits[ch], word)
end
for _,word in pairs(words) do
succs[word] = {}
local ch = word:sub(-1,-1)
if inits[ch] then
for _,succ in pairs(inits[ch]) do
if succ~=word then
table.insert(succs[word],succ)
end
end
end
end
-- SEARCHING:
function expand(list, used, answer)
local word = list[#list]
for _,succ in ipairs(succs[word]) do
if not used[succ] then
used[succ] = true
list[#list+1] = succ
if #list == answer.len then
local perm = table.concat(list," ")
answer.perms[perm] = perm
answer.num = answer.num + 1
elseif #list > answer.len then
answer.len = #list
local perm = table.concat(list," ")
answer.perms = {[perm] = perm}
answer.num = 1
end
expand(list, used, answer)
list[#list] = nil
used[succ] = nil
end
end
end
answers = {}
for _,word in ipairs(words) do
local answer = { word=word, len=0, num=0, perms={} }
answers[#answers+1] = answer
expand({word}, {[word]=true}, answer)
end
-- REPORTING:
table.sort(answers, function(a,b) return a.len<b.len or (a.len==b.len and a.word<b.word) end)
print("first word length count example")
print("---------- ------ ----- -------...")
for _,answer in pairs(answers) do
local perm = next(answer.perms) or ""
print(string.format("%10s %6d %5d %s", answer.word, answer.len, answer.num, perm))
end</syntaxhighlight>
{{out}}
<pre>first word length count example
---------- ------ ----- -------...
audino 0 0
bidoof 0 0
deino 0 0
jumpluff 0 0
pidgeotto 0 0
pikachu 0 0
porygon2 0 0
porygonz 0 0
sealeo 0 0
snorlax 0 0
treecko 0 0
vulpix 0 0
carracosta 2 1 carracosta audino
cresselia 2 1 cresselia audino
emolga 2 1 emolga audino
ledyba 2 1 ledyba audino
poochyena 2 1 poochyena audino
tirtouga 2 1 tirtouga audino
emboar 19 96 emboar relicanth heatmor rufflet trapinch haxorus simisear registeel landorus seaking girafarig gulpin nosepass scrafty yamask kricketune exeggcute emolga audino
exeggcute 19 96 exeggcute emboar relicanth haxorus seaking girafarig gulpin nosepass simisear rufflet trapinch heatmor registeel landorus snivy yamask kricketune emolga audino
nosepass 19 192 nosepass snivy yamask kricketune exeggcute emboar rufflet trapinch heatmor registeel landorus simisear relicanth haxorus seaking girafarig gabite emolga audino
bagon 20 192 bagon nosepass simisear relicanth heatmor rufflet trapinch haxorus scrafty yamask kricketune emboar registeel landorus seaking girafarig gabite exeggcute emolga audino
banette 20 192 banette exeggcute emboar relicanth heatmor registeel landorus starly yamask kangaskhan nosepass simisear rufflet trapinch haxorus seaking girafarig gabite emolga audino
charmeleon 20 192 charmeleon nosepass simisear relicanth heatmor rufflet trapinch haxorus seaking girafarig gabite emboar registeel landorus starly yamask kricketune exeggcute emolga audino
darmanitan 20 192 darmanitan nosepass seaking girafarig gabite exeggcute emboar relicanth haxorus simisear rufflet trapinch heatmor registeel landorus starly yamask kricketune emolga audino
gabite 20 96 gabite emboar rufflet trapinch heatmor relicanth haxorus simisear registeel landorus seaking girafarig gulpin nosepass snivy yamask kricketune exeggcute emolga audino
girafarig 20 480 girafarig gabite emboar registeel landorus spoink kangaskhan nosepass simisear rufflet trapinch heatmor relicanth haxorus snivy yamask kricketune exeggcute emolga audino
gulpin 20 192 gulpin nosepass simisear rufflet trapinch heatmor relicanth haxorus snivy yamask kricketune emboar registeel landorus seaking girafarig gabite exeggcute emolga audino
haxorus 20 288 haxorus starly yamask kricketune exeggcute emboar registeel landorus simisear rufflet trapinch heatmor remoraid darmanitan nosepass seaking girafarig gabite emolga audino
heatmor 20 432 heatmor rufflet trapinch heatran nosepass simisear relicanth haxorus seaking girafarig gabite emboar registeel landorus starly yamask kricketune exeggcute emolga audino
heatran 20 192 heatran nosepass simisear relicanth haxorus seaking girafarig gabite exeggcute emboar rufflet trapinch heatmor registeel landorus starly yamask kricketune emolga audino
kangaskhan 20 192 kangaskhan nosepass seaking girafarig gabite exeggcute emboar relicanth haxorus simisear rufflet trapinch heatmor registeel landorus starly yamask kricketune emolga audino
kricketune 20 96 kricketune exeggcute emboar relicanth heatmor rufflet trapinch haxorus simisear registeel landorus scrafty yamask kangaskhan nosepass seaking girafarig gabite emolga audino
lumineon 20 192 lumineon nosepass seaking girafarig gabite exeggcute emboar rufflet trapinch heatmor relicanth haxorus simisear registeel landorus starly yamask kricketune emolga audino
lunatone 20 192 lunatone emboar rufflet trapinch heatmor registeel landorus starly yamask kangaskhan nosepass simisear relicanth haxorus seaking girafarig gabite exeggcute emolga audino
magnezone 20 192 magnezone exeggcute emboar registeel landorus snivy yamask kangaskhan nosepass simisear relicanth heatmor rufflet trapinch haxorus seaking girafarig gabite emolga audino
mamoswine 20 192 mamoswine exeggcute emboar relicanth haxorus seaking girafarig gulpin nosepass simisear rufflet trapinch heatmor registeel landorus snivy yamask kricketune emolga audino
sableye 20 192 sableye emboar relicanth heatmor registeel landorus simisear rufflet trapinch haxorus seaking girafarig gulpin nosepass starly yamask kricketune exeggcute emolga audino
scolipede 20 192 scolipede exeggcute emboar relicanth haxorus seaking girafarig gulpin nosepass simisear rufflet trapinch heatmor registeel landorus snivy yamask kricketune emolga audino
silcoon 20 192 silcoon nosepass simisear rufflet trapinch haxorus scrafty yamask kricketune exeggcute emboar relicanth heatmor registeel landorus seaking girafarig gabite emolga audino
trapinch 20 576 trapinch heatmor registeel landorus simisear remoraid darmanitan nosepass scrafty yamask kricketune exeggcute emboar relicanth haxorus seaking girafarig gabite emolga audino
tyrogue 20 192 tyrogue emboar rufflet trapinch heatmor registeel landorus seaking girafarig gulpin nosepass simisear relicanth haxorus snivy yamask kricketune exeggcute emolga audino
wartortle 20 192 wartortle exeggcute emboar registeel landorus snivy yamask kangaskhan nosepass simisear relicanth heatmor rufflet trapinch haxorus seaking girafarig gabite emolga audino
yamask 20 96 yamask kangaskhan nosepass seaking girafarig gabite emboar rufflet trapinch heatmor registeel landorus simisear relicanth haxorus spoink kricketune exeggcute emolga audino
baltoy 21 96 baltoy yamask kangaskhan nosepass simisear rufflet trapinch heatmor relicanth haxorus seaking girafarig gabite exeggcute emboar registeel landorus spoink kricketune emolga audino
braviary 21 96 braviary yamask kangaskhan nosepass seaking girafarig gabite exeggcute emboar relicanth haxorus simisear rufflet trapinch heatmor registeel landorus spoink kricketune emolga audino
croagunk 21 288 croagunk kangaskhan nosepass seaking girafarig gabite emboar rufflet trapinch heatmor registeel landorus simisear relicanth haxorus starly yamask kricketune exeggcute emolga audino
jellicent 21 768 jellicent trapinch haxorus seaking girafarig gabite exeggcute emboar relicanth heatmor remoraid darmanitan nosepass simisear registeel landorus snivy yamask kricketune emolga audino
landorus 21 192 landorus seaking girafarig gabite emboar relicanth heatmor rufflet trapinch haxorus simisear registeel loudred darmanitan nosepass starly yamask kricketune exeggcute emolga audino
loudred 21 192 loudred darmanitan nosepass seaking girafarig gabite exeggcute emboar rufflet trapinch haxorus simisear relicanth heatmor registeel landorus snivy yamask kricketune emolga audino
poliwrath 21 912 poliwrath heatmor remoraid darmanitan nosepass simisear registeel landorus seaking girafarig gabite exeggcute emboar rufflet trapinch haxorus scrafty yamask kricketune emolga audino
registeel 21 192 registeel landorus simisear rufflet trapinch heatmor remoraid darmanitan nosepass seaking girafarig gabite exeggcute emboar relicanth haxorus starly yamask kricketune emolga audino
relicanth 21 240 relicanth heatmor rufflet trapinch haxorus simisear registeel landorus seaking girafarig gabite exeggcute emboar remoraid darmanitan nosepass starly yamask kricketune emolga audino
remoraid 21 192 remoraid darmanitan nosepass simisear relicanth heatmor registeel landorus scrafty yamask kricketune exeggcute emboar rufflet trapinch haxorus seaking girafarig gabite emolga audino
rufflet 21 240 rufflet trapinch heatmor remoraid darmanitan nosepass seaking girafarig gabite emboar registeel landorus simisear relicanth haxorus starly yamask kricketune exeggcute emolga audino
scrafty 21 96 scrafty yamask kricketune exeggcute emboar rufflet trapinch heatmor relicanth haxorus spoink kangaskhan nosepass simisear registeel landorus seaking girafarig gabite emolga audino
seaking 21 192 seaking girafarig gabite emboar rufflet trapinch heatmor relicanth haxorus simisear registeel landorus snivy yamask kangaskhan nosepass spoink kricketune exeggcute emolga audino
simisear 21 384 simisear rufflet trapinch haxorus spoink kricketune exeggcute emboar relicanth heatmor registeel landorus snivy yamask kangaskhan nosepass seaking girafarig gabite emolga audino
snivy 21 96 snivy yamask kricketune exeggcute emboar registeel landorus simisear rufflet trapinch heatmor relicanth haxorus spoink kangaskhan nosepass seaking girafarig gabite emolga audino
spoink 21 288 spoink kangaskhan nosepass snivy yamask kricketune emboar relicanth heatmor rufflet trapinch haxorus simisear registeel landorus seaking girafarig gabite exeggcute emolga audino
starly 21 96 starly yamask kangaskhan nosepass simisear rufflet trapinch heatmor relicanth haxorus seaking girafarig gabite exeggcute emboar registeel landorus spoink kricketune emolga audino
vigoroth 21 912 vigoroth haxorus simisear registeel landorus starly yamask kricketune exeggcute emboar rufflet trapinch heatmor remoraid darmanitan nosepass seaking girafarig gabite emolga audino
wailord 21 192 wailord darmanitan nosepass seaking girafarig gabite exeggcute emboar rufflet trapinch haxorus simisear relicanth heatmor registeel landorus snivy yamask kricketune emolga audino
bronzor 22 864 bronzor registeel landorus seaking girafarig gabite emboar rufflet trapinch heatmor remoraid darmanitan nosepass simisear relicanth haxorus snivy yamask kricketune exeggcute emolga audino
ivysaur 22 864 ivysaur registeel landorus seaking girafarig gabite emboar rufflet trapinch heatmor remoraid darmanitan nosepass simisear relicanth haxorus snivy yamask kricketune exeggcute emolga audino
petilil 22 384 petilil landorus simisear rufflet trapinch heatmor relicanth haxorus starly yamask kricketune exeggcute emboar registeel loudred darmanitan nosepass seaking girafarig gabite emolga audino
pinsir 22 864 pinsir rufflet trapinch heatmor registeel landorus seaking girafarig gabite exeggcute emboar relicanth haxorus simisear remoraid darmanitan nosepass snivy yamask kricketune emolga audino
whismur 22 864 whismur registeel landorus seaking girafarig gabite emboar rufflet trapinch heatmor remoraid darmanitan nosepass simisear relicanth haxorus snivy yamask kricketune exeggcute emolga audino
wingull 22 384 wingull landorus snivy yamask kricketune emboar rufflet trapinch haxorus simisear relicanth heatmor registeel loudred darmanitan nosepass seaking girafarig gabite exeggcute emolga audino
machamp 23 1248 machamp petilil landorus simisear relicanth haxorus starly yamask kricketune exeggcute emboar rufflet trapinch heatmor registeel loudred darmanitan nosepass seaking girafarig gabite emolga audino</pre>
=={{header|Mathematica}}/{{header|Wolfram Language}}==
<
NestWhileList[
Append @@@
Line 2,430 ⟶ 2,978:
"snorlax", "spoink", "starly", "tirtouga", "trapinch", "treecko",
"tyrogue", "vigoroth", "vulpix", "wailord", "wartortle",
"whismur", "wingull", "yamask"}]];</
Uses the tactic of only checking chains with the same starting and ending values.
{{out}}
<pre>{baltoy, yamask, kangaskhan, nosepass, sableye, emboar, registeel, landorus, scolipede, emolga, audino}</pre>
=={{header|Nim}}==
Using bit sets of indexes. The program runs in 0.5s.
<syntaxhighlight lang="nim">import tables
const 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"]
type
Index = range[0..Names.len-1]
IndexSet = set[Index]
Successors = Table[Index, IndexSet]
const All = {Index.low..Index.high} # All indexes.
func initSuccessors(): Successors {.compileTime.} =
## Build the mapping from name indexes to set of possible successor indexes.
var names: Table[char, IndexSet] # Map first char to IndexSet.
for idx, name in Names:
names.mgetOrPut(name[0], {}).incl(idx)
for idx, name in Names:
result[idx] = names.getOrDefault(name[^1]) - {idx}
# Mapping name index -> set of successor indexes.
const Succ = initSuccessors()
proc search(starts, available: IndexSet): seq[Index] =
## Search one of the longest sequence of indexes for given
## starting indexes and given available name indexes.
var maxLen = -1
for idx in starts * available:
let list = search(Succ[idx], available - {idx})
if list.len > maxLen:
result = idx & list
maxLen = list.len
let list = search(starts = All, available = All)
echo "Longest lists have length: ", list.len
echo "One of these lists is:"
for idx in list: echo Names[idx]</syntaxhighlight>
{{out}}
<pre>Longest lists have length: 23
One of these lists is:
machamp
petilil
landorus
scrafty
yamask
kricketune
emboar
registeel
loudred
darmanitan
nosepass
simisear
relicanth
heatmor
rufflet
trapinch
haxorus
seaking
girafarig
gabite
exeggcute
emolga
audino</pre>
=={{header|ooRexx}}==
<syntaxhighlight lang="oorexx">
-- create the searcher and run it
searcher = .chainsearcher~new
Line 2,511 ⟶ 3,139:
end
end
</syntaxhighlight>
<pre>
searching 70 names...
Line 2,545 ⟶ 3,173:
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...
<
cresselia croagunk darmanitan deino emboar emolga exeggcute gabite ~
girafarig gulpin haxorus heatmor heatran ivysaur jellicent jumpluff kangaskhan ~
Line 2,628 ⟶ 3,256:
IF lcontinue = FALSE THEN
STOP.
END.</
Output:
Line 2,644 ⟶ 3,272:
Yes No
---------------------------</pre>
=={{header|Perl}}==
Line 2,680 ⟶ 3,282:
*@m keeps the longest sequence which is copied from @w;
*to prevent the words from appearing twice, they are (temporarily) deleted from the structure keeping the value in a stack variable.
<syntaxhighlight lang="perl">use strict;
my(%f,@m);
audino bagon baltoy banette bidoof braviary bronzor carracosta charmeleon
cresselia croagunk darmanitan deino emboar emolga exeggcute gabite
Line 2,692 ⟶ 3,296:
);
sub poke {
our @w;
}
}
poke($_) for keys %f;
print @m.": @m\n";</
{{out}}
<pre>23: machamp petilil landorus seaking girafarig gabite emboar registeel loudred darmanitan nosepass simisear relicanth heatmor rufflet trapinch haxorus scrafty yamask kricketune exeggcute emolga audino</pre>
=={{header|Phix}}==
Using simple start-with-same-letter word chains to minimise the number of elements we have to consider:
<!--<syntaxhighlight lang="phix">(phixonline)-->
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #008080;">constant</span> <span style="color: #000000;">words</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #008000;">"audino"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"bagon"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"baltoy"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"banette"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"bidoof"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"braviary"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"bronzor"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"carracosta"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"charmeleon"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"cresselia"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"croagunk"</span><span style="color: #0000FF;">,</span>
<span style="color: #008000;">"darmanitan"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"deino"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"emboar"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"emolga"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"exeggcute"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"gabite"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"girafarig"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"gulpin"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"haxorus"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"heatmor"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"heatran"</span><span style="color: #0000FF;">,</span>
<span style="color: #008000;">"ivysaur"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"jellicent"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"jumpluff"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"kangaskhan"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"kricketune"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"landorus"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"ledyba"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"loudred"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"lumineon"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"lunatone"</span><span style="color: #0000FF;">,</span>
<span style="color: #008000;">"machamp"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"magnezone"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"mamoswine"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"nosepass"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"petilil"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"pidgeotto"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"pikachu"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"pinsir"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"poliwrath"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"poochyena"</span><span style="color: #0000FF;">,</span>
<span style="color: #008000;">"porygon2"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"porygonz"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"registeel"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"relicanth"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"remoraid"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"rufflet"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"sableye"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"scolipede"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"scrafty"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"seaking"</span><span style="color: #0000FF;">,</span>
<span style="color: #008000;">"sealeo"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"silcoon"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"simisear"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"snivy"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"snorlax"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"spoink"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"starly"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"tirtouga"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"trapinch"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"treecko"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"tyrogue"</span><span style="color: #0000FF;">,</span>
<span style="color: #008000;">"vigoroth"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"vulpix"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"wailord"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"wartortle"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"whismur"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"wingull"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"yamask"</span><span style="color: #0000FF;">}</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">word_chains</span><span style="color: #0000FF;">()</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">first</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">256</span><span style="color: #0000FF;">),</span> <span style="color: #000080;font-style:italic;">-- start of chains for a given letter
-- first['a']=1, first['b']=2, first['c']=8, etc.</span>
<span style="color: #000000;">snext</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">words</span><span style="color: #0000FF;">))</span> <span style="color: #000080;font-style:italic;">-- chains of words starting with the same letter
-- a: snext[1]=0, b: snext[2..7]={3,4,5,6,7,0}, etc.</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">words</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">ch</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">words</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">][</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">first</span><span style="color: #0000FF;">[</span><span style="color: #000000;">ch</span><span style="color: #0000FF;">]=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">first</span><span style="color: #0000FF;">[</span><span style="color: #000000;">ch</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">i</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">j</span><span style="color: #0000FF;">=</span><span style="color: #000000;">i</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">words</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">words</span><span style="color: #0000FF;">[</span><span style="color: #000000;">j</span><span style="color: #0000FF;">][</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]=</span><span style="color: #000000;">ch</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">snext</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">j</span>
<span style="color: #008080;">exit</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">return</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">first</span><span style="color: #0000FF;">,</span><span style="color: #000000;">snext</span><span style="color: #0000FF;">}</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">constant</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">first</span><span style="color: #0000FF;">,</span><span style="color: #000000;">snext</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">word_chains</span><span style="color: #0000FF;">()</span>
<span style="color: #000080;font-style:italic;">-- maintain words already taken as a linked list:</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">tstart</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">taken</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">words</span><span style="color: #0000FF;">))</span> <span style="color: #000080;font-style:italic;">-- 0=no, -1=end of chain, +ve=next
-- and keep a copy of the best for later</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">bstart</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">best</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">maxn</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">count</span>
<span style="color: #008080;">procedure</span> <span style="color: #000000;">find_path</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">ch</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">last</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">next</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">first</span><span style="color: #0000FF;">[</span><span style="color: #000000;">ch</span><span style="color: #0000FF;">]</span>
<span style="color: #008080;">while</span> <span style="color: #000000;">next</span><span style="color: #0000FF;">!=</span><span style="color: #000000;">0</span> <span style="color: #008080;">do</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">taken</span><span style="color: #0000FF;">[</span><span style="color: #000000;">next</span><span style="color: #0000FF;">]=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">taken</span><span style="color: #0000FF;">[</span><span style="color: #000000;">last</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">next</span>
<span style="color: #000000;">taken</span><span style="color: #0000FF;">[</span><span style="color: #000000;">next</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">-</span><span style="color: #000000;">1</span>
<span style="color: #000000;">find_path</span><span style="color: #0000FF;">(</span><span style="color: #000000;">words</span><span style="color: #0000FF;">[</span><span style="color: #000000;">next</span><span style="color: #0000FF;">][$],</span><span style="color: #000000;">next</span><span style="color: #0000FF;">,</span><span style="color: #000000;">n</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">taken</span><span style="color: #0000FF;">[</span><span style="color: #000000;">last</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">-</span><span style="color: #000000;">1</span>
<span style="color: #000000;">taken</span><span style="color: #0000FF;">[</span><span style="color: #000000;">next</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #000000;">next</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">snext</span><span style="color: #0000FF;">[</span><span style="color: #000000;">next</span><span style="color: #0000FF;">]</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">></span><span style="color: #000000;">maxn</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">bstart</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">tstart</span>
<span style="color: #000000;">best</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">deep_copy</span><span style="color: #0000FF;">(</span><span style="color: #000000;">taken</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">maxn</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">n</span>
<span style="color: #000000;">count</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1</span>
<span style="color: #008080;">elsif</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">=</span><span style="color: #000000;">maxn</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">count</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span>
<span style="color: #004080;">atom</span> <span style="color: #000000;">t0</span><span style="color: #0000FF;">=</span><span style="color: #7060A8;">time</span><span style="color: #0000FF;">()</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">words</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">tstart</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">i</span>
<span style="color: #000000;">taken</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">-</span><span style="color: #000000;">1</span>
<span style="color: #000000;">find_path</span><span style="color: #0000FF;">(</span><span style="color: #000000;">words</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">][$],</span><span style="color: #000000;">i</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">taken</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"Runtime: %2.3f seconds. Max length:%d, found %d of such, one of which is:\n"</span><span style="color: #0000FF;">,{</span><span style="color: #7060A8;">time</span><span style="color: #0000FF;">()-</span><span style="color: #000000;">t0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">maxn</span><span style="color: #0000FF;">,</span><span style="color: #000000;">count</span><span style="color: #0000FF;">})</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{}</span>
<span style="color: #008080;">while</span> <span style="color: #000000;">bstart</span><span style="color: #0000FF;">!=-</span><span style="color: #000000;">1</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #000000;">res</span><span style="color: #0000FF;">,</span><span style="color: #000000;">words</span><span style="color: #0000FF;">[</span><span style="color: #000000;">bstart</span><span style="color: #0000FF;">])</span>
<span style="color: #000000;">bstart</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">best</span><span style="color: #0000FF;">[</span><span style="color: #000000;">bstart</span><span style="color: #0000FF;">]</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
<span style="color: #7060A8;">assert</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">res</span><span style="color: #0000FF;">)=</span><span style="color: #000000;">maxn</span><span style="color: #0000FF;">)</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%s\n"</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">join_by</span><span style="color: #0000FF;">(</span><span style="color: #000000;">res</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">10</span><span style="color: #0000FF;">,</span><span style="color: #008000;">" "</span><span style="color: #0000FF;">))</span>
<!--</syntaxhighlight>-->
{{out}}
<pre>
Runtime: 0.625 seconds. Max length:23, found 1248 of such, one of which is:
machamp petilil landorus scrafty yamask kricketune emboar registeel loudred darmanitan
nosepass simisear relicanth heatmor rufflet trapinch haxorus seaking girafarig gabite
exeggcute emolga audino
</pre>
My claim for the extra brownie points, using the list from the Racket entry:
<pre>
Runtime: 0.000 seconds. Max length:2, found 9 of such, one of which is:
Porygon-Z Zubat
</pre>
Which is quite correct: 9 names begin with 'Z', and plenty with 'T' but none with 't' ;-)<br>
Adding a couple of upper(), it found a 302 in a couple of minutes but was still on permutations starting
with word[1] when I got bored and killed it, quickly calculating at the very least another 4.5 days and
quite probably not finishing within my lifetime...
=={{header|Picat}}==
It's a little faster with the words sorted on decreasing lengths (<code>words2</code>): 9.43s vs 11.742s.
<syntaxhighlight lang="picat">go =>
words(Words),
% Words that starts with same letter as <this words>'s last letter.
Starts = new_map(),
foreach(Word in Words)
S = [ Word2 : Word2 in Words, Word != Word2, Word.last() = Word2.first()],
Starts.put(Word,S)
end,
% Sort the words according to lengths in decreasing order.
Words2 = [W : W=_ in Starts.map_to_list().qsort(sort_len)],
% Start the search
MaxLen = _,
Continue := true,
foreach(Len in 2..Words.len, break(Continue == false))
if play1(Words2,Starts,Len,_List) then
else
Continue := false
end
end,
println(maxLen=MaxLen),
% And present the result.
println("\nGet some (5) solutions:"),
get_some_solutions(Words2, Starts, MaxLen,5),
println("\nNnumber of optimal solutions:"),
NumSols = count_all(play1(Words2,Starts,MaxLen,_List)),
println(num_sols=NumSols),
nl.
% Check if it's possible to create a list of length Len.
play1(Words, Starts, Len, LLFL) :-
LLFL1 = new_list(Len),
select(LLFL1[1], Words, Rest),
C = 2,
while (C <= Len)
Among = Starts.get(LLFL1[C-1]),
Among != [],
select(Word,Among,Rest2),
not membchk(Word,LLFL1[1..C-1]),
LLFL1[C] := Word,
Rest := Rest2,
C := C + 1
end,
LLFL = LLFL1.
% Print NumSols solutions
get_some_solutions(Words,Starts,FoundLen,NumSols) =>
Map = get_global_map(),
Map.put(count,1),
play1(Words, Starts, FoundLen, LLFL),
println(LLFL),
C = Map.get(count),
if C < NumSols then Map.put(count,C+1), fail end.
% qsort(List, SortFunction)
% returns a sorted list according to the sort function SortFunction.
qsort([],_F) = [].
qsort([H|T],F) = qsort([E : E in T, call(F,E,H)], F)
% Sort according to length
sort_len((_K1=V1),(_K2=V2)) :-
V1.len >= V2.len.
words(Words) =>
Words =
[
"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"
].</syntaxhighlight>
{{out}}
<pre>maxLen = 23
Get some (5) solutions:
[machamp,petilil,landorus,scrafty,yamask,kricketune,emboar,registeel,loudred,darmanitan,nosepass,simisear,relicanth,heatmor,rufflet,trapinch,haxorus,seaking,girafarig,gabite,exeggcute,emolga,audino]
[machamp,petilil,landorus,scrafty,yamask,kricketune,emboar,registeel,loudred,darmanitan,nosepass,simisear,rufflet,trapinch,heatmor,relicanth,haxorus,seaking,girafarig,gabite,exeggcute,emolga,audino]
[machamp,petilil,landorus,scrafty,yamask,kricketune,emboar,relicanth,haxorus,simisear,rufflet,trapinch,heatmor,registeel,loudred,darmanitan,nosepass,seaking,girafarig,gabite,exeggcute,emolga,audino]
[machamp,petilil,landorus,scrafty,yamask,kricketune,emboar,relicanth,heatmor,registeel,loudred,darmanitan,nosepass,simisear,rufflet,trapinch,haxorus,seaking,girafarig,gabite,exeggcute,emolga,audino]
[machamp,petilil,landorus,scrafty,yamask,kricketune,emboar,relicanth,heatmor,rufflet,trapinch,haxorus,simisear,registeel,loudred,darmanitan,nosepass,seaking,girafarig,gabite,exeggcute,emolga,audino]
Nnumber of optimal solutions:
num_sols = 1248</pre>
=={{header|PicoLisp}}==
<syntaxhighlight 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) ) ) )</syntaxhighlight>
Test:
<pre>
: (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
</pre>
=={{header|Prolog}}==
Works with SWI-Prolog and module '''lambda.pl''' written by '''Ulrich Neumerkel''' found there http://www.complang.tuwien.ac.at/ulrich/Prolog-inedit/lambda.pl
<
:- dynamic res/3.
Line 2,960 ⟶ 3,621:
atom_chars(A, LC),
reverse(LC, [L | _]).
</syntaxhighlight>
Output :
<pre>?- time(last_first(Len, Nb, L)).
Line 2,970 ⟶ 3,631:
=={{header|Python}}==
<
def order_words(words):
Line 3,016 ⟶ 3,677:
l = llfl(pokemon)
for i in range(0, len(l), 8): print(' '.join(l[i:i+8]))
print(len(l))</
;Sample output
<pre>machamp pinsir relicanth heatmor remoraid darmanitan nosepass snivy
yamask kricketune exeggcute emboar registeel landorus simisear rufflet
trapinch haxorus seaking girafarig gabite emolga audino
23</pre>
===Alternative version===
Adapted from the D version. This uses Psyco.
<
nsolutions = 0
Line 3,099 ⟶ 3,760:
psyco.full()
main()</
Output:
<pre>Maximum path length: 23
Line 3,112 ⟶ 3,773:
=={{header|Racket}}==
This is a naive solution, which works fast enough as is (takes about 5 seconds on an old machine):
<
(define names "
Line 3,142 ⟶ 3,803:
(printf "Longest chain found has ~a words:\n ~a\n"
(length longest) (string-join (map word-string longest) " -> "))
</syntaxhighlight>
{{out}}
<pre>
Line 3,152 ⟶ 3,813:
chains using three different combination/relinking functions. Not that the
definiton of `word` is slightly different here.
<
(require "pokemon-names.rkt")
Line 3,334 ⟶ 3,995:
(time (longest-chain/constructive names-70 #:known-max 23))
(longest-chain/constructive names-646)</
Run with ''racket -t last_letter-first_letter-randomised.rkt 2>&1'', to redirect standard error to
Line 3,394 ⟶ 4,055:
Karrablast Throh Happiny Yanmega Armaldo) 333)</pre>
'''File: pokemon-names.rkt'''
<
(provide names-646 names-70)
(define names-70
Line 3,454 ⟶ 4,115:
Beartic Cryogonal Shelmet Accelgor Stunfisk Mienfoo Mienshao Druddigon Golett Golurk Pawniard Bisharp Bouffalant
Rufflet Braviary Vullaby Mandibuzz Heatmor Durant Deino Zweilous Hydreigon Larvesta Volcarona Cobalion Terrakion
Virizion Tornadus Thundurus Reshiram Zekrom Landorus Kyurem))</
=={{header|Raku}}==
(formerly Perl 6)
A breadth-first search that uses disk files to avoid memory exhaustion. Each candidate sequence is encoded at one character per name, so to avoid reuse of names we merely have to make sure there are no repeat characters in our encoded string. (The encoding starts at ASCII space for the first name, so newline is not among the encoded characters.)
<syntaxhighlight lang="raku" line>my @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
>;
my @last = @names.map: {.substr(*-1,1).ord }
my @succs = [] xx 128;
for @names.kv -> $i, $name {
my $ix = $name.ord; # $name.substr(0,1).ord
push @succs[$ix], $i;
}
my $OUT = open "llfl.new", :w orelse .die;
$OUT.print: chr($_ + 32),"\n" for 0 ..^ @names;
close $OUT;
my $new = +@names;
my $len = 1;
while $new {
say "Length { $len++ }: $new candidates";
shell 'mv llfl.new llfl.known';
my $IN = open "llfl.known" orelse .die;
my $OUT = open "llfl.new", :w orelse .die;
$new = 0;
loop {
my $cand = $IN.get // last;
for @succs[@last[$cand.ord - 32]][] -> $i {
my $ic = chr($i + 32);
next if $cand ~~ /$ic/;
$OUT.print: $ic,$cand,"\n";
$new++;
}
}
$IN.close;
$OUT.close;
}
my $IN = open "llfl.known" orelse .die;
my $eg = $IN.lines.pick;
say "Length of longest: ", $eg.chars;
say join ' ', $eg.ords.reverse.map: { @names[$_ - 32] }</syntaxhighlight>
{{out}}
<pre>Length 1: 70 candidates
Length 2: 172 candidates
Length 3: 494 candidates
Length 4: 1288 candidates
Length 5: 3235 candidates
Length 6: 7731 candidates
Length 7: 17628 candidates
Length 8: 37629 candidates
Length 9: 75122 candidates
Length 10: 139091 candidates
Length 11: 236679 candidates
Length 12: 367405 candidates
Length 13: 516210 candidates
Length 14: 650916 candidates
Length 15: 733915 candidates
Length 16: 727566 candidates
Length 17: 621835 candidates
Length 18: 446666 candidates
Length 19: 260862 candidates
Length 20: 119908 candidates
Length 21: 40296 candidates
Length 22: 10112 candidates
Length 23: 1248 candidates
Length of longest: 23
machamp petilil loudred darmanitan nosepass simisear rufflet trapinch heatmor registeel landorus starly yamask kricketune exeggcute emboar relicanth haxorus seaking girafarig gabite emolga audino</pre>
=={{header|REXX}}==
{{trans|ooRexx}}
===brute force version===
(This program is modeled after the ooRexx version, but with a
<br><br>This REXX version allows a limit on the word scan (very useful for testing and debugging), and
<br>also has various speed optimizations.
<
@='audino bagon baltoy banette bidoof braviary bronzor carracosta charmeleon cresselia croagunk darmanitan',
'deino emboar emolga exeggcute gabite girafarig gulpin haxorus heatmor heatran ivysaur jellicent',
Line 3,469 ⟶ 4,208:
'remoraid rufflet sableye scolipede scrafty seaking sealeo silcoon simisear snivy snorlax spoink',
'starly tirtouga trapinch treecko tyrogue vigoroth vulpix wailord wartortle whismur wingull yamask'
#= words(@); ig= 0; !.= 0; @.= /*nullify array and the longest path. */
parse arg limit .; if limit\=='' then #=limit /*allow user to specify a scan limit. */
call build@
do v=#
parse var @.
if !.1.F>1 | !.9.L>1 then iterate
end
$$$=
if ig\==0 then do; call build@; say; say 'ignoring'
MP= 0; MPL= 0 /*the initial Maximum Path Length. */
do j=1 for # /* ─ ─ ─ */
parse value @.1 @.j with @.j @.1; call scan $$$, 2
parse value @.1 @.j with @.j @.1
end /*j*/
g= words($$$)
say 'Of' # "words," MP 'path's(MP) "have the maximum path length of" g'.'
say; say 'One example path of that length is: ' word($$$, 1)
do m=2 to g; say left('', 36)
exit 0 /*stick a fork in it, we're all done. */
/*──────────────────────────────────────────────────────────────────────────────────────*/
s: if arg(1)==1 then return arg(3); return word( arg(2) 's', 1) /*a pluralizer.*/
/*──────────────────────────────────────────────────────────────────────────────────────*/
L=right(@.i, 1); !.9.L= !.9.L + 1 /*L: last " !.9.L= " " last " */
end /*i*/; return
/*──────────────────────────────────────────────────────────────────────────────────────*/
scan: procedure expose @. # !. $$$ MP MPL; parse arg $$$,!; p=! - 1
parse var @.p '' -1 LC /*obtain last character of previous @. */
if !.1.LC==0 then return /*is this a dead─end word? */
/* [↓] PARSE obtains first char of @.i*/
do i=! to #; parse var @.i p 2
if p==LC then do
if !==MPL then MP= MP+1
else if !>MPL then do;
$$$=$$$ @.i /*add last.*/
MP=1;
end
parse value @.! @.i with @.i @.!; call scan $$$, !+1
parse value @.! @.i with @.i @.!
end
end /*i*/; return /*exhausted this particular scan. */</syntaxhighlight>
{{out|output|text= when using the default input:}}
<pre>
Line 3,532 ⟶ 4,282:
emolga
audino
</pre>
===optimized version===
This optimized version has two major improvements:
::* removes dead words (words that cannot be used in a path)
::* stops scanning when a dead-end word is encountered.
With the full list of words being used, there are no dead words (but there are when a limit is used to shorten the list).
<br>In the '''scan''' subroutine, a check is made to see if the word being used is a dead-end word, and if so, the rest of
<br>the recursive scan is aborted and the the next word is scanned.
<br><br>The optimized version is around '''25%''' faster than the brute-force version.
<
@='audino bagon baltoy banette bidoof braviary bronzor carracosta charmeleon cresselia croagunk darmanitan',
'deino emboar emolga exeggcute gabite girafarig gulpin haxorus heatmor heatran ivysaur jellicent',
Line 3,550 ⟶ 4,299:
'remoraid rufflet sableye scolipede scrafty seaking sealeo silcoon simisear snivy snorlax spoink',
'starly tirtouga trapinch treecko tyrogue vigoroth vulpix wailord wartortle whismur wingull yamask'
#= words(@); @.=; @s=@.; ig=0; og=0; !.=0 /*nullify array and the longest path. */
parse arg limit .; if limit\=='' then #=
call build@ /*build a stemmed array from the @ list*/
do v=# by -1 for # /*scrub the @ list for
parse var @.v F 2 '' -1 L /*obtain first and last letter of word.*/
if !.1.F>1 | !.9.L>1 then iterate
say '
end /*v*/ /*delete dead word from @
#= words(@)
parse var @.v F 2 '' -1 L /*obtain first and last letter of word.*/
if !.1.L>0 then iterate /*is this a stop word? */
if @.v\=='' then say 'removing stop word:' @.v
og= og + 1; @= delword(@, v, 1); @s= @s @.v
end /*v*/ /*delete dead word from @ ──┘ */
if og\==0 then do; call build@; say; say 'ignoring' og "stop word"s(og).
say 'stop words: ' @s; say
end
MP= 0; MPL= 0 /*the initial Maximum Path Length. */
do j=1 for # /* ─ ─ ─ */
parse value @.1 @.j with @.j @.1; call scan $$$, 2
parse value @.1 @.j with @.j @.1
end /*j*/
g= words($$$)
say 'Of' # "words," MP 'path's(MP) "have the maximum path length of" g'.'
say;
do m=2 to g; say left('', 36)
end /*m*/
exit /*stick a fork in it, we're all done. */
/*──────────────────────────────────────────────────────────────────────────────────────*/
s: if arg(1)==1 then return arg(3); return word( arg(2) 's', 1) /*a pluralizer.*/
/*──────────────────────────────────────────────────────────────────────────────────────*/
L= right(@.i, 1); !.9.L= !.9.L + 1 /*L: last " !.9.L= " " last " */
end /*i*/; return
/*──────────────────────────────────────────────────────────────────────────────────────*/
scan: procedure expose @. # !. $$$ MP MPL; parse arg $$$,!; p= ! - 1
parse var @.p '' -1 LC /*obtain last character of previous @. */
if !.1.LC==0 then return /*is this a dead─end word? */
/* [↓] PARSE obtains first char of @.i*/
do i=! to #; parse var @.i p 2 /*scan for the longest word path. */
if p==LC then do /*is the first─character ≡ last─char? */
if !==MPL then MP= MP+1
else if !>MPL then do; $$$= @.1
do n=2 for !-2; $$$=$$$ @.n
end /*n*/
$$$= $$$
MP=1; MPL=! /*new path.*/
end
Line 3,597 ⟶ 4,354:
parse value @.! @.i with @.i @.!
end
end /*i*/; return /*exhausted this particular scan. */</syntaxhighlight>
{{out|output|text= is the same as the brute force version.}}
<br><br>
=={{header|Ring}}==
<syntaxhighlight lang="ring">
# Project : Last letter-first letter
ready = []
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"]
strbegin = "gabite"
strdir = "first"
nr = 1
add(ready,strbegin)
see strbegin + nl
while true
if strdir = "first"
strc = right(strbegin, 1)
flag = 1
nr = nr + 1
if nr <= len(names)
if left(names[nr],1) = strc
for n = 1 to len(ready)
if names[nr] = ready[n]
flag = 0
ok
next
if flag = 1
add(ready,names[nr])
see names[nr] + nl
strbegin = names[nr]
nr = 0
strdir = "last"
loop
ok
ok
ok
else
strc = right(strbegin, 1)
flag = 1
nr = nr + 1
if nr <= len(names)
if left(names[nr],1) = strc
for n = 1 to len(ready)
if names[nr] = ready[n]
flag = 0
ok
next
if flag = 1
add(ready,names[nr])
see names[nr] + nl
strbegin = names[nr]
nr = 0
strdir = "first"
loop
ok
ok
ok
ok
end
</syntaxhighlight>
Output:
<pre>
gabite
emboar
registeel
landorus
sableye
emolga
audino
</pre>
=={{header|Ruby}}==
<
def initialize(names)
@names = names.dup
Line 3,643 ⟶ 4,480:
lf = LastL_FirstL.new(names)
lf.search</
outputs
<pre>there are 2076396 possible sequences
Line 3,671 ⟶ 4,508:
22 emolga
23 audino</pre>
=={{header|Rust}}==
{{trans|Kotlin}}
<syntaxhighlight lang="rust">/// # Panics
///
/// If string is empty.
fn first_char(string: &str) -> char {
string.chars().next().unwrap()
}
/// # Panics
///
/// If string is empty.
fn first_and_last_char(string: &str) -> (char, char) {
(
first_char(string),
first_char(string.rmatches(|_: char| true).next().unwrap()),
)
}
struct Pokemon {
name: &'static str,
first: char,
last: char,
}
impl Pokemon {
fn new(name: &'static str) -> Pokemon {
let (first, last) = first_and_last_char(name);
Pokemon { name, first, last }
}
}
#[derive(Default)]
struct App {
max_path_length: usize,
max_path_length_count: usize,
max_path_example: Vec<&'static str>,
pokemon: Vec<Pokemon>,
}
impl App {
fn search(&mut self, offset: usize) {
if offset > self.max_path_length {
self.max_path_length = offset;
self.max_path_length_count = 1;
} else if offset == self.max_path_length {
self.max_path_length_count += 1;
self.max_path_example.clear();
self.max_path_example.extend(
self.pokemon[0..offset]
.iter()
.map(|Pokemon { name, .. }| *name),
);
}
let last_char = self.pokemon[offset - 1].last;
for i in offset..self.pokemon.len() {
if self.pokemon[i].first == last_char {
self.pokemon.swap(offset, i);
self.search(offset + 1);
self.pokemon.swap(offset, i);
}
}
}
}
fn main() {
let pokemon_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",
];
let mut app = App {
pokemon: pokemon_names
.iter()
.map(|name| Pokemon::new(name))
.collect(),
..App::default()
};
for i in 0..app.pokemon.len() {
app.pokemon.swap(0, i);
app.search(1);
app.pokemon.swap(0, i);
}
println!("Maximum path length: {}", app.max_path_length);
println!("Paths of that length: {}", app.max_path_length_count);
println!(
"Example path of that length: {}",
app.max_path_example.join(" "),
);
}
</syntaxhighlight>
Recommend you run as `release` or at least with `opt-level=1`
{{out}}
<pre>
Maximum path length: 23
Paths of that length: 1248
Example path of that length: machamp pinsir rufflet trapinch heatmor remoraid darmanitan nosepass starly yamask kricketune exeggcute emboar relicanth haxorus simisear registeel landorus seaking girafarig gabite emolga audino
</pre>
=={{header|Scala}}==
===Naive===
<
def solve(names: Set[String]) = {
def extend(solutions: List[List[String]]): List[List[String]] = {
Line 3,693 ⟶ 4,701:
println("Example path of that length:")
println(solutions.head.sliding(7,7).map(_.mkString(" ")).map(" "+_).mkString("\n"))
}</
Output:
<pre>Maximum path length: 23
Line 3,703 ⟶ 4,711:
emolga audino</pre>
===With Lookup Table (Faster)===
<
def solve(names: Set[String]) = {
val transitions = {
Line 3,728 ⟶ 4,736:
println("Example path of that length:")
println(solutions.head.sliding(7,7).map(_.mkString(" ")).map(" "+_).mkString("\n"))
}</
===Parallelised With Lookup Table (Faster)===
<
def solve(names: Set[String]) = {
val transitions = {
Line 3,756 ⟶ 4,764:
println("Example path of that length:")
println(solutions.head.sliding(7,7).map(_.mkString(" ")).map(" "+_).mkString("\n"))
}</
=={{header|Seed7}}==
<
var integer: maxPathLength is 0;
Line 3,828 ⟶ 4,836:
writeln("paths of that length: " <& maxPathLengthCount lpad 4);
writeln("example path of that length:" <& maxPathExample);
end func;</
Output:
Line 3,844 ⟶ 4,852:
=={{header|Sidef}}==
{{trans|Perl}}
<
has f = Hash()
Line 3,892 ⟶ 4,900:
var longest = obj.longest_chain()
say "#{longest.len}: #{longest.join(' ')}"</
{{out}}
<pre>
Line 3,899 ⟶ 4,907:
=={{header|Tcl}}==
<
set solutions {}
set c [string index [lindex $path end] end]
Line 3,938 ⟶ 4,946:
}
set path [firstlast $names]
puts "Path (length: [llength $path]): $path"</
Output:
<pre>
Line 3,946 ⟶ 4,954:
=={{header|Ursala}}==
<
mon =
Line 3,964 ⟶ 4,972:
#show+
example = ~&h poke mon</
<pre>machamp
petilil
Line 3,989 ⟶ 4,997:
audino
</pre>
=={{header|VBScript}}==
{{trans|BBC BASIC}}
<syntaxhighlight lang="vb">' Last letter-first letter - VBScript - 11/03/2019
names = array( _
"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")
maxPathLength = 0
maxPathLengthCount = 0
maxPathExample = ""
t1=timer
For i = 0 To ubound(names)
'swap names(0), names(i)
temp=names(0): names(0)=names(i): names(i)=temp
Call lastfirst(names, 1)
'swap names(0), names(i)
temp=names(0): names(0)=names(i): names(i)=temp
Next 'i
buf = buf & "Maximum length = " & maxPathLength & vbCrLf
buf = buf & "Number of solutions with that length = " & maxPathLengthCount & vbCrLf
buf = buf & "One such solution: " & vbCrLf & maxPathExample & vbCrLf
t2=timer
MsgBox buf,,"Last letter-first letter - " & Int(t2-t1) & " sec"
Sub lastfirst(names, offset)
dim i, l
If offset > maxPathLength Then
maxPathLength = offset
maxPathLengthCount = 1
ElseIf offset = maxPathLength Then
maxPathLengthCount = maxPathLengthCount + 1
maxPathExample = ""
For i = 0 To offset-1
maxPathExample = maxPathExample & names(i) & vbCrLf
Next 'i
End If
l = Right(names(offset - 1),1)
For i = offset To ubound(names)
If Left(names(i),1) = l Then
'swap names(i), names(offset)
temp=names(offset): names(offset)=names(i): names(i)=temp
Call lastfirst(names, offset+1)
'swap names(i), names(offset)
temp=names(offset): names(offset)=names(i): names(i)=temp
End If
Next 'i
End Sub 'lastfirst </syntaxhighlight>
{{out}}
<pre>
Maximum length = 23
Number of solutions with that length = 1248
One such solution:
machamp
pinsir
rufflet
trapinch
heatmor
remoraid
darmanitan
nosepass
starly
yamask
kricketune
exeggcute
emboar
relicanth
haxorus
simisear
registeel
landorus
seaking
girafarig
gabite
emolga
audino
</pre>
Duration : 69 sec
=={{header|Wren}}==
{{trans|Kotlin}}
<syntaxhighlight lang="wren">var maxPathLength = 0
var maxPathLengthCount = 0
var maxPathExample = ""
var 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"
]
var search // recursive function
search = Fn.new { |part, offset|
if (offset > maxPathLength) {
maxPathLength = offset
maxPathLengthCount = 1
} else if (offset == maxPathLength) {
maxPathLengthCount = maxPathLengthCount + 1
maxPathExample = ""
for (i in 0...offset) {
maxPathExample = maxPathExample + ((i % 5 == 0) ? "\n " : " ") + part[i]
}
}
var lastChar = part[offset - 1][-1]
for (i in offset...part.count) {
if (part[i][0] == lastChar) {
var tmp = names[offset]
names[offset] = names[i]
names[i] = tmp
search.call(names, offset + 1)
names[i] = names[offset]
names[offset] = tmp
}
}
}
for (i in 0...names.count) {
var tmp = names[0]
names[0] = names[i]
names[i] = tmp
search.call(names, 1)
names[i] = names[0]
names[0] = tmp
}
System.print("Maximum path length : %(maxPathLength)")
System.print("Paths of that length : %(maxPathLengthCount)")
System.print("Example path of that length : %(maxPathExample)")</syntaxhighlight>
{{out}}
<pre>
Maximum path length : 23
Paths of that length : 1248
Example path of that length :
machamp pinsir rufflet trapinch heatmor
remoraid darmanitan nosepass starly yamask
kricketune exeggcute emboar relicanth haxorus
simisear registeel landorus seaking girafarig
gabite emolga audino
</pre>
=={{header|Yabasic}}==
{{trans|Phix}}
<syntaxhighlight lang="yabasic">all$ = "audino bagon baltoy banette bidoof braviary bronzor carracosta charmeleon "
all$ = all$ + "cresselia croagunk darmanitan deino emboar emolga exeggcute gabite "
all$ = all$ + "girafarig gulpin haxorus heatmor heatran ivysaur jellicent jumpluff kangaskhan "
all$ = all$ + "kricketune landorus ledyba loudred lumineon lunatone machamp magnezone mamoswine "
all$ = all$ + "nosepass petilil pidgeotto pikachu pinsir poliwrath poochyena porygon2 "
all$ = all$ + "porygonz registeel relicanth remoraid rufflet sableye scolipede scrafty seaking "
all$ = all$ + "sealeo silcoon simisear snivy snorlax spoink starly tirtouga trapinch treecko "
all$ = all$ + "tyrogue vigoroth vulpix wailord wartortle whismur wingull yamask"
dim word$(1)
lnames = token(all$, word$())
dim first(256), snext(lnames)
for i = 1 to lnames
ch = asc(left$(word$(i), 1))
if first(ch)=0 then
first(ch) = i
end if
for j=i+1 to lnames
if asc(left$(word$(j), 1))=ch then
snext(i) = j
break
end if
next
next
dim taken(lnames), best(lnames)
sub try(ch, last, n)
local nex, i
nex = first(ch)
while(nex <> 0)
if taken(nex)=0 then
taken(last) = nex
taken(nex) = -1
try(asc(right$(word$(nex), 1)),nex,n+1)
taken(last) = -1
taken(nex) = 0
end if
nex = snext(nex)
wend
if n>maxn then
bstart = tstart
for i = 1 to lnames
best(i) = taken(i)
next
maxn = n
count = 1
elsif n=maxn then
count = count + 1
end if
end sub
for i=1 to lnames
tstart = i
taken(i) = -1
try(asc(right$(word$(i), 1)),i,1)
taken(i) = 0
next
print "Runtime: ", peek("millisrunning")/1000, " seconds. Max length: ", maxn, ", found ", count, " of such, one of which is:\n"
do
print word$(bstart), " ";
bstart = best(bstart)
if bstart = -1 break
loop</syntaxhighlight>
=={{header|zkl}}==
Line 3,995 ⟶ 5,239:
No speed records were approached but 25sec seems fine for a one off walk the entire tree.
<
"bronzor carracosta charmeleon cresselia croagunk darmanitan deino "
...
Line 4,016 ⟶ 5,260:
pokemon.reduce('wrap(np,name){ maxPath(walk(name,1,name,tree),np) },T(0,""))
.println();</
{{out}}
<pre>
|