Tes keterbelahan tidak sabar

Tugas Anda adalah menulis program atau fungsi yang menentukan apakah suatu angka dapat dibagi oleh yang lain. Tangkapannya adalah bahwa ia harus memberikan jawaban sesegera mungkin , bahkan jika tidak semua angka angka telah diberikan.

Program Anda harus mengambil bilangan bulat D ≥ 2 dan kemudian serangkaian digit sebagai input. Ini mewakili digit bilangan bulat lain N ≥ 1, mulai dari angka paling tidak signifikan. Pada titik pertama yang N baik harus atau harus tidak menjadi divisble oleh D , program anda harus output jawaban yang tepat dan keluar. Jika akhir input tercapai, seharusnya keluaran apakah penuh N habis dibagi D .

Berikut adalah daftar format input yang dapat diterima untuk N (tinggalkan komentar jika Anda berpikir sesuatu yang tidak termasuk harus diizinkan):

Input standar : digit diberikan pada garis yang berbeda; akhir input adalah EOF atau nilai khusus; keluar berarti bahwa fungsi kembali atau program keluar.
Input analog : melalui mis. Penekanan tombol atau sepuluh tombol yang mewakili setiap digit; akhir input adalah nilai khusus; keluar berarti bahwa fungsi kembali atau program keluar.
Fungsi dengan negara global : dipanggil berulang kali dengan digit berturut-turut; akhir input adalah nilai khusus; keluar berarti bahwa fungsi mengembalikan nilai yang bukan nol. Perhatikan bahwa jika Anda menggunakan keadaan global, itu harus dihapus setelah nilai dikembalikan atau direset sedemikian rupa sehingga fungsi tersebut berfungsi beberapa kali .
Fungsi Curried : mengembalikan fungsi lain untuk dipanggil dengan digit berikutnya atau nilai; akhir input adalah nilai khusus atau memanggil fungsi tanpa argumen; keluar berarti bahwa fungsi mengembalikan jawaban daripada fungsi lain.
GUI prompt atau serupa : ditampilkan berulang kali; akhir input adalah "batal" atau setara, atau nilai khusus; keluar berarti meminta agar berhenti muncul.
Fungsi Iterator : input adalah objek atau fungsi stateful yang mengembalikan digit berikutnya ketika dipanggil, akhir input adalah pengecualian atau nilai khusus; keluar berarti iterator berhenti dipanggil.

Input untuk D dan output dapat melalui metode standar yang dapat diterima .

Kasus uji:

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 Gagang pintu
sumber

Saya pikir kita harus mengasumsikan bahwa satu digit akan diberikan setiap kali solusi kami meminta input, kan? Dan, itu harus menjadi program penuh, karena ini adalah cara objektif untuk memastikan bahwa input diberikan digit demi digit, bukan? (Tantangannya mengatakan "program atau fungsi", hmm ...)

Erik the Outgolfer

@EriktheOutgolfer Format input dijelaskan secara terperinci dalam daftar berpoin dalam pertanyaan.

Gagang Pintu

Saya hanya berpikir tentang bagaimana obyektif format-format itu menjadi ... Saya kira saya akan berhenti nitpicking dan mulai benar-benar menyelesaikan ini . :-)

Erik the Outgolfer

Apakah ada yang salah dengan hanya mengambil daftar sebagai digitsinput dengan nilai khusus untuk EOF?

Jonathan Allan

@EriktheOutgolfer tidak jika ada nilai EOF, kecuali saya telah salah mengerti sesuatu. Sebagai contoh katakanlah seluruh nilai adalah 132 dan potensi pembagi adalah 4 maka []dan [2]kembali apa pun selain falseatau true(termasuk fungsi itu sendiri dll ...) sementara [2,3], [2,3,1]dan [2,3,1,EOF]kembali true. Itu membuat saya sangat dekat dengan pilihan negara global.

Jonathan Allan

Jawaban:

JavaScript (ES6), 70 byte

Format input: Fungsi Kari

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

Cobalah online!

Bagaimana?

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

\begin{matrix} (1) & k \times 10^{n} + q (\mod hal) \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 hal) = (m hal + k) \times 10^{n} + q (\mod hal) = (m hal \times 10^{n} (\mod hal)) + (k \times 10^{n} + q (\mod hal)) (\mod hal) = 0 + (k \times 10^{n} + q (\mod hal)) (\mod hal) = k \times 10^{n} + q (\mod hal)

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

Berkomentar

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
sumber

Batch, 177 169 byte

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

Dibawa dsebagai parameter baris perintah dan membaca angka npada baris terpisah dengan -sebagai penanda EOF. Output 1untuk habis dibagi, 0jika tidak. Penjelasan:

@set n=

Menginisialisasi nke string kosong.

@set g=1

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

:l

Mulailah satu digit pembacaan lingkaran.

@set/ps=

Baca digit selanjutnya.

@if %s%==- goto g

Hentikan pemrosesan di EOF.

@set n=%s%%n%

Tambahkan angka berikutnya ke n.

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

Perbarui gsekarang yang len(n)telah meningkat dan menghitung n%g.

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

Jika rbukan nol maka dpasti tidak membagi n, karena g, faktor d, tidak. Jika rnol maka kita hanya tahu apakah dmembagi njika gsama d, jadi jika tidak, lanjutkan loop.

:g

Keluar dari loop pembacaan digit di sini di EOF.

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

Hitung dan hasilkan secara implisit hasilnya.

Neil
sumber