Детектор сходства вызовов

11

Вызов

Учитывая два идентификатора вопроса, попытайтесь выяснить, насколько они похожи, посмотрев на ответы.

подробности

Вам дадут два идентификатора вопроса для codegolf.stackexchange.com; Вы можете предположить, что для обоих идентификаторов существуют вопросы, которые не удалены, но не обязательно открыты. Вы должны просмотреть все ответы и определить минимальное расстояние Левенштейна между кодом в ответах на два вопроса (не считая удаленных ответов). То есть вы должны сравнить каждый ответ в вопросе 1 с каждым ответом в вопросе 2 и определить минимальное расстояние Левенштейна. Чтобы найти код в ответе, выполните следующую процедуру:

Как найти фрагмент кода

Тело текста - это фактический код ответа, если он в обратных чертах и ​​находится на отдельной строке или имеет отступ с 4 пробелами, с пустой строкой над ним, если над текстом нет текста.

Примеры допустимых и недействительных фрагментов кода (с .пробелом) (разделенных тонной знаков равенства)

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

Если в ответе нет действительных фрагментов кода, полностью проигнорируйте ответ. Обратите внимание, что вы должны взять только первый кодовый блок.

Финальные характеристики

Два идентификатора вопроса могут быть введены в любом разумном формате для 2 целых чисел. Выходными данными должно быть наименьшее расстояние Левенштейна между любыми двумя действительными ответами на любой вопрос. Если для одной или обеих задач нет «правильных» ответов, выведите результат -1.

Прецедент

Для задания 115715(встроенные шестиугольники) и 116616(встроенные треугольники), оба от товарища SparklePony, два ответа на уголь (оба от KritixiLithos) имели расстояние Левенштейна 23, которое было наименьшим. Таким образом, ваш вывод для 115715, 116616будет 23.

редактировать

Вы можете предположить, что на вопрос имеется не более 100 ответов из-за ограничения размера страниц API. Вы не должны игнорировать обратные пометки в блоках кода, только если сам кодовый блок создан с использованием обратных ударов, а не в отдельной строке.

редактировать

Я досрочно завершил период вознаграждения, потому что я обратился к моду с просьбой о приостановке на одну неделю, и я не хотел, чтобы вознаграждение автоматически присваивалось за ответ с наивысшим баллом (который оказывается самым длинным). Если поступит новая заявка или заявка окажется в гольфе достаточно для того, чтобы стать короче, чем 532 байта до фактического окончания периода вознаграждения (UTC 00:00 1 июня), я дам эту награду, чтобы остаться верной моему обещанию, после того, как срок приостановки истекает. Если я правильно помню, мне нужно удвоить период вознаграждения в следующий раз, так что если вы получите ответ, вы можете получить +200 :)

HyperNeutrino
источник
1
Я смущен тем, что считается допустимым фрагментом кода. Почему бы просто не использовать теги <code> в html?
Увлечения Кэлвина
@HelkaHomba А как насчет ограничений новой строки? Я мог бы попытаться найти другой способ включить их.
HyperNeutrino
@HelkaHomba По сути, если ответ содержит код, разделенный обратным знаком, в строке, его следует игнорировать.
HyperNeutrino
Это один из тех ответов, где легче сделать основную часть вопроса. Загрузка страницы и извлечение блоков кода сложнее, чем прохождение дистанции Левенштейна.
Bálint
1
Здорово. Просто проверяю.
Мэтт

Ответы:

1

PowerShell, 532 байта

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

Я оставил там новые строки для удобства чтения. Они все еще отражены в моем количестве байтов.

Уверен, я справлюсь с этим. Самым сложным для меня было получить расстояние Левенштейна, поскольку PowerShell, насколько я знаю, не имеет встроенного средства для этого. Благодаря этому я смог ответить на соответствующий вызов на расстоянии Левенштейна . Когда мой код ссылается на анонимную функцию для LD, вы можете обратиться к этому ответу для более подробного объяснения того, как это работает.

Код с комментариями и индикатором прогресса

Код может стать очень медленным (из-за LD), поэтому я встроил некоторые индикаторы прогресса для себя, чтобы я мог следить за действием по мере его разворачивания и не предполагать, что он где-то застрял в цикле. Код для отслеживания прогресса не находится в верхнем блоке и не учитывается в моем количестве байтов.

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

Моя логика для поиска блоков кода заключается в том, чтобы принимать ответ в виде HTML и искать набор тегов кода, опционально окруженный набором предварительных тегов, который начинается в отдельной строке. При тестировании он нашел все правильные данные по 6 различным наборам вопросов.

Я пытался работать с кодом уценки, но было слишком сложно найти правильный блок кода.

Пробные прогоны

Challenge-Similarity-Detector 97752 122740
57

Challenge-Similarity-Detector 115715 116616
23
Matt
источник
Я потратил лучшую часть 3 дня, изучая это. Это испытание входит в мою пятерку самых забавных. TFTC (спасибо за вызов)
Мэтт
Хорошая работа! Спасибо, я рад, что вам понравилось! :)
HyperNeutrino
Примечание. Я назначил награду раньше, чем было заявлено, потому что я запрашиваю приостановку, поэтому не могу назначить ее позже. Отличная работа! :)
HyperNeutrino
Запрос приостановки?
Мэтт
Да, я попросил Денниса отложить мне 1 неделю, чтобы я мог сосредоточиться на учебе. Это было сделано раньше (хотя я все еще здесь ... Я не знаю, когда исчезну).
HyperNeutrino
3

Java + Jsoup, 1027 байт

Первые два аргумента являются идентификаторами вопроса.

Golfed:

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

Удобочитаемый:

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

}

Tomahawk2001913
источник
бей меня к этому !!!! Ницца!
tuskiomi
1
Добро пожаловать в PPCG! Это не противоречит правилам использования сторонней библиотеки, но мы требуем, чтобы использование библиотеки отмечалось языком (поэтому ответ Java, использующий библиотеку JavaHTML, будет помечен как «Java + JavaHTML»).
Мего
Хорошо спасибо! Я буду помнить это в следующий раз!
Томагавк2001913
Ничто не мешает вам использовать библиотеку в этом испытании, если вы захотите.
Мэтт
Возможно, мне придется теперь, когда кто-то возглавил мой ответ!
Томагавк2001913
0

Mathematica, 540 байт

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


вход

["115715", "116616"]

выход

23

использует встроенный EditDistance, который «дает правку или расстояние Левенштейна между строками или векторами u и v».

Что касается теста Mathematica

EditDistance["FN«AX²ιβ×__β↓↘β←↙β↑←×__β↖β→↗β","NαWα«X²ι↙AX²⁻ι¹β↙β↑↖β→A⁻α¹α"]

возвращает 23

Я думаю, я могу играть в гольф немного больше.
Занимает несколько минут, чтобы бежать

J42161217
источник