Jeśli chcesz, napisz program, który sortuje miasta zgodnie z zasadami gry o nazwie miasta.

• Każda nazwa miasta powinna zaczynać się od ostatniej litery w poprzedniej nazwie miasta. Na przykładLviv -> v -> Viden -> n -> Neapolis -> s -> Sidney -> y -> Yokogama -> a -> Amsterdam -> m -> Madrid -> d -> Denwer

• Na posortowanej liście pierwsza litera pierwszego miasta i ostatnia litera ostatniej nie powinny pasować do niczego , nie musi być tą samą literą.

• Możesz założyć, że nazwy miast mają tylko litery.
• Dane wyjściowe programu powinny mieć taką samą wielkość liter jak dane wejściowe

Przykład:

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

Ruby, 58 55 44 znaków

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

Jeszcze jedna implementacja ruby. Używa również wyrażenia regularnego bez rozróżniania wielkości liter (jako stare rozwiązanie Ventero ), ale test przebiega inaczej.

Poprzednia wersja:

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

Python ( 162 141 124)

Brutalna siła dla zwycięstwa.

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 znaków

Nowe rozwiązanie jest oparte na Howarda „s rozwiązania :

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

Wykorzystuje to fakt, że zawsze będzie prawidłowe rozwiązanie.

Stare rozwiązanie, oparte na w0lf „s rozwiązania :

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

Rubinowy 74 72 104 103 71 70

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

Demo: http://ideone.com/MDK5c (w wersji demo, której użyłem gets().split()zamiast $*; Nie wiem, czy Ideone może symulować argumenty wiersza poleceń).

Python, 113

Bardzo podobny do odpowiedzi @ beary605 i jeszcze bardziej brutalny.

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 bajty

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

Rekurencyjnie znajduje wszystkie rozwiązania. -7 bajtów, jeśli można wypisać wszystkie rozwiązania zamiast pierwszego. Dzięki @Lynn za pozbycie się nieznośnego importu, goląc 18 bajtów z wyniku!

Wypróbuj online!

GolfScript, 78 znaków

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

Pierwsza wersja w GolfScript. Podchodzi także do brutalnej siły. Możesz zobaczyć skrypt działający na przykładowym wejściu online .

Łuska , 10 bajtów

←fΛ~=o_←→P

Wypróbuj online!

Wyjaśnienie

←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"]

Alternatywnie 10 bajtów

We could also count the number of adjacent pairs which satisfy the predicate (#), sort on (Ö) that and take the last element (→) for the same number of bytes:

→Ö#~=o_←→P

Try it online!

Jelly, 25 18 bytes (Improvements welcome!)

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

Try it online!

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!

Thanks to @Lynn for most of these improvements!

25-byte solution:

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

Try it online!

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 znaków

Zdefiniuj listę miast:

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

Znajdź ścieżkę obejmującą wszystkie miasta:

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

Wynik:

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

Powyższe podejście zakłada, że ​​miasta można ułożyć jako wykres ścieżki.

Wykres p pokazano poniżej:

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

Uruchom z nazwami krajów jako argumentami wiersza poleceń

Uwaga:

• brutalne generowanie permutacji
• w celu sprawdzenia zakłada, że ​​nazwy krajów zaczynają się od wielkich liter, a kończą na małe.
• assumes there is only one answer
• In C, assumes that the **v array of main() is writable

J, 69 65 60 59 54 characters

Somewhat off the pace.

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

Example:

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

And here is C# with 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 bajtów

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()):"";}

Wypróbuj online!

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()) : "";
}