Java, 99.04 98.46 97.66 lcs () 호출

작동 원리

예 : 재구성 될 우리의 노선은 00101입니다. 먼저 우리는 제로 전용 string과 (여기서 = lcs를 원래 문자열과 비교) 계산하여 0이 몇 개인 지 알아냅니다 00000. 그런 다음 각 위치를 살펴보고 0a를 뒤집어 1공통 문자열이 더 긴지 확인합니다. 예인 경우 수락하고 다음 위치로 이동하십시오. 그렇지 않은 경우 전류를 1다시 a로 뒤집고 0다음 위치로 이동하십시오.

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

최적화

이것은 “순진한”구현 일 뿐이며, 한 번에 여러 위치를 검사하는보다 정교한 알고리즘을 찾을 수있을 것입니다. 그러나 항상 공통 하위 문자열 의 길이 를 평가할 수 있기 때문에 실제로 더 나은 것이 있는지 확실하지 않습니다 (예 : 해밍 코드와 유사한 패리티 비트 계산 기준) .

주어진 한 줄의 숫자에 대해이 알고리즘은 정확하게 #ofDigitsUntilTheLastOccurenceOf1 + 1검사 해야 합니다. (마지막 숫자가이면 1을 빼십시오 1.)

편집 : 하나의 작은 최적화 : 우리가 두 번째 마지막 자리를 방금 확인했지만 여전히을 삽입 해야하는 1경우 가장 마지막 위치에 있어야하며 해당 검사를 생략 할 수 있습니다.

EDIT2 : 방금 위의 아이디어를 마지막 아이디어에 적용 할 수 있음을 알았습니다 k.

물론 모든 줄을 먼저 다시 정렬하여이 최적화를 통해 약간 낮은 점수를 얻는 것이 가능할 수도 있습니다. 왜냐하면 맨 끝에 줄이있는 줄을 더 많이 얻을 수는 있지만 현재는 물론 더 이상 재미없는 테스트 사례.

실행 시간

상한은 O(#NumberOfBits)입니다.

전체 코드

전체 코드는 다음과 같습니다.

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

    }

}

답변