Teste de divisibilidade impaciente

Sua tarefa é escrever um programa ou função que determine se um número é divisível por outro. O problema é que ele deve dar uma resposta o mais rápido possível , mesmo que nem todos os dígitos do número tenham sido fornecidos.

Seu programa deve ter um número inteiro D ≥ 2 e depois uma série de dígitos como entrada. Eles representam os dígitos de outro número inteiro N ≥ 1, iniciando no dígito menos significativo. No primeiro ponto que N quer deve ou não deve ser divisble por D , seu programa deve saída a resposta adequada e sair. Se a extremidade da entrada é alcançado, deve debitar se o completo N é divisível por D .

Aqui está uma lista de formatos de entrada aceitáveis para N (deixe um comentário se você acha que algo que não está incluído deve ser permitido):

Entrada padrão : os dígitos são dados em linhas separadas; final da entrada é EOF ou um valor especial; exit significa que a função retorna ou o programa sai.
Entrada analógica : através, por exemplo, de teclas ou dez botões representando cada dígito; fim da entrada é um valor especial; exit significa que a função retorna ou o programa sai.
Função com estado global : chamada repetidamente com dígitos sucessivos; fim da entrada é um valor especial; exit significa que a função retorna um valor não nulo. Observe que, se você usar o estado global, ele deverá ser limpo depois que um valor for retornado ou redefinido para que a função funcione várias vezes .
Função ao curry : retorna outra função a ser chamada com o próximo dígito ou um valor; fim da entrada é um valor especial ou chama a função sem argumento; exit significa que a função retorna uma resposta em vez de outra função.
Prompt da GUI ou similar : exibido repetidamente; final da entrada é "cancel" ou equivalente, ou um valor especial; exit significa que os avisos param de aparecer.
Função Iterator : input é um objeto ou função com estado que retorna o próximo dígito quando chamado; o final da entrada é uma exceção ou valor especial; exit significa que o iterador para de ser chamado.

A entrada para D e a saída podem ser feitas por qualquer método padrão aceitável .

Casos de teste:

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 Maçaneta da porta
fonte

Acho que devemos assumir que um dígito será fornecido toda vez que nossa solução solicitar entrada, certo? E, deve ser um programa completo, já que essa é a maneira objetiva de garantir que a entrada seja dada dígito por dígito, não? (O desafio diz "programa ou função", hum ...)

Erik, o Outgolfer, em 1/09/19

@EriktheOutgolfer O formato de entrada é explicado em detalhes na lista com marcadores da pergunta.

Maçaneta

Eu estava pensando em quão objetivos podem ser esses formatos ... Acho que vou parar de comentar e começar a resolver isso . :-)

Erik the Outgolfer

Há algo errado em apenas pegar uma lista como digitsentrada com um valor especial para EOF?

Jonathan Allan

@EriktheOutgolfer não se houver um valor EOF, a menos que eu tenha entendido algo errado. Por exemplo, digamos que todo o valor é 132 e o divisor potencial é 4 então []e [2]retorno outra coisa senão falseou true(incluindo a própria função etc ...) enquanto [2,3], [2,3,1]e [2,3,1,EOF]retorno true. Parece-me tão próximo da opção de estado global.

Jonathan Allan

Respostas:

JavaScript (ES6), 70 bytes

Formato de entrada: Função ao curry

Uma função que pega o divisor e retorna uma função que pega cada dígito ou para EOF. A segunda função retorna (falso), (verdadeiro) ou ela mesma (sem resposta). $-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)

Experimente online!

Quão?

Dado um divisor e um dividendo composto por dígitos decimais, calculamos a seguinte expressão para todos os : $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 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$

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
fonte

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 da linha de comando e lê dígitos nem linhas separadas com -o marcador EOF. Saídas 1para divisíveis, 0se não. Explicação:

@set n=

Inicialize ncom a string vazia.

@set g=1

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

:l

Comece um loop lendo dígitos.

@set/ps=

Leia o próximo dígito.

@if %s%==- goto g

Pare o processamento no EOF.

@set n=%s%%n%

Anexe o próximo dígito a n.

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

Atualize gagora que len(n)aumentou e calcule n%g.

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

Se rfor diferente de zero, então ddefinitivamente não se divide n, porque g, um fator de d, não. Se rfor zero, sabemos apenas se ddivide nse for gigual d; portanto, se não for, continue o loop.

:g

Saia do loop de leitura de dígitos aqui no EOF.

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

Calcular e gerar implicitamente o resultado.

Neil
fonte