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