Niecierpliwy test podzielności

Twoim zadaniem jest napisanie programu lub funkcji, która określa, czy liczba jest podzielna przez inną. Haczyk polega na tym, że powinien udzielić odpowiedzi tak szybko, jak to możliwe , nawet jeśli nie podano wszystkich cyfr numeru.

Twój program powinien przyjąć jako liczbę całkowitą D ≥ 2, a następnie ciąg cyfr. Reprezentują one cyfry innej liczby całkowitej N ≥ 1, zaczynając od co najmniej znaczącej cyfry. Na pierwszym miejscu, że N albo musi lub nie może być divisble przez D , Twój program powinien wypisać właściwą odpowiedź i wysiadanie. Po osiągnięciu końca wejścia, to powinien wypisać czy pełny N jest podzielna przez D .

Oto lista dopuszczalnych formatów wejściowych dla N (zostaw komentarz, jeśli uważasz, że coś nieuwzględnionego powinno być dozwolone):

Standardowe wprowadzanie : cyfry są podawane w osobnych wierszach; koniec wejścia to EOF lub wartość specjalna; Wyjście oznacza, że funkcja zwraca lub program kończy działanie.
Wejście analogowe : np. Poprzez naciśnięcia klawiszy lub dziesięć przycisków reprezentujących każdą cyfrę; koniec wprowadzania jest wartością specjalną; Wyjście oznacza, że funkcja zwraca lub program kończy działanie.
Funkcja ze stanem globalnym : wywoływana wielokrotnie z kolejnymi cyframi; koniec wprowadzania jest wartością specjalną; exit oznacza, że funkcja zwraca wartość inną niż null. Pamiętaj, że jeśli używasz stanu globalnego, musi on zostać wyczyszczony po zwróceniu wartości lub w inny sposób zresetowany , aby funkcja działała wiele razy .
Funkcja curry : zwraca inną funkcję, która ma zostać wywołana z następną cyfrą lub wartością; koniec wejścia to specjalna wartość lub wywołanie funkcji bez argumentu; Wyjście oznacza, że funkcja zwraca odpowiedź, a nie inną funkcję.
Pytanie GUI lub podobne : wyświetlane wielokrotnie; koniec wprowadzania to „anuluj” lub równoważny albo wartość specjalna; exit oznacza, że monity przestają się pojawiać.
Funkcja iteratora : wejście jest obiektem stanowym lub funkcją, która po wywołaniu zwraca następną cyfrę, koniec wejścia to wyjątek lub wartość specjalna; exit oznacza, że iterator przestaje być wywoływany.

Dane wejściowe dla D i dane wyjściowe można przeprowadzić dowolną akceptowalną metodą standardową .

Przypadki testowe:

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 Klamka
źródło

Myślę, że powinniśmy założyć, że za każdym razem, gdy nasze rozwiązanie poprosi o wprowadzenie danych, zostanie podana jedna cyfra, prawda? I powinien to być pełny program, ponieważ jest to obiektywny sposób na zapewnienie, że dane wejściowe są podawane cyfra po cyfrze, prawda? (Wyzwanie mówi „program lub funkcja”, hmm ...)

Erik the Outgolfer

@EriktheOutgolfer Format wejściowy wyjaśniono szczegółowo na liście punktowanej w pytaniu.

Klamka

Właśnie myślałem o tym, jak obiektywne mogą być te formaty ... Wydaje mi się, że po prostu przestałem naciągać i zacząłem rozwiązywać ten problem . :-)

Erik the Outgolfer

Czy coś jest nie tak z przyjmowaniem listy jako digitsdanych wejściowych o specjalnej wartości dla EOF?

Jonathan Allan

@EriktheOutgolfer nie, jeśli istnieje wartość EOF, chyba że coś źle zrozumiałem. Na przykład załóżmy, że cała wartość wynosi 132 a potencjał dzielnik jest 4 wtedy []i [2]coś innego niż powrót falselub true(w tym samej funkcji etc ...), podczas [2,3], [2,3,1]i [2,3,1,EOF]powrót true. Uderza mnie to tak blisko opcji globalnego stanu.

Jonathan Allan

Odpowiedzi:

JavaScript (ES6), 70 bajtów

Format wejściowy: funkcja 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)

Wypróbuj online!

W jaki sposób?

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

Skomentował

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
źródło

Partia, 177 169 bajtów

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

Pobiera djako parametr wiersza polecenia i odczytuje cyfry nna osobnych wierszach -jako znacznik EOF. Wyniki 1dla podzielnej, 0jeśli nie. Wyjaśnienie:

@set n=

Zainicjuj npusty ciąg.

@set g=1

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

:l

Rozpocznij pętlę odczytującą cyfry.

@set/ps=

Przeczytaj następną cyfrę.

@if %s%==- goto g

Zatrzymaj przetwarzanie w EOF.

@set n=%s%%n%

Wpisz następną cyfrę do n.

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

Zaktualizuj gteraz, że len(n)wzrosła i oblicz n%g.

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

Jeśli rjest niezerowe, to dzdecydowanie się nie dzieli n, ponieważ gwspółczynnik dnie. Jeśli rwynosi zero, wiemy tylko, czy ddzieli, njeśli gjest równe d, więc jeśli nie jest, kontynuuj pętlę.

:g

Wyjdź z pętli odczytu cyfr tutaj na EOF.

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

Oblicz i domyślnie wyprowadź wynik.

Neil
źródło