City names game

Question

If you like, write a program which sorts cities according to the rules of city name game.

• Each name of the city should start from the last letter in the previous city name. E.g. Lviv -> v -> Viden -> n -> Neapolis -> s -> Sidney -> y -> Yokogama -> a -> Amsterdam -> m -> Madrid -> d -> Denwer

• In the sorted list first letter of the first city and last letter of the last shouldn't match anything doesn't have to be the same letter.

• You can assume city names have only letters.
• Program output should have same capitalization as input

Example:

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

Answer 1

Ruby, 58 55 44 characters

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

Yet another ruby implementation. Uses also case insensitive regex (as Ventero's old solution) but the test is done differently.

Previous version:

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

Answer 2

Python (162 141 124)

Brute force for the win.

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

Answer 3

Ruby 1.9, 63 54 characters

New solution is based on Howard's solution:

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

This uses the fact that there'll always be a valid solution.

Old solution, based on w0lf's solution:

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

Answer 4

Ruby 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 (in the demo I've used gets().split() instead of $*; I don't know if Ideone can simulate command-line args).

Answer 5

Python, 113

Very similar to @beary605's answer, and even more brute-forced.

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

Answer 6

GolfScript, 78 characters

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

A first version in GolfScript. It also does a brute force approach. You can see the script running on the example input online.

Answer 7

Mathematica 236 chars

Define the list of cities:

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

Find the path that includes all cities:

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

Output:

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

The above approach assumes that the cities can be arranged as a path graph.

---

The graph p is shown below:

Answer 8

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

Run with country names as the command line arguments

Note:

• brute force generation of permutations
• for checking it assumes that country names start with an upper case and end in lower case.
• assumes there is only one answer
• In C, assumes that the **v array of main() is writable

Answer 9

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

Answer 10

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

Answer 11

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