pengantar

Misalkan sesaat bahwa ular berbisa dan tebing hanya berjarak dua langkah, bukan tiga.

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

Sayangnya, Anda adalah tawanan penyiksa sadis. Anda harus mengambil langkah ke kiri atau ke kanan setiap belokan. Jika tidak, mereka langsung menembak mati Anda. Anda diizinkan merencanakan langkah-langkah Anda sebelumnya, tetapi begitu Anda mengambil langkah pertama, Anda tidak dapat mengubah rencana Anda. (Dan juga tidak berlama-lama; mereka akan menembakmu.)

Tiba-tiba, sebuah ide cemerlang muncul di benak saya ...

Ah! Saya bisa saja berganti melangkah ke kanan dan kiri! Langkah kanan, langkah kiri, langkah kanan, langkah kiri, dan seterusnya ...

Ah ah ah, tidak secepat itu. Seperti yang saya katakan, penyiksa itu sadis. Mereka dapat memilih apakah Anda mengambil setiap langkah, atau setiap langkah kedua, atau setiap langkah ketiga, dan seterusnya. Jadi jika Anda secara naif memilih urutannya RLRLRL...maka mereka dapat memaksa Anda untuk mengambil setiap langkah kedua, yang dimulai dengan LL. Uh oh! Anda digigit ular berbisa! Blackness menyapu Anda dan semua yang lain menghilang ...

Sebenarnya tidak, Anda belum mati. Anda masih harus memikirkan rencana Anda. Setelah memikirkannya selama beberapa menit, Anda sadar bahwa Anda sudah dikutuk. Tidak ada cara untuk merencanakan serangkaian langkah yang akan menjamin kelangsungan hidup Anda. Yang terbaik yang bisa Anda dapatkan adalah RLLRLRRLLRR. ¹ Sebelas langkah aman dan tidak lebih. Jika langkah kedua belas R, maka Torturer akan membuat Anda mengambil setiap langkah dan kemudian tiga langkah terakhir mengirim Anda keluar dari tebing. Jika langkah kedua belas L, maka Penyiksa akan membuat Anda mengambil setiap langkah ketiga ( LRLL), yang menempatkan Anda tepat di induk ular berbisa dan gigitan mematikan mereka.

Anda memilih Rsebagai langkah kedua belas, berharap untuk menunda kematian Anda selama mungkin. Dengan angin menderu di telinga Anda, Anda bertanya-tanya pada diri sendiri ...

Bagaimana jika saya memiliki tiga langkah?

Peringatan spoiler!

Kamu masih akan mati. Ternyata, tidak peduli berapa banyak langkah yang Anda miliki, akan ada beberapa titik di mana tidak peduli pilihan apa yang Anda buat, ada urutan langkah-langkah yang dapat diambil oleh Torturer Anda untuk memastikan Anda memenuhi nasib Anda yang mematikan. ² Namun, ketika ular berbisa dan tebing tiga langkah lagi, Anda dapat mengambil total 1.160 langkah aman dan ketika mereka berjarak empat langkah lagi, setidaknya ada 13.000 langkah aman! ³

Tantangan

Dengan bilangan bulat tunggal n < 13000, mengeluarkan urutan nlangkah-langkah aman, dengan asumsi tebing dan ular berbisa berjarak empat langkah.

Aturan

• Bisa berupa program lengkap atau fungsi.
• Input dapat diambil melalui STDIN atau yang setara, atau sebagai argumen fungsi.
• Output harus memiliki dua karakter yang berbeda (yang bisa +/-, R/L, 1/0, dll).
• Setiap spasi putih dalam output tidak masalah.
• Pengkodean keras suatu solusi tidak diizinkan. Itu akan meremehkan tantangan ini.
• Program Anda harus (secara teori) selesai dalam jumlah waktu yang layak. Seperti dalam, n=13000mungkin butuh waktu sebulan, tetapi seharusnya tidak perlu seribu tahun atau lebih. Artinya, tidak ada kekuatan kasar. (Yah, setidaknya cobalah menghindarinya.)
• Bonus seumur hidup: sediakan serangkaian 2000langkah aman. Jika Anda melakukan ini, Torturer akan sangat terkesan dengan keuletan, ketekunan, dan pemikiran Anda sehingga mereka akan membiarkan Anda hidup. Kali ini (Perlakukan urutan ini sebagai angka biner dan berikan desimal yang setara untuk verifikasi. Ini dimaksudkan untuk menghargai jawaban yang selesai dengan cepat karena jawaban dibiarkan memakan waktu yang sangat lama.)
• Nilai: byte , kecuali Anda memenuhi syarat untuk bonus - kalikan dengan 0,75 .

Bertahan!

¹ Ada penjelasan yang bagus tentang masalah ini dan "solusi" oleh salah satu bintang Numberphile, James Grime, di saluran YouTube-nya di sini: https://www.youtube.com/watch?v=pFHsrCNtJu4 .

² Dugaan berusia 80 tahun ini, yang dikenal sebagai masalah ketidaksesuaian Erdos, terbukti baru-baru ini oleh Terence Tao. Berikut ini adalah artikel yang sangat bagus di Majalah Quanta tentang ini: https://www.quantamagazine.org/20151001-tao-erdos-discrepancy-problem/ .

³ Sumber: Serangan SAT pada Erdos Discrepancy dugaan , oleh Boris Konev dan Alexei Lisitsa. Diperoleh dari sini: 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);}}}}

Input diambil sebagai argumen baris perintah.

Ini mencoba hampir semua kemungkinan (satu-satunya batasan adalah bahwa 8 langkah pertama hanya boleh berjalan dalam -1.1.1), akan langkah demi langkah, menggunakan heuristik voodoo ajaib untuk memilih cara mana yang harus dicoba terlebih dahulu.

Ini memecahkan 2000 dan bahkan 4000 dalam 1 detik di komputer saya (cukup cepat). Membutuhkan lebih banyak RAM untuk jumlah yang lebih besar; input terbesar yang saya selesaikan dalam 8GB adalah 5023 dan butuh sekitar 30 detik.

Representasi desimal dari solusi untuk 2000 langkah, sebagaimana dipersyaratkan untuk bonus:

67629177464446960798008264442022667063957880432486338092706841703491740570274032860458934082821213021464065304260003487277917407152662394728833698812373924467640518368465012204980858438160127647802572983143425507448999967241207186701518207195015015739598846687434709056793597015487555707466358473564611432637890414593517116857771284711814076853125419306285869381974622557155019992727242896503018802441210966188045211779436703341152749688824296759097963388158731237092792251164105828728858516951458791084595247591674731645830905744761534078963607725435881491831508342871545788662307953494333833994658998

Tambahkan Ybke dalam CJam untuk mengkonversi kembali ke biner.

Tentang heuristik: pertama, ada pola yang saya gunakan: setiap 9 langkah mencoba untuk mengulangi 9 yang pertama, kecuali setiap langkah (9 * x) mencoba untuk mengulangi langkah ke-X. Ini terinspirasi dari solusi yang saya unduh dan gunakan (hardcoded) dalam jawaban python saya.

Saya melacak berapa kali saya menyimpang dari pola, dan juga berapa kali saya mencapai "tepi" (1 langkah dari kematian). Fungsi heuristik pada dasarnya adalah kombinasi dari 2 angka dan jumlah langkah yang diambil sejauh ini.

Heuristik dapat diubah lebih lanjut untuk meningkatkan kecepatan, dan ada beberapa cara untuk menambahkan faktor acak ke dalamnya juga.
Bahkan, saya baru saja membaca tentang fungsi multiplikasi dalam kaitannya dengan masalah ini, dan sepertinya itu dapat memberikan peningkatan yang signifikan (TODO: implementasikan ini nanti).

Tidak dikumpulkan dan berkomentar:

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 byte

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

Ini cukup cepat, untuk metode brute-force-ish, hanya butuh beberapa detik untuk n = 223, tetapi jauh lebih lama untuk n> = 224.

Penjelasan: Melacak daftar pasangan string-list (s, u), di mana daftar u sedemikian rupa sehingga u [i] adalah posisi saat ini setelah mengikuti setiap langkah ke-5 dalam string. Untuk setiap string dalam daftar, cobalah untuk menambahkan "L" atau "R", lalu ubah nilai dalam daftar yang berpotongan. (yaitu jika string yang dihasilkan memiliki panjang 10, tambahkan atau kurangi 1 dari posisi 1,2,5 dan 10, sesuai dengan arah yang Anda pindahkan). Jika Anda melebihi 3 atau -3 membuang pasangan baru, jika tidak simpanlah dalam daftar. Senar terpanjang disimpan di akhir. Setelah Anda memiliki string dengan panjang n, kembalikan.

Python 2, 729 byte

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]

Saya pikir ini memenuhi syarat untuk bonus juga jika idenya adalah "untuk menghargai jawaban yang selesai dengan cepat".

Namun, ini adalah jawaban yang sulit, yang tidak sesuai dengan semangat tantangan (meskipun tidak secara eksplisit dianulir ketika saya menulisnya).