Desafio

Dadas duas IDs de perguntas, tente descobrir o quão semelhantes elas são olhando as respostas.

Detalhes

Você receberá dois IDs de perguntas para codegolf.stackexchange.com; você pode assumir que existem perguntas para os dois IDs que não foram excluídos, mas não necessariamente abertos. Você deve examinar todas as respostas e determinar a distância mínima de Levenshtein entre o código nas respostas às duas perguntas (sem incluir as respostas excluídas). Ou seja, você deve comparar todas as respostas da pergunta 1 com todas as respostas da questão 2 e determinar a distância mínima de Levenshtein. Para encontrar o código em uma resposta, assuma o seguinte procedimento:

Como encontrar o trecho de código

Um corpo de texto é o código real da resposta se estiver em backticks e estiver em sua própria linha, ou se for recuado com 4 espaços, com uma linha vazia acima, a menos que não haja texto acima.

Exemplos de trechos de código válidos e não válidos (com .um espaço) (separados por uma tonelada de sinais de igual)

This is `not a valid code snippet because it is not on its own line`
========================================
This is:
`A valid code snippet`
========================================
This is
....not a valid code snippet because there's no spacing line above
========================================
This is

....A valid code snippet because there's a spacing line above
========================================
....Valid code snippet because there's no other text
========================================

Se não houver trechos de código válidos na resposta, ignore-a completamente. Observe que você só deve pegar o primeiro código de bloqueio.

Especificações finais

Os dois IDs de perguntas podem ser inseridos em qualquer formato razoável para 2 números inteiros. A saída deve ser a menor distância de Levenshtein entre as duas respostas válidas de qualquer desafio. Se não houver respostas "válidas" para um ou ambos os desafios, produza -1.

Caso de teste

Para o desafio 115715(Embedded Hexagons) e 116616(Embedded Triangles), ambos do camarada SparklePony, as duas respostas de carvão (ambas da KritixiLithos) tinham uma distância de Levenshtein de 23, a menor. Assim, sua saída para 115715, 116616seria 23.

Editar

Você pode supor que a pergunta tenha no máximo 100 respostas devido a uma restrição de tamanho de página da API. Você não deve ignorar backticks em blocos de código, apenas se o próprio bloco de código for criado usando backticks e não em sua própria linha.

Editar

Eu encerrei o período de recompensa mais cedo porque fiz um pedido a um mod para obter uma suspensão de uma semana e não queria que a recompensa fosse automaticamente atribuída à resposta com a pontuação mais alta (que é a mais longa). Se uma nova submissão for recebida ou uma submissão for golfed o suficiente para se tornar menor que 532 bytes antes do final do período de recompensa (UTC 00:00 em 1º de junho), darei a ela uma recompensa para permanecer fiel à minha promessa, depois a suspensão expira. Se bem me lembro, preciso dobrar o período de recompensa na próxima vez. Se você receber uma resposta, poderá receber +200 :)

PowerShell, 532 bytes

$1,$2=$args
$a={irm "api.stackexchange.com/2.2/questions/$args/answers?pagesize=100&site=codegolf&filter=!9YdnSMKKT"|% i*}
$r={$args.body-replace"(?sm).*?^(<pre.*?>)?<code>(.*?)</code>.*",'$2'}
$1=&$a $1;$2=&$a $2
(0..($1.count-1)|%{
    $c=&$r $1[$_]
    0..($2.count-1)|%{
        &{$c,$d=$args;$e,$f=$c,$d|% le*;$m=[object[,]]::new($f+1,$e+1);0..$e|%{$m[0,$_]=$_};0..$f|%{$m[$_,0]=$_};1..$e|%{$i=$_;1..$f|%{$m[$_,$i]=(($m[($_-1),$i]+1),($m[$_,($i-1)]+1),($m[($_-1),($i-1)]+((1,0)[($c[($i-1)]-eq$d[($_-1)])]))|sort)[0]}};$m[$f,$e]} $c $d
    }
}|sort)[0]

Deixei novas linhas para facilitar a leitura. Ainda estão refletidos na minha contagem de bytes.

Tenho certeza de que tenho uma noção disso. A parte mais difícil para mim foi obter a distância de Levenshtein, já que o PowerShell não tem um built-in para isso até onde eu sei. Por causa disso, fui capaz de responder ao desafio relacionado à distância de Levenshtein . Quando meu código se refere a uma função anônima do LD, você pode consultar essa resposta para obter uma explicação mais detalhada de como isso funciona.

Código com comentários e indicador de progresso

O código pode ficar muito lento (por causa do LD), então eu criei alguns indicadores de progresso para poder seguir a ação conforme ela se desenrolava e não assumir que ela estava presa em um loop em algum lugar. O código para monitorar o progresso não está no bloco superior nem é contado na minha contagem de bytes.

# Assign the two integers into two variables. 
$1,$2=$args

# Quick function to download up to 100 of the answer object to a given question using the SE API
$a={irm "api.stackexchange.com/2.2/questions/$args/answers?pagesize=100&site=codegolf&filter=!9YdnSMKKT"|% i*}

# Quick function that takes the body (as HTML) of an answer and parses out the likely codeblock from it. 
$r={$args.body-replace"(?sm).*?^(<pre.*?>)?<code>(.*?)</code>.*",'$2'}

# Get the array of answers from the two questions linked.
$1=&$a $1;$2=&$a $2

# Hash table of parameters used for Write-Progress
# LD calcuations can be really slow on larger strings so I used this for testing so I knew 
# how much longer I needed to wait.
$parentProgressParameters = @{
    ID = 1 
    Activity = "Get LD of all questions" 
    Status = "Counting poppy seeds on the bagel"
}

$childProgressParameters = @{
    ID = 2
    ParentID = 1
    Status = "Progress"
}


# Cycle each code block from each answer against each answer in the other question.
(0..($1.count-1)|%{
    # Get the code block from this answer
    $c=&$r $1[$_]

    # Next line just for displaying progress. Not part of code. 
    Write-Progress @parentProgressParameters -PercentComplete (($_+1) / $1.count * 100) -CurrentOperation "Answer $($_+1) from question 1"

    0..($2.count-1)|%{
        # Get the code block from this answer   
        $d=&$r $2[$_]

        # Next two lines are for progress display. Not part of code. 
        $childProgressParameters.Activity = "Comparing answer $($_+1) of $($2.count)"
        Write-Progress @childProgressParameters -PercentComplete (($_+1) / $2.count * 100) -CurrentOperation "Answer $($_+1) from question 2"

        # Anonymous function to calculate Levenstien Distance
        # Get a better look at that function here: /codegolf//a/123389/52023
        &{$c,$d=$args;$e,$f=$c,$d|% le*;$m=[object[,]]::new($f+1,$e+1);0..$e|%{$m[0,$_]=$_};0..$f|%{$m[$_,0]=$_};1..$e|%{$i=$_;1..$f|%{$m[$_,$i]=(($m[($_-1),$i]+1),($m[$_,($i-1)]+1),($m[($_-1),($i-1)]+((1,0)[($c[($i-1)]-eq$d[($_-1)])]))|sort)[0]}};$m[$f,$e]} $c $d
    }
# Collect results and sort leaving the smallest number on top.
}|sort)[0]

Minha lógica para encontrar os blocos de código é pegar a resposta como HTML e procurar um conjunto de tags de código, opcionalmente cercado por um conjunto de pré tags que começa em sua própria linha. Ao testar, encontrou todos os dados corretos em 6 conjuntos de perguntas diferentes.

Tentei trabalhar com o código de remarcação, mas era muito difícil encontrar o bloco de código certo.

Execuções de amostra

Challenge-Similarity-Detector 97752 122740
57

Challenge-Similarity-Detector 115715 116616
23

Java + Jsoup, 1027 bytes

Os dois primeiros argumentos são os IDs da pergunta.

Golfe:

import org.jsoup.*;import org.jsoup.nodes.*;class M{String a1[]=new String[100],a2[]=new String[100],c[];int i1=0,i2=0;public static void main(String a[])throws Exception{String r="/codegolf/";M m=new M();m.c=m.a1;m.r(Jsoup.connect(r+a[0]).get());m.c=m.a2;m.r(Jsoup.connect(r+a[1]).get());int s=m.ld(m.a1[1],m.a2[1]);for(int i=2;i<m.a1.length;i++)for(int j=2;j<m.a2.length;i++){if(m.a1[i]==null)break;int d=m.ld(m.a1[i],m.a2[j]);if(d<s)s=d;}System.out.print(s);}void r(Document d){a:for(Element e:d.select("td")){for(Element p:e.select("pre")){ a(p.select("code").get(0).html());continue a;}}}void a(String d){c[c==a1?i1++:i2++]=d;}int ld(String a,String b){a=a.toLowerCase();b=b.toLowerCase();int[]costs=new int[b.length()+1];for(int j=0;j<costs.length;j++)costs[j]=j;for(int i=1;i<=a.length();i++){costs[0]=i;int nw=i-1;for(int j=1;j<=b.length();j++){int cj=Math.min(1+Math.min(costs[j],costs[j-1]),a.charAt(i-1)==b.charAt(j-1)?nw:nw+1);nw=costs[j];costs[j]=cj;}}return costs[b.length()];}}

Legível:

import org.jsoup.*;import org.jsoup.nodes.*;

class M {
    String a1[]=new String[100],a2[]=new String[100],c[];
    int i1=0,i2=0;
    public static void main(String a[])throws Exception{
    String r="/codegolf/";
    M m=new M();

    m.c=m.a1;
    m.r(Jsoup.connect(r+a[0]).get());
    m.c=m.a2;
    m.r(Jsoup.connect(r+a[1]).get());

    int s=m.ld(m.a1[1],m.a2[1]);
    for(int i=2;i<m.a1.length;i++)for(int j=2;j<m.a2.length;i++){if(m.a1[i]==null)break;int d=m.ld(m.a1[i],m.a2[j]);if(d<s)s=d;}
    System.out.print(s);
}

void r(Document d) {
    a:for(Element e:d.select("td")) {for(Element p:e.select("pre")) { 
        a(p.select("code").get(0).html());
        continue a;
    }}
}

void a(String d){c[c==a1?i1++:i2++]=d;}

int ld(String a, String b) {
    a = a.toLowerCase();
    b = b.toLowerCase();
    int [] costs = new int [b.length() + 1];
    for (int j = 0; j < costs.length; j++)costs[j] = j;
    for (int i = 1; i <= a.length(); i++) {
        costs[0] = i;
        int nw = i - 1;
        for (int j = 1; j <= b.length(); j++) {
            int cj = Math.min(1 + Math.min(costs[j], costs[j - 1]), a.charAt(i - 1) == b.charAt(j - 1) ? nw : nw + 1);
            nw = costs[j];
            costs[j] = cj;
        }
    }
    return costs[b.length()];
}

}

Mathematica, 540 bytes

f=Flatten;l=Length;P=StringPosition;(H[r_]:=Block[{s,a,t,k},t={};d=1;k="/codegolf/"<>r;s=First/@P[Import[k,"Text"],"<pre><code>"];a=f[First/@P[Import[k,"Text"],"answerCount"]][[1]];While[d<l@s,If[s[[d]]>a,AppendTo[t,s[[d]]]];d++];Table[StringDelete[StringCases[StringTake[Import[k,"Text"],{t[[i]],t[[i]]+200}],"<pre><code>"~~__~~"</code></pre>"],{"<pre><code>","</code></pre>"}],{i, l@t}]];Min@DeleteCases[f@Table[EditDistance[ToString@Row@H[#1][[i]],ToString@Row@H[#2][[j]]],{i,l@H[#1]},{j,l@H[#1]}],0])&

entrada

["115715", "116616"]

resultado

23

usa EditDistance interno que "fornece a distância de edição ou Levenshtein entre cadeias ou vetores u e v".

Quanto ao caso de teste mathematica

EditDistance["ＦＮ«ＡＸ²ιβ×__β↓↘β←↙β↑←×__β↖β→↗β","ＮαＷα«Ｘ²ι↙ＡＸ²⁻ι¹β↙β↑↖β→Ａ⁻α¹α"]

retorna 23

Acho que posso jogar um pouco mais de golfe
Leva alguns minutos para correr