Introducción

Supongamos que usted y su amigo están jugando un juego. Tu amigo piensa en una secuencia particular de nbits, y tu tarea es deducir la secuencia haciéndoles preguntas. Sin embargo, el único tipo de pregunta que se le permite hacer es "¿Cuánto dura la subsecuencia común más larga de su secuencia y S", dónde Ses cualquier secuencia de bits. Cuantas menos preguntas necesite, mejor.

La tarea

Su tarea es escribir un programa o función que tome como entrada un entero positivo ny una secuencia binaria Rde longitud n. La secuencia puede ser una matriz de enteros, una cadena o algún otro tipo razonable de su elección. Su programa generará la secuencia R.

Su programa no puede acceder a la secuencia Rdirectamente. Lo único que se le permite hacer Res darle como entrada a la función len_lcsjunto con otra secuencia binaria S. La función len_lcs(R, S)devuelve la longitud de la subsecuencia común más larga de Ry S. Esto significa la secuencia más larga de bits que ocurre como una subsecuencia (no necesariamente contigua) en ambos Ry S. Las entradas de las len_lcscuales pueden ser de diferentes longitudes. El programa debe invocar esta función Ry otras secuencias varias veces, y luego reconstruir la secuencia en Rfunción de esa información.

Ejemplo

Considere las entradas n = 4y R = "1010". Primero, podríamos evaluar len_lcs(R, "110"), lo que da 3, ya que "110"es la subsecuencia común más larga de "1010"y "110". Entonces sabemos que Rse obtiene "110"al insertar un bit en alguna posición. A continuación, podríamos intentar len_lcs(R, "0110"), que regresa 3ya que las subsecuencias comunes más largas son "110"y "010", por "0110"lo tanto, no es correcta. Luego intentamos len_lcs(R, "1010"), que vuelve 4. Ahora sabemos eso R == "1010", por lo que podemos devolver esa secuencia como la salida correcta. Esto requirió 3 llamadas a len_lcs.

Reglas y puntaje

En este repositorio , encontrará un archivo llamado que subsequence_data.txtcontiene 100 secuencias binarias aleatorias de longitudes entre 75 y 124. Se generaron tomando tres flotadores aleatorios entre 0 y 1, tomando su promedio como a, y luego volteando una amoneda imparcial nveces. Su puntaje es el número promedio de llamadas alen_lcs estas secuencias, siendo menor el puntaje menor. Su envío debe registrar el número de llamadas. No hay límites de tiempo, excepto que debe ejecutar su programa en el archivo antes de enviarlo.

Su presentación será determinista. Los PRNG están permitidos, pero deben usar la fecha de hoy 200116(o el equivalente más cercano) como semilla aleatoria. No está permitido optimizar su envío en relación con estos casos de prueba particulares. Si sospecho que esto está sucediendo, generaré un nuevo lote.

Este no es un código de golf, por lo que se recomienda escribir código legible. Rosetta Code tiene una página en la subsecuencia común más larga ; puede usar eso para implementar len_lcsen su idioma de elección.

Java, 99.04 98.46 97.66 llamadas lcs ()

Cómo funciona

Exaple: Nuestra línea que se va a reconstruir es 00101. Primero descubrimos cuántos ceros hay, comparando (aquí comparando = calculando lcs con la cadena original) por una cadena de solo ceros 00000. Luego pasamos por cada posición, volteamos 0a a 1y verificamos si ahora tenemos una subcadena común más larga. En caso afirmativo, acepte e ir a la siguiente posición, si no, voltee la corriente de 1nuevo a ay 0vaya a la siguiente posición:

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

Optimizaciones

Esta es solo una implementación "ingenua", quizás sería posible encontrar un algoritmo más sofisticado que verifique varias posiciones a la vez. Pero no estoy seguro de si realmente hay uno mejor (por ejemplo, basado en el cálculo de bits de paridad similares al código de Hamming), ya que siempre puede evaluar la longitud de la subcadena común.

Para una línea de dígitos dada, este algoritmo necesita #ofDigitsUntilTheLastOccurenceOf1 + 1verificaciones exactas . (Reste uno si los últimos dígitos son an 1.)

EDITAR: Una pequeña optimización: si solo verificamos el 2do último dígito y aún necesitamos insertar un 1, sabemos con certeza que debe estar en la última posición, y podemos omitir la verificación correspondiente.

EDIT2: Acabo de notar que puedes aplicar la idea anterior a las últimas k.

Por supuesto, podría ser posible lograr un puntaje ligeramente más bajo con esta optimización, al reordenar todas las líneas primero, porque podría ser que obtenga más líneas con unas al final, pero eso obviamente sería una optimización para la actual. casos de prueba que ya no es gracioso.

Tiempo de ejecución

El límite superior es O(#NumberOfBits).

Código completo

Aquí el código completo:

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

    }

}