16
\$\begingroup\$

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"]
\$\endgroup\$
  • 2
    \$\begingroup\$ Can we assume that there will always be a valid solution? \$\endgroup\$ – Gareth Jul 16 '12 at 16:00
  • \$\begingroup\$ @Gareth yes, you can \$\endgroup\$ – defhlt Jul 16 '12 at 16:02
  • \$\begingroup\$ the second rule - "[...] shouldn't match anything" - is it a requirement or just a statement saying that it's OK to have mismatch between the first and last letter? (ex: is a list like ["Viden" ... "Lviv"] invalid?) \$\endgroup\$ – Cristian Lupascu Jul 16 '12 at 18:31
  • \$\begingroup\$ @w0lf by "shouldn't" I meant it doesn't have to, it is not compulsory. So your example is valid. \$\endgroup\$ – defhlt Jul 16 '12 at 18:39
  • \$\begingroup\$ Hint: If you want a nice solution, you can reduce this to the calculation of eulerian paths, where each letter is a vertex and each word is an edge. (For instance, Berlin is the edge BN) This is solvable in O(n), where n is the number of edges. \$\endgroup\$ – FUZxxl Jul 17 '12 at 22:56

15 Answers 15

11
\$\begingroup\$

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,"")!~/,/}
\$\endgroup\$
  • \$\begingroup\$ Very nice! And I think you can get this down to 55 if you use !~ instead of negating the whole expression. \$\endgroup\$ – Cristian Lupascu Jul 17 '12 at 13:33
  • \$\begingroup\$ That is smart regexp \$\endgroup\$ – defhlt Jul 17 '12 at 13:37
  • \$\begingroup\$ @w0lf Of course! How could I not think of that? \$\endgroup\$ – Howard Jul 17 '12 at 14:16
5
\$\begingroup\$

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:]))]
\$\endgroup\$
  • 1
    \$\begingroup\$ I think you can remove the &(j[0][0]!=j[-1][-1]) condition; see the question comments above. \$\endgroup\$ – Cristian Lupascu Jul 16 '12 at 18:45
  • 1
    \$\begingroup\$ 124 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:]))] \$\endgroup\$ – Ev_genus Jul 16 '12 at 21:36
  • \$\begingroup\$ I'm trying to wrap my head around what's going on in this function. What exactly are j, x, y? How are they defined? I'm sorry if these questions are lame, I'm new to Python and would like to work with it some more. \$\endgroup\$ – Rob Jul 17 '12 at 22:56
  • \$\begingroup\$ @MikeDtrick: j contains a permutation of the cities, which is generated with the permutations command. The big if on the end basically validates that for all values in j, the last letter of one value in j is the same as the first letter of the next value in j. Honestly, I don't know either what the zip does, zip works in mysterious ways. \$\endgroup\$ – beary605 Jul 17 '12 at 23:17
  • \$\begingroup\$ Okay, thank you for the explanation! +1 \$\endgroup\$ – Rob Jul 18 '12 at 1:46
5
\$\begingroup\$

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}}
\$\endgroup\$
  • \$\begingroup\$ Nice idea with the max_by. And your new version inspired myself for an even newer (and shorter) one. \$\endgroup\$ – Howard Jul 17 '12 at 14:57
  • \$\begingroup\$ @Howard Thanks! Your new solution is really awesome, will be difficult to beat that. ;) \$\endgroup\$ – Ventero Jul 17 '12 at 15:57
4
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ looks similar to my variant $*.permutation{|p|p p if p.inject(p[0][0]){|m,e|m.casecmp(e[0])==0?e[-1]:?_}>?_} but yours is 9 characters shorter! \$\endgroup\$ – defhlt Jul 16 '12 at 18:48
  • 2
    \$\begingroup\$ p$*.permutation.find{|i|i.inject{|a,e|a&&e[0]=~/#{a[-1]}/i&&e}} is quite a bit shorter. A Ruby 1.8(!) solution which is even shorter: p$*.permutation.find{|i|i.inject{|a,e|a&&a[-1]-32==e[0]&&e}} \$\endgroup\$ – Ventero Jul 17 '12 at 0:03
  • \$\begingroup\$ @Ventero Using case-insensitive regex is a brilliant idea! Please post this as your own answer; I'm not worthy to use that. :) \$\endgroup\$ – Cristian Lupascu Jul 17 '12 at 6:19
  • \$\begingroup\$ @Ventero the -32 solution is also very ingenious, but it relies on the fact that names start with an uppercase letter and end with a lowercase, which may not always be the case. \$\endgroup\$ – Cristian Lupascu Jul 17 '12 at 6:22
  • \$\begingroup\$ @w0lf You're right, I thought I read in the specs that it would be the case, but obviously I'm mistaken. ;) \$\endgroup\$ – Ventero Jul 17 '12 at 12:01
3
\$\begingroup\$

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
\$\endgroup\$
  • 1
    \$\begingroup\$ Woohoo, bogo-sort style! \$\endgroup\$ – beary605 Jul 17 '12 at 15:16
3
\$\begingroup\$

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!

\$\endgroup\$
  • \$\begingroup\$ You can get rid of the Data.Char import with last b==[r!!0!!0..]!!32. Also, you don't need parens in g[x|x<-c,x/=b] \$\endgroup\$ – Lynn May 4 '18 at 10:39
  • 1
    \$\begingroup\$ @Lynn nice, I somehow thought fromEnum would be a must. Funny, I took those parentheses away already once, but I must have copied from the wrong tab… \$\endgroup\$ – Angs May 4 '18 at 10:51
2
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

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!

\$\endgroup\$
2
\$\begingroup\$

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
\$\endgroup\$
  • 2
    \$\begingroup\$ Some improvements: Try it online! I wrote a little changelog in the "Input" field. (Oh, after Ðf I use X to pick a random solution instead of the first one, but works just as well.) \$\endgroup\$ – Lynn May 4 '18 at 14:40
  • \$\begingroup\$ @Lynn Thank you so much! The zip part was very clever, and I think I can use that Ðf quick in a lot of my other programs to save some space! \$\endgroup\$ – Harry May 4 '18 at 15:52
1
\$\begingroup\$

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:

graph

\$\endgroup\$
1
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ Not sure it is exactly valid, but if you do #define L(x)for(int i=x;i<n;i++) and don't declare i at the beginning of main you save 1 byte. \$\endgroup\$ – Tsathoggua May 4 '18 at 11:33
1
\$\begingroup\$

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|
+----+-----+--------+------+--------+---------+------+------+
\$\endgroup\$
1
\$\begingroup\$

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);}}
\$\endgroup\$
0
\$\begingroup\$

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
\$\endgroup\$
0
\$\begingroup\$

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.