# How the encoding works

Given a list of bits:

• Hold a prime (starting with 2)
• Have a list
• For each bit in the input
• If it's the same as the previous bit, add the prime you're holding to the list
• If it's different, hold the next prime and add that to the list
• Return the product of all the numbers in your list
• For the first bit, assume the previous bit was 0

Note: these steps are for illustration purposes only, you are not required to follow them.

# Examples

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


### Some more examples:

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


# Challenge

Write an encoder and a decoder for this encoding method.

(The decoder reverses the process of the encoder).

# Input / Output

• The encoder can take input in any reasonable format

• The encoder must output either an integer or a string

• The decoder must take input in the same format that the encoder utputs

• The decoder must output the same format that the encoder takes as input

In other words decoder( encoder( input ) ) === input

### Notes

• The decoder may assume that its input is decodable
• Your answer only has to deal with integers that your language can natively support without using (long, bigInt, etc.), be reasonable, if you language only supports ints up to 1, maybe reconsider posting an answer

# Scoring

Your score is the sum of the lengths in bytes of the encoder and decoder.

If you need to import a module, the import can be counted only once provided that your encoder and decoder can coexist in the same file and be reused (like functions).

Default loopholes are forbidden.

This is so the shortest score for every language wins.

• Is that last example mandatory, or can we limit the output to up to 64 bits (2^63-1 / 9223372036854775808)? – Kevin Cruijssen Apr 26 '18 at 12:03
• @KevinCruijssen No, your answer only has to work for integers that your language can handle. – Asone Tuhid Apr 26 '18 at 12:06
• @KevinCruijssen *handle natively without libraries of bigints, i'll clarify – Asone Tuhid Apr 26 '18 at 13:07

# 05AB1E, 13 bytes

## Encoder, 8 bytes

0ì¥ĀηOØP


Try it online!

Explanation

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


## Decoder, 5 bytes

Ò.ØÉJ


Try it online!

Explanation

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


# Jelly, 17 bytes

### Encoder (10 bytes):

0;IA+\‘ÆNP


Try it online!

### Decoder (7 bytes):

ÆEĖŒṙḂ¬


Try it online!

### How?

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


Decoder:

Æ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]


# JavaScript (ES6), 130 bytes

I/O: array of bits ↔ integer

## Encoder, 71 bytes

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


Try it online!

## Decoder, 59 bytes

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


Try it online!

# Java 10, 209 bytes

## Encoder, 124 bytes

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


Try it online.

Explanation:

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 bytes

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


Try it online.

Explanation:

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

• You can save 2 bytes by changing long to int. – Asone Tuhid Apr 26 '18 at 19:15

# Husk, 18 bytes

### Encoder, 11 bytes

Πmo!İp→∫Ẋ≠Θ


Try it online!

### Decoder, 7 bytes

mȯ¬%2ṗp


Try it online!

### How they work

Encoder:

Πmo!İp→∫Ẋ≠Θ – Full program. Takes input from the first CLA, outputs to STDOUT.
Θ – Prepend a default element (0 in this case).
Ẋ≠  – Map over pairs of adjacent elements with ≠ (not equals). In Husk,
some operators return other useful things than just boolean values.
Here, ≠ returns the absolute difference between its two arguments.
∫    – Cumulative sums.
mo         – Map the following function over the list of sums:
İp        – Yield the infinite list of primes.
!  →       – And index into it with the current sum incremented.
Π           – Take the product.


Decoder:

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.


# Python 2, 234193 174 bytes

## Encoder, 116101 97 bytes:

Uses Wilson's theorem.

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


Try it online!

## Decoder, 11892 77 bytes:

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


Try it online!

# J, 34 bytes

Heavily inspired by Jonathan Allan's Jelly solution!

## Encoder: 23 bytes

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


Try it 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


I don't like those many cap forks [: - it should be golfable.

## Decoder: 11 bytes

2|[:_1&p:q:


Try it online!

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


# Jelly, 15 bytes

### Encoder, 9 bytes

0;ŒgL€ÆẸH


Try it online!

### Decoder, 6 bytes

Æf’ÆCḂ


Try it online!

# C (gcc), 180 184 bytes

• Added four bytes so that output formats match.

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


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


Try it online!

• @AsoneTuhid Sorry, misread. – Jonathan Frech Apr 26 '18 at 11:31
• @AsoneTuhid Now added a decoder. Hopefully compliant now. – Jonathan Frech Apr 26 '18 at 11:53
• @ovs True; thanks for your remark. – Jonathan Frech Apr 26 '18 at 14:21

# Gol><>, 29 + 39 = 68 bytes

## Encoder, 29 bytes

021IEh{$:}-Q$TP:SP?!t$|1k*3R!  Try it online! ## Decoder, 39 bytes 02I:MZ;:2k%:z}Q$TP:SP?!t$|1k,{{-z:N}3R!  Try it online! ### How these work 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


It'd be better if I could golf down the next-prime loop...