Вы никогда не задумывались, какие страны окружают другие? Я тоже, иногда, и, ну, вот вызов для этого.
Я предоставил список стран и стран, к которым они относятся, которые вы должны узнать в нижней части этого поста в блоке кода. Вам необходимо создать полную программу, которая выводит (наиболее удобным для вас способом на вашем языке) список слоев стран смежных стран в страну ввода. Так, например:
>>> "United Kingdom" 1
Republic of IrelandПотому что "United Kingdom"это название страны и 1количество слоев, которые вы хотите сделать. Фактически, вернется любое количество слоев (кроме 0) Republic of Ireland, потому что на пути к любым другим странам есть море.
Справочная карта:
Примеры (все, что в скобках - это комментарии) (очевидно, порядок вывода не имеет значения):
>>> Bhutan 2
India (layer 1, touching Bhutan)
China (layer 1, touching Bhutan)
Bangladesh (layer 2, touching India)
Myanmar (layer 2, touching China and India)
Laos (layer 2, touching China)
Vietnam (layer 2, touching China)
North Korea (layer 2, touching China)
Russia (layer 2, touching China)
Mongolia (layer 2, touching China)
Kazakstan (layer 2, touching China)
Uzbekistan (layer 2, touching China)
Afganistan (layer 2, touching China)
Pakistan (layer 2, touching China and India)
Kashmir (layer 2, touching China and India)
Nepal (layer 2, touching China and India)>>> Russia 0 (no layers used)
>>> Cyprus 1800 (there's a sea in the way)
>>> "The Gambia" 4 (there's a sea in the way)
Senegal (layer 1)
Mauritania (layer 2)
Mali (layer 2)
Guinea (layer 2)
Guinea-Bissau (layer 2)
Sierra Leone (layer 3)
Liberia (layer 3)
Cote D'Ivoire (layer 3)
Burkina Faso (layer 3)
Niger (layer 3)
Algeria (layer 3)
Western Sahara (layer 3)
Morocco (layer 4)
Tunisia (layer 4)
Libya (layer 4)
Chad (layer 4)
Nigeria (layer 4)
Benin (layer 4)
Togo (layer 4)
Ghana (layer 4)Поскольку мир большой, вы должны компенсировать это, сделав свой код маленьким. В конце концов, это код-гольф .
Список касаний (в произвольном порядке, возможно, в разбираемом формате) (если здесь есть ошибки, пожалуйста, дайте мне знать . Я проходил через это много раз, но я обязательно совершил несколько ошибок):
USA touches: Canada, Mexico
Canada touches: USA
Mexico touches: USA, Belize, Guatemala
Guatemala touches: Mexico, Belize, El Salvador, Honduras
Belize touches: Mexico, Guatemala
El Salvador touches: Guatemala, Honduras
Honduras touches: Guatemala, El Salvador, Nicaragua
Nicaragua touches: Honduras, San Jose
San Jose touches: Nicaragua, Panama
Panama touches: San Jose, Columbia
Columbia touches: Venezuela, Brazil, Peru, Ecuador, Panama
Venezuela touches: Columbia, Brazil, Guyana
Guyana touches: Venezuela, Brazil, Suriname
Suriname touches: Guyana, Brazil, French Guiana
French Guiana touches: Suriname, Brazil
Brazil touches: Columbia, Venezuela, Guyana, Suriname, French Guiana, Peru, Bolivia, Paraguay, Argentina, Uruguay
Ecuador touches: Columbia, Peru
Peru touches: Ecuador, Columbia, Brazil, Bolivia, Chile
Bolivia touches: Peru, Brazil, Paraguay, Argentina, Chile
Chile touches: Peru, Bolivia, Argentina
Paraguay touches: Bolivia, Brazil, Argentina
Argentina touches: Chile, Bolivia, Paraguay, Brazil, Uruguay
Uruguay touches: Argentina, Brazil
The Bahamas touches:
Cuba touches:
Jamaica touches:
Haiti touches: Dominican Republic
Dominican Republic touches: Haiti
Puerto Rico touches:
Saint Kitts and Nevis touches:
Montserrat touches:
Guadeloupe touches:
Dominica touches:
Martinique touches:
Saint Vincent touches:
Barbados touches:
Trinidad and Tobago touches:
Greenland touches:
Azores touches:
Falkland Islands touches:
South Georgia touches:
Cape Verde touches:
Madeira Island touches:
Canary Islands touches:
Faroe Islands touches:
Republic of Ireland touches: United Kingdom
United Kingdom touches: Republic of Ireland
Svalbard touches:
Norway touches: Sweden, Finland, Russia
Sweden touches: Norway, Finland
Finland touches: Sweden, Norway, Russia
Russia touches: Norway, Finland, Estonia, Latvia, Belarus, Ukraine, Turkey, Armenia, Azerbaijan, Kazakhstan, China, Mongolia, North Korea
Denmark touches: Germany
Estonia touches: Russia, Latvia
Latvia touches: Estonia, Russia, Belarus, Lithuania
Lithuania touches: Latvia, Belarus, Poland
Belarus touches: Lithuania, Latvia, Russia, Ukraine, Poland
Germany touches: Luxembourg, Belgium, Netherlands, Denmark, Poland, Czech Republic, Austria, Liechtenstein, Switzerland, France
Netherlands touches: Germany, Belgium
Belgium touches: France, Netherlands, Germany, Luxembourg
Luxembourg touches: France, Belgium, Germany
Poland touches: Germany, Lithuania, Belarus, Ukraine, Slovakia, Czech Republic
Ukraine touches: Slovakia, Poland, Belarus, Russia, Romania, Moldova, Hungary
Czech Republic touches: Germany, Poland, Slovakia, Austria
Slovakia touches: Austria, Czech Republic, Poland, Ukraine, Hungary
Moldova touches: Ukraine, Romania
Romania touches: Hungary, Ukraine, Moldova, Bulgaria, Serbia
Hungary touches: Austria, Slovakia, Ukraine, Romania, Serbia, Croatia, Slovenia
Austria touches: Liechtenstein, Germany, Czech Republic, Slovakia, Hungary, Slovenia, Italy, Switzerland
Liechtenstein touches: Switzerland, Germany, Austria
France touches: Belgium, Luxembourg, Germany, Switzerland, Italy, Spain
Switzerland touches: France, Germany, Liechtenstein, Austria, Italy
Slovenia touches: Italy, Austria, Hungary, Croatia
Croatia touches: Slovenia, Hungary, Serbia, Bosnia and Herzegovina
Bosnia and Herzegovina touches: Croatia, Serbia, Montenegro
Serbia touches: Bosnia and Herzegovina, Croatia, Hungary, Romania, Bulgaria, Macedonia, Albania, Montenegro
Bulgaria touches: Serbia, Romania, Turkey, Greece, Macedonia
Montenegro touches: Bosnia and Herzegovina, Serbia, Albania
Albania touches: Montenegro, Serbia, Macedonia, Greece
Macedonia touches: Albania, Serbia, Bulgaria, Greece
Italy touches: France, Switzerland, Austria, Slovenia
Spain touches: Portugal, France
Portugal touches: Spain
Greece touches: Albania, Macedonia, Bulgaria, Turkey
Turkey touches: Greece, Russia, Armenia, Azerbaijan, Iran, Iraq, Syria, Bulgaria
Malta touches:
Cyprus touches:
Armenia touches: Turkey, Russia, Azerbaijan, Iran
Azerbaijan touches: Turkey, Armenia, Russia, Iran
Kazakhstan touches: Russia, China, Uzbekistan, Turkmenistan
Mongolia touches: China, Russia
North Korea touches: China, Russia, South Korea
South Korea touches: North Korea
China touches: Afghanistan, Uzbekistan, Kazakhstan, Russia, Mongolia, North Korea, Vietnam, Laos, Myanmar, India, Bhutan, Nepal, Kashmir
Uzbekistan touches: Kazakhstan, China, Afghanistan, Turkmenistan
Afghanistan touches: Iran, Turkmenistan, Uzbekistan, China, Kashmir, Pakistan
Turkmenistan touches: Kazakhstan, Uzbekistan, Afghanistan, Iran
Iran touches: Iraq, Turkey, Azerbaijan, Armenia, Turkmenistan, Afghanistan, Pakistan
Iraq touches: Jordan, Syria, Turkey, Iran, Kuwait, Saudi Arabia
Syria touches: Lebanon, Turkey, Iraq, Jordan, Israel
Lebanon touches: Israel, Syria
Israel touches: Egypt, Lebanon, Syria, Jordan
Jordan touches: Israel, Syria, Iraq, Saudi Arabia
Saudi Arabia touches: Jordan, Iraq, Kuwait, Qatar, United Arab Emirates, Oman, Yemen
Kuwait touches: Iraq, Saudi Arabia
Qatar touches: Saudi Arabia
United Arab Emirates touches: Saudi Arabia, Oman
Oman touches: Saudi Arabia, United Arab Emirates, Yemen
Yemen touches: Saudi Arabia, Oman
Pakistan touches: Iran, Afghanistan, Kashmir, India
Kashmir touches: Pakistan, Afghanistan, China, India
India touches: Pakistan, Kashmir, Nepal, Bhutan, Myanmar, Bangladesh, China
Nepal touches: India, China
Bhutan touches: India, China
Bangladesh touches: India, Myanmar
Sri Lanka touches:
Adaman and Nicobar Islands touches:
Myanmar touches: Bangladesh, India, China, Laos, Thailand
Thailand touches: Myanmar, Laos, Cambodia, Malaysia
Laos touches: Myanmar, China, Vietnam, Cambodia, Thailand
Vietnam touches: Laos, China, Cambodia
Cambodia touches: Thailand, Laos, Vietnam
Malaysia touches: Thailand, Brunei, Indonesia
Brunei touches: Malaysia
Phillipines touches:
Indonesia touches: Malaysia, Papua New Guinea
Papua New Guinea touches: Indonesia
Australia touches:
Tasmania touches:
Japan touches:
Guam touches:
Solomon Islands touches:
Vanuatu touches:
Fiji touches:
New Caledonia touches:
New Zealand touches:
Kerguelen Island touches:
Heard Island touches:
Mauritius touches:
Reunion touches:
Mayotte touches:
Comoros touches:
Madagascar touches:
Sao Tome touches:
Bioko touches:
Egypt touches: Libya, Israel, Sudan
Libya touches: Algeria, Tunisia, Egypt, Sudan, Chad, Niger
Tunisia touches: Algeria, Libya
Algeria touches: Western Sahara, Morocco, Tunisia, Libya, Niger, Mali, Mauritania
Morocco touches: Western Sahara, Algeria
Western Sahara touches: Morocco, Algeria, Mauritania
Mauritania touches: Western Sahara, Algeria, Mali, Senegal
Senegal touches: The Gambia, Mauritania, Mali, Guinea, Guinea-Bissau
The Gambia touches: Senegal
Guinea-Bissau touches: Senegal, Guinea
Guinea touches: Guinea-Bissau, Senegal, Mali, Cote D'Ivoire, Liberia, Sierra Leone
Sierra Leone touches: Guinea, Liberia
Liberia touches: Sierra Leone, Guinea, Cote D'Ivoire
Cote D'Ivoire touches: Liberia, Guinea, Mali, Burkina Faso, Ghana
Mali touches: Senegal, Mauritania, Algeria, Niger, Burkina Faso, Cote D'Ivoire, Guinea
Burkina Faso touches: Mali, Niger, Benin, Togo, Ghana, Cote D'Ivoire
Ghana touches: Cote D'Ivoire, Burkina Faso, Togo
Togo touches: Ghana, Burkina Faso, Benin
Benin touches: Togo, Burkina Faso, Niger, Nigeria
Niger touches: Burkina Faso, Mali, Algeria, Libya, Chad, Nigeria, Benin
Nigeria touches: Benin, Niger, Chad, Cameroon
Chad touches: Niger, Libya, Sudan, Central African Republic, Cameroon, Nigeria
Sudan touches: Chad, Libya, Egypt, Eritrea, Ethiopia, Kenya, Uganda, Democratic Republic of the Congo, Central African Republic
Eritrea touches: Sudan, Djibouti, Ethiopia
Djibouti touches: Ethiopia, Eritrea, Somalia
Ethiopia touches: Sudan, Eritrea, Djibouti, Somalia, Kenya
Somalia touches: Kenya, Ethiopia, Djibouti
Kenya touches: Uganda, Sudan, Ethiopia, Somalia, Tanzania
Uganda touches: Democratic Republic of the Congo, Sudan, Kenya, Tanzania, Rwanda
Democratic Republic of the Congo touches: Cabinda, Congo, Central African Republic, Sudan, Uganda, Rwanda, Burundi, Zambia, Angola
Central African Republic touches: Cameroon, Chad, Sudan, Democratic Republic of the Congo, Congo
Cameroon touches: Nigeria, Chad, Central African Republic, Congo, Gabon, Equatorial Guinea
Equatorial Guinea touches: Cameroon, Gabon
Gabon touches: Equatorial Guinea, Cameroon, Congo
Congo touches: Gabon, Cameroon, Central African Republic, Democratic Republic of the Congo, Cabinda
Rwanda touches: Democratic Republic of the Congo, Uganda, Tanzania, Burundi
Burundi touches: Democratic Republic of the Congo, Rwanda, Tanzania
Tanzania touches: Burundi, Rwanda, Uganda, Kenya, Mozambique, Malawi, Zambia
Cabinda touches: Congo, Democratic Republic of the Congo
Angola touches: Democratic Republic of the Congo, Zambia, Namibia
Zambia touches: Angola, Democratic Republic of the Congo, Tanzania, Malawi, Mozambique, Zimbabwe, Botswana, Namibia
Malawi touches: Zambia, Tanzania, Mozambique
Mozambique touches: Zimbabwe, Zambia, Malawi, Tanzania, South Africa, Swaziland
Zimbabwe touches: Namibia, Zambia, Mozambique, South Africa, Botswana
Botswana touches: Namibia, Zambia, Zimbabwe, South Africa
Namibia touches: Angola, Zambia, Zimbabwe, Botswana, South Africa
South Africa touches: Namibia, Botswana, Zimbabwe, Mozambique, Swaziland, Lesotho
Swaziland touches: South Africa, Mozambique
Lesotho touches: South Africa
code-golf
kolmogorov-complexity
Аддисон Крамп
источник
источник
%r=map%$_,%r.Ответы:
Perl
150914961392138913861251124812461241 байтВключает +2 для
-naБеги со страной и рассчитывай на STDIN, например
perl -na countries0.pl <<< "The Gambia 4"Файл
countries.pl:Это работает как есть, но для получения заданной длины все экранированные байты должны быть заменены соответствующими литеральными. Например, вы можете сделать это, используя:
объяснение
Давайте сначала отобразим программу с некоторыми удаленными преобразованиями:
Основная идея состоит в том, чтобы иметь три основных структуры данных:
@countriesсодержащий все страны%touchesиндексов в@countriesмассиве, который$touches{$i}{$j}существует тогда и только тогда, когда он$countries[$i]касается$countries[$j]%reachableкоторый имеет ключ для индекса каждой страны, доступной на рассматриваемом уровне.Тогда алгоритм выглядит так:
@countriesи используйте его для инициализации%reachable$rв%reachableвзгляде вверх$touches{$r}и собрать все ключи вы найдете там%reachable. Поскольку это хеш, любые дубликаты будут удалены%reachableчтобы напечатать соответствующую страну@countries, но не печатайте исходную целевую странуНа этом простота заканчивается и начинается игра в гольф.
@countriesМассив никогда не будет существовать с именем, хотя он создан на короткое время в памяти%reachableХэш будет называться%r%touchesХэш не будет явно существует. Вместо этого я использую глобальное пространство имен perl. Например, страна 6 касается страны 3, а страна 12 будет представлена в хеше,%6который будет содержать(3 => undef, 12 => undef)@countries[keys %reachable]но я не хочу писатьkeysи вместо этого делать@countries[%reachable]. Но так как%reachableбудут содержатьundefзначения, которые станут индексом 0, я начну фактический список стран с индекса 1 и поместу пустую строку в индекс 0. Печать этой пустой строки будет невидимой. Я также позабочусь о том, чтобы целевая страна была заменена пустой строкой. И, наконец, у каждой страны по-прежнему будет новая строка в конце. Зная все, что в конечном итоге становится простоprint @countries[%reachable]. За исключением того, что страны на данный момент будут в$_, так что фактический кодprint+(/$|.+\n/mg)[%r]. Обратите внимание, что регулярное выражение гарантирует, что пустые строки не получат символ новой строки, а полные названия стран -.%reachableв принципе могут быть получены с помощьюmap keys %{$touches{$_}},keys %reachable. Но опять же,keysэто не нужно, если я позабочусь о том, чтобы правильно обрабатывать значения undef, которые я также получаю безkeys. И, как сказано выше, я использую основной глобус для хранения значений, поэтому фактический фрагмент кода таковmap%$_,%r. Я хочу добавить каждое из возвращаемых значений в качестве нового ключа,%rкоторый можно сделать как%r=map%$_,%r. Это, однако, требует, чтобы страны называли себя касающимися, чтобы слой происхождения оставался в наборе. Этот фрагмент кода должен повторяться столько раз, сколько пользователь запросил для слоев. Обратите внимание, что это фактическое ядро программы, все остальное - шум для поддержки этого.-aопция собрала количество слоев в качестве последнего элемента,@Fэто можно выполнить с помощьюeval '%r=map%$_,%r;' x pop @F. В общем, это не самый короткий способ зацикливания в perl, но у него есть преимущество в том, что он не изменяется$_во время зацикливания, и этот факт я буду использовать позже. Размещение количества слоев в отдельной строке в STDIN позволило бы мне заменить ихx pop@F,x<>сохранив 4 байта, но я хочу остаться как можно ближе к спецификации.pop @Fудаления слоев@Fсодержит название начальной страны. Обратите внимание, что страны с пробелами в названии будут разделены на составные части. Мы можем найти цель в строке больших стран$_и немедленно заменить целевую страну пустой строкой (чтобы она не печаталась), выполнивs/^@F$//m. Обратите внимание, что страны с пробелами в их имени восстанавливаются путем@Fинтерполяции. Также обратите внимание, что это должно быть тщательно закреплено, потому что некоторые страны являются подстрока других, например,GuineaиGuinea-BissauилиNigerиNigeria$'=~y/\n//. Если целевая страна не найдена,$`будет содержаться значение из предыдущего регулярного выражения, которое может быть очень неправильным. Вместо этого мы хотим 0 (по какому индексу у нас есть пустая строка). Это может быть достигнуто путем объединения его с предыдущим совпадением вs/^@F$//m*$`=~y/\n//.%reachable. Eval тогда становитсяeval '%r=map%$_,%r,%r,s/^@F$//m*$`=~y/\n//;' x pop@F;. Обратите внимание, что подстановка уничтожает целевую страну,$_поэтому добавляется только в первый раз (если бы это было не так, это не повлияло бы, поскольку индекс целевой страны уже в%reachableлюбом случае)%rмы можем объединить это сprint+(/$|.+\n/mg)[%r]получением реального кодаprint+(/$|.+\n/mg)[eval'%r=map%$_,%r,s/^@F$//m*$`=~y/\n//;'x pop@F]Следующий вопрос - как закодировать список стран. Как объяснено выше, я хочу, чтобы это была огромная строка со странами, оканчивающимися новой строкой и начинающимися с одной новой строки. Для этого мне нужно 26 букв, пробел, перевод строки,
-(дляGuinea-Bissau) и'(дляCote D'Ivoire). Проблема не в том, что иногда буквы в верхнем регистре. Это легко решается заглавными буквами первой буквы после границы слова. Однако есть исключения:Republic of Ireland,Bosnia and HerzegovinaиDemocratic Republic of the Congo. У них есть слово, которое не начинается с заглавной буквы. Я могу справиться с этим, заменив пространство перед этим подчеркиванием,_которое мешает ему распознать границу слова, а затем заменить_его пробелом. Исключение, которое осталосьUSAкоторый в верхнем регистре, который не на границе слова. Для этого я ввожу границы слов, записывая это как,u`s`aа затем удаляю обратные кавычки. Вместе это дает:С помощью этого кода можно закодировать строку страны весь используя только
a-z,,',-,\n,_и`, что 32 различных символов. Таким образом, каждый символ может быть закодирован с 5 битами. Фактически, если у меня есть огромная цепочка битов11110100111..., я могу преобразовать ее в нужные символы, используя:Если у меня есть строка байтов,
$_то огромная цепочка битов, которая мне нужна, может быть создана с помощью$_ = unpack"B*". Таким образом, в основном все это небольшой преобразователь из 256 в 32, и каждая буква страны кодируется с использованием 5 битов в строке входных двоичных стран. Это относительно компактно и ничего не дает для разработки специальных кодов для повторяющихся строк в списке стран с одним исключением:Republicпоявляется в 5 названиях стран. Поскольку оно всегда отображается как полное слово, а название страны не начинается сX(единственной такой буквы), я могу использовать его в качестве escape-кода после того, как первые буквы названий стран указаны в верхнем регистре.Теперь мне нужен способ кодирования отношения «прикосновения». Первое, что нужно отметить, это то, что он симметричен, поэтому, если страна
$nкасается страны$t, то страна$tтакже касается страны$n. Поэтому мне нужно кодировать половину отношений только в том случае, если я заполняю%touchesхэш в обоих направлениях. В упрощенном коде вы видите, что делаетсяЗа исключением того, что фактический код использует
$.вместо,$nпотому что я хочу, чтобы счетчик начинался с 1 вместо 0 (страна 0 - фиктивная пустая строка). Идея состоит в том, чтобы написать последовательность страновых индексов,| A, B, C | D, E | ..которая говорит, что страна 1 касается стран с индексомA,BаCстрана 2 касается индексаDиEи т. д. Фактически я кодирую смещение от текущей страны (которое я позже буду использовать, чтобы сделать значения маленькими), и только положительные смещения (это гарантирует, что отношение "касаний" закодировано только в одном направлении, и метод, который я использую, может не обрабатывать отрицательные числа в любом случае). Некоторые страны имеют пустой список соседей, потому что их отношения касания уже были даны другими странами. Я могу изменить список стран (порядок которых не имеет значения) так, чтобы они были в конце списка. Затем я могу опустить эти страны из последовательности. Это ничего не дает, так как мне нужно столько смещений, сколько существует «сенсорных» отношений, но это позволяет избежать потери байтов, поскольку приходится кодировать фиктивное смещение. Как объяснялось выше, страна 0 - пустая пустая строка, поэтому мне нужно убедиться, что она пропущена. Я могу записать эту последовательность чисел как последовательность байтов, где значение байта соответствует смещению индекса. Однако мне все еще нужно знать, где начинается следующая страна в последовательности (позиции|s в приведенном выше примере). Я делаю это, устанавливая старший бит в 1 для первого индекса в списке касаний конкретной страны, поэтому для индексовAиDв приведенном выше примере.Есть одна досадная проблема: существует более 127 стран. Поэтому я не могу просто использовать символьный бит. Вместо этого я нашел расположение таких стран, что каждая страна никогда не будет дальше 15 позиций от всех стран, к которым она прикасается:
(в то время, когда я писал это объяснение, моя программа поиска фактически нашла заказ, в котором максимальное расстояние не превышает 12). Это означает, что я могу использовать в
0x10качестве флага, чтобы указать начало новой страны, и мне нужно только закодировать 32 различных значения. Это может быть сжато для расширения с тем же самым конвертером от 256 до 32, который был необходим для списка стран. Фактически, я могу поместить сенсорную строку перед строкой страны с0x00промежуточным положением (перед кодированием), если я напишу сенсорный декодер, чтобы он на этом остановился\x00. Декодер страны написан так, чтобы этот0x00оставленный в начале текст стал исходной новой строкой, которая мне нужна, поэтому страна с индексом 0 является пустой строкой.В старой версии кода использовался тот факт, что в графе стран имеется только 4 связанных компонента, чтобы уменьшить индексы стран до уровня ниже 128, но это было намного сложнее и немного длиннее в коде и кодированной строке.
Код для преобразования последовательности байтов в
%touchesхэш становится:Обратите внимание, что все одноэлементные страны просто вообще не кодируются. Используемые в качестве входных данных, они никогда не будут совпадать, поэтому
%reachableбудут содержать ссылки на исходную пустую страну, и ничего не будет напечатано.С этим вся программа объясняется. После этого нужно было написать метапрограмму, которая генерирует огромную закодированную строку, тщательно выбирая порядок стран таким образом, чтобы
'(что приведет к аннулированию последней строки в одинарных кавычках)источник
JavaScript (ES6),
28622324Возвращает объект Set, содержащий правильные страны. Обратите внимание, что это содержит массу непечатных.
Тестовый фрагмент (требуется ES6-совместимый браузер)
Показать фрагмент кода
Как это работает
Прежде всего я удалил из списка все страны, где нет соседей. Затем я сократил список до этого формата:
Это сокращает список до 2130 байтов. Пустая запись была тщательно вставлена, где страна, представленная запятой, должна была бы избежать неудачи регулярного выражения. Теперь для интересной части:
источник
JavaScript (ES6) 2622
3815Функция, возвращающая набор. Рекурсивное сканирование с использованием набора, чтобы избежать повторений.
(2 новых строки добавлены для удобства чтения - это должна быть одна строка)
Заимствование идеи @ETHproductions не хранить страны без соседей . (заимствуя его орфографию, я всегда неправильно пишу это слово)
объяснение
Тест
источник
1/xвместо+x?» Тогда я понял, что это умный способ обойти дело0. +1Python 2,
6967696569506906 байтЯ действительно, очень надеюсь, что я все понял правильно. Пример:
Входные данные:
Выход:
Я надеюсь, что пустая строка разрешена.Нет больше пустой строки! Ура!Объяснение:
Длинная строка вверху - это данные о названии каждой страны и соседних странах. Каждый элемент в списке - это другой список, первым элементом которого является название страны, а другим элементом является индекс каждой страны, которая его окружает. США является первым элементом и содержит индексы
1, 2. Элементом 1 в списке является Канада, а элементом 2 в списке является Мексика. Этот список был создан с помощью этой программы:...... [большой список выше]
Вывод содержал запятые, которые можно удалить с помощью очень простого регулярного выражения, которое можно найти здесь . Вся программа доступна здесь . Выход составляет 4736 байт, что составляет около 88% программы.
Вот остальная часть программы с правильными именами переменных, комментариями и пробелами (предыдущая версия):
источник
{}, к сожалению.{x for d in Q[A][1:] if d not in C}иC|=nвместоfor A in C:цикла.Mathematica, программа 128B + данные 2856B = 2984 байта
Где
FOOстрока длиной 2856 байт (здесь не вставлена, потому что она содержит непечатаемые и только для MMA символы). Строка представляет собой сжатый BZIP2 список списков, где каждый внутренний список имеет форму{Country, Neighbor, Neighbor, ...}. Список уже оптимизирован для удаления лишних ребер.Наличие этого в графическом формате Mathematica позволяет нам делать простые приятные вещи, как это:
Чтобы получить такие вещи, как:
источник
PHP,
5169271626982321 байтОбновить
Это моя вторая, очень укороченная версия. Оригинальный пост смотри ниже.
Это оказалось довольно подробным редактированием ...
Удаление стран без соседей.
Моим первоначальным определением массива было колоссальные 4901 байт - удаление всех стран без соседей (как предложено @ETHproductions) уменьшило это на 725 байт до 4176 байт. Конечно, это требует добавления некоторого дополнительного логического кода, чтобы удовлетворить запасной вариант, но это должно быть незначительным по сравнению с этим огромным выигрышем.
Использование символов вместо цифр
Моим следующим шагом было уменьшение количества байтов, необходимых для декодирования соседних ссылок. Моя первая идея состояла в том, чтобы отказаться от десятичной системы и использовать более высокое основание для представления чисел (например, основание 36, которое будет использовать 0-9 плюс az), но дополнительная логика, необходимая для их декодирования, казалась большой. Поэтому я пошел на что-то другое: персонажи.
Каждый символ ASCII имеет длину только один байт и отображается на четко определенное число в диапазоне 0..255, что именно то, что нужно. Я пропустил первые 39 символов ASCII, так как они непечатные / включают
'и"которые нужно будет экранировать. Результирующее определение массива имело длину всего 2878 байт, экономя 1298 байт или 31% по сравнению с предыдущим. Конечно, это тоже нуждается в дополнительных логиках, но , к счастью ,chrиordдовольно короткие имена функций :-)Сжатие названий стран
Эти названия стран все еще занимали много места, поэтому я решил посмотреть, как можно их сжать. В пяти странах есть термин «республика», поэтому я смог сэкономить 16 байт, объявив
$r='Republic'один раз, а затем записав"$r of Ireland"и т. Д. То же самое касается «Гвинеи», которая появляется 4 раза.Также встречается довольно много буквенных комбинаций, которые встречаются относительно часто, но, поскольку при наборе текста
$xпо-прежнему используются два символа, их замена имеет смысл только для комбинаций с 3+ буквами и, если действительно есть LOT, который можно заменить. Например, замена всех 10-niaсTanzaniaи т. Д. Принесла только 1 байт. То же самое с-istan(4x, -1), больше удачи с-land(7x, -4).PHP "особенности"
К счастью для гольфиста, PHP не слишком возражает, когда вы нарушаете его правила синтаксиса. Здесь мы можем использовать это для удаления некоторых кавычек, превращая
'Lesotho'=>'E'(14 байтов) вLesotho=>E(10 байтов). Удивительно (или: шокирующе?) Это даже работает для любой строки, состоящей из AZ, 0-9 или второй половины таблицы ASCII и не начинающейся с цифры , что делает что-то похожее на ЭТО:India=>nh¢•Q“.Тем не менее, очень жаль, что разработчики таблицы ASCII ставят знаки препинания между буквенными блоками, а это означает, что нет непрерывного блока бессмысленных символов PHP для размещения всех 150 стран в списке. Это приводит к тому, что многие строки сохраняют свои кавычки. Время от времени я перемещал числа назад, чтобы строка не начиналась с цифры.
Окончательное определение массива
Все это приводит к уменьшению определения массива до 2534 байтов, что составляет почти половину исходного значения. Конечно, теперь можно было бы пойти и оптимизировать порядок стран, чтобы как можно большее количество заявок могло потерять свои котировки и т. Д., Но я не хотел вкладывать ЭТО много усилий в это. ;-)
Код
Итак, вторая версия с добавлением дополнительной логики:
Golfed
Редактирование обновления
Сохранено еще 18 байт:
$r='Republic'и т. д. (-10)forнаwhileпетлю (-6)asключевых слов (-2)Я обновил приведенный выше код с изменениями.
Другое редактирование
Сбрил еще 377 байт, создавая индексированный массив из интегрировалась строки первой ( что делает все
=>и"устаревшим, -417 байт накладных расходов) и поворота , что в разыскиваемых ассоциативный массив впоследствии (+40 байт кода). Обновил приведенный выше код еще раз.Начальный пост
Это довольно быстрая первая версия, я еще не делал ЛЮБОГО сжатия списков, кроме очевидных чисел для имен - я мог бы поработать над этим завтра и отредактировать свой пост тогда.
Мой список представляет собой простой ассоциативный массив с записью для каждой страны. Ключ массива - это имя страны, а значение - массив ее соседей, на которые ссылается их индекс в этом массиве. PHP не позволит вам получить доступ к ассоциативным массивам по индексу, так что мне нужна обходной путь , используя
array_keysиarray_valuesфункции.Фактический код прокомментировал:
Как и всегда, любые замечания очень ценятся.
источник
Dyalog APL , 82-байтовая программа + 1924-байтовые данные = 2006-байтовые
Я не делал ничего особенного, чтобы упаковать данные, кроме использования встроенных (de) serialize (
220⌶) и (un) zip ( Dyalog APL )219⌶) .Где эллипсы заменяют строку zlib с этими байтовыми значениями:
Обратите внимание, что как кодированная строка, так и остальная часть программы помещаются в 256-символьную кодовую страницу APL, то есть по одному символу на байт.
Вот как все это выглядит, если сложить вместе (
␀вместо U + 0000):источник