Pengkodean Faktor Utama

15

Cara kerja pengodean

Diberikan daftar bit:

  • Pegang prime (dimulai dengan 2 )
  • Punya daftar
  • Untuk setiap bit dalam input
    • Jika sama dengan bit sebelumnya, tambahkan perdana yang Anda pegang ke daftar
    • Jika berbeda, pegang prime berikutnya dan tambahkan ke daftar
  • Kembalikan produk semua angka dalam daftar Anda
  • Untuk bit pertama, anggap bit sebelumnya adalah 0

Catatan: langkah-langkah ini hanya untuk tujuan ilustrasi, Anda tidak diharuskan untuk mengikutinya.

Contohnya

Input: 001
hold 2

0:         add 2 to the list
0:         add 2 to the list
1: hold 3, add 3 to the list

list: 2,2,3
Output: 12

Input: 1101
hold 2

1: hold 3, add 3 to the list
1:         add 3 to the list
0: hold 5, add 5 to the list
1: hold 7, add 7 to the list

list: 3,3,5,7
Output: 315

Beberapa contoh lagi:

000000000 -> 512
111111111 -> 19683
010101010 -> 223092870
101010101 -> 3234846615
011101101 -> 1891890
000101101010010000 -> 3847834029582062520

Tantangan

Tulis pembuat enkode dan decoder untuk metode penyandian ini.

(Decoder membalikkan proses encoder).

Input output

  • Encoder dapat mengambil input dalam format apa pun yang masuk akal

  • Encoder harus menampilkan bilangan bulat atau string

  • Decoder harus mengambil input dalam format yang sama dengan yang encoder utput

  • Decoder harus menampilkan format yang sama dengan yang diambil oleh encoder sebagai input

Dengan kata lain decoder( encoder( input ) ) === input

Catatan

  • Dekoder dapat mengasumsikan bahwa inputnya dapat didekodekan
  • Jawaban Anda hanya harus berurusan dengan bilangan bulat bahwa bahasa Anda native dapat mendukung tanpa menggunakan ( long, bigInt, dll), masuk akal, jika Anda bahasa hanya mendukung int hingga 1, mungkin mempertimbangkan kembali posting jawaban

Mencetak gol

Skor Anda adalah jumlah dari panjang dalam byte encoder dan decoder.

Jika Anda perlu mengimpor modul, impor hanya dapat dihitung satu kali asalkan encoder dan decoder Anda dapat hidup berdampingan dalam file yang sama dan digunakan kembali (seperti fungsi).

Celah default dilarang.

Ini adalah sehingga skor terpendek untuk setiap bahasa menang.

Asone Tuhid
sumber
Apakah itu contoh terakhir wajib, atau bisakah kita membatasi output hingga 64 bit (2 ^ 63-1 / 9223372036854775808)?
Kevin Cruijssen
1
@KevinCruijssen Tidak, jawaban Anda hanya perlu bekerja untuk bilangan bulat yang dapat ditangani oleh bahasa Anda.
Asone Tuhid
1
@KevinCruijssen * menangani secara asli tanpa perpustakaan bigints, saya akan mengklarifikasi
Asone Tuhid

Jawaban:

8

05AB1E , 13 byte

Encoder, 8 byte

0ì¥ĀηOØP

Cobalah online!

Penjelasan

0ì          # prepend 0 to input
  ¥         # calculate deltas
   Ā        # truthify each
    η       # calculate prefixes
     O      # sum each
      Ø     # get the prime at that index
       P    # product

Decoder, 5 byte

Ò.ØÉJ

Cobalah online!

Penjelasan

Ò       # get prime factors of input
 .Ø     # get their indices among the primes
   É    # check for oddness
    J   # join
Emigna
sumber
7

Jelly , 17 byte

Pengkode (10 byte):

0;IA+\‘ÆNP

Cobalah online!

Dekoder (7 byte):

ÆEĖŒṙḂ¬

Cobalah online!

Bagaimana?

Encoder:

0;IA+\‘ÆNP - Link: list of integers (1s and 0s)  e.g. [1,1,1,1,0]
0;         - prepend a zero                           [0,1,1,1,1,0]
  I        - incremental differences                  [1,0,0,0,-1]
   A       - absolute values                          [1,0,0,0,1]
    +\     - cumulative reduce with addition          [1,1,1,1,2]
      ‘    - increment each of the results            [2,2,2,2,3]
       ÆN  - get the nth prime for each result        [3,3,3,3,5]
         P - product of the list                      405

Dekoder:

ÆEĖŒṙḂ¬ - Link: integer         e.g. 405
ÆE      - prime exponent array       [0,4,1] (representing 2^0*3^4*5^1)
  Ė     - enumerate                  [[1,0],[2,4],[3,1]]
   Œṙ   - run-length decode          [2,2,2,2,3]
     Ḃ  - bit (mod 2)                [0,0,0,0,1]
      ¬ - logical NOT                [1,1,1,1,0]
Jonathan Allan
sumber
5

JavaScript (ES6), 130 byte

I / O: array bit ↔ integer

Encoder, 71 byte

a=>a.map(p=k=>r*=(g=i=>n%--i?g(i):i<2?n:g(++n))(n+=p^(p=k)),r=1,n=2)&&r

Cobalah online!

Decoder, 59 byte

D=(n,k=2,x=b=0)=>k>n?[]:n%k?D(n,k+1,1):[b^=x,...D(n/k,k,0)]

Cobalah online!

Arnauld
sumber
3

Java 10, 209 byte

Encoder, 124 byte

s->{long p=48,P=2,r=1,n,i;for(int c:s.getBytes()){if(p!=(p=c))for(n=0;n<2;)for(n=++P,i=2;i<n;n=n%i++<1?0:n);r*=P;}return r;}

Cobalah online.

Penjelasan:

s->{                // Method with String parameter and long return-type
  long p=48,        //  Previous character, starting at '0'
       P=2,         //  Current prime, starting at 2
       r=1,         //  Result, starting at 1
       n,i;         //  Temp-integers
  for(int c:s.getBytes()){
                    //  Loop over the digits of the input-String as bytes
    if(p!=(p=c))    //   If the current and previous digits are different
      for(n=0;      //    Reset `n` to 0
          n<2;)     //    And loop as long as `n` is still 0 or 1
        for(n=++P,  //     Increase `P` by 1 first with `++P`, and set `n` to this new `P`
            i=2;i<n;n=n%i++<1?0:n);
                    //     Check of the current `n` is a prime
                    //     If it remains the same it's a prime, if it becomes 0 or 1 not
    r*=P;}          //   Multiply the result by the current prime `P`
  return r;}        //  Return the result

Decoder, 85 byte

n->{var r="";for(long P=2,f=0,i=1;++i<=n;)for(;n%i<1;n/=P=i)r+=i!=P?f^=1:f;return r;}

Cobalah online.

Penjelasan:

n->{                // Method with long parameter and String return-type
  var r="";         //  Result-String, starting empty
  for(long P=2,     //  Current prime, starting at 2
      f=0,          //  Flag integer, starting at 0
      i=1;++i<=n;)  //  Loop `i` in the range [2,`n`]
    for(;n%i<1;     //   Inner loop over the prime factors of `n`
        n/=P=i)     //     After every iteration: divide `n` by `i`,
                    //     and set `P` to `i` at the same time
      r+=i!=P?      //    If `i` and `P` are not the same
          f^=1      //     Append the opposite of the flag `f` (0→1; 1→0)
         :          //    Else:
          f;        //     Append the flag `f`
  return r;}        //  Return the result
Kevin Cruijssen
sumber
Anda dapat menyimpan 2 byte dengan mengubah longke int.
Asone Tuhid
3

Sekam , 18 byte

Encoder, 11 byte

Πmo!İp→∫Ẋ≠Θ

Cobalah online!

Decoder, 7 byte

mȯ¬%2ṗp

Cobalah online!

Bagaimana mereka bekerja

Encoder:

!Mo! İp → ∫Ẋ ≠ Θ - Program lengkap. Mengambil input dari CLA pertama, output ke STDOUT.
          Θ - Sertakan elemen default (0 dalam hal ini).
        Ẋ ≠ - Memetakan pasangan elemen yang berdekatan dengan ≠ (tidak sama dengan). Dalam sekam,
              beberapa operator mengembalikan hal-hal lain yang bermanfaat selain nilai boolean
              Di sini, ≠ mengembalikan perbedaan absolut antara dua argumennya.
       ∫ - Jumlah kumulatif.
 mo - Memetakan fungsi berikut di atas daftar jumlah:
    İp - Menghasilkan daftar bilangan prima tak terbatas.
   ! → - Dan indeks ke dalamnya dengan jumlah saat ini bertambah.
Π - Ambil produk.

Dekoder:

mȯ¬%2ṗp – Full program.
      p – Prime factorization.
mȯ      – Map the following function over the list of factors:
     ṗ    – Retrieve the index in  the list of primes.
   %2     – Modulo 2.
  ¬       – Logical NOT.
Tuan Xcoder
sumber
3

Python 2 , 234 193 174 byte

Encoder, 116 101 97 byte:

Menggunakan teorema Wilson .

i=input()
P=n=x=r=1
while i:
 P*=n*n;n+=1
 if P%n:t=(i+[x]).index(x);i=i[t:];r*=n**t;x^=1
print r

Cobalah online!

Decoder, 118 92 77 byte:

i=input()
r=[]
n=x=1
while~-i:
 n+=1;x^=i%n<1
 while i%n<1:r+=x,;i/=n
print r

Cobalah online!

ovs
sumber
1

J , 34 byte

Sangat terinspirasi oleh solusi Jelly Jonathan Allan's!

Encoder: 23 byte

[:*/[:p:[:+/\2|@-~/\0,]

Cobalah online!

                    0,]  NB. prepend 0 to the input
             2  -~/\     NB. find the differences
              |@         NB. and their absolute values 
        [:+/\            NB. running sums
    [:p:                 NB. n-th prime
[:*/                     NB. product  

Saya tidak suka banyak garpu itu [: - itu harus golf.

Decoder: 11 byte

2|[:_1&p:q:

Cobalah online!

        q:    NB. prime factorization
  [:_1&p:      NB. find the number of primes smaller than n
2|             NB. modulo 2 
Galen Ivanov
sumber
1

C (gcc) , 180 184 byte

  • Menambahkan empat byte sehingga format keluaran cocok.

102 bytes - Encoder

p,r,i,m;e(char*_){for(m=0,p=1,i=2;*_;m=*_++-48,p*=i)if(*_-48-m)for(i++,r=2;r<i;i%r++||(r=2,i++));i=p;}

Cobalah online!

82 bytes - Decoder

d(C){for(m=C%2,r=2+m,p=2;C>1;p++)if(C%p<1)p-r&&(m=!m,r=p),putchar(m+48),C/=p,p=1;}

Cobalah online!

Jonathan Frech
sumber
@AsoneTuhid Maaf, salah baca.
Jonathan Frech
@AsoneTuhid Now menambahkan dekoder. Semoga patuh sekarang.
Jonathan Frech
@ovs Benar; terima kasih atas komentar anda.
Jonathan Frech
1

Gol> <> , 29 + 39 = 68 byte

Encoder, 29 byte

021IEh{$:}-Q$TP:SP?!t$|1k*3R!

Cobalah online!

Decoder, 39 byte

02I:MZ;:2k%:z}Q$TP:SP?!t$|1k,{{-z:N}3R!

Cobalah online!

Bagaimana cara kerjanya?

Encoder

021IEh{$:}-Q$TP:SP?!t$|1k*3R!

021                            Setup the stack as [last bit, current prime, current output]
   IEh                         Take input as int; if EOF, print top as number and halt
      {$:}-Q          |        If the next bit is different from the last bit...
            $                    Move the prime to the top
             T      t            Loop indefinitely...
              P:SP?!               Increment; if prime, skip `t` i.e. break
                     $           Move the prime to the correct position
                       1k*     Multiply the prime to the output
                          3R!  Skip 3 next commands (the init part)
                               Loop the entire program until EOF

---

Decoder

02I:MZ;:2k%:z}Q$TP:SP?!t$|1k,{{-z:N}3R!

02I                  Setup the stack as [last bit, current prime, encoded]
   :MZ;              If encoded == 1, halt
       :2k%          Compute encoded modulo prime
           :z}       Store NOT of the last at the bottom of the stack
              Q...|  Same as encoder's next-prime loop
1k,                  Divide encoded by prime (assume it is divisible)
   {{                Pull out the two bits at the bottom
     -z              Compute the next bit
       :N}           Print as number with newline, and move to the bottom
          3R!        Skip 3 init commands
                     Loop the entire program until finished

Akan lebih baik jika saya bisa bermain golf di putaran perdana berikutnya ...

Bubbler
sumber