Desafío

Dadas dos ID de preguntas, intente averiguar qué tan similares son mirando las respuestas.

Detalles

Se le darán dos ID de preguntas para codegolf.stackexchange.com; puede suponer que existen preguntas para ambas ID que no se eliminan, pero que no están necesariamente abiertas. Debe revisar todas las respuestas y determinar la distancia mínima de Levenshtein entre el código en las respuestas a las dos preguntas (sin incluir las respuestas eliminadas). Es decir, debe comparar cada respuesta en la pregunta 1 con cada respuesta en la pregunta 2, y determinar la distancia mínima de Levenshtein. Para encontrar el código en una respuesta, asuma el siguiente procedimiento:

Cómo encontrar el fragmento de código

Un cuerpo de texto es el código real de la respuesta si está en backticks y está en su propia línea, o si está sangrado con 4 espacios, con una línea vacía encima, a menos que no haya texto arriba.

Ejemplos de fragmentos de código válidos y no válidos (con .un espacio) (separados por una tonelada de signos iguales)

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

Si no hay fragmentos de código válidos en la respuesta, ignore la respuesta por completo. Tenga en cuenta que solo debe tomar el primer bloque de código.

Especificaciones finales

Las dos ID de preguntas se pueden ingresar en cualquier formato razonable para 2 enteros. El resultado debe ser la distancia de Levenshtein más pequeña entre dos respuestas válidas de cualquier desafío. Si no hay respuestas "válidas" para uno o ambos desafíos, salida -1.

Caso de prueba

Para el desafío 115715(Hexágonos incrustados) y 116616(Triángulos incrustados), ambos del camarada SparklePony, las dos respuestas de carbón (ambas de KritixiLithos) tenían una distancia de Levenshtein de 23, que era la más pequeña. Por lo tanto, su salida para 115715, 116616sería 23.

Editar

Puede suponer que la pregunta tiene como máximo 100 respuestas debido a una restricción de tamaño de página API. No debe ignorar los backticks en los bloques de código, solo si el bloque de código en sí se crea usando backticks y no en su propia línea.

Editar

Terminé el período de recompensa temprano porque solicité a un mod para obtener una suspensión de una semana y no quería que la recompensa se otorgara automáticamente a la respuesta de mayor puntuación (que es la más larga). Si llega una nueva presentación o si una presentación es lo suficientemente mejorada como para ser más corta que 532 bytes antes del final del período de recompensa (UTC 00:00 el 1 de junio), le daré una recompensa para cumplir con mi promesa, después La suspensión expira. Si no recuerdo mal, necesito duplicar el período de recompensa la próxima vez, así que si recibes una respuesta, podrías obtener +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]

Dejé nuevas líneas allí para cierta legibilidad. Todavía se reflejan en mi recuento de bytes.

Estoy bastante seguro de que tengo un control sobre esto. La parte más difícil para mí fue obtener la distancia de Levenshtein ya que PowerShell no tiene una capacidad incorporada para eso, que yo sepa. Por eso pude responder al desafío relacionado con la distancia de Levenshtein . Cuando mi código se refiere a una función anónima para LD, puede consultar esa respuesta para obtener una explicación más detallada de cómo funciona.

Código con comentarios e indicador de progreso

El código puede volverse muy lento (debido al LD), así que construí algunos indicadores de progreso por mí mismo para poder seguir la acción a medida que se desarrollaba y no asumir que estaba atrapada en un bucle en alguna parte. El código para monitorear el progreso no se encuentra en el bloque superior ni se cuenta en mi recuento 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]

Mi lógica para encontrar los bloques de código es tomar la respuesta como HTML y buscar un conjunto de etiquetas de código, opcionalmente rodeado por un conjunto de etiquetas previas que comienza en su propia línea. En las pruebas, encontró todos los datos correctos en 6 conjuntos de preguntas diferentes.

Traté de trabajar desde el código de descuento, pero fue demasiado difícil encontrar el bloque de código correcto.

Ejecuciones de muestra

Challenge-Similarity-Detector 97752 122740
57

Challenge-Similarity-Detector 115715 116616
23

Java + Jsoup, 1027 bytes

Los primeros dos argumentos son los ID de las preguntas.

Golfizado:

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

Legible:

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"]

salida

23

usa EditDistance incorporado que "proporciona la distancia de edición o Levenshtein entre cadenas o vectores u y v".

En cuanto al caso de prueba Mathica

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

devuelve 23

Supongo que puedo jugar al golf un poco más.
Toma unos minutos correr