Last letter-first letter: Difference between revisions

{{task}}

 

Child 2: goldfish

Child 1: hippopotamus

</pre>

 

 

cresselia croagunk darmanitan deino emboar emolga exeggcute gabite

girafarig gulpin haxorus heatmor heatran ivysaur jellicent jumpluff kangaskhan

porygonz registeel relicanth remoraid rufflet sableye scolipede scrafty seaking

sealeo silcoon simisear snivy snorlax spoink starly tirtouga trapinch treecko

 

 

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

emolga

audino</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:

 

if (len > longest.length)

longest = items[0 .. len].dup;

immutable lastChar = items[len - 1][$ - 1];

foreach (ref item; items[len .. $])

}

 

auto pokemon = "audino bagon baltoy banette bidoof braviary

bronzor carracosta charmeleon cresselia croagunk darmanitan deino

 

string[] solution;

 

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

Output:

<pre>machamp

emolga

audino</pre>

 

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

 

const adj = seq

.assocArray;

SList!string res;

 

void inner(in string it, SList!string lst) nothrow {

lst.insertFront(it);

}

 

}

 

"audino bagon baltoy banette bidoof braviary

bronzor carracosta charmeleon cresselia croagunk darmanitan deino

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

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

 

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

Of 70 words, 1248 paths have the maximum path length of 23.

 

</pre>

 

===optimized version===

This optimized version has two major improvements:

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

 

<br><br>

 

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

 

var integer: maxPathLength is 0;

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

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

 

Output:

simisear registeel landorus seaking girafarig

gabite emolga audino

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

...

"whismur wingull yamask").split();

 

T( name, pokemon.filter('wrap(nm){ name[-1]==nm[0] }) )

});

 

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

{{out}}

<pre>