Pernah bertanya-tanya negara apa yang mengelilingi negara lain? Saya juga melakukannya, kadang-kadang, dan, inilah tantangannya.
Saya telah memberikan daftar negara dan negara yang mereka sentuh yang harus Anda kenali di bagian bawah pos ini dalam blok kode. Anda perlu membuat program lengkap yang menampilkan (dengan cara yang paling nyaman dalam bahasa Anda) daftar lapisan negara-negara yang berdekatan ke negara input. Jadi, misalnya:
>>> "United Kingdom" 1
Republic of IrelandKarena itu "United Kingdom"adalah nama negara dan 1jumlah lapisan yang ingin Anda buat. Bahkan, sejumlah lapisan (kecuali 0) akan kembali Republic of Ireland, karena ada lautan dalam perjalanan ke negara lain.
Peta Referensi:
Contoh (apapun dalam tanda kurung adalah komentar) (jelas, urutan output tidak masalah):
>>> 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)Karena dunia ini besar, Anda harus mengimbanginya dengan membuat kode Anda kecil. Lagipula ini golf kode .
Daftar Menyentuh (tanpa urutan tertentu, mudah-mudahan dalam format yang dapat diuraikan) (jika ada kesalahan di sini, tolong beri tahu saya . Saya sudah berkali-kali mengalaminya, tapi saya pasti telah membuat beberapa kesalahan):
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
sumber
sumber
%r=map%$_,%r.Jawaban:
Perl,
150914961392138913861251124812461241 bytesTermasuk +2 untuk
-naJalankan dengan negara dan mengandalkan STDIN, mis
perl -na countries0.pl <<< "The Gambia 4"File
countries.pl:Ini berfungsi sebagaimana mestinya, tetapi untuk mendapatkan panjang yang diberikan semua byte yang lolos harus digantikan oleh byte literal yang sesuai. Anda dapat melakukan hal itu menggunakan:
Penjelasan
Pertama-tama mari kita tampilkan program dengan beberapa transformasi dihapus:
Ide dasarnya adalah memiliki tiga struktur data utama:
@countriesberisi semua negara%touchesindeks dalam@countriesarray sedemikian rupa sehingga$touches{$i}{$j}ada jika dan hanya jika$countries[$i]menyentuh$countries[$j]%reachableyang memiliki kunci untuk indeks setiap negara yang dapat dijangkau pada lapisan yang saat ini sedang dipertimbangkan.Maka algoritma tersebut adalah:
@countriesdan gunakan untuk menginisialisasi%reachable$rdalam%reachablemencari$touches{$r}dan mengumpulkan semua kunci yang Anda temukan di sana%reachable. Karena ini adalah hash, duplikat apa pun akan dijatuhkan%reachableuntuk mencetak negara terkait@countries, tetapi jangan mencetak negara target asliDi sinilah kesederhanaan berakhir dan golf dimulai.
@countriesArray tidak akan pernah ada dengan nama, meskipun dibuat secara singkat dalam memori%reachablehash akan diberi nama%r%toucheshash tidak akan secara eksplisit ada. Sebagai gantinya saya menggunakan perl namespace global. Misalnya negara 6 menyentuh negara 3 dan negara 12 akan diwakili dalam hash%6yang akan berisi(3 => undef, 12 => undef)@countries[keys %reachable]tetapi saya tidak ingin menuliskeysdan malah melakukannya@countries[%reachable]. Tetapi karena%reachableakan berisiundefnilai-nilai yang menjadi indeks 0, saya akan memulai daftar negara yang sebenarnya pada indeks 1 dan meletakkan string kosong pada indeks 0. Mencetak string kosong itu tidak akan terlihat. Saya juga akan memastikan negara target diganti dengan string kosong. Dan akhirnya masing-masing negara masih akan memiliki baris baru di akhir. Mengetahui semua hasil akhirnya menjadi sederhanaprint @countries[%reachable]. Kecuali bahwa negara-negara pada saat ini akan masuk$_, jadi kode sebenarnya adalahprint+(/$|.+\n/mg)[%r]. Perhatikan bagaimana regex memastikan garis kosong tidak mendapatkan baris baru tetapi nama negara lengkap melakukannya.%reachablepada prinsipnya dapat diambil dengan menggunakanmap keys %{$touches{$_}},keys %reachable. Tetapi sekali lagikeystidak diperlukan jika saya berhati-hati menangani nilai undef yang saya dapatkan tanpakeys. Dan seperti yang saya katakan sebelumnya saya menggunakan glob utama untuk menyimpan nilai-nilai, jadi fragmen kode yang sebenarnya adalahmap%$_,%r. Saya ingin menambahkan masing-masing nilai yang dikembalikan sebagai kunci baru%ryang dapat dilakukan sebagai%r=map%$_,%r. Namun ini perlu negara-negara untuk menyebut diri mereka sebagai menyentuh sehingga lapisan asal tetap di set. Fragmen kode ini harus diulang sebanyak yang diminta pengguna untuk layer. Perhatikan bahwa ini adalah inti sebenarnya dari program, yang lainnya berisik untuk mendukung ini.-aopsi mengumpulkan jumlah layer sebagai elemen terakhir dalam@Fini dapat dicapai menggunakaneval '%r=map%$_,%r;' x pop @F. Ini pada umumnya bukan cara terpendek untuk mengulang dalam perl tetapi memiliki keuntungan bahwa itu tidak berubah$_selama loop, sebuah fakta yang akan saya gunakan nanti. Menempatkan jumlah lapisan pada barisnya sendiri di STDIN akan membiarkan saya menggantix pop@Fdenganx<>menghemat 4 byte, tapi saya ingin tetap sedekat mungkin dengan spesifikasi.pop @Fdihapus, layer-layer tersebut@Fberisi nama negara awal. Perhatikan bahwa negara-negara dengan spasi atas namanya akan dibagi menjadi beberapa bagian komponennya. Kita dapat menemukan target dalam string negara-negara besar$_dan segera mengganti negara target dengan string emty (sehingga tidak akan dicetak) dengan melakukans/^@F$//m. Perhatikan bahwa negara-negara dengan ruang atas namanya direkonstruksi oleh@Finterpolasi. Juga perhatikan bahwa ini harus hati-hati berlabuh karena beberapa negara substring dari orang lain, misalnyaGuineadanGuinea-BissauatauNigerdanNigeria$'=~y/\n//. Jika negara target tidak ditemukan$`akan mengandung nilai dari regex sebelumnya yang bisa sangat salah. Alih-alih kita menginginkan 0 (di mana indeks kita memiliki string kosong). Ini bisa dicapai dengan menggabungkannya dengan pertandingan sebelumnyas/^@F$//m*$`=~y/\n//.%reachable. Eval itu kemudian menjadieval '%r=map%$_,%r,%r,s/^@F$//m*$`=~y/\n//;' x pop@F;. Perhatikan bahwa substitusi menghancurkan negara target$_sehingga hanya itu yang ditambahkan pertama kali (tidak akan berubah jika ini tidak terjadi karena indeks negara target sudah ada%reachable)%rkita dapat menggabungkan ini denganprint+(/$|.+\n/mg)[%r]untuk sampai pada kode aktualprint+(/$|.+\n/mg)[eval'%r=map%$_,%r,s/^@F$//m*$`=~y/\n//;'x pop@F]Pertanyaan selanjutnya adalah bagaimana menyandikan daftar negara. Seperti yang dijelaskan di atas, saya menginginkannya sebagai rangkaian besar dengan negara-negara diakhiri oleh baris baru dan dimulai dengan baris baru tunggal. Untuk ini saya perlu 26 huruf, spasi, baris baru,
-(untukGuinea-Bissau) dan'(untukCote D'Ivoire). Masalahnya tentu saja bahwa kadang-kadang huruf dalam huruf besar. Ini dengan mudah dipecahkan dengan menggunakan huruf besar setelah batas kata. Namun ada pengecualian:Republic of Ireland,Bosnia and HerzegovinadanDemocratic Republic of the Congo. Ini memiliki kata yang tidak dimulai dengan huruf besar. Saya bisa mengatasinya dengan mengganti spasi sebelum itu dengan garis bawah_yang menghentikannya agar tidak dikenali sebagai batas kata, kemudian diganti_dengan spasi. Pengecualian yang tersisa adalahUSAyang memiliki huruf besar yang tidak pada batas kata. Untuk itu saya perkenalkan batasan kata dengan menulis ini sebagaiu`s`adan kemudian menghapus backquotes. Bersama yang memberi:Dengan kode ini saya dapat mengkodekan seluruh negara string menggunakan hanya
a-z,,',-,\n,_dan`, yang 32 karakter yang berbeda. Jadi setiap karakter dapat dikodekan dengan 5 bit. Bahkan, jika saya memiliki bitstring yang besar11110100111..., saya dapat mengubahnya menjadi karakter yang diperlukan menggunakan:Jika saya memiliki string byte
$_maka bitstring besar yang saya butuhkan dapat dibuat menggunakan$_ = unpack"B*". Jadi pada dasarnya semua ini adalah basis kecil 256 ke basis 32 converter dan setiap huruf negara dikodekan menggunakan 5 bit dalam string negara biner yang masuk. Ini relatif kompak dan tidak menghasilkan apa pun untuk mengembangkan kode khusus untuk string berulang di daftar negara dengan satu pengecualian:Republicmuncul dalam 5 nama negara. Karena selalu muncul sebagai kata yang lengkap dan tidak ada nama negara yang dimulai denganX(satu-satunya huruf seperti itu) saya dapat menggunakannya sebagai kode pelarian setelah huruf pertama dari nama negara ditulis dengan huruf besar.Sekarang saya perlu cara untuk menyandikan hubungan "sentuhan". Hal pertama yang perlu diperhatikan adalah bahwa itu simetris, jadi jika negara
$nmenyentuh negara$t, maka negara$tjuga menyentuh negara$n. Jadi saya hanya perlu menyandikan setengah hubungan jika saya mengisi%toucheshash dua arah. Dalam kode yang disederhanakan Anda melihat bahwa sedang dilakukan olehKecuali bahwa kode yang sebenarnya digunakan
$.bukan$nkarena saya ingin penghitung mulai dari 1 bukannya 0 (negara 0 adalah string kosong boneka). Idenya adalah untuk menulis urutan indeks negara| A, B, C | D, E | ..yang mengatakan negara 1 menyentuh negara dengan indeksA,BdanC, negara 2 menyentuh indeksDdanEdll. Sebenarnya saya menyandikan offset dari negara saat ini (yang nantinya akan saya gunakan untuk membuat nilai-nilai kecil) dan hanya offset positif (ini memastikan hubungan "sentuhan" hanya dikodekan dalam satu arah, dan metode yang saya gunakan dapat tidak dapat menangani angka negatif). Beberapa negara memiliki daftar tetangga yang kosong karena hubungan sentuhan mereka telah diberikan oleh negara lain. Saya dapat rearange daftar negara (yang urutannya tidak relevan) sehingga ini datang di akhir daftar. Saya kemudian dapat menghilangkan negara-negara ini dari urutan. Ini tidak mendapatkan apa-apa karena saya membutuhkan banyak offset karena ada hubungan "sentuh" tetapi itu menghindari kehilangan byte dengan harus menyandikan dummy offset. Seperti yang dijelaskan di atas negara 0 adalah dummy string kosong jadi saya perlu memastikan bahwa akan dilewati. Saya bisa menulis urutan angka ini sebagai urutan byte di mana nilai byte sesuai dengan indeks offset. Namun saya masih perlu tahu di mana negara berikutnya secara berurutan dimulai (posisi|s dalam contoh di atas). Saya melakukan ini dengan menetapkan bit tinggi ke 1 untuk indeks pertama dalam daftar sentuhan negara tertentu, jadi untuk indeksAdanDdalam contoh di atas.Namun ada satu masalah yang menjengkelkan: ada lebih dari 127 negara. Jadi saya tidak bisa hanya menggunakan bit tanda karakter. Alih-alih, saya menemukan pengaturan negara sedemikian sehingga setiap negara tidak pernah lebih jauh sehingga 15 posisi jauh dari semua negara yang disentuhnya:
(pada saat saya menulis penjelasan ini, program pencarian saya benar-benar menemukan urutan di mana jarak maksimum paling banyak 12). Ini berarti saya dapat menggunakan
0x10sebagai bendera untuk menunjukkan awal dari negara baru dan saya hanya perlu menyandikan 32 nilai yang berbeda. Ini dapat dikompres untuk ekspansi dengan basis 256 yang sama dengan basis 32 konverter seperti yang diperlukan untuk daftar negara. Saya sebenarnya bisa meletakkan string sentuh sebelum string negara dengan0x00inbetween (sebelum pengkodean) jika saya menulis decoder sentuh sehingga berhenti pada ini\x00. Decoder negara ditulis sehingga ini0x00dibiarkan di awal menjadi baris baru awal yang saya butuhkan sehingga negara pada indeks 0 adalah string kosong.Versi kode yang lebih lama menggunakan fakta bahwa hanya ada 4 komponen yang terhubung dalam grafik negara untuk mengurangi indeks negara menjadi di bawah 128, tetapi itu jauh lebih rumit dan sedikit lebih lama dalam kode dan string yang dikodekan.
Kode untuk mengubah urutan byte ke
%toucheshash kemudian menjadi:Perhatikan bahwa semua negara singleton sama sekali tidak dikodekan sama sekali. Karena itu, digunakan sebagai input, mereka tidak akan pernah cocok, jadi
%reachablehanya akan berisi referensi ke negara kosong awal dan tidak ada yang dicetak.Dengan itu seluruh program dijelaskan. Semua yang diperlukan setelah itu adalah menulis sebuah program-meta yang menghasilkan string besar yang dikodekan dengan hati-hati memilih urutan negara-negara sedemikian rupa sehingga
'(yang akan membatalkan string tunggal yang dikutip akhir)sumber
JavaScript (ES6),
28622324Mengembalikan objek Set yang berisi negara yang tepat. Perhatikan bahwa ini berisi banyak hal yang tidak patut.
Cuplikan uji (diperlukan browser yang mendukung ES6)
Tampilkan cuplikan kode
Bagaimana itu bekerja
Sebelum yang lain, saya menghapus semua negara tanpa tetangga dari daftar. Lalu saya mengurangi daftar ke format ini:
Ini memadatkan daftar menjadi 2130 byte. Entri kosong dimasukkan dengan hati-hati di mana negara yang diwakili oleh koma adalah untuk menghindari kegagalan regex. Sekarang untuk bagian yang menarik:
sumber
JavaScript (ES6) 2622
3815Suatu fungsi mengembalikan satu set. Pemindaian rekursif menggunakan satu set untuk menghindari pengulangan.
(2 baris baru ditambahkan untuk dibaca - harus satu baris)
Meminjam gagasan @ETHproduk tidak menyimpan negara tanpa tetangga . (Meminjam ortografinya juga, saya selalu salah mengeja kata itu)
Penjelasan
Uji
sumber
1/xbukannya+x?" Kemudian saya menyadari bahwa itu adalah cara yang cerdas untuk mengatasi kasus ini0. +1Python 2,
6967696569506906 byteSaya benar-benar berharap semuanya beres. Contoh:
Memasukkan:
Keluaran:
Saya harap garis kosong diizinkan.Tidak ada lagi baris kosong! Yay!Penjelasan:
Garis panjang di atas adalah data tentang nama masing-masing negara, dan negara-negara di sekitarnya. Setiap elemen dalam daftar adalah daftar lain, yang elemen pertama adalah nama negara, dan elemen lainnya adalah indeks dari setiap negara yang mengelilinginya. AS adalah elemen pertama, dan berisi indeks
1, 2. Elemen 1 dalam daftar adalah Kanada, dan elemen 2 dalam daftar adalah Meksiko. Daftar ini dibuat menggunakan program ini:...... [daftar besar di atas]
Output berisi koma yang dapat dihapus oleh Regex yang sangat sederhana, yang dapat ditemukan di sini . Seluruh program tersedia di sini . Outputnya adalah 4.736 byte, sekitar 88% dari program.
Berikut adalah sisa dari program dengan nama variabel yang tepat, komentar dan spasi putih (versi sebelumnya):
sumber
{}membuat keputusan, sayangnya.{x for d in Q[A][1:] if d not in C}danC|=nbukannyafor A in C:loop.Mathematica, program 128B + 2856B data = 2984 byte
Di mana
FOOstring 2856-byte (tidak disisipkan di sini karena mengandung karakter yang tidak dapat dicetak dan hanya MMA). String adalah daftar daftar terkompresi BZIP2, di mana setiap daftar dalam memiliki formulir{Country, Neighbor, Neighbor, ...}. Daftar ini sudah dioptimalkan untuk menghapus tepi yang berlebihan.Setelah itu dalam format grafik Mathematica memungkinkan kita melakukan hal-hal baik yang mudah seperti ini:
Untuk mendapatkan hal-hal seperti:
sumber
PHP,
5169271626982321 byteMemperbarui
Ini adalah versi saya yang kedua, yang sangat singkat. Posting asli lihat di bawah.
Ini ternyata menjadi edit yang agak rinci ...
Menghapus negara tanpa tetangga.
Definisi array asli saya adalah panjang 4901 byte kekalahan - menghapus semua negara tanpa tetangga (seperti yang disarankan @ETHproductions) mengurangi ini sebesar 725 byte menjadi 4176 byte. Tentu saja ini membutuhkan beberapa kode logika tambahan yang ditambahkan untuk memenuhi fallback, tetapi itu harus diabaikan dibandingkan dengan keuntungan besar ini.
Menggunakan karakter alih-alih angka
Langkah saya berikutnya adalah mengurangi jumlah byte yang dibutuhkan untuk memecahkan kode referensi tetangga. Ide pertama saya adalah untuk membuang sistem desimal dan menggunakan basis yang lebih tinggi untuk mewakili angka-angka (misalnya basis 36 yang akan menggunakan 0-9 plus az), tetapi logika tambahan yang diperlukan untuk memecahkan kode ini tampak banyak. Jadi saya mencari sesuatu yang lain: karakter.
Setiap karakter ASCII hanya satu byte panjang dan memetakan ke sejumlah rentang 0..255 yang terdefinisi dengan baik, yang persis apa yang dibutuhkan. Saya melewatkan 39 karakter ASCII pertama karena tidak dapat dicetak / termasuk
'dan"mana yang perlu melarikan diri. Definisi array yang dihasilkan hanya 2878 byte, menghemat 1298 byte atau 31% bila dibandingkan dengan sebelumnya. Tentu saja, ini juga membutuhkan logika tambahan, tapi untungnyachrdanordnama fungsi yang agak pendek :-)Mengompresi nama negara
Nama-nama negara itu masih memakan banyak ruang, jadi saya memutuskan untuk melihat bagaimana saya bisa mengompres mereka. Lima negara memiliki istilah "Republik" di dalamnya, jadi saya dapat menyimpan 16 byte dengan menyatakan
$r='Republic'sekali dan kemudian menulis"$r of Ireland"dll. Hal yang sama berlaku untuk "Guinea", yang muncul 4 kali.Ada juga beberapa kombinasi huruf yang terjadi relatif sering, tetapi karena mengetik
$xmasih dua karakter, menggantikannya hanya masuk akal untuk kombinasi dengan 3+ huruf dan jika benar-benar ada BANYAK yang dapat diganti. Sebagai contoh, mengganti semua 10-nias diTanzaniadll. Hanya diperoleh 1 byte. Sama dengan-istan(4x, -1), lebih banyak keberuntungan dengan-land(7x, -4).PHP "fitur"
Untungnya untuk pegolf kode, PHP tidak terlalu keberatan ketika Anda melanggar aturan sintaksisnya. Di sini, kita dapat menggunakan ini untuk menghapus beberapa tanda kutip, mengubah
'Lesotho'=>'E'(14 byte) menjadiLesotho=>E(10 byte). Hebatnya (atau:? Mengejutkan) ini bahkan bekerja untuk setiap string yang terdiri dari AZ, 0-9 atau paruh kedua tabel ASCII dan tidak dimulai dengan angka , membuat sesuatu seperti INI mungkin:India=>nh¢•Q“.Namun, sangat disayangkan bahwa desainer dari tabel ASCII menempatkan tanda baca di antara blok huruf, yang berarti bahwa tidak ada blok berkelanjutan dari karakter yang tidak bermakna PHP untuk mengakomodasi 150 negara dalam daftar. Ini menghasilkan banyak string yang masih mempertahankan kuotasi. Kadang-kadang saya memindahkan angka ke belakang sehingga string tidak akan mulai dengan angka.
Definisi array akhir
Semua ini membawa definisi array ke 2534 byte, hampir setengah dari nilai awal. Tentu saja, orang sekarang bisa pergi dan mengoptimalkan urutan negara sehingga sebanyak mungkin entri dapat kehilangan tanda kutip, dll., Tetapi saya tidak ingin melakukan banyak upaya dalam hal ini. ;-)
Kode
Jadi ini dia, versi kedua, dengan sedikit tambahan logika ditambahkan:
Golf
Edit dari pembaruan
Disimpan 18 byte lagi oleh:
$r='Republic'dll. (-10)fordenganwhileloop (-6)askata kunci (-2)Saya memperbarui kode di atas dengan perubahan.
Sunting lagi
Memotong 377 byte lainnya dengan membuat array yang diindeks dari string yang meledak terlebih dahulu (membuat semua
=>dan"usang, -417 byte overhead) dan mengubahnya menjadi array asosiatif yang diinginkan sesudahnya (+40 byte kode). Memperbarui kode di atas lagi.Posting awal
Ini adalah versi pertama yang agak cepat, saya belum melakukan kompresi daftar APA PUN selain nomor yang jelas untuk nama - saya mungkin bekerja besok dan mengedit posting saya kemudian.
Daftar saya adalah array asosiatif sederhana dengan entri untuk setiap negara. Kunci array adalah nama negara dan nilai array dari tetangganya, dirujuk oleh indeks mereka dalam array itu. PHP tidak akan membiarkan Anda mengakses array asosiatif menurut indeks, jadi saya perlu solusi
array_keysdanarray_valuesfungsi yang digunakan.Kode aktual berkomentar:
Seperti sebelumnya dan selalu, setiap ucapan sangat dihargai.
sumber
Dyalog APL , program 82 byte + data 1924 byte = 2006 byte
Saya tidak melakukan sesuatu yang istimewa untuk mengemas data selain menggunakan Dyalog APL built-in (de) serialize (
220⌶) dan (un-) zip (219⌶).Di mana elips berdiri untuk string zlib'ed dengan nilai byte ini:
Perhatikan bahwa string yang disandikan, dan program lainnya cocok dengan halaman kode 256 karakter APL, yaitu satu simbol per byte.
Inilah yang terlihat seperti ketika disatukan, (
␀berdiri untuk U + 0000):sumber