Wprowadzenie

Załóżmy, że ty i twój przyjaciel gracie w grę. Twój przyjaciel myśli o określonej sekwencji nbitów, a Twoim zadaniem jest wydedukować sekwencję, zadając im pytania. Jednak jedynym rodzajem pytania, które możesz zadać, jest: „Jaka jest najdłuższa wspólna podsekwencja twojej sekwencji i S”, gdzie Sjest dowolna sekwencja bitów. Im mniej pytań potrzebujesz, tym lepiej.

Zadanie

Twoim zadaniem jest napisanie programu lub funkcji, która przyjmuje jako dane wejściowe dodatnią liczbę całkowitą ni binarną sekwencję Rdługości n. Sekwencją może być tablica liczb całkowitych, ciąg znaków lub inny rozsądny typ twojego wyboru. Twój program wyświetli sekwencję R.

Twój program nie ma Rbezpośredniego dostępu do sekwencji . Tylko rzecz to wolno zrobić, aby Rto dać to jako wejście do funkcji len_lcswraz z innej sekwencji binarnej S. Funkcja len_lcs(R, S)zwraca długość najdłuższego wspólnego podsekwencji Ri S. Oznacza to najdłuższą sekwencję bitów, która występuje jako (niekoniecznie ciągła) podsekwencja zarówno w, jak Ri S. Dane wejściowe len_lcsmogą mieć różne długości. Program powinien wywołać tę funkcję Ri inne sekwencje kilka razy, a następnie zrekonstruować sekwencję Rna podstawie tej informacji.

Przykład

Rozważ dane wejściowe n = 4i R = "1010". Po pierwsze, możemy ocenić len_lcs(R, "110"), co daje 3, ponieważ "110"jest to najdłuższa wspólna podsekwencja "1010"i "110". Wtedy wiemy, że Ruzyskuje się to "110"poprzez wstawienie jednego bitu w pewnej pozycji. Następnie możemy spróbować len_lcs(R, "0110"), który powraca 3od najdłuższych wspólnych podciągów to "110"i "010"tak "0110"nie jest poprawna. Następnie próbujemy len_lcs(R, "1010"), co powraca 4. Teraz wiemy o tym R == "1010", abyśmy mogli zwrócić tę sekwencję jako poprawne wyjście. Wymagało to 3 połączeń z len_lcs.

Zasady i punktacja

W tym repozytorium znajdziesz plik o nazwie subsequence_data.txtzawierający 100 losowych sekwencji binarnych o długości od 75 do 124. Zostały one wygenerowane poprzez pobranie trzech losowych liczb zmiennoprzecinkowych od 0 do 1, przyjęcie ich średniej jako a, a następnie przerzucenie abezstronnych nczasów monet . Twój wynik to średnia liczba wywołańlen_lcs w tych sekwencjach, przy czym niższy wynik jest lepszy. Twoje zgłoszenie powinno rejestrować liczbę połączeń. Nie ma ograniczeń czasowych, z wyjątkiem tego, że powinieneś uruchomić program na pliku przed jego przesłaniem.

Twoje zgłoszenie będzie deterministyczne. PRNG są dozwolone, ale muszą używać dzisiejszej daty 200116(lub najbliższego odpowiednika) jako losowego materiału siewnego. Niedozwolone jest optymalizowanie procesu przesyłania w odniesieniu do tych konkretnych przypadków testowych. Jeśli podejrzewam, że tak się dzieje, wygeneruję nową partię.

To nie jest kod golfowy, więc zachęcamy do napisania czytelnego kodu. Kod Rosetta ma stronę o najdłuższym wspólnym podsekwencji ; możesz użyć tego do wdrożenia len_lcsw swoim wybranym języku.

Java, 99,04 98,46 97,66 lcs ()

Jak to działa

Przykład: nasza linia, która ma zostać zrekonstruowana, to 00101. Najpierw dowiadujemy się, ile jest zer, porównując (tutaj porównując = obliczanie lcs z oryginalnym ciągiem) przez ciąg tylko zer 00000. Następnie przeglądamy każdą pozycję, przełączamy na 0a 1i sprawdzamy, czy mamy już dłuższy wspólny podłańcuch. Jeśli tak, zaakceptuj i przejdź do następnej pozycji, jeśli nie, odwróć bieżącą pozycję z 1powrotem do pozycji 0i przejdź do następnej pozycji:

For our example of "00101" we get following steps:
input  lcs  prev.'best'
00000  3    0           //number of zeros
̲10000  3    3           //reject
0̲1000  3    3           //reject
00̲100  4    3           //accept
001̲10  4    4           //reject
0010̲1  5    4           //accept

Optymalizacje

Jest to po prostu „naiwna” implementacja, być może byłoby możliwe znalezienie bardziej wyrafinowanego algorytmu sprawdzającego wiele pozycji jednocześnie. Ale nie jestem pewien, czy naprawdę jest lepszy (np. Na podstawie obliczenia bitów parzystości podobnych do kodu Hamminga), ponieważ zawsze można po prostu ocenić długość wspólnego podłańcucha.

Dla jednej linii cyfr ten algorytm wymaga dokładnie #ofDigitsUntilTheLastOccurenceOf1 + 1sprawdzenia. (Odejmij jeden, jeśli ostatnie cyfry to 1.)

EDYCJA: Jedna mała optymalizacja: Jeśli właśnie sprawdziliśmy drugą ostatnią cyfrę i nadal musimy wstawić a 1, wiemy na pewno, że musi ona znajdować się na ostatniej pozycji i możemy pominąć odpowiednie sprawdzenie.

EDYCJA 2: Właśnie zauważyłem, że możesz zastosować powyższy pomysł do ostatnich k.

Dzięki tej optymalizacji można oczywiście uzyskać nieco niższy wynik, zmieniając najpierw wszystkie linie, ponieważ może się zdarzyć, że na końcu pojawi się więcej linii, ale to oczywiście będzie optymalizacja dla bieżącego przypadki testowe, które nie są już śmieszne.

Środowisko wykonawcze

Górny limit to O(#NumberOfBits).

Pełny kod

Oto pełny kod:

package jcodegolf;

import java.io.BufferedReader;
import java.io.File;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;

// http://codegolf.stackexchange.com/questions/69799/know-a-sequence-by-its-subsequences

public class SequenceReconstructor { 
    public static int counter = 0;
    public static int lcs(String a, String b) { //stolen from http://rosettacode.org/wiki/Longest_common_subsequence#Java
        int[][] lengths = new int[a.length()+1][b.length()+1];

        // row 0 and column 0 are initialized to 0 already

        for (int i = 0; i < a.length(); i++)
            for (int j = 0; j < b.length(); j++)
                if (a.charAt(i) == b.charAt(j))
                    lengths[i+1][j+1] = lengths[i][j] + 1;
                else
                    lengths[i+1][j+1] =
                        Math.max(lengths[i+1][j], lengths[i][j+1]);

        // read the substring out from the matrix
        StringBuffer sb = new StringBuffer();
        for (int x = a.length(), y = b.length();
             x != 0 && y != 0; ) {
            if (lengths[x][y] == lengths[x-1][y])
                x--;
            else if (lengths[x][y] == lengths[x][y-1])
                y--;
            else {
                assert a.charAt(x-1) == b.charAt(y-1);
                sb.append(a.charAt(x-1));
                x--;
                y--;
            }
        }

        counter ++;
        return sb.reverse().toString().length();
    }


    public static String reconstruct(String secretLine, int lineLength){
        int current_lcs = 0; 
        int previous_lcs = 0;
        char [] myGuess = new char[lineLength];
        for (int k=0; k<lineLength; k++){
            myGuess[k] = '0';
        }

        //find the number of zeros:
        int numberOfZeros = lcs(secretLine, String.valueOf(myGuess));
        current_lcs = numberOfZeros;
        previous_lcs = numberOfZeros;

        if(current_lcs == lineLength){ //were done
            return String.valueOf(myGuess);
        }


        int numberOfOnes = lineLength - numberOfZeros;
        //try to greedily insert ones at the positions where they maximize the common substring length
        int onesCounter = 0;
        for(int n=0; n < lineLength && onesCounter < numberOfOnes; n++){

            myGuess[n] = '1';
            current_lcs = lcs(secretLine, String.valueOf(myGuess));

            if(current_lcs > previous_lcs){ //accept

                previous_lcs = current_lcs;
                onesCounter ++;

            } else { // do not accept
                myGuess[n]='0';     
            }

            if(n == lineLength-(numberOfOnes-onesCounter)-1 && onesCounter < numberOfOnes){ //lets test if we have as many locations left as we have ones to insert
                                                                // then we know that the rest are ones
                for(int k=n+1;k<lineLength;k++){
                    myGuess[k] = '1';
                }
                break;
            }

        }

        return String.valueOf(myGuess);
    }

    public static void main(String[] args) {
        try {

            //read the file
            BufferedReader br;

            br = new BufferedReader(new FileReader("PATH/TO/YOUR/FILE/LOCATION/subsequence_data.txt"));

            String line;

            //iterate over each line
            while ( (line = br.readLine()) != null){

                String r = reconstruct(line, line.length());
                System.out.println(line);     //print original line
                System.out.println(r);        //print current line
                System.out.println(counter/100.0);  //print current number of calls
                if (! line.equals(r)){
                    System.out.println("SOMETHING WENT HORRIBLY WRONG!!!");
                    System.exit(1);
                }

            }


        } catch(Exception e){
            e.printStackTrace();;
        }

    }

}