Code golf: Memecahkan masalah logika Knights dan Knaves dengan menguraikan bahasa Inggris

16

Latar Belakang

Ada dua orang, Bill dan John. Salah satunya adalah seorang ksatria, yang selalu mengatakan yang sebenarnya, dan yang lainnya adalah seorang ksatria, yang selalu mengatakan kebohongan. Anda tidak tahu siapa ksatria dan siapa yang menjadi ksatria. Setiap orang kemudian mengatakan beberapa pernyataan tentang siapa yang menjadi knave dan siapa yang knight. Dengan menggunakan informasi ini, Anda harus sampai pada kesimpulan tentang siapa ksatria dan siapa yang menjadi ksatria.

Masalah logika Ksatria dan Knaves didasarkan pada aljabar Booleen. Kata-kata yang dikatakan seseorang membentuk masalah kepuasan Booleen. Pernyataan knave harus selalu salah dan pernyataan knight lain harus selalu benar.

John berkata, "Aku adalah seorang yang baik dan Bill juga seorang yang baik". Jika John adalah ksatria, maka pernyataan ini akan salah, jadi dia tidak bisa menjadi ksatria. Jika dia adalah orang yang baik dan Bill adalah ksatria, pernyataan ini akan tetap salah, bahkan mengira bagian pertama itu benar. Jadi, John adalah penjahatnya.

Tantangan

Tantangan Anda adalah menulis program sesingkat mungkin yang akan mengambil daftar pernyataan yang dibuat oleh setiap orang dan akan mencari tahu siapa yang menjadi knave dan siapa yang knight. Ada banyak detail yang harus dibahas, sehingga masalah ini dijelaskan dalam tiga bagian.

Memasukkan

Input akan terdiri dari dua baris diikuti oleh baris baru. Setiap baris akan memberikan nama salah satu karakter, diikuti oleh tanda titik dua, diikuti oleh beberapa kalimat yang diucapkan oleh orang itu. Jika satu orang adalah ksatria, maka semua kalimatnya akan benar, dan semua kalimat tentang knave itu salah. Huruf pertama dari sebuah kalimat akan selalu ditulis dengan huruf besar, dan setiap kalimat akan berakhir dengan tanda titik. Berikut ini sebuah contoh:

Joe: Both I am a knight and neither Steve is a knave nor I am a knave.
Steve: Joe is a knave. Either Joe is a knight or I am a knight.

Parsing

Setiap kalimat terdiri dari setidaknya satu klausa. Setiap klausa berisi salah satu dari beberapa hal (mudah-mudahan Anda dapat memahami notasi saya):

both [clause] and [clause]
either [clause] or [clause]
neither [clause] nor [clause]
[I am | (other person's name) is] a [knight | knave]

Ini tidak beragama karena dapat dipahami dengan cara yang mirip dengan notasi Polandia. Ini adalah contoh kalimat:

Both I am a knight and neither Steve is a knave nor I am a knave.

Terjemahan ke aljabar Booleen sangat mudah. Pernyataan "keduanya" adalah AND, pernyataan "salah" adalah XOR, dan pernyataan "tidak" adalah NOR.

(I am a knight) AND ((Steve is a knave) NOR (I am a knave))

Keluaran

Output akan terdiri dari dua baris. Setiap baris terdiri dari nama seseorang (dalam urutan) dan kemudian mengatakan apakah dia adalah ksatria atau knave. Akan selalu ada satu kesatria dan satu kesatria. Berikut ini adalah output untuk contoh di atas:

Joe is the knave.
Steve is the knight.

Jika masalahnya tidak dapat dipecahkan (Anda tidak dapat mengatakan siapa itu apa, atau tidak ada solusi), maka program Anda dapat melakukan apa saja KECUALI menghasilkan output yang valid.

Lebih banyak contoh

Memasukkan

Sir Lancelot: Either both I am a knight and Merlin is a knave or both I am a knave and Merlin is a knight.
Merlin: Either both I am a knight and Sir Lancelot is a knight or both I am a knave and Sir Lancelot is a knave.

Keluaran

Sir Lancelot is the knight.
Merlin is the knave.

Memasukkan

David: Neither I am a knave nor Patrick is a knight. Either I am a knight or Patrick is a knave.
Patrick: Either I am a knight or both I am a knight and David is a knight.

Keluaran

David is the knave.
Patrick is the knight.

Memasukkan

Lizard: I am a knight.
Spock: I am a knave.

Satu kemungkinan keluaran

Rock Paper Scissors

Aturan, Regulasi dan Catatan

  1. Aturan golf kode standar berlaku
  2. Program Anda harus terdiri dari ASCII yang dapat dicetak
  3. Semua input dan output akan berasal dari STDIN dan STDOUT
PhiNotPi
sumber
Bagaimana dengan sensitivitas kasus? Deskripsi sintaks Anda adalah huruf kecil, contoh Anda adalah huruf besar. Apakah ketidakpekaan kasus merupakan persyaratan?
ugoren
Huruf pertama dari setiap kalimat akan dikapitalisasi, tetapi selain itu hanya nama yang akan dikapitalisasi. Apa masalah spesifik yang Anda lihat?
PhiNotPi
Karena Anda menggunakan kapitalisasi bahasa Inggris yang benar, huruf pertama dalam keduanya / salah satu / keduanya tidak tergantung pada konteksnya. Saya kira menjadi case-insensitive adalah cara mudah untuk menghadapinya.
ugoren

Jawaban:

6

Python, 491 karakter

Bekerja dengan mengonversi setiap baris ke ekspresi Python, dan meluaskannya.
Knave dan knight dievaluasi sebagai 0 dan 1. Untuk dua orang, kami mencoba kedua opsi.
Misalnya, Joe: Steve is a knavemenjadi Joe==(Steve==knave). Dengan cara ini, jika itu Joeadalah pertanda, hasilnya benar hanya jika dia berbohong.
Anda mendapatkan kesalahan buruk saat itu tidak mungkin atau belum diputuskan. Jika tidak mungkin, r[0]adalah kesalahan indeks, karena rkosong. Jika tidak diputuskan, menyatukan r[1:]ke daftar string menyebabkan masalah.

import sys
def p():
    a=s.pop(0)
    try:return{"both":"(%s*%s)","either":"(%s|%s)","neither":"(1-(%s|%s))"}[a.lower()]%(p(),p())
    except KeyError:r=s[2];del s[:4];return"(%s==%s)"%((a,m)[a=="I"],r)
x=[];w=[]
for l in sys.stdin:
    m,l=l.split(":");w+=[m]
    for s in l.split("."):
        s=s.split()
        while s:x+=["%s==%s"%(m,p())]
k=("knave","knight")
r=[a for a in[{w[0]:z,w[1]:1-z}for z in(0,1)]if all(eval(l,{k[0]:0,k[1]:1},a)for l in x)]
print"\n".join(x+" is the "+k[r[0][x]]+"."for x in w+r[1:])
ugoren
sumber
3

Ruby, 352 karakter

Solusinya menjadi cukup lama sehingga mungkin masih ada tempat untuk bermain golf. Ini membutuhkan input untuk dibentuk dengan baik (karena semua contoh di atas adalah - tetapi jangan mencoba untuk menyebut seseorang "Keduanya" ...).

q=->{gets.split /: |\.\s/}
C,*E=q[]
D,*F=q[]
r=->c,m{t=c.shift;t[1]?(x=r[c,m];c.shift;y=r[c,m];t[0]==?B?x&y :t[0]==?E?x^y :1-(x|y)):(c.shift(2);h=c.shift[2]==?I?m : 1-m;t==?I?h :1-h)}
s=->u,v,b{u.map{|c|r[c.gsub(v,?J).upcase.split,b]==b}.all?}
t=->b{s[E,D,b]&&s[F,C,1-b]}
u=->v,b{v+" is the kn#{b ?:ight: :ave}."}
puts t[1]^t[0]&&u[C,t[1]]+$/+u[D,t[0]]
Howard
sumber
Anda tampaknya mengabaikan periode dalam output, tetapi sepertinya perbaikan dua karakter.
PhiNotPi
1
@PhiNotPi Selesai. Adalah perbaikan nol karakter ...
Howard
0

Perl - 483 byte

(($a,$b),($c,$d))=map{split':'}@ARGV;$h='y';$i='x';$s=' is the kn';$g='ight.';$v='ave.';for($b,$d){$_.=' 1';s/ am a | is a /==/g;s/knight/1)/g;s/knave/0)/g;s/I=/(\$$i=/g;s/($a|$c)=/(\$$h=/g;s/([^.]+)\./($1)and/g;s/ or / xor /g;s/ nor / or /g;while(s/(?<= )(\w+ \((?:[^()]+|(?1))\) \w+ \((?:[^()]+|(?1))\))/($1)/g){}s/neither/!/gi;s/both|either//gi;$h=$i++}$x=0;$y=1;$k=!eval($b)&&eval($d);$x=$y--;$n=!eval($d)&&eval($b);print"$a$s$v
$c$s$g"if($k&&!$n);print"$a$s$g
$c$s$v"if($n&&!$k)

Mirip dengan solusi Python. Ini mengurangi kalimat ke kode Perl dan kemudian evals mereka. Ia dapat mencetak keluaran yang hampir valid jika inputnya aneh tetapi tidak mencetak apa pun jika itu tidak dapat dipastikan. Input yang terbentuk dengan baik berfungsi seperti yang diharapkan. Kalimat-kalimat dilewatkan pada baris perintah di dalam tanda kutip dan tidak ada bendera khusus yang diperlukan.

CJ Dennis
sumber