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

Haskell, 94 74 bytes

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

Recursively finds all solutions. -7 bytes if it's ok to output all solutions instead of the first. Thanks to @Lynn for getting rid of the pesky import, shaving 18 bytes off the score!

Try it online!

Answer 6

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 7

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

Answer 8

Husk, 10 bytes

←fΛ~=o_←→P

Try it online!

Explanation

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

Alternatively, 10 bytes

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!

Answer 9

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 10

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 11

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 12

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 13

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

Answer 14

C# (.NET Core), 297 bytes

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

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

Answer 15

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