Lingkaran kemasan

21

Lihatlah gambar ini. Secara khusus, pada bagaimana lubang di ujungnya diatur.

masukkan deskripsi gambar di sini

( Sumber gambar )

Perhatikan bagaimana pipa di gambar ini dikemas dalam pola heksagonal. Diketahui bahwa dalam 2D, kisi heksagonal adalah kemasan lingkaran yang paling padat. Dalam tantangan ini, kami akan fokus pada meminimalkan keliling kemasan lingkaran. Salah satu cara yang berguna untuk memvisualisasikan perimeter adalah membayangkan meletakkan karet gelang di sekitar kumpulan lingkaran.

Tugas

Dengan bilangan bulat positif nsebagai input, tunjukkan kumpulan nlingkaran yang dikemas sekencang mungkin.

Aturan dan Klarifikasi

  • Asumsikan lingkaran memiliki diameter 1 unit.
  • Variabel yang akan diminimalkan adalah panjang perimeter, yang didefinisikan sebagai lambung cembung dari pusat lingkaran dalam grup. Lihatlah gambar ini:

masukkan deskripsi gambar di sini

Tiga lingkaran dalam garis lurus memiliki perimeter 4 (cembung cembung adalah persegi panjang 2x0, dan 2 dihitung dua kali), yang disusun dalam sudut 120 derajat memiliki perimeter sekitar 3,85, dan segitiga memiliki perimeter hanya 3 unit. Perhatikan bahwa saya mengabaikan unit pi tambahan yang perimeter sebenarnya karena saya hanya melihat pusat lingkaran, bukan tepi mereka.

  • Mungkin ada (dan hampir pasti akan) beberapa solusi untuk setiap yang diberikan n. Anda dapat menampilkan semua ini atas kebijakan Anda. Orientasi tidak masalah.
  • Lingkaran harus pada kisi heksagonal.
  • Lingkaran harus berdiameter minimal 10 piksel, dan dapat diisi atau tidak.
  • Anda dapat menulis program atau fungsi.
  • Input dapat diambil melalui STDIN, sebagai argumen fungsi, atau setara terdekat.
  • Output dapat ditampilkan atau output ke file.

Contohnya

Di bawah ini saya memiliki contoh output yang valid dan tidak valid untuk n dari 1 hingga 10 (contoh yang valid hanya untuk lima yang pertama). Contoh yang valid ada di sebelah kiri; setiap contoh di sebelah kanan memiliki perimeter lebih besar dari contoh valid yang sesuai.

masukkan deskripsi gambar di sini

Terima kasih banyak kepada steveverrill atas bantuannya menulis tantangan ini. Selamat packing!

El'endia Starman
sumber
3
Menunggu di Hexagony, saya bertaruh. ; D
Addison Crump
@VoteToClose: Saya tidak berpikir Hexagony memiliki output grafis, tapi MAN, itu akan luar biasa!
El'endia Starman
@ El'endiaStarman Baiklah, Anda bisa menulis SVG ke stdout, tapi saya rasa saya tidak akan ...: P
Martin Ender
1
Wow, tidak ada yang mengucapkan terima kasih dengan berani atas komentar saya di kotak pasir sebelumnya. Aku tersipu :-D Tentu saja aku berkomentar karena aku menyukai tantangan, meskipun aku tidak yakin apakah aku akan punya waktu untuk menjawabnya.
Level River St
Per diskusi saya dengan Reto Koradi pada jawaban pengguna81655, saya pikir segi enam terbesar yang akan kita lihat dengan sudut tajam adalah sidelength 7d (8 lingkaran.) Itu N = total 169 lingkaran. Anda dapat mempertimbangkan untuk membatasi masalah ke nomor itu, yang akan memberi lebih banyak peluang untuk mendapatkan jawaban yang benar (saat ini tidak ada) dan dapat memeriksa. Di sisi lain mungkin akan lebih menarik untuk membiarkan masalah terbuka untuk sembarang N.
Level River St

Jawaban:

4

Mathematica 295 950 byte

Catatan: Versi yang masih harus di-golf ini membahas masalah yang diangkat oleh Steve Merrill tentang upaya saya sebelumnya.

Meskipun ini merupakan peningkatan dari versi pertama, ia tidak akan menemukan konfigurasi handle terpadat di mana orang akan mencari bentuk keseluruhan yang melingkar, bukannya heksagonal.

Ia menemukan solusi dengan membangun segi enam bagian dalam yang lengkap (untuk n> = 6, dan kemudian memeriksa semua konfigurasi untuk melengkapi kulit terluar dengan lingkaran yang tersisa.

Menariknya, seperti yang dicatat Steve Merrill dalam komentar, solusi untuk n+1lingkaran tidak selalu terdiri dari solusi untuk n lingkaran dengan lingkaran lain ditambahkan. Bandingkan solusi yang diberikan untuk 30 lingkaran dengan solusi yang diberikan untuk 31 lingkaran. (Catatan: ada solusi unik untuk 30 lingkaran.)

m[pts_]:={Show[ConvexHullMesh[pts],Graphics[{Point/@pts,Circle[#,1/2]&/@ pts}], 
ImageSize->Tiny,PlotLabel->qRow[{Length[pts],"  circles"}]],
RegionMeasure[RegionBoundary[ConvexHullMesh[pts]]]};
nPoints = ((#+1)^3-#^3)&;pointsAtLevelJ[0] = {{0,0}};
pointsAtLevelJ[j_]:=RotateLeft@DeleteDuplicates@Flatten[Subdivide[#1, #2, j] &@@@
Partition[Append[(w=Table[j{Cos[k Pi/3],Sin[k Pi/3]},{k,0,5}]), 
w[[1]]], 2, 1], 1];nPointsAtLevelJ[j_] := Length[pointsAtLevelJ[j]]
getNPoints[n_] := Module[{level = 0, pts = {}},While[nPoints[level]<=n, 
pts=Join[pointsAtLevelJ[level],pts];level++];Join[Take[pointsAtLevelJ[level],n-Length[pts]],
pts]];ns={1,7,19,37,61,91};getLevel[n_]:=Position[Union@Append[ns,n],n][[1, 1]]-1;
getBaseN[n_] := ns[[getLevel[n]]];pack[1]=Graphics[{Point[{0,0}], Circle[{0, 0}, 1/2]}, 
ImageSize->Tiny];pack[n_]:=Quiet@Module[{base = getNPoints[getBaseN[n]], 
outerRing = pointsAtLevelJ[getLevel[n]], ss},ss=Subsets[outerRing,{n-getBaseN[n]}];
SortBy[m[Join[base,#]]&/@ss,Last][[1]]]

Beberapa cek mensyaratkan perbandingan lebih dari seratus ribu kasus untuk nilai tunggal n (termasuk simetri). Butuh waktu sekitar 5 menit untuk menjalankan total 34 kasus uji. Tak perlu dikatakan, dengan lebih besar n'spendekatan brute-force ini akan segera terbukti tidak praktis. Pendekatan yang lebih efisien pasti ada.

Angka-angka di sebelah kanan setiap kemasan adalah batas masing-masing lambung cembung biru. Di bawah ini adalah output untuk 3 < n < 35. Lingkaran merah adalah yang ditambahkan di sekitar segi enam biasa.

disk


DavidC
sumber
1
Seperti yang saya sebutkan pada jawaban pengguna 81655, lingkaran tunggal yang menonjol pada 22 (dan 17, 25, 28, 31, 34) akan lebih baik ditempatkan di tengah barisan lingkaran tempat ia duduk.
Level River St
Saya juga berpikir demikian, tetapi kemudian saya perhatikan bahwa 9, yang juga memiliki lingkaran yang menonjol dianggap benar. Ketika saya punya waktu, saya akan membandingkan pengukuran lambung cembung (pusat).
DavidC
di 9 lingkaran yang menonjol adalah 1/4 atau 3/4 di sepanjang baris datar, sehingga tidak ada bedanya. dalam 17, 22, 25, 28, 31 lingkaran yang menonjol adalah 1/6, 3/6 atau 5/6 sepanjang, sehingga posisi tengah lebih baik (pikirkan tentang menarik tali ke samping: lebih mudah untuk menarik dari tengah karena itu cara string memiliki ekstensi lebih sedikit untuk dilakukan. Dalam 34 (dan 35) kita memiliki 1/8, 3/8, 5/8 dan 7/8 sepanjang sisi datar. Jadi untuk ini kita harus memilih 3/8 dan 5/8 sebelum 1/8 dan 7/8
Level River St
Anda memang benar dan ini dikonfirmasi oleh pengukuran.
DavidC
Ini luar biasa! Transisi 30-> 31 menunjukkan bahwa kita tidak bisa hanya mengambil bentuk sebelumnya dan menambahkan lingkaran ke luar (yang akan memberikan perimeter 16,464.) Ada juga setidaknya satu kasus di mana Anda bisa menambahkan satu lingkaran ke luar, tetapi memilih pengaturan yang berbeda: 12-> 13
Level River St