Identifikasi string dari substringnya

20

pengantar

Saya sebelumnya telah menciptakan dua tantangan di mana idenya adalah untuk merekonstruksi objek menggunakan sesedikit mungkin jenis operasi query; ini akan menjadi yang ketiga.

Tugas

Input Anda harus berupa string yang tidak kosong di Satas alfabet abcdan panjangnya, dan output Anda akan menjadi S. Tanpa batasan, ini tentu saja akan menjadi tugas yang sepele; tangkapannya adalah Anda tidak diizinkan mengakses Ssecara langsung. Satu-satunya hal yang boleh Anda lakukan Sadalah memanggil fungsi num_occur(T, S), di mana Tada string lain, dan num_occurmenghitung jumlah kemunculan Tdi S. Kejadian yang tumpang tindih dihitung sebagai berbeda, sehingga num_occur(T, S)benar-benar mengembalikan jumlah indeks isedemikian rupa

S[i, i+1, …, i+length(T)-1] == T

Misalnya num_occur("aba", "cababaababb")akan kembali 3. Perhatikan juga bahwa num_occur(S, S)akan kembali 1. Hasil num_occur("", S)tidak terdefinisi, dan Anda tidak boleh memanggil fungsi pada string kosong.

Singkatnya, Anda harus menulis fungsi atau program yang mengambil Sdan length(S)sebagai input, memanggil num_occurbeberapa string yang lebih pendek dan Sbeberapa kali, merekonstruksi Sdari informasi itu dan mengembalikannya.

Aturan dan penilaian

Tujuan Anda adalah menulis program yang membuat panggilan sesedikit num_occurmungkin. Dalam repositori ini , Anda akan menemukan file bernama abc_strings.txt. File ini berisi 100 string, masing-masing pada barisnya sendiri, antara panjang 50 dan 99. Skor Anda adalah jumlah total panggilan num_occurpada input ini , skor yang lebih rendah lebih baik. Solusi Anda lebih baik akan melacak nomor ini saat berjalan, dan mencetaknya setelah selesai. String dihasilkan dengan memilih huruf acak seragam dari abc; Anda diizinkan untuk mengoptimalkan metode menghasilkan string ini, tetapi bukan string itu sendiri.

Tidak ada batasan waktu, kecuali bahwa Anda harus menjalankan solusi Anda pada test case sebelum mengirimkannya. Solusi Anda harus bekerja untuk setiap input yang valid S, bukan hanya kasus uji.

Anda juga dianjurkan untuk membagikan implementasi Anda num_occur, jika Anda tidak menggunakan orang lain. Untuk mendapatkan bola yang menggelinding, berikut ini implementasinya dengan Python:

def num_occur(needle, haystack):
    num = 0
    for i in range(len(haystack) - len(needle) + 1):
        if haystack[i : i + len(needle)] == needle:
            num += 1
    return num
string fewest-operations Zgarb
sumber
Apakah algoritme kami harus berfungsi untuk semua string yang mungkin S, atau hanya untuk kasus uji?
Loovjo
@Loovjo Pertanyaan bagus. Secara teoritis mereka harus bekerja untuk semua string yang tidak kosong. Saya akan mengedit tantangannya.
Zgarb
all non-empty stringsberapa pun panjangnya?
edc65
@ edc65 Secara teoritis ya. Anda dapat mengabaikan alamat memori terbatas dan batasan praktis lainnya.
Zgarb
Dimungkinkan untuk menambahkan algoritme VW agar lulus tes evaluasi dengan sukses: Periksa dulu apakah ada string abc_strings.txt yang diketahui
Emmanuel

Jawaban:

6

Javascript, 14325 14311 panggilan

Kami mulai dengan string kosong dan melanjutkan dengan rekursif dengan menambahkan huruf baru di akhir atau di awal string saat ini sementara kami masih memiliki setidaknya satu kecocokan.

Semua hasil sebelumnya dari numOccur()disimpan di symobjek dan kami menggunakan data ini untuk segera menolak string baru yang tidak mungkin menjadi kandidat.

EDIT : Karena kita selalu mulai dengan 'a', kita selalu tahu jumlah pasti dari astring. Kami menggunakan informasi ini untuk mengakhiri proses lebih awal ketika kami mendeteksi bahwa hanya urutan ayang hilang. Juga memperbaiki ekspresi reguler yang tidak valid di Chrome dan IE.

var test = [
  'ccccbcbbbbacbaaababbccaacbccaaaaccbccaaaaaabcbbbab',
  // etc.
];
var call = 0;

function guess(S, len) {
  var sym = {};
  recurse(S, len, "", sym);
  return sym.result;
}

function recurse(S, len, s, sym) {
  var dictionary = [];

  if(s == '' || (isCandidate(s, sym) && (sym[s] = numOccur(S, s)))) {
    if(s.length == len) {
      sym.result = s;
    }
    else if(sym['a'] && count(s, 'a') == sym['a'] - (len - s.length)) {
      dictionary = [ Array(len - s.length + 1).join('a') ];
    }
    else {
      dictionary = [ "a", "b", "c" ];
    }
    dictionary.some(function(e) {
      return recurse(S, len, s + e, sym) || recurse(S, len, e + s, sym);
    });
    return true;
  }
  return false;
}

function isCandidate(s, sym) {
  return sym[s] === undefined && Object.keys(sym).every(function(k) {
    return count(s, k) <= sym[k];
  });
}

function count(s0, s1) {
  return (s0.match(new RegExp(s1, 'g')) || []).length;
}

function numOccur(S, s) {
  call++;
  return count(S, s);
}

test.forEach(function(S) {
  if(guess(S, S.length) != S) {
    console.log("Failed for: '" + S + "'");
  }
});
console.log(call + " calls");

Cuplikan yang dapat dieksekusi penuh di bawah.

Tampilkan cuplikan kode

Arnauld
sumber
"Singkatnya, Anda harus menulis fungsi atau program yang [...], merekonstruksi S dari informasi itu dan mengembalikannya ."
KarlKastor
@KarlKastor - Ups. Kamu benar. Itu sudah diperbaiki. Terima kasih!
Arnauld
4

Python, 15205 panggilan

def findS(S, len_s, alphabeth = "abc"):
    if len_s == 0:
        return ""
    current = ""
    add_at_start = True
    while len(current) < len_s:
        worked = False 
        for letter in alphabeth:
            if add_at_start:
                current_new = current + letter
            else:
                current_new = letter + current
            if num_occur(current_new, S) > 0:
                current = current_new
                worked = True
                break
        if not worked:
            add_at_start = False
    return current

Pengajuan ini kemungkinan besar suboptimal, karena hanya digunakan num_occuruntuk memeriksa apakah string adalah substring S, dan tidak pernah menggunakannya untuk benar-benar menghitung jumlah substring.

Algoritma bekerja dengan menyimpan string currentyang dibangun agar sama dengan Spada akhirnya. Berikut ini semua langkah dalam algoritme:

  1. Kami menetapkan currentsama dengan''

  2. Telusuri setiap huruf dalam alfabet, dan lakukan hal berikut:

    2.1. Buat string baru current_new, dan atur sama dengan currentdiikuti oleh huruf.

    2.2. Periksa apakah current_newdisertakan Sdengan menjalankannya num_occurdan lihat apakah hasilnya lebih dari satu.

    2.3. Jika current_newtermasuk dalam S, set currentke current_newdan kembali ke langkah 2. Lain, kita pergi ke surat berikutnya.

  3. Jika panjangnya currentsama dengan panjangnya Skita bisa mengatakan bahwa kita sudah selesai. Lain, kita kembali ke langkah 2, tetapi memodifikasi langkah 2.1 untuk membuat current_newsama dengan huruf diikuti oleh currentsebagai gantinya. Ketika kita mencapai langkah ini lagi, kita selesai.

Loovjo
sumber
1
Python untuk loop memiliki klausa lain. Ini akan menjadi kasus penggunaan yang sempurna untuk itu.
Jakube
4

Python 2, 14952 14754 panggilan

Sangat mirip dengan jawaban pertama, tetapi tidak mencoba karakter berikutnya yang menghasilkan substring yang tidak mungkin:

  • kita tahu num_occurbahwa itu tidak terjadi pada target (dari panggilan sebelumnya)

  • kami sudah menggunakan substring lebih sering daripada yang terjadi menurut num_occur

(akan menambahkan penghitungan substring dalam satu menit) dilakukan

def get_that_string(h,l,alpha = "abc"):
    dic = {}
    s = ""
    ##costs 1 additional call per example, but its worth it
    char_list = [num_occur(j,h) for j in alpha[:-1]]
    char_list.append(l - sum(char_list))
    for y, z in zip(char_list,alpha):
        dic[z] = y
    end_reached = False
    while len(s) < l:
        for t in alpha:
            if not end_reached:
                neu_s = s + t
                substrings = [neu_s[i:]   for i in range(len(neu_s))]
            else:
                neu_s = t + s
                substrings = [neu_s[:i+1] for i in range(len(neu_s))]
            ## Test if we know that that can't be the next char
            all_in_d = [suff for suff in substrings if suff in dic.keys()]
            poss=all(map(dic.get,all_in_d))
            if poss:
                if not neu_s in dic.keys():
                    dic[neu_s] = num_occur(neu_s,h)
                if dic[neu_s] > 0:
                    s=neu_s
                    for suff in all_in_d:
                        dic[suff] -= 1
                    break
        else:
            end_reached = True
    ##print s
    return s


## test suite start
import urllib

def num_occur(needle, haystack):
    global calls
    calls += 1
    num = 0
    for i in range(len(haystack) - len(needle) + 1):
        if haystack[i : i + len(needle)] == needle:
            num += 1
    return num

calls = 0
url = "https://raw.githubusercontent.com/iatorm/random-data/master/abc_strings.txt"
inputs = urllib.urlopen(url).read().split("\n")
print "Check: ", inputs == map(lambda h: get_that_string(h, len(h)), inputs)
print "Calls: ", calls
KarlKastor
sumber
4

Python 12705 12632 panggilan

  1. membuat daftar kejadian string 2 karakter
  2. urutkan daftar
  3. bangun string dengan mencoba karakter yang paling memungkinkan terlebih dahulu, jangan tes jika hanya ada satu kemungkinan
  4. perbarui daftar
  5. jika daftar kosong maka sudah selesai lain langkah 2

Saya menggunakan kerangka fungsi Loovjo. Saya tidak pernah kode dengan Python saya butuh bootsrap

EDIT:
Kode yang ditambahkan untuk satu string karakter
ditambahkan kode untuk menolak pola yang sudah cocok

def finds(S):

    if len(S) == 0:
            return ""
    if len(S) == 1 
            if num_occur("a",S) == 1 :
                         return "a"
            if num_occur("b",S) == 1 :
                         return "b"
            return "c"
    tuples=[]
    alphabet=[ "aa", "ab", "ac", "ba", "bb", "bc", "ca", "cb"]
    for s in alphabet : tuples.append( (num_occur(s,S), s) )

    sum=0
    for (i,s) in tuples :   sum+=i
    tuples.append( (len(S)-sum-1, "cc") )
    tuples.sort(key=lambda x:(-x[0],x[1]))

    (i, current) = tuples[0]
    tuples[0] = (i-1, current)

    add_at_start = True
    nomatch=[]
    while len(tuples) > 0:
            worked = False
            tuples.sort(key=lambda x:(-x[0],x[1]))
            count=0
            if not add_at_start :
                    for (n, s) in tuples :
                            if s[0]==current[-1:] :         count+=1
            for i in range(len(tuples)):
                    (n, s)=tuples[i]
                    if add_at_start:
                            if current[0] == s[1] :
                                    current_new = s[0] + current
                                    possible=True
                                    for nm in nomatch :
                                            lng=len(nm)
                                            if current_new[0:lng] == nm :
                                                    possible=False
                                                    break
                                    if possible and num_occur(current_new, S) > 0:
                                            current = current_new
                                            worked = True
                                    else :
                                            nomatch.append(current_new)
                    else:
                            if current[-1:] == s[0] :
                                    current_new =  current + s[1]
                                    possible=True
                                    for nm in nomatch :
                                            lng=len(nm)
                                            if current_new[-lng:] == nm :
                                                    possible=False
                                                    break
                                    if count == 1 or (possible and num_occur(current_new, S) > 0) :
                                            current = current_new
                                            worked = True
                                    else :
                                            nomatch.append(current_new)
                    if worked :
                            if n == 1:
                                    del tuples[i]
                            else    :
                                    tuples[i] = (n-1, s)
                            break
            if not worked:
                    add_at_start = False
    return current
Emmanuel
sumber
tidak ada 'cc' di alfabet Anda?
Sparr
@Sparr "cc" dihitung, itu menyimpan 100 panggilan: `tuples.append ((len (S) -sum-1," cc "))`
Emmanuel