2011-05-03

Spoiler alert: Code to solve GoogleNexus Challenge #4

SPOILER ALERT: Don't read this if you haven't yet given up on GoogleNexus challenge #4!
It's a great puzzle, try to figure it out first.

--

Yesterday's GoogleNexus Challenge took you to this page which linked to this map of urban rail systems.  There were actually two puzzles embedded in the challenge: The first puzzle involved the colored circles at the top, which corresponded to line crossings, and the numbers corresponded to the index of the letter to take in the crossing name.  Reading off these letters gave LONDON.  Then there was a list of seemingly random words which are actually anagrams of London Tube stop names, only missing a letter.  The missing letters (one per line) spell out the answer, "Please send me a Nexus S so Google goodies I can access".

You could totally do this by hand if you're good with anagrams, but since comparing 44 anagrams (that are each missing a letter) to 306 tube stops is not my idea of fun, I wrote code to do it.

Here's the code I wrote to solve the puzzle (after copying the list of tube stops from Wikipedia).  I basically cross out one letter at a time  from the anagram in the station name, then output the single letter that results.

Don't judge my code, I wrote this at light speed...




import java.util.ArrayList;


public class Main {


    static String[] stations = {


    "Acton Town", "Aldgate", "Aldgate East", "All Saints", "Alperton", "Amersham", "Angel", "Archway", "Arnos Grove", "Arsenal",
            "Baker Street", "Balham", "Bank", "Barbican", "Barking", "Barkingside", "Barons Court", "Bayswater", "Beckton",
            "Beckton Park", "Becontree", "Belsize Park", "Bermondsey", "Bethnal Green", "Blackfriars [ 9 ]", "Blackhorse Road",
            "Blackwall", "Bond Street", "Borough", "Boston Manor", "Bounds Green", "Bow Church", "Bow Road", "Brent Cross",
            "Brixton", "Bromley-by-Bow", "Buckhurst Hill", "Burnt Oak", "Caledonian Road", "Camden Town", "Canada Water",
            "Canary Wharf", "Canary Wharf", "Canning Town", "Cannon Street", "Canons Park", "Chalfont & Latimer", "Chalk Farm",
            "Chancery Lane", "Charing Cross", "Chesham", "Chigwell", "Chiswick Park", "Chorleywood", "Clapham Common",
            "Clapham North", "Clapham South", "Cockfosters", "Colindale", "Colliers Wood", "Covent Garden", "Crossharbour",
            "Croxley", "Custom House", "Cutty Sark for Maritime Greenwich", "Cyprus", "Dagenham East", "Dagenham Heathway",
            "Debden", "Deptford Bridge", "Devons Road", "Dollis Hill", "Ealing Broadway", "Ealing Common", "Earl's Court",
            "East Acton", "East Finchley", "East Ham", "East India", "East Putney", "Eastcote", "Edgware", "Edgware Road",
            "Edgware Road", "Elephant & Castle", "Elm Park", "Elverson Road", "Embankment", "Epping", "Euston", "Euston Square",
            "Fairlop", "Farringdon", "Finchley Central", "Finchley Road", "Finsbury Park", "Fulham Broadway", "Gallions Reach",
            "Gants Hill", "Gloucester Road", "Golders Green", "Goldhawk Road", "Goodge Street", "Grange Hill",
            "Great Portland Street", "Greenford", "Green Park", "Greenwich", "Gunnersbury", "Hainault", "Hammersmith",
            "Hammersmith", "Hampstead", "Hanger Lane", "Harlesden", "Harrow & Wealdstone", "Harrow-on-the-Hill", "Hatton Cross",
            "Heathrow Terminals 1, 2, 3", "Heathrow Terminal 4", "Heathrow Terminal 5", "Hendon Central", "Heron Quays",
            "High Barnet", "Highbury & Islington", "Highgate", "High Street Kensington", "Hillingdon", "Holborn", "Holland Park",
            "Holloway Road", "Hornchurch", "Hounslow Central", "Hounslow East", "Hounslow West", "Hyde Park Corner", "Ickenham",
            "Island Gardens", "Kennington", "Kensal Green", "Kensington (Olympia)", "Kentish Town", "Kenton", "Kew Gardens",
            "Kilburn", "Kilburn Park", "King George V", "Kingsbury", "King's Cross St. Pancras", "Knightsbridge", "Ladbroke Grove",
            "Lambeth North", "Lancaster Gate", "Langdon Park", "Latimer Road", "Leicester Square", "Lewisham", "Leyton",
            "Leytonstone", "Limehouse", "Liverpool Street", "London Bridge", "London City Airport", "Loughton", "Maida Vale",
            "Manor House", "Mansion House", "Marble Arch", "Marylebone", "Mile End", "Mill Hill East", "Monument", "Moorgate",
            "Moor Park", "Morden", "Mornington Crescent", "Mudchute", "Neasden", "Newbury Park", "North Acton", "North Ealing",
            "North Greenwich", "North Harrow", "North Wembley", "Northfields", "Northolt", "Northwick Park", "Northwood",
            "Northwood Hills", "Notting Hill Gate", "Oakwood", "Old Street", "Osterley", "Oval", "Oxford Circus", "Paddington",
            "Park Royal", "Parsons Green", "Perivale", "Piccadilly Circus", "Pimlico", "Pinner", "Plaistow", "Pontoon Dock",
            "Poplar", "Preston Road", "Prince Regent", "Pudding Mill Lane", "Putney Bridge", "Queen's Park", "Queensbury",
            "Queensway", "Ravenscourt Park", "Rayners Lane", "Redbridge", "Regent's Park", "Richmond", "Rickmansworth",
            "Roding Valley", "Royal Albert", "Royal Oak", "Royal Victoria", "Ruislip", "Ruislip Gardens", "Ruislip Manor",
            "Russell Square", "St. James's Park", "St. John's Wood", "St. Paul's", "Seven Sisters", "Shadwell", "Shepherd's Bush",
            "Shepherd's Bush Market", "Sloane Square", "Snaresbrook", "South Ealing", "South Harrow", "South Kensington",
            "South Kenton", "South Quay", "South Ruislip", "South Wimbledon", "South Woodford", "Southfields", "Southgate",
            "Southwark", "Stamford Brook", "Stanmore", "Stepney Green", "Stockwell", "Stonebridge Park", "Stratford",
            "Sudbury Hill", "Sudbury Town", "Swiss Cottage", "Temple", "Theydon Bois", "Tooting Bec", "Tooting Broadway",
            "Tottenham Court Road", "Tottenham Hale", "Totteridge & Whetstone", "Tower Gateway", "Tower Hill", "Tufnell Park",
            "Turnham Green", "Turnpike Lane", "Upminster", "Upminster Bridge", "Upney", "Upton Park", "Uxbridge", "Vauxhall",
            "Victoria", "Walthamstow Central", "Wanstead", "Warren Street", "Warwick Avenue", "Waterloo", "Watford",
            "Wembley Central", "Wembley Park", "West Acton", "West Brompton", "West Finchley", "West Ham", "West Hampstead",
            "West Harrow", "West India Quay", "West Kensington", "West Ruislip", "West Silvertown", "Westbourne Park", "Westferry",
            "Westminster", "White City", "Whitechapel", "Willesden Green", "Willesden Junction", "Wimbledon", "Wimbledon Park",
            "Wood Green", "Wood Lane", "Woodford", "Woodside Park", "Woolwich Arsenal" };


    static String[] matches = { "renumber digits", "rub ink", "long hiatus", "big redskin", "damp heat", "calming moon",
            "third felon", "neutral pink", "technical flyer", "robs enemy", "sea honour", "saintly chef", "two cents",
            "old enchanter", "sparkle biz", "crocus fiord", "dusty brown", "ruby queen", "rich garcons", "sardine gland",
            "sans broker", "hated seaman", "not tensely", "gloved barker", "noted cavern", "evilest trooper", "scarlet esquire",
            "educators role", "manly beer", "carrot nubs", "thinks bigger", "hawthorn holler", "nocturnal howls", "diurnal gripes",
            "mad realtor", "gas alternate", "civil oratory", "orange press", "english carol", "tallest peahen", "rare lotus",
            "clan idol", "concerning torment", "darn heel" };


    public static void main(String[] args) {
        ArrayList<String> stops = new ArrayList<String>();
        for (String s : stations) {
            String sout = "";
            for (int i = 0; i < s.length(); i++) {
                char c = Character.toLowerCase(s.charAt(i));
                if (c >= 'a' && c <= 'z')
                    sout += c;
            }
            stops.add(sout);
        }


        for (String m : matches) {
            for (String s : stops) {
                if (s.length() == m.length()) {
                    StringBuffer buf = new StringBuffer(s);
                    for (int i = 0; i < m.length(); i++) {
                        char c = m.charAt(i);
                        if (c != ' ') {
                            int p = buf.indexOf(c + "");
                            if (p >= 0) {
                                buf.setCharAt(p, ' ');
                            }
                        }
                    }
                    String bs = buf.toString().trim();
                    if (bs.length() == 1)
                        System.out.print(bs);
                }
            }
        }
    }
}




10 comments:

  1. I can't imagine how you noticed the connection between the stops and the words in the puzzle :) Congrats

    ReplyDelete
  2. Congrats ! Wonderfully solved.. !

    ReplyDelete
  3. Haha, how did you even find this blog post? I wasn't going to publicize it until people had had a chance to solve the puzzle. I guess Google's realtime indexing is working nicely.

    ReplyDelete
  4. Here's a simple Python implementation, which might be easier to understand (it assumes the "matches" and "stations" variables have been set). Note that rather than remove a letter from the station name, I add a letter to the match:

    from string import ascii_lowercase

    def clean(s):
        return sorted(c for c in s.lower() if c in ascii_lowercase)

    for match in matches:
        for station in stations:
            for letter in ascii_lowercase:
                if clean(match + letter) == clean(station):
                    print letter

    ReplyDelete
  5. Yeah, that's a much nicer approach. Java pretty much sucks :-)

    ReplyDelete
  6. O_O oh so that's what it meant... people just kept putting that up and I didn't understand what they were saying :)

    Nice work, I really suck at those challenges... my answer was "3" cause only 3 or those random phrases had the letters of london.

    Maybe it would be a good idea for me to learn programming :)

    Awesome post!

    ReplyDelete
  7. Haha, pretty impressive, Luke!

    There are a lot of places your code could be cleaned up, but I'm not here to judge.

    ReplyDelete
  8. Yeah, the code sucks, partly because Java sucks and forces you to write boilerplate code. I'm not proud.

    ReplyDelete
  9. Nice job. How did you know the phrases were imperfect anagrams for London Tube stops? I too realized that the phrases were anagrams, and I also thought to check out the London Tube map, but I never imagined the phrases were all exactly one letter short of the location names. Clearly, you were 100% sure of this fact by the time you wrote the script. So what tipped you off? Did you just cross reference the map with the phrases by eye until something jumped out at you or what?

    ReplyDelete
  10. Great question Casey -- what tipped me off was this: http://ni.chol.as/media/geoff-files/sillymaps/anagrammap.gif

    I forget what my exact search terms were, but I did a Google Image search for "London Tube map" or something similar, and this was the first image that came up. I don't know London at all so I thought it was the real map at first, and I was laughing at the quirkiness of British culture. "Seriously, who names their subway stops things like 'Ogre Awarded', 'Strange Perk' or 'Togetherness Thinking'?" I mean, I know England has some pretty darned weird names for historical reasons, so I didn't question it :-) Then I crossed the threshold of incredulity and I thought they must be plays on word sounds or placename meanings -- somehow I missed the fact that it was linked from this page: http://ni.chol.as/media/sillytube.html

    Anyway once I realized it was an anagram map, I thought I had the key in-hand. But then I realized I couldn't see any matches between the list of clues and the map.

    So, long story short, I figured if they were anagrams, finding the shortest match would be the easiest, so I picked the one that ended up matching Kilburn. But visual search over an image was taking forever, even to verify a short match. So I took a risk and simply assumed the theory might be right, even if it would lose me time, and I found a text-based list on Wikipedia, pasted into a spreadsheet to pull out the first column, pasted into gedit to add the quotes and commas at every newline, pasted into eclipse, and wrote a quick program to loop through each string to list just strings for which str.contains("k") && str.contains("i") && str.contains("l") etc. I got a match so I hurriedly wrote the rest.

    I only won by 2 minutes, and the second guy did it by pasting strings into an online anagram applet of some sort. I don't know how he did it because I have no idea how an anagram applet could handle the missing letter...

    One quick way to do this by hand is to realize you only have to match clues to station names that are the same length (including the space in the clue and not including spaces in the station name). That cuts down on a lot of the work.

    ReplyDelete