Prueba de divisibilidad impaciente

Su tarea es escribir un programa o función que determine si un número es divisible por otro. El problema es que debe dar una respuesta lo antes posible , incluso si no se han dado todos los dígitos del número.

Su programa debe tomar un número entero D ≥ 2 y luego una serie de dígitos como entrada. Estos representan los dígitos de otro número entero N ≥ 1, comenzando en el dígito menos significativo. En el primer punto que N sea debe o no debe ser divisible por D , el programa debería devolver la respuesta apropiada y salida. Si se alcanza el final de la entrada, se debe de salida si el total N es divisible por D .

Aquí hay una lista de formatos de entrada aceptables para N (deje un comentario si cree que se debe permitir algo que no está incluido):

Entrada estándar : los dígitos se dan en líneas separadas; el final de la entrada es EOF o un valor especial; salir significa que la función regresa o el programa sale.
Entrada analógica : mediante, por ejemplo, pulsaciones de teclas o diez botones que representan cada dígito; El final de la entrada es un valor especial; salir significa que la función regresa o el programa sale.
Función con estado global : llamada repetidamente con dígitos sucesivos; El final de la entrada es un valor especial; salir significa que la función devuelve un valor no nulo. Tenga en cuenta que si usa el estado global, debe borrarse después de que se devuelve un valor o restablecerse de otra manera para que la función funcione varias veces .
Función curry : devuelve otra función que se llamará con el siguiente dígito o un valor; El final de la entrada es un valor especial o se llama a la función sin argumento; salir significa que la función devuelve una respuesta en lugar de otra función.
Solicitud de GUI o similar : se muestra repetidamente; el final de la entrada es "cancelar" o equivalente, o un valor especial; salir significa que las indicaciones dejan de aparecer.
Función de iterador : la entrada es un objeto o función con estado que devuelve el siguiente dígito cuando se llama, el final de la entrada es una excepción o un valor especial; salir significa que el iterador deja de ser llamado.

La entrada para D y la salida pueden realizarse a través de cualquier método estándar aceptable .

Casos de prueba:

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 Pomo de la puerta
fuente

Creo que debemos suponer que se dará un dígito cada vez que nuestra solución solicite información, ¿verdad? Y, debería ser un programa completo, ya que esta es la forma objetiva de garantizar que la entrada se dé dígito a dígito, ¿no? (El desafío dice "programa o función", hmm ...)

Erik the Outgolfer

@EriktheOutgolfer El formato de entrada se explica en detalle en la lista con viñetas de la pregunta.

Pomo de la puerta

Estaba pensando en cuán objetivos pueden ser esos formatos ... Supongo que simplemente dejaré de hablar y comenzaré a resolver esto . :-)

Erik the Outgolfer

¿Tiene algo de malo simplemente tomar una lista como digitsentrada con un valor especial para EOF?

Jonathan Allan

@EriktheOutgolfer no si hay un valor EOF, a menos que haya entendido mal algo. Por ejemplo digamos que todo el valor es 132 y el divisor potencial es 4 a continuación, []y [2]de retorno que no sea nada falseo true(incluyendo la propia función etc ...), mientras que [2,3], [2,3,1]y [2,3,1,EOF]de retorno true. Me parece lo más cercano a la opción de estado global.

Jonathan Allan

Respuestas:

JavaScript (ES6), 70 bytes

Formato de entrada: función curry

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

Pruébalo en línea!

¿Cómo?

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

\begin{matrix} (1) & k \times 10^{norte} + q (modificación pag) \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^{norte} + q (modificación pag) = (metro pag + k) \times 10^{norte} + q (modificación pag) = (metro pag \times 10^{norte} (modificación pag)) + (k \times 10^{norte} + q (modificación pag)) (modificación pag) = 0 0 + (k \times 10^{norte} + q (modificación pag)) (modificación pag) = k \times 10^{norte} + q (modificación pag)

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

Comentado

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
fuente

Lote, 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)

Toma dcomo parámetro de línea de comando y lee dígitos de nen líneas separadas con -el marcador EOF. Salidas 1para divisible, 0si no. Explicación:

@set n=

Inicializar na la cadena vacía.

@set g=1

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

:l

Comience un ciclo de lectura de dígitos.

@set/ps=

Lee el siguiente dígito.

@if %s%==- goto g

Detener el procesamiento en EOF.

@set n=%s%%n%

Anteponer el siguiente dígito a n.

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

Actualice gahora que len(n)ha aumentado y calcule n%g.

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

Si rno es cero, entonces ddefinitivamente no se divide n, porque g, un factor de d, no lo hace. Si res cero, entonces solo sabemos sid divide nsi ges igual d, así que si no lo es, continúa el ciclo.

:g

Salga del ciclo de lectura de dígitos aquí en EOF.

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

Calcular y generar implícitamente el resultado.

Neil
fuente