Sprawdź, czy liczba całkowita jest podzielna przez 3

20

Twoim celem jest ustalenie, czy liczbę można podzielić przez 3 bez użycia warunków warunkowych. Wprowadzony zostanie 8-bitowa liczba bez znaku od 0 do 255. Zachęcamy do kreatywności!

Możesz używać TYLKO

  • Równość / nierówność ( ==, !=, >, <, >=, <=)

  • Arytmetyczna ( +, -, x)

  • Operatory logiczne ( !nie &&i, || lub)

  • Operatory bitowe ( ~nie, &i, |lub, ^xor, <<, >>, >>>arytmetyczne i logiczne zmiany lewy i prawy)

  • Stałe (byłoby lepiej, gdybyś trzymał je małe)

  • Zmienne przypisanie

Wyjście, 0jeśli fałsz, 1jeśli prawda.

Obowiązują standardowe zasady kodowania atomowego. Jeśli masz jakieś pytania, zostaw je w komentarzach. Przykładowe metody tutaj . Token to dowolny z powyższych elementów, z wyłączeniem stałych i zmiennych.

qwr
źródło
@GregHewgill Moja literówka powinna być liczbą 8-bitową.
qwr
2
Czy wolno nam korzystać tylko z powyższych operatorów? W przeciwnym razie modulo uczyniłoby to w ten sposób zbyt łatwym.
Jwosty
A co powiesz na wyszukiwanie w tabeli?
Greg Hewgill
3
Czy możesz wyjaśnić, co masz na myśli przez brak warunkowych? Czy ogranicza się do instrukcji JEŻELI, czy też odnosi się do rzeczy takich jak pętle?
Ruslan
1
@ Ruslan Możesz używać tylko powyższych.
qwr

Odpowiedzi:

31

C - 2 żetony

int div3(int x) {
    return x * 0xAAAAAAAB <= x;
}

Wydaje się działać do 2 31 -1.

Kredyty zalgo("nhahtdh")na multiplikatywny odwrotny pomysł.

aditsu
źródło
1
+1. Był nieco zaskoczony tym, jak <=działa, i pamiętał, że 0xAAAAAAAB jest traktowane jako unsigned inttyp, więc wynik mnożenia jest niepodpisany.
n̴̖̋h̷͉̃a̷̭̿h̸̡̅ẗ̵̨d̷̰̀ĥ̷̳
@DigitalTrauma operatorzy nierówności są dozwoleni, nie zbanowani
aditsu
@aditsu Ups! Czasami muszę uważniej czytać! +1 świetna odpowiedź!
Digital Trauma
@aditsu, przepraszam jestem noob, jak dokładnie to działa?
Kartik_Koro
2
@Kartik_Koro 0xAAAAAAAB * 3 == 1 z powodu przepełnienia, więc dla dowolnego int x, x * 0xAAAAAAAB * 3 == x. Również y * 3 ma różne wartości dla różnych y, dlatego y = x * 0xAAAAAAAB musi być jedynym y takim, że y * 3 == x. Jeśli x jest wielokrotnością 3, to y musi być x / 3, w przeciwnym razie musi działać przez przepełnienie. Prostym sposobem sprawdzenia jest porównanie y z x. Zobacz także en.wikipedia.org/wiki/Modular_multiplicative_inverse
aditsu
17

Pyton, 3 2 tokeny

Rozwiązanie brutalnej siły, ale działa.

0x9249249249249249249249249249249249249249249249249249249249249249>>x&1

Podziękowania dla Howarda za redukcję 1 tokena.

Greg Hewgill
źródło
Łał! Twoje rozwiązanie jest prawdopodobnie najkrótsze (3 tokeny), ale chcę zachęcić również inne odpowiedzi.
qwr
11
Jest nawet 2 rozwiązanie znak: 0x9......>>x&1.
Howard
6

C - 5 4 (?) Żetonów

int div3_m2(uint32_t n) {
    return n == 3 * (n * 0xAAAAAAABull >> 33);
}

Pracuje dla dowolnym niepodpisanym 32-bitowym numerem .

Ten kod wykorzystuje multiplikatywny odwrotny moduł 2 32 dzielnika do przekształcania operacji dzielenia na operację mnożenia.

Edytować

Moje rozwiązanie (opublikowane 2 minuty później) ma tego samego ducha, co rozwiązanie aditsu. Podziękowania dla niego za użycie== tego ulepsza moje rozwiązanie o 1 token.

Odniesienie

n̴̖̋h̷͉̃a̷̭̿h̸̡̅ẗ̵̨d̷̰̀ĥ̷̳
źródło
1
To jest niesamowite. Wiedziałem o magicznych liczbach ze słynnej sztuczki z odwrotnym kwadratem, ale nie wiedziałem, że można jej użyć do dowolnego dzielnika. To jest Bull: P
qwr
Tak, 0xAAAAAAAB = (2 ^ 33 + 1) / 3 i 171 = (2 ^ 9 + 1) / 3. Wybrałem najmniejszą stałą, która działa. Hmm, właściwie to wydaje się również działać z 86 = (2 ^ 8 + 2) / 3
aditsu
Szczury, nawet 43 = (2 ^ 7 + 1) / 3 działa, nie jestem pewien, jak mi tego brakowało. Edytowane teraz.
aditsu
4

C - 15 (?) Żetonów

int div3_m1(unsigned int n) {
    n = (n & 0xf) + (n >> 4);
    n = (n & 0x3) + (n >> 2);
    n = (n & 0x3) + (n >> 2);
    return n == 0 || n == 3;
}

Od 4 ≡ 1 (mod 3) mamy 4 n ≡ 1 (mod 3). Reguła sumowania cyfr nie ogranicza się do sumowania cyfr, ale pozwala również dowolnie podzielić liczbę na sekwencje cyfr i zsumować je wszystkie, zachowując zgodność.

Przykład w bazie 10, dzielnik = 9:

1234 ≡ 12 + 34 ≡ 1 + 2 + 3 + 4 ≡ 123 + 4 ≡ 1 (mod 9)

Wszystkie instrukcje w programie korzystają z tej właściwości. Można go uprościć do pętli, która uruchamia instrukcję, n = (n & 0x3) + (n >> 2);dopóki n < 4instrukcja nie podzieli liczby w bazie-4 na co najmniej znaczącą cyfrę i zsumuje 2 części.

n̴̖̋h̷͉̃a̷̭̿h̸̡̅ẗ̵̨d̷̰̀ĥ̷̳
źródło
+1: co ciekawe, działa to dla n do 512 (faktycznie n = 590), ale nie jestem całkiem pewien, dlaczego.
Paul R
@PaulR: To nie zadziała dla większych liczb z powodu przenoszenia (zwróć uwagę, że użyłem dodawania w obliczeniach). Zwróć także uwagę na powtarzające się linie.
n̴̖̋h̷͉̃a̷̭̿h̸̡̅ẗ̵̨d̷̰̀ĥ̷̳
Tak, po prostu nie jestem pewien, dlaczego działa dla wartości 9-bitowych, ponieważ wydaje się, że testuje tylko 8 bitów?
Paul R
dla liczb 9-bitowych po pierwszym dodaniu staje się co najwyżej 5 bitów, po pierwszym n = (n & 0x3) + (n >> 2);wyniku zmniejsza się do 3 bitów, a powtórzenie spowodowało, że pozostały tylko 2 bity stackoverflow.com/a/3421654/995714
phuclv
1
och, popełniłem błąd. Liczba 5-bitowa + liczba 4-bitowa może dać liczbę 6-bitową. Ale jeśli n <= 588, dodanie 4 górnych bitów i 2 dolnych bitów tej 6-bitowej liczby daje tylko 4-bitową sumę. Ponownie dodanie tego wyniku daje liczbę 2-bitową. 589 i 590 dają 3 bity w ostatniej sumie, ale nawiasem mówiąc, nie można ich podzielić przez 3, więc wynik jest poprawny
phuclv
2

Python (2 tokeny?)

1&66166908135609254527754848576393090201868562666080322308261476575950359794249L>>x

Lub

1&0x9249249249249249249249249249249249249249249249249249249249249249L>>x

Lub

1&0b1001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001>>x
.ıʇǝɥʇuʎs
źródło
2
Duplikat komentarza Howarda
aditsu
@aditsu ... Wielkie umysły myślą podobnie? Przysięgam, że nie widziałem tego przed opublikowaniem tego.
23ıʇǝɥʇuʎs
2

JavaScript - 3 tokeny

function div3(n) {
    var a = n * 0.3333333333333333;
    return (a | 0) == a;
}

To narusza fakt, że użycie bitowych operatorów na liczbach skraca ją do liczby całkowitej w JavaScript.

Tyilo
źródło
Powinno być 4 tokeny: =, *, |,==
n̴̖̋h̷͉a̷̭̿h̸̡̅ẗ̵̨d̷̰ĥ̷̳
1
Nie sądzę, aby przypisanie zmiennej liczyło się jako token.
Tyilo
1

C - 4 żetony

int div3(int x) {
    return ((x * 43) >> 7) * 3 == x;
}

Działa do 383.

Poprzednia wersja (większe stałe):

int div3(int x) {
    return ((x * 171) >> 9) * 3 == x;
}

Działa do 1535

aditsu
źródło
1

bash - ???

Nie jestem pewien, jak to zdobyć.

seq 0 85 | awk '{print $1 * 3}' | grep -w [number] | wc -l

na przykład

$ seq 0 85 | awk '{print $1 * 3}' | grep -w 11 | wc -l
0

$ seq 0 85 | awk '{print $1 * 3}' | grep -w 12 | wc -l
1

$seq 0 85 | awk '{print $1 * 3}' | grep -w 254 | wc -l
0

$seq 0 85 | awk '{print $1 * 3}' | grep -w 255 | wc -l
1

źródło
1

Befunge 93 - 5 żetonów

Naprawiono - podział został usunięty.

v      @._1.@
         \   
         0   
         +   
         3   
>&>3-:0\`|   
  ^      <   

Pobiera dane wejściowe, odejmuje 3, aż będzie mniejsze niż 0, skieruj wskaźnik w górę („|”), a następnie dodaje 3. Jeśli wartość wynosi 0, wówczas wskaźnik przesuwa się w prawo („ 1. @” wysyła „1”), w przeciwnym razie przesuwa się w lewo („@. ” wyprowadza „0”). „@” kończy program.

AndoDaan
źródło
1

Partia - 7 żetonów

Myślę

@echo off
for /L %%a in (0,3,%1) do set a=%%a
if %a%==%1 echo 1

Zwraca, 1jeśli podaną liczbę (jako stdin) można podzielić przez trzy.

nieprzyzwoity
źródło
Czy pętle są dozwolone?
sergiol
1

Rubin, 6 (?) Żetonów

Naprawdę nie jestem pewien, jak liczyć tokeny. OP, możesz mnie zdobyć?

Myślę, że to 6 ... 1, 0, 0,* , 255,x

Zauważ, że *mnożenie nie jest liczbą całkowitą.

def div3(x)
  ([1,0,0]*255)[x]
end
Nie ten Charles
źródło
Czy token w sensie OP nie byłby tylko jednym z powyższych wymienionych w pytaniu?
C5H8NNaO4
@ C5H8NNaO4 Co z tego? 0?
Nie to, że Charles
@ C5H8NNaO4 może 4 dla stałych?
Nie, że Charles
1

Python 0

Wysłałem Eariler, ale użyłem warunkowych. Nie używaj warunkowych i żadnych tokenów, tylko słowa kluczowe

def g(x): return ([[lambda : g(sum(int(y) for y in list(str(x)))),lambda: 0][[False,True].index(x in[0,1,2,4,5,7,8])], lambda: 1][[False,True].index((lambda y: y in[3,6,9])(x))])()

wykorzystuje sztuczkę polegającą na tym, że wielokrotność 3 ma cyfry, które dodają do 3

Edycja: Usunięto niepotrzebną lambda

def g(x):return([[lambda: g(sum(int(y) for y in list(str(x)))),lambda:0][[False,True].index(x in[0,1,2,4,5,7,8])], lambda:1][[False,True].index(x in[3,6,9])])()

Edycja: Dalsza gra w golfa (117 znaków) wciąż nie zawiera tokenów

exec"g=`x:(((`:g(sum(int(y)for y in str(x)),`:0)[x in[0,1,2,4,5,7,8]],`:1)[x in[3,6,9]])()".replace('`','lambda ')

Zabity bezpośredni dostęp do fajnego getitem Pythona Dłuższy w 132 znakach

exec"g={0}x:((({0}:g(sum(int(y)for y in str(x))),{0}:0{1}0,1,2,4,5,7,8]),{0}:1{1}3,6,9]))()".format('lambda ',').__getitem__(x in[')

http://www.codeskulptor.org/#user34_uUl7SwOBJb_0.py

Dylan Madisetti
źródło
Dostęp do tablicy []jest jednak niedozwolony.
n̴̖̋h̷͉̃a̷̭̿h̸̡̅ẗ̵̨d̷̰̀ĥ̷̳
To jest? Po tych regułach codegolf.stackexchange.com/tags/atomic-code-golf/info
Dylan Madisetti
Cóż, pytanie nie używa reguły w wiki tagu. Pytanie ma dozwolone ograniczenia operacji. Zwróć uwagę na słowo only.
n̴̖̋h̷͉̃a̷̭̿h̸̡̅ẗ̵̨d̷̰̀ĥ̷̳
@ n̴̖̋h̷͉̃a̷̭̿h̸̡̅ẗ̵̷̨̰́̀ĥ̷̷̳̰̀ĥ̷̳ Dobrze, że python ma też natywny atrybut
Dylan Madisetti
0

Python - 25 tokenów

Na początek mam długie rozwiązanie, które jest implementacją jednej z odpowiedzi w linku w moim pierwszym poście. njest wejściem.

a = (n>>7)-((n&64)>>6)+((n&32)>>5)-((n&16)>>4)+((n&8)>>3)-((n&4)>>2)+((n&2)>>1)-(n&1)
print(a==0 or a==3)

orjest równoważne z ||.

qwr
źródło
0

JavaScript - 3 tokeny

Przetestuj na konsoli przeglądarki:

a = prompt().split('');
sum = 0;

do {
  sum = a.reduce(function(p, c) {
     return parseInt(p) + parseInt(c); 
  });

  a = sum.toString().split('');

} while(a.length > 1)

alert([3, 6, 9].indexOf(+sum) > -1)
William Barbosa
źródło
Jak doszedłeś do tego wniosku? Liczę około 37 żetonów.
nyuszika7h
„Token to dowolny z powyższych elementów, z wyłączeniem stałych i zmiennych”. Jak naliczyłeś 37?
William Barbosa
1
Rozumiem. OP wydaje się nie zgadzać ze stroną informacyjną atomic-code-golf .
nyuszika7h
Właściwie nie jestem pewien, czy mam rację, czy nie. Mój wynik wyniósłby 70+ według skrzypków golfowych z kodem atomowym.
William Barbosa
1
Problem nie dotyczy liczby tokenów, ale tego, jakich operacji używasz. Nie wydaje mi się, aby dozwolone było toTrybowanie, analiza, pętle, tablice itp.
aditsu
0

JavaScript
nie jest pewny co do tokena #

function mod3 (i) { return {'undefined':'100','0':'0'}[[0][i]][i.toString (3).split('').pop ()]}

lub jeśli wyjście dla 0 może wynosić 1;

function mod3 (i) { return '100'[i.toString (3).split('').pop ()]}

C5H8NNaO4
źródło
2
Muszę powiedzieć, że nie jestem pewien, jakie zasady dotyczą tego wyzwania. Czy dozwolone są wywołania funkcji i dostęp do nieruchomości?
C5H8NNaO4
0

Tcl , 83 bajty

proc T n {while \$n>9 {set n [expr [join [split $n ""] +]]};expr {$n in {0 3 6 9}}}

Wypróbuj online!

sergiol
źródło
Nieudany outgolf: 96 bajtów proc T n {set n [expr [join [split [expr [join [split $n ""] +]] ""] +]];expr {$n in {0 3 6 9}}} Wypróbuj online!
sergiol
Kolejny błąd: ** 87 bajtów ** proc T n {expr {[expr [join [split [expr [join [split $n ""] +]] ""] +]] in {0 3 6 9}}} Wypróbuj online!
sergiol