London Underground AKA The Tube является старейшим подземной железной дорогой в мире, в настоящее время он состоит из одиннадцати линий * обслуживание 267 названных станций (строго 269 ** станций , так как «Эджвэр Road» и «Хаммерсмит» каждый занимают два места)
Соревнование
Выведите названия линий, обслуживающих станцию, заданную по имени в качестве ввода.
Ввод:
строка или список символов
Можно предположить, что это действительное название станции (как указано в кодовом блоке ниже).
Вы можете предположить, что любое
&из входных данных будет всегда словомand(илиAnd) вместо этого, если хотите, просто четко сформулируйте это в своем ответе.
Выходные данные:
Отдельный выходной список со списком из одиннадцати линий, обслуживающих эту станцию:
Список строк, список списков символов, печатный текст, строка, список символов; если сомневаешься спроси.
Вы можете последовательно выводить слово
and(илиAnd) вместо любого,&если хотите, просто четко сформулируйте это в своем ответе.С оговоркой, что если при печати или возврате строки или списка символов, что используемая разделительная подстрока не присутствует ни в одном из имен строк (включая
&илиandилиAndиспользуется), - это исключает использование одного символа пробела в качестве разделителя. ,
Tube Network :
- Примечание: это конечное состояние, даже если оно содержит орфографическую ошибку (если не было решено до каких-либо ответов)
Input (Station Name) : Output (list of tube line names)
----------------------------------------------------------------------------------------------------------------
"Acton Town" : ["District","Piccadilly"]
"Aldgate" : ["Circle","Metropolitan"]
"Aldgate East" : ["District","Hammersmith & City"]
"Alperton" : ["Piccadilly"]
"Amersham" : ["Metropolitan"]
"Angel" : ["Northern"]
"Archway" : ["Northern"]
"Arnos Grove" : ["Piccadilly"]
"Arsenal" : ["Piccadilly"]
"Baker Street" : ["Bakerloo","Circle","Hammersmith & City","Jubilee","Metropolitan"]
"Balham" : ["Northern"]
"Bank" : ["Central","Northern","Waterloo & City"]
"Barbican" : ["Circle","Hammersmith & City","Metropolitan"]
"Barking" : ["District","Hammersmith & City"]
"Barkingside" : ["Central"]
"Barons Court" : ["District","Piccadilly"]
"Bayswater" : ["Circle","District"]
"Becontree" : ["District"]
"Belsize Park" : ["Northern"]
"Bermondsey" : ["Jubilee"]
"Bethnal Green" : ["Central"]
"Blackfriars" : ["Circle","District"]
"Blackhorse Road" : ["Victoria"]
"Bond Street" : ["Central","Jubilee"]
"Borough" : ["Northern"]
"Boston Manor" : ["Piccadilly"]
"Bounds Green" : ["Piccadilly"]
"Bow Road" : ["District","Hammersmith & City"]
"Brent Cross" : ["Northern"]
"Brixton" : ["Victoria"]
"Bromley-by-Bow" : ["District","Hammersmith & City"]
"Buckhurst Hill" : ["Central"]
"Burnt Oak" : ["Northern"]
"Caledonian Road" : ["Piccadilly"]
"Camden Town" : ["Northern"]
"Canada Water" : ["Jubilee"]
"Canary Wharf" : ["Jubilee"]
"Canning Town" : ["Jubilee"]
"Cannon Street" : ["Circle","District"]
"Canons Park" : ["Jubilee"]
"Chalfont & Latimer" : ["Metropolitan"]
"Chalk Farm" : ["Northern"]
"Chancery Lane" : ["Central"]
"Charing Cross" : ["Bakerloo","Northern"]
"Chesham" : ["Metropolitan"]
"Chigwell" : ["Central"]
"Chiswick Park" : ["District"]
"Chorleywood" : ["Metropolitan"]
"Clapham Common" : ["Northern"]
"Clapham North" : ["Northern"]
"Clapham South" : ["Northern"]
"Cockfosters" : ["Piccadilly"]
"Colindale" : ["Northern"]
"Colliers Wood" : ["Northern"]
"Covent Garden" : ["Piccadilly"]
"Croxley" : ["Metropolitan"]
"Dagenham East" : ["District"]
"Dagenham Heathway" : ["District"]
"Debden" : ["Central"]
"Dollis Hill" : ["Jubilee"]
"Ealing Broadway" : ["Central","District"]
"Ealing Common" : ["District","Piccadilly"]
"Earl's Court" : ["District","Piccadilly"]
"East Acton" : ["Central"]
"East Finchley" : ["Northern"]
"East Ham" : ["District","Hammersmith & City"]
"East Putney" : ["District"]
"Eastcote" : ["Metropolitan","Piccadilly"]
"Edgware" : ["Northern"]
"Edgware Road" : ["Bakerloo","Circle","District","Hammersmith & City"]
"Elephant & Castle" : ["Bakerloo","Northern"]
"Elm Park" : ["District"]
"Embankment" : ["Bakerloo","Circle","District","Northern"]
"Epping" : ["Central"]
"Euston" : ["Northern","Victoria"]
"Euston Square" : ["Circle","Hammersmith & City","Metropolitan"]
"Fairlop" : ["Central"]
"Farringdon" : ["Circle","Hammersmith & City","Metropolitan"]
"Finchley Central" : ["Northern"]
"Finchley Road" : ["Jubilee","Metropolitan"]
"Finsbury Park" : ["Piccadilly","Victoria"]
"Fulham Broadway" : ["District"]
"Gants Hill" : ["Central"]
"Gloucester Road" : ["Circle","District","Piccadilly"]
"Golders Green" : ["Northern"]
"Goldhawk Road" : ["Circle","Hammersmith & City"]
"Goodge Street" : ["Northern"]
"Grange Hill" : ["Central"]
"Great Portland Street" : ["Circle","Hammersmith & City","Metropolitan"]
"Greenford" : ["Central"]
"Green Park" : ["Jubilee","Piccadilly","Victoria"]
"Gunnersbury" : ["District"]
"Hainault" : ["Central"]
"Hammersmith" : ["Circle","District","Hammersmith & City","Piccadilly"]
"Hampstead" : ["Northern"]
"Hanger Lane" : ["Central"]
"Harlesden" : ["Bakerloo"]
"Harrow & Wealdstone" : ["Bakerloo"]
"Harrow-on-the-Hill" : ["Metropolitan"]
"Hatton Cross" : ["Piccadilly"]
"Heathrow Terminals 1, 2, 3" : ["Piccadilly"]
"Heathrow Terminal 4" : ["Piccadilly"]
"Heathrow Terminal 5" : ["Piccadilly"]
"Hendon Central" : ["Northern"]
"High Barnet" : ["Northern"]
"Highbury & Islington" : ["Victoria"]
"Highgate" : ["Northern"]
"High Street Kensington" : ["Circle","District"]
"Hillingdon" : ["Metropolitan","Piccadilly"]
"Holborn" : ["Central","Piccadilly"]
"Holland Park" : ["Central"]
"Holloway Road" : ["Piccadilly"]
"Hornchurch" : ["District"]
"Hounslow Central" : ["Piccadilly"]
"Hounslow East" : ["Piccadilly"]
"Hounslow West" : ["Piccadilly"]
"Hyde Park Corner" : ["Piccadilly"]
"Ickenham" : ["Metropolitan","Piccadilly"]
"Kennington" : ["Northern"]
"Kensal Green" : ["Bakerloo"]
"Kensington (Olympia)" : ["District"]
"Kentish Town" : ["Northern"]
"Kenton" : ["Bakerloo"]
"Kew Gardens" : ["District"]
"Kilburn" : ["Jubilee"]
"Kilburn Park" : ["Bakerloo"]
"Kingsbury" : ["Jubilee"]
"King's Cross St. Pancras" : ["Circle","Hammersmith & City","Metropolitan","Northern","Piccadilly","Victoria"]
"Knightsbridge" : ["Piccadilly"]
"Ladbroke Grove" : ["Circle","Hammersmith & City"]
"Lambeth North" : ["Bakerloo"]
"Lancaster Gate" : ["Central"]
"Latimer Road" : ["Circle","Hammersmith & City"]
"Leicester Square" : ["Northern","Piccadilly"]
"Leyton" : ["Central"]
"Leytonstone" : ["Central"]
"Liverpool Street" : ["Central","Circle","Hammersmith & City","Metropolitan"]
"London Bridge" : ["Jubilee","Northern"]
"Loughton" : ["Central"]
"Maida Vale" : ["Bakerloo"]
"Manor House" : ["Piccadilly"]
"Mansion House" : ["Circle","District"]
"Marble Arch" : ["Central"]
"Marylebone" : ["Bakerloo"]
"Mile End" : ["Central","District","Hammersmith & City"]
"Mill Hill East" : ["Northern"]
"Monument" : ["Circle","District"]
"Moorgate" : ["Circle","Hammersmith & City","Metropolitan","Northern"]
"Moor Park" : ["Metropolitan"]
"Morden" : ["Northern"]
"Mornington Crescent" : ["Northern"]
"Neasden" : ["Jubilee"]
"Newbury Park" : ["Central"]
"North Acton" : ["Central"]
"North Ealing" : ["Piccadilly"]
"North Greenwich" : ["Jubilee"]
"North Harrow" : ["Metropolitan"]
"North Wembley" : ["Bakerloo"]
"Northfields" : ["Piccadilly"]
"Northolt" : ["Central"]
"Northwick Park" : ["Metropolitan"]
"Northwood" : ["Metropolitan"]
"Northwood Hills" : ["Metropolitan"]
"Notting Hill Gate" : ["Central","Circle","District"]
"Oakwood" : ["Piccadilly"]
"Old Street" : ["Northern"]
"Osterley" : ["Piccadilly"]
"Oval" : ["Northern"]
"Oxford Circus" : ["Bakerloo","Central","Victoria"]
"Paddington" : ["Bakerloo","Circle","District","Hammersmith & City"]
"Park Royal" : ["Piccadilly"]
"Parsons Green" : ["District"]
"Perivale" : ["Central"]
"Piccadilly Circus" : ["Bakerloo","Piccadilly"]
"Pimlico" : ["Victoria"]
"Pinner" : ["Metropolitan"]
"Plaistow" : ["District","Hammersmith & City"]
"Preston Road" : ["Metropolitan"]
"Putney Bridge" : ["District"]
"Queen's Park" : ["Bakerloo"]
"Queensbury" : ["Jubilee"]
"Queensway" : ["Central"]
"Ravenscourt Park" : ["District"]
"Rayners Lane" : ["Metropolitan","Piccadilly"]
"Redbridge" : ["Central"]
"Regent's Park" : ["Bakerloo"]
"Richmond" : ["District"]
"Rickmansworth" : ["Metropolitan"]
"Roding Valley" : ["Central"]
"Royal Oak" : ["Circle","Hammersmith & City"]
"Ruislip" : ["Metropolitan","Piccadilly"]
"Ruislip Gardens" : ["Central"]
"Ruislip Manor" : ["Metropolitan","Piccadilly"]
"Russell Square" : ["Piccadilly"]
"St. James's Park" : ["Circle","District"]
"St. John's Wood" : ["Jubilee"]
"St. Paul's" : ["Central"]
"Seven Sisters" : ["Victoria"]
"Shepherd's Bush" : ["Central"]
"Shepherd's Bush Market" : ["Circle","Hammersmith & City"]
"Sloane Square" : ["Circle","District"]
"Snaresbrook" : ["Central"]
"South Ealing" : ["Piccadilly"]
"South Harrow" : ["Piccadilly"]
"South Kensington" : ["Circle","District","Piccadilly"]
"South Kenton" : ["Bakerloo"]
"South Ruislip" : ["Central"]
"South Wimbledon" : ["Northern"]
"South Woodford" : ["Central"]
"Southfields" : ["District"]
"Southgate" : ["Piccadilly"]
"Southwark" : ["Jubilee"]
"Stamford Brook" : ["District"]
"Stanmore" : ["Jubilee"]
"Stepney Green" : ["District","Hammersmith & City"]
"Stockwell" : ["Northern","Victoria"]
"Stonebridge Park" : ["Bakerloo"]
"Stratford" : ["Central","Jubilee"]
"Sudbury Hill" : ["Piccadilly"]
"Sudbury Town" : ["Piccadilly"]
"Swiss Cottage" : ["Jubilee"]
"Temple" : ["Circle","District"]
"Theydon Bois" : ["Central"]
"Tooting Bec" : ["Northern"]
"Tooting Broadway" : ["Northern"]
"Tottenham Court Road" : ["Central","Northern"]
"Tottenham Hale" : ["Victoria"]
"Totteridge & Whetstone" : ["Northern"]
"Tower Hill" : ["Circle","District"]
"Tufnell Park" : ["Northern"]
"Turnham Green" : ["District","Piccadilly"]
"Turnpike Lane" : ["Piccadilly"]
"Upminster" : ["District"]
"Upminster Bridge" : ["District"]
"Upney" : ["District"]
"Upton Park" : ["District","Hammersmith & City"]
"Uxbridge" : ["Metropolitan","Piccadilly"]
"Vauxhall" : ["Victoria"]
"Victoria" : ["Circle","District","Victoria"]
"Walthamstow Central" : ["Victoria"]
"Wanstead" : ["Central"]
"Warren Street" : ["Northern","Victoria"]
"Warwick Avenue" : ["Bakerloo"]
"Waterloo" : ["Bakerloo","Jubilee","Northern","Waterloo & City"]
"Watford" : ["Metropolitan"]
"Wembley Central" : ["Bakerloo"]
"Wembley Park" : ["Jubilee","Metropolitan"]
"West Acton" : ["Central"]
"West Brompton" : ["District"]
"West Finchley" : ["Northern"]
"West Ham" : ["District","Hammersmith & City","Jubilee"]
"West Hampstead" : ["Jubilee"]
"West Harrow" : ["Metropolitan"]
"West Kensington" : ["District"]
"West Ruislip" : ["Central"]
"Westbourne Park" : ["Circle","Hammersmith & City"]
"Westminster" : ["Circle","District","Jubilee"]
"White City" : ["Central"]
"Whitechapel" : ["District","Hammersmith & City"]
"Willesden Green" : ["Jubilee"]
"Willesden Junction" : ["Bakerloo"]
"Wimbledon" : ["District"]
"Wimbledon Park" : ["District"]
"Wood Green" : ["Piccadilly"]
"Wood Lane" : ["Circle","Hammersmith & City"]
"Woodford" : ["Central"]
"Woodside Park" : ["Northern"]
... одиннадцать имен строк:
Bakerloo
Central
Circle
District
Hammersmith & City
Jubilee
Metropolitan
Northern
Piccadilly
Victoria
Waterloo & City
* Транспорт Для Лондона также управляют другими железнодорожными линиями, некоторые из них также могут упоминаться как часть "The Tube" (скорее всего, "Docklands Light Railway" или "DLR"), но мы будем придерживаться одиннадцати, перечисленных здесь.
** На связанной странице Википедии в настоящее время указано 270, но я считаю, что они ошибочно считают второе местоположение Кэнэри-Уорф, хотя оно обслуживает только "DLR")
Куча мнимых очков брауни (и, скорее всего, также много голосов против) для подачи в гольф с использованием Mornington Crescent (совместимая IDE доступна здесь )!
Это код-гольф , поэтому самый короткий код в байтах выигрывает для каждого языка, а самое короткое решение выигрывает (не позволяйте языкам игры в гольф отталкивать вас от игры в гольф на других языках). Повеселись!
code-golf
graph-theory
compression
Джонатан Аллан
источник
источник
Ответы:
Mathematica 8+, 266 байт
Это решение изначально имело такое же количество байтов, что и станции. Я предполагаю, что это может быть занято в гольфе еще приблизительно 50 байтами, но это казалось подходящим местом, чтобы остановиться пока.
Введение
Mathematica хорошо известна своей большой стандартной библиотекой и доступом к большой онлайновой «вычислимой базе знаний». Я нагло искал Wolfram | Alpha, надеясь легко найти соответствующие данные о транзите, но, хотя он понимает область моего запроса, эти данные пока недоступны .
К счастью, обширная встроенная документация Mathematica поставляется с аккуратными примерами. Некоторые из этих страниц просто используют сеть London Underground для демонстрации функциональности, связанной с графами. Мы будем использовать график из примера «Планирование поездки» из-за его короткого имени.
Вот другие интересные варианты использования той же сети .
Я не верю, что программный доступ к собственной документации Mathematica относится к лазекам типа «Извлечение из внешнего источника» .
Импортируйте страницу примера
Мы можем импортировать страницу примера в виде выражения блокнота :
Можно извлечь весь график из глубины блокнота выражения:
Обратите внимание, что вершины графа - это просто названия станций. Края имеют пользовательское
"Lines"свойство, представляющее собой список строк, представляющих линии, которые проходят между двумя его станциями:Теперь мы можем найти все прямые, проходящие через вершину, получив все ее инцидентные ребра из
IncidenceList[g, vertex]отображенияPropertyValue[{g, edge}, "Lines"]их и так далее.Однако мы пропустим описанный выше метод и сэкономим много байтов путем сопоставления с шаблоном для соответствующей части
Graphконструктора -Propertiesопции.Извлечь строки
GraphКонструктор имеет следующий формат:(Вы можете увидеть это, проверив
FullForm[g]или прочитав исходный кодTripPlanning.nb- для его полного пути, запуститеFindFile["ExamplePages/TripPlanning.nb"].)Вот пример одного свойства ребра:
Давайте превратим это выражение в компактный шаблон:
Сделать таблицу поиска
Теперь мы можем соответствовать
v1,v2иlines, но мы хотим{v1 -> lines, v2 -> lines}. Полезно,Casesможет одновременно соответствовать шаблону и преобразовывать его.Это производит список формы
{{v1 -> lines, v2 -> lines}, {v1 -> lines, v3 -> lines}, ...}. Наконец, мы объединяем список по вершине:В менее чем 90 байтах мы создали почти идеальную таблицу поиска для линий каждой станции.
Исправить опечатки
К сожалению, некоторые названия станций написаны с ошибками или отсутствуют.
Нечеткое совпадение строк должно заботиться о опечатках. Мы можем найти
Nearestназвание станции с ошибкой в названии станции ввода:Замените входы
"Wood Lane"и"Shepherd's Bush Market"(новые станции) на"Royal Oak", так как эти три станции имеют одинаковые линии:Составьте эти функции, чтобы получить поддельное имя станции, посмотреть ее строки в таблице и сохранить в
r:Исправить устаревшие
Сеть также немного устарела из-за капитального ремонта кольцевой линии.
Если входной станцией является
"Hammersmith"или если возвращается только таблица поиска{"Hammersmith & City"}, добавьте"Circle"к строкам.Удалить посторонние линии
На графике есть несколько строк, которые нам не нужны, поэтому удалите их:
Это оно!
Попытайся! (с обходными путями)
Если вы хотите поиграть с моим решением, но у вас нет Mathematica, вы можете воспользоваться бесплатным облаком программирования Wolfram. Идите сюда , нажмите
Create a New Notebook, затем подождите.К сожалению, у платформы есть некоторые ограничения, которые мешают моему коду импорта ноутбука. Вот некоторые грубые обходные пути:
Поскольку страницы с примером нет, мы можем попытаться использовать функцию копирования ввода в буфер обмена из онлайн-документации. Я использовал инструменты разработчика своего браузера и увидел, что был сделан запрос
http://reference.wolfram.com/language/example/Files/TripPlanning.en/i_1.txt(предупреждение: большой). Однако прокси-сервер платформы не разрешает доменreference.wolfram.com, поэтому я сделал это вручную.Сначала вставьте это и нажмите, shift+enterчтобы выполнить. Теперь замените
<<ExamplePages/TripPlanning.nbнаgWorkaround.Тестовые данные
Вызовите функцию
fи проверьте ее по заданным данным:источник
ES6, Node.js / Chrome,
989977931892889887 байтПолный набор тестов (Node.js)
Попробуйте онлайн!
Демо (Chrome)
Примечание : из-за несоответствий в реализации
parseInt()между браузерами (1) , это гарантированно будет работать только для всех станций в Chrome.Показать фрагмент кода
(1) Из спецификации : Пусть mathInt будет математическим целочисленным значением, которое представлено Z в обозначении radix-R [...]. Если R не равен 2, 4, 8, 10, 16 или 32, тогда mathInt может быть зависимым от реализации приближением математического целочисленного значения, которое представлено Z в обозначении radix-R.
Как?
Ниже приведен пример пошагового декодирования для ввода
s = "St. James's Park".Шаг 1
Сначала мы расширяем основную таблицу поиска (от 503 до 2328 байт), расширяя все ее символы заполнения. Эти символы кодируются кодом ASCII больше 92, тогда как данные полезной нагрузки используют диапазон 48-90.
Шаг 2
Мы удаляем все не алфавитные символы из входной строки:
который дает
"StJamessPark".Шаг 3
Мы анализируем полученную строку как величину base-36:
который дает
3793395908848905700(это приблизительный результат, возвращаемый Chrome V8 ).Шаг № 4
Мы вычисляем значение хеша:
который дает
533.Примечание : из-за потери точности этот результат не является математически правильным (так и должно быть
184). Но справочная таблица была, конечно же, построена таким же образом, так что именно этого мы и ожидали.Шаг № 5
Мы извлекаем ASCII-код символа в этой позиции в основной справочной таблице:
который дает
58(это персонаж':').Шаг № 6
Мы используем это значение для извлечения двухсимвольной строки из вторичной таблицы поиска:
который дает
0c.Шаг № 7
Мы анализируем эту строку как величину base-36:
который дает
12.Шаг № 8
Наконец, мы фильтруем список станций в соответствии с установленными битами
msk, начиная с наименее значимого:В нашем примере
mskвыполняется12, что00000001100в двоичном виде. Таким образом , мы держим 3 - й и 4 - й станции, что приводит к конечному результату:[ 'Circle', 'District' ].источник
Northern.Котлин ,
2271227020001694 байтукрашенный
Тест
Правки
Убраны ненужные разделители труб -270 байт
Сжатый с почтовыми инструментами -306 байтов
источник
Python 2 ,
230923012218 байтПопробуйте онлайн!
-6 спасибо мистеру Xcoder .
Слишком долго ... может быть, это гольф.
источник
Корица Камедь , 2100 байт
HexDump:
Попробуйте онлайн!
Я не сомневаюсь, что это может быть много в гольф лучше, проблема заключается в отсутствии полных документов Cinnamon Gum. (@quartata, пожалуйста, у этого есть большой шанс быть удивительным троллем). Я мог бы покопаться в исходном коде, чтобы посмотреть, есть ли что-нибудь, что может быть полезным для этого.
Это скрипт Python, который я взломал, чтобы создать сжатую строку.
источник
PHP,
178517801471 байтукрашенный
объяснение
Чтобы различить название станции с таким количеством символов, я немного поиграл и обнаружил, что если бы я взял 22-й, 23-й и 24-й символы хэша MD5, он был бы уникальным, за исключением ОДНОГО столкновения:
ddbмогло бы означатьHeathrow Terminals 1, 2, 3как дляDagenham Heathway.Чтобы сослаться на 11 названий линий трубки, я просто использую шестнадцатеричную цифру от 0 до A.
Затем я создал разделенный запятыми список подстрок хеша MD5, с соответствующими цифрами линии трубки рядом с ним. Но я исключил из
Heathrow Terminals 1, 2, 3списка, чтобы избежать столкновения.Пример:
fe538означает, что любая станция с именем md5, имеющая символыfe5на 22-м, 23-м и 24-м месте, запускает линии трубки, на которые указывают3и8. ЗначениеActon Townпроходит по трубным линиямDistrictиPiccadilly.Затем я написал простую функцию, которая проверяет ввод. MD5 хеширует это. Принимает 22-го, 23-го и 24-го персонажа. Сопоставляет его со списком, который я создал. И показывает соответствующие названия труб. За
ddbисключением отклонения от курса, которое жестко закодированоPiccadilly, когда заданная строка начинается сH.Правки
array()с[]для -5 символовeval(gzinflate(base64_decode()))для -309 символовисточник
Python 2 ,
1430,1418,1416 байт.Попробуйте онлайн!
Пояснение Входные данные кодируются в виде двоичного представления (8-битный код ASCII для каждой буквы входного слова) при заполнении входного слова пробелами справа, если длина слова меньше 26. Я уже сделал такое же представление для все возможные входы и найти минимальные биты, которые дифференцируют выходы. Код просматривает эти конкретные биты, чтобы принять решение о выводе.
источник
s=(s+' '*22)[:26]вместоs+=' '*(26-len(s)).n=0newlinefor e in(input()+' '*26)[:26]:n=n*256+ord(e). Еще два, используяn=i=0сверху тоже.SyntaxError: Non-ASCII character...когда пытаюсь это сделать) - может понадобиться заголовок кодировки или что-то в этом роде.Jotlin 1.0 , 1539 байт
представление
Тестовый код
источник