Cytując to pytanie w SO (alert spoilera!):

To pytanie zostało zadane w wywiadzie dla Oracle.

Jak podzieliłbyś liczbę przez 3 bez użycia operatorów *, /, +, -,%?

Numer może być podpisany lub niepodpisany.

Zadanie można rozwiązać, ale sprawdź, czy możesz napisać najkrótszy kod.

Zasady:

• Wykonaj wymagany podział na liczby całkowite ( /3)
• Nie używać operatorów nietekstowa z siedzibą w *, /, +, -, lub %(lub ich odpowiedników, takich jak __div__lub add()). Dotyczy to również operatorów zwiększających i zmniejszających, takich jak i++lub i--. Używanie operatorów do łączenia i formatowania ciągów jest OK. Używanie tych znaków dla różnych operatorów, takich jak -operator jednoargumentowy dla liczb ujemnych lub *do reprezentowania wskaźnika w C, jest również OK.
• Wartość wejściowa może być dowolnie duża (cokolwiek twój system może obsłużyć), zarówno dodatnia, jak i ujemna
• Dane wejściowe mogą być na STDIN lub ARGV lub wprowadzone w inny sposób
• Utwórz najkrótszy kod, który możesz wykonać powyżej

J, 45 44 10 znaków

".,&'r3'":

Działa z negatywami:

".,&'r3'": 15
5
   ".,&'r3'": _9
_3
   ".,&'r3'": 3e99
1e99

": - sformatuj jako tekst

,&'r3'- dołącz r3do końca

". - wykonać ciąg, np 15r3

C, 167503724710

Oto moje rozwiązanie problemu. Przyznaję, że jest mało prawdopodobne, aby wygrać zawody w ścisłym kodzie golfowym, ale nie używa żadnych sztuczek, aby pośrednio wywoływać wbudowaną funkcję podziału, jest napisany w przenośnym C (jak zadawano oryginalne pytanie Stack Overflow), działa idealnie dla liczb ujemnych, a kod jest wyjątkowo jasny i wyraźny.

Mój program jest wynikiem działania następującego skryptu:

#!/usr/bin/env python3
import sys

# 71
sys.stdout.write('''#include <stdint.h>
#include <stdio.h>
int32_t div_by_3(int32_t input){''')

# 39 * 2**32
for i in range(-2**31, 2**31):
    # 18 + 11 + 10 = 39
    sys.stdout.write('if(input==%11d)return%10d;' % (i, i / 3))

# 95
sys.stdout.write(r'''return 7;}int main(int c,char**v){int32_t n=atoi(a[1]);printf("%d / 3 = %d\n",n, div_by_3(n));}''')

Liczba znaków: 71 + 39 * 2 ** 32 + 95 = 167503724710

Benchmarki

Zapytano, ile to zajmie i ile pamięci zajmie, więc oto kilka testów porównawczych:

• Czas wykonywania skryptu - Uruchamianie ./test.py | pv --buffer-size=1M --average-rate > /dev/nullprzez około 30 sekund daje szybkość około 14,8 MB / s. Można rozsądnie założyć, że szybkość produkcji jest w przybliżeniu stała, więc czas działania do ukończenia powinien wynosić około 167503724710 B / (14,8 * 1048576 B / s) ≈ 10794 s.
• Czas kompilacji - kompilator TCC twierdzi, że kompiluje kod C z prędkością 29,6 MB / s , co zapewnia czas kompilacji 167503724710 B / (29,6 * 1048576 B / s) ≈ 5397 s. (Oczywiście może to działać w potoku ze skryptem).
• Rozmiar skompilowanego kodu - próbowałem go oszacować za pomocą ./test.py | tcc -c - -o /dev/stdout | pv --buffer-size=1M --average-rate > /dev/null, ale wydaje się, że tccnic nie wyświetla, dopóki nie wczyta całego pliku źródłowego.
• Wykorzystanie pamięci do uruchomienia - Ponieważ algorytm jest liniowy (a tcc nie optymalizuje się między wierszami), narzut pamięci powinien wynosić zaledwie kilka kilobajtów (oczywiście poza samym kodem).

Rubin 28

b=->n{n.to_s(3).chop.to_i 3}

Aby podzielić przez 3, wystarczy usunąć końcowe zero w liczbie podstawowej 3: 120 -> 11110 -> 1111 -> 40

Działa z negatywami:

ice distantstar:~/virt/golf [349:1]% ruby ./div3.rb
666
222
ice distantstar:~/virt/golf [349]% ruby ./div3.rb
-15        
-5

Ruby, 60 45

Alternatywnie, bez użycia konwersji bazowej:

d = -> n {x = n.abs; r = (0..1,0 / 0). step (3) .take (x) .index x; n> 0? r: -r}

d=->n{(r=1.step(n.abs,3).to_a.size);n>0?r:-r}

Mathematica, 13 znaków

Mean@{#,0,0}&

JavaScript, 56

alert(Array(-~prompt()).join().replace(/,,,/g,1).length)

Sprawia ciąg długości npowtarzania ,S i zastępuje ,,,się 1. Następnie mierzy wynikową długość łańcucha. (Mam nadzieję, że jedność -jest dozwolona!)

Python, 41 38

print"-"[x:]+`len(xrange(2,abs(x),3))`

xrange wydaje się być w stanie obsłużyć duże liczby (myślę, że limit jest taki sam jak dla długiego w C) prawie natychmiast.

>>> x = -72
-24

>>> x = 9223372036854775806
3074457345618258602

Haskell, 90 106

d n=snd.head.dropWhile((/=n).fst)$zip([0..]>>=ν)([0..]>>=replicate 3>>=ν);ν q=[negate q,q]

Tworzy nieskończoną (leniwą) listę odnośników [(0,0),(0,0),(-1,0),(1,0),(-2,0),(2,0),(-3,-1),(3,1), ...], przycina wszystkie elementy, które nie pasują n( /=w Haskell jest nierówność) i zwraca pierwszą, która się zgadza .

To staje się znacznie prostsze, jeśli nie ma liczb ujemnych:

25 27

(([0..]>>=replicate 3)!!)

po prostu zwraca nelement th listy [0,0,0,1,1,1,2, ...].

C #, 232 bajty

Mój pierwszy kod golfowy ... A ponieważ nie było żadnego C # i chciałem wypróbować inną metodę, której nie wypróbowałem tutaj, pomyślałem, że dam temu szansę. Podobnie jak niektóre inne tutaj, tylko liczby nieujemne.

class l:System.Collections.Generic.List<int>{}class p{static void Main(string[] g){int n=int.Parse(g[0]);l b,a=new l();b=new l();while(a.Count<n)a.Add(1);while(a.Count>2){a.RemoveRange(0,3);b.Add(1);}System.Console.Write(b.Count);}}

Bez golfa

class l : System.Collections.Generic.List<int>
{ }
class p
{
    static void Main(string[] g)
    {
        int n = int.Parse(g[0]);
        l b, a = new l();
        b = new l();
        while (a.Count < n) a.Add(1);
        while (a.Count > 2)
        {
            a.RemoveRange(0, 3);
            b.Add(1);
        }
        System.Console.Write(b.Count);
    }
}

Perl (26 22)

$_=3x pop;say s|333||g

Ta wersja (ab) wykorzystuje silnik wyrażeń regularnych Perla. Odczytuje liczbę jako ostatni argument wiersza poleceń ( pop) i buduje ciąg 3s o tej długości ( "3" x $number). Operator podstawienia wyrażenia regularnego ( s///tutaj napisany różnymi separatorami ze względu na reguły układanki i gflagę lobal) podstawia trzy znaki pustym łańcuchem i zwraca liczbę podstawień, która jest liczbą całkowitą podzieloną przez trzy. Można go nawet napisać bez 3, ale powyższa wersja wygląda śmieszniej.

$ perl -E '$_=3x pop;say s|333||g' 42
14

C, 160 znaków

Rozwiązanie podziału znak po znaku za pomocą tabel odnośników, tj. Bez ciągu atoi () lub printf () do konwersji między ciągami podstawowymi 10 a liczbami całkowitymi.

Czasami wynik będzie zawierał wiodące zero - część jego uroku.

main(int n,char**a){
char*s=a[1],*x=0;
if(*s==45)s=&s[1];
for(;*s;s=&s[1])n=&x[*s&15],x="036"[(int)x],*s=&x["000111222333"[n]&3],x="012012012012"[n]&3;
puts(a[1]);
}

Uwaga:

• nadużywa dostępu do tablicy w celu dodania implementacji.
• kompiluje się z clang 4.0, inne kompilatory mogą mieć problemy.

Testowanie:

./a.out -6            -2
./a.out -5            -1
./a.out -4            -1
./a.out -3            -1
./a.out -2            -0
./a.out -1            -0
./a.out 0             0
./a.out 1             0
./a.out 2             0
./a.out 3             1
./a.out 4             1
./a.out 5             1
./a.out 6             2
./a.out 42            14
./a.out 2011          0670

Python 42

int(' -'[x<0]+str(len(range(2,abs(x),3))))

Ponieważ każde opublikowane tutaj rozwiązanie, które sprawdziłem, obcina ułamki dziesiętne, jest to moje rozwiązanie, które to robi.

Python 50 51

int(' -'[x<0]+str(len(range([2,0][x<0],abs(x),3))))

Ponieważ python wykonuje podział podłogi, oto moje rozwiązanie, które to implementuje.

Wejściowa liczba całkowita znajduje się w zmiennej x.

Testowany w Pythonie 2.7, ale podejrzewam, że działa również w wersji 3.

JavaScript, 55

alert(parseInt((~~prompt()).toString(3).slice(0,-1),3))

Jeśli nie można użyć -1, to jest wersja zastępująca go ~0(dzięki Peter Taylor!).

alert(parseInt((~~prompt()).toString(3).slice(0,~0),3))

C 83 znaków

Liczba do dzielenia jest przekazywana przez stdin i zwraca ją jako kod wyjścia z main()(% ERRORLEVEL% w CMD). Ten kod narusza niektóre wersje MinGW, ponieważ gdy optymalizacje nie są włączone, traktuje ostatnią wartość przypisania jako instrukcję return. Prawdopodobnie można to nieco zmniejszyć. Obsługuje wszystkie liczby, które mogą się zmieścić wint

Jeśli jednoargumentowe negowanie (-) jest niedozwolone: ​​(129)

I(unsigned a){a=a&1?I(a>>1)<<1:a|1;}main(a,b,c){scanf("%i",&b);a=b;a=a<0?a:I(~a);for(c=0;a<~1;a=I(I(I(a))))c=I(c);b=b<0?I(~c):c;}

Jeśli dozwolone jest jednoargumentowe zanegowanie : (123)

I(unsigned a){a=a&1?I(a>>1)<<1:a|1;}main(a,b,c){scanf("%i",&b);a=b;a=a<0?a:-a;for(c=0;a<~1;a=I(I(I(a))))c=I(c);b=b<0?-c:c;}

EDYCJA: ugoren wskazał mi, że - ~ jest przyrostem ...

83 Znaki, jeśli dozwolona jest jednoznaczna negacja: D

main(a,b,c){scanf("%i",&b);a=b;a=a<0?a:-a;for(c=0;a<~1;a=-~-~-~a)c=-~c;b=b<0?-c:c;}

C, 139 znaków

t;A(a,b){return a?A((a&b)<<1,a^b):b;}main(int n,char**a){n=atoi(a[1]);for(n=A(n,n<0?2:1);n&~3;t=A(n>>2,t),n=A(n>>2,n&3));printf("%d\n",t);}

Uruchom z liczbą jako argumentem wiersza poleceń

• Obsługuje zarówno liczby ujemne, jak i dodatnie

Testowanie:

 ./a.out -6            -2
 ./a.out -5            -1
 ./a.out -4            -1
 ./a.out -3            -1
 ./a.out -2            0
 ./a.out -1            0
 ./a.out 0             0
 ./a.out 1             0
 ./a.out 2             0
 ./a.out 3             1
 ./a.out 4             1
 ./a.out 5             1
 ./a.out 6             2
 ./a.out 42            14
 ./a.out 2011          670

Edycje:

• zapisano 10 znaków przez tasowanie dodawania (A) w celu usunięcia zmiennych lokalnych.

ZSH - 31 20/21

echo {2..x..3}|wc -w

Dla liczb ujemnych:

echo {-2..x..3}|wc -w

Z liczbami ujemnymi (ZSH + bc) -62 61

Prawdopodobnie nie powinienem podawać dwóch programów jako odpowiedzi, więc oto jeden, który działa na dowolny znak liczby:

echo 'obase=10;ibase=3;'`echo 'obase=3;x'|bc|sed 's/.$//'`|bc

Wykorzystuje tę samą podstawową sztuczkę konwersji, co odpowiedź Artem Ice .

C, 81 73 znaków

Obsługuje tylko liczby nieujemne.

char*x,*i;
main(){
    for(scanf("%d",&x);x>2;x=&x[~2])i=&i[1];
    printf("%d",i);
}

Chodzi o użycie arytmetyki wskaźnika. Liczba jest wczytywana do wskaźnika x, który nigdzie nie wskazuje. &x[~2]= &x[-3]= x-3służy do odejmowania 3. To się powtarza, dopóki liczba jest powyżej 2. iZlicza ile razy jest to zrobione ( &i[1]= i+1).

Jawa 86 79

Załóżmy, że liczba całkowita jest w y:

Konwertuje na ciąg znaków w bazie 3, usuwa ostatni znak (prawy Shift „>>” w bazie 3), a następnie konwertuje z powrotem na liczbę całkowitą.

Działa dla liczb ujemnych.

Jeśli liczba y wynosi <3 lub> -3, to daje 0.

System.out.print(~2<y&y<3?0:Long.valueOf(Long.toString(y,3).split(".$")[0],3));

Pierwszy post na kod-golfie. =) Więc nie mogę jeszcze komentować.

Dziękuję Kevin Cruijssen za wskazówki.

Python 2.6 ( 29 ) ( 71 ) ( 57 ) ( 52 ) (43)

z=len(range(2,abs(x),3))
print (z,-z)[x<0]

print len(range(2,input(),3))

Edycja - Właśnie zdałem sobie sprawę, że musimy również obsługiwać liczby całkowite ujemne. Naprawię to później

Edycja2 - Naprawiono

Edit3 - Zapisano 5 znaków, postępując zgodnie z radą Joela Cornetta

Edit4 - Ponieważ dane wejściowe niekoniecznie muszą pochodzić ze STDIN lub ARGV, zapisano 9 znaków, nie pobierając żadnych danych wejściowych ze standardowego wejścia

JavaScript, 47 29

Używa evaldo dynamicznego generowania pliku /. Używa +tylko do łączenia łańcuchów, a nie dodawania.

alert(eval(prompt()+"\57"+3))

EDYCJA: Używane "\57"zamiastString.fromCharCode(47)

Rubin ( 43 22 17)

Nie tylko golf, ale także elegancja :)

p Rational gets,3

Wyjście będzie jak (41/1). Jeśli musi być liczbą całkowitą, musimy dodać .to_iwynik, a jeśli zmienimy to_ina, to_fwówczas możemy uzyskać dane wyjściowe również dla liczb zmiennoprzecinkowych .

TI-Basic, 8 bajtów

Zwycięzca? :)

int(mean({Ans,0,0

PS Zaokrągla w kierunku nieskończoności dla liczb ujemnych (patrz tutaj, dlaczego). Aby zaokrąglić do zera zamiast wymienić int(ze iPart(bez zmian bajtów.

Przypadki testowe

-4:prgmDIVIDE
              -2
11:prgmDIVIDE
               3
109:prgmDIVIDE
              36

Python 2.x, 54 53 51

print' -'[x<0],len(range(*(2,-2,x,x,3,-3)[x<0::2]))

Gdzie _jest dywidenda i jest wpisana jako taka.

>>> x=-19
>>> print' -'[x<0],len(range(*(2,-2,x,x,3,-3)[x<0::2]))
- 6

Uwaga: Nie jestem pewien, czy korzystanie z interaktywnego interpretera jest dozwolone, ale zgodnie z OP: „Wejście może być na STDIN lub ARGV lub wprowadzone w inny sposób”

Edycja: Teraz dla Pythona 3 (działa w wersji 2.x, ale drukuje krotkę). Działa z negatywami.

C ++, 191

Z main i obejmuje, jego 246, bez main i obejmuje, to tylko 178. Newlines liczą się jako 1 znak. Traktuje wszystkie liczby jako niepodpisane. Nie dostaję ostrzeżeń za to, że główny zwrot jest bez znaku, więc jest to uczciwa gra.

Mój pierwszy w historii kodegolf.

#include<iostream>
#define R return
typedef unsigned int U;U a(U x,U y){R y?a(x^y,(x|y^x^y)<<1):x;}U d(U i){if(i==3)R 1;U t=i&3,r=i>>=2;t=a(t,i&3);while(i>>=2)t=a(t,i&3),r=a(r,i);R r&&t?a(r,d(t)):0;}U main(){U i;std::cin>>i,std::cout<<d(i);R 0;}

używa przesunięć do wielokrotnego dzielenia liczby przez 4 i oblicza sumę (która jest zbieżna do 1/3)

Pseudo kod:

// typedefs and #defines for brevity

function a(x, y):
    magically add x and y using recursion and bitwise things
    return x+y.

function d(x):
    if x = 3:
        return 1.
    variable total, remainder
    until x is zero:
        remainder = x mod 4
        x = x / 4
        total = total + x
    if total and remainder both zero:
        return 0.
    else:
        return a(total, d(remainder)).

Nawiasem mówiąc, mógłbym wyeliminować główną metodę, nazywając d main i ustawiając go jako char ** i używając programów zwracających wartość jako wynik. Zwróci liczbę argumentów wiersza poleceń podzieloną przez trzy, zaokrągloną w dół. To zwiększa jego długość do reklamowanej 191:

#define R return
typedef unsigned int U;U a(U x,U y){R y?a(x^y,(x|y^x^y)<<1):x;}U main(U i,char**q){if(i==3)R 1;U t=i&3,r=i>>=2;t=a(t,i&3);while(i>>=2)t=a(t,i&3),r=a(r,i);R r&&t?a(r,d(t)):0;}

Golfscript - 13 znaków

~3base);3base

PowerShell 57 lub 46

57 znakami %używanymi jako operator foreach PowerShell, a nie modulo. To rozwiązanie może przyjmować dodatnie lub ujemne liczby całkowite.

(-join(1..(Read-Host)|%{1})-replace111,0-replace1).Length

W 46 znakach, jeśli *jest dozwolone jako operator powtarzania łańcucha, nie mnożyć. Ta opcja wymaga dodatnich liczb całkowitych jako wartości wejściowych.

("1"*(Read-Host)-replace111,0-replace1).Length

R

Te działają tylko z dodatnimi liczbami całkowitymi:

max(sapply(split(1:x,1:3), length))
# Gives a warning that should be ignored

Lub:

min(table(rep(1:3, x)[1:x]))

Lub:

length((1:x)[seq(3,x,3)])

Lub:

sum(rep(1,x)[seq(3,x,3)])

[[EDYCJA]] I brzydka:

trunc(sum(rep(0.3333333333, x)))

[[EDIT2]] Plus prawdopodobnie najlepszy - zainspirowany powyższym kodem Matlab autorstwa Elliota G:

length(seq(1,x,3))

SmileBASIC, 58 51 36 bajtów (brak funkcji matematycznych!)

INPUT N
BGANIM.,4,-3,N
WAIT?BGROT(0)

Wyjaśnienie:

INPUT N           'get input
BGANIM 0,"R",-3,N 'smoothly rotate background layer 0 by N degrees over 3 frames
WAIT              'wait 1 frame
PRINT BGROT(0)    'display angle of layer 0

Program płynnie przesuwa warstwę tła o 3 klatki, a następnie uzyskuje kąt po 1 klatce, gdy pokonał 1/3 całkowitej odległości.

Wersja z pływakiem, 38 bajtów:

INPUT N
BGANIM.,7,-3,N
WAIT?BGVAR(0,7)

Wyjaśnienie:

INPUT N           'input
BGANIM 0,"V",-3,N 'smoothly change layer 0's internal variable to N over 3 frames
WAIT              'wait 1 frame
PRINT BGVAR(0,7)  'display layer 0's internal variable

Haskell 41 39 znaków

Działa z pełnym zestawem liczb całkowitych dodatnich i ujemnych

f n=sum[sum$1:[-2|n<0]|i<-[3,6..abs n]]

Najpierw tworzy listę 1 lub (-1) (w zależności od znaku wejścia) dla co trzeciej liczby całkowitej od 0 do wejścia n .abs(n)dla liczb ujemnych włącznie.

na przykład n=8 -> [0,3,6]

Następnie zwraca sumę tej listy.

Clojure, 87; działa z negatywami; oparty na lazyseqs

(defn d[n](def r(nth(apply interleave(repeat 3(range)))(Math/abs n)))(if(> n 0)r(- r)))

Nie golfowany:

(defn d [n]
  (let [r (nth (->> (range) (repeat 3) (apply interleave))
               (Math/abs n))]
        (if (pos? n)
          r
          (- r))))

Sage Notebook (21)

ZZ(n.digits(3)[1:],3)