Si vous le souhaitez, écrivez un programme qui trie les villes selon les règles du jeu des noms de villes.

• Chaque nom de la ville doit commencer par la dernière lettre du nom de la ville précédente. Par exempleLviv -> v -> Viden -> n -> Neapolis -> s -> Sidney -> y -> Yokogama -> a -> Amsterdam -> m -> Madrid -> d -> Denwer

• Dans la liste triée, la première lettre de la première ville et la dernière lettre de la dernière ne doivent pas correspondre. Rien ne doit être la même lettre.

• Vous pouvez supposer que les noms de villes n'ont que des lettres.
• La sortie du programme doit avoir la même capitalisation que l'entrée

Exemple:

% ./script Neapolis Yokogama Sidney Amsterdam Madrid Lviv Viden Denwer
["Lviv", "Viden", "Neapolis", "Sidney", "Yokogama", "Amsterdam", "Madrid", "Denwer"]

Ruby, 58 55 44 caractères

p$*.permutation.find{|i|i*?,!~/(.),(?!\1)/i}

Encore une autre implémentation rubis. Utilise également des expressions rationnelles insensibles à la casse (comme l'ancienne solution de Ventero ) mais le test est effectué différemment.

La version précédente:

p$*.permutation.find{|i|(i*?,).gsub(/(.),\1/i,"")!~/,/}

Python ( 162 141 124 124)

Force brute pour la victoire.

from itertools import*
print[j for j in permutations(raw_input().split())if all(x[-1]==y[0].lower()for x,y in zip(j,j[1:]))]

Ruby 1.9, 63 54 caractères

La nouvelle solution est basée sur la solution d' Howard :

p$*.permutation.max_by{|i|(i*?,).scan(/(.),\1/i).size}

Cela utilise le fait qu'il y aura toujours une solution valable.

Ancienne solution, basée sur la solution de w0lf :

p$*.permutation.find{|i|i.inject{|a,e|a&&e[0]=~/#{a[-1]}/i&&e}}

Rubis 74 72104103 71 70

p$*.permutation.find{|i|i.inject{|a,e|a[-1].casecmp(e[0])==0?e:?,}>?,}

Démo: http://ideone.com/MDK5c (dans la démo que j'ai utilisée à la gets().split()place de $*; je ne sais pas si Ideone peut simuler des arguments de ligne de commande).

Python, 113

Très similaire à la réponse de @ beary605, et encore plus forcé par la force brute.

from random import*
l=raw_input().split()
while any(x[-1]!=y[0].lower()for x,y in zip(l,l[1:])):
 shuffle(l)
print l

Haskell , 94 74 octets

g[a]=[[a]]
g c=[b:r|b<-c,r<-g[x|x<-c,x/=b],last b==[r!!0!!0..]!!32]
head.g

Trouve récursivement toutes les solutions. -7 octets si vous pouvez sortir toutes les solutions au lieu de la première. Merci à @Lynn de se débarrasser de l'importante importune, en réduisant de 18 octets le score!

Essayez-le en ligne!

GolfScript, 78 caractères

" ":s/.{1${1$=!},{:h.,{1$-1={1$0=^31&!{[1$1$]s*[\](\h\-c}*;}+/}{;.p}if}:c~;}/;

Une première version dans GolfScript. Il fait également une approche par force brute. Vous pouvez voir le script s'exécuter sur l'exemple d'entrée en ligne .

Husk , 10 octets

←fΛ~=o_←→P

Essayez-le en ligne!

Explication

←fΛ~=(_←)→P  -- example input: ["Xbc","Abc","Cba"]
          P  -- all permutations: [["Xbc","Abc","Cba"],…,[Xbc","Cba","Abc"]]
 f           -- filter by the following (example with ["Xbc","Cba","Abc"])
  Λ          -- | all adjacent pairs ([("Xbc","Cba"),("Cba","Abc")])
   ~=        -- | | are they equal when..
     (_←)    -- | | .. taking the first character lower-cased
         →   -- | | .. taking the last character
             -- | : ['c'=='c','a'=='a'] -> 4
             -- : [["Xbc","Cba","Abc"]]
←            -- take the first element: ["Xbc","Cba","Abc"]

Alternativement, 10 octets

Nous pourrions également compter le nombre de paires adjacentes qui satisfont le prédicat (# ), trier sur ( Ö) cela et prendre le dernier élément ( →) pour le même nombre d'octets:

→Ö#~=o_←→P

Essayez-le en ligne!

Gelée , 25 18 octets (Améliorations bienvenues!)

UżḢŒuE
ḲŒ!çƝẠ$ÐfḢK

Essayez-le en ligne!

UżḢŒuE        dyadic (2-arg) "check two adjacent city names" function:
Uż            pair (żip) the letters of the reversed left argument with the right argument,
  Ḣ           get the Ḣead of that pairing to yield just the last letter of left and the first letter of right,
   Œu         capitalize both letters,
     E       and check that they're equal!
ḲŒ!çƝẠ$ÐfḢK    i/o and check / fold function:
ḲŒ!            split the input on spaces and get all permutations of it,
   çƝẠ$        run the above function on every adjacent pair (çƝ), and return true if Ȧll pairs are true
       Ðf      filter the permutations to only get the correct ones,
         ḢK    take the first of those, and join by spaces!

Merci à @Lynn pour la plupart de ces améliorations!

Solution de 25 octets:

Uḣ1Œu=⁹ḣ1
çƝȦ
ḲŒ!©Ç€i1ị®K

Essayez-le en ligne!

Uḣ1Œu=⁹ḣ1      dyadic (2-arg) "check two adjacent city names" function:
Uḣ1Œu          reverse the left arg, get the ḣead, and capitalize it (AKA capitalize the last letter),
     =⁹ḣ1      and check if it's equal to the head (first letter) of the right argument.
çƝȦ            run the above function on every adjacent pair (çƝ), and return true if Ȧll pairs are true
ḲŒ!©Ç€i1ị®K     main i/o function:
ḲŒ!©           split the input on spaces and get all its permutations, ©opy that to the register
    Ç€         run the above link on €ach permutation,
      i1       find the index of the first "successful" permutation,
        ị®K    and ®ecall the permutation list to get the actual ordering at that ịndex, separating output by spaces

Mathematica 236 caractères

Définissez la liste des villes:

d = {"Neapolis", "Yokogama", "Sidney", "Amsterdam", "Madrid", "Lviv", "Viden", "Denver"}

Trouvez le chemin qui inclut toutes les villes:

c = Characters; f = Flatten;
w = Outer[List, d, d]~f~1;
p = Graph[Cases[w, {x_, y_} /;x != y \[And] (ToUpperCase@c[x][[-1]]== c[y][[1]]) :> (x->y)]];
v = f[Cases[{#[[1]], #[[2]], GraphDistance[p, #[[1]], #[[2]]]} & /@  w, {_, _, Length[d] - 1}]];
FindShortestPath[p, v[[1]], v[[2]]]

Production:

{"Lviv", "Viden", "Neapolis", "Sidney", "Yokogama", "Amsterdam","Madrid", "Denver"}

L'approche ci-dessus suppose que les villes peuvent être organisées sous forme de graphique de chemin.

Le graphique p est illustré ci-dessous:

C, 225

#define S t=v[c];v[c]=v[i];v[i]=t
#define L(x)for(i=x;i<n;i++)
char*t;f;n=0;main(int c,char**v){int i;if(!n)n=c,c=1;if(c==n-1){f=1;L(2){for(t=v[i-1];t[1];t++);if(v[i][0]+32-*t)f=n;}L(f)puts(v[i]);}else L(c){S;main(c+1,v);S;}}

Exécuter avec des noms de pays comme arguments de ligne de commande

Remarque:

• génération de permutations par force brute
• pour le vérifier, il suppose que les noms de pays commencent par des majuscules et finissent par des minuscules.
• suppose qu'il n'y a qu'une seule réponse
• En C, suppose que le tableau ** v de main () est accessible en écriture

J, 69 65 60 59 54 caractères

Un peu hors du rythme.

{.l\:+/2=/\|:tolower;"2({.,{:)@>l=.(i.@!@#A.]);:1!:1[1

Exemple:

   {.l\:+/2=/\|:tolower;"2({.,{:)@>l=.(i.@!@#A.]);:1!:1[1
Neapolis Yokogama Sydney Amsterdam Madrid Lviv Viden Denwer
+----+-----+--------+------+--------+---------+------+------+
|Lviv|Viden|Neapolis|Sydney|Yokogama|Amsterdam|Madrid|Denwer|
+----+-----+--------+------+--------+---------+------+------+

C #, 398

Et voici C # avec Linq 5 cents

IEnumerable<string>CityNameGame(string[]input){var cities=new List<string>(input);string lastCity=null;while(cities.Any()){var city=lastCity??cities.First();lastCity=cities.First(name=>string.Equals(city.Substring(city.Length-1),name.Substring(0,1),StringComparison.CurrentCultureIgnoreCase));cities.RemoveAll(name=>name==city||name==lastCity);yield return string.Format("{0}→{1}",city,lastCity);}}

K, 96

{m@&{&/(~).'+(,_1_1#'x),,-1_-1#'x}@'$m:{$[x=1;y;,/.z.s[x-1;y]{x,/:{x@&~x in y}[y;x]}\:y]}[#x;x]}

.

k){m@&{&/(~).'+(,_1_1#'x),,-1_-1#'x}@'$m:{$[x=1;y;,/.z.s[x-1;y]{x,/:{x@&~x in y}[y;x]}\:y]}[#x;x]}`Neapolis`Yokogama`Sidney`Amsterdam`Madrid`Lviv`Viden`Denver
Lviv Viden Neapolis Sidney Yokogama Amsterdam Madrid Denver

C # (.NET Core) , 297 octets

using System;
using System.Linq;

var S="";int I=0,C=s.Count();for(;I<C;I++)S=Array.Find(s,x=>s[I].Substring(0,1).ToUpper()==x.Substring(x.Length-1).ToUpper())==null?s[I]:S;for(I=0;I<C;I++){Console.Write(S+" ");S=C>I?Array.Find(s,x=>S.Substring(S.Length-1).ToUpper()==x.Substring(0,1).ToUpper()):"";}

Essayez-le en ligne!

using System;
using System.Linq;

var S = "";
int I = 0, C = s.Count();
for (; I < C; I++)
    S = Array.Find(
        s, x =>
        s[I].Substring(0, 1).ToUpper() == x.Substring(x.Length - 1).ToUpper()
    ) == null ?
    s[I] :
    S;
for (I = 0; I < C; I++) {
    Console.Write(S + " ");
    S = C > I ? Array.Find(s, x => S.Substring(S.Length - 1).ToUpper() == x.Substring(0, 1).ToUpper()) : "";
}