Juzguemos algunos libros por sus portadas

47

Todos saben que el contenido hace la pregunta. Pero un buen título también ayuda, y eso es lo primero que vemos. Es hora de convertir esa primera impresión en un programa y descubrir qué tipos de títulos obtienen más votos positivos.

Por el presente, se le desafía a escribir un programa o función que tome el título de una pregunta PPCG como entrada y devuelva una predicción de su puntaje.

Por ejemplo, puede recibir Counting Grains of Ricecomo entrada, e intentaría devolver algo cercano al puntaje, 59en este caso. Las suposiciones no enteras están bien, pero las suposiciones iguales o inferiores -20no.

Aquí están los datos, para probar y calificar:

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

Puntuación: Su programa se ejecutará en cada pregunta en el historial de este sitio (PPCG), sin contar las preguntas cerradas. La función ln(score + 20)se aplicará a cada puntaje y a cada suposición. La raíz del error cuadrático medio entre los dos conjuntos de valores resultantes es su puntaje. Más bajo es mejor.

Por ejemplo, un programa que adivinó 0 cada vez obtendría una puntuación de 0.577, mientras que uno que adivinó 11 cada vez obtendría una puntuación de 0.362.

Calcule su puntaje e inclúyalo en el título de su respuesta. Incluya también la predicción de su programa sobre cuántos votos positivos obtendrá esta pregunta.

Restricciones

  • Para evitar una codificación excesiva, no más de 1000 caracteres.

  • Debe ejecutarse en todo el conjunto de datos anterior en menos de un minuto en una máquina razonable.

  • Las lagunas estándar están cerradas.

Aquí hay un probador escrito en Python, para su uso y / o para aclarar ambigüedades:

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))
code-challenge isaacg
fuente
19
Buena idea, pero es una pena que el conjunto de datos no sea estable, por lo que las puntuaciones se volverán inválidas después de un tiempo. También hay una pequeña posibilidad de votación estratégica: ¡cualquiera que responda a esta pregunta y gane una insignia de vox-populi en la misma semana debe ser visto con sospecha! ;-)
Level River St
1
¿El título incluirá o excluirá cosas como [closed]y [on hold], cuando corresponda?
es1024
44
@steveverrill Bueno, la otra cara de esto es que a medida que pasa el tiempo, podremos ver si los programas funcionan bien en publicaciones futuras y en publicaciones pasadas.
isaacg
66
Es difícil vencer a la codificación rígida. Cada pregunta codificada y votada con más votos puede reducir hasta 0.4 puntos. Y parece que no hay mucho patrón común también, jaja. Estoy prediciendo que las respuestas solo competirán sobre cómo ajustar tantos resultados codificados en 1000 bytes.
justo el
55
No debe utilizar el conjunto completo de preguntas como conjunto de pruebas. Debe preseleccionar un número determinado (10% -20%) al azar y definirlos como su conjunto de prueba (pero no decirle a nadie qué es eso). Es mucho más fácil crear un algoritmo que prediga la historia pasada, que uno que tenga un valor predictivo futuro (es decir, uno que funcione bien en cualquier subconjunto dado). (Sería aún mejor eliminar ese 10% de lo que podemos ver, pero eso realmente no funcionaría).
Joe

Respuestas:

9

Python 2, 991 caracteres, puntaje 0.221854834221, predicen 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)

Explicación:

Este es un hardcoding descarado, pero intenta hacerlo de manera eficiente.

Preprocesamiento:

En un código separado, hechice cada título a un valor entre 0 y 256 ^ 2-1. Llamemos a estos valores bins. Para cada contenedor, calculé el puntaje promedio. (El promedio es necesario porque para una pequeña fracción de los contenedores, hay colisiones: más de 1 título hash en el mismo contenedor. Pero para la gran mayoría, cada título se asigna a un contenedor propio).

La idea detrás del código de 2 bytes para cada título es que 1 byte no es suficiente: tenemos demasiadas colisiones, por lo que realmente no sabemos qué puntaje asignar a cada bin de 1 byte. Pero con los contenedores de 2 bytes, casi no hay colisiones, y efectivamente obtenemos una representación de 2 bytes de cada título.

Luego clasifique los bins: calcule la ganancia en puntaje si asignamos a este bin su valor calculado, en lugar de simplemente adivinar 11. Tome los N bins superiores y codifíquelos en una cadena (que es d en el código real).

La codificación: la clave de la papelera está codificada como 2 bytes. El valor se codifica con 1 byte. Encontré valores entre -8 y 300 + algo, así que tuve que apretar un poco para ponerlo en 1 byte: x -> (x + 8) / 2.

Código actual:

leer d como tripletes de bytes, decodificando la codificación explicada anteriormente. Cuando se otorga un título, calcule su hash (módulo 256 ^ 2), y si esa clave se encuentra en el dict, devuelva el valor al que se asigna. De lo contrario, regrese 11.

Ofri Raviv
fuente
3
Una sugerencia: el puntaje promedio no es tan bueno. Mira la función de puntuación de desafíos, no es lineal.
Deduplicador
1
@Dupuplicator Gracias, me di cuenta de eso después de que terminé. La cuestión es que, para el 99% de los contenedores, no hay colisiones, por lo que el promedio es en realidad solo el puntaje del título único que se asigna a ese contenedor.
Ofri Raviv
16

Javascript ES6

Puntuación: 0.245663
Longitud: 1000 bytes
Predice: 5

(Supongo que la pregunta se debe a una avalancha inesperada de votos negativos: P)

Minified

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]));

Expandido

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] )
);

La función Sacepta una cadena (título) y devuelve su puntuación.

Notas sobre el comportamiento:

  • ≤ 70 títulos de voto se manejan por separado de> 70 títulos de voto
  • ≤ 70 títulos de voto se clasifican en bandejas utilizando un algoritmo de optimización de potencial de seguimiento de palabras clave holonómico altamente sofisticado que de ninguna manera se asemeja a una función hash de cadena
  • después de un poco de cálculo feliz, resulta que la suposición óptima para cada contenedor es simplemente el promedio geométrico de (votos + 20) para todos los títulos en el contenedor, menos 20
  • las conjeturas óptimas para todos los 479 contenedores se codifican como una cadena de base 70 de 479 caracteres
  • para> 70 títulos de voto, a los títulos se les asignan códigos únicos de base de 36 dígitos de 3 dígitos generados utilizando una técnica de hash de última generación que garantiza que no haya colisiones con otros títulos de> 70 votos ni detecciones falsas de ≤ 70 títulos de voto. Esta técnica de vanguardia no se parece en nada a intentar conteos aleatorios de contenedores hasta que uno no produce colisiones.
  • los> 70 códigos de título de voto y sus recuentos de votos se codifican en una cadena (6 bytes por título), que se convierte en una tabla de búsqueda simple. La rutina, por lo tanto, tiene cero errores para todos los títulos de> 70 votos.
COTO
fuente
10

Python 2, Puntuación = 0.335027, 999 caracteres, Predecir 11.34828 para esta pregunta

Solo para que la pelota ruede. Esto no es óptimo en ninguna parte.

Lo elegante de SVM es solo mi idea aleatoria y tuve ganas de implementarlo, así que aquí está. Mejora la línea de base en 0.02 puntos, así que estoy bastante feliz con eso. Pero para mostrar que codificar la entrada es de donde proviene la mayoría de las mejoras, también estoy codificando alguna respuesta.

Sin la codificación rígida, el puntaje es 0.360 (y en realidad todas las predicciones son alrededor de 11, jaja)

Estoy usando scikit-learn y 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
justo
fuente
No estoy seguro de entender: ¿leyó las puntuaciones de un archivo externo? Entonces, ¿por qué no solo predecir sd [t]? Esto daría una puntuación de 0 ...
Ofri Raviv
2
Porque eso no sería divertido = p
solo el
4

Python 2, 986 caracteres, puntaje 0.3480188, predicen 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]

La función relevante es J.

El programa es esencialmente Naive Bayes usando palabras de título como características, pero está extremadamente restringido gracias al límite de caracteres. ¿Cuán restringido? Bien...

  • Para cada título, convertimos a minúsculas y solo miramos palabras de al menos 4 letras de largo. Luego tomamos las primeras tres letras de cada una de esas palabras como características. Nos saltamos los signos de puntuación para ahorrar en caracteres.
  • Elegimos solo trillizos de letras que están al principio de al menos 19 palabras (estas se almacenan warriba). La compresión se realiza reorganizando los tripletes para que haya tantas letras duplicadas como sea posible, y estos pares se reemplacen con su correspondiente ASCII en mayúsculas (por ejemplo, fiLoNoN ... → fil, lon, non, ...)
  • Para cada triplete, observamos los puntajes de los títulos en los que aparece y calculamos la media y la desviación estándar de los puntajes. Luego los convertimos en enteros y los almacenamos m, sarriba, usando el hecho de que la media / sd es como máximo 90 (permitiendo una codificación ASCII directa, ya que hay 95 ASCII imprimibles)
  • G es la función de distribución normal: redondeamos e a 2dp y la raíz cuadrada inversa de 2 pi a 1 dp para guardar en caracteres.

En conjunto, el límite extremo de char hizo de esta una de las peores ideas que se me ocurrió, pero estoy muy contento con lo mucho que logré meter (aunque no funciona muy bien). Si alguien tiene mejores ideas para la compresión, hágamelo saber :)

(Gracias a KennyTM por señalar mi compresión sin sentido)

Sp3000
fuente
A menos que haya ejecutado el código incorrectamente, su código de compresión es incluso más largo que el resultado descomprimido ... w='grge…scse';w=[w[i:i+2]for i in range(0,len(w),2)]es de 165 bytes mientras que el suyo C=lambda:…;w=C('…')es de 179 bytes.
kennytm
@KennyTM Oh, gracias. He estado jugando mucho con el código, tratando de ajustar el límite de char que había perdido la noción de toda la compresión. : P
Sp3000
4

Python 2, 535 caracteres, puntaje 0.330910, predice 11.35

Promedio de la puntuación de los títulos que contienen cada palabra, luego use las 50 palabras superiores e inferiores para modificar posiblemente la puntuación BASE en la guess(title)función.

Código de 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
Caballero Lógico
fuente
3

C

Puntuación: Desconocido
Longitud: 5 bytes
Predice: 5

Golfizado:

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

Sin golf:

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

Una consulta de los puntajes da un puntaje promedio de 5.

No tengo la capacidad de probarlo en este momento, otros son bienvenidos para ejecutar / editar.

Joshpbarron
fuente
Más Golfo: int s () {return 5;}
Joshua
"Se le desafía a escribir un programa o función que tome el título de una pregunta PPCG como entrada y devuelva una predicción de su puntaje". - Lo siento pero no: 0
Joshpbarron
He visto una plataforma por la cual si olvidaste main (), tu primera función fue main (). Tal vez depende de eso.
Joshua