Mari Menilai Beberapa Buku Dari Sampulnya

47

Semua orang tahu bahwa konten membuat pertanyaan. Tapi gelar yang bagus juga membantu, dan itulah hal pertama yang kita lihat. Inilah saatnya untuk mengubah kesan pertama itu menjadi sebuah program, dan mencari tahu judul-judul apa yang mendapatkan lebih banyak suara.

Anda dengan ini ditantang untuk menulis program atau fungsi yang mengambil judul pertanyaan PPCG sebagai input, dan mengembalikan prediksi nilainya.

Misalnya, Anda mungkin menerima Counting Grains of Ricesebagai masukan, dan Anda akan mencoba mengembalikan sesuatu yang mendekati skor, 59dalam hal ini. Tebakan non-integer baik-baik saja, tetapi tebakan pada atau di bawah -20tidak.

Berikut adalah datanya, untuk pengujian dan penilaian:

http://data.stackexchange.com/codegolf/query/244871/names-and-upvotes

Penilaian: Program Anda akan dijalankan pada setiap pertanyaan dalam riwayat situs (PPCG) ini, tidak termasuk pertanyaan tertutup. Fungsi ln(score + 20)kemudian akan diterapkan ke setiap skor, dan untuk setiap tebakan. Root-mean-squared-error antara dua set nilai yang dihasilkan adalah skor Anda. Lebih rendah lebih baik.

Misalnya, sebuah program yang menebak 0 setiap kali akan mencetak 0,577, sedangkan yang menebak 11 setiap kali akan mencetak 0,362.

Silakan hitung skor Anda dan sertakan dalam judul jawaban Anda. Harap sertakan juga prediksi program Anda untuk berapa banyak upvotes yang akan didapat pertanyaan ini.

Pembatasan:

  • Untuk mencegah pengkodean yang berlebihan, tidak lebih dari 1000 karakter.

  • Harus dijalankan pada seluruh data yang ditetapkan di atas dalam waktu kurang dari satu menit pada mesin yang masuk akal.

  • Lubang Standar ditutup.


Berikut ini adalah penguji yang ditulis dengan Python, untuk penggunaan Anda dan / atau untuk menjernihkan ambiguitas:

import sys
import math
import csv

scores_dict = {}

with open(sys.argv[1], 'r') as csv_file:
    score_reader = csv.reader(csv_file)
    for score, title in score_reader:
        if score == 'Score':
            continue
        scores_dict[title] = int(score)

def rate_guesses(guesser):
    def transform(score):
        return math.log(score + 20) if score > -20 else 0
    off_by_total = 0
    lines_count = 0
    for title in scores_dict:
        guessed_score = guesser(title)
        real_score = scores_dict[title]
        off_by_total += (transform(real_score) - transform(guessed_score)) ** 2
    return (off_by_total/len(scores_dict)) ** .5

def constant11(title):
    return 11

print(rate_guesses(constant11))
isaacg
sumber
19
Gagasan bagus, tapi sayang dataset tidak stabil, jadi skornya akan menjadi tidak valid setelah beberapa saat. Ada juga kemungkinan kecil pemungutan suara strategis: siapa pun yang menjawab pertanyaan ini dan mendapat lencana vox-populi di minggu yang sama harus dilihat dengan kecurigaan! ;-)
Level River St
1
Apakah judul menyertakan atau mengecualikan hal-hal seperti [closed]dan [on hold], di mana berlaku?
es1024
4
@steveverrill Nah, sisi buruknya adalah seiring berjalannya waktu, kita akan dapat melihat apakah program bekerja dengan baik pada pos di masa mendatang maupun di masa lalu.
isaacg
6
Sulit untuk mengalahkan hard-coding. Setiap pertanyaan terpilih dengan hard-kode dapat mengurangi skor sebanyak 0,4. Dan tampaknya tidak ada banyak pola umum juga, haha. Saya memperkirakan bahwa jawaban hanya akan bersaing tentang bagaimana agar sesuai dengan hasil hard-kode sebanyak 1000 byte.
justhalf
5
Anda sebaiknya tidak menggunakan seluruh tubuh pertanyaan sebagai set tes Anda. Anda harus memilih dulu nomor tertentu (10% -20%) secara acak, dan mendefinisikannya sebagai set tes Anda (tetapi tidak memberi tahu siapa pun apa itu). Jauh lebih mudah untuk membuat algoritma yang memprediksi riwayat masa lalu, daripada yang memiliki nilai prediksi masa depan (yaitu, yang bekerja dengan baik pada setiap bagian yang diberikan). (Akan lebih baik untuk menghapus 10% dari apa yang dapat kita lihat sama sekali, tetapi itu tidak akan bekerja dengan baik.)
Joe

Jawaban:

9

Python 2, 991 karakter, skor 0,221854834221, prediksi 11

import base64
e={}
d=base64.decodestring('vgAcRAEVDAIsqgQYalYaggcjQKwVXAoZWAsYQg0Ckg4VlWEX9hEDRhMe0hckCBkeuhsW3CAWQiEm\nSiMZMiwgTDAZZjIcSLMZfDQDnjwCe2AVaEQCYWEBIEgnDEoXzk0e3lQb5FYVKlkVZlwB+F0XwmI/\nGmRcuGUXWmYdVGkbzmwafG8eaHMdInkggHonRn5sKoMXgIkpbowVOI4cNJAubpQdYpcydJgVypkA\nZpweMp8ZsqEcRKMghKQYkKVPPXEWMqkWHKwbjrEdzLIBNLMf1LQivrYC99UV9rxNRsABNMEiPzob\npc0ActAhn3gcrNUZYNcWYNov/t8VgOEXAuMYqOUWsqUiCPIefPWNbvtKevwWvP0Cl9UsjQMdWwQb\nfQdpJQgWYwkCZRLBjxMWWdkqHRkWNxwB6x8p2SEZyyICSyYcgysaOS0CUy8hezAaGeEVpTRQ3zUz\nZzkZRzohizwwST4c8UAdF0OqG9AXIuEYYRN6208nU1AktVEVJ1IVWeMkIVQXdY4D2VYYD/cYb1om\nG1xA0zoY3uUaRWAhWpBSHWUXQTxGe+cad20CO3AZX3EBw3IiMXcef3gecXsVGXwhw30VbX4W24BD\n6qyQ45YaYYgZ4YobbYwauY4bMY82HZEdO5YmQ5cV35sVxaMbY6gYNas576ws+bADO7QpN7hdLJ8B\n4Eoks8EYX8VU68cYWfcar82QOdAaxdEfQ9UiW/kXL9k2ddwCW90m694enqUCkeEBE+IYWvsfA1FC\nJ+spMVIjhe4WEP0fAfYax/c3MfgbgfkqP/0DLf4V\n')
for i in range(0,600,3):
 e[ord(d[i])*256+ord(d[i+1])]=ord(d[i+2])*2-8
def p(t):
 return e.get(hash(t)%256**2,11)

Penjelasan:

Ini adalah hardcoding yang tidak tahu malu, tetapi berusaha melakukannya dengan efisien.

Pra-pemrosesan:

Dalam kode terpisah, saya memotong setiap judul dengan nilai antara 0 dan 256 ^ 2-1. Sebut saja nilainya nampan ini. Untuk setiap nampan, saya menghitung skor rata-rata. (Rata-rata diperlukan karena untuk sebagian kecil dari nampan, ada tabrakan - lebih dari 1 judul hash ke nampan yang sama. Tapi untuk sebagian besar setiap judul memetakan ke nampan sendiri).

Gagasan di balik kode 2-byte untuk setiap judul adalah bahwa 1 byte tidak cukup - kita mendapatkan terlalu banyak tabrakan, jadi kita tidak benar-benar tahu skor apa yang harus ditetapkan untuk setiap nampan 1-byte. Tetapi dengan bin 2-byte, hampir tidak ada tabrakan, dan kami secara efektif mendapatkan representasi 2 byte dari setiap judul.

Kemudian beri peringkat nampan - hitung gain dalam skor jika kita menetapkan nampan ini nilainya yang dihitung, alih-alih hanya menebak 11. Ambil n nampan teratas, dan kode mereka ke dalam string (yang d dalam kode aktual).

Pengkodean: kunci tempat sampah dikodekan sebagai 2 byte. nilai dikodekan menggunakan 1 byte. Saya menemukan nilai antara -8 dan 300 + sesuatu, jadi harus memeras sedikit untuk mendapatkannya menjadi 1 byte: x -> (x + 8) / 2.

Kode aktual:

baca d sebagai byte triplet, decoding encoding yang dijelaskan di atas. Ketika sebuah judul diberikan, hitung hash-nya (modulo 256 ^ 2), dan jika kunci itu ditemukan dalam dict, kembalikan nilai yang dipetakannya. Kalau tidak, kembalikan 11.

Ofri Raviv
sumber
3
Saran: Skor rata-rata tidak sebaik itu. Lihatlah fungsi penilaian tantangan, ini non-linear.
Deduplicator
1
@Dupuplikator Terima kasih, saya menyadari bahwa setelah saya selesai. Masalahnya, untuk 99% dari sampah, tidak ada tabrakan, jadi rata-rata sebenarnya hanya skor dari judul tunggal yang memetakan ke tempat sampah.
Ofri Raviv
16

Javascript ES6

Nilai: 0,245663
Panjang: 1000 byte
Prediksi: 5

(Saya kira pertanyaannya adalah karena longvotes downvotes yang tak terduga.: P)

Diperkecil

E="ABCDEFGHIJKLMNOPQRSTUVWXYZ";E=E+E.toLowerCase()+"0123456789!@#$%;*()";P="RCRHIFMGPGIDQKHMJLLRMLFJGKHEqHPOgJNKGPCHPJNUPOSGJQKKKMELMIJHLKIKNcKDOfSJLFHDILGKIOUKLMLLKMKIHGHJGIIJDGJKIHIIFIGMTIHFJMIKDJGQJKGMKJHPRJPLMGIOPIIIIPBYFMGLEIKIMMRUKFLFGJFKFTHPFODEQTGTHKIJDHNJGDGiHKNYLHHDLJHGILOEViKNEKGQZfHJMIISIJFRHKLJMLPIFJILKKKJKKJESHNLLIKIGKGJJJHKJRGULLSLRONJNEeLKIQGGPQIHPLEIHHIDXjQHNBKOGWWIENRbYoHINHNMKTNKHTGMIPXFJLLMLIHPPLDJJKFUMIQMOKJLJJKIJKNLHRILJIAIbJEZOGIELGHGLOINDPJMJeJWRIIJHSOZDOsOFRRIOIOTIJSGGJKFUIDOINGOcLQEJFEITLMNIIGIGIMG7LPSNLKVOKIFGHJITGOFUJIIRN";K={};"99r1501vz076mip077myv0733it280exx081gt9118i1g279dyx102uho203ejd07433z087uje097kdg1567ft2088rk275dmu1203ez106lih1763ei126f6q101aax084owh088aid161i9y179gvn236ptn3338vf132i55080fke101l4z3789ai281ulm081blm124euz074o5m07513z14117l095qdn092gl30757n5153".replace(/(...)(...)/g,(_,a,b)=>K[a]=1*b);D=40655;N=479;H=(s,T)=>(h=7,[...s].map(c=>h=~~(h*T+c.charCodeAt(0))),h);S=s=>(y=H(s,31),K[((y%D+D)%D).toString(36)]||E.indexOf(P[(H(s,48)%N+N)%N]));

Diperluas

E = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
E = E + E.toLowerCase() + "0123456789!@#$%;*()";
K = {};
P = "RCRHIFMGPGIDQKHMJLLRMLFJGKHEqHPOgJNKGPCHPJNUPOSGJQKKKMELMIJHLKIKNcKDOfSJL" +
    "FHDILGKIOUKLMLLKMKIHGHJGIIJDGJKIHIIFIGMTIHFJMIKDJGQJKGMKJHPRJPLMGIOPIIIIP" +
    "BYFMGLEIKIMMRUKFLFGJFKFTHPFODEQTGTHKIJDHNJGDGiHKNYLHHDLJHGILOEViKNEKGQZfH" +
    "JMIISIJFRHKLJMLPIFJILKKKJKKJESHNLLIKIGKGJJJHKJRGULLSLRONJNEeLKIQGGPQIHPLE" +
    "IHHIDXjQHNBKOGWWIENRbYoHINHNMKTNKHTGMIPXFJLLMLIHPPLDJJKFUMIQMOKJLJJKIJKNL" +
    "HRILJIAIbJEZOGIELGHGLOINDPJMJeJWRIIJHSOZDOsOFRRIOIOTIJSGGJKFUIDOINGOcLQEJ" +
    "FEITLMNIIGIGIMG7LPSNLKVOKIFGHJITGOFUJIIRN";

   ("99r1501vz076mip077myv0733it280exx081gt9118i1g279dyx102uho203ejd07433z087u" +
    "je097kdg1567ft2088rk275dmu1203ez106lih1763ei126f6q101aax084owh088aid161i9" +
    "y179gvn236ptn3338vf132i55080fke101l4z3789ai281ulm081blm124euz074o5m07513z" +
    "14117l095qdn092gl30757n5153").
        replace( /(...)(...)/g, (_,a,b) => K[a] = 1*b );

D = 40655;
N = 479;
H = (s,T) => (
    h = 7,
    [...s].map( c => h = ~~(h*T + c.charCodeAt(0)) ),
    h
);

S = s => (
    y = H( s, 31 ),
    K[((y%D + D)%D).toString( 36 )] || E.indexOf( P[(H( s, 48 )%N + N)%N] )
);

Fungsi Smenerima string (judul) dan mengembalikan nilainya.

Catatan tentang Perilaku:

  • ≤ 70 judul suara ditangani secara terpisah dari> 70 judul suara
  • ≤ 70 judul suara diurutkan ke dalam nampan menggunakan algoritma optimisasi potensi pelacakan kata kunci holonomis yang sangat canggih yang sama sekali tidak menyerupai fungsi hash string
  • setelah sedikit kalkulus bahagia ternyata tebakan optimal untuk setiap nampan hanyalah rata-rata geometris dari (suara + 20) untuk semua judul dalam nampan, minus 20
  • tebakan optimal untuk semua 479 sampah kemudian dikodekan sebagai string basis-70 karakter 479
  • untuk> 70 judul suara, judul-judul tersebut diberikan kode basis-36 3-digit unik yang dihasilkan menggunakan teknik hashing canggih yang menjamin tidak ada tabrakan dengan> 70 judul suara lainnya dan tidak ada deteksi palsu judul-judul suara ≤ 70. Teknik canggih ini sama sekali tidak menyerupai mencoba jumlah bin acak sampai seseorang tidak menghasilkan tabrakan.
  • kode judul> 70 suara dan jumlah suara mereka dikodekan dalam string (6 byte per judul), yang dikonversi ke tabel pencarian sederhana. Karena itu, rutin tidak memiliki kesalahan untuk semua> 70 judul suara.
COTO
sumber
10

Python 2, Skor = 0,335027, 999 karakter, Prediksi 11,34828 untuk pertanyaan ini

Hanya untuk membuat bola bergulir. Ini tidak optimal.

SVM yang mewah hanyalah ide acak saya dan saya ingin mengimplementasikannya, jadi ini dia. Itu meningkatkan baseline sebesar 0,02 poin, jadi saya cukup senang dengan itu. Tetapi untuk menunjukkan bahwa pengkodean keras input adalah tempat sebagian besar perbaikan berasal, saya juga mengkode beberapa jawaban.

Tanpa hard-coding skornya adalah 0,360 (dan sebenarnya semua prediksi sekitar 11, haha)

Saya menggunakan scikit-learn dan nltk

import sys
import math
import csv
from sklearn.feature_extraction.text import TfidfVectorizer as TV
from sklearn.svm import SVR
from nltk.stem.porter import PorterStemmer as PS
sd = {}
lr = None
tv = None
with open(sys.argv[1], 'r') as cf:
    sr = csv.reader(cf)
    for sc, t in sr:
        if sc == 'Score':
            continue
        sd[t] = int(sc)
ts,scs = zip(*sd.items())
s = PS()
def analyzer(st):
    r = []
    for word in st.split():
        if word.isdigit():
            r.append('<NUM>')
        elif not word.isalnum():
            r.append('<PUNCT>')
        else:
            r.append(s.stem(word.lower()))
    return r
tv = TV(min_df=25, stop_words='english', analyzer=analyzer)
ti = tv.fit_transform(ts)
lr = SVR()
lr.fit(ti, scs)
d={'4 w':378,'y 42':333,'eeta':280,'an Got':279,'s 2 ':275,"e I'":208,'r CP':203,'? No':179,'B.O':156}
def c(t):
    for s in d.keys():
        if s in t:
            return d[s]
    t = tv.transform([t])
    r = lr.predict(t)[0]+1.5
    return r
justhalf
sumber
Saya tidak yakin saya mengerti - Anda membaca skor dari file eksternal? Jadi mengapa tidak memprediksi SD [t] saja? Ini akan memberikan skor 0 ...
Ofri Raviv
2
Karena itu tidak akan menyenangkan = p
justhalf
4

Python 2, 986 karakter, skor 0,3480188, prediksi 12

M,S=14.29,23.02
D=lambda x:[ord(y)-32 for y in x]
w='fiLoNoNuMiNoTiMoShOnLoGoLeThRantexgensuBaSqUnInPeReGaMuLinprOuThInThEvEnClOpExPyThADdiSoLiSiMaTrEqUsImAsCoManstARrePoWoReawhapoLandradeTyPaLOsoReCreprediVeReSpebeTiPrImPladaTrihelmakwhicolpaReValpaTrafoROsoumovfinfunpuzyoufaSeQuiwhecoDeChagivcouchehanpoStrdiGraconjavwricalfrowitbinbrafrabuipoi'
for i in range(26):w=w.replace(chr(65+i),chr(97+i)*2)
w=[w[i:i+3]for i in range(0,372,3)]
m=D("(+),+)+=*...+..++'(*)5)/2)*43++16+0,+33*4*/(0.'+>-)+13+(2?8+6;,3;43+4(+.('(,.*.*+56+6)0((++(B,))+E0,-7/)/*++),+***)2+(3(.*)'")
s=D("))'B)'*j+:51(*3+0')+)^'/<-+MG,-1=),-0:A+T&J&K1%,O*()4Y-%:_A.=A*C]MJ-N%)5(%%-0+).*3Q(M&0'%(+$p*)()a8:-T?%5(-*'/.'+)+@,'J&1'&&")
def G(x,m,s):s=s or 1e-9;return(.4/s)*(2.78**(-(x-m)**2./(2*s*s)))
d={w[i]:(m[i],s[i])for i in range(124)}
def Z(t,c):
 p=1
 for W in t.split():
  if len(W)>3:
   W=W[:3].lower()
   if W in d:p*=G(c,*d[W])
 return p*G(c,M,S)
def J(t):return max([(Z(t,r),r)for r in range(-9,99)])[1]

Fungsi yang relevan adalah J.

Program ini pada dasarnya Naif Bayes menggunakan kata-kata judul sebagai fitur, tetapi ini sangat terbatas berkat batas char. Bagaimana dibatasi? Baik...

  • Untuk setiap judul, kami mengonversi ke huruf kecil dan hanya melihat kata yang panjangnya minimal 4 huruf. Lalu kita ambil tiga huruf pertama dari masing-masing kata itu sebagai fitur. Kami melewatkan tanda baca untuk menghemat karakter.
  • Kami hanya memilih surat kembar tiga yang berada di awal setidaknya 19 kata (ini disimpan di watas). Kompresi dilakukan dengan menata ulang kembar tiga sehingga sebanyak mungkin surat berlipat ganda, dan pasangan ini diganti dengan huruf besar ASCII yang sesuai (mis. FiLoNoN ... → fil, lon, non, ...)
  • Untuk setiap triplet, kami melihat skor judul yang muncul dan menghitung rata-rata dan standar deviasi skor. Kemudian kita mengkonversi mereka untuk bilangan bulat dan menyimpannya dalam m, sdi atas, dengan menggunakan fakta bahwa rata-rata / sd yang paling 90 (memungkinkan encoding ASCII langsung, karena ada 95 ASCII dicetak)
  • G adalah fungsi distribusi normal - kita membulatkan e ke 2dp dan akar kuadrat terbalik dari 2 pi hingga 1 dp untuk menghemat karakter.

Secara keseluruhan, batas char ekstrim membuat ini menjadi salah satu ide terburuk yang pernah saya buat, tapi saya cukup senang dengan seberapa banyak saya berhasil menjejalkannya (meskipun itu tidak bekerja dengan baik). Jika ada yang punya ide lebih baik untuk kompresi, beri tahu saya :)

(Terima kasih kepada KennyTM karena menunjukkan kompresi tidak berguna saya)

Sp3000
sumber
Kecuali jika saya salah mengeksekusi kode, kode kompresi Anda bahkan lebih lama dari hasil dekompresi ... w='grge…scse';w=[w[i:i+2]for i in range(0,len(w),2)]adalah 165 byte sedangkan Anda C=lambda:…;w=C('…')adalah 179 byte.
kennytm
@ KennyTM Oh terima kasih - Saya telah bermain-main dengan kode begitu banyak, mencoba untuk memenuhi batas char bahwa saya telah kehilangan jejak dari semua kompresi. : P
Sp3000
4

Python 2, 535 karakter, skor 0,330910, memprediksi 11,35

Rata-rata skor untuk judul yang berisi setiap kata, lalu gunakan 50 kata teratas dan terbawah untuk mengubah skor BASE dalam guess(title)fungsi.

Kode python:

BASE = 11.35
word={}
for sc,ti in csv.reader(open(sys.argv[1])):
    if sc == 'Score': continue
    parts = re.findall(r"[-a-zA-Z']+", ti.lower())
    for p in parts:
        a, c = word.get(p, (0.0,0))
        word[p] = (a+int(sc), c+1)

rank = sorted([(sc/ct,wd) for wd,(sc,ct) in word.items() if ct > 2])
adjust = rank[:50] + rank[-50:]

def guess(title):
    score = BASE
    parts = re.findall(r"[-a-zA-Z']+", title.lower())
    for sc,wd in adjust:
        if wd in parts:
            score *= 0.7 + 0.3*sc/BASE
    return score
Ksatria Logika
sumber
3

C

Nilai:
Panjang Tidak Diketahui : 5 byte
Prediksi: 5

Golf:

int s(char *p){return 5;}

Tidak Disatukan:

int s(char *p)
{
   return 5;
}

Kueri skor memberikan skor rata-rata 5.

Saya tidak punya kemampuan untuk mengujinya saat ini, orang lain dipersilakan untuk menjalankan / mengedit.

Joshpbarron
sumber
Lebih jauh Gulfed: int s () {return 5;}
Joshua
"Dengan ini Anda ditantang untuk menulis sebuah program atau fungsi yang menggunakan judul pertanyaan PPCG sebagai input, dan mengembalikan prediksi nilainya." - Maaf tapi tidak: 0
Joshpbarron
Saya telah melihat platform di mana jika Anda lupa main (), fungsi pertama Anda adalah main (). Mungkin dia tergantung pada itu.
Joshua