*** ameoba graph **** adalah jenis pohon yang semua simpulnya memiliki nilai dari 0 hingga beberapa bilangan bulat non-negatif, dan setiap simpul tertentu dengan nilai x <N terhubung ke x + 1 node berbeda dengan nilai x + 1.
Grafik Ameoba untuk N = 3: (Ditandakan A 3 )
Perhatikan bahwa 2's tidak diizinkan untuk membagikan salah satu dari 3's; tepat tiga 3 harus "milik" masing-masing 2.
Tantangan
Tugas Anda adalah secara induktif "menumbuhkan" grafik ameoba ini dalam kisi 2 dimensi dengan dengan rakus meminimalkan jarak Manhattan antara node:
- Kasing dasar: A 0 hanyalah grafik
0
. - Langkah induktif: A N + 1 dihasilkan dengan secara iteratif menempatkan node bernilai N + 1 sedekat mungkin ke node nilai N dalam struktur A N yang ada. (Itu hanya bisa sedekat mungkin karena tempat terdekat mungkin sudah diisi.)
Untuk langkah induktif, prosedur umum yang harus Anda ikuti adalah:
for each existing node P with value N:
for each new N+1 valued node Q you need to connect to P: //this loops N+1 times
find the set of vacant spots that are minimally distant from P //by Manhattan distance
place Q in any of these vacant spots
(Prosedur berbeda dengan hasil yang tidak bisa dibedakan tidak masalah.)
Contoh pertumbuhan untuk A 4 :
A0 is always the same:
0
For A1 I happen to put the 1 to the right of the 0 (it has to go on one of the 4 open sides):
01
For A2 I happen to put the two 2's above and to the right of the 1:
2
012
For A3 I find that one of the six 3's I must place cannot be directly next to a 2, so I put in one of the next closest places:
3
323
0123
33 <-- this 3 is distance two away from its 2
The process continues in A4. Note that I'm iterating over each 3 and placing four 4's next to it or as close as possible, then moving to the next 3 (the order of 3's does not matter):
444
443444
4323444
4012344
44334
4444
44
Always keep in mind that nodes cannot be "shared".
Program
Program yang Anda tulis harus mengambil angka dari 0 hingga 8 (inklusif) dan mengeluarkan grafik ameoba yang valid, menggunakan pola pertumbuhan induktif yang dijelaskan di atas.
Apa yang terjadi di luar 8 tidak masalah.
(A 8 berisi 46234 node yang mendorongnya. Apa pun di luar A 8 akan terlalu jauh. Terima kasih kepada Martin Büttner karena memperhatikan ini.)
Input harus berasal dari stdin atau baris perintah dan output harus pergi ke stdout atau file.
Contoh (diambil langsung dari atas)
Input: 0
Output:
0
Input: 1
Output:
01
Input: 2
Output:
2
012
Input: 3
Output:
3
323
0123
33
Input: 4
Output:
444
443444
4323444
4012344
44334
4444
44
* Jenis grafik ini mungkin sudah memiliki nama. Saya akui saya hanya mengada-ada. ;)
Jawaban:
Mathematica,
353288285275 bytesTidak Disatukan:
Berikut adalah contoh output untuk
n = 5
:Input
8
membutuhkan waktu sekitar 4,5 menit.Untuk perincian cepat algoritme saya:
Saya menggunakan dua tabel pencarian,
f
dang
. Yang pertama hanyalah peta tipis yang berisi sel-sel yang tidak kosong. Yang terakhir adalah daftar yang berisi semua pasangan koordinat untuk setiap nilai sel (saya pikir saya bahkan tidak perlu melacak yang lama di sini). Saya mengulangi melalui koordinatg
untuk memperluas setiap sel dari iterasi terakhir. Untuk melakukan itu saya mengulangi jarak Manhattan, membuat semua vektor yang mungkin untuk setiap jarak, dan memeriksa apakah sel yang dihasilkan masih kosong (dalam hal ini saya mengisinya). Ulangi sampai cukup sel baru dibuat.Ketika saya selesai, saya menemukan koordinat minimum dan maksimum
g
dan saya membuat grid yang sesuai, yang diisi dengan mencari sel-sel di dalamnyaf
. Sisanya hanya menggabungkan semuanya menjadi satu string dengan jeda baris.sumber
C -
309 305 301275 bytesMeh, terlalu lama ... jika hanya satu yang bisa mengetik
#D
atau sesuatu#define
, maka C akan sangat bagus. Tentu saja-D
flag compiler dimungkinkan tetapi itu tampak seperti menipu saya, untuk memiliki karakter selain yang ada di file sumber.Instruksi berlari:
Hati-hati! Tombol pertama yang Anda tekan setelah program dimulai merupakan input. Setelah entri karakter selain '0' hingga '8', siapa yang tahu hal-hal yang tidak terdefinisi akan terjadi.
Versi Ungolfed (tapi sudah memikirkan golf masa depan):
Sunting: Saya menyadari bahwa karena saya memindahkan deklarasi di luar main (), array tidak lagi dapat dialokasikan pada stack, jadi saya bebas menggunakan memori secara boros tanpa risiko meluap.
sumber
Ruby - 296
Sedikit tidak berbulu.
sumber
APL (Dyalog) (121)
Karakteristik kinerja: ini O (n!). Di sistem saya, hingga n = 5 itu instan; n = 6 membutuhkan satu detik, n = 7 membutuhkan satu menit dan n = 8 membutuhkan satu jam.
Versi non-golf
Uji:
Penjelasan:
{
...}⎕
: baca baris dari keyboard, evaluasilah, dan berikan hasilnya ke fungsi.0::0
: jika kode lain menimbulkan kesalahan, kembalikan satu0
. Ini karena matematika gagal ketika mencoba menghitung ukuran untuk grafik dengan 0 node, yang merupakan kasus ketika output seharusnya0
. (Versi sebelumnya memiliki⍵=0:0
, (jika input0
dikembalikan0
sebaliknya buat grafik), tetapi0::0
(coba saja dan kembali0
jika gagal) lebih pendek.)M←⌈4×.5*⍨3÷⍨+/!⍳⍵
: dengan asumsi output adalah lingkaran kasar (ini berfungsi), jumlah faktorial dari1
ke⍵
(= area output), bagi dengan 3 (cukup dekat ke pi), ambil akar kuadrat (memberikan jari-jari output), kalikan dengan 4, dan ambil langit-langit. Ini memberi dua kali diameter lingkaran, sehingga output cocok dengan ruang yang tersisa. Simpan di iniM
.V←,⍳⍴Z←' '⍴⍨2/M
: Membuat matriks M-by-M ruang dan menyimpannya dalamZ
. Ini akan menahan output. Menyimpan daftar koordinat semua elemen diV
.Z[G;G←⌈M÷2]←'0'
: setel elemen tengahZ
ke0
.Z⊢{
...}¨⍳⍵
: kembaliZ
, setelah menerapkan fungsi berikut ke angka1
ke⍵
:⍵∘{
...}V/,Z=⍕⍵-1
: untuk setiap elemenZ
dengan nilai node sebelumnya:⍵∘{
...}⍺/⍺
: untuk simpul saat ini, N kali,⊃F[⍋+/¨|(F←V/⍨,Z=' ')-⊂⍺]
: dapatkan ruang kosong terdekat dengan simpul saat ini,(
...⌷Z)←⍕⍵
: dan atur spasi tersebutZ
ke nilai node saat ini.sumber