Você já se perguntou que países cercam outro? Eu também, às vezes, e, bem, aqui está o desafio.
Forneci uma lista de países e países em que eles tocam que você deve reconhecer na parte inferior desta postagem em um bloco de código. Você precisa criar um programa completo que produza (da maneira mais conveniente possível no seu idioma) a lista de camadas de países de países adjacentes para um país de entrada. Então, por exemplo:
>>> "United Kingdom" 1
Republic of IrelandPorque "United Kingdom"é o nome do país e 1é o número de camadas que você deseja criar. De fato, qualquer número de camadas (exceto 0) retornará Republic of Ireland, porque há um mar no caminho de chegar a outros países.
Mapa de referência:
Exemplos (qualquer coisa entre parênteses são comentários) (obviamente, a ordem de saída não importa):
>>> 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)Como o mundo é grande, você deve compensar diminuindo seu código. Afinal, isso é código-golfe .
Touching List (em nenhuma ordem específica, espero que em um formato analisável) (se houver erros aqui, por favor , avise-me . Eu já o examinei muitas vezes, mas provavelmente cometi alguns erros):
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
Addison Crump
fonte
fonte
%r=map%$_,%r.Respostas:
Perl,
150914961392138913861251124812461241 bytesInclui +2 para
-naCorra com o país e conte com o STDIN, por exemplo
perl -na countries0.pl <<< "The Gambia 4"Arquivo
countries.pl:Isso funciona como está, mas, para obter o comprimento especificado, todos os bytes de escape precisam ser substituídos pelos literais correspondentes. Você pode, por exemplo, fazer isso usando:
Explicação
Vamos primeiro exibir o programa com algumas transformações removidas:
A idéia básica é ter três estruturas de dados principais:
@countriescontendo todos os países%touchesde dois níveis de índices na@countriesmatriz que$touches{$i}{$j}existe se e somente se$countries[$i]toca$countries[$j]%reachableque possui uma chave para o índice de todos os países alcançáveis na camada que está sendo considerada no momento.Então o algoritmo é:
@countriese use-o para inicializar%reachable$r,%reachableprocure$touches{$r}e colete todas as chaves encontradas lá%reachable. Como esse é um hash, as duplicatas serão descartadas%reachablepara imprimir o país correspondente@countries, mas não imprima o país de destino originalÉ aqui que a simplicidade termina e o golfe começa.
@countriesmatriz nunca existirá com um nome, embora seja criada brevemente na memória%reachablehash será nomeado%r%toucheshash não existirá explicitamente. Em vez disso, uso o namespace global perl. Por exemplo, aquele país 6 toca o país 3 e o país 12 será representado no hash%6que conterá(3 => undef, 12 => undef)@countries[keys %reachable]mas não quero escrever okeyse, em vez disso, escrever@countries[%reachable]. Porém, como%reachableconterãoundefvalores que se tornam o índice 0, iniciarei a lista de países real no índice 1 e colocarei a cadeia vazia no índice 0. A impressão dessa cadeia vazia será invisível. Também assegurarei que o país de destino seja substituído por uma string vazia. E, finalmente, cada país ainda terá uma nova linha no final. Saber tudo o que o resultado final se torna simplesmenteprint @countries[%reachable]. Exceto que os países neste momento estarão dentro$_, então o código atual éprint+(/$|.+\n/mg)[%r]. Observe como a regex garante que as linhas vazias não recebam uma nova linha, mas os nomes completos dos países.%reachablepodem, em princípio, ser buscados usandomap keys %{$touches{$_}},keys %reachable. Mas, novamente, issokeysnão é necessário se eu tiver o cuidado de lidar adequadamente com os valores undef que também recebo sem okeys. E, como dito antes, eu uso o glob principal para armazenar os valores, então o fragmento de código real émap%$_,%r. Eu quero adicionar cada um dos valores retornados como uma nova chave à%rqual pode ser feito como%r=map%$_,%r. No entanto, isso precisa que os países se referam a si mesmos como tocantes, para que a camada de origem permaneça no conjunto. Esse fragmento de código deve ser repetido quantas vezes o usuário solicitou camadas. Observe que esse é o núcleo real do programa; tudo o resto é barulho para apoiar isso.-aopção coletou, o número de camadas como o último elemento@Fpode ser realizado usandoeval '%r=map%$_,%r;' x pop @F. Isso geralmente não é o caminho mais curto para executar o loop em perl, mas tem a vantagem de não mudar$_durante o loop, um fato que usarei mais tarde. Colocar o número de camadas em sua própria linha em STDIN me deixaria substituir ox pop@Fporx<>salvar 4 bytes, mas eu quero permanecer tão perto da especificação quanto possível.pop @Fremoção, as camadas@Fcontêm o nome do país inicial. Observe que os países com espaços em seus nomes serão divididos em suas partes componentes. Podemos encontrar o destino na cadeia de grandes países$_e substituir imediatamente o país de destino pela cadeia de caracteres emty (para que não seja impressa)s/^@F$//m. Observe que países com espaços em seu nome são reconstruídos pela@Finterpolação. Note também que esta deve ser cuidadosamente ancorado porque alguns países são substrings dos outros, por exemplo,GuineaeGuinea-BissauouNigereNigeria$'=~y/\n//. Se o país de destino não for encontrado$`, conterá um valor de uma regex anterior que pode estar muito errado. Em vez disso, queremos 0 (em que índice temos uma string vazia). Isso pode ser conseguido combinando-o com a correspondência anterior ems/^@F$//m*$`=~y/\n//.%reachable. A avaliação então se tornaeval '%r=map%$_,%r,%r,s/^@F$//m*$`=~y/\n//;' x pop@F;. Observe que a substituição destrói o país de destino$_apenas para que seja adicionada apenas na primeira vez (não seria importante se não fosse assim, pois o índice do país de destino já está de%reachablequalquer maneira)%r, podemos combiná-lo comprint+(/$|.+\n/mg)[%r]para chegar ao código realprint+(/$|.+\n/mg)[eval'%r=map%$_,%r,s/^@F$//m*$`=~y/\n//;'x pop@F]A próxima pergunta é como codificar o país. Como explicado acima, quero que seja uma sequência enorme de países terminados por nova linha e começando com uma única nova linha. Para isso, preciso de 26 letras, espaço, nova linha,
-(forGuinea-Bissau) e'(forCote D'Ivoire). É claro que o problema é que às vezes as letras estão em maiúsculas. Isso é facilmente resolvido com a primeira letra após um limite de palavra. No entanto, existem exceções:Republic of Ireland,Bosnia and HerzegovinaeDemocratic Republic of the Congo. Estes têm uma palavra que não começa com maiúsculas. Eu posso lidar com isso substituindo o espaço anterior por um sublinhado_que impede que seja reconhecido como um limite de palavra e, posteriormente, substitua o_por um espaço. A exceção que resta éUSAque possui letras maiúsculas que não estão no limite de uma palavra. Para isso, introduzo os limites das palavras escrevendo issou`s`ae depois removo as aspas. Juntos, isso dá:Com este código que eu pode codificar toda a cadeia de países utilizando apenas
a-z,,',-,\n,_e`, o que é de 32 caracteres diferentes. Portanto, cada caractere pode ser codificado com 5 bits. De fato, se eu tiver uma cadeia de bits enorme11110100111..., posso convertê-la nos caracteres necessários usando:Se eu tiver uma cadeia de bytes,
$_então a enorme cadeia de bits necessária poderá ser criada usando$_ = unpack"B*". Então, basicamente, tudo isso é um pequeno conversor de base 256 para base 32 e cada letra de país é codificada usando 5 bits na cadeia de países binários de entrada. Isso é relativamente compacto e não ganha nada para desenvolver códigos especiais para seqüências repetidas na lista de países, com uma exceção:Republicaparece em 5 nomes de países. Como sempre aparece como uma palavra completa e nenhum nome de país começa comX(a única letra desse tipo), posso usá-lo como código de escape depois que as primeiras letras dos nomes de países estiverem em maiúsculas.Agora eu preciso de uma maneira de codificar a relação "toques". A primeira coisa a notar é que é simétrica; portanto, se o país
$ntoca no país$t, o país$ttambém toca no país$n. Então, só preciso codificar metade dos relacionamentos se preencher o%toucheshash nos dois sentidos. No código simplificado, você vê que isso está sendo feito porExceto que o código real usa em
$.vez de$nporque eu quero que o contador inicie em 1 em vez de 0 (o país 0 é a sequência vazia dummy). A idéia é escrever uma seqüência de índices de países| A, B, C | D, E | ..que diz que o país 1 toques países com índiceA,BeC, país 2 toques índiceDeEetc. Na verdade, codifico o deslocamento do país atual (que usarei mais tarde para reduzir os valores) e apenas compensações positivas (isso garante que o relacionamento "toques" seja codificado apenas em uma direção, e o método que utilizo possa de qualquer forma, lida com números negativos). Alguns países têm uma lista vazia de vizinhos porque seu relacionamento de toque já foi dado por outros países. Posso reorganizar a lista de países (cuja ordem é irrelevante) de forma que eles cheguem ao final da lista. Posso então omitir esses países da sequência. Isso não ganha nada, pois eu preciso de tantos deslocamentos quanto as relações de "toque", mas evita a perda de bytes ao codificar um deslocamento fictício. Como explicado acima, o país 0 é uma string vazia e, portanto, preciso garantir que isso seja ignorado. Eu posso escrever essa sequência de números como uma sequência de bytes em que o valor do byte corresponde ao deslocamento do índice. No entanto, ainda preciso saber onde começa o próximo país em uma sequência (as posições do|s no exemplo acima). Para fazer isso, defina um bit alto como 1 para o primeiro índice na lista de toques de um país em particular, para índicesAeDno exemplo acima.Há um problema irritante: existem mais de 127 países. Portanto, não posso simplesmente usar o bit do sinal de caractere. Em vez disso, encontrei um arranjo dos países de tal maneira que cada país nunca fica mais longe que 15 posições de distância de todos os países em que toca:
(no momento em que escrevi essa explicação, meu programa de pesquisa encontrou um pedido em que a distância máxima é de no máximo 12). Isso significa que posso usar
0x10como bandeira para indicar o início de um novo país e preciso codificar apenas 32 valores diferentes. Isso pode ser compactado para expansão com o mesmo conversor de base 256 para base 32, conforme necessário para a lista de países. Na verdade, posso colocar a sequência de toque antes da sequência de país com um0x00entre (antes da codificação) se eu escrever o decodificador de toque para que ele pare com isso\x00. O decodificador de país é gravado de forma que essa0x00esquerda no início se torne a nova linha inicial necessária para que o país no índice 0 seja a sequência vazia.Uma versão mais antiga do código usava o fato de haver apenas quatro componentes conectados no gráfico do país para reduzir os índices do país para abaixo de 128, mas isso era muito complicado e um pouco mais longo no código e na cadeia codificada.
O código para converter uma sequência de bytes em
%toucheshash se torna:Observe que todos os países singleton simplesmente não são codificados. Utilizados como entrada, eles nunca coincidem, portanto
%reachable, conterão apenas referências ao país vazio inicial e nada será impresso.Com isso, todo o programa é explicado. Tudo o que foi necessário depois disso foi escrever um metaprograma que gere a enorme cadeia codificada, escolhendo cuidadosamente a ordem dos países, para que
'(o que invalidaria a sequência final entre aspas simples)fonte
JavaScript (ES6),
28622324Retorna um objeto Set contendo os países apropriados. Observe que isso contém uma tonelada de não imprimíveis.
Snippet de teste (é necessário um navegador compatível com ES6)
Mostrar snippet de código
Como funciona
Antes de mais nada, removi todos os países sem vizinhos da lista. Então reduzi a lista para este formato:
Isso condensa a lista para 2130 bytes. Uma entrada em branco foi cuidadosamente inserida onde o país representado por uma vírgula seria para evitar falhas na expressão regular. Agora a parte interessante:
fonte
JavaScript (ES6) 2622
3815Uma função retornando um conjunto. Varredura recursiva usando um conjunto para evitar repetições.
(2 novas linhas adicionadas para facilitar a leitura - deve ser uma única linha)
Tomando emprestada a ideia de @ETHproductions de não armazenar países sem vizinhos . (emprestando sua ortografia também, eu sempre escrevo errado essa palavra)
Explicação
Teste
fonte
1/xinvés de+x?" Então percebi que é uma maneira inteligente de contornar o caso0. +1Python 2,
6967696569506906 bytesEu realmente espero que tenha acertado tudo. Exemplo:
Entrada:
Saída:
Espero que a linha vazia seja permitida.Não há mais linha vazia! Yay!Explicação:
A linha longa na parte superior contém dados sobre o nome de cada país e os países vizinhos. Cada elemento da lista é outra lista, cujo primeiro elemento é o nome do país e o outro elemento é o índice de cada país que o rodeia. EUA é o primeiro elemento e contém os índices
1, 2. O elemento 1 na lista é o Canadá e o elemento 2 na lista é o México. Esta lista foi gerada usando este programa:...... [a grande lista acima]
A saída continha vírgulas que poderiam ser removidas por um Regex muito simples, que pode ser encontrado aqui . Todo o programa está disponível aqui . A saída é de 4.736 bytes, cerca de 88% do programa.
Aqui está o restante do programa com nomes de variáveis, comentários e espaços em branco adequados (versão anterior):
fonte
{}faz um ditado , infelizmente.{x for d in Q[A][1:] if d not in C}e emC|=nvez dofor A in C:loop.Mathematica, programa 128B + dados 2856B = 2984 bytes
Onde
FOOestá uma sequência de 2856 bytes (não colada aqui porque contém caracteres não imprimíveis e somente MMA). A sequência é uma lista de listas compactadas em BZIP2, em que cada lista interna possui o formulário{Country, Neighbor, Neighbor, ...}. A lista já está otimizada para remover arestas redundantes.Tê-lo no formato de gráfico do Mathematica nos permite fazer coisas legais fáceis como esta:
Para obter coisas como:
fonte
PHP,
5169271626982321 bytesAtualizar
Esta é a minha segunda versão extremamente reduzida. Post original veja abaixo.
Isso acabou se tornando uma edição bastante detalhada ...
Remoção de países sem vizinhos.
Minha definição original de matriz era de 4901 bytes - a remoção de todos os países sem vizinhos (como sugerido pela @ETHproductions) reduziu isso em 725 bytes para 4176 bytes. É claro que isso exige que algum código lógico extra seja adicionado para atender ao fallback, mas isso deve ser negligenciável em comparação com esse enorme ganho.
Usando caracteres em vez de números
Meu próximo passo foi reduzir a quantidade de bytes necessários para decodificar as referências vizinhas. Minha primeira idéia foi abandonar o sistema decimal e usar uma base mais alta para representar os números (por exemplo, a base 36, que usaria 0-9 mais az), mas a lógica extra necessária para decodificá-los parecia muito. Então, eu fui para outra coisa: personagens.
Cada caractere ASCII tem apenas um byte e é mapeado para um número bem definido do intervalo de 0 a 255, que é exatamente o que seria necessário. Eu pulei os primeiros 39 caracteres ASCII, pois eles não são imprimíveis / incluem
'e"precisam ser escapados. A definição de matriz resultante tinha apenas 2878 bytes, economizando 1298 bytes ou 31% quando comparado com o anterior. Obviamente, isso também precisa de lógica extra, mas felizmentechreordsão nomes de função bastante curtos :-)Comprimindo nomes de países
Mas esses nomes de países ainda ocupavam muito espaço, então decidi ver como poderia compactá-los. Cinco países têm o termo "República", então pude salvar 16 bytes declarando
$r='Republic'uma vez e depois escrevendo"$r of Ireland"etc. O mesmo vale para "Guiné", que aparece 4 vezes.Também existem algumas combinações de letras que ocorrem com relativa frequência, mas como a digitação
$xainda tem dois caracteres, substituí-las só faz sentido para combinações com mais de 3 letras e se realmente existe MUITO que pode ser substituído. Por exemplo, substituir todos os 10-nias emTanzaniaetc. ganhou apenas 1 byte. Mesmo com-istan(4x, -1), mais sorte com-land(7x, -4)."Recursos" do PHP
Felizmente para o jogador de código, o PHP não se importa muito quando você viola suas regras de sintaxe. Aqui, podemos usar isso para remover algumas aspas, transformando
'Lesotho'=>'E'(14 bytes) emLesotho=>E(10 bytes). Surpreendentemente (ou: chocantemente?) Isso funciona mesmo para qualquer string que consiste em AZ, 0-9 ou na segunda metade da tabela ASCII e não começa com um número , tornando possível algo como ISSO:India=>nh¢•Q“.No entanto, é uma pena que os designers da tabela ASCII coloquem pontuação entre os blocos de letras, o que significa que não há um bloco contínuo de caracteres sem significado PHP para acomodar todos os 150 países da lista. Isso resulta em muitas seqüências de caracteres ainda mantendo suas aspas. Ocasionalmente, movia os números para trás, para que a sequência não começasse com um dígito.
Definição final da matriz
Tudo isso reduz a definição da matriz para 2534 bytes, quase metade do valor inicial. Claro, agora é possível otimizar a ordem dos países para que o maior número possível de entradas possa perder suas cotações, etc., mas eu não queria colocar tanto esforço nisso. ;-)
Código
Então aqui está, a segunda versão, com um pouco de lógica adicional adicionada:
Golfe
Edição da atualização
Salvou outros 18 bytes por:
$r='Republic'etc. (-10)forporwhileloop (-6)aspalavras-chave (-2)Eu atualizei o código acima com as alterações.
Outra edição
Raspado mais 377 bytes, criando uma matriz indexada a partir de uma cadeia Implosão primeiro (tornando tudo
=>e"obsoleto, -417 bytes de sobrecarga) e girando em que a matriz associativa desejado depois (+40 bytes de código). Atualizado o código acima novamente.Postagem inicial
Esta é uma primeira versão bastante rápida, eu não fiz QUALQUER compactação de lista além dos números óbvios para nomes ainda - eu poderia trabalhar nisso amanhã e editar meu post.
Minha lista é uma matriz associativa simples, com uma entrada para cada país. A chave da matriz é o nome do país e o valor de uma matriz de seus vizinhos, referenciada por seu índice nessa matriz. O PHP não permitirá que você acesse matrizes associativas por índice, então eu precisava de uma solução alternativa usando
array_keysearray_valuesfunções.O código real comentou:
Como antes e sempre, quaisquer comentários são muito apreciados.
fonte
Dyalog APL , programa de 82 bytes + dados de 1924 bytes = 2006 bytes
Eu não fiz nada de especial para empacotar os dados além de usar (des) serializar (
220⌶) e ( des ) zip (219⌶) interno do Dyalog APL .Onde as elipses representam uma cadeia de caracteres zlib'ed com estes valores de bytes:
Observe que a seqüência de caracteres codificada e o restante do programa se encaixam na página de códigos de 256 caracteres da APL, ou seja, um símbolo por byte.
Aqui está o que tudo se parece quando reunidos (
␀substituindo U + 0000):fonte