소개
당신과 당신의 친구가 게임을하고 있다고 가정하자. 친구는 특정 순서의 n
비트를 생각 하며 과제는 질문을 통해 순서를 추론하는 것입니다. 그러나 질문 할 수있는 유일한 유형의 질문은 “시퀀스의 가장 긴 공통 하위 시퀀스의 길이는 얼마입니까 S
” 와 S
비트 시퀀스의 위치 는 ” 입니다. 필요한 질문이 적을수록 좋습니다.
작업
당신의 임무는 입력으로 양의 정수 n
와 R
길이 의 이진 시퀀스 를 취하는 프로그램이나 함수를 작성하는 것 n
입니다. 시퀀스는 정수 배열, 문자열 또는 다른 합리적인 유형의 선택 일 수 있습니다. 프로그램은 시퀀스를 출력해야합니다 R
.
프로그램이 시퀀스에 직접 액세스 할 수 없습니다R
. 그것이 할 수 있는 유일한 일은 다른 바이너리 시퀀스와 함께 R
함수에 입력으로 제공하는 것 입니다. 이 함수는 가장 긴 일반적인 서브 순서의 길이를 반환 하고 . 이 둘의 (반드시 연속적이지) 시퀀스로 발생 된 비트의 긴 시퀀스 수단 과 . 입력 길이가 다를 수 있습니다. 프로그램은이 함수 와 다른 시퀀스에서 여러 번 이 함수를 호출 한 다음 해당 정보를 기반으로 시퀀스를 재구성 해야합니다.len_lcs
S
len_lcs(R, S)
R
S
R
S
len_lcs
R
R
예
입력 n = 4
과를 고려하십시오 R = "1010"
. 첫째, 우리는 평가 수 len_lcs(R, "110")
주는, 3
이후 "110"
의 가장 긴 일반적인 서브가 "1010"
와 "110"
. 그런 다음 특정 위치에 1 비트를 삽입 R
하여 얻은 것을 알 수 "110"
있습니다. 다음으로, 가장 긴 공통 서브 시퀀스가 and 이므로 len_lcs(R, "0110")
리턴하는을 시도해 볼 수 있습니다 . 그런 다음 을 반환합니다 . 이제 우리는 그 시퀀스를 올바른 출력으로 반환 할 수 있다는 것을 알고 있습니다. 에 3 번의 전화가 필요했습니다 .3
"110"
"010"
"0110"
len_lcs(R, "1010")
4
R == "1010"
len_lcs
규칙과 득점
에서 이 저장소 , 당신은라는 파일을 찾을 수 있습니다 subsequence_data.txt
(75) 및 (124) 사이의 길이의 100 개 무작위 이진 시퀀스 그들은, 0과 1 사이의 세 가지 임의 수레를 가지고 그들의 평균하여 생성 된 포함 a
AN, 다음 뒤집기 a
-biased 동전 n
번. 점수는 이 시퀀스에 대한 평균 통화 횟수이며len_lcs
, 점수가 낮을수록 좋습니다. 제출 한 통화 수를 기록해야합니다. 제출하기 전에 파일에서 프로그램을 실행해야한다는 점을 제외하고 시간 제한이 없습니다.
귀하의 제출은 결정 론적이어야합니다. PRNG는 허용되지만 오늘 날짜 200116
(또는 가장 가까운 것)를 임의의 시드로 사용해야합니다 . 이러한 특정 테스트 사례에 대해 제출을 최적화 할 수 없습니다. 이것이 일어나고 있다고 생각되면 새로운 배치를 생성합니다.
이것은 코드 골프가 아니므로 읽을 수있는 코드를 작성하는 것이 좋습니다. Rosetta Code는 가장 긴 공통 서브 시퀀스에 대한 페이지를 가지고 있습니다 . 이를 사용 len_lcs
하여 선택한 언어 로 구현할 수 있습니다.
답변
Java, 99.04 98.46 97.66 lcs () 호출
작동 원리
예 : 재구성 될 우리의 노선은 00101
입니다. 먼저 우리는 제로 전용 string과 (여기서 = lcs를 원래 문자열과 비교) 계산하여 0이 몇 개인 지 알아냅니다 00000
. 그런 다음 각 위치를 살펴보고 0
a를 뒤집어 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();;
}
}
}