Bayangkan sebuah jalan yang terdiri dari <dan >dan berakhir dengan @, misalnya
><>@
Alat bantu jalan dimulai di sel paling kiri. Dia akan melintasi jalan sebagai berikut:
- Jika alat bantu berjalan di
@sel, dia mencapai tujuan dan selesai. - Jika alat bantu jalan ada di
>sel, seluruh jalur akan bergeser satu langkah ke kanan, secara siklis, membawa alat bantu jalan itu . - Jika alat bantu jalan ada di
<sel, seluruh jalur akan bergeser satu langkah ke kiri, secara siklis, membawa alat bantu jalan itu . - Setelah itu, walker mengambil satu langkah. Jika dia berada di kedua ujung jalan, dia bergerak menjauh dari ujung. Kalau tidak, ia terus bergerak ke arah yang ia bergerak pada langkah terakhir (mengabaikan rotasi), berjalan pada awalnya.
Mari kita bekerja melalui contoh di atas. Posisi walker ditandai dengan ^:
><>@ --rotate--> @><>
^ ^
step right (first step):
@><> --rotate--> ><>@
^ ^
step right:
><>@ --rotate--> @><>
^ ^
step left (dead end):
@><> --rotate--> ><>@
^ ^
step left:
><>@ --rotate--> @><>
^ ^
step left:
@><> Goal reached!
^
Pejalan itu mengunjungi 6 sel dalam proses (termasuk sel awal dan juga @, dan menghitung setiap sel sesering yang dikunjungi).
Berikut adalah contoh kecil, di mana walker diangkut melintasi tepi dengan rotasi:
>>@ --rotate--> @>>
^ ^
step right (first step):
@>> --rotate--> >@>
^ ^
step right (dead end):
>@> Goal reached!
^
Kali ini pejalan kaki mengunjungi 3 sel.
Kita dapat dengan mudah mengubah ini menjadi urutan bilangan bulat:
- Anda diberi bilangan bulat positif N , mis
9. - Anda menghitung representasi biner dari integer ini, misalnya
1001. - Kemudian putar
1ke>dan0menjadi<dan menambahkan sebuah@:><<>@. - Kami mengasosiasikan dengan N jumlah sel yang dikunjungi oleh walker dalam jumlah yang dibangun dengan cara ini.
Beberapa elemen pertama dari urutan yang dihasilkan adalah:
2, 3, 3, 4, 6, 4, 4, 5, 5, 5, 5, 5, 5, 5, 5, 6, 6,
6, 10, 6, 10, 8, 8, 6, 10, 8, 8, 6, 6, 6, 6, 7, 7
Ini mungkin tampak sangat arbitrer, tetapi urutan yang dihasilkan ternyata memiliki banyak struktur:
Untuk referensi, Anda dapat menemukan nomor 2048 pertama dari urutan dalam pastebin ini .
Tantangan
Anda menebaknya: Anda harus menghitung urutan di atas. Anda dapat melakukannya dengan satu dari tiga cara berikut:
- Anda dapat menghasilkan urutan tak terbatas (sementara memori mengizinkan), baik dengan terus-menerus mengeluarkan nilai (dipisahkan oleh karakter non-numerik) atau dengan menggunakan beberapa bentuk generator tak terbatas dalam bahasa yang mendukungnya. Jika Anda mencetak aliran tanpa batas ke STDOUT, Anda tidak perlu mencetak angka satu per satu, tetapi pastikan bahwa setiap angka akan dicetak setelah waktu yang terbatas (dan berurutan). Jika Anda menggunakan opsi ini, Anda tidak boleh mengambil input apa pun.
- Anda dapat mengambil bilangan bulat N sebagai input dan menghasilkan istilah N urutan.
- Anda dapat mengambil integer N sebagai input dan menghasilkan semuanya hingga istilah ke - N dari urutan, baik sebagai daftar atau string menggunakan pemisah yang tidak ambigu.
Karena saya tidak ingin menghukum bahasa yang tidak dapat dengan mudah mengkonversi antara basis, alih-alih bilangan bulat N Anda dapat mengambil representasi biner dari N , menggunakan 0s dan 1s seperti biasa (sebagai daftar atau string), dengan yang paling bit-signifikan dulu.
Anda dapat menulis sebuah program atau fungsi, mengambil input melalui STDIN (atau alternatif terdekat), argumen baris perintah atau argumen fungsi dan mengeluarkan hasilnya melalui STDOUT (atau alternatif terdekat), nilai pengembalian fungsi atau parameter function (out).
Aturan standar kode-golf berlaku.
Latar Belakang
Ini sebenarnya menghitung jumlah "ticks" seorang penerjemah langsung dari bahasa pemrograman esoterik saya Labyrinth perlu menafsirkan "path" sebagai kode sumber. Dalam hal itu, "walker" hanyalah penunjuk instruksi (yang memiliki posisi dan arah), @perintah mengakhiri program dan <dan >merupakan perintah modifikasi kode sumber.
Jawaban:
Jelly , 10 byte
Fungsi ini menerima integer tunggal dalam bentuk daftar digit binernya sebagai input.
Algoritma ini setara dengan yang dari jawaban @ Agawa001 .
Cobalah online! atau menghasilkan angka 2048 pertama .
Latar Belakang
Menghitung posisi di bawah jalan dari 0 hingga L , memberikan total posisi L +1 . L bertepatan jumlah digit biner dari angka N yang mengkodekan path. Dengan notasi ini, walker dimulai pada posisi 0 , tujuan pada posisi L .
Dengan setiap langkah yang diambil pejalan, ia semakin dekat dengan tujuan (ke arah yang saat ini ia jalani). Juga, dengan setiap langkah shift, tergantung pada apakah ia berjalan dengan atau melawan arah shifting, ia menambah atau mengurangi posisinya dengan 2 modulo L +1 , atau ia tetap di posisi saat ini.
Untuk mengubah arah, ia harus mendarat di posisi L - 1 (menghadap L ) atau posisi 1 (menghadap 0 ), lalu bergeser ke arahnya. Langkah selanjutnya yang diambilnya akan membawanya kembali ke posisi sebelumnya, menghadap ke arah yang berlawanan.
Jika L adalah genap, L - 1 adalah ganjil, jadi ia tidak dapat naik dari posisi awalnya ke L - 1 secara langsung. Satu-satunya cara untuk mencapainya adalah dengan melewati L , dibawa ke 0 dan mengambil langkah berikutnya untuk mendarat di 1 , lalu maju ke kanan. Ini membutuhkan posisi 2L yang lebih maju , yang dapat dilakukan tidak kurang dari langkah L.
Namun, setelah mengambil langkah L tanpa mengubah arah, ia akan mencapai tujuan. Menambahkan satu untuk sel awal, kami mendapatkan total sel L + 1 yang dikunjungi dalam kasus ini.
Jika L aneh, L - 1 genap, sehingga ia dapat mencapai posisi itu dengan digeser (L - 1) / 2 kali ke kanan. Jika posisi L - 1 di bawah angka 1 pada saat itu, ia akan digeser ke posisi L , berbalik, dan menginjak posisi L - 1 (menghadap ke kiri).
Ini mungkin atau mungkin tidak terjadi sebelum dia mencapai tujuannya, jadi ada dua kasus untuk dianalisis:
Jika ada kurang dari (L + 1) / 2 kejadian 1 dalam ekspansi biner N , mengambil langkah L tidak akan cukup untuk mengubah arah. Karena langkah - langkah L ini membawa walker ke tujuannya, menambahkan satu untuk sel awal, kami mendapatkan total sel L + 1 yang dikunjungi dalam kasus ini.
Jika ada setidaknya (L + 1) / 2 kejadian 1 dalam ekspansi biner dari N , maju ke ((L + 1) / 2) th terjadinya akan membutuhkan saya langkah, di mana saya adalah posisi awal kejadian yang dari 1 .
Dengan demikian, setelah mengambil langkah I , alat bantu jalan berada di posisi L - 1 , menghadap ke kiri. Untuk mengubah arah lagi, ia harus berjalan maju ke kiri ke posisi 1 . Namun, seperti dalam kasus genap, karena (L - 1) - 1 adalah ganjil, ini akan membutuhkan melalui 0 dan mengambil tidak kurang dari langkah L.
Karena jarak awal ke gawang di arah kiri adalah 1 , setelah mengambil langkah I , walker menemukan dirinya pada jarak I + 1 dari gawang setelah mengubah arah. Karena saya <L , kita memiliki I + 1 ≤ L , sehingga langkah I + 1 berikutnya akan membawanya ke tujuan.
Ini memberikan total I + I + 1 = 2I + 1 langkah yang diambil. Menambahkan satu untuk sel awal, kami mendapatkan total 2I + 1 + 1 = 2 (I + 1) sel yang dikunjungi dalam kasus ini.
Bagaimana itu bekerja
sumber
Matlab (skor = 230, n = inf)
infjika Anda ingin tetap tak terbatas).h=1000000000000000000000000000000000000000000000000000;w(h,h+1)untuk memastikan.Algoritme mengikuti pendekatan matematika yang akan saya jelaskan nanti, dan itu mengkonfirmasi daftar yang direferensikan Martin, berdasarkan pada program ini:
Karena algoritma memverifikasi 2048 testcases pertama, saya akan secara membabi buta menganggapnya untuk kasus uji apa pun, jadi algoritme saya berfungsi mengenai beberapa properti yang saya temukan dalam proses ini tanpa kesulitan menggeser dan memindahkan pointer:
1 - jika dua kali jumlah 1 dalam terjemahan biner tidak melebihi panjang sequnce
Lsehingga hasilnya adalahL+12- jika panjang urutannya genap dan kondisi sebelumnya tidak diatur sehingga outputnya sama
L+13 - jika tidak, output adalah dua kali
L/2indeks ke-1.sumber
a=dec2bin(input(''));c=find(a=='1');g=nnz(a)+1;if nnz(c)<g/2|mod(g,2);g,else,2*c(g/2),end, yang hanya memberikan elemen tunggal dari urutan tersebut.Python,
122119113110108107103 byteMengambil input sebagai daftar digit biner. Fungsi pembantu untuk menguji:
Kredit ke Lynn untuk menghemat 7 byte.
sumber
p-d-1in[-2,w]menghemat satu byte.d*=2*(1!=d-p>~w)-1menyimpan empat lagi! ° v °Python 2, 99 byte
Port python jawaban brilian Agawa001.
Versi yang dapat dibaca:
sumber
MATL,
31, 25 byteIni hanya versi MATL dari algoritma Agawa001, kecuali ia mengambil input integer N dan mengembalikan istilah N-th dalam urutan. Itu sulit mengikuti semua elemen di tumpukan! Saya harus menggunakan clipboard untuk menghindari gila. Anda dapat mencobanya secara online!
Dapat dibuat menjadi loop mencetak istilah N pertama dengan menambahkan
:"@sebelum kode, dan]Dsesudahnya.Terima kasih kepada Luis Mendo karena telah menghemat 6 byte penuh!
sumber
Julia 0.4, 4̷4̷ 42 byte
Fungsi ini menerima integer tunggal dalam bentuk daftar digit binernya sebagai input.
Algoritma ini setara dengan yang dari jawaban @ Agawa001 dan jawaban Jelly saya .
Cobalah online!
Bagaimana itu bekerja
find(x)mengembalikan indeks berbasis 1 dari semua elemen x yang tidak nol . Kami berupaya mengakses array yang dihasilkan pada indeks k / 2 dan, jika berhasil, menimpa k dengan indeks yang dipilih dua kali.Ini akan gagal jika dan hanya jika salah satu dari yang berikut ini benar:
k / 2 adalah float non-integral, jadi dan InexactError dinaikkan.
Array indeks memiliki kurang dari k / 2 elemen, sehingga BoundsError dinaikkan.
Dalam kedua kasus, menimpa k akan gagal, sehingga nilai aslinya akan dikembalikan.
sumber
JavaScript (ES6), 65 byte
Menerima string biner. Menggunakan cek bouncing dari berbagai jawaban lainnya.
sumber
Python 2, 74 byte
Fungsi ini menerima integer tunggal dalam bentuk daftar digit binernya sebagai input.
Algoritma ini setara dengan yang dari jawaban @ Agawa001 dan jawaban Jelly saya .
Uji di Ideone .
Bagaimana itu bekerja
nextmencoba menemukan bilangan bulat 2i pertama yangk==2*sum(x[:i])mengembalikan true. Karenax[:i]mengandung elemen i , ini memberikan indeks berbasis 1 dari (k / 2) ke- 1 .nextakan gagal jika k / 2 adalah non-integral atau jika x mengandung kurang dari k / 2 . Dalam hal ini, nilai default k dikembalikan.sumber
> <> , 63 byte
Dari saat saya melihat contoh pola dalam tantangan ini, saya tahu bahasa mana yang harus digunakan :)
Menggunakan N untuk mendapatkan istilah ke- N .
Input diasumsikan dalam biner di stack. Daripada memindahkan walker, solusi ini lebih banyak bergantung pada memindahkan plester di bawah walker.
Cobalah online!
sumber