Apakah dadu ini tidak transitif?

31

Dadu nontransitif adalah mainan kecil yang bagus yang menentang intuisi kita dalam teori probabilitas. Kami membutuhkan beberapa definisi untuk tantangan ini:

Pertimbangkan dua dadu A dan B yang dilemparkan sekaligus. Kami mengatakan bahwa A mengalahkan B jika probabilitas A menunjukkan jumlah yang lebih besar daripada B benar-benar lebih besar dari probabilitas B yang menunjukkan jumlah yang lebih besar daripada A .

Sekarang mempertimbangkan satu set dari tiga dadu, dengan label A , B , C . Seperangkat dadu semacam itu disebut nontransitif jika

  • baik A mengalahkan B , B mengalahkan C dan C mengalahkan A
  • atau C mengalahkan B , B mengalahkan A dan A mengalahkan C .

Sebagai salah satu contoh favorit saya, pertimbangkan dadu Grime , yang memiliki sisi berikut:

A: 3 3 3 3 3 6
B: 2 2 2 5 5 5
C: 1 4 4 4 4 4

Menariknya, rata-rata setiap dadu adalah 3,5, sama seperti dadu biasa.

Seseorang dapat menunjukkan bahwa:

  • A mengalahkan B dengan probabilitas 7/12.
  • B mengalahkan C dengan probabilitas 7/12.
  • C mengalahkan A dengan probabilitas 25/36.

Sekarang dadu khusus ini bahkan lebih aneh. Jika kita menggulung masing-masing dadu dua kali dan menjumlahkan hasilnya, urutan ketukan yang dibalik:

  • B mengalahkan A dengan probabilitas 85/144.
  • C ketukan B dengan probabilitas 85/144.
  • Sebuah mengalahkan C dengan probabilitas 671/1296.

Mari kita memanggil satu set dadu dengan properti ini Grime-nontransitive .

Di sisi lain, jika dadu mempertahankan siklus aslinya saat menggunakan dua lemparan, kami menyebutnya sangat tidak transitif . (Jika tidak ada siklus sama sekali untuk dua lemparan, kami cukup menyebutnya tidak transitif .)

Tantangan

Mengingat tiga dadu bersisi enam, menentukan sifat-sifat di atas set ini memiliki, dan output salah satu string berikut: none, nontransitive, Grime-nontransitive, strongly nontransitive.

Anda dapat menulis program atau fungsi, mengambil input melalui STDIN, argumen baris perintah, prompt atau argumen fungsi, dan menulis hasilnya ke STDOUT atau mengembalikannya sebagai string.

Anda dapat mengasumsikan bahwa semua pihak adalah bilangan bulat non-negatif. Anda tidak dapat mengasumsikan bahwa sisi atau dadu berada dalam urutan tertentu. Anda dapat mengambil input dalam format string atau daftar yang mudah digunakan.

Ini adalah kode golf, jadi jawaban tersingkat (dalam byte) menang.

Uji Kasus

none
1 2 3 4 5 6, 6 5 4 3 2 1, 1 3 5 2 4 6
1 1 1 6 6 6, 4 4 4 5 5 5, 5 5 5 5 5 5
1 1 2 5 6 6, 2 2 3 4 4 6, 2 3 3 4 4 5
0 1 2 3 4 5, 1 1 2 3 3 5, 1 2 2 2 3 5
3 13 5 7 13 7, 5 7 11 5 7 13, 5 9 13 5 7 9

nontransitive
1 2 2 4 6 6, 1 2 3 5 5 5, 2 3 4 4 4 4
1 4 4 4 4 4, 2 2 2 4 5 6, 2 3 3 3 5 5
1 2 1 6 5 6, 3 1 3 6 2 6, 2 4 2 4 4 5
3 4 6 6 7 7, 4 4 4 7 7 7, 5 5 5 5 6 7
2 5 11 11 14 14, 5 5 5 14 14 14, 8 8 8 8 8 17

Grime-nontransitive
3 3 3 3 3 6, 2 2 2 5 5 5, 1 4 4 4 4 4
1 1 4 5 5 5, 2 2 2 3 6 6, 3 3 3 4 4 4
2 1 4 6 4 4, 2 4 5 2 3 5, 3 3 6 3 3 3
11 11 13 15 15 16, 12 12 12 13 16 16, 13 13 13 14 14 14
4 4 7 16 19 19, 4 7 13 13 13 19, 4 10 10 10 16 19

strongly nontransitive
2 2 2 5 5 5, 2 3 3 3 5 5, 1 1 4 5 5 5
2 2 2 3 6 6, 2 2 2 5 5 5, 2 2 4 4 4 5
1 5 1 3 6 5, 6 6 4 2 2 1, 5 3 4 3 4 2
0 0 2 4 4 5, 0 1 1 3 5 5, 1 1 2 3 4 4
1 1 9 17 17 21, 1 5 5 13 21 21, 5 5 13 13 13 17

Jika Anda ingin menguji kode Anda bahkan lebih teliti, Peter Taylor cukup baik untuk menulis implementasi referensi, yang mengklasifikasikan semua ~ 5000 set dadu dengan sisi 1 hingga 6 dan rata-rata 3,5. Tautan pastebin

Martin Ender
sumber
Saya benar-benar lupa tentang dadu non-transitif. Terima kasih :)
npst
Apakah contoh nontransitif pertama benar? 1 2 2 4 6 6, 1 2 3 5 5 5, 2 3 4 4 4 4Saya mendapatkan A <B 17/36, B> C 19/36, C <A 16/36.
Tobia
@Tobia Anda lupa bahwa undian dimungkinkan. Anda juga perlu mengetahui seberapa sering masing-masing dadu kalah melawan yang lain, dan periksa apakah itu kurang dari probabilitas menang: Ya A menang melawan B dengan 17/36, tetapi A kalah melawan B dengan hanya 16/36, jadi A mengalahkan B Demikian juga, C menang melawan A dengan 16/36 seperti yang Anda katakan, tetapi C kalah melawan A dengan hanya 14/36, jadi C mengalahkan A.
Martin Ender

Jawaban:

5

Dyalog APL, 107 100 byte

{({+/×+/¨,¨×⍵∘.-¨1⌽⍵}{3≠|a←⍺⍺⍵:1⋄a=b←⍺⍺∘.+⍨¨⍵:2⋄3+a=-b}⍵)⊃(⊂'none'),'strongly '⍬'Grime-',¨⊂'nontransitive'}

{T←{+/×+/¨∊¨×⍵∘.-¨1⌽⍵}⋄3≠|S←T⍵:'none'⋄N←'nontransitive'⋄S=D←T∘.+⍨¨⍵:'strongly ',N⋄S=-D:'Grime-',N⋄N}

(Terima kasih @Tobia untuk solusi yang lebih sederhana, lebih pendek, dan lebih baik ini)

Dasar-dasar:

  • tugas

  • pemisah pernyataan

  • {} bentuk lambda

  • ⍺⍵ argumen kiri dan kanan

  • A:Bpenjaga ("jika Akemudian kembali B")

Tadalah fungsi yang mengembalikan 3 jika A mengalahkan B, B mengalahkan C, dan C mengalahkan A; -3 jika yang terjadi adalah sebaliknya; dan sesuatu peralihan sebaliknya. Secara terperinci:

  • 1⌽⍵adalah satu-rotasi dari . Jika ABC, rotasi adalah BCA.

  • ∘.-menghitung tabel pengurangan antara dua vektor ( 1 2...10 ∘.× 1 2...10akan menjadi tabel perkalian yang kita tahu dari sekolah). Kami menerapkan ini di antara setiap ( ¨) item dan item terkait di 1⌽⍵.

  • × signum dari semua angka dalam tabel pengurangan

  • ∊¨ ratakan setiap meja

  • +/¨dan jumlah itu. Kami sekarang memiliki tiga angka yang mewakili saldo: jumlah kemenangan dikurangi kekalahan untuk masing-masing A vs B, B vs C, C vs A.

  • × signum dari mereka

  • +/ jumlah

Kemudian menangani kasus-kasus secara bergantian:

  • 3≠|S←T⍵:'none'jika T⍵nilai absolut bukan 3, kembalikan 'tidak ada'

  • N←'nontransitive' kita akan membutuhkan kata ini banyak

  • S=D←T∘.+⍨¨⍵:'strongly ',Nmenghitung Tpasangan dadu ( ∘.+⍨¨⍵← → ⍵((∘.+)¨)⍵) dan mengembalikan "sangat ..." jika hubungan yang sama di antara ABC masih berlaku

  • S=-D:'Grime-',N ⍝ "Grime" jika hubungan berada di arah yang berlawanan

  • N jika semuanya gagal, cukup "tidak transitif"

ngn
sumber
1
Anda mengalahkan saya untuk itu! Saya sedang mengerjakan masalah ini 3 hari yang lalu, tetapi kemudian saya berhenti menulis jawaban saya. Lagi pula, ini mirip dengan milik Anda, jadi saya akan mempostingnya di sini. Ini sedikit lebih pendek di 100 karakter:{T←{+/×+/¨∊¨×⍵∘.-¨1⌽⍵}⋄3≠|S←T⍵:'none'⋄N←'nontransitive'⋄S=D←T∘.+⍨¨⍵:'strongly ',N⋄S=-D:'Grime-',N⋄N}
Tobia
@ MartinBüttner: Istilah yang benar dalam judul adalah "karakter", karena jumlah byte akan bervariasi tergantung pada charset yang digunakan untuk menyandikan simbol APL. Secara tradisional mereka hanya dikodekan di bagian atas byte 8-bit, setelah ASCII. Saat ini kami menggunakan UTF-8, tetapi rangkaian karakter lama masih berguna ... terutama untuk mengurangi jumlah byte ke jumlah karakter saat bermain golf!
Tobia
@Tobia Dalam kode golf kartu truf lebih pendek sebelumnya, jadi Anda menang! Saya tidak terlalu mengenal etiket golf, tetapi saya pikir Anda harus mempostingnya sebagai jawaban terpisah karena ini sangat berbeda dan Anda tiba secara mandiri.
ngn
@Tobia Saya lebih suka untuk menghitung dalam karakter juga, tetapi jika pengkodean klasik tersirat, maka byte = karakter, jadi mungkin itu tidak terlalu penting apa yang kita sebut ...
ngn
@Tobia Yah tidak ada gunanya untuk memasok jumlah karakter dalam sebuah tantangan yang mendapat skor dari byte. Namun, tidak ada yang pernah mengatakan kami mencetak dalam UTF-8 byte. Sebenarnya tag wiki secara eksplisit mengatakan bahwa pengkodean yang ada dapat digunakan untuk karakter di luar rentang ASCII. Dan APL memang memiliki codepage sendiri sehingga seluruh rangkaian karakter sesuai dalam satu byte. Kebijakan tentang PPCG adalah menggunakan codepage ini untuk menghitung APL - tidak adil untuk menghukum APL karena lebih tua dari ASCII.
Martin Ender
13

Python 2, 269

Berikut adalah ekspresi kecil yang menyenangkan yang mengevaluasi fungsi. Ia menerima tiga daftar bilangan bulat. Lewati semua kasus uji.

lambda A,B,C,w=lambda A,B:cmp(sum(cmp(a,b)for a in A for b in B),0),x=lambda A,B:cmp(sum(cmp(a+c,b+d)for a in A for b in B for c in A for d in B),0): (w(A,B)==w(B,C)==w(C,A)!=0)*((x(A,B)==x(B,C)==x(C,A))*["","strongly ","Grime-"][x(A,B)*w(A,B)]+"nontransitive")or"none"
feersum
sumber
2

J - 311 257 byte

Pembaruan (13 Jan 2015):

g=:4 :'(+/,x>/y)>+/,y>/x'
h=:4 :'(,+/~x)g,+/~y'
f=: 3 :0
'a b c'=:y
if. (b g a)*(c g b)*a g c do.
a=.2{y
c=.0{y
end.
'none'([`]@.((a g b)*(b g c)*c g a))((''([`]@.((b h a)*(c h b)*a h c))'Grime-')([`]@.((a h b)*(b h c)*c h a))'strongly '),'nontransitive'
)

Penjelasan: Menggunakan Gerunds, sederhanakan if.s ke @.s.

Versi yang lebih lama:

Pertama coba di kedua coding di J dan juga golf.

g=:4 :'(+/,x>/y)>+/,y>/x'
h=:4 :'(,+/~x)g,+/~y'
f=: 3 :0
'a b c'=:y
if. (b g a)*(c g b)*a g c do.
a=.2{y
c=.0{y
end.
if. (a g b)*(b g c)*c g a do.
if. (a h b)*(b h c)*c h a do.
'strongly nontransitive'
elseif. (b h a)*(c h b)*a h c do.
'Grime-nontransitive'
elseif. do.
'nontransitive'
end.
else.
'none'
end.
)

Jalankan menggunakan sintaksis yang mirip dengan berikut (spasi ekstra untuk kejelasan):

f 3 6 $          1 1 9 17 17 21, 1 5 5 13 21 21, 5 5 13 13 13 17

Penjelasan:

gdidefinisikan sebagai diad yang mengambil dua larik yang memberitahu jika dadu pertama mengalahkan dadu kedua
hdidefinisikan sebagai diad yang mengambil dua larik yang memberitahu jika melempar dua kali dan menjumlahkan, apakah dadu pertama mengalahkan kedua
f adalah monad yang mengambil tabel dan mengembalikan string dengan jawaban benar

Sunting: Perbaiki kesalahan dalam kondisi Grime-nontransitive (ganti ,dengan *)

Jay Bosamiya
sumber
Saya ingin ada saran untuk perbaikan. :)
Jay Bosamiya
@ MartinBüttner, saya awalnya mencobanya, tetapi tidak tahu bagaimana menggabungkan beberapa baris (atau kalimat, seperti yang dikenal dalam J) tanpa menambah panjang kode lebih banyak ... belajar tentang "gerunds" membuat saya membuat banyak kalimat menjadi satu yang akhirnya memperpendek kode juga ...
Jay Bosamiya
1

Pyth 129 133

Lmsd^b2Msmsm>bkGHDPNK-ghNeNgeNhNR?^tZ<KZKZAGHmsdCm,PkP,yhkyekm,@Qb@QhbUQ?"none"|!G%G3s[*!+GH"Grime-"*qGH"strongly ""nontransitive

Cobalah di sini , atau setidaknya Anda bisa, tetapi secara online evalsepertinya tidak suka daftar daftar :( Jika Anda ingin mencobanya di sana, secara manual simpan daftar 3 dadu ke dalam variabel yang tidak digunakan oleh program dan kemudian ganti semua contoh Qdengan variabel itu. Inisialisasi sampel:

J[[3 3 3 3 3 6)[2 2 2 5 5 5)[1 4 4 4 4 4))

Ini melewati semua kasus uji Martin, saya belum hati melewati semua kasus Peter: P

Penjelasan (ini akan menjadi doozy)

Lmsd^b2

Cukup sederhana, membuat fungsi yyang mengembalikan jumlah dari setiap pasangan nilai Cartesian dalam iterable. Setara dengan: def y(b):return map(lambda d:sum(d),product(b,repeats=2)). Ini digunakan untuk membuat banyak sisi cetakan yang mensimulasikan melempar mati biasa dua kali.

Msmsm>bkGH

Mendefinisikan fungsi g2 argumen yang mengembalikan berapa kali sebuah die mengalahkan yang lain. Setara dengan def g(G,H):return sum(map(lambda k:sum(map(lambda b:b>k,G)),H).

DPNK-ghNeNgeNhNR?^tZ<KZKZ

Mendefinisikan funtion Pyang menggunakan daftar dua dadu sebagai argumennya. Ini mengembalikan -1 jika die pertama 'kalah', 0 untuk dasi dan 1 jika die pertama 'menang'. Setara dengan:

def P(N):
 K=g(N[0],N[-1]) - g(N[-1],N[0])
 return -1**(K<0) if K else 0

The AGHditunjuk bertindak seperti python 2-tupel tugas. IntinyaG,H=(result)

msdCm,PkP,yhkyekm,@Qb@QhbUQ

Akan menjelaskan mundur melalui peta. m,@Qb@QhbUQiterasi lebih dari b = 0..2 dan menghasilkan 2-tupel dadu dengan indeks b dan indeks b +1. Ini memberi kita dadu (A, B), (B, C), (C, A) (pyth secara otomatis mengubah indeks dengan panjang daftar).

Selanjutnya, m,PkP,yhkyekulangi hasil dari peta sebelumnya, dengan masing-masing pasangan dadu disimpan dalam k pada setiap lintasan. Pengembalian tuple(P(k),P(tuple(y(k[0]),y(k[-1]))))untuk setiap nilai. Itu bermuara pada `((A beats B?, 2 * A beats 2 * B), (B beats C?, 2 * B beats ..)).

Terakhir, msdCjumlahkan nilai-nilai peta sebelumnya setelah zip. Zip menyebabkan semua nilai 'beats' dadu tunggal dalam tupel pertama, dan nilai dadu ganda dalam dadu kedua.

?"none"|!G%G3s[*!+GH"Grime-"*qGH"strongly ""nontransitive

Suatu hal yang kotor yang mencetak hasilnya. Jika G adalah 0 atau tidak habis dibagi 3, ini tangkapan bot +/- 3, ( |!G%G3), cetakan none, jika tidak mencetak jumlah dari daftar follwing: [not(G+H)*"Grime",(G==H)*"strongly ","nontransitive"]. Saya pikir boolean cukup jelas tentang definisi dalam pertanyaan. Perhatikan bahwa G tidak boleh nol di sini, seperti yang ditangkap oleh cek sebelumnya.

FryAmTheEggman
sumber
1

J (204)

Terlalu lama, mungkin bisa banyak bermain golf dengan memiliki sistem yang lebih efisien untuk memilih string yang tepat.

f=:3 :'(<,>)/"1+/"2>"1,"2(<,>)/L:0{(,.(1&|.))y'
n=:'nontransitive'
d=:3 :0
if.+/*/a=.f y do.+/*/b=.f<"1>,"2+/L:0{,.~y if.a-:b do.'strongly ',n elseif.a-:-.b do.'Grime-',n elseif.do.n end.else.'none'end.
)
ɐɔıʇǝɥʇu
sumber
1

Matlab (427)

Ini tidak sesingkat itu dan saya yakin itu bisa bermain golf lebih banyak, saya hanya mencoba untuk menyelesaikan tantangan ini karena saya pikir itu adalah tugas yang sangat menyenangkan, jadi terima kasih @ MartinBüttner untuk membuat tantangan ini!

a=input();b=input();c=input();
m = 'non';l=@(a)ones(numel(a),1)*a;n=@(a,b)sum(sum(l(a)>l(b)'));g=@(a,b)n(a,b)>n(b,a);s=@(a,b,c)sum([g(a,b),g(b,c),g(c,a)]);
x=s(a,b,c);y=s(a,c,b);if x~=3 && y~=3;m=[m,'e'];else m=[m,'transitive'];o=ones(6,1);a=o*a;a=a+a';a=a(:)';b=o*b;b=b+b';b=b(:)';c=o*c;c=c+c';c=c(:)';u=s(a,b,c);
v=s(a,c,b);if u==3|| v==3;if x==3&&u==3 || y==3&&v==3 m=['strongly ',m];else m=['Grime-',m];end;end;end;disp(m);

Berikut kode panjang lengkap dengan beberapa komentar jika Anda ingin mencoba memahami apa yang terjadi. Saya menyertakan beberapa test case kelinci dan tidak memasukkan perintah input:

%nontransitive
% a = [1 2 2 4 6 6];
% b = [1 2 3 5 5 5];
% c = [2 3 4 4 4 4];

%none
% a = [1 2 3 4 5 6];
% b = [6 5 4 3 2 1];
% c = [1 3 5 2 4 6];

%grime nontransitive
% a = [3 3 3 3 3 6];
% b = [2 2 2 5 5 5];
% c = [1 4 4 4 4 4];

%strongly nontransitive
% a = [2 2 2 5 5 5];
% b = [2 3 3 3 5 5];
% c = [1 1 4 5 5 5];

m = 'non';

l=@(a)ones(numel(a),1)*a;
n=@(a,b)sum(sum(l(a)>l(b)'));
%input as row vector, tests whether the left one beats the right one:
g=@(a,b)n(a,b)>n(b,a);
s=@(a,b,c)sum([g(a,b),g(b,c),g(c,a)]);
%if one of those x,y has the value 3, we'll have intransitivity
x=s(a,b,c); 
y=s(a,c,b);
if x~=3 && y~=3 %nontransitive
    m=[m,'e'];
else %transitive
    m=[m,'transitive'];
    o=ones(6,1);
    a=o*a;a=a+a';a=a(:)'; %all possible sums of two elements of a
    b=o*b;b=b+b';b=b(:)';
    c=o*c;c=c+c';c=c(:)';
    u=s(a,b,c);
    v=s(a,c,b);

    %again: is u or v equal to 3 then we have transitivity
    if u==3 || v==3 %grime OR strongly
        % if e.g. x==3 and u==3 then the 'intransitivity' is in the same
        % 'order', that means stronlgy transitive
        if x==3 && u==3 || y==3 && v==3%strongly
            m=['strongly ',m];
        else %grime
            m=['Grime-',m];
        end   
    end
end

disp(m);
cacat
sumber
Bukankah lebih pendek jika Anda membaca satu array input()dan kemudian menetapkan tiga elemen a,b,c? Juga, gunakan string tepat di spec ( none, nontransitive, dan dikapitalisasi Grime) ... mungkin harus bahkan menghemat byte.
Martin Ender
Ya ini mungkin akan lebih pendek, saya akan melihatnya. String akan persis seperti yang saya baru saja menghapus dispperintah dalam versi panjang, mereka hanya untuk menguji program, tetapi pesan terakhir disimpan di m. Dan saya mengoreksi G.
flawr
0

JavaScript - 276 byte

function(l){r=function(i){return l[i][Math.random()*6|0]};p=q=0;for(i=0;j=(i+1)%3,i<3;++i)for(k=0;k<1e5;++k){p+=(r(i)>r(j))-(r(i)<r(j));q+=(r(i)+r(i)>r(j)+r(j))-(r(i)+r(i)<r(j)+r(j))}alert((a=Math.abs)(p)>5e3?((a(q)>5e3?p*q>0?'strongly ':'Grime-':'')+'nontransitive'):'none')}

Saya tidak benar-benar baik dalam probabilitas, jadi untuk memastikan hasil saya, saya lebih suka melempar dadu ratusan ribu kali.

Ekspresi mengevaluasi ke suatu fungsi, yang harus dipanggil dengan hanya satu argumen: array tiga array bilangan bulat. Periksa biola untuk dapat menjalankan kode sendiri.

Ini adalah versi yang tidak disunat:

function (diceList) {
    var getRandomValue = function (idDie) {
        return diceList[idDie][Math.floor(Math.random() * 6)];
    };

    var probabilitySimpleThrow = 0;
    var probabilityDoubleThrow = 0;

    for (var idDieA = 0; idDieA < 3; ++idDieA)
    {
        var idDieB = (idDieA + 1) % 3;
        for (var idThrow = 0; idThrow < 1e5; ++idThrow)
        {
            probabilitySimpleThrow += getRandomValue(idDieA) > getRandomValue(idDieB);
            probabilitySimpleThrow -= getRandomValue(idDieA) < getRandomValue(idDieB);

            probabilityDoubleThrow += getRandomValue(idDieA) + getRandomValue(idDieA) > getRandomValue(idDieB) + getRandomValue(idDieB);
            probabilityDoubleThrow -= getRandomValue(idDieA) + getRandomValue(idDieA) < getRandomValue(idDieB) + getRandomValue(idDieB);
        }
    }

    if (Math.abs(probabilitySimpleThrow) > 5e3) {
        if (Math.abs(probabilityDoubleThrow) > 5e3) {
            if (probabilitySimpleThrow * probabilityDoubleThrow > 0) {
                var result = 'strongly ';
            }
            else {
                var result = 'Grime-';
            }
        }
        else {
            var result = '';
        }

        result += 'nontransitive';
    }
    else {
        var result = 'none';
    }

    alert(result);
}
Lubang hitam
sumber
Hm, saya tidak berpikir ini benar-benar dalam semangat tantangan. Anda pada dasarnya mengubahnya dari tantangan teori probabilitas menjadi tantangan statistik. ;) ... Alih-alih melakukan lemparan acak, Anda bisa menghitung semua kemungkinan lemparan tepat satu kali. Itu akan memberi Anda hasil yang tepat (dan akan berjalan lebih cepat).
Martin Ender
Saya akan memeriksa apakah ini mengarah ke skrip yang lebih ringkas. Terima kasih atas saranmu :).
Blackhole