tło

Większość ludzi tutaj powinna znać kilka podstawowych systemów liczb całkowitych: dziesiętny, binarny, szesnastkowy, ósemkowy. Na przykład w systemie szesnastkowym, liczba abc.de ₁₆ stanowiłoby

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

Można jednak również stosować zasady niecałkowite, takie jak liczby niewymierne. Gdy takie bazowa wykorzystuje złoty stosunek cp = (1 + √5) / 2 ≈ 1,618 ... . Są one zdefiniowane analogicznie do zasad całkowitych. Zatem liczba abc.de _φ (gdzie a to e są cyframi całkowitymi) reprezentuje

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

Zauważ, że w zasadzie każda z cyfr może być ujemna (chociaż nie jesteśmy do tego przyzwyczajeni) - będziemy reprezentować cyfrę ujemną z wiodącym ~. Na potrzeby tego pytania ograniczamy się do cyfr od ~9do 9, dzięki czemu możemy jednoznacznie zapisać liczbę jako jeden ciąg znaków (z tyldami pomiędzy nimi). Więc

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

byłoby napisane jako ~290.~43. Nazywamy taki numer numerem fikcyjnym .

Liczbę finarną można zawsze przedstawić w postaci standardowej , co oznacza, że ​​w reprezentacji są używane tylko cyfry 1i 0, bez 11nigdzie, oraz z opcjonalnym znakiem minus wskazującym, że cała liczba jest ujemna. (Co ciekawe, każda liczba całkowita ma unikatową skończoną reprezentację w standardowej formie).

Reprezentacje, które nie są w formie standardowej, zawsze można przekształcić w formę standardową, korzystając z następujących obserwacji:

1. 011 _φ = 100 _φ (ponieważ φ ² = φ + 1)
2. 0200 _φ = 1001 _φ (ponieważ φ ² + 1 / φ = 2φ)
3. 0 ~ 10 _φ = ~ 101 _φ (ponieważ φ - 1 / φ = 1)

Dodatkowo:

4. Jeżeli najbardziej znacząca cyfra ~1(z reszta numeru będąc formą standard), liczba jest ujemna, a my możemy przekształcić go w formie standardowej poprzez zamianę wszystkich 1i ~1, poprzedzenie znakiem minus, i stosując powyższe trzy zasady ponownie, dopóki nie uzyskaj standardowy formularz.

Oto przykład takiej normalizacji (używam dodatkowych spacji dla cyfr dodatnich, aby utrzymać wyrównanie pozycji każdej cyfry): 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)

Wydajność .-0.0101φ

Do dalszego czytania Wikipedia ma bardzo pouczający artykuł na ten temat.

Wyzwanie

Stąd, lub w inny sposób, napisz program lub funkcję, która, biorąc pod uwagę ciąg reprezentujący liczbę finarną (jak opisano powyżej), wyświetla swoją standardową postać, bez zer wiodących ani końcowych. Dane wejściowe niekoniecznie zawierają punkt fikcyjny, ale zawsze będą zawierały cyfrę po lewej stronie (więc nie .123). Wyjście musi zawsze zawierać punkt fiński i co najmniej jedną cyfrę po jego lewej stronie.

Możesz pobrać dane wejściowe za pomocą argumentu STDIN, ARGV lub funkcji i albo zwrócić wynik, albo wydrukować go do STDOUT.

Możesz użyć innego algorytmu niż powyższa procedura, o ile jest on zasadniczo poprawny i dokładny dla dowolnych (prawidłowych) danych wejściowych - to znaczy, jedynymi ograniczeniami, które mogą potencjalnie złamać twoją implementację, powinny być ograniczenia techniczne, takie jak rozmiar wbudowanego typy danych lub dostępna pamięć RAM. Na przykład, ocena danych wejściowych jako liczby zmiennoprzecinkowej, a następnie łapczywe wybieranie cyfr jest niedozwolona, ​​ponieważ można znaleźć dane wejściowe, dla których niedokładności zmiennoprzecinkowe doprowadziłyby do niepoprawnych wyników.

To jest kod golfowy, wygrywa najkrótsza odpowiedź (w bajtach).

Przypadki testowe

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

JavaScript (ES6) - 446 418 422 420 bajtów

Zminimalizowane:

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,'')}

Rozszerzony:

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, '' );
}

Kod tworzy funkcję, Fktóra wykonuje określoną konwersję.

To trudny problem dla golfa. Liczne przypadki brzegowe pełzają, co uniemożliwia uproszczenie kodu. W szczególności radzenie sobie z negatywami jest uciążliwe zarówno pod względem analizy, jak i logicznego postępowania.

Powinienem zauważyć, że kod obsługuje tylko „rozsądny zakres” danych wejściowych. Aby rozszerzyć domenę funkcji bez ograniczeń, zmożna zwiększyć liczbę zer , a stałą ograniczającą while( c++ < 99 )pętlę można zwiększyć. Obecnie obsługiwany zakres jest już nadmierny dla dostarczonych przypadków testowych.

Przykładowe dane wyjściowe

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

To -0.nie jest ładne, ale odpowiedź jest nadal poprawna. W razie potrzeby mogę to naprawić.

Haskell, 336 bajtów

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

Jest to chciwy algorytm, ale z dokładną reprezentacją [a,b]liczb a + bφ ( a , b ∈ ℤ), aby uniknąć błędów zmiennoprzecinkowych. g[a,b]sprawdza, czy a + bφ <0. Przykład użycia:

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