Ini adalah salah satu dari beberapa tantangan yang tersisa untuk komunitas oleh Calvin Hobbies .
Ambil file "pohon keluarga yang menggambarkan" dengan garis-garis bentuk:
[ID] [mother ID] [father ID] [gender] [full name]
seperti ini yang menggambarkan silsilah keluarga pertama di http://en.wikipedia.org/wiki/Cousin :
1 ? ? M Adam
2 ? ? F Agatha
3 ? ? M Bill
4 2 1 F Betty
5 2 1 M Charles
6 ? ? F Corinda
7 3 4 M David
8 6 5 F Emma
Tulis sebuah program atau fungsi yang menggunakan nama file dan dua ID serta menampilkan bagaimana orang-orang itu berhubungan darah dalam istilah yang paling sederhana, menggunakan nama bahasa Inggris yang umum untuk relasi. Input mungkin melalui STDIN, ARGV atau argumen fungsi tetapi output harus ke STDOUT.
Catatan
- ID adalah bilangan bulat positif.
?
digunakan ketika garis keturunan tidak diketahui.- Asumsikan grafik akan terhubung dan tidak memiliki siklus.
- Anda tidak boleh berasumsi bahwa orang tua setiap orang terdaftar sebelum orang itu (sehingga ID orang tua seseorang bisa lebih besar daripada ID mereka sendiri).
- Asumsikan setiap orang adalah pria atau wanita dan setiap orang memiliki satu ibu dan satu ayah (dari jenis kelamin yang tepat), meskipun mereka mungkin tidak diketahui.
- Asumsikan nama itu unik.
- Nama dapat memiliki spasi di dalamnya.
Hubungan darah
Berikut definisi dari hubungan R menentukan apakah seseorang A adalah R atau orang B . Jika dua varian R yang tercantum, yang pertama adalah untuk perempuan A dan yang kedua untuk laki-laki A . Semua ini perlu diimplementasikan. Jika beberapa definisi cocok, yang lebih awal harus digunakan. Istilah dalam tanda kurung adalah istilah netral-gender, yang tidak perlu diterapkan tetapi akan digunakan kembali dalam definisi lebih lanjut. Dalam definisi yang melibatkan N dan M , asumsikan N> 1 dan M> 0 .
- anak perempuan / anak laki-laki: A mencantumkan B sebagai orang tua.
- ibu / ayah (orang tua): B mendaftar A sebagai orang tua.
- saudara perempuan / laki-laki (saudara kandung): A dan B mendaftar ibu dan ayah yang sama.
- setengah saudara perempuan / saudara laki-laki (saudara kandung): A dan B daftar ibu yang sama atau ayah yang sama.
- keponakan / keponakan: Sebuah daftar orang tua yang adalah saudara dari B .
- bibi / paman: B adalah keponakan atau keponakan A.
- cucu perempuan / cucu laki-laki (cucu): A mendaftar orangtua yang mencantumkan B sebagai orangtua mereka.
- nenek / kakek (kakek nenek): B adalah cucu A.
- besar-keponakan / besar-keponakan: A adalah cucu dari C yang merupakan saudara dari B .
- buyut / paman buyut: B adalah keponakan atau keponakan dari A.
- cicit / anak laki-laki (cicit ke-1): A adalah cucu dari C yang mendaftarkan B sebagai orang tua mereka.
- buyut / ayah (buyut ke-1): B adalah buyut ke-1 A.
- Cicit perempuan / anak laki-laki (cicit ke-N): A adalah cucu (N-1) C yang mendaftarkan B sebagai orang tua mereka.
- Nenek buyut / ayah (buyut ke-N): B adalah buyut ke-N dari A.
- N besar-keponakan / keponakan: A adalah (N-1) th besar-cucu dari C yang merupakan saudara dari B .
- N bibik / paman: B adalah A 's n besar-keponakan dari n besar-keponakan.
- Sepupu: Sebuah adalah cucu dari C yang merupakan kakek dari B .
- Sepupu n: A adalah (N-1) th cucu dari C yang merupakan (N-1) th kakek dari B .
- sepupu, M kali dihapus: A adalah cucu dari C yang merupakan kakek Mth dari B atau A adalah cucu Mth dari C yang merupakan kakek dari B .
- Sepupu N, M kali dihapus: A adalah cicit Pth dari C yang merupakan kakek buyut ke- B dari B , di mana
N = min(P,Q) + 1
danM = |P-Q|
.
Untuk Nth
, menulis 2nd
, 3rd
, 4th
, 5th
dll
Untuk M times
, menulis once
, twice
, thrice
, 4 times
, 5 times
dll
Contohnya
Asumsikan file berikut digunakan (Anda tidak harus bisa berurusan dengan banyak spasi, tapi saya menambahkannya untuk keterbacaan):
1 ? ? F Agatha
2 ? ? M Adam
3 ? ? F Betty
4 1 2 M Bertrand
5 1 2 F Charlotte
6 ? ? M Carl
7 ? ? F Daisy
8 3 4 M David
9 5 6 F Emma
10 ? ? M Edward
11 ? ? F Freya
12 7 8 M Fred
13 9 10 F Grace
14 ? ? M Gerald
15 ? ? F Hillary
16 11 12 M Herbert
17 13 14 F Jane
18 ? ? M James
19 15 16 F Kate
20 17 18 M Larry
21 ? 18 F Mary
Maka ID input harus dipetakan ke output sebagai berikut:
1 2 --> Agatha is not a blood relative to Adam.
8 3 --> David is the son of Betty.
9 13 --> Emma is the mother of Grace.
4 5 --> Bertrand is the brother of Charlotte.
9 4 --> Emma is the niece of Bertrand.
5 8 --> Charlotte is the aunt of David.
16 7 --> Herbert is the grandson of Daisy.
1 9 --> Agatha is the grandmother Emma.
12 5 --> Fred is the great-nephew of Charlotte.
4 13 --> Bertrand is the great-uncle of Grace.
16 3 --> Herbert is the great-grandson of Betty.
6 17 --> Carl is the great-grandfather of Jane.
19 2 --> Kate is the 3rd great-granddaughter of Adam.
1 17 --> Agatha is the 2nd great-grandmother of Jane.
20 4 --> Larry is the 3rd great-nephew of Bertrand.
5 16 --> Charlotte is the 2nd great-aunt of Herbert.
8 9 --> David is the cousin of Emma.
19 20 --> Kate is the 4th cousin of Larry.
16 9 --> Herbert is the cousin, twice removed, of Emma.
12 17 --> Fred is the 2nd cousin, once removed, of Jane.
21 20 --> Mary is the half-sister of Larry.
Saya menulisnya dengan tangan jadi beri tahu saya jika Anda menemukan kesalahan.
Seperangkat data pengujian lainnya (disediakan oleh Scott Leadley, setiap kesalahan adalah milik saya dan bukan milik Martin).
Pohon keluarga Ptolemeus
. Gambar ini menggambarkan; data di bawah ini berasal dari artikel Wikipedia " Dinasti Ptolemaic ".
1 ? ? F Berenice I of Egypt
2 ? ? M Ptolemy I Soter
41 1 2 F Arsinoe II of Egypt
3 1 2 M Ptolemy II Philadelphus
4 ? ? F Arsinoe I of Egypt
5 ? ? M Philip
6 4 3 M Ptolemy III Euergetes
7 1 5 F Magas of Cyrene
8 7 ? F Berenice II
9 8 6 M Ptolemy IV Philopator
10 8 6 F Arsinoe III of Egypt
11 10 9 M Ptolemy V Epiphanes
12 ? ? F Cleopatra I of Egypt
13 12 11 M Ptolemy VI Philometor
14 12 11 F Cleopatra II
15 12 11 M Ptolemy VIII Physcon
19 ? ? F Eirene
16 14 13 M Ptolemy VII Neos Philopator
17 14 13 F Cleopatra III
18 14 15 M Ptolemy Memphites
20 19 15 M Ptolemy Apion
21 17 15 F Cleopatra IV
22 17 15 M Ptolemy IX Lathyros
23 17 15 F Cleopatra Selene I
24 17 15 M Ptolemy X Alexander I
25 23 22 F Berenice III of Egypt
26 23 24 M Ptolemy XI Alexander II
27 21 22 M Ptolemy XII Auletes
28 25 24 F Cleopatra V of Egypt
29 28 27 F Cleopatra VI of Egypt
30 28 27 F Berenice IV of Egypt
31 28 27 M Ptolemy XIII Theos Philopator
32 28 27 F Cleopatra VII Thea Philopator
33 28 27 M Ptolemy XIV
34 28 27 F Arsinoe IV of Egypt
35 ? ? M Julius Caesar
37 32 35 M Ptolemy XV Caesarion
36 ? ? M Mark Anthony
38 32 36 M Alexander Helios
39 32 36 M Ptolemy XVI Philadelphus
40 32 36 F Cleopatra Selene II
sumber
Ruby -
189212901247Jalankan sebagai
ruby relation.rb ID1 ID2 relationship_file
.Versi ungolfed -
52513416 (pohon panggilan yang sama, hanya melakukan banyak kode lipat)Lulus rangkaian uji berikut:
sumber
Javascript, 2292
Saya yakin itu bisa bermain golf lebih jauh, semua yang saya lakukan adalah memasukkan versi tanpa ungolfed melalui minifier.
Anda dapat menjalankan versi yang tidak diklik di sini di jsFiddle . Berikut ini adalah output untuk contoh data:
sumber
Python 3: 1183
Nama file dan ID orang yang akan diuraikan dibaca dari input standar pada satu baris.
Bagian atas kode adalah definisi fungsi. Script mulai setengah jalan, dan pertama-tama berfungsi memproses input (mem-parsing file, kemudian menugaskan anak-anak ke orang tua mereka di lintasan kedua).
Setelah data diatur, kami memanggil
A
fungsi satu kali untuk memulai pencarian rekursif. Hasilnya mendefinisikan hubungan.Sisa kode ini didedikasikan untuk menggambarkan hubungan itu dalam bahasa Inggris. Saudara dan sepupu itu rumit (dan menggunakan garis panjang), sisanya cukup lurus ke depan.
Contoh dijalankan (baris kedua adalah input saya):
Fungsi dan kunci nama variabel:
f
: Nama file data keluarga dibaca.a
: Id dari orang yang memiliki hubungan yang kita namakan.b
: Id dari orang yang didefinisikan hubungannya dengan relatif.t
: Silsilah keluarga itu sendiri, sebagai pemetaan kamus dari id ke 5-tupel id ibu, id ayah, jenis kelamin, nama dan daftar anak-anak.g
: Nilai Boolean yang mencerminkan jenis kelamin seseoranga
. ItuTrue
jika mereka laki-laki.u
: Jumlah generasi darib
ke nenek moyanga
danb
(atau 0 jikab
yaitua
's nenek moyang).d
: Jumlah generasi daria
ke nenek moyanga
danb
(atau 0 jikaa
yaitub
's nenek moyang).D(i)
: Pencarian secara turunan dari orangi
ke oranga
. Kembalikan kedalamana
ditemukan di, atau Tidak ada jika tidak ditemukan.A(i)
: Pencariani
dani
keturunan secara rekursif, tetapi jika tidak ditemukani
, nenek moyang pencarian secara rekursif (dan keturunan mereka) juga. Mengembalikan 2-tupel, nilai siapa,u
dand
dijelaskan di atas. Jika suatu hubungan ditemukan melalui kedua orang tua, yang paling sedikit dengan langkah generasi (u+d
) lebih disukai. Jika seseoranga
tidak memiliki hubungan darah dengan seseorangi
,A(i)
kembalilahNone
.P(r)
: Mencetak string hasil yangr
ditandai oleh nama oranga
danb
.O(n)
: Mengembalikan string ordinal untuk nomor yang diberikann
. Hanya mendukung1 < n < 21
.G(n)
: Kembalikan string awalan yang setara dengann-1
"hebat" (mis."2nd great-"
Untuk n = 2`). Akan mengembalikan string kosong untuk n <= 1.GG(n)
: Mengembalikan string awalan dengan "Nth great-" dan "grand", yang sesuai untukn
generasi. Akan mengembalikan string kosong untuk n <= 1.Saya mengambil beberapa jalan pintas atas nama kode pendek yang dapat direvisi untuk kinerja yang lebih baik (atau sedikit lebih benar) pada silsilah besar. The
A
fungsi tidak membuat upaya untuk menghindari recursing pohon anak yang sudah dicari, yang membuatnya lambat dari yang diperlukan (meskipun mungkin masih cukup cepat untuk keluarga berukuran wajar). TheO
Fungsi tidak benar menangani ordinals lebih besar dari 20 (itu memagut sulit untuk mendapatkan semua11th
,21st
dan101st
benar, tapi di salah satu versi draft saya melakukannya dalam waktu sekitar 25 bytes tambahan). Kecuali jika Anda berurusan dengan keluarga yang sangat tua dan terkenal (misalnya beberapa keluarga kerajaan Eropa), saya tidak yakin saya akan mempercayai keakuratan silsilah yang kembali sejauh itu.Di sisi lain, saya juga telah melompati beberapa tempat di mana saya bisa mencukur beberapa byte. Sebagai contoh, saya bisa menyimpan 3 byte dengan mengganti nama
GG
menjadi satu karakter, tetapi mendasarkan nama itugreat-grand
nampak lebih berharga bagi saya.Saya percaya bahwa semua ruang putih dalam kode diperlukan, tetapi ada kemungkinan bahwa beberapa dapat dilewati dan saya baru saja melewatkannya (saya terus menemukan ruang liar dalam daftar argumen saat saya mengetik jawaban ini, tapi saya rasa saya ' sudah mendapatkan semuanya sekarang).
Karena pencocokan rekursif saya memerlukan aturan yang relatif sederhana untuk memilih hubungan mana jika ada lebih dari satu, saya tidak memberikan hasil yang diminta secara tepat dalam beberapa kasus tidak jelas yang melibatkan inses antar generasi. Misalnya, jika orang tersebut
a
adalahb
paman dan kakek, kode saya akan lebih suka hubungan kakek meskipun ada pertanyaan yang mengatakan bahwa hubungan paman harus lebih diutamakan.Berikut contoh dataset yang memaparkan masalah:
Saya menduga bahwa untuk sebagian besar program, hubungan antara Bob dan Claire atau antara Bob dan Danielle akan menimbulkan masalah. Mereka akan memanggil pasangan pertama saudara tiri daripada ayah / anak perempuan atau mereka akan menggambarkan pasangan yang terakhir sebagai kakek / cucu daripada paman / keponakan. Kode saya melakukan yang terakhir, dan saya tidak melihat cara yang masuk akal untuk mengubahnya untuk mendapatkan hasil yang diminta tanpa juga membuat pasangan pertama salah.
sumber
Suite uji. Masukkan ke t / relation.t dan jalankan "membuktikan" atau "perl t / relation.t". Saat ini mengasumsikan file program adalah "relation.rb".
Ini adalah wiki komunitas, jadi jangan ragu untuk menambahkan tes. Jika Anda mengubahnya, saya pikir cap waktu (atau bendera lain yang jelas) akan beres. Daftar keinginan:
sumber