Ungeduldiger Teilbarkeitstest

Ihre Aufgabe ist es, ein Programm oder eine Funktion zu schreiben, die bestimmt, ob eine Zahl durch eine andere teilbar ist. Der Haken ist, dass es so schnell wie möglich eine Antwort geben sollte , auch wenn nicht alle Ziffern der Nummer angegeben wurden.

Ihr Programm sollte eine ganze Zahl D ≥ 2 und dann eine Reihe von Ziffern als Eingabe annehmen . Diese repräsentieren die Ziffern einer anderen ganzen Zahl N ≥ 1, beginnend mit der niedrigstwertigen Ziffer. Beim ersten Punkt, an dem N durch D teilbar sein muss oder nicht , sollte Ihr Programm die entsprechende Antwort ausgeben und beenden . Wenn das Ende der Eingabe erreicht ist, sollte ausgegeben werden, ob das volle N durch D teilbar ist .

Hier ist eine Liste akzeptabler Eingabeformate für N (hinterlassen Sie einen Kommentar, wenn Sie der Meinung sind, dass etwas, das nicht enthalten ist, zulässig sein sollte):

Standardeingabe : Ziffern werden in separaten Zeilen angegeben; Ende der Eingabe ist EOF oder ein spezieller Wert; exit bedeutet, dass die Funktion zurückkehrt oder das Programm beendet wird.
Analogeingang : über z. B. Tastenanschläge oder zehn Tasten, die jede Ziffer darstellen; Das Eingabeende ist ein spezieller Wert. exit bedeutet, dass die Funktion zurückkehrt oder das Programm beendet wird.
Funktion mit globalem Status : wiederholt mit aufeinanderfolgenden Ziffern aufgerufen; Das Eingabeende ist ein spezieller Wert. exit bedeutet, dass die Funktion einen Wert ungleich null zurückgibt. Beachten Sie, dass , wenn Sie globalen Zustand zu verwenden, müssen sie gelöscht werden , nachdem ein Wert zurückgegeben oder auf andere Weise zurückgesetzt , so dass die Funktion mehrmals funktioniert .
Curry-Funktion : Gibt entweder eine andere Funktion zurück, die mit der nächsten Ziffer oder einem Wert aufgerufen werden soll. Das Eingabeende ist ein spezieller Wert oder der Aufruf der Funktion ohne Argument. exit bedeutet, dass die Funktion eine Antwort und keine andere Funktion zurückgibt.
GUI-Eingabeaufforderung oder ähnliches : wird wiederholt angezeigt; Ende der Eingabe ist "Abbruch" oder Äquivalent oder ein spezieller Wert; exit bedeutet, dass keine Eingabeaufforderungen mehr angezeigt werden.
Iteratorfunktion : input ist ein statusbehaftetes Objekt oder eine Funktion, die beim Aufruf die nächste Ziffer zurückgibt, end of input ist eine Ausnahme oder ein spezieller Wert; exit bedeutet, dass der Iterator nicht mehr aufgerufen wird.

Die Eingabe für D und die Ausgabe kann über jede akzeptable Standardmethode erfolgen .

Testfälle:

2;   6               => true
5;   6               => false
20;  0 3             => false
20;  0 4             => true
100; 1               => false
100; 0 0             => true
100; 0 2             => false
4;   2 4             => false
4;   2 5             => true
4;   2 [eof]         => false
4;   4 [eof]         => true
625; 5 5             => false
625; 5 7 2           => false
625; 5 7 3 6         => false
625; 5 7 3 4         => true
7;   9 3 4 [eof]     => false
7;   9 3 4 5 [eof]   => true
140; 0 3             => false
140; 0 4 5 [eof]     => false
140; 0 4 5 1 [eof]   => true
14;  4 5 1 4 [eof]   => false
14;  4 5 1 4 1 [eof] => true

code-golf number decision-problem number-theory division Türknauf
quelle

Ich denke, wir sollten davon ausgehen, dass jedes Mal, wenn unsere Lösung Eingaben anfordert, eine Ziffer vergeben wird, oder? Und es sollte ein vollständiges Programm sein, da dies der objektive Weg ist, um sicherzustellen, dass die Eingabe ziffernweise erfolgt, nicht wahr? (Die Herausforderung sagt "Programm oder Funktion", hmm ...)

Erik der Outgolfer

@EriktheOutgolfer Das Eingabeformat wird in der Aufzählung in der Frage ausführlich erläutert.

Türklinke

Ich habe nur darüber nachgedacht, wie objektiv diese Formate sein können ... Ich werde wohl einfach aufhören zu suchen und anfangen , dies tatsächlich zu lösen . :-)

Erik der Outgolfer

Ist etwas falsch daran, nur eine Liste als digitsEingabe mit einem speziellen Wert für EOF zu verwenden?

Jonathan Allan

@EriktheOutgolfer nicht, wenn es einen EOF-Wert gibt, es sei denn, ich habe etwas falsch verstanden. Zum Beispiel lassen Sie uns sagen , dass der ganze Wert 132 und das Potential Teiler 4 ist dann []und [2]Rückkehr etwas anderes als falseoder true(einschließlich der Funktion selbst etc ...) , während [2,3], [2,3,1]und [2,3,1,EOF]Rückkehr true. Es kommt mir der globalen Staatsoption sehr nahe.

Jonathan Allan

Antworten:

JavaScript (ES6), 70 Byte

Eingabeformat: Curry-Funktion

$-1$ $0$ $1$

p=>(q='',g=(d,t=k=z=!~d||(q=d+q,p))=>k--?g(d,t-=(k+q)%p<1):t?t-z&&g:1)

Probieren Sie es online!

Wie?

$p$ $q$ $n$ $0 \le k < p$

\begin{matrix} (1) & k \times 10^{n} + q (\mod p) \end{matrix}

$k\times 10^n+q \pmod p\tag{1}$

$x\ge p$ $m\ge 1$ $0 \le k < p$ $x=mp+k$

x \times 10^{n} + q (\mod p) = (m p + k) \times 10^{n} + q (\mod p) = (m p \times 10^{n} (\mod p)) + (k \times 10^{n} + q (\mod p)) (\mod p) = 0 + (k \times 10^{n} + q (\mod p)) (\mod p) = k \times 10^{n} + q (\mod p)

$x\times 10^n+q \pmod p=\\ (mp+k)\times 10^n+q \pmod p=\\ (mp\times 10^n \pmod p)+ (k\times 10^n+q \pmod p)\pmod p=\\ 0+(k\times 10^n+q \pmod p)\pmod p=\\ k\times 10^n+q \pmod p$

$(1)$ $0$ $0 \le k < p$ $0$ $k \ge p$

$(1)$ $0$ $0 \le k < p$

$(1)$ $q$

Kommentiert

p => (                       // p = divisor
  q = '',                    // q = dividend stored as a string, initially empty
  g = (                      // g() = curried function taking:
    d,                       //   d = next digit
    t =                      //   t = number of iterations yielding a non-zero value
    k =                      //   k = total number of iterations to process
    z =                      //   z = copy of k
      !~d ||                 //   if d == -1 (meaning EOF), use only 1 iteration
                             //   so that we simply test the current value of q
      (q = d + q, p)         //   otherwise, prepend d to q and use p iterations
  ) =>                       //
    k-- ?                    //   decrement k; if it was not equal to zero:
      g(                     //     do a recursive call to g():
        d,                   //       pass the current value of d (will be ignored anyway)
        t -= (k + q) % p < 1 //       test (k + q) % p and update t accordingly
      )                      //     end of recursive call
    :                        //   else:
      t ?                    //     if t is greater than 0:
        t - z && g           //       return 0 if t == z, or g otherwise
      :                      //     else:
        1                    //       return 1
)                            //

Arnauld
quelle

Batch, 177 169 Bytes

@set n=
@set g=1
:l
@set/ps=
@if %s%==- goto g
@set n=%s%%n%
@set/ae=%1/g,g*=2-e%%2,g*=1+4*!(e%%5),r=n%%g
@if %g% neq %1 if %r%==0 goto l
:g
@cmd/cset/a!(n%%%1)

Wird dals Befehlszeilenparameter verwendet und liest Ziffern nin separaten Zeilen mit -dem EOF-Marker. Ausgänge 1für teilbare,0 wenn nicht. Erläuterung:

@set n=

Initialisieren Sie nauf die leere Zeichenfolge.

@set g=1

g ist gcd(d, 10**len(n))

:l

Beginnen Sie mit dem Lesen einer Schleife.

@set/ps=

Lesen Sie die nächste Ziffer.

@if %s%==- goto g

Stoppen Sie die Verarbeitung bei EOF.

@set n=%s%%n%

Stellen Sie die nächste Ziffer vor n.

@set/ae=%1/g,g*=2-e%%2,g*=1+4*!(e%%5),r=n%%g

gJetzt aktualisieren , das len(n)hat zugenommen und kalkuliert n%g.

@if %g% neq %1 if %r%==0 goto l

Wenn rnicht Null ist, dann dteilt sich das definitiv nicht n, weil gein Faktor von ddies nicht tut. Wenn rNull ist, wissen wir nur, ob ddividiert wird, nwenn dies ggleich dist. Wenn dies nicht der Fall ist, setzen Sie die Schleife fort.

:g

Brechen Sie hier auf EOF aus der Ziffernleseschleife aus.

@cmd/cset/a!(n%%%1)

Berechnen Sie das Ergebnis und geben Sie es implizit aus.

Neil
quelle