Encodage du facteur premier

15

Comment fonctionne l'encodage

Étant donné une liste de bits:

  • Tenir un premier (en commençant par 2)
  • Avoir une liste
  • Pour chaque bit en entrée
    • Si c'est le même que le bit précédent, ajoutez le premier que vous tenez à la liste
    • Si c'est différent, maintenez le premier prime et ajoutez-le à la liste
  • Retournez le produit de tous les numéros de votre liste
  • Pour le premier bit, supposons que le bit précédent était 0

Remarque: ces étapes sont uniquement à des fins d'illustration, vous n'êtes pas obligé de les suivre.

Exemples

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

Quelques exemples supplémentaires:

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

Défi

Écrivez un encodeur et un décodeur pour cette méthode d'encodage.

(Le décodeur inverse le processus de l'encodeur).

Entrée sortie

  • L'encodeur peut prendre des entrées dans n'importe quel format raisonnable

  • L'encodeur doit sortir soit un entier soit une chaîne

  • Le décodeur doit accepter l'entrée dans le même format que le codeur émet

  • Le décodeur doit sortir le même format que l'encodeur prend en entrée

En d'autres termes decoder( encoder( input ) ) === input

Remarques

  • Le décodeur peut supposer que son entrée est décodable
  • Votre réponse a seulement pour traiter des entiers que votre langue peut prendre en charge de manière native sans utiliser ( long, bigInt, etc.), être raisonnable, si vous ne supporterais que la langue ints jusqu'à 1, peut - être revenir sur l' affichage d' une réponse

Notation

Votre score est la somme des longueurs en octets de l'encodeur et du décodeur.

Si vous devez importer un module, l'importation ne peut être comptée qu'une seule fois à condition que votre encodeur et votre décodeur puissent coexister dans le même fichier et être réutilisés (comme les fonctions).

Les failles par défaut sont interdites.

C'est le donc le score le plus court pour chaque langue l'emporte.

Asone Tuhid
la source
Ce dernier exemple est-il obligatoire ou pouvons-nous limiter la sortie à 64 bits maximum (2 ^ 63-1 / 9223372036854775808)?
Kevin Cruijssen
1
@KevinCruijssen Non, votre réponse ne doit fonctionner que pour les nombres entiers que votre langue peut gérer.
Asone Tuhid
1
@KevinCruijssen * gérer nativement sans bibliothèques de bigints, je vais clarifier
Asone Tuhid

Réponses:

8

05AB1E , 13 octets

Encodeur, 8 octets

0ì¥ĀηOØP

Essayez-le en ligne!

Explication

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

Décodeur, 5 octets

Ò.ØÉJ

Essayez-le en ligne!

Explication

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

Gelée , 17 octets

Encodeur (10 octets):

0;IA+\‘ÆNP

Essayez-le en ligne!

Décodeur (7 octets):

ÆEĖŒṙḂ¬

Essayez-le en ligne!

Comment?

Encodeur:

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

Décodeur:

Æ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
la source
5

JavaScript (ES6), 130 octets

E / S: tableau de bits ↔ entier

Encodeur, 71 octets

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

Essayez-le en ligne!

Décodeur, 59 octets

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

Essayez-le en ligne!

Arnauld
la source
3

Java 10, 209 octets

Encodeur, 124 octets

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

Essayez-le en ligne.

Explication:

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

Décodeur, 85 octets

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

Essayez-le en ligne.

Explication:

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
la source
Vous pouvez enregistrer 2 octets en changeant longpour int.
Asone Tuhid
3

Husk , 18 octets

Encodeur, 11 octets

Πmo!İp→∫Ẋ≠Θ

Essayez-le en ligne!

Décodeur, 7 octets

mȯ¬%2ṗp

Essayez-le en ligne!

Comment ils travaillent

Encodeur:

Πmo! İp → ∫Ẋ ≠ Θ - Programme complet. Prend les entrées du premier CLA, les sorties vers STDOUT.
          Θ - Ajoute un élément par défaut (0 dans ce cas).
        Ẋ ≠ - Carte sur des paires d'éléments adjacents avec ≠ (différent de). À Husk,
              certains opérateurs renvoient d'autres choses utiles que de simples valeurs booléennes.
              Ici, ≠ renvoie la différence absolue entre ses deux arguments.
       ∫ - Sommes cumulées.
 mo - Mappez la fonction suivante sur la liste des sommes:
    İp - Rend la liste infinie de nombres premiers.
   ! → - Et indexez-le avec la somme courante incrémentée.
Π - Prenez le produit.

Décodeur:

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.
M. Xcoder
la source
3

Python 2 , 234 193 174 octets

Encodeur, 116 101 97 octets:

Utilise le théorème de 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

Essayez-le en ligne!

Décodeur, 118 92 77 octets:

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

Essayez-le en ligne!

ovs
la source
1

J , 34 octets

Fortement inspiré par la solution Jelly de Jonathan Allan!

Encodeur: 23 octets

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

Essayez-le en ligne!

                    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  

Je n'aime pas ces nombreuses fourchettes [:- elles devraient être jouables au golf.

Décodeur: 11 octets

2|[:_1&p:q:

Essayez-le en ligne!

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

C (gcc) , 180 184 octets

  • Ajout de quatre octets pour que les formats de sortie correspondent.

102 octets - Encodeur

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

Essayez-le en ligne!

82 octets - Décodeur

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

Essayez-le en ligne!

Jonathan Frech
la source
@AsoneTuhid Désolé, mal lu.
Jonathan Frech
@AsoneTuhid Maintenant ajouté un décodeur. Espérons que maintenant conforme.
Jonathan Frech
@ovs True; merci pour votre remarque.
Jonathan Frech
1

Gol> <> , 29 + 39 = 68 octets

Encodeur, 29 octets

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

Essayez-le en ligne!

Décodeur, 39 octets

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

Essayez-le en ligne!

Comment ça marche

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

Ce serait mieux si je pouvais jouer au golf dans la prochaine boucle d'amorçage ...

Bubbler
la source