Wprowadzenie

Załóżmy przez chwilę, że żmije i klif są tylko dwa kroki, a nie trzy.

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

Niestety jesteś uwięzionym sadystycznym oprawcą. Za każdym zakrętem musisz zrobić krok w lewo lub w prawo. Jeśli tego nie zrobisz, natychmiast zastrzelą cię. Możesz wcześniej zaplanować swoje kroki, ale kiedy zrobisz pierwszy krok, nie możesz zmienić swojego planu. (I nie ma sensu; zastrzelą cię.)

Nagle przychodzi na myśl jasny pomysł ...

Ach! Mogę tylko na przemian kroczyć w prawo i lewo! Krok w prawo, krok w lewo, krok w prawo, krok w lewo i tak dalej ...

Ah ah ah, nie tak szybko. Jak powiedziałem, oprawca jest sadystyczny. Mogą wybrać, czy podejmiesz każdy krok, czy co drugi krok, czy co trzeci krok i tak dalej. Więc jeśli naiwnie wybierzesz sekwencję RLRLRL..., mogą zmusić cię do zrobienia co drugiego kroku, który zaczyna się od LL. O o! Zostałeś ugryziony przez żmije! Ciemność otacza cię i wszystko inne znika ...

Właściwie nie, jeszcze nie jesteś martwy. Nadal musisz wymyślić swój plan. Po kilku minutach zastanowienia zdajesz sobie sprawę, że jesteś skazany. Nie ma możliwości zaplanowania szeregu kroków, które zagwarantują ci przetrwanie. Najlepsze, co możesz wymyślić, to RLLRLRRLLRR. ¹ Jedenaście bezpiecznych kroków i nie więcej. Jeśli dwunasty krok jest R, to oprawca zmusi cię do zrobienia każdego kroku, a następnie trzy ostatnie kroki wyślą cię z klifu. Jeśli dwunasty krok jest L, to oprawca zmusi cię do zrobienia co trzeciego kroku ( LRLL), co wprawia cię w stan lęgowy żmii i ich śmiertelnych ugryzień.

Ty wybierasz Rjako dwunasty krok, mając nadzieję na jak najdłuższe opóźnienie śmierci. Gdy w uszach ryczy wiatr, zastanawiasz się ...

Co jeśli miałbym trzy kroki?

Alert spoilera!

Nadal byś umarł. Jak się okazuje, bez względu na to, ile kroków masz, będzie taki moment, w którym bez względu na dokonany przez ciebie wybór, oprawca może wykonać sekwencję kroków, aby upewnić się, że spotkasz swój śmiertelny los. ² Jednakże, gdy żmije i klif znajdują się w odległości trzech kroków, możesz wykonać łącznie 1160 bezpiecznych kroków, a gdy są cztery kroki dalej, jest co najmniej 13 000 bezpiecznych kroków! ³⁾

Wyzwanie

Biorąc pod uwagę jedną liczbę całkowitą n < 13000, wypisz sekwencję nbezpiecznych kroków, zakładając, że klif i żmije znajdują się w odległości czterech kroków.

Zasady

• Może być pełnym programem lub funkcją.
• Dane wejściowe mogą być pobierane przez STDIN lub równoważne, lub jako argument funkcji.
• Wyjście musi mieć dwa różne znaki (które mogą być +/-, R/L, 1/0, itd.).
• Wszelkie białe znaki na wydruku nie mają znaczenia.
• Kodowanie rozwiązania jest niedozwolone. To by trywializowało to wyzwanie.
• Twój program powinien (teoretycznie) zakończyć się w przyzwoitym czasie. Jak w, n=13000może to potrwać miesiąc, ale nie powinno to zająć tysiąca lat lub więcej. Oznacza to, że nie ma brutalnej siły. (Cóż, przynajmniej spróbuj tego uniknąć).
• Bonus życiowy: zapewnij szereg 2000bezpiecznych kroków. Jeśli to zrobisz, oprawca będzie pod wrażeniem twojej wytrwałości, wytrwałości i przewidywania, że ​​pozwolą ci żyć. Ten jeden raz. (Potraktuj tę sekwencję jako liczbę binarną i podaj dziesiętny ekwiwalent do weryfikacji. Ma to na celu nagradzanie odpowiedzi, które kończą się szybko, ponieważ odpowiedzi mogą trwać bardzo długo).
• Wynik: bajty , chyba że kwalifikujesz się do premii - pomnóż przez 0,75 .

Przetrwać!

¹ Istnieje dobre wyjaśnienie tego problemu i „rozwiązania” jednej z gwiazd Numberphile, Jamesa Grime'a, na jego kanale na YouTube: https://www.youtube.com/watch?v=pFHsrCNtJu4 .

² Ta 80-letnia hipoteza, znana jako problem rozbieżności Erdosa, bardzo niedawno udowodnił Terence Tao. Oto bardzo fajny artykuł na temat magazynu Quanta na ten temat: https://www.quantamagazine.org/20151001-tao-erdos-discrepancy-problem/ .

³ Źródło: Atak SAT na hipotezę rozbieżności Erdosa , autorstwa Borisa Koneva i Aleksieja Lisicy. Źródło: 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);}}}}

Dane wejściowe są traktowane jako argument wiersza poleceń.

Wypróbowuje prawie wszystkie możliwości (jedynym ograniczeniem jest to, że pierwsze 8 kroków powinno iść tylko w zakresie -1..1), idąc krok po kroku, używając magicznej heurystyki voodoo, aby wybrać, który sposób spróbować najpierw.

Rozwiązuje 2000, a nawet 4000 w ciągu 1 sekundy na moim (dość szybkim) komputerze. Potrzebuje więcej pamięci RAM dla większych liczb; największe wejście, które rozwiązałem w obrębie 8 GB, to 5023 i zajęło to około 30 sekund.

Reprezentacja dziesiętna rozwiązania dla 2000 kroków, zgodnie z wymaganiem premii:

67629177464446960798008264442022667063957880432486338092706841703491740570274032860458934082821213021464065304260003487277917407152662394728833698812373924467640518368465012204980858438160127647802572983143425507448999967241207186701518207195015015739598846687434709056793597015487555707466358473564611432637890414593517116857771284711814076853125419306285869381974622557155019992727242896503018802441210966188045211779436703341152749688824296759097963388158731237092792251164105828728858516951458791084595247591674731645830905744761534078963607725435881491831508342871545788662307953494333833994658998

Dołącz Ybdo niego w CJam, aby przekonwertować z powrotem na binarny.

O heurystyce: po pierwsze, używam wzorca: co 9 kroków spróbuj powtórzyć pierwsze 9, z wyjątkiem tego, że każdy (9 * x) krok próbuje powtórzyć krok x. Jest to inspirowane rozwiązaniem, które pobrałem i użyłem (na stałe) w mojej odpowiedzi na python.

Śledzę, ile razy odbiegałem od wzoru, a także ile razy dotarłem do „krawędzi” (1 krok od śmierci). Funkcja heurystyczna jest w zasadzie ważoną kombinacją tych 2 liczb i liczby wykonanych do tej pory kroków.

Heurystykę można jeszcze bardziej ulepszyć, aby poprawić prędkość, i istnieje kilka sposobów dodania do niej czynnika losowego.
W rzeczywistości, właśnie przeczytałem o funkcjach multiplikatywnych w związku z tym problemem i wygląda na to, że może to zapewnić znaczną poprawę (TODO: zaimplementuj to później).

Nie golfił i skomentował:

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 bajtów

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

Jest to dość szybkie, jak na metodę brutalnej siły, zajmuje tylko kilka sekund dla n = 223, ale znacznie dłużej dla n> = 224.

Objaśnienie: Śledź listę par ciągów list (s, u), gdzie lista u jest taka, że ​​u [i] jest bieżącą pozycją po każdym i-tym kroku w łańcuchu. Dla każdego ciągu na liście spróbuj dodać „L” lub „R”, a następnie zmień wartości na przecinającej się liście. (tzn. jeśli wynikowy ciąg ma długość 10, dodaj lub odejmij 1 od pozycji 1, 2, 5 i 10, zgodnie z kierunkami, które wykonałeś). Jeśli przekroczysz 3 lub -3, wyrzuć nową parę, w przeciwnym razie pozostaw ją na liście. Najdłuższe ciągi znaków są przechowywane na końcu. Po uzyskaniu ciągu o długości n zwróć go.

Python 2, 729 bajtów

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]

Myślę, że to również kwalifikuje się do premii, jeśli chodzi o „nagradzanie odpowiedzi, które szybko się kończą”.

Jest to jednak mocno zakodowana odpowiedź, która nie jest zgodna z duchem wyzwania (choć nie jest wyraźnie niedozwolona, ​​gdy ją napisałem).