Membakukan Nomor Phinary

32

Latar Belakang

Kebanyakan orang di sini harus terbiasa dengan beberapa sistem basis integer: desimal, biner, heksadesimal, oktal. Misalnya dalam sistem heksadesimal, angka abc.de 16 akan mewakili

a*16^2 + b*16^1 + c*16^0 + d*16^-1 + e*16^-2

Namun, kita juga dapat menggunakan basis non-integer, seperti bilangan irasional. Setelah dasar seperti menggunakan rasio emas φ = (1 + √5) / 2 ≈ 1,618 ... . Ini didefinisikan secara analog ke basis integer. Jadi angka abc.de φ (di mana a ke e adalah angka integer) akan mewakili

a*φ^2 + b*φ^1 + c*φ^0 + d*φ^-1 + e*φ^-2

Perhatikan bahwa pada prinsipnya salah satu digit bisa negatif (meskipun kami tidak terbiasa dengan itu) - kami akan mewakili digit negatif dengan yang terdepan ~. Untuk tujuan pertanyaan ini kita membatasi diri untuk angka dari ~9ke 9, jadi kami jelas bisa menulis nomor sebagai satu string (dengan tildes di antara). Begitu

-2*φ^2 + 9*φ^1 + 0*φ^0 + -4*φ^-1 + 3*φ^-2

akan ditulis sebagai ~290.~43. Kami menyebut nomor tersebut sebagai nomor telepon biasa .

Bilangan phinary selalu dapat direpresentasikan dalam bentuk standar , yang berarti bahwa representasi hanya menggunakan digit 1dan 0, tanpa mengandung di 11mana pun, dan dengan tanda minus opsional untuk menunjukkan bahwa seluruh bilangan tersebut negatif. (Menariknya, setiap bilangan bulat memiliki representasi terbatas yang unik dalam bentuk standar.)

Representasi yang tidak dalam bentuk standar selalu dapat dikonversi menjadi bentuk standar menggunakan pengamatan berikut:

  1. 011 φ = 100 φ (karena φ 2 = φ + 1)
  2. 0200 φ = 1001 φ (karena φ 2 + 1 / φ = 2φ)
  3. 0 ~ 10 φ = ~ 101 φ (karena φ - 1 / φ = 1)

Tambahan:

  1. Jika digit paling signifikan adalah ~1(dengan sisa angka menjadi bentuk standar), angka tersebut negatif, dan kita dapat mengubahnya menjadi bentuk standar dengan menukar semua 1dan ~1, menambahkan tanda minus, dan menerapkan tiga aturan di atas lagi sampai kita dapatkan formulir standar.

Berikut ini adalah contoh normalisasi (Saya menggunakan ruang tambahan untuk digit positif, untuk menjaga agar setiap posisi digit selaras): 1~3.2~1φ

      1~3. 2~1φ         Rule:
=     0~2. 3~1φ         (3)
=    ~1~1. 4~1φ         (3)
=  ~1 0 0. 4~1φ         (3)
=  ~1 0 0. 3 0 1φ       (3)
=  ~1 0 1. 1 0 2φ       (2)
=  ~1 1 0. 0 0 2φ       (1)
=  ~1 1 0. 0 1 0 0 1φ   (2)
= - 1~1 0. 0~1 0 0~1φ   (4)
= - 0 0 1. 0~1 0 0~1φ   (3)
= - 0 0 1.~1 0 1 0~1φ   (3)
= - 0 0 0. 0 1 1 0~1φ   (3)
= - 0 0 0. 0 1 1~1 0 1φ (3)
= - 0 0 0. 0 1 0 0 1 1φ (3)
= - 0 0 0. 0 1 0 1 0 0φ (1)

Menghasilkan .-0.0101φ

Untuk bacaan lebih lanjut, Wikipedia memiliki artikel yang sangat informatif tentang topik ini.

Tantangan

Oleh karena itu, atau sebaliknya, tulis sebuah program atau fungsi yang, diberi string yang mewakili angka finary (seperti yang dijelaskan di atas), menampilkan bentuk standarnya, tanpa memimpin atau membuntuti nol. Input tidak harus mengandung titik faring, tetapi akan selalu berisi digit di sebelah kiri (jadi tidak .123). Outputnya harus selalu menyertakan titik phinary dan setidaknya satu digit di sebelah kiri itu.

Anda dapat mengambil input melalui STDIN, ARGV atau argumen fungsi dan mengembalikan hasilnya atau mencetaknya ke STDOUT.

Anda dapat menggunakan algoritme yang berbeda dari prosedur di atas asalkan pada prinsipnya benar dan tepat untuk input yang sewenang-wenang - yaitu, satu-satunya batasan yang berpotensi memecah implementasi Anda haruslah batasan teknis seperti ukuran bawaan tipe data atau RAM yang tersedia. Misalnya, mengevaluasi input sebagai angka titik-mengambang dan kemudian memilih angka dengan rakus tidak diperbolehkan, karena orang dapat menemukan input yang ketidakakuratan titik-mengambang akan mengarah pada hasil yang salah.

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

Uji Kasus

Input       Output

1           1.
9           10010.0101
1.618       10000.0000101
1~3.2~1     -0.0101
0.~1021     0. (or -0.)
105.~2      1010.0101
~31~5.~1    -100000.1001
Martin Ender
sumber
Sekarang saya ingin menggunakan angka negatif di nomor saya! 1 ~ 3 * 6 == 5 ~ 8
Aaron

Jawaban:

6

Javascript (ES6) - 446 418 422 420 byte

Diperkecil:

F=s=>{D=[];z='000000000';N=t=n=i=e=0;s=(z+s.replace(/^([^.]*)$/,'$1.')+z).replace(/~/g,'-').replace(/-?\d/g,s=>((D[n++]=s/1),0));for(;i<n-3;i=j){if(p=D[j=i+1]){if(!e&&p<0){D=D.map(k=>-k);N=~N;p=-p}e=1}d=D[i];x=D[i+2];m=D[i+3];if(p<0){d--;p++;x++;e=j=0}if(p>1){d++;m++;p-=2;e=j=0}if(!d&&p*x==1){d=p;e=j=p=x=0}D[i]=d;D[i+1]=p;D[i+2]=x;D[i+3]=m}return(N?'-':'')+s.replace(/0/g,()=>D[t++]).replace(/^(0(?!\.))+|0+$/g,'')}

Diperluas:

F = s => {
    D = [];
    z = '000000000';
    N = t = n = i = e = 0;
    s = (z + s.replace( /^([^.]*)$/, '$1.' ) + z).replace( /~/g, '-' ).
        replace( /-?\d/g, s => ((D[n++]=s/1),0) );

    for( ; i < n-3; i = j ) {
        if( p = D[j = i+1] ) {
            if( !e && p < 0 ) {
                D = D.map( k=>-k );
                N = ~N;
                p = -p;
            }
            e = 1;
        }
        d = D[i];
        x = D[i+2];
        m = D[i+3];

        if( p < 0 ) {
            d--;
            p++;
            x++;
            e = j = 0;
        }
        if( p > 1 ) {
            d++;
            m++;
            p-=2;
            e = j = 0;
        }
        if( !d && p*x == 1 ) {
            d = p;
            e = j = p = x = 0;
        }

        D[i] = d;
        D[i+1] = p;
        D[i+2] = x;
        D[i+3] = m;
    }

    return (N ? '-' : '') + s.replace( /0/g, ()=>D[t++] ).replace( /^(0(?!\.))+|0+$/g, '' );
}

Kode menghasilkan fungsi Fyang melakukan konversi yang ditentukan.

Ini masalah sulit untuk golf. Banyak kasus tepi merayap yang mencegah penyederhanaan kode. Secara khusus, berurusan dengan negatif adalah rasa sakit, baik dalam hal parsing dan dalam hal penanganan logis.

Saya harus mencatat bahwa kode hanya menangani "kisaran wajar" input. Untuk memperluas domain fungsi tanpa terikat, jumlah nol diz dapat ditingkatkan, dan konstanta yang membatasi while( c++ < 99 )loop dapat ditingkatkan. Rentang yang saat ini didukung sudah berlebihan untuk kasus uji yang disediakan.

Output Sampel

F('1')          1.
F('9')          10010.0101
F('1~3.2~1')    -0.0101
F('0.~1021')    -0.
F('105.~2')     1010.0101
F('~31~5.~1')   -100000.1001

Tidak -0.cantik, tapi jawabannya masih benar. Saya bisa memperbaikinya jika perlu.

COTO
sumber
@ MartinBüttner: Anda bisa, tetapi itu akan sulit. Ia membatasi jumlah "lintasan" pada input penuh, dan setiap lintasan terdiri dari beberapa operasi. Perasaan saya adalah bahwa jumlah lintasan yang diperlukan untuk menormalkan ninput -digit akan berada di antara ndan n log(n). Bagaimanapun, jumlah lintasan dapat dinaikkan dengan faktor 10 untuk setiap karakter yang ditambahkan. Jumlah nol dalam zkonstanta juga merupakan masalah yang menarik. Saya menduga bahwa angka 9 adalah berlebihan untuk setiap input yang mungkin.
COTO
@ MartinBüttner: Terima kasih. Saya menghapus pelarian di kelas karakter. Adapun $0, Javascript tidak mendukungnya. Atau setidaknya Firefox tidak. : P
COTO
Oke, saya pikir Anda tidak perlu lebih dari 7 angka nol sebagai penyangga, tapi saya pikir angka nol akan sedikit lebih sulit untuk diperkirakan. Adapun loop luar, saya tidak berpikir Anda bahkan membutuhkan itu, jika Anda hanya membuat loop sementara (atau mengintegrasikannya ke dalam untuk loop) dan hanya keluar ketika tidak ada lagi perubahan yang ditemukan. Saya kira spec saya bisa menjadi sedikit lebih jelas dalam hal itu tetapi dengan "pada prinsipnya benar dan tepat untuk input (valid) sewenang-wenang" Maksud saya satu-satunya batasan teoretis adalah ukuran dari tipe data bawaan / RAM Anda.
Martin Ender
1
@COTO Untuk menghemat 1 byte, Anda dapat mencoba memindahkan bagian pertama dari for( i = e = 0; i < n-3; i = j )by for(; i < n-3; i = j )dan memindahkan deklarasi ke atas, N = t = n = 0;digantikan denganN = t = n = i = e = 0;
Ismael Miguel
1
@IsmaelMiguel: jtidak dipegang konstan pada nilai i+1. Perhatikan di tiga ifblok, jdiatur ulang ke 0. Karenanya pada titik mana pun setelah ifblok pertama itu tidak dapat digunakan sebagai proxy untuk i+1. Variabel iitu sendiri tidak dapat diperbarui sampai akhir loop (menggunakan pernyataan ketiga dalam for) karena nilainya digunakan sampai akhir loop. Tapi setelah mengatakan itu, mungkin aku kehilangan sesuatu. Jika Anda dapat mempersingkat kodenya, mengujinya, dan memverifikasi kodenya masih berfungsi, silakan kirim salinannya ke pastebin.com dan tautan di sini. Saya akan memberikan kredit kepada Anda dalam jawabannya. :)
COTO
2

Haskell, 336 byte

z=[0,0]
g[a,b]|a*b<0=g[b,a+b]
g x=x<z
k![a,b,c,d]=[b,a+b,d-c+read k,c]
p('.':s)=1:0:2`drop`p s
p('~':k:s)=['-',k]!p s
p(k:s)=[k]!p s
p[]=1:0:z
[1,0]&y='.':z?y
[a,b]&y=[b,a+b]?y
x@[a,b]?y@[c,d]|x==z,y==z=""|g y='-':x?[-c,-d]|g[c-1,d]='0':x&[d,c+d]|g[c,d-1]='1':x&[d,c+d-1]|0<1=[b-a,a]?[d-c,c]
m[a,b,c,d]=[1,0]?[a*d+b*c-a*c,a*c+b*d]
f=m.p

Ini adalah algoritma serakah, tetapi dengan representasi [a,b]angka yang tepat a + ( a , b ∈ ℤ) untuk menghindari kesalahan floating-point. g[a,b]menguji apakah a + <0. Contoh penggunaan:

*Main> f "9"
"10010.0101"
*Main> f "1~3.2~1"
"-0.0101"
*Main> f "0.~1021"
"0."
Anders Kaseorg
sumber