Tugas
Anda harus menulis sebuah program atau fungsi dalam bahasa pilihan Anda yang secara akurat menghitung jumlah siklus terminal dari grafik sederhana yang diarahkan.
Jenis grafik terarah khusus ini direpresentasikan sebagai array n bilangan bulat, masing-masing dengan nilai acak yang dipilih secara independen antara 1 dan n (atau 0 dan n-1, jika bahasa Anda dihitung dari 0). Grafik dapat dianggap sebagai panah yang menunjuk dari satu indeks (simpul) ke indeks yang cocok dengan nilai yang ditemukan pada indeks awal.
Fungsi Anda harus mampu menerima grafik besar, hingga n = 1024, atau ukuran integer yang lebih kecil.
Contoh
Pertimbangkan grafik ini untuk n = 10:
[9, 7, 8, 10, 2, 6, 3, 10, 6, 8]
Indeks 1 berisi 9, jadi ada panah dari indeks 1 ke indeks 9. Indeks 9 berisi 6, jadi ada panah 9 -> 6. Indeks 6 berisi 6, yang merupakan siklus terminal, menunjuk kembali ke dirinya sendiri.
Indeks 2 berisi 7. Indeks 7 berisi 3. Indeks 3 berisi 8. Indeks 8 berisi 10. Indeks 10 berisi 8, jadi itu adalah siklus terminal kedua (8 -> 10 -> 8 -> 10, dll. ).
Indeks 4 -> 10, yang memasuki siklus terminal kedua. Demikian juga, indeks 5 -> 2 -> 7 -> 3 -> 8, yang juga merupakan bagian dari siklus terminal kedua.
Pada titik ini, semua indeks (node) telah diperiksa, semua jalur telah diikuti, dan dua siklus terminal yang unik diidentifikasi. Oleh karena itu, fungsi harus mengembalikan 2 , karena itu adalah jumlah siklus terminal dalam grafik yang diarahkan ini.
Mencetak gol
Bidik kode terkecil, tetapi pastikan ia menghitung siklus terminal dengan benar. Kode terpendek setelah 1 minggu menang.
Uji Kasus
Berikut adalah beberapa kasus uji untuk memeriksa kebenaran kode Anda. Jika bahasa Anda menghitung indeks array mulai dari 0, tentu saja Anda harus mengurangi 1 dari nilai setiap elemen array, untuk mencegah indeks out-of-bound.
n = 32, 5 siklus:
[8, 28, 14, 8, 2, 1, 13, 15, 30, 17, 9, 8, 18, 19, 30, 3, 8, 25, 23, 12, 6, 7, 19, 24, 17, 7, 21, 20, 29, 15, 32, 32]
n = 32, 4 siklus:
[20, 31, 3, 18, 18, 18, 8, 12, 25, 10, 10, 19, 3, 9, 18, 1, 13, 5, 18, 23, 20, 26, 16, 22, 4, 16, 19, 31, 21, 32, 15, 22]
n = 32, 3 siklus:
[28, 13, 17, 14, 4, 31, 11, 4, 22, 6, 32, 1, 13, 15, 7, 19, 10, 28, 9, 22, 5, 26, 17, 8, 6, 13, 7, 10, 9, 30, 23, 25]
n = 32, 2 siklus:
[25, 23, 22, 6, 24, 3, 1, 21, 6, 18, 20, 4, 8, 5, 16, 10, 15, 32, 26, 25, 27, 14, 13, 12, 9, 9, 29, 8, 13, 31, 32, 1]
n = 32, 1 siklus:
[6, 21, 15, 14, 22, 12, 5, 32, 29, 3, 22, 23, 6, 16, 20, 2, 16, 25, 9, 22, 13, 2, 19, 20, 26, 19, 32, 3, 32, 19, 28, 16]
n = 32, 1 siklus:
[8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 1, 2, 3, 4, 5, 6, 7]
n = 1024, 6 siklus:
[239, 631, 200, 595, 178, 428, 582, 191, 230, 551, 223, 61, 564, 463, 568, 527, 143, 403, 154, 236, 928, 650, 14, 931, 236, 170, 910, 782, 861, 464, 378, 748, 468, 779, 440, 396, 467, 630, 451, 130, 694, 167, 594, 115, 671, 853, 612, 238, 464, 771, 825, 471, 167, 653, 561, 337, 585, 986, 79, 506, 192, 873, 184, 617, 4, 259, 4, 662, 623, 694, 859, 6, 346, 431, 181, 703, 823, 140, 635, 90, 559, 689, 118, 117, 130, 248, 931, 767, 840, 158, 696, 275, 610, 217, 989, 640, 363, 91, 129, 399, 105, 770, 870, 800, 429, 473, 119, 908, 481, 337, 504, 45, 1011, 684, 306, 126, 215, 729, 771, 5, 302, 992, 380, 824, 868, 205, 807, 917, 407, 759, 181, 640, 685, 795, 258, 180, 900, 20, 773, 546, 866, 564, 761, 632, 895, 968, 980, 651, 225, 676, 18, 685, 784, 208, 227, 3, 267, 852, 57, 487, 566, 633, 849, 309, 543, 145, 575, 811, 621, 560, 492, 24, 665, 66, 851, 168, 262, 259, 754, 481, 565, 768, 172, 1012, 241, 3, 370, 985, 389, 82, 779, 744, 829, 836, 249, 975, 909, 840, 226, 867, 499, 192, 909, 972, 735, 252, 785, 545, 486, 186, 1011, 89, 939, 649, 110, 119, 185, 836, 717, 545, 938, 621, 946, 94, 363, 721, 177, 747, 59, 819, 146, 283, 821, 547, 654, 941, 755, 18, 449, 367, 499, 944, 62, 553, 435, 344, 900, 25, 251, 920, 902, 99, 326, 98, 495, 385, 929, 865, 327, 725, 674, 33, 173, 429, 873, 558, 90, 460, 366, 543, 583, 954, 792, 213, 536, 670, 49, 738, 802, 1015, 23, 915, 119, 263, 307, 601, 474, 971, 826, 613, 446, 37, 145, 894, 901, 307, 906, 886, 990, 89, 798, 384, 487, 822, 354, 768, 902, 163, 179, 134, 920, 439, 619, 215, 94, 709, 744, 366, 543, 349, 347, 2, 438, 141, 486, 19, 998, 500, 857, 955, 932, 1, 587, 195, 646, 550, 887, 626, 400, 348, 154, 808, 678, 873, 186, 282, 168, 993, 722, 56, 345, 5, 226, 328, 22, 894, 658, 264, 13, 803, 791, 359, 217, 997, 168, 578, 952, 734, 964, 898, 659, 628, 980, 15, 31, 439, 13, 875, 687, 1004, 1023, 165, 642, 561, 897, 711, 124, 404, 346, 723, 774, 352, 784, 276, 395, 14, 443, 343, 153, 510, 590, 172, 215, 130, 106, 295, 906, 133, 758, 483, 898, 391, 760, 702, 972, 721, 611, 592, 1001, 724, 934, 59, 831, 171, 253, 869, 431, 538, 20, 648, 76, 351, 103, 33, 385, 852, 437, 470, 95, 434, 408, 430, 994, 366, 706, 809, 532, 161, 388, 668, 245, 965, 365, 913, 471, 927, 245, 256, 805, 540, 380, 995, 446, 657, 545, 573, 955, 499, 322, 949, 635, 401, 185, 421, 626, 534, 429, 930, 633, 563, 348, 626, 518, 682, 233, 775, 444, 42, 199, 57, 271, 683, 397, 883, 620, 768, 8, 331, 497, 19, 340, 900, 919, 497, 276, 78, 252, 164, 764, 927, 242, 270, 759, 824, 945, 886, 262, 59, 439, 217, 720, 519, 862, 626, 326, 339, 589, 16, 565, 947, 604, 144, 87, 520, 256, 240, 336, 685, 361, 998, 805, 678, 24, 980, 203, 818, 855, 85, 276, 822, 183, 266, 347, 8, 663, 620, 147, 189, 497, 128, 357, 855, 507, 275, 420, 755, 131, 469, 672, 926, 859, 156, 127, 986, 489, 803, 433, 622, 951, 83, 862, 108, 192, 167, 862, 242, 519, 574, 358, 549, 119, 630, 60, 925, 414, 479, 330, 927, 94, 767, 562, 919, 1011, 999, 908, 113, 932, 632, 403, 309, 838, 341, 179, 708, 847, 472, 907, 537, 516, 992, 944, 615, 778, 801, 413, 653, 690, 393, 452, 394, 596, 545, 591, 136, 109, 942, 546, 57, 626, 61, 587, 862, 829, 988, 965, 781, 849, 843, 815, 60, 928, 784, 388, 341, 491, 565, 83, 110, 164, 38, 1024, 859, 297, 520, 327, 733, 699, 631, 78, 178, 671, 895, 818, 637, 99, 425, 933, 248, 299, 333, 144, 323, 105, 849, 942, 767, 265, 72, 204, 547, 934, 916, 304, 919, 273, 396, 665, 452, 423, 471, 641, 675, 60, 388, 97, 963, 902, 321, 826, 476, 782, 723, 99, 735, 893, 565, 175, 141, 70, 918, 659, 935, 492, 751, 261, 362, 849, 593, 924, 590, 982, 876, 73, 993, 767, 441, 70, 875, 640, 567, 920, 321, 46, 938, 377, 905, 303, 736, 182, 626, 899, 512, 894, 744, 254, 984, 325, 694, 6, 367, 532, 432, 133, 938, 74, 967, 725, 87, 502, 946, 708, 122, 887, 256, 595, 169, 101, 828, 696, 897, 961, 376, 910, 82, 144, 967, 885, 89, 114, 215, 187, 38, 873, 125, 522, 884, 947, 962, 45, 585, 644, 476, 710, 839, 486, 634, 431, 475, 979, 877, 18, 226, 656, 573, 3, 29, 743, 508, 544, 252, 254, 388, 873, 70, 640, 918, 93, 508, 853, 609, 333, 378, 172, 875, 617, 167, 771, 375, 503, 221, 624, 67, 655, 465, 272, 278, 161, 840, 52, 1016, 909, 567, 544, 234, 339, 463, 621, 951, 962, 1019, 383, 523, 279, 780, 838, 984, 999, 29, 897, 564, 762, 753, 393, 205, 31, 150, 490, 156, 796, 586, 676, 773, 465, 489, 1024, 433, 214, 701, 480, 604, 280, 241, 563, 943, 911, 12, 400, 261, 883, 999, 207, 618, 141, 959, 767, 978, 461, 992, 982, 272, 143, 404, 645, 331, 348, 783, 698, 827, 82, 145, 536, 449, 852, 750, 789, 413, 913, 420, 14, 499, 285, 533, 223, 75, 591, 994, 884, 237, 63, 411, 563, 611, 801, 173, 759, 278, 318, 772, 1018, 48, 440, 333, 611, 834, 423, 583, 22, 716, 393, 794, 83, 83, 864, 859, 600, 525, 808, 569, 95, 952, 852, 567, 651, 2, 984, 906, 992, 747, 602, 143, 547, 1008, 940, 245, 633, 378, 193, 771, 965, 648, 437, 873, 591, 664, 271, 777, 274, 742, 68, 429, 825, 144, 55, 272, 279, 6, 400, 485, 66, 311, 663, 441, 23, 988, 726, 48, 624, 302, 617, 120, 653, 810, 641, 142]
sumber
Jawaban:
GolfScript, 25 karakter
Pendekatan yang sama seperti solusi Keith Randall tetapi dalam GolfScript. Perhatikan bahwa GolfScript memiliki array yang diindeks nol. Penguji online .
sumber
Mathematica 69
Kode
Ini menemukan jumlah komponen grafik.
Kasus uji pertama:
Analisis
Buat daftar tepi terarah di antara indeks, (menggunakan contoh 1).
Graph
menggambar grafik yang menunjukkan komponen grafik.ImagePadding
danVertexLabels
digunakan di sini untuk menampilkan indeks.WeaklyConnectedComponents
mengembalikan daftar simpul untuk setiap komponen.Length
mengembalikan jumlah komponen.Waktu daftar sampel dengan 1024 elemen:
Pengaturan waktu: 0,002015 dtk
Hanya untuk bersenang-senang, inilah gambar kasus ujian akhir, yang dibuat gambarnya. Saya menghilangkan label titik; terlalu banyak.
sumber
WeaklyConnectedComponents
sangat verbose. Tapi itu banyak pekerjaan. (Seseorang seharusnya tidak pernah meremehkan bahasa J dan bahasa-bahasa serupa untuk keringkasan.)Python,
132116 karakterUntuk setiap indeks, kami mengikuti tepian untuk n hop, yang menjamin kami berada dalam siklus terminal. Kami kemudian mengikuti n lebih banyak lompatan dan menemukan indeks minimum dalam siklus itu. Jumlah total siklus terminal adalah jumlah minimum yang berbeda yang kita temukan.
sumber
#define F for i in r
menggunakan Python, C (++) - style ... :)Dengan Python:
sumber
if
kondisi.c=lambda l:0 if l==[] else c(l[:-1])+1 if l[-1]==len(l) else c([[x,l[-1]][x==len(l)] for x in l[:-1]])
lebih baik: 102 byte.J -
6153 charYang ini doozy.
The
<@<:
mengubah daftar ke grafik J, yang terlihat seperti daftar kotak, dan kotak pada indeksi
berisi semua node nodei
menghubungkan ke. Indeks J dari nol, jadi kami gunakan<:
untuk mengurangi semuanya satu per satu sebelum bertinju<
.The
<~.@(],;@:{~)^:_&.>]
berubah setiap node menjadi daftar semua node yang dapat dicapai dari itu. Yang<...&.>]
bertanggung jawab untuk membuat ini terjadi pada setiap node, dan~.@(],;@:{~)^:_
sebenarnya berasal dari J golf dari tugas 'node terjangkau' yang saya lakukan beberapa minggu yang lalu.e.
melakukan tugas yang menarik. Jika "reachability" penutupan grafik (versi grafik sedemikian rupa sehingga jika ada tepi terarah X → Y dan Y → Z kita tambahkan edge X → Z.) Memiliki N node dan E edge, makae.
pada grafik ini membuat matriks boolean dari N baris dan kolom E, dengan True jika node yang sesuai berbagi node yang dapat dijangkau dengan tepi ini. Membingungkan, tapi tahan dengan sayaSelanjutnya, kita harus menemukan jumlah siklus terminal, yaitu jumlah grup yang membagikan Trues di antara kolom mereka. Kami ingin membuat semacam tabel perkalian dari baris (
"1/~
), dan kami menggunakan jenis produk dalam sebagai perkalian, yang dipasangkan dengan AND dan kemudian ATAU semua hasil secara bersamaan (+./ .*
). Matriks yang dihasilkan adalah tabel persegi dengan True di setiap posisi yang dua baris berbagi setidaknya satu kolom di antara mereka.Sekarang yang tersisa untuk dilakukan adalah memeriksa berapa banyak jenis pola baris yang ada. Jadi kami melakukan hal itu: kelompokkan baris bersama-sama dari jenis yang sama (
/.~
), laporkan angka di setiap grup (#
), lalu ambil jumlah grup (#@
).Penggunaan pada contoh lain:
Sayangnya kasus elemen 1024 sekarang membutuhkan waktu yang sangat lama untuk diakhiri. Versi sebelumnya
<:@#@((#~0={.+/@:*"1])^:a:)@e.@(~.@(],;@:{~)^:_&.>~<)@:(<@<:)
(61 char) butuh sedikit lebih dari satu detik untuk melakukan ini.sumber
Python (96)
Sangat, sangat, sangat, sangat berdasarkan pada jawaban user2228078, karena kerjanya persis sama, tetapi lebih golf:
(Pertanyaan teknis: haruskah golf jawaban orang lain menjadi komunitas wiki?)
sumber
Python
(89)(87)Gagasan utamanya adalah memulai pada setiap simpul secara bergantian dan berjalan di sepanjang jalan dari sana, menandai setiap simpul yang kita kunjungi dengan label unik ke simpul yang kita mulai. Jika kita pernah mengenai simpul yang ditandai, kita berhenti berjalan, dan memeriksa apakah yang menandai itu sesuai dengan simpul awal kita. Jika itu adalah kita harus berjalan satu lingkaran, jadi kita menambah hitungan siklus satu per satu.
Dalam kode,
u
adalah penghitung siklus,i
adalah simpul awal,j
adalah simpul saat ini yang kami lewati. Label yang sesuai dengan starting nodei
adalah komplemen bitnya~i
yang selalu negatif. Kami menandai sebuah simpul dengan mengarahkannya ke nilai itu, menimpa simpul apa pun yang sebenarnya ditunjuknya (berhati-hati untuk berjalan ke simpul itu sebelum dilupakan).Kami tahu kami telah mencapai simpul yang ditandai ketika kami berjalan ke "simpul" bernilai negatif segera setelahnya. Kami memeriksa apakah nilai negatif itu adalah label saat ini untuk melihat apakah kami telah menjalani siklus. Karena setiap simpul yang kita berjalan dihapus secara efektif, setiap siklus hanya akan berjalan satu kali.
Menghemat karakter untuk menghitung
i
secara manual dengan variabel dummy loop_
lalu sebagaifor i in range(len(G))
. Daftar python diindeks 0. Jika mereka bukan 1-diindeks, kita dapat menyimpan dua karakter dengan menulisj=i=i+1
untuk dimilikii
danj
menjadi 1 untuk loop pertama, dan menulisj>0
di tempatj>=0
.Edit:
Kita dapat menyimpan dua karakter dengan mengulangi
i
elemen-elemen dalam daftar daripada indeks, karena simpul yang tidak ditunjukkan oleh sisi mana pun tidak masalah. Kita harus mengulanginya terlebih dahuluset(G)
untuk menghindari pengulangan simpul awal yang ditunjukkan oleh beberapa simpul lainnya.sumber