Perhatikan ini adalah pertanyaan yang terutama berfokus pada struktur data
pengantar
Bacefook ingin orang lebih ramah! Karena itu, mereka menerapkan sistem baru untuk menyarankan teman! Tugas Anda adalah membantu Bacefook untuk mengimplementasikan sistem saran baru mereka.
Spesifikasi:
Program Anda harus REPL (lingkaran baca-eval-print) mendukung 3 jenis perintah: FRIEND
, SUGGEST
dan KNOW
.
FRIEND X Y
- Menentukan itu X
dan Y
berteman di jejaring sosial.
Jika X berteman dengan Y, maka Y berteman dengan X
Bisa, tetapi tidak harus memiliki output
X selalu berteman dengan X
KNOW X Y
- Keluarkan nilai kebenaran jika X dan Y berteman, falsy sebaliknya
KNOW X X
akan selalu menghasilkan nilai yang benar
SUGGEST X Y
- Keluarkan nilai yang benar jika X dan Y harus menjadi teman, jika tidak sebaliknya. X dan Y harus berteman jika:
X dan Y bukan teman
X dan Y memiliki setidaknya 1 teman yang sama
Anda diizinkan untuk mengganti FRIEND
, SUGGEST
dan KNOW
dengan string Anda sendiri, tetapi Anda harus menyebutkan string apa yang telah Anda ganti dengan setiap perintah.
Program Anda dapat menerima input / menghasilkan output dengan cara apa pun yang diinginkan, asalkan cukup mudah untuk mengenali cara kerjanya.
Jumlah orang di jejaring sosial N
adalah antara 1 dan 100.000, tetapi mungkin ada sejumlah "tautan pertemanan" (tepian).
Jika Anda belum menyadarinya, ini adalah masalah pencarian grafik. Struktur data (yang kemungkinan) paling mudah (dan mungkin paling cepat) untuk mengimplementasikannya adalah matriks adjacency.
Uji kasus
FRIEND A B
FRIEND A C
FRIEND B D
SUGGEST A B -> Falsy, as they are friends
SUGGEST A D -> Truthy, as they share B as a common friend
SUGGEST C D -> Falsy, they do not share a common friend
KNOW D B -> Truthy, they are friends
KNOW B C -> Falsy, not friends
=============
FRIEND Tom Tim
KNOW Tom Tim -> Truthy
KNOW Tim Tom -> Truthy
KNOW Tom Kit -> Falsy
=============
KNOW Tim Kit -> Falsy
FRIEND Tim Tom
KNOW Tim Kit -> Falsy
FRIEND Tom Kit
SUGGEST Tim Kit -> Truthy
=============
FRIEND X Y
SUGGEST X Y -> Falsy since X is friends with X
Berikut beberapa kasus uji lagi dalam bentuk gambar
Kondisi menang
Ini kode-golf , kode terpendek menang!
{A, B, C, D}
?SUGGEST UK EU
.Jawaban:
SWI-Prolog,
624741 byteProlog tidak terlalu sering berguna, tetapi ketika itu hanya indah. Kami akan gunakan
a+b
untuk memberi tahu yanga
berteman denganb
,a*b
yanga
tahub
dana?b
yangb
harus disarankana
atau tidak. Baris pertama hanya mengatakan ituX*Y
benar jika salahX+Y
,Y+X
atauX == Y
benar. Ini mengimplementasikan simetri mengenal satu sama lain. Menanyakan apakah harus ada saran sangat sederhana. Kami hanya meminta jika adaZ
sehinggaX*Y
adalah salah danX*Z
danY*Z
benar. Persis seperti yang dijelaskan dalam tantangan.Jika Anda menyimpan ini sebagai file (mis.
friends.pl
) Dan membuka SWI-Prolog dengan file ini (prolog -l friends.pl
), Anda akan dimasukkan ke dalam REPL.Anda dapat menegaskan pertemanan seperti ini:
Anda dapat memeriksa apakah orang tahu satu sama lain atau saran harus dibuat:
sumber
k(X,Y)
denganX*Y
dan sama denganf
dans
menggunakan operan yang berbeda. 21 byte jika saya sudah menghitung dengan benar.f
.PHP,
138 133129 bytePHP mengalahkan Mathematica - kejadian langka.
cetakan
1
untuk string yang benar dan kosong untuk kepalsuan. Jalankan dengan-nr
atau coba online .membutuhkan PHP 7.1 untuk penugasan daftar; nama pengguna adalah case sensitif dan harus mengecualikan
a
,b
,s
.kerusakan
$s
harus dipangkas karena termasuk karakter baris baru.array_intersect_key
harus dibisukan atau akan menghasilkan peringatan untuk kosong$$a
atau$$b
.+18+15 byte untuk semua nama pengguna: Ganti$$a
dengan$f[$a]
dan$$b
dengan$f[$b]
.sumber
CMD (Gelombang), 50 + 20 + 135 = 205 byte
TEMAN. CMD
TAHU. CMD
Cetakan
1
untuk teman, garis kosong untuk orang asing.SARAN.CMD
Cetakan
1
atau garis kosong. Saya pikir enam berturut-turut%
mungkin menjadi yang terbaik pribadi baru.sumber
Python 3,
122118 + 2 = 120 bytePenggunaannya persis sama dengan jawaban ovs.
sumber
Python 3,
163149143 + 2 = 145 byte-6 byte berkat @FelipeNardiBatista
Simpan ke file dan jalankan sebagai
python3 -i file.py
Gunakan
-
f("a", "b")
bukanFRIENDS a b
-
k("a", "b")
bukanKNOW a b
-
s("a", "b")
bukanSUGGEST a b
Output Falsey: 0, set (),
Output False Truthy: set non-kosong, Benar
Cobalah online
164 byte ketika tidak menggunakan interpreter python sebagai REPL:
Menggunakan
-
f
untukFRIEND
-
s
untukSUGGEST
- apa pun untuk
KNOW
Cobalah online
sumber
l.extend([(a,b),(b,a)])
, tidak bisakah Anda melakukannyal+=[(a,b),(b,a)]
? (Saya belum menguji ini)UnboundLocalError
. Ngomong-ngomong, jawaban yang bagus!bool()
daris
fungsi, dan menggunakan0
,{}
danFalse
sebagai Falsey danTrue
dan tidak kosongset
sebagai Kebenaran, Anda bisa menyimpan 6 byteMathematica, 164 byte
Mendefinisikan tiga fungsi utama
F
,S
danK
dengan perilaku yang diinginkan. Misalnya, urutan perintahadalah kasus uji terakhir dari gambar yang ditautkan dalam OP; yang
F
perintah tidak menghasilkan output (titik koma tunggal tampaknya harga kecil untuk membayar untuk ini), sementara enamS
danK
hasil perintahseperti yang diinginkan.
Setiap saat,
f
adalah daftar pasangan memerintahkan dari bentuk{A, B}
manaA
tahuB
, sedangkanp
adalah daftar orang-orang yang muncul dalam beberapa unsurf
. MemanggilF@{A, B}
menambahkan empat pasang memerintahkan{A, B}
,{B, A}
,{A, A}
, dan{B, B}
untukf
.Juga, setiap saat,
m
adalah matriks kedekatan dari grafik yang mendasarinya (seseorang berdekatan dengan diri mereka sendiri dan dengan semuaF
riends mereka ); baris dan kolom diindeks olehp
, dani
mengonversi seseorang ke nomor baris / kolom yang sesuai. Fungsi helpera
mengambil sebuah matriks dan dua orang sebagai input dan mencari entri dari matriks yang "koordinat" -nya adalah dua orang, mengembalikanTrue
jika angkanya positif danFalse
jika nol. (Dimungkinkan juga untuk menelepona
ketika salah satu dari orang-orang input belum dikenali — misalnya, membuat permintaan TAHU atau SUGGEST sebelum deklarasi TEMAN, atau bertanya tentang beberapa orang miskin yang tidak memiliki teman; ini melempar kesalahan, tetapi aturannya/._@__->0
memaksa output menjadiFalse
toh.)Memanggil
K[A, B]
karena itu mencari apakahm[A, B]
positif, yang mengimplementasikanK
kata kerja sekarang. Produk matriksm.m
adalah matriks panjang-2-jalur, yang berisi sejumlah cara untuk berpindah dari satu orang ke orang lain di sepanjang jalur panjang 2; ini memungkinkanS[A, B]
untuk mengimplementasikanS
kata kerja ugest, selama kita juga memeriksa dengan tangan (&&!K@##
) bahwa input orang belum mengenal satu sama lain.Fun fakta: gratis, implementasi ini memungkinkan kita untuk menyatakan geng teman-perintah
F@{A, B, C, D}
setara dengan semuaF@{A, B}
,F@{A, C}
,F@{A, D}
,F@{B, C}
,F@{B, D}
, danF@{C, D}
gabungan.sumber
Python 2 , 118 byte
Cobalah online!
Karena saya tidak dapat menemukan alat pengganti online untuk python 2, saya telah menambahkan TIO Nexus (dalam format REPL).
Permintaan opsi dan kemungkinan outputnya
0 untuk Diketahui - Tidak Ada
1 untuk Teman - Benar atau Salah
2 untuk Sarankan - Benar atau Salah
Contoh penggunaan dan contoh output dalam interpreter python repl.
sumber
GNU sed , 158 + 2 (rn flags) = 160 byte
Karena sed adalah bahasa berbasis regex, tidak ada tipe primitif, belum lagi struktur data abstrak. Data jaringan disimpan sebagai teks format bebas, dalam hal ini sebagai tautan teman yang berlebihan seperti
A-B;B-A;
dll, yang kemudian dicocokkan dengan berbagai pola regex.Cobalah online!
Secara desain, sed menjalankan seluruh skrip untuk setiap baris input. Saya merekomendasikan pengujian dalam mode interaktif, untuk melihat output dari suatu perintah segera setelah mengetik.
Penggunaan: tidak ada nilai true / falsy di sed, jadi konvensi keluaran yang saya gunakan dipinjam dari bash, di mana string yang tidak kosong dianggap sebagai kebenaran, dan string kosong sebagai falsy.
F X Y
untukFRIEND X Y
. Tidak memiliki output.K X Y
untukKNOW X Y
. Menghasilkan 'K' sebagai kebenaran, dan tidak ada yang palsu.S X Y
untukSUGGEST X Y
. Menghasilkan 'S' sebagai kebenaran, dan tidak ada yang palsu.Penjelasan:
sumber