Penomoran Halaman Gaya xkcd

65

Buku Randall Munroe "xkcd, volume 0" menggunakan sistem angka yang agak aneh untuk nomor halaman. Beberapa nomor halaman pertama adalah

1, 2, 10, 11, 12, 20, 100, 101, 102, 110, 111, 112, 120, 200, 1000, 1001, ...

Ini agak mirip ternary, tetapi perhatikan bahwa ia melompat dari 20lurus ke 100, dari 120ke 200dan dari 200ke 1000. Salah satu cara untuk mendefinisikan urutan ini adalah dengan mengatakan bahwa ia menyebutkan semua nomor terner yang berisi paling banyak satu 2dan tidak ada 1setelah itu 2. Anda dapat menemukan ini di OEIS di entri A169683 . Sistem angka ini dikenal sebagai biner miring .

Tugas Anda adalah menemukan representasi bilangan bulat positif yang diberikan Ndalam sistem angka ini.

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

Output dapat berupa string, angka dengan representasi desimal sama dengan representasi biner miring, atau daftar digit (sebagai bilangan bulat atau karakter / string). Anda tidak boleh mengembalikan angka nol di depan.

Ini adalah kode golf, jadi jawaban tersingkat (dalam byte) menang.

Fakta menyenangkan: Sebenarnya ada beberapa manfaat untuk sistem angka ini. Saat menambah angka, Anda akan selalu mengubah paling banyak dua digit yang berdekatan - Anda tidak akan perlu membawa perubahan melalui seluruh angka. Dengan representasi yang tepat yang memungkinkan penambahan di O (1).

Uji Kasus

1 => 1
2 => 2
3 => 10
6 => 20
7 => 100
50 => 11011
100 => 110020
200 => 1100110
1000 => 111110120
10000 => 1001110001012
100000 => 1100001101010020
1000000 => 1111010000100100100
1048576 => 10000000000000000001

1000000000000000000 => 11011110000010110110101100111010011101100100000000000001102

Saya akan memberikan hadiah kepada jawaban terpendek yang dapat memecahkan kasus uji terakhir (dan input lain yang sama besarnya, jadi jangan berpikir tentang hardcoding) dalam waktu kurang dari satu detik.

Papan peringkat

Berikut ini adalah Stack Snippet untuk menghasilkan leaderboard biasa dan gambaran umum pemenang berdasarkan bahasa.

Untuk memastikan bahwa jawaban Anda muncul, silakan mulai jawaban Anda dengan tajuk utama, menggunakan templat Penurunan harga berikut:

# Language Name, N bytes

di mana Nukuran kiriman Anda. Jika Anda meningkatkan skor Anda, Anda dapat menyimpan skor lama di headline, dengan mencoretnya. Misalnya:

# Ruby, <s>104</s> <s>101</s> 96 bytes

<script>site = 'meta.codegolf'; postID = 5314; isAnswer = true; QUESTION_ID = 51517</script><script src='https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js'></script><script>jQuery(function(){var u='https://api.stackexchange.com/2.2/';if(isAnswer)u+='answers/'+postID+'?order=asc&sort=creation&site='+site+'&filter=!GeEyUcJFJeRCD';else u+='questions/'+postID+'?order=asc&sort=creation&site='+site+'&filter=!GeEyUcJFJO6t)';jQuery.get(u,function(b){function d(s){return jQuery('<textarea>').html(s).text()};function r(l){return new RegExp('<pre class="snippet-code-'+l+'\\b[^>]*><code>([\\s\\S]*?)</code></pre>')};b=b.items[0].body;var j=r('js').exec(b),c=r('css').exec(b),h=r('html').exec(b);if(c!==null)jQuery('head').append(jQuery('<style>').text(d(c[1])));if (h!==null)jQuery('body').append(d(h[1]));if(j!==null)jQuery('body').append(jQuery('<script>').text(d(j[1])))})})</script>

Martin Ender
sumber
32
Saya sudah memiliki buku itu sejak pertama kali keluar dan tidak pernah memperhatikan penomoran halaman.
Alex A.
2
@AlexA. Saya memilikinya di Kindle saya di mana Anda tidak dapat melakukan penomoran halaman yang menarik.
LegionMammal978
21
@ LegionMammal978: Tragis.
Alex A.
1
@ SuperJedi224 Konsensus tampaknya tidak , jadi maaf (saya akan membuat pengecualian dari konsensus jika itu adalah satu-satunya jenis input yang dapat ditangani bahasa Anda, tetapi sepertinya tidak demikian).
Martin Ender
4
Ini mengingatkan saya pada bagaimana saya biasanya menghitung ketika saya berusia 3. Saya beralasan: "tidak ada lima puluh sepuluh, jadi setelah seratus sembilan pasti dua ratus." Saya baru menyadari kesalahan saya setelah melihat perbedaan antara 59->60dan 109->110, dengan tambahan 0.
Cyoce

Jawaban:

12

Pyth, 17 byte

Ljb3ye.f!-P-yZ01Q

Ini agak lambat - O(output^log_2(3)). Itu eksponensial dalam panjang input, tetapi tidak eksponensial ganda, seperti beberapa jawaban di halaman. Beberapa ide diambil dari jawaban @ Dennis, di sini .

Demonstrasi.

Itu memanfaatkan .ffungsi "loop sampai n kecocokan telah ditemukan" Pyth.

isaacg
sumber
32

CJam, 24 23 22 21 19 byte

ri_)2b,,W%{2\#(md}/

Ini adalah pendekatan O (log n) , di mana n adalah input, yang menyelesaikan kasus uji terakhir secara instan. Ini mengkonversi n langsung ke miring biner, menggunakan pembagian modular dengan nilai-nilai digit 1 .

Kode ini selesai dengan kesalahan yang masuk ke STDERR dengan Java interpreter, yang diizinkan sesuai dengan konsensus tentang Meta .

Jika Anda mencoba kode ini dalam juru bahasa CJam , abaikan saja semuanya kecuali baris keluaran terakhir.

Kesalahan dapat dihilangkan, dengan biaya 2 byte, dengan menambahkan 2>ke W%.

Terima kasih kepada @ MartinBüttner untuk bermain golf satu byte.

Latar Belakang

Representasi kemiringan miring a k ... a 0 sesuai dengan bilangan bulat n = (2 k + 1 -1) a k + ... + (2 1 -1) a 0 .

Karena keduanya (2 k -1) + ... + (2 1 -1) = 2 k + 1 - (k + 2) dan (2 k -1) + ... + 2 (2 j -1) = 2 k + 1 - (2 j + 1 - 2 j + k + 1) kurang dari 2 k + 1 -1 , nilai-nilai suatu k untuk sebuah 0 dapat dipulihkan dengan pembagian modular berturut-turut oleh 2 k + 1 -1 , 2 k -1 , dll.

Untuk memulai, kita harus menemukan nilai 2 k + 1 -1 terlebih dahulu. Karena n paling banyak 2 (2 k + 1 -1) , integer n + 1 harus lebih kecil dari 2 k + 2 .

Dengan demikian, mengambil bagian integer dari logaritma biner dari n + 1 menghasilkan k + 1 .

Akhirnya, kami mengamati bahwa integer n + 1 memiliki ⌊log 2 (n + 1) ⌋ digit di basis 2.

Bagaimana itu bekerja

ri    e# Read an integer N from STDIN.
2b,   e# Push the number of binary digits of N + 1, i.e, K + 2 = log(N + 1) + 1.
,W%   e# Push the range [K+1 ... 0].
{     e# For each J in the range:
  2\# e#   J -> 2**J
  (   e#     -> 2**J - 1
  md  e#   Perform modular division of the integer on the stack (initially N)
      e#   by 2**J - 1: N, 2**J - 1 -> N/(2**J - 1), N%(2**J - 1)
}/    e#

Dalam dua iterasi terakhir, kami melakukan pembagian modular dengan 1 dan 0 . Yang pertama mendorong 0 yang tidak diinginkan pada stack. Upaya terakhir untuk mengeksekusi 0 0 md, yang mengeluarkan 0 s yang tidak diinginkan dari stack, keluar dengan segera alih-alih mendorong apa pun dan membuang stack ke STDOUT.

Dennis
sumber
28

Python 2, 67 byte

def f(n):x=len(bin(n+1))-3;y=2**x-1;return n and n/y*10**~-x+f(n%y)

Tampaknya bekerja untuk test case yang diberikan. Jika saya sudah benar, ini seharusnya tentang O(place values set in output), jadi itu kasus terakhir dengan mudah.

Sebut seperti f(100). Mengembalikan representasi desimal sama dengan biner miring.

Python 3, 65 byte

def g(n,x=1):*a,b=n>x*2and g(n,x-~x)or[n];return a+[b//x,b%x][:x]

Agak kurang efisien tetapi masih logaritmik, jadi kasing terakhir hampir instan.

Sebut seperti g(100). Mengembalikan daftar digit.

Sp3000
sumber
apakah 2andkompilasi dalam 3? Saya berada di 2 dan 2and2melempar kesalahan sintaks
TankorSmash
3
@TankorSmash 2and2tidak akan berfungsi karena akan diuraikan sebagai 2 and2- coba 2and 2, yang akan berfungsi jika versi Python Anda cukup baru (diuji dengan Python 2.7.10)
Sp3000
Oh bagus, kamu benar. Bahkan pada 2.7.3 berfungsi.
TankorSmash
12

CJam, 22 21 20 byte

ri_me,3fb{0-W<1-!},=

Ini adalah pendekatan O (e n n) , di mana n adalah input. Ini daftar pertama ⌊e n bilangan bulat non-negatif dalam basis 3, menghilangkan orang-orang yang memiliki 2 s atau 1 s setelah pertama 2 (jika ada) dan memilih n + 1 th .

Cobalah online di juru bahasa CJam .

Bagaimana itu bekerja

ri    e# Read an integer N from STDIN.
_me,  e# Push [0 ... floor(exp(N))-1].
3fb   e# Replace each integer in the range by the array of its digits in base 3.
{     e# Filter; for each array A:
  0-  e#   Remove all 0's.
  W<  e#   Remove the last element.
  1-  e#   Remove all 1's.
  !   e#   Logical NOT. Pushes 1 iff the array is empty.
},    e#   If ! pushed 1, keep the array.
=     e# Select the (N+1)th element of the filtered array.
Dennis
sumber
9

Pyth, 20 byte

Jt^2hslhQ#p/=%QJ=/J2

Berjalan di O (log (input ())), jauh di bawah satu detik untuk kasus uji akhir. Berbasis di sekitar run sampai loop kesalahan. Tidak ada baris baru.

Demonstrasi.

Penjelasan:

Jt^2hslhQ#p/=%QJ=/J2
                        Implicit: Q is the input.
      lhQ                          log(Q+1,2)
     slhQ                    floor(log(Q+1,2))
    hslhQ                    floor(log(Q+1,2))+1
  ^2hslhQ                 2^(floor(log(Q+1,2))+1)
 t^2hslhQ                 2^(floor(log(Q+1,2))+1)-1
Jt^2hslhQ               J=2^(floor(log(Q+1,2))+1)-1
         #              until an error is thrown:
            =%QJ        Q=Q%J
                =/J2    J=J/2
           /            The value Q/J, with the new values of Q and J.
          p             print that charcter, with no trailing newline.

J diinisialisasi dengan nilai posisi digit miring biner terkecil yang lebih besar dari input. Kemudian, setiap kali melalui loop, kami melakukan hal berikut:

  • Hapus setiap digit nilai Jdari Qdengan =%QJ. Misalnya, jika Q=10dan J=7, Qmenjadi 3, yang sesuai dengan biner miring yang berubah dari 110menjadi 10. Ini tidak berpengaruh pada iterasi pertama.
  • Ubah Jnilai biner miring kemiringan berikutnya dengan =/J2. Ini adalah pembagian lantai dengan 2, berubah J=7menjadi J=3, misalnya. Karena ini terjadi sebelum digit pertama adalah output, Jposisi satu digit lebih tinggi dari yang dibutuhkan.
  • Temukan nilai digit aktual dengan /QJ(efektif).
  • Cetak nilai itu dengan p, alih-alih pencetakan standar Pyth, untuk menghindari baris baru yang tertinggal.

Loop ini akan mengulang sampai Jmenjadi nol, di mana titik kesalahan dibagi dengan nol akan dilemparkan, dan loop akan berakhir.

isaacg
sumber
8

ES6, 105 byte

f=n=>{for(o=0;n--;c?o+=Math.pow(3,s.length-c):o++)s=t(o),c=s.search(2)+1;return t(o);},t=a=>a.toString(3)

Penggunaannya adalah: f(1048576)=> `" 10000000000000000001 "

Uji argumen terakhir atas risiko Anda sendiri. Saya menyerah setelah 5 detik.

Dan cukup cetak dengan komentar!

f=n=>{ //define function f with input of n (iteration)
    for(o=0; //define o (output value in decimal)
        n--; //decrement n (goes towards falsy 0) each loop until 0
        c?o+=Math.pow(3,s.length-c):o++) //if search finds a 2, increment output by 3^place (basically moves the 2 to the left and sets the place to 0), else ++
        s=t(o), //convert output to base 3      
        c=s.search(2)+1; //find the location of 2, +1, so a not-found becomes falsy 0.
    return t(o); //return the output in base 3
},

t=a=>a.toString(3);  //convert input a to base 3
Kompas
sumber
5
Btw, fungsi tanpa nama sangat bisa diterima, jadi Anda tidak perlu f=.
Martin Ender
2
-16 byte:f=n=>{for(o=0;~n--;o+=c?Math.pow(3,s.length+c):1)s=o.toString(3),c=~s.search(2);return s}
nderscore
@nderscore Cukup keren: D
Kompas
1
-7 byte jika Anda menggunakan ES7: ganti Math.pow(3,s.length+c)dengan 3**(s.length+c).
Gustavo Rodrigues
3
@GustavoRodrigues Saya bahkan belum selesai belajar ES6! @ _ @
Kompas
7

Retina, 55 byte

^
0a
(+`12(.*a)1
20$1
0?2(.*a)1
10$1
0a1
1a
)`1a1
2a
a
<empty line>

Mengambil input di unary.

Setiap baris harus menuju ke file sendiri tetapi Anda dapat menjalankan kode sebagai satu file dengan -sbendera. Misalnya:

> echo 11111|retina -s skew
12

Metode: Menjalankan penambahan pada jumlah input string kali mulai dari string 0.

Kami menggunakan aturan kenaikan berikut:

  • jika mengandung 2: ^2 -> ^12; 02 -> 12;12 -> 20
  • jika tidak mengandung 2: 0$ -> 1$;1$ -> 2$

(Paling banyak ada satu 2di string; ^dan $menandai awal dan akhir string dalam aturan.)

Informasi lebih lanjut tentang Retina.

randomra
sumber
7

Jawa, 154 148

n->{String s="0";for(;n-->0;)s=s.contains("2")?s.replaceAll("(^|0)2","10").replace("12","20"):s.replaceAll("1$","2").replaceAll("0$","1");return s;}

Jawaban ini mengambil bentuk fungsi anonim tunggal yang mengambil argumen integer dan mengembalikan jawaban sebagai String. Di bawah ini adalah kelas lengkap untuk menguji solusi ini.

import java.util.function.Function;
public class Skew {
    public static void main(String[] args){
        Function<Integer,String> skew = n->{String s="0";for(;n-->0;)s=s.contains("2")?s.replaceAll("(^|0)2","10").replace("12","20"):s.replaceAll("1$","2").replaceAll("0$","1");return s;};

        for(String s:args){
            System.out.println(skew.apply(Integer.parseInt(s)));
        }
    }
}
ankh-morpork
sumber
5

Bash + coreutils, 52

dc -e3o0[r1+prdx]dx|grep -v 2.\*[12]|sed -n $1{p\;q}

Ini kasar, jadi agak lambat untuk jumlah yang lebih besar.

Keluaran:

$ ./xkcdnum.sh 1000
111110120
$ 
Trauma Digital
sumber
5

Java, 337 335 253 246 244 byte

Metode yang mengambil dalam indeks sebagai longdan mengembalikan hasilnya sebagai string

Menggunakan a longuntuk indeks sehingga secara teoritis dapat menangani test case terakhir, tetapi saya benar - benar tidak akan menyarankannya.

String f(long i){List<Long>l=new ArrayList<>();l.add(0L);for(;i-->0;){int j=l.indexOf(2);if(j!=-1){l.set(j,0L);if(j==0){l.add(0,1L);}else{l.set(j-1,l.get(j-1)+1);}}else{j=l.size()-1;l.set(j,l.get(j)+1);}}String s="";for(long q:l)s+=q;return s;}
SuperJedi224
sumber
4
Anda dapat mempersingkat ini dengan membuatnya menjadi fungsi alih-alih program penuh (dan mengambil input sebagai argumen alih-alih dari Pemindai).
Geobits
2
Anda tidak perlu kawat gigi dalam if(j == 0) pernyataan (empat byte). Anda tidak perlu mendeklarasikan k; Anda bisa menggunakan jlagi (empat lagi). Anda dapat menggunakan inferensi tipe umum (di Jawa 7) dalam deklarasi Daftar Anda ( new ArrayList<>();) (4 lainnya)
durron597
4

Haskell, 73 72

Terima kasih kepada @nimi untuk 1 byte!

Solusi ini tidak akan memenangkan hadiah apa pun, tes pasangan terakhir membutuhkan banyak waktu untuk berlari, tapi, saya pikir saya telah bermain golf dengan cukup baik.

i(2:b)=1:0:b
i[b]=[b+1]
i(b:2:c)=b+1:0:c
i(b:c)=b:i c
s=(iterate i[0]!!)

Solusi ini adalah pendekatan yang agak naif yang menghitung angka biner miring ndengan menambah 0 nkali.

ankh-morpork
sumber
4

CJam, 24 byte

Q{0\+2a/())+a\+0a*}ri*si

Ini adalah pendekatan O (n log n) , di mana n adalah input. Ini dimulai dengan representasi biner miring 0 dan menambah bilangan bulat yang sesuai n kali.

Cobalah online di juru bahasa CJam .

Latar Belakang

Menambah angka dalam biner miring dapat dilakukan dengan mengikuti dua langkah mudah:

  1. Ganti akhirnya 2 dengan 0 .

  2. Jika 2 telah diganti, tambahkan digit ke kiri.

    Jika tidak, tambahkan digit terakhir.

Bagaimana itu bekerja

Q     e# Push an empty array.
{     e# Define an anonymous function:
  0\+ e#   Prepend a 0 to the array.
  2a/ e#   Split the array at 2's.
  (   e#   Shift out the first chunk of this array.
  )   e#   Pop the last digit.
  )+  e#   Increment it and append it to the array.
  a\+ e#   Prepend the chunk to the array of chunks.
  0a* e#   Join the chunks, using [0] as separator.
      e#   If there was a 2, it will get replaced with a 0. Otherewise, there's
      e#   only one chunk and joining the array dumps the chunk on the stack.
}     e#
ri*   e# Call the function int(input()) times.
si    e# Cast to string, then to integer. This eliminates leading 0's.
Dennis
sumber
4

VBA, 209 147 142 byte

Sub p(k)
For i=1To k
a=StrReverse(q)
If Left(Replace(a,"0",""),1)=2Then:q=q-2*10^(InStr(a,2)-1)+10^InStr(a,2):Else:q=q+1
Next
msgbox q
End Sub

Matematika saya tidak efisien dan golf saya bisa menggunakan pekerjaan. Tapi ini upaya pertama saya di PoG dan saya pikir saya akan mencoba yang ini. Tapi semacam cara Brute Force.

Itu hanya menghitung dengan 1 kecuali digit terakhir adalah 2 lalu mundur 2 dan melompat ke depan 10. Ditambah 0 yang tertinggal.

Ini berhenti bekerja di 65534 karena VBA bersikeras memberi hasil dalam notasi ilmiah, tetapi logika harus bekerja dengan baik untuk angka yang lebih tinggi

Menantikan saran golf, VBA tidak terlalu ramah golf tetapi tidak sering diwakili, dan saya pikir itu bisa mengalahkan Jawa lama.

Sunting1: Terima kasih Manu karena membantu mencukur 62 byte

Sunting2: Ditukar debug.printuntuk msgboxsebagai output. Disimpan 5 byte

JimmyJazzx
sumber
1
Anda dapat menghapus tanda kurung Debug.Print (q). Anda juga dapat menghapus sebagian besar spasi putih (editor akan mengembalikannya, tetapi itu tidak perlu). Anda tidak perlu mendeklarasikan k as Long, cukup tulis k. Ini akan menjadi variabel dari jenis Varian dan kode akan tetap berfungsi. Dengan tips ini Anda harus turun ke ~ 165 byte.
CommonGuy
Beberapa pemikiran lagi: Anda dapat mengabaikan argumen pertama dan terakhir dari InStr, mereka adalah opsional. Trim()tidak perlu, karena Anda tidak memiliki spasi putih. Diterapkan dengan benar, saya mendapatkan 147 byte .
CommonGuy
1
Terima kasih atas Help Manu, Satu pertanyaan singkat, Output harus menjadi Output Standar. Saya tidak yakin apa yang akan terjadi di VBA. debug.print qakan menjadi output Standar? msgbox qlebih pendek tapi Sekali lagi sepertinya itu tidak cukup keluaran standar. Sheet1.cells(1,1)sepertinya keluaran Khas tetapi mengasumsikan berjalan di excel. Saya hanya tidak begitu yakin tentang seberapa ketat kode-golf tentang hal-hal semacam ini.
JimmyJazzx
Selamat, Anda mengalahkan jawaban java;) Saya juga tidak tahu ... Gunakan saja MsgBox, jika seseorang mengeluh, Anda masih dapat mengubahnya kembali.
CommonGuy
4

Javascript ES6, 99 86 78 76 72 karakter

f=n=>{for(s="1";--n;s=s.replace(/.?2|.$/,m=>[1,2,10][+m]||20));return s}

// Old version, 76 chars:
f=n=>{for(s="1";--n;s=s.replace(/02|12|2|.$/,m=>[1,2,10][+m]||20));return s}

// Old version, 86 chars:
f=n=>{for(s="1";--n;s=s.replace(/(02|12|2|.$)/,m=>[1,2,10,,,,,,,,,,20][+m]));return s}

// Old version, 99 chars:
f=n=>{for(s="1";--n;s=s.replace(/(^2|02|12|20|.$)/,m=>({0:1,1:2,2:10,12:20,20:100}[+m])));return s}

Uji:

;[1,2,3,6,7,50,100,200,1000,10000,100000,1000000,1048576].map(f) == "1,2,10,20,100,11011,110020,1100110,111110120,1001110001012,1100001101010020,1111010000100100100,10000000000000000001"

Fakta menyenangkan: Sebenarnya ada beberapa manfaat untuk sistem angka ini. Saat menambah angka, Anda akan selalu mengubah paling banyak dua digit yang berdekatan - Anda tidak akan perlu membawa perubahan melalui seluruh angka. Dengan representasi yang tepat yang memungkinkan penambahan di O (1).

Terima kasih atas faktanya - ini adalah dasar dari solusi saya :)

Qwertiy
sumber
Bagaimana saya bisa meninggalkan kawat gigi yang tidak perlu di regex? o_O
Qwertiy
3

Oktaf, 107 , 101 byte

Seharusnya O (log n) jika saya memperkirakan ini benar ...

function r=s(n)r="";for(a=2.^(uint64(fix(log2(n+1))):-1:1)-1)x=idivide(n,a);r=[r x+48];n-=x*a;end;end

Cukup cetak:

function r=s(n)
  r="";
  for(a=2.^(uint64(fix(log2(n+1))):-1:1)-1)
    x=idivide(n,a);
    r=[r x+48];
    n-=x*a;
  end
end

Saya agak terhalang mengatasi tantangan terakhir, karena Oktaf secara default memperlakukan semuanya sebagai angka floating point dan saya tidak memiliki presisi yang diperlukan untuk menghitung yang terakhir. Saya menyiasatinya dengan menghabiskan byte berharga untuk memaksa semuanya menjadi bilangan bulat yang tidak ditandatangani. Hasil yang terakhir terlalu besar untuk diperlakukan sebagai angka, jadi hasilnya adalah string.

Keluaran (Saya termasuk 1e18 - 1untuk menunjukkan bahwa saya dapat melakukannya secara akurat, dan rangkaian keluaran terakhir menunjukkan berapa lama untuk menghitung nilai itu):

octave:83> s(uint64(1e18))
ans = 11011110000010110110101100111010011101100100000000000001102

octave:84> s(uint64(1e18)-1)
ans = 11011110000010110110101100111010011101100100000000000001101

octave:85> tic();s(uint64(1e18)-1);toc()
Elapsed time is 0.0270021 seconds.
dcsohl
sumber
3

T-SQL, 221 189 177 byte

EDIT: Versi asli dari kode ini akan menghasilkan output yang tidak benar untuk beberapa angka, ini telah diperbaiki.

Dengan setiap kueri di sini, tambahkan saja angka untuk menghitung sebelum koma pertama.

Semua orang tahu bahwa T-SQL adalah bahasa golf terbaik. Ini adalah versi yang akan menghitung bahkan test case terakhir. Pada mesin saya mengujinya, itu berjalan di bawah satu detik, saya akan tertarik untuk melihat cara kerjanya untuk orang lain.

DECLARE @ BIGINT=,@T VARCHAR(MAX)='';WITH M AS(SELECT CAST(2AS BIGINT)I UNION ALL SELECT I*2FROM M WHERE I<@)SELECT @T += STR(@/(I-1),1),@%=(I-1)FROM M ORDER BY I DESC SELECT @T

Dan ini dia lagi, tetapi bisa dibaca:

DECLARE 
    @ BIGINT=,
    @T VARCHAR(MAX)='';

WITH M AS
(
    SELECT
        CAST(2 AS BIGINT) I

    UNION ALL

    SELECT I * 2
    FROM M
    WHERE I < @
)

SELECT 
    @T+=STR(@/(I-1),1),
    @%=(I-1)
FROM M 
ORDER BY I DESC

SELECT @T

Jika saya hanya menggunakan int, ini bisa sedikit lebih pendek, keluar pada 157 byte:

DECLARE @ INT=,@T VARCHAR(MAX)='';WITH M AS(SELECT 2I UNION ALL SELECT I*2FROM M WHERE I<@)SELECT @T+=STR(@/(I-1),1),@%=(I-1)FROM M ORDER BY I DESC SELECT @T

Dan sekali lagi, lebih mudah dibaca:

DECLARE 
    @ INT=,
    @T VARCHAR(MAX)='';

WITH M AS
(
    SELECT
        2I

    UNION ALL

    SELECT 
        I * 2
    FROM M
    WHERE I < @
)

SELECT 
    @T+=STR(@/(I-1),1),
    @%=(I-1)
FROM M 
ORDER BY I DESC

SELECT @T
PenutReaper
sumber
Ingat @adalah pengidentifikasi yang valid dalam sql dan Anda kemungkinan besar bisa lolos dengan Char(8000) yang masih lebih murah daripada nvarchar (maks). Anda juga dapat mengonversi ke charalih-alih varchar, atau menggunakan strfungsi.
Michael B
@MichaelB Oh, saya pikir saya telah menggunakan @, konyol saya. The CHAR(8000)saran cukup bagus, saya akan mencoba itu. Saya sepertinya selalu lupa tentang keberadaan STR()terima kasih untuk kepala.
PenutReaper
sebenarnya tidak membantu. Namun, Anda dapat menulis ulang bagian setelah CTE menjadi :: select @t=concat(@t,@/i)yang seharusnya lebih kecil. Membutuhkan sql2012.
Michael B
@MichaelB ah. CONCAT, Saya pada 2008. Jadi saya tidak bisa mengujinya tanpa menggunakan biola SQL sekarang. Panggilan yang bagus.
PenutReaper
3

Kode Mesin Turing, 333 293 byte

Saya menggunakan penyandian seperti yang digunakan di sini .

Mesin ini menggunakan 9 status dan 11 warna.

Jika input biner diizinkan, ini dapat dikurangi menjadi hanya 4 warna, menghemat beberapa puluh byte dalam proses.

0 _ _ l 1
0 * * r 0
1 9 8 l 2 
1 8 7 l 2
1 7 6 l 2
1 6 5 l 2
1 5 4 l 2
1 4 3 l 2
1 3 2 l 2
1 2 1 l 2
1 1 0 l 2
1 0 9 l 1
1 _ _ r 8
2 _ _ l 3
2 * * l 2
3 _ 1 r 4
3 * * l 5
4 _ _ r 0
4 * * r 4
5 * * l 5
5 _ _ r 6
6 _ _ l 7
6 2 0 l 7
6 * * r 6
7 _ 1 r 4
7 0 1 r 4
7 1 2 r 4
8 _ _ * halt
8 * _ r 8

Jika tautan di atas tidak berfungsi (kadang-kadang itu berfungsi untuk saya, di lain waktu halaman tersebut menolak untuk memuat) Anda juga dapat menguji ini menggunakan implementasi java ini.

SuperJedi224
sumber
2

Perl, 66 byte

Nomor harus dimasukkan melalui STDIN.

$_=1;$c=<>;s/(.*)(.?)2(.*)/$1.$2+1 .$3.0/e||$_++while(--$c);print;
frederick
sumber
Bisakah Anda menjelaskan cara kerja solusi Anda? Saya tidak melihat bagaimana Anda harus (.?)di $2sejak (.*)di $1harus serakah dan mendapatkan karakter yang pertama. Tetapi jika itu dihapus kode tidak menghasilkan hasil yang benar lagi! Omong-omong, Anda tidak perlu final ;.
CJ Dennis
@ CJDennis Terima kasih untuk byte yang disimpan. Lagi pula, itu.? akan mendapatkan digit tepat sebelum keduanya kecuali jika tidak ada digit di sana (mis. 20). Dalam kasus seperti 120 atau 10020, kelompok regex menyukai ini: () (1) 2 (0) dan (10) (0) 2 (0). Kemudian grup pertama diabaikan, grup kedua (yang selalu satu digit jika mungkin atau kosong) bertambah, dan grup ketiga (selalu terdiri dari nol) diabaikan dan nol ditambahkan. Saya hanya menggunakan entri OEIS sebagai panduan saya untuk regex ini.
frederick
Aku punya kode Anda ke 53 bytes: $c=<>;s/(.*)2(.*)/$1+1 .$2.0/e||$_++while($c--);print. Aku benar, (.?)tidak pernah menangkap apa pun.
CJ Dennis
Dapat dioptimalkan hingga $_=1;$c=<>;s/(.?)2/1+$1.0/e||$_++while(--$c);print, yaitu 50 byte. .*di awal atau akhir dapat dioptimalkan jauh, jika Anda hanya menggantinya dengan teks asli. Juga tidak ada alasan untuk menambahkan 0 di akhir, karena selalu ada nol saja di aslinya $3.
Thraidh
2

Pyth, 19 byte

m/=%Qtydtd^L2_SslhQ

Kompleksitas logaritmik. Mudah selesai dalam jumlah waktu yang diperlukan. Output dalam bentuk daftar digit.

Demonstrasi .

isaacg
sumber
2

Perl, 84 70 67 byte

$n=<>;$d*=2while($d++<$n);$_.=int($n/$d)while($n%=$d--,$d/=2);print

Tidak terlalu golf, Menjadi lebih baik tetapi bekerja dengan sangat cepat!

Saran Dennis membuatnya turun menjadi 51 (50 byte + -p switch)

$d*=2while$d++<$_;$\.=$_/$d|0while$_%=$d--,$d/=2}{

Itu harus disebut seperti di perl -p skew_binary.pl num_list.txtmana num_list.txtberisi satu baris dengan nomor untuk dikodekan di atasnya.

CJ Dennis
sumber
@ Patrick, kita berada di tepi kursi kita menunggu 2.
Robert Grant
@RobertGrant Dia mengomentari komentarnya dari dua hal menjadi satu hal!
CJ Dennis
Dua hal: 1. Alih-alih menggunakan $ ARGV [0], gunakan <> sebagai input. Ini akan mengambil input dari stdin kecuali ada file sebagai argumen. 2. Untuk skema penghitungan ganjil seperti ini, gunakan ekspresi reguler. Alih-alih melakukan operasi matematika aneh, Anda dapat mengganti angka dalam angka seolah-olah itu adalah string. Bagian terbaiknya adalah Anda bisa menggunakan operasi matematika (seperti increment) pada saat yang bersamaan, asalkan itu adalah string yang sepenuhnya terdiri dari digit. Periksa dokumentasi untuk operator ekspresi reguler, karena mereka bisa sangat berguna dalam banyak kesempatan.
frederick
Maaf, saya menekan enter dan itu disimpan sebelum saya menyelesaikan komentar.
frederick
@ Patrick tidak terlalu sederhana. Kami tahu apa yang terjadi!
Robert Grant
1

Mathematica, 65

Seharusnya cukup cepat, walaupun harus kuakui aku mengintip kiriman lain sebelum membuat ini.

f = (n = #;
     l = 0; 
     While[n > 0,
      m = Floor[Log2[1 + n]];
      l += 10^(m - 1);
      n -= 2^m - 1
     ]; l)&

Pemakaian:

f[1000000000000000000]

Keluaran:

11011110000010110110101100111010011101100100000000000001102

Mulai memberikan pesan kesalahan MaxExtraPrecision di suatu tempat di atas 10 ^ 228 (yang menghitung hasilnya dalam 0,03 detik pada mesin saya)

Setelah menghapus batas MaxExtraPrecision, itu akan menangani angka hingga sekitar 10 ^ 8000 dalam satu detik.

Memasukkan:

Timing[Block[{$MaxExtraPrecision = Infinity}, f[10^8000]];]

Keluaran:

{1.060807, Null}
Menghitung
sumber
1

C, 95 byte

void f(unsigned long i,int*b){for(unsigned long a=~0,m=0;a;a/=2,b+=!!m)m|=*b=i/a,i-=a**b;*b=3;}

Ini menerima integer dan buffer untuk mengembalikan digit. Hasilnya disimpan dalam b, diakhiri dengan nilai 3(yang tidak dapat terjadi dalam output). Kami tidak harus menangani input 0(seperti pertanyaan yang ditentukan hanya bilangan bulat positif), jadi tidak ada casing khusus untuk menghindari output kosong.

Kode diperluas

void f(unsigned long i,int*b)
{
    for (unsigned long a=~0, m=0;  a;  a/=2, b+=(m!=0)) {
        *b = i/a;               /* rounds down */
        i -= *b * a;
        m = m | *b;             /* m != 0 after leading zeros */
    }
    *b=3;                       /* add terminator */
}

Kami beroperasi dengan pengurangan berturut-turut, dimulai dengan digit paling signifikan. Satu-satunya komplikasi adalah kita menggunakan variabel muntuk menghindari pencetakan angka nol di depan. Perluasan alami untuk unsigned long longdibuat jika diinginkan, dengan biaya 10 byte.

Program uji

Lewati angka yang akan dikonversi sebagai argumen perintah. Itu mengkonversi intbuffer array ke string angka yang dapat dicetak. Runtime kurang dari satu milidetik untuk input 1000000000000000000.

#include <stdio.h>
#include <stdlib.h>
int main(int argc, char**argv)
{
    while (*++argv) {
        unsigned long i = strtoul(*argv, NULL, 10);
        int result[1024];
        f(i,result);

        /* convert to string */
        char s[1024];
        {char*d=s;int*p=result;while(*p!=3)*d++=*p+++'0';*d=0;}
        printf("%lu = %s\n", i, s);
    }

    return EXIT_SUCCESS;
}

Hasil tes

$ ./51517 $(seq 20)
1 = 1
2 = 2
3 = 10
4 = 11
5 = 12
6 = 20
7 = 100
8 = 101
9 = 102
10 = 110
11 = 111
12 = 112
13 = 120
14 = 200
15 = 1000
16 = 1001
17 = 1002
18 = 1010
19 = 1011
20 = 1012
Toby Speight
sumber
Saya kira versi C ++ mirip, tetapi dapat digunakan auto a=~0ulluntuk sedikit keuntungan ...
Toby Speight
0

CoffeeScript, 92 69 byte

Berdasarkan jawaban dan pembaruan Qwertiy :

f=(n)->s='1';(s=s.replace /(.?2|.$)/,(m)->[1,2,10][+m]||20)while--n;s

# older version, 92 bytes
f=(n)->s='1';(s=s.replace /(^2|02|12|20|.$)/,(m)->{0:1,1:2,2:10,12:20,20:100}[+m])while--n;s
rink.attendant.6
sumber
2
Mengubah ke bahasa lain bahkan tanpa optimasi sederhana dengan menghapus kawat gigi yang tidak perlu di regex sepertinya tidak keren untuk saya ...
Qwertiy
@Qwertiy Saya telah memberikan atribusi untuk jawaban Anda, dan dengan kedua jawaban itu saya tidak dapat menghasilkan hasil yang sama tanpa tanda kurung di regex
rink.attendant.6
Seluruh kejadian diganti. Mengapa Anda perlu berada di dalam grup? Versi JS berfungsi di Firefox tanpa tanda kurung.
Qwertiy
0

Japt , 31 byte

_r/?2|.$/g_÷C ç20 ª°Zs3}}gU['0]

Cobalah online!

Hampir mengarahkan port solusi JS ini . Tidak tahu apakah ada cara yang lebih baik.

Dibongkar & Cara kerjanya

X{Xr/?2|.$/gZ{Z÷C ç20 ||++Zs3}}gU['0]

X{     Declare a function...
Xr       Accept a string, replace the regex...
/?2|.$/g   /.?2|.$/   (g is needed to match *only once*, opposite of JS)
Z{       ...with the function... (matched string will be 0,1,2,02 or 12)
Z÷C        Implicitly cast the matched string into number, divide by 12
ç20        Repeat "20" that many times (discard fractions)
||         If the above results in "", use the next one instead
++Z        Increment the value
s3         Convert to base-3 string (so 0,1,2 becomes 1,2,10)
}}
gU['0] Repeatedly apply the function on "0", U (input) times
Bubbler
sumber
0

Stax , 16 byte

üxëàè£öΦGΩ│Je5█ò

Jalankan dan debug itu

Saya tidak yakin apa sebenarnya kelas kompleksitas formal, tetapi cukup cepat untuk melakukan semua kasus uji dalam sepersepuluh detik pada mesin ini.

Dibongkar, tidak diserang, dan dikomentari, sepertinya ini. Dalam program ini, register x awalnya berisi input.

z       push []
{       start block for while loop
 |X:2N  -log2(++x)
 {^}&   increment array at index (pad with 0s if necessary)
 xc:G-X unset high bit of x; write back to x register
w       while; loop until x is falsy (0)
$       convert to string

Jalankan yang ini

rekursif
sumber