Detektor Kesamaan Tantangan

11

Tantangan

Diberikan dua ID pertanyaan, cobalah untuk mencari tahu seberapa miripnya mereka dengan melihat jawabannya.

Detail

Anda akan diberikan dua ID pertanyaan untuk codegolf.stackexchange.com; Anda dapat berasumsi bahwa ada pertanyaan untuk kedua ID yang tidak dihapus, tetapi belum tentu terbuka. Anda harus menjalankan semua jawaban dan menentukan jarak Levenshtein minimum antara kode dalam jawaban untuk dua pertanyaan (tidak termasuk jawaban yang dihapus). Artinya, Anda harus membandingkan setiap jawaban dalam pertanyaan 1 dengan setiap jawaban dalam pertanyaan 2, dan menentukan jarak Levenshtein minimum. Untuk menemukan kode dalam jawaban, asumsikan prosedur berikut:

Cara menemukan cuplikan kode

Tubuh teks adalah kode jawaban yang sebenarnya jika berada di backtick dan berada pada barisnya sendiri, atau jika diindentasi dengan 4 spasi, dengan baris kosong di atasnya, kecuali tidak ada teks di atas.

Contoh cuplikan kode yang valid dan tidak valid (dengan .spasi) (dipisahkan oleh satu ton tanda sama dengan)

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

Jika tidak ada potongan kode yang valid dalam jawaban, abaikan jawaban sepenuhnya. Perhatikan bahwa Anda hanya harus mengambil kunci kode pertama.

Spesifikasi Akhir

Dua ID pertanyaan dapat dimasukkan dalam format apa pun yang masuk akal untuk 2 bilangan bulat. Outputnya harus menjadi jarak Levenshtein terkecil antara dua jawaban yang valid dari setiap tantangan. Jika tidak ada jawaban "valid" untuk satu atau kedua tantangan, keluaran -1.

Kasus cobaan

Untuk tantangan 115715(Embedded Hexagons) dan 116616(Embedded Triangles) baik oleh Kamerad SparklePony, kedua jawaban Charcoal (keduanya oleh KritixiLithos) memiliki jarak Levenshtein 23, yang merupakan yang terkecil. Dengan demikian, output Anda 115715, 116616akan menjadi 23.

Edit

Anda dapat berasumsi bahwa pertanyaan memiliki paling banyak 100 jawaban karena pembatasan pageize API. Anda tidak boleh mengabaikan backticks dalam blok kode, hanya jika blok kode itu sendiri dibuat menggunakan backticks dan bukan pada barisnya sendiri.

Edit

Saya mengakhiri periode bounty lebih awal karena saya meminta mod untuk mendapatkan penangguhan satu minggu dan saya tidak ingin bounty itu secara otomatis diberikan ke jawaban skor tertinggi (yang kebetulan paling lama). Jika kiriman baru masuk atau kiriman cukup golf untuk menjadi lebih pendek dari 532 byte sebelum akhir periode hadiah sebenarnya (UTC 00:00 pada 1 Juni), saya akan memberikan hadiah itu untuk tetap setia pada janji saya, setelah penangguhan berakhir. Jika saya ingat dengan benar, saya perlu menggandakan periode hadiah di waktu berikutnya jadi jika Anda mendapatkan jawaban, Anda mungkin mendapatkan +200 :)

HyperNeutrino
sumber
1
Saya bingung dengan apa yang dianggap sebagai cuplikan kode yang valid. Mengapa bukan sembarang tag <code> di html?
Hobi Calvin
@HelkaHomba Bagaimana dengan pembatasan baris baru? Saya bisa mencoba mencari cara lain untuk menggabungkannya.
HyperNeutrino
@HelkaHomba Pada dasarnya, jika jawabannya berisi kode backtick-delimited dalam satu baris, itu harus diabaikan.
HyperNeutrino
Ini adalah salah satu jawaban itu, di mana lebih mudah untuk melakukan bagian utama dari pertanyaan itu. Mengunduh halaman dan mengekstrak blok kode lebih sulit daripada melakukan jarak levenshtein.
Bálint
1
Keren. Hanya mengecek.
Matt

Jawaban:

1

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]

Saya meninggalkan baris baru di sana untuk dibaca. Masih tercermin dalam jumlah byte saya.

Cukup yakin saya punya pegangan dalam hal ini. Bagian yang sulit bagi saya sebenarnya mendapatkan jarak Levenshtein karena PowerShell tidak memiliki builtin untuk itu sejauh yang saya tahu. Karena itu saya bisa menjawab tantangan terkait jarak Levenshtein . Saat kode saya merujuk ke fungsi anonim untuk LD, Anda dapat merujuk ke jawaban itu untuk penjelasan yang lebih terperinci tentang cara kerjanya.

Kode dengan komentar dan indikator kemajuan

Kode dapat menjadi sangat lambat (karena LD) jadi saya membuat beberapa indikator kemajuan untuk diri saya sendiri sehingga saya bisa mengikuti tindakan saat dibuka dan tidak menganggapnya macet di suatu tempat. Kode untuk memantau kemajuan tidak di blok atas atau dihitung dalam jumlah byte saya.

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

Logika saya untuk menemukan blok kode adalah mengambil jawaban sebagai HTML dan mencari satu set tag kode, secara opsional dikelilingi oleh set tag pra yang dimulai pada barisnya sendiri. Dalam pengujian itu ditemukan semua data yang benar pada 6 set pertanyaan yang berbeda.

Saya mencoba bekerja dari kode penurunan harga tetapi terlalu sulit untuk menemukan blok kode yang tepat.

Sampel dijalankan

Challenge-Similarity-Detector 97752 122740
57

Challenge-Similarity-Detector 115715 116616
23
Mat
sumber
Saya telah menghabiskan sebagian dari 3 hari melihat ini. Tantangan ini ada di 5 teratas saya untuk upaya paling menyenangkan. TFTC (Terima kasih atas tantangannya)
Matt
Pekerjaan yang baik! Terima kasih, saya senang Anda menikmatinya! :)
HyperNeutrino
Catatan: Saya memberi hadiah lebih awal dari yang disebutkan karena saya meminta penskorsan jadi saya tidak bisa memberikannya nanti. Kerja bagus! :)
HyperNeutrino
Meminta penangguhan?
Matt
Ya, saya meminta Dennis memberi saya penangguhan 1 minggu agar saya dapat fokus pada tugas sekolah. Ini sudah dilakukan sebelumnya (walaupun saya masih di sini ... Saya tidak tahu kapan saya akan menghilang).
HyperNeutrino
3

Java + Jsoup, 1027 byte

Dua argumen pertama adalah ID pertanyaan.

Golf:

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

Dapat dibaca:

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
sumber
hajar aku sampai !!!! Bagus!
tuskiomi
1
Selamat datang di PPCG! Itu tidak melanggar aturan untuk menggunakan perpustakaan pihak ketiga, tetapi kami mengharuskan penggunaan perpustakaan dicatat dengan bahasa (jadi jawaban Java yang menggunakan perpustakaan yang disebut JavaHTML akan diberi label "Java + JavaHTML").
Mego
Ok terima kasih! Saya akan mengingatnya untuk waktu berikutnya!
Tomahawk2001913
Tidak ada yang menghentikan Anda dari menggunakan perpustakaan dalam tantangan ini jika Anda mau.
Matt
Saya mungkin harus sekarang bahwa seseorang telah menduduki jawaban saya!
Tomahawk2001913
0

Mathematica, 540 byte

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


memasukkan

["115715", "116616"]

keluaran

23

menggunakan EditDistance bawaan yang "memberikan jarak edit atau Levenshtein antara string atau vektor u dan v."

Sedangkan untuk test case Mathematica

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

mengembalikan 23

Saya kira saya bisa bermain golf lebih lama.
Butuh beberapa menit untuk berlari

J42161217
sumber