Regresión lineal en una cuerda

25

Este desafío es un poco complicado, pero bastante simple, dada una cadena s:

meta.codegolf.stackexchange.com

Use la posición del carácter en la cadena como xcoordenada y el valor ascii como ycoordenada. Para la cadena anterior, el conjunto resultante de coordenadas sería:

0, 109
1, 101
2, 116
3, 97
4, 46
5, 99
6, 111
7, 100
8, 101
9, 103
10,111
11,108
12,102
13,46
14,115
15,116
16,97
17,99
18,107
19,101
20,120
21,99
22,104
23,97
24,110
25,103
26,101
27,46
28,99
29,111
30,109

A continuación, debe calcular tanto la pendiente como la intersección con el eje y del conjunto que ha obtenido utilizando Regresión lineal , aquí está el conjunto anterior trazado:

Trama

Lo que da como resultado una línea de mejor ajuste de (índice 0):

y = 0.014516129032258x + 99.266129032258

Aquí está la línea de mejor ajuste indexada 1 :

y = 0.014516129032258x + 99.251612903226

Entonces su programa volvería:

f("meta.codegolf.stackexchange.com") = [0.014516129032258, 99.266129032258]

O (cualquier otro formato sensible):

f("meta.codegolf.stackexchange.com") = "0.014516129032258x + 99.266129032258"

O (cualquier otro formato sensible):

f("meta.codegolf.stackexchange.com") = "0.014516129032258\n99.266129032258"

O (cualquier otro formato sensible):

f("meta.codegolf.stackexchange.com") = "0.014516129032258 99.266129032258"

Simplemente explique por qué está volviendo en ese formato si no es obvio.


Algunas reglas aclaratorias:

- Strings are 0-indexed or 1 indexed both are acceptable.
- Output may be on new lines, as a tuple, as an array or any other format.
- Precision of the output is arbitrary but should be enough to verify validity (min 5).

Este es el más bajo de conteo de bytes gana.

Urna de pulpo mágico
fuente
3
¿Tiene algún enlace / fórmula para calcular la pendiente y la intersección con el eje y?
Rod
16
Estimados votantes poco claros: Si bien estoy de acuerdo en que es bueno tener la fórmula, de ninguna manera es necesaria. La regresión lineal es una cosa bien definida en el mundo matemático, y el OP puede querer dejar la búsqueda de la ecuación al lector.
Nathan Merrill
66
en.wikipedia.org/wiki/Simple_linear_regression
Urna mágica del pulpo el
2
¿Está bien devolver la ecuación real de la línea de mejor ajuste, como 0.014516129032258x + 99.266129032258?
Greg Martin el
2
El título de este desafío ha puesto esta maravillosa canción en mi cabeza por el resto del día
Luis Mendo

Respuestas:

2

MATL , 8 bytes

n:G3$1ZQ

Se utiliza la indexación de cadenas basada en 1.

Pruébalo en línea!

Explicación

n:     % Input string implicitly. Push [1 2 ... n] where n is string length.
       % These are the x values
G      % Push the input string. A string is an array of chars, which is
       % equivalent to an array of ASCII codes. These are the y values
3$     % The next function will use 3 inputs
1      % Push 1
ZQ     % Fit polynomial of degree 1 to those x, y data. The result is an
       % array with the polynomial coefficients. Implicitly display
Luis Mendo
fuente
7

Octava, 29 26 24 20 bytes

@(s)s/[!!s;1:nnz(s)]

Pruébalo en línea!

Tenemos el modelo

y= intercept *x^0 + slope * x
 = intercept * 1  + slope * x

Aquí yestá el valor ASCII de cadenas

Para encontrar los parámetros de intercepción y pendiente podemos formar la siguiente ecuación:

s = [intercept slope] * [1 X]

asi que

[intercept slope] = s/[1 x]

!!sconvierte una cadena en un vector de unos con la misma longitud que la cadena.
El vector de unos se usa para estimar la intersección.
1:nnz(s)es un rango de valores desde 1 hasta el número de elementos de la cadena utilizada como x.

Respuesta anterior

@(s)ols(s'+0,[!!s;1:nnz(s)]')

Para la prueba, pegue el siguiente código en Octave Online

(@(s)ols(s'+0,[!!s;1:nnz(s)]'))('meta.codegolf.stackexchange.com')

Una función que acepta una cadena como entrada y aplica la estimación ordinaria de mínimos cuadrados del modelo y = x*b + e

El primer argumento de ols es yque para ello transponemos la cadena sy agregamos con el número 0 para obtener su código ASCII.

rahnema1
fuente
/, ¡gran idea!
Luis Mendo
6

TI-Basic, 51 (+ 141) bytes

Las cadenas están basadas en 1 en TI-Basic.

Input Str1
seq(I,I,1,length(Str1->L1
32+seq(inString(Str2,sub(Str1,I,1)),I,1,length(Str1->L2
LinReg(ax+b)

Al igual que el otro ejemplo, esto genera la ecuación de la línea de mejor ajuste, en términos de X. Además, en Str2 necesita tener esta cadena, que es 141 bytes en TI-Basic:

! "# $% & '() * +, -. / 0123456789:; <=>? @ ABCDEFGHIJKLMNOPQRSTUVWXYZ [] ^ _abcdefghijklmnopqrstuvwxyz{|}~

La razón por la que esto no puede ser parte del programa es porque dos caracteres en TI-Basic no se pueden agregar automáticamente a una cadena. Una es la STO->flecha, pero esto no es un problema porque no es parte de ASCII. El otro es el literal de cadena ( "), que solo se puede stringificar escribiendo una Y=ecuación y usando Equ>String(.

Timtech
fuente
Me preguntaba seriamente si alguien sacaría sus viejas calculadoras para esto :). Tenía mi vieja TI-83 en mente cuando pensé en esto.
Magic Octopus Urn
@carusocomputing ¡Hola, bien! Me gusta mucho el lenguaje de programación TI-Basic y lo uso para muchos de mis códigos de golf. Si solo fuera compatible con ASCII ...
Timtech
Dos comentarios: 1, puede hacer una cadena "de caracteres solicitándolo también como entrada del usuario en un programa, lo que no lo ayuda aquí, pero solo quería señalar ese hecho. 2, no reconozco algunos de esos caracteres como existentes en la calculadora. Podría estar equivocado, pero por ejemplo, ¿de dónde sacas @y ~? Así como #, $, y &.
Patrick Roberts el
Gracias por el comentario, @PatrickRoberts. Esos son tokens de dos bytes que comienzan con 0xBB. Mire en la columna D de tibasicdev.wikidot.com/miscellaneous-tokens
Timtech
6

R, 46 45 bytes

x=1:nchar(y<-scan(,""));lm(utf8ToInt(y)~x)$co

Lee la entrada de stdin y para el caso de prueba dado devuelve (un índice):

(Intercept)           x 
99.25161290  0.01451613 
Billywob
fuente
Ligeramente más corto (pero no probado, posiblemente algunos problemas de evaluación al analizar la fórmula):lm(utf8ToInt(y<-scan(,""))~1:nchar(y))$co
rturnbull
@rturnbull Intenté esto al principio, pero parece que la xvariable tiene que estar predefinida para lmque funcione.
Billywob
@rturnbull Me sale un error de longitud variable diferente en eso. Se nos da sasí que x=1:nchar(s);lm(charToRaw(s)~x)$coguarda algunos bytes. Tampoco sé si $coes técnicamente necesario, ya que todavía obtienes el intercepto + coeficiente sin él
Chris
@ Chris Bastante seguro de que no es una respuesta viable. Debe haber alguna entrada de stdin o como argumento de función.
Billywob
Bastante justo, solo mi lectura de la pregunta: también ofrece una comparación más justa con las respuestas de Python + octava
Chris
5

Python, 82 80 bytes

-2 bytes gracias a @Mego

Utilizando scipy:

import scipy
lambda s:scipy.stats.linregress(range(len(s)),list(map(ord,s)))[:2]
dfernan
fuente
Se permiten lambdas sin nombre, por lo que puede soltar el f=.
Mego
@DigitalTrauma numpy.linalg.lstsqaparentemente difiere en argumentos scipy.stats.linregressy es más complejo.
dfernan
4

Mathematica, 31 bytes

Fit[ToCharacterCode@#,{1,x},x]&

Función sin nombre que toma una cadena como entrada y devuelve la ecuación real de la línea de mejor ajuste en cuestión. Por ejemplo, f=Fit[ToCharacterCode@#,{1,x},x]&; f["meta.codegolf.stackexchange.com"]vuelve 99.2516 + 0.0145161 x.

ToCharacterCodeconvierte una cadena ASCII en una lista de los valores ASCII correspondientes; de hecho, por defecto es UTF-8 de manera más general. (Un poco triste, en este contexto, que el nombre de una función comprende más del 48% de la longitud del código ...) Y Fit[...,{1,x},x]es el incorporado para calcular la regresión lineal.

Greg Martin
fuente
1
Gracias por el ejemplo de la línea indexada 1, no tuve que calcularla debido a ti jaja.
Urna de pulpo mágico el
4

Node.js, 84 bytes

Utilizando regression:

s=>require('regression')('linear',s.split``.map((c,i)=>[i,c.charCodeAt()])).equation

Manifestación

// polyfill, since this is clearly not Node.js
function require(module) {
  return window[module];
}
// test
["meta.codegolf.stackexchange.com"].forEach(function test(string) {
  console.log(string);
  console.log(this(string));
},
// submission
s=>require('regression')('linear',s.split``.map((c,i)=>[i,c.charCodeAt()])).equation
);
<script src="https://cdn.rawgit.com/Tom-Alexander/regression-js/master/src/regression.js"></script>

Patrick Roberts
fuente
3

Sabio, 76 bytes

var('m','c')
y(x)=m*x+c
f=lambda x:find_fit(zip(range(len(x)),map(ord,x)),y)

Casi ningún juego de golf, probablemente más que una respuesta de Python, pero sí ...

busukxuan
fuente
2

J , 11 bytes

3&u:%.1,.#\

Esto usa indexación basada en uno.

Pruébalo en línea!

Explicación

3&u:%.1,.#\  Input: string S
         #\  Get the length of each prefix of S
             Forms the range [1, 2, ..., len(S)]
      1,.    Pair each with 1
3&u:         Get the ASCII value of each char in S
    %.       Matrix divide
millas
fuente
2

JavaScript, 151148 bytes

s=>([a,b,c,d,e]=[].map.call(s,c=>c.charCodeAt()).reduce(([a,b,c,d,e],y,x)=>[a+1,b+x,c+x*x,d+y,e+x*y],[0,0,0,0,0]),[k=(e*a-b*d)/(c*a-b*b),(d-k*b)/a])

Más legible:

Markus Jarderot
fuente
Puede guardar un byte mediante la eliminación 0de c.charCodeAt(0), y otros 2 bytes moviendo el k=...grupo de coma y ponerlo directamente en el primer índice de la matriz devuelta como[k=...,(d-k*b)/a]
Patrick Roberts
2

Javascript (ES6), 112 bytes

s=>[m=(a=b=c=d=0,([...s].map((u,x)=>{a+=n=x,b+=y=u.charCodeAt(),c+=x*x,d+=x*y}),++n)*d-a*b)/(n*c-a*a),b/n-m*a/n]

F=s=>[m=(a=b=c=d=0,([...s].map((u,x)=>{a+=n=x,b+=y=u.charCodeAt(),c+=x*x,d+=x*y}),++n)*d-a*b)/(n*c-a*a),b/n-m*a/n]

const update = () => {
  console.clear();
  console.log(F(input.value));
};
input.oninput = update;
update();
#input {
  width: 100%;
  box-sizing: border-box;
}
<input id="input" type="text" value="meta.codegolf.stackexchange.com" length=99/>
<div id="output"></div>

George Reith
fuente
2

Haskell, 154 142 bytes

import Statistics.LinearRegression
import Data.Vector
g x=linearRegression(generate(Prelude.length x)i)$i.fromEnum<$>fromList x
i=fromIntegral

Es demasiado largo para mi gusto debido a las importaciones y nombres largos de funciones, pero bueno. No se me ocurrió ningún otro método de golf, aunque no soy un experto en el área de las importaciones de golf.

Se eliminaron 12 bytes al reemplazarlos ordy la importación de Data.CharfromEnum gracias a nimi.

Renzeee
fuente
1
Puede reemplazar ordcon fromEnumy deshacerse de él import Data.Char.
nimi
1

Lenguaje de macros SAS, 180 bytes

Utiliza indexación basada en 1. La solución se vuelve bastante prolija cuando la salida es solo la pendiente y la intersección.

%macro t(a);data w;%do i=1 %to %length(&a);x=&i;y=%sysfunc(rank(%substr(&a,&i,1)));output;%end;run;proc reg outtest=m;model y=x/noprint;run;proc print data=m;var x intercept;%mend;
J_Lard
fuente
1

Clojure, 160 bytes

Sin elementos integrados, utiliza el algoritmo iterativo descrito en el artículo de Perceptron . Es posible que no converja en otras entradas, en ese caso, reduzca la tasa de aprendizaje 2e-4y quizás aumente el recuento de iteraciones 1e5. No estoy seguro si el algoritmo no iterativo hubiera sido más corto de implementar.

#(nth(iterate(fn[p](let[A apply e(for[x(range(count %))](-(int(get % x))(*(p 1)x)(p 0)))](mapv(fn[p e](+(* e 2e-4)p))p[(A + e)(A +(map *(range)e))])))[0 0])1e5)

Ejemplo:

(def f #( ... ))
(f "meta.codegolf.stackexchange.com")

[99.26612903225386 0.014516129032464659]
NikoNyrh
fuente
1

Arce, 65 bytes

Statistics:-LinearFit(b*x+a,[$(1..length(s))],convert(s,bytes),x)

Uso:

s := "meta.codegolf.stackexchange.com";
Statistics:-LinearFit(b*x+a,[$(1..length(s))],convert(s,bytes),x);

Devoluciones:

99.2516129032259+0.0145161290322573*x

Notas: Utiliza el comando Ajustar para ajustar un polinomio de la forma a * x + b a los datos. Los valores ASCII para la cadena se encuentran convirtiendo a bytes.

DSkoog
fuente