14
\$\begingroup\$

Your task is to write a program or function that determines whether a number is divisible by another. The catch is that it should give an answer as soon as possible, even if not all digits of the number have been given.

Your program should take an integer D ≥ 2 and then a series of digits as input. These represent the digits of another integer N ≥ 1, starting at the least significant digit. At the first point that N either must or must not be divisble by D, your program should output the appropriate answer and exit. If the end of the input is reached, it should output whether the full N is divisible by D.

Here is a list of acceptable input formats for N (leave a comment if you think something that isn't included should be allowed):

  • Standard input: digits are given on separate lines; end of input is EOF or a special value; exit means that the function returns or the program exits.

  • Analog input: through e.g. keystrokes or ten buttons representing each digit; end of input is a special value; exit means that the function returns or the program exits.

  • Function with global state: called repeatedly with successive digits; end of input is a special value; exit means that the function returns a non-null value. Note that if you use global state, it must be cleared after a value is returned or otherwise reset such that the function works multiple times.

  • Curried function: returns either another function to be called with the next digit or a value; end of input is a special value or calling the function with no argument; exit means that the function returns an answer rather than another function.

  • GUI prompt or similar: displayed repeatedly; end of input is "cancel" or equivalent, or a special value; exit means that prompts stop appearing.

  • Iterator function: input is a stateful object or function that returns the next digit when called, end of input is an exception or special value; exit means that the iterator stops being called.

Input for D and the output can be through any acceptable standard method.

Test cases:

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
\$\endgroup\$
  • \$\begingroup\$ I think we should assume that one digit will be given every time our solution asks for input, right? And, it should be a full program, since this is the objective way to ensure that input is given digit by digit, no? (The challenge says "program or function", hmm...) \$\endgroup\$ – Erik the Outgolfer Sep 1 '18 at 21:47
  • 1
    \$\begingroup\$ @EriktheOutgolfer The input format is explained in detail in the bulleted list in the question. \$\endgroup\$ – Doorknob Sep 1 '18 at 21:50
  • 1
    \$\begingroup\$ I was just thinking about how objective can those formats be...I guess I'll just quit nitpicking and start actually solving this. :-) \$\endgroup\$ – Erik the Outgolfer Sep 1 '18 at 21:52
  • 1
    \$\begingroup\$ Is anything wrong with just taking a list as the digits input with a special value for EOF? \$\endgroup\$ – Jonathan Allan Sep 2 '18 at 9:48
  • 1
    \$\begingroup\$ @EriktheOutgolfer not if there is an EOF value, unless I've misunderstood something. For example let's say the whole value is 132 and the potential divisor is 4 then [] and [2] return anything other than false or true (including the function itself etc...) while [2,3], [2,3,1], and [2,3,1,EOF] return true. It strikes me as close to the global state option. \$\endgroup\$ – Jonathan Allan Sep 2 '18 at 11:44
8
\$\begingroup\$

JavaScript (ES6), 70 bytes

Input format: Curried function

A function that takes the divisor and returns a function that takes each digit or \$-1\$ for EOF. The second function returns either \$0\$ (false), \$1\$ (true) or itself (no answer).

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)

Try it online!

How?

Given a divisor \$p\$ and a dividend \$q\$ consisting of \$n\$ decimal digits, we compute the following expression for all \$0 \le k < p\$:

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

For any \$x\ge p\$ there exists \$m\ge 1\$ and \$0 \le k < p\$ such that \$x=mp+k\$, leading to:

$$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$$

Therefore, if \$(1)\$ is equal to \$0\$ for all \$0 \le k < p\$, it will also be equal to \$0\$ for any \$k \ge p\$ and the answer is true.

For the same reason, if \$(1)\$ is greater than \$0\$ for all \$0 \le k < p\$, the answer is false.

If the results of \$(1)\$ are mixed, we can't decide yet and need either more digits of \$q\$ or the EOF notification.

Commented

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
)                            //
\$\endgroup\$
2
\$\begingroup\$

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)

Takes d as a command-line parameter and reads digits of n on separate lines with - as the EOF marker. Outputs 1 for divisible, 0 if not. Explanation:

@set n=

Initialise n to the empty string.

@set g=1

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

:l

Begin a loop reading digits.

@set/ps=

Read the next digit.

@if %s%==- goto g

Stop processing at EOF.

@set n=%s%%n%

Prepend the next digit to n.

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

Update g now that len(n) has increased and calculate n%g.

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

If r is non-zero then the d definitely does not divide n, because g, a factor of d, does not. If r is zero then we only know whether d divides n if g equals d, so if it isn't, continue the loop.

:g

Break out of the digit-reading loop here on EOF.

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

Calculate and implicitly output the result.

\$\endgroup\$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.