Introdução

Suponha por um momento que as víboras e o penhasco estejam a apenas dois passos, em vez de três.

            o
           ---
Hsss!       |
 ';;' ___  /_\  ___  _
                      |

Você é, infelizmente, prisioneiro de um torturador sádico. Você deve dar um passo à esquerda ou à direita a cada curva. Caso contrário, eles matam você instantaneamente. Você tem permissão para planejar suas etapas com antecedência, mas depois de dar sua primeira etapa, você não poderá alterar seu plano. (E também não demore; eles vão atirar em você.)

De repente, uma idéia brilhante vem à mente ...

Ah! Eu posso apenas alternar pisando direita e esquerda! Passo para a direita, passo para a esquerda, passo para a direita, passo para a esquerda e assim por diante ...

Ah ah ah, não tão rápido. Como eu disse, o torturador é sádico. Eles escolhem se você dá cada passo, ou segundo passo, ou terceiro passo, e assim por diante. Portanto, se você escolher ingenuamente a sequência RLRLRL..., eles poderão forçá-lo a dar cada segundo passo, que começa com LL. Oh! Você foi mordido por víboras! A escuridão toma conta de você e tudo mais desaparece ...

Na verdade não, você ainda não está morto. Você ainda precisa propor seu plano. Depois de pensar por alguns minutos, você percebe que está condenado. Não há como planejar uma série de etapas que garantam sua sobrevivência. O melhor que você pode fazer é RLLRLRRLLRR. ¹ Onze etapas seguras e nada mais. Se o décimo segundo passo for R, o Torturador fará com que você dê todos os passos e, em seguida, os três últimos passos o enviarão do penhasco. Se o décimo segundo passo for L, o Torturador fará com que você dê cada terceiro passo ( LRLL), o que o coloca bem na ninhada de víboras e suas mordidas letais.

Você escolhe Ro décimo segundo passo, esperando adiar sua morte o maior tempo possível. Com o vento rugindo em seus ouvidos, você se pergunta ...

E se eu tivesse três etapas?

Alerta de spoiler!

Você ainda morreria. Acontece que, não importa quantos passos você tenha, haverá algum momento em que, independentemente da escolha que você faça, há uma sequência de passos que seu Torturador pode seguir para garantir que você cumpra seu destino mortal. ² No entanto, quando as víboras e o penhasco estão a três passos, você pode fazer um total de 1160 etapas seguras e, quando estão a quatro etapas, existem pelo menos 13.000 etapas seguras! ³

O desafio

Dado um único número inteiro n < 13000, produza uma sequência de netapas seguras, assumindo que o penhasco e as víboras estão a quatro passos.

Regras

• Pode ser um programa completo ou uma função.
• A entrada pode ser obtida através de STDIN ou equivalente, ou como argumento de função.
• Saída deve ter dois caracteres distintos (que pode ser +/-, R/L, 1/0, etc.).
• Qualquer espaço em branco na saída não importa.
• A codificação embutida de uma solução não é permitida. Isso banalizaria esse desafio.
• Seu programa deve (em teoria) terminar em uma quantidade decente de tempo. Como n=13000pode demorar um mês, mas não deve demorar mil anos ou mais. Ou seja, sem força bruta. (Bem, pelo menos tente evitá-lo.)
• Bônus de vida: forneça uma série de 2000etapas seguras. Se você fizer isso, o Torturador ficará tão impressionado com sua tenacidade, perseverança e premeditação que eles deixarão você viver. Desta vez. (Trate esta sequência como um número binário e forneça o equivalente decimal para verificação. Isso visa recompensar respostas que terminam rapidamente, pois as respostas podem demorar muito tempo.)
• Pontuação: bytes , a menos que você se qualifique para o bônus - multiplique por 0,75 .

Sobreviver!

¹ Há uma boa explicação sobre esse problema e a "solução" de uma das estrelas do Numberphile, James Grime, em seu canal do YouTube aqui: https://www.youtube.com/watch?v=pFHsrCNtJu4 .

² Essa conjectura de 80 anos, conhecida como problema de discrepância de Erdos, foi provada muito recentemente por Terence Tao. Aqui está um artigo muito bom na Revista Quanta sobre isso: https://www.quantamagazine.org/20151001-tao-erdos-discrepancy-problem/ .

³ Fonte: Um ataque do SAT à conjectura de discrepância de Erdos , de Boris Konev e Alexei Lisitsa. Retirado daqui: http://arxiv.org/pdf/1402.2184v2.pdf .

Java, 915 * 0,75 = 686,25

import java.util.*;class E implements Comparable<E>{static
int n,m,t,u;byte[]a;int k=2,b,d;E(){a=new byte[5];a[1]=13;}E(E
x){a=Arrays.copyOf(x.a,n+1);k=x.k;d=x.d;b=x.b;}int
g(int x){return(a[x]+1)%3-1;}void s(int x,int y){a[x]=(byte)(a[x]/3*3+(y+3)%3);}void
S(int x,int y){a[x]=(byte)(a[x]%3+(y+3)*3);}E
w(int x){if(g(k)==-x)return null;E e=new E(this);e.s(k,x);e.S(e.k++,x);for(m=0;++m<k;)if(k%m<1){u=e.a[m]/3-3+x;if(u==(k<9?2:4)*x)return
null;e.S(m,u);if(u==3*x){e.b++;if(k+m<=n){if(e.g(k+m)==x)return
null;e.s(k+m,-x);}}}return e;}public int compareTo(E o){m=d-o.d+(b-o.b)/60+(o.k-k)/150;return
m==0?o.k-k:m;}public static void main(String[]a){n=Integer.valueOf(a[0]);Queue<E>q=new PriorityQueue<>();q.add(new
E());for(;;){E x=q.remove(),y;if(x.k>n){for(t=0;++t<x.k;)System.out.print((x.g(t)+1)/2);return;}t=x.g(x.k<9?1:x.k%9==0?x.k/9:x.k%9);y=x.w(t);if(y!=null)q.add(y);y=x.w(-t);if(y!=null){y.d++;q.add(y);}}}}

A entrada é aceita como um argumento da linha de comandos.

Isso tenta quase todas as possibilidades (a única restrição é que os oito primeiros passos só devem ir dentro de -1..1), indo passo a passo, usando uma heurística mágica de vodu para escolher qual caminho tentar primeiro.

Resolve 2000 e até 4000 em 1 segundo no meu computador (bastante rápido). Precisa de mais RAM para números maiores; a maior entrada que resolvi em 8 GB é 5023 e demorou cerca de 30 segundos.

Representação decimal da solução para as etapas de 2000, conforme exigido para o bônus:

67629177464446960798008264442022667063957880432486338092706841703491740570274032860458934082821213021464065304260003487277917407152662394728833698812373924467640518368465012204980858438160127647802572983143425507448999967241207186701518207195015015739598846687434709056793597015487555707466358473564611432637890414593517116857771284711814076853125419306285869381974622557155019992727242896503018802441210966188045211779436703341152749688824296759097963388158731237092792251164105828728858516951458791084595247591674731645830905744761534078963607725435881491831508342871545788662307953494333833994658998

Acrescente Yba ele no CJam para converter novamente em binário.

Sobre a heurística: primeiro, há um padrão que estou usando: a cada 9 etapas, tente repetir as 9 primeiras, exceto a cada 9 (x) etapa, tente repetir a décima segunda etapa. Isso é inspirado na solução que baixei e usei (codificada) na minha resposta python.

Estou acompanhando o número de vezes que me desviei do padrão e também o número de vezes que cheguei a um "limite" (1 passo após a morte). A função heurística é basicamente uma combinação ponderada desses 2 números e o número de etapas executadas até o momento.

A heurística pode ser aprimorada ainda mais para melhorar a velocidade, e existem várias maneiras de adicionar um fator aleatório a ela também.
De fato, acabei de ler sobre funções multiplicativas em relação a esse problema, e parece que isso pode proporcionar uma melhoria significativa (TODO: implemente isso mais tarde).

Ungolfed e comentou:

import java.util.*;

public class Erdos implements Comparable<Erdos> {
    static int n; // input (requested number of steps)
    static int m, t, u; // auxiliary variables

    byte[] a; // keeps each step and sum combined into 1 byte
    int k = 2; // number of steps + 1 (steps are 1-based)
    int edge; // number of times we got to an edge
    int diff; // number of differences from the expected pattern

    // start with one step
    Erdos() {
        a = new byte[5];
        set(1, 1);
        setSum(1, 1);
    }

    // copy constructor
    Erdos(Erdos x) {
        a = Arrays.copyOf(x.a, n + 1);
        k = x.k;
        diff = x.diff;
        edge = x.edge;
    }

    // get the x'th step (can be -1, 0 or 1)
    int get(int x) {
        return (a[x] + 1) % 3 - 1;
    }

    // set the x'th step
    void set(int x, int y) {
        a[x] = (byte) (a[x] / 3 * 3 + (y + 3) % 3);
    }

    // get the sum of every x'th step (should be within -3..3)
    int getSum(int x) {
        return a[x] / 3 - 3;
    }

    // set the sum of every x'th step
    void setSum(int x, int y) {
        a[x] = (byte) (a[x] % 3 + (y + 3) * 3);
    }

    // try to add a step with value x (1 or -1)
    Erdos grow(int x) {
        if (get(k) == -x) // predetermined step doesn't match
            return null;
        Erdos e = new Erdos(this);
        e.set(k, x);
        e.setSum(e.k++, x);
        for (m = 0; ++m < k;)
            if (k % m < 1) { // check all divisors of k
                u = e.getSum(m) + x; // updated sum
                if (u == (k < 9 ? 2 : 4) * x) // use limit 2 for the first 8 steps, 4 for the rest
                    return null; // dead
                e.setSum(m, u);
                if (u == 3 * x) { // we're at an edge
                    e.edge++;
                    if (k + m <= n) { // predetermine future step - should be going back
                        if (e.get(k + m) == x) // conflict
                            return null;
                        e.set(k + m, -x);
                    }
                }
            }
        return e;
    }

    public int compareTo(Erdos o) { // heuristic function
        m = diff - o.diff + (edge - o.edge) / 60 + (o.k - k) / 150;
        return m == 0 ? o.k - k : m;
    }

    public static void main(String[] a) {
        n = Integer.valueOf(a[0]);
        Queue<Erdos> q = new PriorityQueue<>();
        q.add(new Erdos());
        for (;;) {
            Erdos x = q.remove(), y;
            if (x.k > n) { // we made it
                for (t = 0; ++t < x.k;)
                    System.out.print((x.get(t) + 1) / 2);
                return;
            }
            t = x.get(x.k < 9 ? 1 : x.k % 9 == 0 ? x.k / 9 : x.k % 9); // next step based on the pattern
            y = x.grow(t);
            if (y != null)
                q.add(y);
            y = x.grow(-t);
            if (y != null) {
                y.diff++;
                q.add(y);
            }
        }
    }
}

Python 2, 236 bytes

n=input();r=len;u=[("",[0]*(n//4))]
while n>r(u[-1][0]):
 y,t=u.pop()
 for c in 0,1:
  s=t[:];u+=(y+"LR"[c],s),
  for i in range(r(s)):
   if-~r(y)//-~i*-~i==-~r(y):s[i]+=2*c-1;
   if abs(s[i])>3:u.pop();break;
print(u[-1][0])

Isso é bastante rápido, para um método de força bruta, levando apenas alguns segundos para n = 223, mas muito mais tempo para n> = 224.

Explicação: Mantenha o controle de uma lista de pares de listas de cadeias (s, u), em que a lista u é tal que u [i] é a posição atual depois de seguir cada i-ésimo passo na cadeia. Para cada sequência da lista, tente adicionar "L" ou "R" e altere os valores na lista que se cruzam. (ou seja, se a sequência resultante tiver comprimento 10, adicione ou subtraia 1 das posições 1,2,5 e 10, de acordo com as instruções que você moveu). Se você exceder 3 ou -3, jogue o novo par fora, caso contrário, mantenha-o na lista. As seqüências mais longas são mantidas no final. Depois de ter uma sequência de comprimento n, retorne-a.

Python 2, 729 bytes

n=0
for x in"eJytVU2LwyAQPWzTvZjjspcsxFYTBdNuQSEF+///1jp+p5o0hYVSBl9nfOObNz1MlAgqzMcEEwQkDyIkFpDYCW0UnChbyZJiK2sfhDcYmu9hT0GdIPQvLduAmoCvvqEssvq84CVCpLzrNcOOspLhY6/KswB6FmoSxGPBcWts7lsMp/0q83da1hgC6k7GoqBir1ruAFIVvWIdTi++oGIAyZw8mkuG03uDDc+rEsSWTmFBwbLgtTF8hl1e/lpCigR7+pM5V9lIqVJBjStzKNRRQDp6UOrvwga6VFrGcWz6YHwLNYWUYeZfWO/DQTq7i4dAxixeszmtFEw7Cr5v9R3lRVF55TDzY6QRrSfzF9NLE7lAZ+vLnGgYLZ/FlCuoRcOugeFduHTqRWmyh1J91XpIndIbEk8jifL8hs8qQ8vjAVoGqhK5Tm/O5svpXd82QH4Azq05kYnhj93PzLbcTisFzXWfDqIC5zsq3jU7UUhSh1R3L4+i4HCXKlrGyywSBttPr2zpL4gCDPtk2HPN5tgZFomzSDPfGAlASus+e4KlLcjS0vPQ0f5/mR/r1s4PcxsgMLRSMp617AveCuup2OCAPBT6yltWrPO9azsbp6fphR87Lc7VzcbEt5F4Ydg/NzhXTA==".decode("base64").decode("zip"):n=n*64+ord(x)
print bin(n)[2:input()+2]

Eu acho que isso também se qualifica para o bônus se a idéia for "recompensar respostas que terminem rapidamente".

No entanto, essa é uma resposta codificada, que não está no espírito do desafio (embora não seja explicitamente proibida quando eu a escrevi).