Wdrożenie zasady podzielności przez 7

25

Aby sprawdzić, czy liczba dziesiętna jest podzielna przez 7:

Usuń ostatnią cyfrę. Pomnóż to przez 2 i odejmij od tego, co zostało. Jeśli wynik jest podzielny przez 7, pierwotna liczba jest podzielna przez 7.

(opisane również np. tutaj )

Ta zasada jest przydatna przy ręcznym sprawdzaniu podzielności. Na przykład:

Czy 2016 można podzielić przez 7?

Odejmij 6*2od 201; otrzymujemy 189. Czy można to podzielić przez 7? Aby to sprawdzić, zastosujmy ponownie regułę.

Odejmij 9*2od 18; otrzymujemy 0. Dlatego 2016 można podzielić przez 7.

W tym wyzwaniu powinieneś stosować tę regułę, dopóki status podzielności nie będzie oczywisty , to znaczy liczba nie będzie większa niż 70 (patrz szczegóły poniżej). Utwórz funkcję lub pełny program.

Dane wejściowe : dodatnia liczba całkowita; twój kod powinien obsługiwać dane wejściowe do 32767 (obsługa liczb całkowitych o dowolnej dokładności jest zaletą; patrz poniżej).

Wyjście : liczba całkowita (prawdopodobnie ujemna), nie większa niż 70, która jest wynikiem zastosowania reguły podzielności przez 7 zero lub więcej razy.

Przypadki testowe:

Input                   Output      Alternative output

1                       1
10                      10          1
100                     10          1
13                      13          -5
42                      42          0
2016                    0
9                       9
99                      -9
9999                    -3
12345                   3
32767                   28          -14

---------- Values below are only relevant for the bonus

700168844221            70          7
36893488147419103232    32          -1
231584178474632390847141970017375815706539969331281128078915168015826259279872    8

W przypadku określenia dwóch możliwych wyników, każdy wynik jest poprawny: drugi odpowiada zastosowaniu reguły jeszcze raz. Zabronione jest stosowanie reguły do ​​liczby jednocyfrowej: jeśli usuniesz cyfrę, nie pozostanie nic (nie 0).


Bonus : Jeśli twój algorytm

gdzie njest liczba cyfr dziesiętnych:

Odejmij 50% liczby bajtów kodu.

Prawdziwy bonus :

Ponadto, jeśli twój algorytm odczytuje dane wejściowe w normalnym kierunku, zaczynając od najbardziej znaczącej cyfry, odejmij 50% jeszcze raz - twój wynik to 25% liczby bajtów (wydaje się to możliwe, ale nie jestem absolutnie pewien).

anatolig
źródło
1
@DenkerAffe Zwrócenie danych wejściowych w stanie „jak jest” jest dopuszczalne. Zaktualizowałem przypadek testowy wejścia = 10, aby to odzwierciedlić; taki był pomysł od samego początku.
anatolyg
4
Nie chciałbym używać tej reguły 1000000000000000000001.
Neil
1
Ale co, jeśli twój język ma long longwbudowany s lub inny równoważny typ?
SuperJedi224
1
Mówiłem, że w niektórych implementacjach jest to 128-bitowa liczba całkowita, która jest więcej niż wystarczająco duża dla tego ostatniego przypadku testowego.
SuperJedi224
7
-1. Nie wszystkie języki obsługują dowolną precyzję.
Marzec Ho

Odpowiedzi:

23

Golfscript, 27 22 bajtów

{.9>{.10/\10%2*-f}*}:f

Możesz użyć tego w następujący sposób:

1000f

Wyjaśnienie

{.9>{.10/\10%2*-f}*}:f
{                  }:f    # Define block 'f' (similar to a function)
 .                        # Duplicate the first value of the stack
  9>{            }*       # If the value on top of the stack is greater than 9 then the block is executed
     .10/\10%2*-          # Same as nb/10 - (nb%10 * 2) with some stack manipulations '.' to duplicate the top of the stack and '\' to swap the the first and second element of the stack
                f         # Execute block 'f'

5 bajtów zapisanych dzięki Dennisowi!

Dica
źródło
1
Witamy w Programowaniu zagadek i Code Golf. To dobra odpowiedź, jednak można ją poprawić, dodając podział kodu i wyjaśnienie, podobnie jak powyższe pytania. Aby odpowiedzieć na ten komentarz, wpisz @wizzwizz4( @następnie moją nazwę użytkownika) na początku komentarza (lub w dowolnym innym miejscu).
wizzwizz4
1
@ wizzwizz4 Better? Nie jestem pewien, czy rozumiem, co rozumiesz przez „rozbicie kodu” (przepraszam nie z native speakera)
Dica
8
Wierzę, że przez „rozbicie kodu” miał na myśli wyjaśnienie, które dodałeś. To naprawdę bardzo ładna pierwsza odpowiedź. Witamy na stronie!
Alex A.
1
Możesz przepisać {...}{}ifczęść jako {...}*, która po prostu zastosuje blok kodu zero jeden raz, w zależności od wartości wypchniętej przez >. Ponadto, mamy prawo wykonywać jedna iteracja (tak zastępując 70ze 9zapisuje bajt) i nie sądzę, trzeba pop z bloku ;.
Dennis
3
@Dica, jest to pierwsza odpowiedź wystarczająco dobra, aby uzyskać ponad 12 pozytywnych opinii na pytanie z jedynie 624 odsłonami i pochwalić dwóch moderatorów. Jeśli tak będzie dalej, wkrótce wyprzedzisz Dennisa!
wizzwizz4
13

Haskell, 35 bajtów

until(<71)(\n->div n 10-2*mod n 10)

Przykład użycia: until(<71)(\n->div n 10-2*mod n 10) 36893488147419103232-> 32.

Nic wielkiego do wyjaśnienia, to bezpośrednia implementacja algorytmu.

nimi
źródło
9

Galaretka, 11 bajtów

d⁵Uḅ-2µ>9$¿

Wypróbuj online!

Jak to działa

d⁵Uḅ-2µ>9$¿  Main link. Input: n

d⁵           Divmod; return [n : 10, n % 10].
  U          Upend; yield [n % 10, n : 10].
   ḅ-2       Convert from base -2 to integer, i.e., yield -2 × (n % 10) + (n : 10).

      µ      Push the previous chain as a link and begin a new, monadic chain.
          ¿  Apply the previous chain while...
       >9$     its return value is greater than 9.
Dennis
źródło
I jak zawsze galaretka wygrywa. Dennis, ile bajtów zajmie wdrożenie interpretera galaretki w Jelly?
Bálint
6

Python 2, 38 bajtów

f=lambda x:f(x/10-x%10*2)if x>70else x

Wypróbuj tutaj !

Proste podejście rekurencyjne. Drukuje x, jeśli jego <70 w przeciwnym razie stosuje zasadę podzielności i wywołuje się z wynikiem.

Denker
źródło
nie potrzebujesz miejsca po)
Maltysen
@Maltysen True. Kopiuj wkleiłem niewłaściwy, dzięki za podpowiedź!
Denker
2
If jest zbyt szczegółowe. f=lambda x:x*(x<70)or f(x/10-x%10*2)
patrz
1
@Seeq Dobra sztuczka, dzięki! Powinno to działać teoretycznie, ale osiąga maksymalną głębokość rekurencji z danymi wejściowymi 2016, podczas gdy moja wersja nie. Masz pomysł, dlaczego?
Denker
Ach, racja, nie brałem tego pod uwagę. Ta sztuczka jest uważana x*(x<70) != 0za warunek końcowy. Jeśli x osiągnie wartość 0 - podobnie jak w 2016 r. - warunek końcowy nigdy nie nastąpi.
patrz
6

Pyth, 13 bajtów

.W>H9-/ZTyeZQ

Wypróbuj online: pakiet demonstracyjny lub testowy

Spowoduje to wydrukowanie wszystkich alternatywnych odpowiedzi.

Wyjaśnienie:

.W>H9-/ZTyeZQ   
            Q   read a number from input
.W              while
  >H9              the number is greater than 9
                do the following with the number:
      /ZT          divide it by 10
     -             and subtract
         yeZ       2*(number%10)
Jakube
źródło
5

Julia, 27 26 bajtów

f(x)=x>9?f(x÷10-x%10*2):x

Jest to funkcja rekurencyjna, która przyjmuje liczbę całkowitą i zwraca a BigInt. Jeśli dane wejściowe są duże, jak w poprzednim przykładzie, Julia analizuje je jako a BigInt, więc konwersja ręczna nie jest konieczna.

Podejście to jest po prostu implementacją algorytmu. Będzie produkować alternatywne wyjścia. Biorąc moduł przy dzieleniu przez 10, otrzymujemy ostatnią cyfrę, a iloraz z dzielenia liczb całkowitych przez 10 daje wszystko oprócz ostatniej cyfry.

Oszczędność bajtu dzięki Dennisowi!

Alex A.
źródło
Mamy prawo wykonywać jedną iterację, więc zastąpienie 70ze 9zapisuje bajt.
Dennis
@Dennis Dobry telefon, dzięki!
Alex A.
4

Pyth, 17 bajtów

L?<b70by-/bT*%bT2

Wypróbuj tutaj!

To samo rekurencyjne podejście jak w mojej odpowiedzi w python . Definiuje lambda y, które nazywa się tak: y12345.
Licznik bajtów w tłumaczeniu online pokazuje 19 bajtów, ponieważ dodałem do niego wywołanie lambda, więc możesz po prostu spróbować, naciskając przycisk Run.

Wyjaśnienie

L?<b70by-/bT*%bT2

L                  # Defines the lambda y with the parameter b
 ?<b70             # if b < 70:
      b            # return b, else:
       -/bT*%bT2   # calculate b/10 - b%10*2 and return it
Denker
źródło
Masz literówkę w swoim wyjaśnieniu, 17 powinno mieć 70: P
FryAmTheEggman
4

CJam - 19 bajtów

Wersja do wykonania:

r~A*{`)]:~~Y*-_9>}g

Wypróbuj online lub W wersji nr 1:

r~{_9>}{`)]:~~Y*-}w

Wypróbuj online lub Podczas wersji 2:

r~{_9>}{_A/\A%Y*-}w

Wypróbuj online .

r~                     | Read and convert input
  A*                   | Multiply by 10 to get around "if" rule
     `                 | Stringify
      )                | Split last character off
       ]               | Convert stack to array
        :~             | Foreach in array convert to value
          ~            | Dump array
           Y*          | Multiply by 2
             -         | Subtract
              _        | Duplicate
               9>      | Greater than 9?
    {            }g    | do-while
CJ Dennis
źródło
3

Oracle SQL 11.2, 116 bajtów

WITH v(i)AS(SELECT:1 FROM DUAL UNION ALL SELECT TRUNC(i/10)-(i-TRUNC(i,-1))*2 FROM v WHERE i>70)SELECT MIN(i)FROM v;

Nie grał w golfa

WITH v(i) AS
(
  SELECT :1 FROM DUAL
  UNION ALL
  SELECT TRUNC(i/10)-(i-TRUNC(i,-1))*2 FROM v WHERE i>70
)
SELECT MIN(i) FROM v;
Jeto
źródło
3

Haskell, 157 192 184 167 159 147 138 138 + 5 bajtów - 50% = 71,5 bajtów

O (1) space, O (n) time, single-pass!

h d=d%mod d 10
d%r=(quot(r-d)10,r)
p![d]=d-p*10
p![d,e]=d#(e-p)
p!(d:e:f)|(b,a)<-quotRem(2*d)10,(q,r)<-h$e-a-p=(b+q)!(r:f)
m#0=m
m#n=n-2*m
(0!)

Użyj, 0![6,1,0,2]aby zastosować regułę do 2016 r., Tzn. Przekaż jej liczbę w formie strumienia, zaczynając od najmniej znaczącej liczby. W ten sposób przejdzie przez cyfrę po cyfrze, stosując regułę o złożoności przestrzeni O (1).

Niegolfowany kod jest tutaj:

import Data.Char

{- sub a b = sub2 0 a b
  where
    sub2 borrow (a:as) (b:bs) = res : sub2 borrow2 as bs
      where
        (borrow2, res) = subDig borrow a b
    sub2 borrow (a:as) [] = sub2 borrow (a:as) (0:[])
    sub2 _ [] _ = [] -}

--subDig :: Int -> Int -> Int -> (Int, Int)
subDig borrow a b = subDig2 (a - b - borrow)
  where
    subDig2 d = subDig3 d (d `mod` 10)
    subDig3 d r = ((r-d) `quot` 10, r)

seven ds = seven2 0 ds
seven2 borrow (d:e:f:gs) = seven2 (b + borrow2) (res:f:gs)
  where
    (a, b) = double d
    (borrow2, res) = subDig borrow e a
seven2 borrow (d:e:[]) = finalApp d (e-borrow)
seven2 borrow (d:[]) = d - borrow*10

double d = ((2*d) `mod` 10, (2*d) `quot` 10)

finalApp m 0 = m
finalApp m n = n - 2*m

num2stream :: Int -> [Int]
num2stream = reverse . map digitToInt . show
sev = seven . num2stream

Istotą tego, jak to działa, jest to, że implementuje on algorytm odejmowania cyfra po cyfrze , ale wykorzystuje fakt, że każda liczba, która ma być odejmowana, to co najwyżej 2 cyfry, dzięki czemu możemy odjąć dowolną ich liczbę 1- lub dwucyfrowe liczby od głównej (a także do jedzenia najmniej znaczących cyfr).

Algorytm odejmowania to O (1) i zapisuje tylko bieżącą wartość „pożycz”. Zmieniłem to, aby dodać dodatkową cyfrę (0 lub 1), i zauważamy, że ta wartość pożyczki jest ograniczona (w zakresie [-2,2], więc do przechowywania tego potrzebujemy tylko 3 bity).

Pozostałe wartości przechowywane w pamięci to zmienne tymczasowe reprezentujące bieżącą 2-cyfrową liczbę do dodania, jedno spojrzenie w przyszłość w strumieniu i zastosowanie jednego kroku algorytmu odejmowania (tj. Wymaga dwóch cyfr i wartości pożyczonej i zwraca wartość jedna cyfra i nowa wartość pożyczki).

Na koniec na koniec przetwarza jednocześnie dwie ostatnie cyfry w strumieniu, aby zwrócić liczbę jednocyfrową zamiast listy cyfr.

Uwaga: sevfunkcja w wersji bez golfa będzie działać na Integerkonwertowaniu do postaci strumienia odwróconego.

azotawy
źródło
Chciałem, żeby premia była w normalnej kolejności cyfr. Ale nigdy tego nie powiedziałem, więc sprawiedliwie jest otrzymać bonus za odwróconą kolejność, mimo że jest to mniej zabawne. W każdym razie nawet odwrócona kolejność jest trudniejsza niż myślałem, więc jest wystarczająco zabawna!
anatolyg
@anatolyg: Dzięki! Nie jestem pewien, czy można wykonać implementację normalnego rzędu pojedynczego przejścia O (1) ... reguła zależy od najmniej znaczących liczb, więc teoretycznie bezpośrednie zastosowanie reguły jest niemożliwe, chyba że w odwrotnej kolejności. Jedyną rzeczą, o której mogę pomyśleć, jest znalezienie matematycznie równoważnej formy - na przykład Mod[18 - Quotient[n, 10] - 2*n, 21] - 18 + Quotient[n, 10]działa empirycznie dla n od 10 do 99, ale staje się bardziej skomplikowane, im więcej cyfr ma ...
nitro
Hmm, pomyślałem o tym i wydawało mi się, że może być jakiś sposób, utrzymując przednie 2 cyfry i stosując każdą kolejną cyfrę, ale mnożąc przez (-2) ^ n, aby uwzględnić to „filtrowanie” ... aż do można powiedzieć, iż nie ma możliwości, aby tę pracę bez zachowania wszystkich cyfr w pamięci i poświęcania o (1) „ności lub nawet o (n)” Ness ... Myślę, że normalny porządek jest zdecydowanie niemożliwe :(
azotu
1
Obawiam się, że musisz także liczyć bajty inicjału 0podczas wywoływania !, np. Jako sekcja (0!)(+ nowa linia), tj. +5 bajtów. Z drugiej strony możesz skrócić pierwszy do wzorca dopasowania !do p![d]=i p![d,e]=. Ponadto, stosowanie wzorca strzeże zamiast let: p!(d:e:f)|(b,a)<-quotRem(2*d)10,(q,r)<-h$e-a-p=(b+q)!(r:f).
nimi
1
@ nitit: Oh mam (0!)na myśli własną linię. (0!)to funkcja, którą podajesz jako odpowiedź. Jest 0to wymagane, ale nie ma nic wspólnego z danymi wejściowymi, więc nie możesz zlecić go dzwoniącemu. Oczywiście możesz również użyć f x=0!x, ale jest to dłuższe.
nimi
3

GNU dc, 20 15 bajtów

[10~2*-d70<F]sF

To określa moje pierwsze (w ogóle) funkcję DC F. Pobiera dane wejściowe na szczycie stosu i pozostawia jego wynik na szczycie stosu. Przykładowe użycie:

36893488147419103232
lFxp
32
Toby Speight
źródło
2

Mathematica, 47 44 bajtów

If[#>70,#0[{1,-2}.{⌊#/10⌋,#~Mod~10}],#]&

Proste podejście rekurencyjne. Prawdopodobnie mógłby być dalej golfem.

LegionMammal978
źródło
#0[{1,-2}.QuotientRemainder[#,10]]zapisuje bajt.
njpipeorgan
2

R, 43 bajty

x=scan();while(x>70)x=floor(x/10)-x%%10*2;x

Wyjaśnienie:

x=scan()                                      # Takes input as a double
        ;                                     # Next line
         while(x>70)                          # While-loop that runs as long x > 70
                      floor(x/10)             # Divide x by 10 and round that down
                                 -x%%10*2     # Substract twice the last integer
                    x=                        # Update x
                                         ;    # Next line once x <= 70
                                          x   # Print x

Przykładowe przebiegi:

> x=scan();while(x>70)x=floor(x/10)-x%%10*2;x
1: 9999
2: 
Read 1 item
[1] -3

> x=scan();while(x>70)x=floor(x/10)-x%%10*2;x
1: 32767
2: 
Read 1 item
[1] 28
Później
źródło
1

JavaScript ES6, 38 bajtów

a=i=>i>70?a(Math.floor(i/10)-i%10*2):i

Zawieszenia 36893488147419103232i używanie ~~(1/10)również się nie powiedzie700168844221

Test:

a=i=>i>70?a(Math.floor(i/10)-i%10*2):i
O.textContent = O.textContent.replace(/(-?\d+) +(-?\d+)/g, (_,i,o) =>
  _+": "+(a(+i)==o?"OK":"Fail")
);
<pre id=O>1                       1
10                      10
100                     10
13                      13
42                      42
2016                    0
9                       9
99                      -9
9999                    -3
12345                   3
700168844221            70
36893488147419103232    32</pre>

andlrc
źródło
Dostaję dwa Fails ... 70 i 32
Conor O'Brien
@ CᴏɴᴏʀO'Bʀɪᴇɴ Tak, wciąż zastanawiam się, dlaczego ...
andlrc
Ponieważ typ liczbowy JavaScript nie obsługuje przynajmniej ostatniego przypadku.
Conor O'Brien
1
f=n=>n>70?f((n-n%10*21)/10):njest krótszą wersją, ale nadal działa tylko dla maksymalnie 2**56.
Neil
@Neil zobacz moją odpowiedź na dowolną precyzję i bardzo proszę, graj w golfa.
Patrick Roberts,
1

Mathematica, 33 bajty

#//.a_/;a>70:>⌊a/10⌋-2a~Mod~10&

Przypadek testowy

%[9999]
(* -3 *)
njpipeorgan
źródło
1

Perl 5, 47 46 bajtów

Musiałem użyć bigintdo ostatniego przypadku testowego. (Zwraca 20 bez)

use bigint;$_=<>;while($_>9){$_-=2*chop;}print

Nie jestem pewien, czy jest to kandydat na premię, więc nie wziąłem tego pod uwagę. (Myślę, że tak, ale tak naprawdę nie jestem przyzwyczajony do koncepcji)

Wypróbuj tutaj!

Paul Picard
źródło
1

ES6, 108 bajtów

f=(s,n=0)=>s>1e9?f(s.slice(0,-1),((1+s.slice(-1)-n%10)%10*21+n-s.slice(-1))/10):s>9?f(((s-=n)-s%10*21)/10):s

Działa dla 2²⁵⁷ i 1000000000000000000001, ale przydałby się dalszy golf.

Neil
źródło
@PatrickRoberts Ups, nadzór przy ponownym formatowaniu zgłoszenia.
Neil
1

JavaScript ES6, 140 142 bajtów

f=s=>s>9?eval("t=s.replace(/.$/,'-$&*2');for(i=-1;0>(n=eval(u=t[c='slice'](i-4)))&&u!=t;i--);n<0?n:f(t[c](0,i-4)+('0'.repeat(-i)+n)[c](i))"):s

Jest to prawdziwa matematyka o dowolnej precyzji, działa nawet na największym przypadku testowym.

Ta funkcja rekurencyjnie usuwa ostatnią cyfrę z łańcucha, a następnie odejmuje 2 * ostatnią cyfrę od pozostałego łańcucha numerycznego, iteracyjnie zwiększając liczbę cyfr, które mają zostać zastosowane do minuend, aż różnica będzie dodatnia. Następnie dołącza tę różnicę do końca łańcucha za pomocą odpowiednio wypełnionych znaków 0s i wywołuje się rekurencyjnie, dopóki jej wartość liczbowa nie będzie mniejsza lub równa 9.

  • Grał w golfa 7 bajtów dzięki @Neil (tak, wiem, że zyskałem 2 bajty, ale naprawiłem kilka błędów, które powodowały zawieszanie się funkcji lub zwracanie błędnych danych wyjściowych w niektórych przypadkach).

f=s=>s>9?eval("t=s.replace(/.$/,'-$&*2');for(i=-1;0>(n=eval(u=t[c='slice'](i-4)))&&u!=t;i--);n<0?n:f(t[c](0,i-4)+('0'.repeat(-i)+n)[c](i))"):s;[['1',1],['10',1],['100',1],['13',-5],['42',0],['2016',0],['9',9],['99',-9],['9999',-3],['12345',3],['700168844221',7],['36893488147419103232',-1],['231584178474632390847141970017375815706539969331281128078915168015826259279872',8]].map(a=>document.write(`<pre>${f(a[0])==a[1]?'PASS':'FAIL'} ${a[0]}=>${a[1]}</pre>`))

Patrick Roberts
źródło
Fajnie, ale może nie działać 1000000000000000000001.
Neil,
1
Spróbować s.replace(/.$/,'-$&*2'). Niestety nie mam żadnych oczywistych pomysłów na resztę.
Neil
1

C #, 111 104 bajtów

int d(int n){var s=""+n;return n<71?n:d(int.Parse(s.Remove(s.Length-1))-int.Parse(""+s[s.Length-1])*2);}
TheLethalCoder
źródło
1

Brain-Flak , 368 360 bajtów

Wypróbuj online!

([([({})]<(())>)](<>)){({}())<>}{}<>{}{}<>(({})){{}{}<>(<(())>)}{}({}<>){{}(({}))(<((()()()()()){}<>)>)<>{({}[()])<>(({}()[({})])){{}(<({}({}))>)}{}<>}{}<>([([([(({}<{}><>)<([{}]{})(<((()()()()()){}(<>))>)<>{({}[()])<>(({}()[({}<({}())>)])){{}(<({}({}<({}[()])>))>)}{}<>}{}<>{}{}({}<>)>){}]{})]<(())>)(<>)]){({}())<>}{}<>{}{}<>(({})){{}{}<>(<(())>)}{}({}<>)}{}

Wyjaśnienie

Aby rozpocząć, cały kod znajduje się w pętli, która działa, dopóki górna część stosu nie będzie mniejsza niż zero:

([([({})]<(())>)](<>)){({}())<>}{}<>{}{}<>(({})){{}{}<>(<(())>)}{}({}<>)
{{}
 ...
 ([([({})]<(())>)](<>)){({}())<>}{}<>{}{}<>(({})){{}{}<>(<(())>)}{}({}<>)
}{}

Wewnątrz pętli uruchamiamy podzielny przez siedem algorytm:

Zduplikuj górę stosu

(({}))

Weź mod 10 na górze stosu (ostatnia cyfra)

(<((()()()()()){}<>)>)<>{({}[()])<>(({}()[({})])){{}(<({}({}))>)}{}<>}{}<>({}<{}><>)

To trochę bałagan, ale robi resztę algorytmu, który mógłbym wyjaśnić później, ale nie pamiętam, jak to działa:

([(({})<([{}]{})(<((()()()()()){}(<>))>)<>{({}[()])<>(({}()[({}<({}())>)])){{}(<({}({}<({}[()])>))>)}{}<>}{}<>{}{}({}<>)>){}]{})
Kreator pszenicy
źródło
1

C, 56 bajtów - 75% = 14

Chociaż nie podaje to dokładnie takich samych liczb jak przypadki testowe, spełnia on ducha pytania (i prawdopodobnie więcej). Poprawnie identyfikuje dokładne wielokrotności 7 i podaje dokładną resztę dla innych liczb (ponieważ nigdy nie używa liczb ujemnych).

n;f(char*c){for(n=0;*c;)n-=n>6?7:'0'-n-n-*c++;return n;}

W algorytmie nie ma mnożenia ani dzielenia, tylko dodawanie i odejmowanie, a cyfry są przetwarzane w jednym przejściu od lewej do prawej. Działa w następujący sposób, zaczynając od 0 w akumulatorze:

  1. Odejmij 7, jeśli to konieczne, i ponownie, jeśli to konieczne
  2. Pomnóż bieżącą sumę przez trzy i dodaj następną cyfrę

Krok „pomnóż przez trzy” jest zapisywany jako n-=-n-nzapisanie bajtu i uniknięcie operatora mnożenia.

Kiedy osiągniemy koniec, nie odejmujemy siódemek, więc wynik będzie w zakresie 0-24; jeśli chcesz ścisłej moduł (0-7), zastępczego *cze *c||n>6w forwarunku pętli.

Kwalifikuje się do ulepszonego bonusu, ponieważ to

  • obsługuje liczby całkowite o dowolnej dokładności
  • wykonuje tylko jeden przebieg na wejściu, w kolejności od lewej do prawej
  • ma złożoność przestrzenną O (1)
  • ma złożoność czasową O (n).

Program testowy i wyniki

#include <stdio.h>
int main(int argc, char **argv) {
    while (*++argv)
        printf("%s -> %d\n", *argv, f(*argv));
    return 0;
}
540 -> 15
541 -> 16
542 -> 17
543 -> 18
544 -> 19
545 -> 20
546 -> 21
547 -> 22
548 -> 23
549 -> 24
550 -> 18
99 -> 15
999 -> 12
12345 -> 11
32767 -> 7
700168844221 -> 7
36893488147419103232 -> 11
231584178474632390847141970017375815706539969331281128078915168015826259279872 -> 11

Alternatywna wersja

Oto jedna z nich, która powtarza się (będziesz chciał włączyć optymalizacje kompilatora, aby wykonać transformację wywołania ogona lub możesz przepełnić swój stos; użyłem gcc -std=c89 -O3):

f(c,n)char*c;{return n>6?f(c,n-7):*c?f(c+1,n+n+n+*c-'0'):n;}

Nazwij to z „0” jako drugim argumentem.

Obie wersje obliczają pozostałą liczbę siedmiu modułów z liczby 60 000 cyfr w czasie poniżej 50 milisekund na moim komputerze.

Toby Speight
źródło
Dzięki za bonus - to sprawia, że ​​C staje się tak konkurencyjny! Obecnie pokonany tylko przez Jelly (11) i Pyth (13). :-)
Toby Speight
1

PHP, 50 bajtów

for($n=$argv[1];$n>9;)$n=$n/10|0-2*($n%10);echo$n;

wykorzystuje alternatywne wyjście; działa doPHP_INT_MAX


wersja łańcuchowa, działa na dowolną (dodatnią) liczbę (64 bajty):

for($n=$argv[1];$n>9;)$n=substr($n,0,-1)-2*substr($n,-1);echo$n;
Tytus
źródło
0

Java, 133 bajty

int d(int n){String s=""+n;return n<71?n:d(Integer.parseInt(s.replaceFirst(".$",""))-Integer.parseInt(""+s.charAt(s.length()-1))*2);}

Nienawidzę, jak gadatliwy Integer.parseIntjest. Nie golfowany:

static int div(int n) {
    if (n <= 70) {
        return n;
    } else {
        String num = ("" + n);
        int last = Integer.parseInt("" + num.charAt(num.length() - 1));
        int k = Integer.parseInt(num.replaceFirst(".$", "")) - last * 2;
        return div(k);
    }
}
Justin
źródło