Implementieren Sie die Divisibility-by-7-Regel

25

So überprüfen Sie, ob eine Dezimalzahl durch 7 teilbar ist:

Löschen Sie die letzte Ziffer. Multipliziere es mit 2 und subtrahiere von dem, was übrig ist. Wenn das Ergebnis durch 7 teilbar ist, ist die ursprüngliche Zahl durch 7 teilbar.

(auch zB hier beschrieben )

Diese Regel eignet sich für die manuelle Teilbarkeitsprüfung. Beispielsweise:

Ist 2016 durch 7 teilbar?

Subtrahieren 6*2von 201; wir bekommen 189. Ist das durch 7 teilbar? Um dies zu überprüfen, wenden wir die Regel erneut an.

Subtrahieren 9*2von 18; wir bekommen 0. Deshalb ist 2016 durch 7 teilbar.

Bei dieser Herausforderung sollten Sie diese Regel anwenden, bis der Teilbarkeitsstatus offensichtlich ist , d. H., Die Anzahl ist nicht größer als 70 (Einzelheiten siehe unten). Machen Sie eine Funktion oder ein volles Programm.

Eingabe : eine positive ganze Zahl; Ihr Code sollte Eingaben bis zu 32767 unterstützen (die Unterstützung von Ganzzahlen mit beliebiger Genauigkeit ist ein Bonus; siehe unten).

Ausgabe : eine ganze Zahl (möglicherweise negativ), nicht größer als 70, die das Ergebnis der null- oder mehrmaligen Anwendung der Teilbarkeitsregel durch 7 ist.

Testfälle:

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

Wenn zwei mögliche Ausgaben angegeben sind, ist jedes Ergebnis korrekt: Die zweite entspricht der erneuten Anwendung der Regel. Es ist verboten, die Regel auf eine einstellige Zahl anzuwenden: Wenn Sie die Ziffer löschen, bleibt nichts (nicht 0) übrig.


Bonus : Wenn Ihr Algorithmus

wo nist die Anzahl der Nachkommastellen:

Subtrahieren Sie 50% von der Byteanzahl Ihres Codes.

Echter Bonus :

Wenn Ihr Algorithmus die Eingabe ausgehend von der höchstwertigen Ziffer in normaler Richtung liest, subtrahieren Sie 50% erneut - Ihre Punktzahl beträgt 25% Ihrer Byteanzahl (es scheint möglich, aber ich bin mir nicht ganz sicher).

anatolyg
quelle
1
@DenkerAffe Es ist akzeptabel, die Eingabe so wie sie ist zurückzugeben. Ich habe den Testfall von input = 10 aktualisiert, um dies widerzuspiegeln. das war die idee von anfang an.
Anatolyg
4
Ich würde diese Regel nicht anwenden wollen 1000000000000000000001.
Neil
1
Aber was ist, wenn in Ihrer Sprache long longs oder ein gleichwertiger Typ integriert ist?
SuperJedi224
1
Was ich gesagt habe war, dass es sich bei einigen Implementierungen um eine 128-Bit-Ganzzahl handelt, die mehr als groß genug für diesen letzten Testfall ist.
SuperJedi224
7
-1. Nicht alle Sprachen unterstützen eine beliebige Genauigkeit.
März

Antworten:

23

Golfscript, 27 22 Bytes

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

Sie können es folgendermaßen verwenden:

1000f

Erläuterung

{.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 Bytes gespart dank Dennis!

Dica
quelle
1
Willkommen bei Programming Puzzles und Code Golf. Dies ist eine gute Antwort. Sie können sie jedoch verbessern, indem Sie eine Code-Aufschlüsselung und eine Erklärung wie in den obigen Fragen hinzufügen. Um auf diesen Kommentar zu antworten, geben Sie @wizzwizz4( @dann meinen Benutzernamen) am Anfang (oder an einer beliebigen Stelle in) eines Kommentars ein.
wizzwizz4
1
@ wizzwizz4 Besser? Ich bin mir nicht sicher, ob ich verstehe, was Sie unter "Code-Aufschlüsselung" verstehen (kein Muttersprachler, sorry)
Dica
8
Ich glaube, dass er mit "Codezusammenbruch" eine Erklärung meinte, die Sie hinzugefügt haben. Dies ist in der Tat eine sehr schöne erste Antwort. Willkommen auf der Seite!
Alex A.
1
Sie können das {...}{}ifTeil wie {...}*folgt umschreiben: Dabei wird der Codeblock je nach dem von gedrückten Wert nur einmal auf Null gesetzt >. Außerdem sind wir eine weitere Iteration (so ersetzt ausführen darf 70mit 9speichert ein Byte), und ich glaube nicht , dass Sie den Block mit Pop benötigen ;.
Dennis
3
@Dica, dies ist eine erste Antwort, die gut genug ist, um über 12 Stimmen für eine Frage mit nur 624 Ansichten zu erhalten und von zwei Moderatoren gelobt zu werden. Wenn Sie so weitermachen, werden Sie Dennis bald überholen!
wizzwizz4
13

Haskell, 35 Bytes

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

Anwendungsbeispiel: until(<71)(\n->div n 10-2*mod n 10) 36893488147419103232-> 32.

Es gibt nicht viel zu erklären, es ist eine direkte Implementierung des Algorithmus.

nimi
quelle
9

Jelly, 11 Bytes

d⁵Uḅ-2µ>9$¿

Probieren Sie es online!

Wie es funktioniert

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
quelle
Und wie immer gewinnt Jelly. Dennis, wie viele Bytes würde es brauchen, um einen Jelly-Interpreter in Jelly zu implementieren?
Bálint
6

Python 2, 38 Bytes

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

Probieren Sie es hier aus !

Einfacher rekursiver Ansatz. Gibt x aus, wenn <70 andernfalls die Teilungsregel anwendet, und ruft sich selbst mit dem Ergebnis auf.

Denker
quelle
Sie brauchen keinen Platz nach dem)
Maltysen
@Maltysen Stimmt. Copy hat den falschen eingefügt, danke für den Hinweis!
Denker
2
Das Wenn ist zu ausführlich. f=lambda x:x*(x<70)or f(x/10-x%10*2)
Siehe auch
1
@Seeq Netter Trick, danke! Dies sollte theoretisch funktionieren, aber es erreicht die maximale Rekursionstiefe mit 2016 als Eingabe, während meine Version dies nicht tut. Irgendeine Idee warum?
Denker
Ah, richtig, das habe ich nicht bedacht. Dieser Trick gilt x*(x<70) != 0als Endbedingung. Wenn x - wie bei 2016 - den Wert 0 annimmt, tritt die Endebedingung niemals ein.
Siehe auch
6

Pyth, 13 Bytes

.W>H9-/ZTyeZQ

Probieren Sie es online aus: Demo oder Test Suite

Dadurch werden alle alternativen Antworten gedruckt.

Erläuterung:

.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
quelle
5

Julia, 27 26 Bytes

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

Dies ist eine rekursive Funktion, die eine Ganzzahl akzeptiert und a zurückgibt BigInt. Wenn die Eingabe wie im letzten Beispiel eine große Zahl ist, analysiert Julia sie als a BigInt, sodass keine manuelle Konvertierung erforderlich ist.

Der Ansatz ist nur eine einfache Implementierung des Algorithmus. Es werden die alternativen Ausgänge erzeugt. Wenn Sie den Modul durch 10 dividieren, erhalten Sie die letzte Ziffer, und der Quotient aus der Ganzzahldivision durch 10 ergibt alles außer der letzten Ziffer.

Dank Dennis ein Byte gespart!

Alex A.
quelle
Wir dürfen noch eine Iteration durchführen, also spart das Ersetzen 70durch 9ein Byte.
Dennis
@ Tennis Guter Anruf, danke!
Alex A.
4

Pyth, 17 Bytes

L?<b70by-/bT*%bT2

Probieren Sie es hier aus!

Gleicher rekursiver Ansatz wie in meiner Python-Antwort . Definiert eine Lambda , ydie wie folgt aufgerufen: y12345.
Der Bytezähler im Online-Interpreter zeigt 19 Bytes an, weil ich den Lambda-Aufruf hinzugefügt habe. Sie können ihn also einfach ausprobieren, indem Sie auf die Schaltfläche "Ausführen" klicken.

Erläuterung

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
quelle
Sie haben einen Tippfehler in Ihrer Erklärung, 17 sollte 70 sein: P
FryAmTheEggman
4

CJam - 19 Bytes

Do-While-Version:

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

Probieren Sie es online oder während Version 1:

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

Probieren Sie es online oder während Version 2:

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

Probieren Sie es online aus .

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
quelle
3

Oracle SQL 11.2, 116 Bytes

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;

Nicht golfen

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
quelle
3

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

O (1) Raum, O (n) Zeit, 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!)

Verwenden Sie diese Option 0![6,1,0,2], um die Regel auf 2016 anzuwenden, dh übergeben Sie eine Zahl in Stream-Form mit der niedrigsten Ziffer zuerst. Auf diese Weise wird die Zahl Ziffer für Ziffer weitergereicht, wobei die Regel mit der Komplexität von O (1) Leerzeichen angewendet wird.

Der ungolfed Code ist hier:

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

Der Kern der Funktionsweise besteht darin, dass ein ziffernweiser Subtraktionsalgorithmus implementiert wird , wobei jedoch die Tatsache ausgenutzt wird, dass jede zu subtrahierende Zahl höchstens 2-stellig ist. Daher können wir eine beliebige Menge dieser 1 -stelligen Zahlen subtrahieren. oder-2 Ziffern von der Hauptziffer (sowie die niedrigstwertigen Ziffern).

Der Subtraktionsalgorithmus ist O (1) und speichert nur den aktuellen Ausleihwert. Ich habe dies geändert, um die zusätzliche Ziffer (entweder 0 oder 1) hinzuzufügen, und wir stellen fest, dass dieser Ausleihwert begrenzt ist (innerhalb des Bereichs [-2,2], sodass wir nur 3 Bits benötigen, um dies zu speichern).

Die anderen im Speicher abgelegten Werte sind temporäre Variablen, die die aktuell zu addierende zweistellige Zahl, eine einzelne Vorausschau im Datenstrom und einen Schritt des Subtraktionsalgorithmus darstellen (dh es werden zwei Ziffern und ein Ausleihwert verwendet und zurückgegeben) eine Ziffer und ein neuer Ausleihwert).

Am Ende werden die letzten beiden Ziffern des Streams gleichzeitig verarbeitet, um eine einstellige Zahl anstelle einer Ziffernliste zurückzugeben.

NB Die sevFunktion in der ungolfed Version wird auf einem funktionieren Integerund es in die umgekehrte Stromform umwandeln.

nitros
quelle
Ich wollte, dass der Bonus für die normale Ziffernfolge gilt. Aber ich habe es nie gesagt, also ist es fair, den Bonus für die umgekehrte Reihenfolge zu erhalten, obwohl es weniger Spaß macht. Auf jeden Fall ist sogar die umgekehrte Reihenfolge schwieriger als ich dachte, also macht es Spaß genug!
Anatolyg
@anatolyg: Danke! Ich bin mir nicht sicher, ob es möglich ist, eine O (1) -Implementierung in einem Durchgang in der normalen Reihenfolge durchzuführen ... Die Regel hängt von den niedrigstwertigen Zahlen ab, sodass theoretisch eine direkte Anwendung der Regel nur in umgekehrter Reihenfolge möglich ist. Das einzige, was ich denken kann , ist durch eine mathematisch äquivalente Form zu finden - zum Beispiel Mod[18 - Quotient[n, 10] - 2*n, 21] - 18 + Quotient[n, 10]arbeitet empirisch für n zwischen 10 und 99, wird aber mehr die mehr Stellen komplizieren n ...
nitrosen
Hmm, ich habe darüber nachgedacht und es schien, als gäbe es einen Weg, die vorderen 2 Ziffern beizubehalten und jede nachfolgende Ziffer anzuwenden, aber mit (-2) ^ n zu multiplizieren, um zu berücksichtigen, dass sie 'durchgefiltert' werden ... so weit ich komme Ich kann sagen, dass es keine Möglichkeit gibt, diese Arbeit zu machen, ohne alle Ziffern im Speicher zu behalten und die O (1) - oder sogar die O (n) -Ness zu opfern ... Ich denke, die normale Reihenfolge ist definitiv unmöglich :(
Nitrous
1
Ich fürchte, Sie müssen auch 0beim Aufruf die Bytes der Initialen zählen !, z. B. als Abschnitt (0!)(+ eine neue Zeile), dh +5 Bytes. Auf der anderen Seite können Sie die ersten zu Musterübereinstimmungen von !bis p![d]=und kürzen p![d,e]=. Außerdem schützt Verwendungsmuster statt der let: p!(d:e:f)|(b,a)<-quotRem(2*d)10,(q,r)<-h$e-a-p=(b+q)!(r:f).
Nimi
1
@nitrous: Oh, ich erwähne es (0!)auf einer eigenen Linie. (0!)ist die Funktion, die Sie als Antwort geben. Das 0ist erforderlich, hat aber nichts mit der Eingabe zu tun, sodass Sie es nicht an den Aufrufer auslagern können. Das könnte man natürlich auch gebrauchen f x=0!x, aber das ist länger.
Nimi
3

GNU dc, 20 15 Bytes

[10~2*-d70<F]sF

Dies definiert meine erste (überhaupt) Gleichstromfunktion F. Es nimmt die Eingabe oben auf dem Stapel entgegen und belässt die Ausgabe oben auf dem Stapel. Anwendungsbeispiel:

36893488147419103232
lFxp
32
Toby Speight
quelle
2

Mathematica, 47 44 Bytes

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

Einfacher rekursiver Ansatz. Könnte wahrscheinlich weiter golfen werden.

LegionMammal978
quelle
#0[{1,-2}.QuotientRemainder[#,10]]Speichert ein Byte.
njpipeorgan
2

R, 43 Bytes

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

Erläuterung:

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

Probeläufe:

> 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
Später
quelle
1

JavaScript ES6, 38 Byte

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

Fehler mit 36893488147419103232und mit ~~(1/10)schlagen ebenfalls fehl700168844221

Prüfung:

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>

undlrc
quelle
Ich bekomme zwei Fail... 70 und 32
Conor O'Brien
@ CᴏɴᴏʀO'Bʀɪᴇɴ Ja, ich frage mich immer noch, warum ...
andlrc
Weil der Nummerntyp von JavaScript zumindest den letzten Fall nicht behandelt.
Conor O'Brien
1
f=n=>n>70?f((n-n%10*21)/10):nist eine kürzere Version, funktioniert aber immer noch nur für bis zu 2**56.
Neil
@Neil sehen meine Antwort für willkürliche Präzision, und fühlen Sie sich bitte frei, Golf, sehr geschätzt.
Patrick Roberts
1

Mathematica, 33 Bytes

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

Testfall

%[9999]
(* -3 *)
njpipeorgan
quelle
1

Perl 5, 47 46 Bytes

Musste bigintfür den letzten Testfall verwenden. (Es gibt 20 ohne)

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

Ich bin mir nicht sicher, ob es ein Kandidat für den Bonus ist, deshalb habe ich ihn nicht berücksichtigt. (Ich glaube schon, aber ich bin nicht wirklich an die Konzepte gewöhnt)

Probieren Sie es hier aus!

Paul Picard
quelle
1

ES6, 108 Bytes

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

Funktioniert für 2²⁵⁷ und 1000000000000000000001, könnte aber weiteres Golfen gebrauchen.

Neil
quelle
@PatrickRoberts Ups, Versehen beim Neuformatieren für die Einreichung.
Neil
1

JavaScript ES6, 140 142 Bytes

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

Dies ist eine echte Mathematik mit willkürlicher Genauigkeit, die sogar für den größten Testfall geeignet ist.

Diese Funktion entfernt rekursiv die letzte Ziffer aus der Zeichenfolge und subtrahiert dann 2 * die letzte Ziffer von der verbleibenden numerischen Zeichenfolge, indem die Anzahl der Stellen, die auf das Minuend angewendet werden sollen, iterativ erhöht wird, bis die Differenz positiv ist. Dann hängt er diese Differenz mit entsprechend aufgefüllten 0s an das Ende der Zeichenfolge an und ruft sich rekursiv auf, bis sein numerischer Wert kleiner oder gleich ist9 .

  • Dank @Neil 7 Bytes Golf gespielt (ja, ich weiß, dass ich 2 Bytes gewonnen habe, aber ich habe ein paar Fehler behoben, die dazu geführt haben, dass die Funktion für einige Fälle eingefroren ist oder eine falsche Ausgabe zurückgegeben hat).

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
quelle
Schön, aber es könnte nicht funktionieren 1000000000000000000001.
Neil
1
Versuchen Sie es s.replace(/.$/,'-$&*2'). Ich habe keine offensichtlichen Ideen für den Rest, aber es tut mir leid.
Neil
1

C #, 111 104 Bytes

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
quelle
1

Brain-Flak , 368 360 Bytes

Probieren Sie es online!

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

Erläuterung

Zu Beginn befindet sich der gesamte Code in einer Schleife, die so lange ausgeführt wird, bis der obere Rand des Stapels kleiner als Null ist:

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

Innerhalb der Schleife führen wir den durch sieben teilbaren Algorithmus aus:

Duplizieren Sie die Oberseite des Stapels

(({}))

Nimm den Mod 10 von oben (letzte Ziffer)

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

Das ist ein bisschen chaotisch, aber es erledigt den Rest des Algorithmus. Vielleicht erkläre ich es später, aber ich erinnere mich nicht ganz, wie es funktioniert:

([(({})<([{}]{})(<((()()()()()){}(<>))>)<>{({}[()])<>(({}()[({}<({}())>)])){{}(<({}({}<({}[()])>))>)}{}<>}{}<>{}{}({}<>)>){}]{})
Weizen-Assistent
quelle
1

C, 56 Bytes - 75% = 14

Dies gibt zwar nicht genau die gleichen Zahlen wie die Testfälle, erfüllt jedoch den Grundgedanken der Frage (und möglicherweise mehr). Es identifiziert die exakten Vielfachen von 7 korrekt und gibt den exakten Rest für andere Zahlen an (da keine negativen Zahlen verwendet werden).

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

Es gibt keine Multiplikation oder Division im Algorithmus, nur Addition und Subtraktion, und Ziffern werden in einem einzigen Durchgang von links nach rechts verarbeitet. Es funktioniert wie folgt, beginnend mit 0 im Akkumulator:

  1. Subtrahieren Sie 7, falls erforderlich, und erneut, falls immer noch erforderlich
  2. Multiplizieren Sie die laufende Summe mit drei und addieren Sie die nächste Ziffer

Der Schritt "Multiplizieren mit drei" wird als geschrieben n-=-n-n , um ein Byte zu sparen und den Multiplikationsoperator zu vermeiden.

Wenn wir das Ende erreichen, subtrahieren wir keine sieben, sodass das Ergebnis im Bereich von 0 bis 24 liegt. Wenn Sie einen Strengemodul (0-7) wünschen, ersetzen Sie ihn *cdurch *c||n>6infor Schleifenbedingung.

Es qualifiziert sich für den erhöhten Bonus, weil es

  • unterstützt Ganzzahlen mit beliebiger Genauigkeit
  • Führt nur einen Durchlauf der Eingabe in der Reihenfolge von links nach rechts durch
  • hat Raumkomplexität O (1)
  • hat Zeitkomplexität O (n).

Testprogramm und Ergebnisse

#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

Alternative Version

Hier ist eine, die wiederkehrt (Sie möchten Compiler-Optimierungen für die Tail-Call-Transformation aktivieren, oder Sie könnten Ihren Stack überlaufen lassen; ich habe sie verwendet 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;}

Nennen Sie es mit '0' als zweites Argument.

Beide Versionen berechnen den Rest-Modulo-Sieben einer 60.000-stelligen Zahl in weniger als 50 Millisekunden auf meinem Computer.

Toby Speight
quelle
Vielen Dank für den Bonus - es ist eine echte Veränderung für C, so wettbewerbsfähig zu werden! Derzeit nur von Jelly (11) und Pyth (13) geschlagen. :-)
Toby Speight
1

PHP, 50 Bytes

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

verwendet alternative Ausgabe; funktioniert bis zuPHP_INT_MAX


String-Version, funktioniert für jede (positive) Zahl (64 Bytes):

for($n=$argv[1];$n>9;)$n=substr($n,0,-1)-2*substr($n,-1);echo$n;
Titus
quelle
0

Java, 133 Bytes

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

Ich hasse es, wie wortreich es Integer.parseIntist. Ungolfed:

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
quelle