Diberikan grafik terarah, menghasilkan siklus terpanjang.
Aturan
- Format input yang masuk akal diizinkan (misalnya daftar tepi, matriks konektivitas).
- Label tidak penting, jadi Anda dapat memberlakukan batasan pada label yang Anda butuhkan dan / atau inginkan, asalkan label tersebut tidak mengandung informasi tambahan yang tidak diberikan dalam input (mis. Anda tidak dapat mengharuskan bahwa node dalam siklus adalah dilabeli dengan bilangan bulat, dan simpul lainnya diberi label dengan string alfabet).
- Siklus adalah urutan node yang semuanya terhubung, dan tidak ada simpul yang diulang, selain simpul yang merupakan awal dan akhir siklus (
[1, 2, 3, 1]
adalah siklus, tetapi[1, 2, 3, 2, 1]
tidak). - Jika grafik asiklik, siklus terpanjang memiliki panjang 0, dan karenanya akan menghasilkan output kosong (mis. Daftar kosong, tidak ada output sama sekali).
- Mengulang simpul pertama di akhir daftar node dalam siklus adalah opsional (
[1, 2, 3, 1]
dan[1, 2, 3]
menunjukkan siklus yang sama). - Jika ada beberapa siklus dengan panjang yang sama, salah satu atau semuanya mungkin merupakan output.
- Builtin diperbolehkan, tetapi jika solusi Anda menggunakannya, Anda disarankan untuk memasukkan solusi alternatif yang tidak menggunakan builtin yang diremehkan (misalnya builtin yang menghasilkan semua siklus). Namun, solusi alternatif tidak akan dihitung sama sekali dengan skor Anda, sehingga sepenuhnya opsional.
Uji Kasus
Dalam kasus uji ini, input diberikan sebagai daftar tepi (di mana elemen pertama adalah simpul sumber dan elemen kedua adalah simpul tujuan), dan outputnya adalah daftar simpul tanpa pengulangan simpul pertama / terakhir.
[(0, 0), (0, 1)] -> [0]
[(0, 1), (1, 2)] -> []
[(0, 1), (1, 0)] -> [0, 1]
[(0, 1), (1, 2), (1, 3), (2, 4), (4, 5), (5, 1)] -> [1, 2, 4, 5]
[(0, 1), (0, 2), (1, 3), (2, 4), (3, 0), (4, 6), (6, 8), (8, 0)] -> [0, 2, 4, 6, 8]
[(0, 0), (0, 8), (0, 2), (0, 3), (0, 9), (1, 0), (1, 1), (1, 6), (1, 7), (1, 8), (1, 9), (2, 1), (2, 3), (2, 4), (2, 5), (3, 8), (3, 1), (3, 6), (3, 7), (4, 1), (4, 3), (4, 4), (4, 5), (4, 6), (4, 8), (5, 0), (5, 8), (5, 4), (6, 0), (6, 1), (6, 2), (6, 3), (6, 4), (6, 5), (6, 6), (6, 7), (6, 9), (7, 0), (7, 1), (7, 2), (7, 3), (7, 4), (7, 5), (7, 8), (7, 9), (8, 0), (8, 1), (8, 2), (8, 5), (8, 9), (9, 1), (9, 2), (9, 3), (9, 4), (9, 5), (9, 6)] -> [0, 9, 6, 7, 8, 2, 5, 4, 3, 1]
[(0, 0), (0, 2), (0, 4), (0, 5), (0, 7), (0, 9), (0, 11), (1, 2), (1, 4), (1, 5), (1, 8), (1, 9), (1, 10), (2, 0), (2, 1), (2, 3), (2, 4), (2, 5), (2, 6), (3, 0), (3, 1), (3, 5), (3, 6), (3, 7), (3, 8), (3, 9), (3, 11), (4, 1), (4, 3), (4, 7), (4, 8), (4, 9), (4, 10), (4, 11), (5, 0), (5, 4), (5, 6), (5, 7), (5, 8), (5, 11), (6, 0), (6, 8), (6, 10), (6, 3), (6, 9), (7, 8), (7, 9), (7, 2), (7, 4), (7, 5), (8, 8), (8, 9), (8, 2), (8, 4), (8, 7), (9, 0), (9, 1), (9, 2), (9, 3), (9, 6), (9, 10), (9, 11), (10, 8), (10, 3), (10, 5), (10, 6), (11, 2), (11, 4), (11, 5), (11, 9), (11, 10), (11, 11)] -> [0, 11, 10, 6, 9, 3, 8, 7, 5, 4, 1, 2]
code-golf
graph-theory
Mego
sumber
sumber
Jawaban:
Mathematica,
8058 byteMenyimpan 22 byte kekalahan berkat JungHwan Min
adalah karakter penggunaan pribadi tiga byte yangU+F3D5
mewakili\[DirectedEdge]
. Fungsi murni dengan argumen pertama#
diharapkan menjadi daftar tepi terarah. TemukanAll
panjang siklus paling banyakInfinity
diGraph@#
, kemudian menggantikan daftar kosong dengan daftar diri loop. Siklus direpresentasikan sebagai daftar tepi dan disortir menurut panjangnya, jadi kami mengambil siklus yang terakhir, lalu dari semua tepinya, kami mengambil argumen pertama sehingga kami mendapatkan daftar simpul dalam format output yang ditentukan.Jika hanya Mathematica memperlakukan loop sebagai siklus panjang
1
(AcyclicGraphQ @ CycleGraph[1, DirectedEdges -> True]
memberiTrue
, serius), maka kita bisa menyimpan26
byte lain :sumber
MaximalBy
karena hasilnyaFindCycle
sudah diurutkan berdasarkan panjang (elemen terakhir adalah yang terpanjang). Juga, argumen pertamaFindCycle
dapat berupa daftar\[DirectedEdge]
(bukan aGraph
). Plus, Anda dapat menggunakan 2-byte;;
(=1;;-1
) bukan 3-byteAll
dalamPart
untuk menyimpan byte. -22 bytes (58 bytes):(FindCycle[#,∞,All]/.{}->{Cases[#,v_v_]})[[-1,;;,1]]&
Haskell ,
157 154150 byteCobalah online!
Terima kasih @Laikoni dan @Zgrab karena telah menyelamatkan banyak byte!
Ini adalah program yang sangat tidak efisien:
Fungsi pertama
#
mengambil daftar jalurl
(daftar daftar angka) dan mencoba memperluas elemenl
dengan menambahkan setiap tepi yang mungkin (daftar panjang 2)g
untuk setiap elemenl
. Ini terjadi hanya jika elemenl
belum merupakan siklus dan jika node baru yang akan ditambahkan tidak sudah terkandung dalam elemenl
. Jika sudah menjadi siklus, kami tidak menambahkan apa pun selain menambahkannya ke daftar jalur baru, jika kami dapat memperluasnya, kami menambahkan jalur yang diperluas ke daftar baru, jika tidak, kami tidak menambahkannya ke daftar baru .Sekarang fungsi
h
berulang kali mencoba untuk memperpanjang jalur tersebut (dimulai dengan daftar tepi itu sendiri) sampai kita mencapai titik tetap, yaitu kita tidak dapat memperluas jalur apa pun lebih jauh. Pada titik ini kami hanya memiliki siklus dalam daftar kami. Maka itu hanya masalah memilih siklus terpanjang. Jelas sekali siklus muncul beberapa kali dalam daftar ini karena setiap kemungkinan rotasi siklus dari siklus adalah siklus.sumber
(p:q)<-l
.<$>
bukannyamap
harus menyimpan byte lain di((,)=<<length)<$>[]:
.d@(p:q)<-l
menghemat beberapa byte.d@(p:q)
ini benar-benar bagus, terima kasih telah menunjukkan padaku!Pyth, 20 byte
Suite uji
Mengambil daftar tepi, seperti pada contoh.
Penjelasan:
sumber
Bash + bsdutils, 129 byte
tsort melakukan semua pengangkatan berat, tetapi format outputnya agak unik dan tidak mendeteksi siklus panjang 1. Perhatikan bahwa ini tidak bekerja dengan GNU tsort.
Verifikasi
sumber
JavaScript (ES6),
173163156145139 byteDisimpan 5 byte berkat @Neil
Cuplikan tes
Tampilkan cuplikan kode
sumber
map
menghemat beberapa byte?.filter().map()
, jadi hampir pasti tidak. Switch menyelamatkan saya 10 byte (meskipun tidak sepenuhnya golf seperti sekarang)a.filter(z=>!e).map(z=>d)
Anda dapat menggunakana.map(z=>e?0:d)
.a+a?
:-)Haskell ,
109108 byteSolusi brute force: buat semua daftar tepi dengan panjang yang meningkat hingga panjang input, pertahankan yang merupakan siklus, kembalikan yang terakhir. Mengambil grafik dalam format
[(1,2),(2,3),(2,4),(4,1)]
. Cobalah online!Penjelasan
sumber
MATLAB,
291byteMengambil matriks adjecency di
A
mana tepi(i,j)
dilambangkan dengan1
inA(i,j)
, danA
nol di semua entri lainnya. Outputnya adalah daftar siklus terpanjang. Daftar ini kosong jika tidak ada siklus sama sekali, dan daftar termasuk awal dan titik akhir jika ada siklus. Itu menggunakan1
pengindeksan berbasis.Solusi ini tidak menggunakan fungsi bawaan yang terkait dengan grafik.
Sayangnya ini tidak berjalan di TryItOnline karena menggunakan fungsi dalam suatu fungsi, yang bersifat rekursif. Sedikit modifikasi memungkinkan Anda untuk mencobanya di octave-online.net .
Untuk kasus tes terakhir saya menemukan alternatif siklus terpanjang
[0 2 1 4 3 5 7 8 9 11 10 6 0]
(notasi ini menggunakan pengindeksan berbasis 0)Penjelasan
Pendekatan dasar di sini adalah bahwa kami melakukan BFS dari setiap node dan berhati-hati agar kami tidak mengunjungi salah satu dari intermediate node lagi kecuali node start. Dengan gagasan itu kami dapat mengumpulkan semua siklus yang mungkin, dan dengan mudah memilih yang terpanjang.
sumber