Wyzwanie Detektor podobieństwa

11

Wyzwanie

Biorąc pod uwagę dwa identyfikatory pytań, spróbuj dowiedzieć się, jak są one podobne, patrząc na odpowiedzi.

Detale

Otrzymasz dwa identyfikatory pytań codegolf.stackexchange.com; możesz założyć, że istnieją pytania dotyczące obu identyfikatorów, które nie zostały usunięte, ale niekoniecznie są otwarte. Musisz przejrzeć wszystkie odpowiedzi i określić minimalną odległość Levenshteina między kodem w odpowiedziach na dwa pytania (nie uwzględniając usuniętych odpowiedzi). Oznacza to, że powinieneś porównać każdą odpowiedź w pytaniu 1 z każdą odpowiedzią w pytaniu 2 i określić minimalną odległość Levenshteina. Aby znaleźć kod w odpowiedzi, załóż następującą procedurę:

Jak znaleźć fragment kodu

Treść tekstu jest faktycznym kodem odpowiedzi, jeśli znajduje się w odwrotnych wierszach i znajduje się we własnej linii lub jeśli jest wcięta 4 spacjami, z pustą linią nad nią, chyba że powyżej nie ma tekstu.

Przykłady poprawnych i niepoprawnych fragmentów kodu (ze .spacją) (oddzielonych toną znaków równości)

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

Jeśli w odpowiedzi nie ma poprawnych fragmentów kodu, całkowicie zignoruj ​​odpowiedź. Pamiętaj, że powinieneś wziąć tylko pierwszy kod.

Ostateczne specyfikacje

Dwa identyfikatory pytań można wprowadzić w dowolnym rozsądnym formacie dla 2 liczb całkowitych. Wynik powinien być najmniejszą odległością Levenshteina między dowolnymi dwoma prawidłowymi odpowiedziami z obu wyzwań. Jeśli nie ma „poprawnych” odpowiedzi dla jednego lub obu wyzwań, wynik -1.

Przypadek testowy

W przypadku wyzwania 115715(Embedded Hexagons) i 116616(Embedded Triangles) zarówno przez towarzysza SparklePony, dwie odpowiedzi na węgiel drzewny (oba przez KritixiLithos) miały odległość Levenshteina równą 23, co było najmniejsze. Zatem twój wynik 115715, 116616byłby 23.

Edytować

Możesz założyć, że pytanie ma maksymalnie 100 odpowiedzi z powodu ograniczenia rozmiaru strony API. Nie należy ignorować znaków wstecznych w blokach kodu, tylko jeśli sam blok kodu jest tworzony za pomocą znaków wstecznych, a nie we własnej linii.

Edytować

Okres nagród wygasłem wcześniej, ponieważ poprosiłem mod, aby uzyskał tygodniowe zawieszenie i nie chciałem, aby nagroda była automatycznie przyznawana za najwyższą odpowiedź (która jest najdłuższa). Jeśli nadejdzie nowe zgłoszenie lub zgłoszenie zostanie na tyle zagrane w golfa, że ​​będzie krótsze niż 532 bajty przed faktycznym końcem okresu nagród (UTC 00:00 w dniu 1 czerwca), dam nagrodę za dotrzymanie mojej obietnicy po zawieszenie wygasa. Jeśli dobrze pamiętam, następnym razem muszę podwoić okres nagrody, więc jeśli dostaniesz odpowiedź, możesz otrzymać +200 :)

HyperNeutrino
źródło
1
Jestem zdezorientowany tym, co liczy się jako prawidłowy fragment kodu. Dlaczego nie tylko to, co jest w tagach <code> w html?
Calvin's Hobbies
@HelkaHomba Co z ograniczeniami nowej linii? Mógłbym spróbować znaleźć inny sposób na ich włączenie.
HyperNeutrino
@HelkaHomba Zasadniczo, jeśli odpowiedź zawiera kod rozdzielany znakiem wstecz w wierszu, należy go zignorować.
HyperNeutrino
To jedna z tych odpowiedzi, w której łatwiej jest wykonać główną część pytania. Pobranie strony i wyodrębnienie bloków kodu jest trudniejsze niż zrobienie dystansu levenshtein.
Bálint
1
Fajne. Tylko sprawdzam.
Matt

Odpowiedzi:

1

PowerShell, 532 bajtów

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

Zostawiłem tam nowe wiersze dla pewnej czytelności. Są nadal odzwierciedlone w mojej liczbie bajtów.

Jestem całkiem pewien, że mam na to wpływ. Trudną częścią było dla mnie uzyskanie dystansu Levenshteina, ponieważ PowerShell nie ma wbudowanego do tego celu, o ile wiem. Dzięki temu mogłem odpowiedzieć na powiązane wyzwanie na dystansie Levenshtein . Kiedy mój kod odnosi się do anonimowej funkcji dla LD, możesz odnieść się do tej odpowiedzi, aby uzyskać bardziej szczegółowe wyjaśnienie, jak to działa.

Kod z komentarzami i wskaźnikiem postępu

Kod może być bardzo powolny (z powodu LD), więc wbudowałem dla siebie kilka wskaźników postępu, dzięki czemu mogłem śledzić akcję, gdy się rozwijała i nie zakładać, że utknął gdzieś w pętli. Kod monitorowania postępu nie znajduje się w górnym bloku ani nie jest liczony w mojej liczbie bajtów.

# 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: https://codegolf.stackexchange.com/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]

Moją logiką do znajdowania bloków kodu jest wzięcie odpowiedzi jako HTML i poszukiwanie zestawu znaczników kodu, opcjonalnie otoczonego przez zestaw znaczników wstępnych, który zaczyna się w swojej linii. Podczas testowania znalazł wszystkie prawidłowe dane w 6 różnych zestawach pytań.

Próbowałem pracować na podstawie kodu przeceny, ale znalezienie odpowiedniego bloku kodu było zbyt trudne.

Przykładowe przebiegi

Challenge-Similarity-Detector 97752 122740
57

Challenge-Similarity-Detector 115715 116616
23
Matt
źródło
Spędziłem większą część 3 dni, przyglądając się temu. To wyzwanie znajduje się w mojej pierwszej piątce, jeśli chodzi o najbardziej zabawne próby. TFTC (Dzięki za wyzwanie)
Matt
Dobra robota! Dzięki, cieszę się, że ci się podobało! :)
HyperNeutrino
Uwaga: Nagrodę przyznałem wcześniej niż podano, ponieważ żądam zawieszenia, więc nie mogę go później przyznać. Dobra robota! :)
HyperNeutrino
Żądasz zawieszenia?
Matt
Tak, poprosiłem Dennisa o tygodniowe zawieszenie, abym mógł skupić się na pracy szkolnej. Zrobiono to wcześniej (chociaż wciąż tu jestem ... Nie wiem, kiedy zniknę).
HyperNeutrino
3

Java + Jsoup, 1027 bajtów

Pierwsze dwa argumenty to identyfikatory pytań.

Gra w golfa:

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

Czytelny:

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
źródło
pobili mnie do tego !!!! Ładny!
tuskiomi
1
Witamy w PPCG! Korzystanie z biblioteki innej firmy nie jest sprzeczne z zasadami, ale wymagamy, aby użycie biblioteki było odnotowane w języku (więc odpowiedź Java, która korzysta z biblioteki o nazwie JavaHTML, będzie oznaczona jako „Java + JavaHTML”).
Mego
Ok dzięki! Będę o tym pamiętać następnym razem!
Tomahawk2001913
Nic nie stoi na przeszkodzie, abyś używał biblioteki w tym wyzwaniu, jeśli chcesz.
Matt
Być może muszę teraz, gdy ktoś przewyższy moją odpowiedź!
Tomahawk2001913
0

Mathematica, 540 bajtów

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


Wejście

[„115715”, „116616”]

wynik

23

wykorzystuje wbudowany EditDistance, który „podaje odległość edycji lub Levenshteina między łańcuchami lub wektorami u i v”.

Co do przypadku matematyki

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

zwraca 23

Chyba mogę trochę dłużej grać w golfa.
Trwa kilka minut

J42161217
źródło