Last letter-first letter: Difference between revisions

{{trans|Python}}

 

DefaultDict[Char, Set[String]] byfirst

L(word) words

L(i) (0 .< l.len).step(8)

print(l[i .< i + 8].join(‘ ’))

 

{{out}}

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

 

=={{header|C++}}==

#include <string>

#include <vector>

}

std::cout << '\n';

 

{{out}}

 

=={{header|Clojure}}==

(:require clojure.string))

 

(filter #(not (empty? %)) words)))

 

Evaluating the last line:

[23

("machamp"

"kricketune"

"emolga"

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)

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

=={{header|JavaScript}}==

{{Works with|Node.js}} (Required for the ''process'' object)

* Find the letter the word ends on

* @param {string} word

 

findPaths(pokimon);

 

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

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

local perm = next(answer.perms) or ""

print(string.format("%10s %6d %5d %s", answer.word, answer.len, answer.num, perm))

{{out}}

<pre>first word length count example

 

=={{header|Mathematica}}/{{header|Wolfram Language}}==

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

=={{header|Nim}}==

Using bit sets of indexes. The program runs in 0.5s.

 

const Names = ["audino", "bagon", "baltoy", "banette", "bidoof", "braviary", "bronzor",

echo "Longest lists have length: ", list.len

echo "One of these lists is:"

 

{{out}}

 

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

*@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);

 

 

poke($_) for keys %f;

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

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

 

=={{header|Picat}}==

words(Words),

"sealeo", "silcoon", "simisear", "snivy", "snorlax", "spoink", "starly", "tirtouga", "trapinch", "treecko",

"tyrogue", "vigoroth", "vulpix", "wailord", "wartortle", "whismur", "wingull", "yamask"

 

 

<pre>maxLen = 23

 

 

=={{header|PicoLisp}}==

(let Names (make (in File (while (read) (link @))))

(for Name Names

(setq Res Lst) )

(mapc recurse (val Name) (circ Lst)) ) ) ) )

Test:

<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

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

audino bagon baltoy banette bidoof braviary bronzor carracosta charmeleon

cresselia croagunk darmanitan deino emboar emolga exeggcute gabite

my $eg = $IN.lines.pick;

say "Length of longest: ", $eg.chars;

{{out}}

<pre>Length 1: 70 candidates

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

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

end

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

<pre>

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

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

=={{header|Rust}}==

{{trans|Kotlin}}

///

/// If string is empty.

);

}

Recommend you run as `release` or at least with `opt-level=1`

{{out}}

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

=={{header|VBScript}}==

{{trans|BBC BASIC}}

names = array( _

"audino", "bagon", "baltoy", "banette", _

End If

Next 'i

{{out}}

<pre>

=={{header|Wren}}==

{{trans|Kotlin}}

var maxPathLengthCount = 0

var maxPathExample = ""

System.print("Maximum path length : %(maxPathLength)")

System.print("Paths of that length : %(maxPathLengthCount)")

 

{{out}}

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

bstart = best(bstart)

if bstart = -1 break

 

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