Kodowanie Prime Factor

15

Jak działa kodowanie

Biorąc pod uwagę listę bitów:

  • Hold the prime (zaczynając od 2)
  • Mam listę
  • Dla każdego bitu na wejściu
    • Jeśli jest taki sam jak poprzedni bit, dodaj liczbę pierwszą, którą trzymasz na liście
    • Jeśli jest inaczej, przytrzymaj następną liczbę pierwszą i dodaj ją do listy
  • Zwróć iloczyn wszystkich liczb z listy
  • Dla pierwszego bitu załóżmy, że poprzedni był 0

Uwaga: te kroki mają wyłącznie charakter ilustracyjny, nie musisz ich przestrzegać.

Przykłady

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

Kilka innych przykładów:

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

Wyzwanie

Napisz koder i dekoder dla tej metody kodowania.

(Dekoder odwraca proces enkodera).

Wejście wyjście

  • Koder może przyjmować dane wejściowe w dowolnym rozsądnym formacie

  • Koder musi wyprowadzać liczbę całkowitą lub ciąg znaków

  • Dekoder musi pobierać dane wejściowe w tym samym formacie, w jakim koder podaje

  • Dekoder musi wysyłać ten sam format, który koder przyjmuje jako dane wejściowe

Innymi słowy decoder( encoder( input ) ) === input

Notatki

  • Dekoder może założyć, że jego wejście jest dekodowalne
  • Twoja odpowiedź musi dotyczyć liczb całkowitych, które Twój język może natywnie obsługiwać bez użycia ( long, bigIntitp.), Być rozsądna, jeśli Twój język obsługuje tylko liczby całkowite do 1, być może ponownie rozważ opublikowanie odpowiedzi

Punktacja

Twój wynik jest sumą długości w bajtach enkodera i dekodera.

Jeśli musisz zaimportować moduł, import można policzyć tylko raz, pod warunkiem, że Twój koder i dekoder mogą współistnieć w tym samym pliku i zostać ponownie użyte (podobnie jak funkcje).

Domyślne luki są zabronione.

To jest więc wygrywa najkrótszy wynik dla każdego języka.

Asone Tuhid
źródło
Czy ten ostatni przykład jest obowiązkowy, czy możemy ograniczyć wyjście do 64 bitów (2 ^ 63-1 / 9223372036854775808)?
Kevin Cruijssen
1
@KevinCruijssen Nie, twoja odpowiedź musi działać tylko dla liczb całkowitych obsługiwanych przez twój język.
Asone Tuhid
1
@KevinCruijssen * radzimy sobie natywnie bez bibliotek bigintów, wyjaśnię
Asone Tuhid

Odpowiedzi:

8

05AB1E , 13 bajtów

Koder, 8 bajtów

0ì¥ĀηOØP

Wypróbuj online!

Wyjaśnienie

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

Dekoder, 5 bajtów

Ò.ØÉJ

Wypróbuj online!

Wyjaśnienie

Ò       # get prime factors of input
 .Ø     # get their indices among the primes
   É    # check for oddness
    J   # join
Emigna
źródło
7

Galaretka , 17 bajtów

Koder (10 bajtów):

0;IA+\‘ÆNP

Wypróbuj online!

Dekoder (7 bajtów):

ÆEĖŒṙḂ¬

Wypróbuj online!

W jaki sposób?

Enkoder:

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

JavaScript (ES6), 130 bajtów

I / O: tablica bitów ↔ liczba całkowita

Koder, 71 bajtów

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

Wypróbuj online!

Dekoder, 59 bajtów

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

Wypróbuj online!

Arnauld
źródło
3

Java 10, 209 bajtów

Koder, 124 bajty

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;}

Wypróbuj online.

Wyjaśnienie:

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

Dekoder, 85 bajtów

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;}

Wypróbuj online.

Wyjaśnienie:

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
źródło
Możesz zapisać 2 bajty, zmieniając longna int.
Asone Tuhid,
3

Łuska , 18 bajtów

Koder, 11 bajtów

Πmo!İp→∫Ẋ≠Θ

Wypróbuj online!

Dekoder, 7 bajtów

mȯ¬%2ṗp

Wypróbuj online!

Jak oni pracują

Enkoder:

Πmo! İp → ∫Ẋ ≠ Θ - Pełny program. Pobiera dane wejściowe z pierwszego CLA, dane wyjściowe do STDOUT.
          Θ - wstaw element domyślny (w tym przypadku 0).
        Ẋ ≠ - Mapuj pary sąsiadujących elementów za pomocą with (nie równa się). W łusce
              niektórzy operatorzy zwracają inne przydatne rzeczy niż tylko wartości logiczne.
              Tutaj ≠ zwraca bezwzględną różnicę między dwoma argumentami.
       ∫ - Sumy skumulowane.
 mo - Zamapuj następującą funkcję na liście sum:
    İp - Uzyskanie nieskończonej listy liczb pierwszych.
   ! → - I zindeksuj go, zwiększając bieżącą sumę.
Π - Weź produkt.

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.
Pan Xcoder
źródło
3

Python 2 , 234 193 174 bajtów

Enkoder, 116 101 97 bajtów:

Wykorzystuje twierdzenie Wilsona .

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

Wypróbuj online!

Dekoder, 118 92 77 bajtów:

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

Wypróbuj online!

ovs
źródło
1

J , 34 bajty

Mocno zainspirowany galaretką Jonathana Allana!

Koder: 23 bajty

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

Wypróbuj 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  

Nie lubię tych wielu widelców do czapek [: - powinno być możliwe do gry w golfa.

Dekoder: 11 bajtów

2|[:_1&p:q:

Wypróbuj online!

        q:    NB. prime factorization
  [:_1&p:      NB. find the number of primes smaller than n
2|             NB. modulo 2 
Galen Iwanow
źródło
1

C (gcc) , 180 184 bajtów

  • Dodano cztery bajty, aby dopasować formaty wyjściowe.

102 bajty - koder

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;}

Wypróbuj online!

82 bajty - dekoder

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;}

Wypróbuj online!

Jonathan Frech
źródło
@AsoneTuhid Przepraszamy, źle odczytany.
Jonathan Frech
@AsoneTuhid Teraz dodano dekoder. Mam nadzieję, że teraz jest zgodny.
Jonathan Frech
@ovs True; dziękuję za twoją uwagę.
Jonathan Frech
1

Gol> <> , 29 + 39 = 68 bajtów

Enkoder, 29 bajtów

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

Wypróbuj online!

Dekoder, 39 bajtów

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

Wypróbuj online!

Jak działają

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

Byłoby lepiej, gdybym mógł zagrać w golfa w następnej pętli ...

Bubbler
źródło