Last letter-first letter: Difference between revisions
Content deleted Content added
Added Easylang |
|||
(3 intermediate revisions by 3 users not shown) | |||
Line 37:
{{trans|Python}}
<
DefaultDict[Char, Set[String]] byfirst
L(word) words
Line 70:
L(i) (0 .< l.len).step(8)
print(l[i .< i + 8].join(‘ ’))
print(l.len)</
{{out}}
Line 82:
=={{header|Ada}}==
<
procedure Lalefile is
Line 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 191:
=={{header|BaCon}}==
Naive implementation showing the algorithm.
<
"cresselia croagunk darmanitan deino emboar emolga exeggcute gabite " \
"girafarig gulpin haxorus heatmor heatran ivysaur jellicent jumpluff kangaskhan " \
Line 221:
PRINT total, ": ", result$
PRINT NL$, "Speed: ", TIMER, " msecs."</
{{out}}
<pre>
Line 229:
</pre>
Optimized implementation. The idea is to quantify the equations.
<
"cresselia croagunk darmanitan deino emboar emolga exeggcute gabite " \
"girafarig gulpin haxorus heatmor heatran ivysaur jellicent jumpluff kangaskhan " \
Line 282:
END SUB
</syntaxhighlight>
</lang>▼
{{out}}
<pre>
Line 291:
=={{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 348:
index[b] = t
end subroutine
</syntaxhighlight>
Output:
Line 362:
=={{header|BBC BASIC}}==
{{works with|BBC BASIC for Windows}}
<
names$() = "audino", "bagon", "baltoy", "banette", \
\ "bidoof", "braviary", "bronzor", "carracosta", "charmeleon", \
Line 412:
ENDIF
NEXT
ENDPROC</
'''Output:'''
<pre>
Line 445:
=={{header|Bracmat}}==
===Naive===
<
carracosta charmeleon cresselia croagunk darmanitan deino
emboar emolga exeggcute gabite girafarig gulpin haxorus
Line 487:
& lalefile$(.!names)
& out$("Length:" !max "Sequence:" !sequence)
);</
Output (read from bottom to top):
<pre> Length:
Line 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 599:
& lalefile$(.!names)
& out$("Length:" !max "Sequence:" !sequence)
);</
Output (read from bottom to top):
<pre> Length:
Line 630:
=={{header|C}}==
From the D version.
<
#include <string.h>
#include <stdio.h>
Line 743:
return 0;
}</
Output:
<pre>Maximum path length: 23
Line 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 951:
printf("longest found: %d\n", best);
return 0;
}</
307: voltorb breloom magikarp palpito...
308: voltorb bayleef forretress swinub b...
Line 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 1,026:
}
}
}</
petilil
landorus
Line 1,049:
=={{header|C++}}==
<
#include <string>
#include <vector>
Line 1,116:
}
std::cout << '\n';
}</
{{out}}
Line 1,130:
=={{header|Clojure}}==
<
(:require clojure.string))
Line 1,167:
(filter #(not (empty? %)) words)))
(time (longest-word-chain (word-list-from-file "pokemon.txt")))</
Evaluating the last line:
<
[23
("machamp"
Line 1,193:
"kricketune"
"emolga"
"audino")]</
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.
Line 1,199:
=={{header|Common Lisp}}==
Pretty brute force here. Takes a couple of seconds to run.
<
(defun filter-with-init (words init)
Line 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,360:
writefln("%-(%s\n%)", solution);
}</
Output:
<pre>machamp
Line 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,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,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,550:
writeln("Example path of that length:");
writefln("%( %-(%s %)\n%)", sol[1].chunks(7));
}</
{{out}}
<pre>Maximum path length: 23
Line 1,563:
===Alternative Version===
{{trans|PicoLisp}}
<
std.container, std.range;
Line 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,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,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
=={{header|Elixir}}==
{{trans|Ruby}}
<
def search(names) do
first = Enum.group_by(names, &String.first/1)
Line 1,928 ⟶ 1,979:
)
LastLetter_FirstLetter.search(names)</
{{out}}
Line 1,962 ⟶ 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 2,013 ⟶ 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 2,027 ⟶ 2,078:
=={{header|Go}}==
Depth first, starting with each possible name.
<
import (
Line 2,082 ⟶ 2,133:
}
}
}</
Output:
<pre>
Line 2,097 ⟶ 2,148:
=={{header|Haskell}}==
Note: This takes ~80 seconds to complete on my machine.
<
import qualified Data.ByteString.Char8 as B
Line 2,119 ⟶ 2,170:
isLink pl pr = B.last pl == B.head pr
main = mapM_ B.putStrLn $ growChains $ map (\x -> [x]) allPokemon</
Output:
<pre>machamp
Line 2,145 ⟶ 2,196:
audino</pre>
A simpler version (no ByteString), about 2.4 times slower (GHC -O3), same output:
<
allPokemon = words
Line 2,165 ⟶ 2,216:
isLink pl pr = last pl == head pr
main = mapM_ putStrLn $ growChains $ map (\x -> [x]) allPokemon</
=={{header|Icon}} and {{header|Unicon}}==
Line 2,171 ⟶ 2,222:
Works in both languages (brute force):
<
procedure main()
Line 2,194 ⟶ 2,245:
while l := !f do
l ? while tab(upto(&letters)) do suspend tab(many(&letters))\1
end</
Sample run on sample data:
Line 2,207 ⟶ 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 2,227 ⟶ 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,233 ⟶ 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,261 ⟶ 2,312:
exeggcute
emolga
audino </
=={{header|Java}}==
<
final class LastLetterFirstLetter {
static int maxPathLength = 0;
Line 2,324 ⟶ 2,375:
}
}
</syntaxhighlight>
Output:<pre>maximum path length : 23
Line 2,338 ⟶ 2,389:
=={{header|JavaScript}}==
{{Works with|Node.js}} (Required for the ''process'' object)
<
* Find the letter the word ends on
* @param {string} word
Line 2,428 ⟶ 2,479:
findPaths(pokimon);
</syntaxhighlight>
<pre>
Line 2,468 ⟶ 2,519:
'''Utility functions''':
<
def dictionary:
reduce .[] as $word ({}; .[$word[0:1]] += [$word]) ;
Line 2,474 ⟶ 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,517 ⟶ 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,535 ⟶ 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,638 ⟶ 2,689:
"audino"
]
]</
=={{header|Julia}}==
Line 2,644 ⟶ 2,695:
{{trans|Python}}
<
orderwords(words::Vector) = Dict(w[1][1] => Set(w) for w in groupby(first, words))
Line 2,680 ⟶ 2,731:
l = llfl(pokemon)
println("Example of longest seq.:\n", join(l, ", "))
println("Max length: ", length(l)</
{{out}}
Line 2,689 ⟶ 2,740:
=={{header|Kotlin}}==
{{trans|Java}}
<
var maxPathLength = 0
Line 2,750 ⟶ 2,801:
println("Paths of that length : $maxPathLengthCount")
println("Example path of that length : $maxPathExample")
}</
{{out}}
Line 2,765 ⟶ 2,816:
=={{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.
<
pokemon = [[
audino bagon baltoy banette bidoof braviary bronzor carracosta charmeleon
Line 2,831 ⟶ 2,882:
local perm = next(answer.perms) or ""
print(string.format("%10s %6d %5d %s", answer.word, answer.len, answer.num, perm))
end</
{{out}}
<pre>first word length count example
Line 2,907 ⟶ 2,958:
=={{header|Mathematica}}/{{header|Wolfram Language}}==
<
NestWhileList[
Append @@@
Line 2,927 ⟶ 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}}
Line 2,934 ⟶ 2,985:
=={{header|Nim}}==
Using bit sets of indexes. The program runs in 0.5s.
<
const Names = ["audino", "bagon", "baltoy", "banette", "bidoof", "braviary", "bronzor",
Line 2,983 ⟶ 3,034:
echo "Longest lists have length: ", list.len
echo "One of these lists is:"
for idx in list: echo Names[idx]</
{{out}}
Line 3,013 ⟶ 3,064:
=={{header|ooRexx}}==
<syntaxhighlight lang="oorexx">
-- create the searcher and run it
searcher = .chainsearcher~new
Line 3,088 ⟶ 3,139:
end
end
</syntaxhighlight>
<pre>
searching 70 names...
Line 3,122 ⟶ 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 3,205 ⟶ 3,256:
IF lcontinue = FALSE THEN
STOP.
END.</
Output:
Line 3,231 ⟶ 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.
<
my(%f,@m);
Line 3,260 ⟶ 3,311:
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>
Line 3,266 ⟶ 3,317:
=={{header|Phix}}==
Using simple start-with-same-letter word chains to minimise the number of elements we have to consider:
<!--<
<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>
Line 3,346 ⟶ 3,397:
<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>
<!--</
{{out}}
<pre>
Line 3,365 ⟶ 3,416:
=={{header|Picat}}==
It's a little faster with the words sorted on decreasing lengths (<code>words2</code>): 9.43s vs 11.742s.
<
words(Words),
Line 3,450 ⟶ 3,501:
"sealeo", "silcoon", "simisear", "snivy", "snorlax", "spoink", "starly", "tirtouga", "trapinch", "treecko",
"tyrogue", "vigoroth", "vulpix", "wailord", "wartortle", "whismur", "wingull", "yamask"
].</
{{out}}
<pre>maxLen = 23
Line 3,467 ⟶ 3,518:
=={{header|PicoLisp}}==
<
(let Names (make (in File (while (read) (link @))))
(for Name Names
Line 3,481 ⟶ 3,532:
(setq Res Lst) )
(mapc recurse (val Name) (circ Lst)) ) ) ) )
(flip Res) ) ) )</
Test:
<pre>
Line 3,494 ⟶ 3,545:
=={{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 3,570 ⟶ 3,621:
atom_chars(A, LC),
reverse(LC, [L | _]).
</syntaxhighlight>
Output :
<pre>?- time(last_first(Len, Nb, L)).
Line 3,580 ⟶ 3,631:
=={{header|Python}}==
<
def order_words(words):
Line 3,626 ⟶ 3,677:
l = llfl(pokemon)
for i in range(0, len(l), 8): print(' '.join(l[i:i+8]))
print(len(l))</
;Sample output
Line 3,635 ⟶ 3,686:
===Alternative version===
Adapted from the D version. This uses Psyco.
<
nsolutions = 0
Line 3,709 ⟶ 3,760:
psyco.full()
main()</
Output:
<pre>Maximum path length: 23
Line 3,722 ⟶ 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,752 ⟶ 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,762 ⟶ 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,944 ⟶ 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 4,004 ⟶ 4,055:
Karrablast Throh Happiny Yanmega Armaldo) 333)</pre>
'''File: pokemon-names.rkt'''
<
(provide names-646 names-70)
(define names-70
Line 4,064 ⟶ 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"
audino bagon baltoy banette bidoof braviary bronzor carracosta charmeleon
cresselia croagunk darmanitan deino emboar emolga exeggcute gabite
Line 4,116 ⟶ 4,167:
my $eg = $IN.lines.pick;
say "Length of longest: ", $eg.chars;
say join ' ', $eg.ords.reverse.map: { @names[$_ - 32] }</
{{out}}
<pre>Length 1: 70 candidates
Line 4,150 ⟶ 4,201:
<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 4,203 ⟶ 4,254:
parse value @.! @.i with @.i @.!
end
end /*i*/; return /*exhausted this particular scan. */</
{{out|output|text= when using the default input:}}
<pre>
Line 4,241 ⟶ 4,292:
<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 4,303 ⟶ 4,354:
parse value @.! @.i with @.i @.!
end
end /*i*/; return /*exhausted this particular scan. */</
{{out|output|text= is the same as the brute force version.}}
<br><br>
=={{header|Ring}}==
<
# Project : Last letter-first letter
Line 4,376 ⟶ 4,427:
ok
end
</syntaxhighlight>
Output:
<pre>
Line 4,389 ⟶ 4,440:
=={{header|Ruby}}==
<
def initialize(names)
@names = names.dup
Line 4,429 ⟶ 4,480:
lf = LastL_FirstL.new(names)
lf.search</
outputs
<pre>there are 2076396 possible sequences
Line 4,460 ⟶ 4,511:
=={{header|Rust}}==
{{trans|Kotlin}}
<
///
/// If string is empty.
Line 4,619 ⟶ 4,670:
);
}
</syntaxhighlight>
Recommend you run as `release` or at least with `opt-level=1`
{{out}}
Line 4,630 ⟶ 4,681:
=={{header|Scala}}==
===Naive===
<
def solve(names: Set[String]) = {
def extend(solutions: List[List[String]]): List[List[String]] = {
Line 4,650 ⟶ 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 4,660 ⟶ 4,711:
emolga audino</pre>
===With Lookup Table (Faster)===
<
def solve(names: Set[String]) = {
val transitions = {
Line 4,685 ⟶ 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 4,713 ⟶ 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 4,785 ⟶ 4,836:
writeln("paths of that length: " <& maxPathLengthCount lpad 4);
writeln("example path of that length:" <& maxPathExample);
end func;</
Output:
Line 4,801 ⟶ 4,852:
=={{header|Sidef}}==
{{trans|Perl}}
<
has f = Hash()
Line 4,849 ⟶ 4,900:
var longest = obj.longest_chain()
say "#{longest.len}: #{longest.join(' ')}"</
{{out}}
<pre>
Line 4,856 ⟶ 4,907:
=={{header|Tcl}}==
<
set solutions {}
set c [string index [lindex $path end] end]
Line 4,895 ⟶ 4,946:
}
set path [firstlast $names]
puts "Path (length: [llength $path]): $path"</
Output:
<pre>
Line 4,903 ⟶ 4,954:
=={{header|Ursala}}==
<
mon =
Line 4,921 ⟶ 4,972:
#show+
example = ~&h poke mon</
<pre>machamp
petilil
Line 4,949 ⟶ 5,000:
=={{header|VBScript}}==
{{trans|BBC BASIC}}
<
names = array( _
"audino", "bagon", "baltoy", "banette", _
Line 5,006 ⟶ 5,057:
End If
Next 'i
End Sub 'lastfirst </
{{out}}
<pre>
Line 5,040 ⟶ 5,091:
=={{header|Wren}}==
{{trans|Kotlin}}
<
var maxPathLengthCount = 0
var maxPathExample = ""
Line 5,096 ⟶ 5,147:
System.print("Maximum path length : %(maxPathLength)")
System.print("Paths of that length : %(maxPathLengthCount)")
System.print("Example path of that length : %(maxPathExample)")</
{{out}}
Line 5,112 ⟶ 5,163:
=={{header|Yabasic}}==
{{trans|Phix}}
<
all$ = all$ + "cresselia croagunk darmanitan deino emboar emolga exeggcute gabite "
all$ = all$ + "girafarig gulpin haxorus heatmor heatran ivysaur jellicent jumpluff kangaskhan "
Line 5,181 ⟶ 5,232:
bstart = best(bstart)
if bstart = -1 break
loop</
=={{header|zkl}}==
Line 5,188 ⟶ 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 5,209 ⟶ 5,260:
pokemon.reduce('wrap(np,name){ maxPath(walk(name,1,name,tree),np) },T(0,""))
.println();</
{{out}}
<pre>
|