[Esta pergunta é um acompanhamento para calcular as execuções de uma string ]

Um período pde uma string wé qualquer número inteiro positivo, de pmodo que, w[i]=w[i+p] sempre que ambos os lados desta equação forem definidos. Vamos per(w)denotar o tamanho do menor período de w. Dizemos que uma string wé periódica se per(w) <= |w|/2.

Tão informalmente, uma sequência periódica é apenas uma sequência composta de outra sequência repetida pelo menos uma vez. A única complicação é que, no final da sequência, não exigimos uma cópia completa da sequência repetida, desde que seja repetida na íntegra pelo menos uma vez.

Por exemplo, considere a sequência x = abcab. per(abcab) = 3como x[1] = x[1+3] = a, x[2]=x[2+3] = be não há período menor. A sequência abcabnão é, portanto, periódica. No entanto, a cadeia ababaé periódica como per(ababa) = 2.

Como outros exemplos, abcabca, ababababae abcabcabctambém são periódicas.

Para quem gosta de expressões regulares, este detecta se uma sequência é periódica ou não:

\b(\w*)(\w+\1)\2+\b

A tarefa é encontrar todas as substrings periódicas máximas em uma sequência mais longa. Essas são algumas vezes chamadas de execuções na literatura.

Uma substring wé uma substring periódica máxima (execução) se for periódica e não for w[i-1] = w[i-1+p]nem w[j+1] = w[j+1-p]. Informalmente, a "execução" não pode estar contida em uma "execução" maior com o mesmo período.

Como duas execuções podem representar a mesma sequência de caracteres que ocorre em locais diferentes na sequência geral, representaremos as execuções por intervalos. Aqui está a definição acima repetida em termos de intervalos.

Uma execução (ou substring periódica máxima) em uma string Té um intervalo [i...j]com j>=i, de modo que

• T[i...j] é uma palavra periódica com o período p = per(T[i...j])
• É o máximo. Formalmente, nem T[i-1] = T[i-1+p]nem T[j+1] = T[j+1-p]. Informalmente, a execução não pode estar contida em uma execução maior com o mesmo período.

Indique pelo RUNS(T)conjunto de execuções na cadeia de caracteres T.

Exemplos de execuções

• Os quatro substrings periódicas máximas (runs) em corda T = atattattsão T[4,5] = tt, T[7,8] = tt, T[1,4] = atat, T[2,8] = tattatt.

• A cadeia de caracteres T = aabaabaaaacaacaccontém os seguintes máximos 7 subsequências periódicos (separações): T[1,2] = aa, T[4,5] = aa, T[7,10] = aaaa, T[12,13] = aa, T[13,16] = acac, T[1,8] = aabaabaa, T[9,15] = aacaaca.

• A sequência T = atatbatatbcontém as três execuções a seguir. Eles são: T[1, 4] = atat, T[6, 9] = atate T[1, 10] = atatbatatb.

Aqui estou usando a indexação 1.

A tarefa

Escreva o código para que, para cada número inteiro n começando em 2, você produza o maior número de execuções contidas em qualquer cadeia de comprimento binária n.

Ponto

Sua pontuação é a mais alta que nvocê alcança em 120 segundos, de modo que, para todos k <= n, ninguém postou uma resposta correta mais alta que você. Claramente, se você tiver todas as respostas ideais, obterá a pontuação mais alta nque postar. No entanto, mesmo que sua resposta não seja a ideal, você ainda pode obter a pontuação se ninguém mais conseguir vencê-la.

Línguas e bibliotecas

Você pode usar qualquer idioma e bibliotecas disponíveis que desejar. Onde for possível, seria bom poder executar seu código; portanto, inclua uma explicação completa de como executar / compilar seu código no Linux, se possível.

Exemplo optima

No seguinte: n, optimum number of runs, example string.

2 1 00
3 1 000
4 2 0011
5 2 00011
6 3 001001
7 4 0010011
8 5 00110011
9 5 000110011
10 6 0010011001
11 7 00100110011
12 8 001001100100
13 8 0001001100100
14 10 00100110010011
15 10 000100110010011
16 11 0010011001001100
17 12 00100101101001011
18 13 001001100100110011
19 14 0010011001001100100
20 15 00101001011010010100
21 15 000101001011010010100
22 16 0010010100101101001011

O que exatamente meu código deve produzir?

Para cada um, nseu código deve gerar uma única string e o número de execuções que ele contém.

Minha máquina Os horários serão executados na minha máquina. Esta é uma instalação padrão do ubuntu em um processador AMD FX-8350 de oito núcleos. Isso também significa que eu preciso poder executar seu código.

Respostas principais

• 49 por Anders Kaseorg em C . Thread único e executado com L = 12 (2 GB de RAM).
• 27 por cdlane em C .

C

Isso faz uma pesquisa recursiva por soluções ótimas, altamente otimizadas usando um limite superior no número de execuções que podem ser concluídas pelo restante desconhecido da sequência. O cálculo do limite superior usa uma tabela de pesquisa gigantesca cujo tamanho é controlado pela constante L( L=11: 0,5 GiB L=12,: 2 GiB L=13,: 8 GiB).

No meu laptop, isso aumenta n = 50 em 100 segundos; a próxima linha chega aos 142 segundos.

#include <stdbool.h>
#include <stdint.h>
#include <stdio.h>
#include <string.h>

#define N (8*sizeof(unsigned long long))
#define L 13
static bool a[N], best_a[N];
static int start[N/2 + 1], best_runs;
static uint8_t end_runs[2 << 2*L][2], small[N + 1][2 << 2*L];

static inline unsigned next_state(unsigned state, int b)
{
    state *= 2;
    state += b;
    if (state >= 2 << 2*L) {
        state &= ~(2 << 2*L);
        state |= 1 << 2*L;
    }
    return state;
}

static void search(int n, int i, int runs, unsigned state)
{
    if (i == n) {
        int r = runs;
        unsigned long long m = 0;
        for (int p = n / 2; p > 0; p--) {
            if (i - start[p] >= 2*p && !(m & 1ULL << start[p])) {
                m |= 1ULL << start[p];
                r++;
            }
        }
        if (r > best_runs) {
            best_runs = r;
            memcpy(best_a, a, n*sizeof(a[0]));
        }
    } else {
        a[i] = false;
        do {
            int r = runs, bound = 0, saved = 0, save_p[N/2], save_start[N/2], p, s = next_state(state, a[i]);
            unsigned long long m = 0;
            for (p = n/2; p > i; p--)
                if (p > L)
                    bound += (n - p + 1)/(p + 1);
            for (; p > 0; p--) {
                if (a[i] != a[i - p]) {
                    if (i - start[p] >= 2*p && !(m & 1ULL << start[p])) {
                        m |= 1ULL << start[p];
                        r++;
                    }
                    save_p[saved] = p;
                    save_start[saved] = start[p];
                    saved++;
                    start[p] = i + 1 - p;
                    if (p > L)
                        bound += (n - i)/(p + 1);
                } else {
                    if (p > L)
                        bound += (n - (start[p] + p - 1 > i - p ? start[p] + p - 1 : i - p))/(p + 1);
                }
            }
            bound += small[n - i - 1][s];

            if (r + bound > best_runs)
                search(n, i + 1, r, s);
            while (saved--)
                start[save_p[saved]] = save_start[saved];
        } while ((a[i] = !a[i]));
    }
}

int main()
{
    for (int n = 0; n <= N; n++) {
        if (n <= 2*L) {
            for (unsigned state = 1U << n; state < 2U << n; state++) {
                for (int b = 0; b < 2; b++) {
                    int r = 0;
                    unsigned long long m = 0;
                    for (int p = n / 2; p > 0; p--) {
                        if ((b ^ state >> (p - 1)) & 1) {
                            unsigned k = state ^ state >> p;
                            k &= -k;
                            k <<= p;
                            if (!(k & ~(~0U << n)))
                                k = 1U << n;
                            if (!((m | ~(~0U << 2*p)) & k)) {
                                m |= k;
                                r++;
                            }
                        }
                    }
                    end_runs[state][b] = r;
                }
                small[0][state] = end_runs[state][0] + end_runs[state][1];
            }
        }

        for (int l = 2*L < n - 1 ? 2*L : n - 1; l >= 0; l--) {
            for (unsigned state = 1U << l; state < 2U << l; state++) {
                int r0 = small[n - l - 1][next_state(state, 0)] + end_runs[state][0],
                    r1 = small[n - l - 1][next_state(state, 1)] + end_runs[state][1];
                small[n - l][state] = r0 > r1 ? r0 : r1;
            }
        }

        if (n >= 2) {
            search(n, 1, 0, 2U);
            printf("%d %d ", n, best_runs);
            for (int i = 0; i < n; i++)
                printf("%d", best_a[i]);
            printf("\n");
            fflush(stdout);
            best_runs--;
        }
    }
    return 0;
}

Saída:

$ gcc -mcmodel=medium -O2 runs.c -o runs
$ ./runs
2 1 00
3 1 000
4 2 0011
5 2 00011
6 3 001001
7 4 0010011
8 5 00110011
9 5 000110011
10 6 0010011001
11 7 00100110011
12 8 001001100100
13 8 0001001100100
14 10 00100110010011
15 10 000100110010011
16 11 0010011001001100
17 12 00100101101001011
18 13 001001100100110011
19 14 0010011001001100100
20 15 00101001011010010100
21 15 000101001011010010100
22 16 0010010100101101001011
23 17 00100101001011010010100
24 18 001001100100110110011011
25 19 0010011001000100110010011
26 20 00101001011010010100101101
27 21 001001010010110100101001011
28 22 0010100101101001010010110100
29 23 00101001011010010100101101011
30 24 001011010010110101101001011010
31 25 0010100101101001010010110100101
32 26 00101001011010010100101101001011
33 27 001010010110100101001011010010100
34 27 0001010010110100101001011010010100
35 28 00100101001011010010100101101001011
36 29 001001010010110100101001011010010100
37 30 0010011001001100100010011001001100100
38 30 00010011001001100100010011001001100100
39 31 001001010010110100101001011010010100100
40 32 0010010100101101001010010110100101001011
41 33 00100110010001001100100110010001001100100
42 35 001010010110100101001011010110100101101011
43 35 0001010010110100101001011010110100101101011
44 36 00101001011001010010110100101001011010010100
45 37 001001010010110100101001011010110100101101011
46 38 0010100101101001010010110100101001011010010100
47 39 00101101001010010110100101101001010010110100101
48 40 001010010110100101001011010010110101101001011010
49 41 0010100101101001010010110100101101001010010110100
50 42 00101001011010010100101101001011010110100101101011
51 43 001010010110100101001011010110100101001011010010100

Aqui estão todas as seqüências ideais para n ≤ 64 (não apenas o primeiro lexicograficamente), geradas por uma versão modificada deste programa e por muitas horas de computação.

Uma sequência quase ótima

Os prefixos da sequência fractal infinita

1010010110100101001011010010110100101001011010010100101…

que é invariável sob a transformação 101 × 10100, 00 × 101:

  101   00  101   101   00  101   00  101   101   00  101   101   00  …
= 10100 101 10100 10100 101 10100 101 10100 10100 101 10100 10100 101 …

parecem ter números quase ótimos de execuções - sempre dentro de 2 da ideal para n ≤ 64. O número de execuções nos primeiros n caracteres divididos por n abordagens (13 - 5√5) / 2 ≈ 0,90983. Mas acontece que essa não é a proporção ideal - veja os comentários.

Como não é uma corrida se houver apenas um cavalo, estou enviando minha solução, embora seja apenas uma fração da velocidade de Anders Kaseorg e uma apenas um terço como enigmática. Ajuntar com:

gcc -O2 contagem de execução.c -o contagem de execução

O coração do meu algoritmo é uma mudança simples e um esquema XOR:

Uma execução de zeros no resultado XOR que é maior ou igual ao período / turno atual indica uma execução na sequência original para esse período. A partir disso, você pode dizer quanto tempo durou a execução e onde começa e termina. O restante do código está sobrecarregado, configurando a situação e decodificando os resultados.

Espero que faça pelo menos 28 depois de dois minutos na máquina de Lembik. (Eu escrevi uma versão pthread, mas só consegui fazê-la funcionar ainda mais devagar.)

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <stdbool.h>

enum { START = 0, WIDTH } ;

// Compare and shuffle just one thing while storing two
typedef union {
    uint16_t token;
    uint8_t data[sizeof(uint16_t)];
} overlay_t;

#define SENTINAL (0)  // marks the end of an array of overlay_t

#define NUMBER_OF_BITS (8 * sizeof(uint64_t))

void period_runs(uint64_t xor_bits, uint8_t nbits, uint8_t period, overlay_t *results) {

    overlay_t *results_ptr = results;
    uint8_t count = 0;

    for (uint8_t position = 0; position < nbits; position++) {

        if (xor_bits & 1ULL) {

            if ((nbits - position) < period) {
                break;  // no room left to succeed further
            }

            if (count >= period) {  // we found a run

                results_ptr->data[START] = position - (count - 1);
                results_ptr->data[WIDTH] = period + count;
                results_ptr++;
            }

            count = 0;
        } else {

            count++;
        }

        xor_bits >>= 1;
    }

    if (count >= period) {  // process the final run, if any

        results_ptr->data[START] = 0;
        results_ptr->data[WIDTH] = period + count;
        results_ptr++;
    }

    results_ptr->token = SENTINAL;
}

void number_runs(uint64_t number, uint8_t bit_length, overlay_t *results) {

    overlay_t sub_results[bit_length];
    uint8_t limit = bit_length / 2 + 1;
    uint64_t mask = (1ULL << (bit_length - 1)) - 1;

    overlay_t *results_ptr = results;
    results_ptr->token = SENTINAL;

    for (uint8_t period = 1; period < limit; period++) {

        uint64_t xor_bits = mask & (number ^ (number >> period));  // heart of the code
        period_runs(xor_bits, bit_length - period, period, sub_results);

        for (size_t i = 0; sub_results[i].token != SENTINAL; i++) {

            bool stop = false;  // combine previous and current results

            for (size_t j = 0; !stop && results[j].token != SENTINAL; j++) {

                // lower period result disqualifies higher period result over the same span 
                stop = (sub_results[i].token == results[j].token);
            }

            if (!stop) {

                (results_ptr++)->token = sub_results[i].token;
                results_ptr->token = SENTINAL;
            }
        }

        mask >>= 1;
    }
}

int main() {

    overlay_t results[NUMBER_OF_BITS];

    for (uint8_t bit_length = 2; bit_length < 25; bit_length++) {

        int best_results = -1;
        uint64_t best_number = 0;

        for (uint64_t number = 1ULL << (bit_length - 1); number < (1ULL << bit_length); number++) {

            // from the discussion comments, I should be able to solve this
            // with just bit strings that begin "11...", so toss the rest
            if ((number & (1ULL << (bit_length - 2))) == 0ULL) {

                continue;
            }

            uint64_t reversed = 0;

            for (uint8_t i = 0; i < bit_length; i++) {

                if (number & (1ULL << i)) {

                    reversed |= (1ULL << ((bit_length - 1) - i));
                }
            }

            if (reversed > number) {

                continue;  // ~ 1/4 of bit_strings are simply reversals, toss 'em
            }

            number_runs(number, bit_length, results);
            overlay_t *results_ptr = results;
            int count = 0;

            while ((results_ptr++)->token != SENTINAL) {

                count++;
            }

            if (count > best_results) {

                best_results = count;
                best_number = number;
            }
        }

        char *best_string = malloc(bit_length + 1);
        uint64_t number = best_number;
        char *string_ptr = best_string;

        for (int i = bit_length - 1; i >= 0; i--) {

            *(string_ptr++) = (number & (1ULL << i)) ? '1' : '0';
        }

        *string_ptr = '\0';

        printf("%u %d %s\n", bit_length, best_results, best_string);

        free(best_string);
    }

    return 0;
}

Saída:

> gcc -O2 run-count.c -o run-count
> ./run-count
2 1 11
3 1 110
4 2 1100
5 2 11000
6 3 110011
7 4 1100100
8 5 11001100
9 5 110010011
10 6 1100110011
11 7 11001100100
12 8 110110011011
13 8 1100100010011
14 10 11001001100100
15 10 110010011001000
16 11 1100100110010011
17 12 11001100100110011
18 13 110011001001100100
19 14 1101001011010010100
20 15 11010110100101101011
21 15 110010011001001100100
22 16 1100101001011010010100
23 17 11010010110100101001011
24 18 110100101001011010010100
25 19 1100100110010001001100100
26 20 11010010100101101001010010
27 21 110010011001000100110010011
28 22 1101001010010110100101001011