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__
lubadd()
). Dotyczy to również operatorów zwiększających i zmniejszających, takich jaki++
lubi--
. 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
Odpowiedzi:
J,
45 4410 znaków".,&'r3'":
Działa z negatywami:
":
- sformatuj jako tekst,&'r3'
- dołączr3
do końca".
- wykonać ciąg, np15r3
źródło
3 3 3 #: 9
. Wygląda na to, że musisz wiedzieć, jak długo potrwa twój trójkowy numer._3]\i.
jest również możliwym punktem wyjścia do czegoś, ale nie wiem, czy byłoby to krótsze niż twoje rozwiązanie tutaj. Problem#_3]\i.
polega na tym, że zawsze zaokrągla w górę zamiast w dół.##~3=_3#\i.
dla 11 znaków?##~0 0 1$~
.3#.}:(#:~$&3)
ale jest jeszcze dłuższy i nie rozwiązuje problemu liczby ujemnej.^:
lub Agendy@.
do wymianyif
lubif...else
zamiany. W takim przypadku możesz użyć@.
dwóch czasowników połączonych ze znakiem `` '' (gerund w J-speak), aby wybrać jedno lub drugie na podstawie warunku.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:
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:
./test.py | pv --buffer-size=1M --average-rate > /dev/null
przez 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../test.py | tcc -c - -o /dev/stdout | pv --buffer-size=1M --average-rate > /dev/null
, ale wydaje się, żetcc
nic nie wyświetla, dopóki nie wczyta całego pliku źródłowego.źródło
a[b]
jest cukrem syntaktycznym*(a + b)
, który dodaje.Rubin 28
Aby podzielić przez 3, wystarczy usunąć końcowe zero w liczbie podstawowej 3:
120 -> 11110 -> 1111 -> 40
Działa z negatywami:
Ruby,
6045Alternatywnie, 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}źródło
/
operator, w którym sięFloat::INFINITY
stał1.0/0
. Z Ruby 2.1 można grać(0..1.0/0).step(3)
w golfa0.step(p,3)
, usuwając/
. Większy problem polega na tym, że-r
używa się go-
do negowania. Zmiana-r
na 5 kosztuje~r.pred
, nadużywając liczby całkowitej przed odjęciem 1 bez operatora odejmowania.Mathematica, 13 znaków
źródło
&
i użyć zwykłej zmiennej (inni tutaj też to robią).JavaScript, 56
Sprawia ciąg długości
n
powtarzania,
S i zastępuje,,,
się1
. Następnie mierzy wynikową długość łańcucha. (Mam nadzieję, że jedność-
jest dozwolona!)źródło
-
operatora negacji.-~
zparseInt()
-~prompt()
jest o jeden większa niżparseInt(prompt())
. Nie jestem pewien, jak sobie z tym poradzisz.alert(Array(parseInt(prompt())).slice(1).join().replace(/,,,/g,1).length)
Python,
4138xrange
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.źródło
10/3
wynosi 3, a nie 4.print" -"[x<0]+
len (range (2, abs (x), 3)) `` ogoliłby go do 39 znakówlen()
jako skrótrepr()
range
, ponieważ faktycznie utworzy listę.xrange
tylko udaje, że jest w stanie obsłużyć ogromne liczby bez marnowania czasu / pamięci.Haskell, 90
106Tworzy 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
27po prostu zwraca
n
element th listy[0,0,0,1,1,1,2, ...]
.źródło
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.
Bez golfa
źródło
string[] g
i zmieniając go wstring[]g
.Add
?Perl (
2622)Ta wersja (ab) wykorzystuje silnik wyrażeń regularnych Perla. Odczytuje liczbę jako ostatni argument wiersza poleceń (
pop
) i buduje ciąg3
s 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 ig
flagę 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ć bez3
, ale powyższa wersja wygląda śmieszniej.źródło
$_=3x pop;say s|333||g
.'$_=3x pop;say s|333||g||0
. Wolno przy dużych liczbach, takich jak 99999999, i nie działa z liczbami ujemnymi.-p
w wierszu poleceń, a możesz:$_=3x$_;$_=0|s|...||g
w sumie 22, w tym pokrycie 0, 1 lub 2 wejść.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.
Uwaga:
Testowanie:
źródło
Python 42
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
5051Ponieważ 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.
źródło
-3
jest to poprawna odpowiedź-10/3
.JavaScript, 55
Jeśli nie można użyć
-1
, to jest wersja zastępująca go~0
(dzięki Peter Taylor!).źródło
~
jest operatorem bitowym, który odwraca bity argumentu (najpierw konwertując go na liczbę). Jest to najkrótszy sposób na konwersję ciągu na liczbę (o ile wiem).~~
na liczbę całkowitą, w przeciwieństwie do+
.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)
Jeśli dozwolone jest jednoargumentowe zanegowanie : (123)
EDYCJA: ugoren wskazał mi, że - ~ jest przyrostem ...
83 Znaki, jeśli dozwolona jest jednoznaczna negacja: D
źródło
x+3
jest-~-~-~x
.C, 139 znaków
Uruchom z liczbą jako argumentem wiersza poleceń
Testowanie:
Edycje:
źródło
A
, moja funkcja sprawdza tylko bit i pod numerem n. Czy standard C pozwala na pomijanie deklaracji typu, czy jest to jakiś kompilator?ZSH -
3120/21Dla liczb ujemnych:
Z liczbami ujemnymi (ZSH +
bc
) -6261Prawdopodobnie nie powinienem podawać dwóch programów jako odpowiedzi, więc oto jeden, który działa na dowolny znak liczby:
Wykorzystuje tę samą podstawową sztuczkę konwersji, co odpowiedź Artem Ice .
źródło
C,
8173 znakówObsługuje tylko liczby nieujemne.
Chodzi o użycie arytmetyki wskaźnika. Liczba jest wczytywana do wskaźnika
x
, który nigdzie nie wskazuje.&x[~2]
=&x[-3]
=x-3
służy do odejmowania 3. To się powtarza, dopóki liczba jest powyżej 2.i
Zlicza ile razy jest to zrobione (&i[1]
=i+1
).źródło
Jawa
8679Załóż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.
Pierwszy post na kod-golfie. =) Więc nie mogę jeszcze komentować.
Dziękuję Kevin Cruijssen za wskazówki.
źródło
&&
do&
i 2xInteger
doLong
. (Ponadto, dlaczego używasz~2
zamiast po prostu-3
? Są one tym samym licznikiem bajtów.)-
, ale nie wiem, czy to się liczy dla jednoznacznej negacji.Python 2.6 (
29) (71) (57) (52) (43)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
źródło
abs()
print z if x==abs(x) else -z
print (z,-z)[x<0]
JavaScript,
4729Używa
eval
do dynamicznego generowania pliku/
. Używa+
tylko do łączenia łańcuchów, a nie dodawania.EDYCJA: Używane
"\57"
zamiastString.fromCharCode(47)
źródło
alert(eval(prompt()+"\573"))
?Rubin (
432217)Nie tylko golf, ale także elegancja :)
Wyjście będzie jak
(41/1)
. Jeśli musi być liczbą całkowitą, musimy dodać.to_i
wynik, a jeśli zmienimyto_i
na,to_f
wówczas możemy uzyskać dane wyjściowe również dla liczb zmiennoprzecinkowych .źródło
rational
linii w Ruby 1.9.3. Pominięcie nawiasów oszczędza jeszcze jeden znak .TI-Basic, 8 bajtów
Zwycięzca? :)
PS Zaokrągla w kierunku nieskończoności dla liczb ujemnych (patrz tutaj, dlaczego). Aby zaokrąglić do zera zamiast wymienić
int(
zeiPart(
bez zmian bajtów.Przypadki testowe
źródło
Python 2.x,
545351print' -'[x<0],len(range(*(2,-2,x,x,3,-3)[x<0::2]))
Gdzie
_
jest dywidenda i jest wpisana jako taka.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.
źródło
__len__
wystarczy.len(range(100,1000))
daje900
w 3.2.3 na Linuksie.len(xrange(0,_,3))
jest krótszy i znacznie szybszy.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.
używa przesunięć do wielokrotnego dzielenia liczby przez 4 i oblicza sumę (która jest zbieżna do 1/3)
Pseudo kod:
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:
źródło
Golfscript - 13 znaków
źródło
s/seem to //
:(. Muszę się nad tym zastanowić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.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.źródło
R
Te działają tylko z dodatnimi liczbami całkowitymi:
Lub:
Lub:
Lub:
[[EDYCJA]] I brzydka:
[[EDIT2]] Plus prawdopodobnie najlepszy - zainspirowany powyższym kodem Matlab autorstwa Elliota G:
źródło
wrong sign in 'by' argument
SmileBASIC,
585136 bajtów (brak funkcji matematycznych!)Wyjaśnienie:
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:
Wyjaśnienie:
źródło
Haskell
4139 znakówDziała z pełnym zestawem liczb całkowitych dodatnich i ujemnych
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.
źródło
Clojure, 87; działa z negatywami; oparty na lazyseqs
Nie golfowany:
źródło
Sage Notebook (21)
źródło