Last letter-first letter: Difference between revisions

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

<br><br>

 

=={{header|Ada}}==

 

 

procedure Lalefile is

Ada.Text_IO.Put_Line("One such path:");

Write(Best);

 

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,

=={{header|BaCon}}==

Naive implementation showing the algorithm.

"cresselia croagunk darmanitan deino emboar emolga exeggcute gabite " \

"girafarig gulpin haxorus heatmor heatran ivysaur jellicent jumpluff kangaskhan " \

PRINT total, ": ", result$

 

{{out}}

<pre>

</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 " \

 

END SUB

{{out}}

<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" }

 

index[b] = t

end subroutine

 

Output:

=={{header|BBC BASIC}}==

{{works with|BBC BASIC for Windows}}

names$() = "audino", "bagon", "baltoy", "banette", \

\ "bidoof", "braviary", "bronzor", "carracosta", "charmeleon", \

ENDIF

NEXT

'''Output:'''

<pre>

=={{header|Bracmat}}==

===Naive===

carracosta charmeleon cresselia croagunk darmanitan deino

emboar emolga exeggcute gabite girafarig gulpin haxorus

& lalefile$(.!names)

& out$("Length:" !max "Sequence:" !sequence)

Output (read from bottom to top):

<pre> Length:

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

& lalefile$(.!names)

& out$("Length:" !max "Sequence:" !sequence)

Output (read from bottom to top):

<pre> Length:

=={{header|C}}==

From the D version.

#include <string.h>

#include <stdio.h>

 

return 0;

Output:

<pre>Maximum path length: 23

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

printf("longest found: %d\n", best);

return 0;

307: voltorb breloom magikarp palpito...

308: voltorb bayleef forretress swinub b...

322: voltorb beldum mandibuzz zekrom murk...

323: voltorb breloom mandibuzz zekr...

 

=={{header|C sharp}}==

using System.Collections.Generic;

using System.Linq;

}

}

petilil

landorus

emolga

audino</pre>

 

=={{header|Common Lisp}}==

Pretty brute force here. Takes a couple of seconds to run.

 

(defun filter-with-init (words init)

tyrogue vigoroth vulpix wailord wartortle whismur wingull yamask)))

 

"LOUDRED" "DARMANITAN" "NOSEPASS" "SIMISEAR" "RELICANTH" "HEATMOR" "RUFFLET"

=={{header|D}}==

===Simple Version===

Modified from the Go version:

 

void trySwap(string[] items, ref string item, in size_t len, ref string[] longest)

 

writefln("%-(%s\n%)", solution);

Output:

<pre>machamp

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

 

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

addl $4, %esi

decl %ebp

 

The run-time is about 0.65 seconds with LDC2 compiler. The output is similar.

 

===Faster Version===

 

Tuple!(uint, string[]) findLongestChain(in string[] words)

writeln("Example path of that length:");

writefln("%( %-(%s %)\n%)", sol[1].chunks(7));

{{out}}

<pre>Maximum path length: 23

===Alternative Version===

{{trans|PicoLisp}}

std.container, std.range;

 

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>

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

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|Elixir}}==

{{trans|Ruby}}

def search(names) do

first = Enum.group_by(names, &String.first/1)

)

 

 

{{out}}

=={{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.

-module( last_letter_first_letter ).

 

 

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">>.

{{out}}

<pre>

=={{header|Go}}==

Depth first, starting with each possible name.

 

import (

}

}

Output:

<pre>

=={{header|Haskell}}==

Note: This takes ~80 seconds to complete on my machine.

import qualified Data.ByteString.Char8 as B

 

isLink pl pr = B.last pl == B.head pr

 

Output:

<pre>machamp

audino</pre>

A simpler version (no ByteString), about 2.4 times slower (GHC -O3), same output:

 

allPokemon = words

isLink pl pr = last pl == head pr

 

 

=={{header|Icon}} and {{header|Unicon}}==

Works in both languages (brute force):

 

 

procedure main()

while l := !f do

l ? while tab(upto(&letters)) do suspend tab(many(&letters))\1

 

Sample run on sample data:

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

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.

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

 

 

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

exeggcute

emolga

 

=={{header|Java}}==

final class LastLetterFirstLetter {

static int maxPathLength = 0;

}

}

 

Output:<pre>maximum path length : 23

simisear registeel landorus seaking girafarig

gabite emolga audino

</pre>

 

 

'''Utility functions''':

def dictionary:

reduce .[] as $word ({}; .[$word[0:1]] += [$word]) ;

# remove "word" from the input dictionary assuming the key is already there:

def remove(word):

 

'''The last-letter/first-letter game''':

def admissible:

.[0][-1:] == .[1][0:1];

# If your jq does not include "debug", simply remove or comment-out the following line:

| ([$name, $ans[0]] | debug) as $debug

'''Example''':

["audino", "bagon", "baltoy", "banette",

"bidoof", "braviary", "bronzor", "carracosta", "charmeleon",

"wailord", "wartortle", "whismur", "wingull", "yamask" ] ;

 

 

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

"audino"

]

 

=={{header|Julia}}==

{{trans|Python}}

 

 

orderwords(words::Vector) = Dict(w[1][1] => Set(w) for w in groupby(first, words))

l = llfl(pokemon)

println("Example of longest seq.:\n", join(l, ", "))

 

{{out}}

=={{header|Kotlin}}==

{{trans|Java}}

 

var maxPathLength = 0

println("Paths of that length : $maxPathLengthCount")

println("Example path of that length : $maxPathExample")

 

{{out}}

gabite emolga audino

</pre>

 

NestWhileList[

Append @@@

"snorlax", "spoink", "starly", "tirtouga", "trapinch", "treecko",

"tyrogue", "vigoroth", "vulpix", "wailord", "wartortle",

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|ooRexx}}==

-- create the searcher and run it

searcher = .chainsearcher~new

end

end

<pre>

searching 70 names...

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 ~

IF lcontinue = FALSE THEN

STOP.

 

Output:

Yes No

---------------------------</pre>

 

=={{header|Perl}}==

*@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.

 

audino bagon baltoy banette bidoof braviary bronzor carracosta charmeleon

cresselia croagunk darmanitan deino emboar emolga exeggcute gabite

);

 

}

 

poke($_) for keys %f;

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

 

 

 

 

 

 

 

 

 

 

 

 

 

{{out}}

<pre>

</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.

atom_chars(A, LC),

reverse(LC, [L | _]).

Output :

<pre>?- time(last_first(Len, Nb, L)).

 

=={{header|Python}}==

 

def order_words(words):

l = llfl(pokemon)

for i in range(0, len(l), 8): print(' '.join(l[i:i+8]))

 

;Sample output

23</pre>

===Alternative version===

Adapted from the D version. This uses Psyco.

 

nsolutions = 0

 

psyco.full()

Output:

<pre>Maximum path length: 23

=={{header|Racket}}==

This is a naive solution, which works fast enough as is (takes about 5 seconds on an old machine):

 

(define names "

(printf "Longest chain found has ~a words:\n ~a\n"

(length longest) (string-join (map word-string longest) " -> "))

{{out}}

<pre>

chains using three different combination/relinking functions. Not that the

definiton of `word` is slightly different here.

(require "pokemon-names.rkt")

 

 

(time (longest-chain/constructive names-70 #:known-max 23))

 

Run with ''racket -t last_letter-first_letter-randomised.rkt 2>&1'', to redirect standard error to

Karrablast Throh Happiny Yanmega Armaldo) 333)</pre>

'''File: pokemon-names.rkt'''

(provide names-646 names-70)

(define names-70

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

 

=={{header|REXX}}==

{{trans|ooRexx}}

===brute force version===

<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',

'remoraid rufflet sableye scolipede scrafty seaking sealeo silcoon simisear snivy snorlax spoink',

'starly tirtouga trapinch treecko tyrogue vigoroth vulpix wailord wartortle whismur wingull yamask'

parse arg limit .; if limit\=='' then #=limit /*allow user to specify a scan limit. */

say 'Of' # "words," MP 'path's(MP) "have the maximum path length of" g'.'

/*──────────────────────────────────────────────────────────────────────────────────────*/

s: if arg(1)==1 then return arg(3); return word( arg(2) 's', 1) /*a pluralizer.*/

/*──────────────────────────────────────────────────────────────────────────────────────*/

parse var @.p '' -1 LC /*obtain last character of previous @. */

/* [↓] PARSE obtains first char of @.i*/

$$$=$$$ @.i /*add last.*/

parse value @.! @.i with @.i @.!; call scan $$$, !+1

parse value @.! @.i with @.i @.!

{{out|output|text=&nbsp; when using the default input:}}

<pre>

===optimized version===

This optimized version has two major improvements:

With the full list of words being used, there are no dead words &nbsp; (but there are when a limit is used to shorten the list).

<br>In the &nbsp; '''scan''' &nbsp; 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 &nbsp; '''25%''' &nbsp; 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',

'remoraid rufflet sableye scolipede scrafty seaking sealeo silcoon simisear snivy snorlax spoink',

'starly tirtouga trapinch treecko tyrogue vigoroth vulpix wailord wartortle whismur wingull yamask'

call build@ /*build a stemmed array from the @ list*/

do v=# by -1 for # /*scrub the @ list for unusable words. */

parse var @.v F 2 '' -1 L /*obtain first and last letter of word.*/

end /*v*/ /*delete dead word from @ ──┘ */

$$$= /*nullify the possible longest path. */

do j=1 for # /* ─ ─ ─ */

parse value @.1 @.j with @.j @.1; call scan $$$, 2

parse value @.1 @.j with @.j @.1

end /*j*/

say 'Of' # "words," MP 'path's(MP) "have the maximum path length of" g'.'

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.*/

/*──────────────────────────────────────────────────────────────────────────────────────*/

parse var @.p '' -1 LC /*obtain last character of previous @. */

if !.1.LC==0 then return /*is this a dead─end word? */

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? */

do n=2 for !-2; $$$=$$$ @.n

end /*n*/

MP=1; MPL=! /*new path.*/

end

parse value @.! @.i with @.i @.!

end

{{out|output|text=&nbsp; is the same as the brute force version.}}

<br><br>

 

=={{header|Ring}}==

# Project : Last letter-first letter

 

ok

end

Output:

<pre>

 

=={{header|Ruby}}==

def initialize(names)

@names = names.dup

 

lf = LastL_FirstL.new(names)

outputs

<pre>there are 2076396 possible sequences

22 emolga

23 audino</pre>

=={{header|Scala}}==

===Naive===

def solve(names: Set[String]) = {

def extend(solutions: List[List[String]]): List[List[String]] = {

println("Example path of that length:")

println(solutions.head.sliding(7,7).map(_.mkString(" ")).map(" "+_).mkString("\n"))

Output:

<pre>Maximum path length: 23

emolga audino</pre>

===With Lookup Table (Faster)===

def solve(names: Set[String]) = {

val transitions = {

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

println("Example path of that length:")

println(solutions.head.sliding(7,7).map(_.mkString(" ")).map(" "+_).mkString("\n"))

 

=={{header|Seed7}}==

 

var integer: maxPathLength is 0;

writeln("paths of that length: " <& maxPathLengthCount lpad 4);

writeln("example path of that length:" <& maxPathExample);

 

Output:

=={{header|Sidef}}==

{{trans|Perl}}

 

has f = Hash()

var longest = obj.longest_chain()

 

{{out}}

<pre>

 

=={{header|Tcl}}==

set solutions {}

set c [string index [lindex $path end] end]

}

set path [firstlast $names]

Output:

<pre>

=={{header|Ursala}}==

 

 

mon =

#show+

 

<pre>machamp

petilil

audino

</pre>

 

=={{header|zkl}}==

No speed records were approached but 25sec seems fine for a one off walk the entire tree.

 

"bronzor carracosta charmeleon cresselia croagunk darmanitan deino "

...

 

pokemon.reduce('wrap(np,name){ maxPath(walk(name,1,name,tree),np) },T(0,""))

{{out}}

<pre>