introduction

Supposons un instant que les vipères et la falaise ne soient qu'à deux pas, au lieu de trois.

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

Vous êtes, malheureusement, captif d'un tortionnaire sadique. Vous devez faire un pas à gauche ou à droite à chaque tour. Sinon, ils vous abattent instantanément. Vous êtes autorisé à planifier vos étapes à l'avance, mais une fois que vous avez fait votre premier pas, vous ne pouvez pas modifier votre plan. (Et pas de flânerie non plus; ils vous tireront dessus.)

Soudain, une idée lumineuse me vient à l'esprit ...

Ah! Je peux simplement alterner les pas à droite et à gauche! Pas à droite, pas à gauche, pas à droite, pas à gauche, etc.

Ah ah ah, pas si vite. Comme je l'ai dit, le tortionnaire est sadique. Ils peuvent choisir si vous prenez chaque étape, ou chaque deuxième étape, ou chaque troisième étape, et ainsi de suite. Donc, si vous choisissez naïvement la séquence, RLRLRL...ils peuvent vous forcer à faire chaque deuxième étape, qui commence par LL. Euh oh! Vous avez été mordu par des vipères! La noirceur vous envahit et tout le reste s'estompe ...

En fait non, tu n'es pas encore mort. Vous devez toujours proposer votre plan. Après y avoir réfléchi pendant quelques minutes, vous réalisez que vous êtes condamné. Il n'y a aucun moyen de planifier une série d'étapes qui garantiront votre survie. Le mieux que vous puissiez trouver est RLLRLRRLLRR. ¹ Onze étapes sûres et pas plus. Si la douzième étape est R, alors le tortionnaire vous fera faire chaque étape, puis les trois dernières étapes vous enverront hors de la falaise. Si la douzième étape est L, alors le tortionnaire vous fera faire toutes les trois étapes ( LRLL), ce qui vous mettra dans la couvée des vipères et de leurs morsures mortelles.

Vous choisissez Rcomme la douzième étape, en espérant retarder votre disparition aussi longtemps que possible. Avec le vent qui gronde dans vos oreilles, vous vous demandez ...

Et si j'avais trois étapes?

Alerte spoil!

Tu mourrais encore. En fin de compte, peu importe le nombre d'étapes que vous avez, il y aura un moment où, quel que soit le choix que vous fassiez, il y a une séquence d'étapes que votre tortionnaire peut choisir pour vous assurer de rencontrer votre destin mortel. ² Cependant, lorsque les vipères et la falaise sont à trois pas, vous pouvez faire un total de 1160 pas sûrs et quand ils sont à quatre pas, il y a au moins 13 000 pas sûrs! ³

Le défi

Étant donné un seul entier n < 13000, affichez une séquence d' nétapes sûres, en supposant que la falaise et les vipères sont à quatre pas.

Règles

• Peut être un programme complet ou une fonction.
• L'entrée peut être prise via STDIN ou équivalent, ou comme argument de fonction.
• Sortie doit avoir deux caractères distincts (qui peut être +/-, R/L, 1/0, etc.).
• Tout espace dans la sortie n'a pas d'importance.
• Le codage en dur d'une solution n'est pas autorisé. Cela banaliserait ce défi.
• Votre programme devrait (en théorie) se terminer dans un laps de temps décent. Comme dans, cela n=13000peut prendre un mois, mais cela ne devrait pas prendre mille ans ou plus. Autrement dit, pas de force brute. (Eh bien, essayez au moins de l'éviter.)
• Bonus à vie: fournissez une série d' 2000étapes sûres. Si vous faites cela, le tortionnaire sera tellement impressionné par votre ténacité, votre persévérance et votre prévoyance qu'ils vous laisseront vivre. Cette fois. (Traitez cette séquence comme un nombre binaire et fournissez l'équivalent décimal pour la vérification. Ceci est destiné à récompenser les réponses qui se terminent rapidement car les réponses peuvent prendre très longtemps.)
• Score: octets , sauf si vous vous qualifiez pour le bonus - multipliez par 0,75 .

Survivre!

¹ Il y a une bonne explication de ce problème et de la "solution" par l'une des stars de Numberphile, James Grime, sur sa chaîne YouTube ici: https://www.youtube.com/watch?v=pFHsrCNtJu4 .

² Cette conjecture vieille de 80 ans, connue sous le nom de problème de divergence d'Erdos, a été prouvée très récemment par Terence Tao. Voici un très bel article sur Quanta Magazine à ce sujet: https://www.quantamagazine.org/20151001-tao-erdos-discrepancy-problem/ .

³ Source: A SAT Attack on the Erdos Discrepancy Conjecture , par Boris Konev et Alexei Lisitsa. Consulté ici: 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);}}}}

L'entrée est considérée comme un argument de ligne de commande.

Cela essaie presque toutes les possibilités (la seule restriction est que les 8 premières étapes ne doivent aller que dans -1..1), en allant pas à pas, en utilisant une heuristique magique vaudou pour choisir la première façon d'essayer.

Il résout 2000 et même 4000 en 1 seconde sur mon ordinateur (assez rapide). Besoin de plus de RAM pour les plus grands nombres; la plus grande entrée que j'ai résolue dans les 8 Go est 5023 et cela a pris environ 30 secondes.

Représentation décimale de la solution pour 2000 étapes, comme requis pour le bonus:

67629177464446960798008264442022667063957880432486338092706841703491740570274032860458934082821213021464065304260003487277917407152662394728833698812373924467640518368465012204980858438160127647802572983143425507448999967241207186701518207195015015739598846687434709056793597015487555707466358473564611432637890414593517116857771284711814076853125419306285869381974622557155019992727242896503018802441210966188045211779436703341152749688824296759097963388158731237092792251164105828728858516951458791084595247591674731645830905744761534078963607725435881491831508342871545788662307953494333833994658998

Ajoutez- Yble dans CJam pour reconvertir en binaire.

À propos de l'heuristique: d'abord, il y a un modèle que j'utilise: toutes les 9 étapes essaient de répéter les 9 premières, sauf chaque (9 * x) e étape essaie de répéter la xième étape. Ceci est inspiré de la solution que j'ai téléchargée et utilisée (codée en dur) dans ma réponse python.

Je garde une trace du nombre de fois où je me suis écarté du modèle, et aussi du nombre de fois où je suis arrivé à un "bord" (à 1 pas de la mort). La fonction heuristique est essentiellement une combinaison pondérée de ces 2 nombres et du nombre de pas effectués jusqu'à présent.

L'heuristique pourrait être encore modifiée pour améliorer la vitesse, et il existe plusieurs façons d'y ajouter un facteur aléatoire.
En fait, je viens de lire sur les fonctions multiplicatives par rapport à ce problème, et il semble que cela puisse apporter une amélioration significative (TODO: implémentez-le plus tard).

Non golfé et commenté:

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 octets

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])

C'est assez rapide, pour une méthode de force brute, ne prenant que quelques secondes pour n = 223, mais beaucoup plus pour n> = 224.

Explication: Gardez une trace d'une liste de paires chaîne-liste (s, u), où la liste u est telle que u [i] est la position actuelle après avoir suivi chaque cinquième étape de la chaîne. Pour chaque chaîne de la liste, essayez d'ajouter "L" ou "R", puis modifiez les valeurs de la liste qui se croisent. (c.-à-d. si la chaîne résultante a une longueur de 10, ajoutez ou soustrayez 1 des positions 1, 2, 5 et 10, selon les directions que vous avez déplacées). Si vous dépassez 3 ou -3 jetez la nouvelle paire, sinon conservez-la dans la liste. Les cordes les plus longues sont conservées à la fin. Une fois que vous avez une chaîne de longueur n, retournez-la.

Python 2, 729 octets

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]

Je pense que cela donne également droit au bonus si l'idée est de "récompenser des réponses qui se terminent rapidement".

Cependant, c'est une réponse codée en dur, qui n'est pas dans l'esprit du défi (bien qu'elle ne soit pas explicitement interdite lorsque je l'ai écrite).