Haruskah kita berteman?

30

Perhatikan ini adalah pertanyaan yang terutama berfokus pada

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, SUGGESTdan KNOW.

FRIEND X Y- Menentukan itu Xdan Yberteman 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, SUGGESTdan KNOWdengan 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 Nadalah 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 terpendek menang!

Thunda
sumber
Jadi misalnya, bisakah kita mulai dengan memasukkan daftar semua orang di jaringan, seperti {A, B, C, D}?
Greg Martin
2
Memiliki kasus uji dalam bentuk teks akan jauh lebih bermanfaat.
Greg Martin
1
Bisakah kita menghasilkan output setelah perintah FRIEND?
Ovs
7
SUGGEST UK EU.
WBT
1
@Thunda dalam Python, menggunakan REPL bawaan membutuhkan dua karakter tambahan dalam perintah. Haruskah bahasa seperti ini menambahkan byte ekstra ke panjang total program?
kuintopia

Jawaban:

44

SWI-Prolog, 62 47 41 byte

X*Y:-X+Y;Y+X;X==Y.
X?Y:-not(X*Y),X*Z,Y*Z.

Prolog tidak terlalu sering berguna, tetapi ketika itu hanya indah. Kami akan gunakan a+buntuk memberi tahu yang aberteman dengan b, a*byang atahu bdan a?byang bharus disarankan aatau tidak. Baris pertama hanya mengatakan itu X*Ybenar jika salah X+Y, Y+Xatau X == Ybenar. Ini mengimplementasikan simetri mengenal satu sama lain. Menanyakan apakah harus ada saran sangat sederhana. Kami hanya meminta jika ada Zsehingga X*Yadalah salah dan X*Zdan Y*Zbenar. 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:

assert('a' + 'b').
assert('a' + 'c').
assert('b' + 'd').

Anda dapat memeriksa apakah orang tahu satu sama lain atau saran harus dibuat:

'a'*'b'.
'a'?'d'.
orlp
sumber
Anda harus dapat menyimpan banyak byte yang diganti k(X,Y)dengan X*Ydan sama dengan fdan smenggunakan operan yang berbeda. 21 byte jika saya sudah menghitung dengan benar.
Emigna
Tidak yakin bagaimana mereka bekerja dengan menegaskan, jadi saya tidak yakin f.
Emigna
12
Kentut sepenuhnya melalui struktur data yang mendesain bagian dari pertanyaan. Luar biasa.
Thunda
@ Emigna Saya sudah menerapkannya, tetapi itu tidak menghemat sebanyak yang Anda hitung.
orlp
Saya mengujinya seperti ini pada 41 byte. Saya tidak punya REPL untuk mencobanya, jadi saya tidak tahu apakah itu bekerja berbeda di sana.
Emigna
15

PHP, 138 133 129 byte

PHP mengalahkan Mathematica - kejadian langka.

for(;$s=fgets(STDIN);$s>G?print$$a[$b]?$s<L:$s>L&&@array_intersect_key($$a,$$b):$$a[$b]=$$b[$a]=1)[,$a,$b]=explode(" ",trim($s));

cetakan 1untuk string yang benar dan kosong untuk kepalsuan. Jalankan dengan -nratau coba online .
membutuhkan PHP 7.1 untuk penugasan daftar; nama pengguna adalah case sensitif dan harus mengecualikan a, b, s.

kerusakan

for(;$s=fgets(STDIN);                       # loop through input
    $s>G                                        # 2. evaluate command
        ?print$$a[$b]
            # command KNOW: true if $$a[$b]
            ?$s<L
            # command SUGGEST: true if !$$a[$b] and array_intersect_key returns truthy
            :$s>L&&@array_intersect_key($$a,$$b)
        # command FRIEND: set keys in $$a and $$b
        :$$a[$b]=$$b[$a]=1
)
    [,$a,$b]=explode(" ",trim($s));             # 1. parse user names to $a and $b
  • $s harus dipangkas karena termasuk karakter baris baru.
  • array_intersect_keyharus dibisukan atau akan menghasilkan peringatan untuk kosong $$aatau $$b.
  • +18 +15 byte untuk semua nama pengguna: Ganti $$adengan $f[$a]dan $$bdengan $f[$b].
Titus
sumber
12

CMD (Gelombang), 50 + 20 + 135 = 205 byte

  • TEMAN. CMD

    @for %%f in (%1.%1 %1.%2 %2.%2 %2.%1)do @set %%f=1
    
  • TAHU. CMD

    @call echo(%%%1.%2%%
    

    Cetakan 1untuk teman, garis kosong untuk orang asing.

  • SARAN.CMD

    @call set k=0%%%1.%2%%
    @set k=1&if %k%==0 for /f "tokens=2 delims=.=" %%f in ('set %1.')do @call set k=%%k%%%%%%f.%2%%
    @echo(%k:~1,1%
    

    Cetakan 1atau garis kosong. Saya pikir enam berturut-turut %mungkin menjadi yang terbaik pribadi baru.

Neil
sumber
Itu gila, luar biasa. Solusi bagus
AdmBorkBork
6

Python 3, 122 118 + 2 = 120 byte

l={}
def f(*r):l[r]=l[r[::-1]]=1
k=lambda a,b:a==b or(a,b)in l
s=lambda a,b:1-k(a,b)and any(k(a,z)&k(b,z)for z,_ in l)

Penggunaannya persis sama dengan jawaban ovs.

orlp
sumber
1
Ini cukup jelas bagi saya, tetapi persyaratan mengatakan Anda harus menentukan cara menggunakan REPL Anda dan dengan perintah apa. Semoga bermanfaat bagi mereka yang tidak tahu python. (Kebetulan, ini persis metode yang saya akan gunakan.)
quintopia
6

Python 3, 163 149 143 + 2 = 145 byte

-6 byte berkat @FelipeNardiBatista

l=[]
def f(a,b):l.extend([(a,b),(b,a)])
k=lambda a,b:a==b or(a,b)in l
s=lambda a,b:k(a,b)-1and{c for c,d in l if d==a}&{c for c,d in l if d==b}

Simpan ke file dan jalankan sebagai python3 -i file.py
Gunakan
- f("a", "b")bukan FRIENDS a b
- k("a", "b")bukan KNOW 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:

f=[]
while 1:c,a,b=input().split();i=(a,b)in f;f+=c=="f"and[(a,b),(b,a)]or[(i+(a==b),-i+1and{c for c,d in f if d==a}&{c for c,d in f if d==b})];print(f[-1][c=="s"])

Menggunakan
- funtuk FRIEND
- suntuk SUGGEST
- apa pun untukKNOW

Cobalah online

ovs
sumber
Sarankan fungsi rusak untuk tautan kedua
Thunda
@Thunda memperbaikinya
ovs
Koreksi saya jika saya kehilangan sesuatu, tetapi bukannya l.extend([(a,b),(b,a)]), tidak bisakah Anda melakukannya l+=[(a,b),(b,a)]? (Saya belum menguji ini)
HyperNeutrino
Oh maaf, saya menyadari kesalahan saya, yang menyebabkan seorang UnboundLocalError. Ngomong-ngomong, jawaban yang bagus!
HyperNeutrino
jika Anda menghapus bool()dari sfungsi, dan menggunakan 0, {}dan Falsesebagai Falsey dan Truedan tidak kosong setsebagai Kebenaran, Anda bisa menyimpan 6 byte
Felipe Nardi Batista
5

Mathematica, 164 byte

f={}
p:=Union@@f
i=Position[p,#][[1,1]]&
m:=Outer[Boole@MemberQ[f,{##}]&,p,p]
a=(#[[i@#2,i@#3]]/._@__->0)>0&
F=(f=#~Tuples~2~Join~f;)&
K=m~a~##&
S=a[m.m,##]&&!K@##&

Mendefinisikan tiga fungsi utama F, Sdan Kdengan perilaku yang diinginkan. Misalnya, urutan perintah

F@{David, Bob}
F@{Bob, Alex}
F@{Alex, Kitty}
F@{Daniel, David}
F@{David, Kit}
S[David, Alex]
S[Bob, Kitty]
S[David, Kitty]
S[David, Bob]
K[David, Bob]
F@{Kit, Kitty}
S[David, Kitty]

adalah kasus uji terakhir dari gambar yang ditautkan dalam OP; yang Fperintah tidak menghasilkan output (titik koma tunggal tampaknya harga kecil untuk membayar untuk ini), sementara enam Sdan Khasil perintah

True
True
False
False
True
True

seperti yang diinginkan.

Setiap saat, fadalah daftar pasangan memerintahkan dari bentuk {A, B}mana Atahu B, sedangkan padalah daftar orang-orang yang muncul dalam beberapa unsur f. Memanggil F@{A, B}menambahkan empat pasang memerintahkan {A, B}, {B, A}, {A, A}, dan {B, B}untuk f.

Juga, setiap saat, madalah matriks kedekatan dari grafik yang mendasarinya (seseorang berdekatan dengan diri mereka sendiri dan dengan semua Friends mereka ); baris dan kolom diindeks oleh p, dan imengonversi seseorang ke nomor baris / kolom yang sesuai. Fungsi helper amengambil sebuah matriks dan dua orang sebagai input dan mencari entri dari matriks yang "koordinat" -nya adalah dua orang, mengembalikan Truejika angkanya positif dan Falsejika nol. (Dimungkinkan juga untuk menelepon aketika 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 /._@__->0memaksa output menjadi Falsetoh.)

Memanggil K[A, B]karena itu mencari apakah m[A, B]positif, yang mengimplementasikan Kkata kerja sekarang. Produk matriks m.madalah matriks panjang-2-jalur, yang berisi sejumlah cara untuk berpindah dari satu orang ke orang lain di sepanjang jalur panjang 2; ini memungkinkan S[A, B]untuk mengimplementasikan Skata 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 semua F@{A, B}, F@{A, C}, F@{A, D}, F@{B, C}, F@{B, D}, dan F@{C, D}gabungan.

Greg Martin
sumber
2

Python 2 , 118 byte

F=[]
def s(f,c):c=set(c);r=c in F;return F.append(c)if f%2 else not r^(4 in[len(x|c)for x in F])if f else 2>len(c)or r

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.

>>> F=[]
>>> def s(f,c):c=set(c);r=c in F;return F.append(c)if f%2 else not r^(4 in[len(x|c)for x in F])if f else 2>len(c)or r
...
>>> s(1,['A','B'])
>>> s(1,['A','C'])
>>> s(1,['B','D'])
>>> s(2,['A','B'])
False
>>> s(2,['A','D'])
True
>>> s(2,['C','D'])
False
>>> s(0,['D','B'])
True
>>> s(0,['D','C'])
False
Keerthana Prabhakaran
sumber
0

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.

G
/^F/{s:. (.+) (.+)\n:\1-\1;\1-\2;\2-\1;\2-\2;:;h}
/^K |^S /{s:(.) (.+) (.+)\n.*\2-\3.*:\1:;/^K$/p}
/^S /s:(.) (.+) (.+)\n.*(.+)-(\2.*\4-\3|\3.*\4-\2).*:\1:p

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 Yuntuk FRIEND X Y. Tidak memiliki output.
  • K X Yuntuk KNOW X Y. Menghasilkan 'K' sebagai kebenaran, dan tidak ada yang palsu.
  • S X Yuntuk SUGGEST X Y. Menghasilkan 'S' sebagai kebenaran, dan tidak ada yang palsu.

Penjelasan:

G
# append stored network data, if any, to the current input line
/^F/{
# if command is 'F' (FRIEND), for ex. 'F X Y'
   s:. (.+) (.+)\n:\1-\1;\1-\2;\2-\1;\2-\2;:
   # generate friend links, for ex. 'X-X;X-Y;Y-X;Y-Y'
   h
   # store updated network data
}
/^K |^S /{
# if command is either 'K' (KNOW) or 'S' (SUGGEST), for ex. 'K X Y'
   s:(.) (.+) (.+)\n.*\2-\3.*:\1:
   # search friend link 'X-Y'. If found, delete pattern except the command letter.
   /^K$/p
   # if only letter K left, print it (command is 'K', 'X' and 'Y' are friends)
}
/^S /
# if command is 'S', for ex. 'S X Y', but 'X' and 'Y' aren't friends
   s:(.) (.+) (.+)\n.*(.+)-(\2.*\4-\3|\3.*\4-\2).*:\1:p
   # search if 'X' and 'Y' have a friend in common (for ex. 'C'), and if so print
   #letter S. The search is for ex. 'C-X.*C-Y' and 'C-Y.*C-X'.
seshoumara
sumber