Regressão linear em uma string

25

Esse desafio é um pouco complicado, mas bastante simples, dada uma sequência s:

meta.codegolf.stackexchange.com

Use a posição do caractere na string como xcoordenada e o valor ascii como ycoordenada. Para a sequência acima, o conjunto resultante de coordenadas seria:

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

Em seguida, você deve calcular a inclinação e o intercepto em y do conjunto que você obteve usando a regressão linear , aqui está o conjunto acima plotado:

Enredo

O que resulta em uma linha de melhor ajuste (indexada 0):

y = 0.014516129032258x + 99.266129032258

Aqui está a linha de melhor ajuste indexada em 1 :

y = 0.014516129032258x + 99.251612903226

Portanto, seu programa retornaria:

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

Ou (qualquer outro formato sensível):

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

Ou (qualquer outro formato sensível):

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

Ou (qualquer outro formato sensível):

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

Apenas explique por que está retornando nesse formato, se não for óbvio.


Algumas regras de esclarecimento:

- 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).

São as vitórias mais baixas em contagem de bytes do .

Urna de polvo mágico
fonte
3
Você tem algum link / fórmula para calcular a inclinação e a interceptação em y?
Rod
16
Caros eleitores pouco claros: Embora eu concorde que é bom ter a fórmula, ela não é de forma alguma necessária. A regressão linear é uma coisa bem definida no mundo matemático, e o OP pode querer deixar de encontrar a equação para o leitor.
Nathan Merrill
2
Tudo bem retornar a equação real da linha de melhor ajuste, como 0.014516129032258x + 99.266129032258?
Greg Martin
2
O título deste desafio colocou essa música maravilhosa na minha cabeça pelo resto do dia
Luis Mendo

Respostas:

2

MATL , 8 bytes

n:G3$1ZQ

A indexação de string com base em 1 é usada.

Experimente online!

Explicação

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
fonte
7

Oitava, 29 26 24 20 bytes

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

Experimente Online!

Nós temos o modelo

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

Aqui y está o valor ASCII da strings

Para encontrar parâmetros de interceptação e inclinação, podemos formar a seguinte equação:

s = [intercept slope] * [1 X]

então

[intercept slope] = s/[1 x]

!!sconverte uma string em um vetor de uns com o mesmo comprimento que a string.
O vetor de uns é usado para estimar a interceptação.
1:nnz(s)é o intervalo de valores de 1 a número de elementos da sequência usada como x.

Resposta anterior

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

Para teste, cole o seguinte código no Octave Online

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

Uma função que aceita uma string como entrada e aplica uma estimativa ordinária de mínimos quadrados do modelo y = x*b + e

O primeiro argumento de ols é yque, para isso, transpomos a string se adicionamos com o número 0 para obter seu código ASCII.

rahnema1
fonte
/, boa ideia!
Luis Mendo
6

TI-Basic, 51 (+ 141) bytes

As strings são baseadas em 1 no 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)

Como no outro exemplo, isso gera a equação da linha de melhor ajuste, em termos de X. Além disso, em Str2, você precisa ter essa sequência, que é de 141 bytes no TI-Basic:

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

A razão pela qual isso não pode fazer parte do programa é porque dois caracteres no TI-Basic não podem ser adicionados automaticamente a uma sequência. Uma é a STO->seta, mas isso não é um problema, porque não faz parte do ASCII. A outra é a string literal ( "), que pode ser modificada apenas digitando em uma Y=equação e usando Equ>String(.

Timtech
fonte
Eu estava seriamente me perguntando se alguém iria quebrar suas calculadoras antigas para isso :). Eu tinha minha antiga TI-83 em mente quando pensei nisso.
Magic Octopus Urn
@carusocomputing Ei, que bom! Gosto muito da linguagem de programação TI-Basic e a uso em muitos dos meus campos de golfe de código. Se apenas apoiou ASCII ...
Timtech
Dois comentários: 1, você pode especificar ", solicitando também a entrada do usuário em um programa, o que não ajuda aqui, mas eu só queria apontar esse fato. 2, não reconheço alguns desses caracteres como existentes na calculadora. Eu posso estar errado, mas por exemplo, onde você consegue @e ~? Bem como #, $e &.
Patrick Roberts
Obrigado pelo comentário, @PatrickRoberts. Esses são tokens de dois bytes começando com 0xBB. Procure na coluna D de tibasicdev.wikidot.com/misc Miscellaneous
tokens #
6

R, 46 45 bytes

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

Lê a entrada de stdin e para os retornos de caso de teste fornecidos (um indexado):

(Intercept)           x 
99.25161290  0.01451613 
Billywob
fonte
Um pouco mais curto (mas não testado, possivelmente com alguns problemas de avaliação na análise da fórmula):lm(utf8ToInt(y<-scan(,""))~1:nchar(y))$co
rturnbull 10/01
@rturnbull Eu tentei isso no começo, mas parece que a xvariável precisa ser predefinida para lmfuncionar.
Billywob
@rturnbull Recebo uma variável comprimentos diferem erro nisso. Nos é dado, sportanto, x=1:nchar(s);lm(charToRaw(s)~x)$cosalva alguns bytes. Eu também não sei se o $coé tecnicamente necessário, como você ainda obter o coeficiente de intercepção + sem ele
Chris
@ Chris Com certeza, essa não é uma resposta viável. Deve haver alguma entrada do stdin ou como um argumento de função.
precisa saber é o seguinte
É justo, apenas a minha leitura da pergunta - ela também oferece uma comparação mais justa com as respostas python + oitava #
Chris
5

Python, 82 80 bytes

-2 bytes graças a @Mego

Usando scipy:

import scipy
lambda s:scipy.stats.linregress(range(len(s)),list(map(ord,s)))[:2]
dfernan
fonte
Lambdas sem nome são permitidas, para que você possa soltar o f=.
Mego
O @DigitalTrauma numpy.linalg.lstsqaparentemente difere em argumentos scipy.stats.linregresse é mais complexo.
dfernan
4

Mathematica, 31 bytes

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

Função sem nome, usando uma string como entrada e retornando a equação real da linha de melhor ajuste em questão. Por exemplo, f=Fit[ToCharacterCode@#,{1,x},x]&; f["meta.codegolf.stackexchange.com"]retorna 99.2516 + 0.0145161 x.

ToCharacterCodeconverte uma string ASCII em uma lista dos valores ASCII correspondentes; na verdade, o padrão é UTF-8 de maneira mais geral. (É meio triste, nesse contexto, que um nome de função represente mais de 48% do comprimento do código ....) E Fit[...,{1,x},x]é o componente interno para calcular a regressão linear.

Greg Martin
fonte
1
Obrigado pelo exemplo da linha indexada em 1, não precisei calculá-lo por sua causa haha.
Magic Octopus Urn
4

Node.js, 84 bytes

Usando regression:

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

Demo

// 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
fonte
3

Sábio, 76 bytes

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

Dificilmente qualquer jogador de golfe, provavelmente mais do que uma resposta em Python, mas sim ...

busukxuan
fonte
2

J , 11 bytes

3&u:%.1,.#\

Isso usa indexação baseada em um.

Experimente online!

Explicação

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
milhas
fonte
2

JavaScript, 151 148 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])

Mais legível:

Markus Jarderot
fonte
Você pode salvar um byte através da remoção 0de c.charCodeAt(0), e mais 2 bytes movendo o k=...grupo vírgula e colocá-lo diretamente no primeiro índice do array retornado 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
fonte
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

É muito longo para os meus gostos por causa das importações e nomes de funções longos, mas também. Eu não conseguia pensar em nenhum outro método de golfe restante, embora eu não seja especialista na área de importações de golfe.

Retirou 12 bytes substituindo orde importando de Data.CharfromEnum graças a nimi.

Renzeee
fonte
1
Você pode substituir ordcom fromEnume se livrar import Data.Char.
nimi
1

Linguagem de Macro SAS, 180 bytes

Usa indexação baseada em 1. A solução fica bastante prolixo quando a saída é apenas a inclinação e a interceptação.

%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
fonte
1

Clojure, 160 bytes

Sem built-ins, usa o algoritmo iterativo descrito no artigo da Perceptron . Pode não convergir para outras entradas, nesse caso, diminuir a taxa de aprendizado 2e-4e talvez aumentar a contagem de iterações 1e5. Não tenho certeza se o algoritmo não iterativo teria sido mais curto 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)

Exemplo:

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

[99.26612903225386 0.014516129032464659]
NikoNyrh
fonte
1

Bordo, 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);

Devoluções:

99.2516129032259+0.0145161290322573*x

Notas: Isso usa o comando Ajustar para ajustar um polinômio do formato a * x + b aos dados. Os valores ASCII para a cadeia são encontrados convertendo para bytes.

DSkoog
fonte