Encode integers with some others

Question

Input a non-empty array of positive (greater than 0) integers. Output another non-empty array of positive integers which encode the input array. Output array does not use any numbers used in the input array.

Rules

• Output array should not contain any numbers used in the input array.
  • Both input and output array may contain duplicate numbers.
• Output array may have same length, may be longer, may be shorter than the original one.
• It should be able to decode the original array from the output array.
  • You only need to decode arrays your encoder output. You are not required to implement a one-to-one mapping.
  • Your decoder may only use any info encoded with numbers in the array and its length. You are not allowed to pass extra info by using other properties of the array (whenever your language support it).
  • Input array is not sorted. And after decode, you should keep the order of input numbers. [3, 2, 1], and [1, 2, 3] are two different arrays.
  • You may implement your decoder in a different language.
• Encoding to a single integer is allowed. If your encoder always encode to a single integer, it may output an integer instead of an array.
• The word "array" talked in this post does not include SparseArray (in case your language support it). SparseArray is a special kind of array while there may be gaps between array items.
• You may output integers as strings of their decimal representation, if your output integers are too large, or you just prefer so.
  • Leading zeros in the output strings are allowed. But if there are any, after removing leading zeros or padding more leading zeros, your decoder should still output the original array. Or in the other words, your decoder should not relay on the number of leading zeros to work.
• Your program should at least support any array of 100 numbers, while every number in 1~100.
  • The word "support" here means it should be able to decode the original array without any errors introduced by integer overflow or floating point precision. Your program may however timeout on TIO as long as it will output correct result when given enough resources.
• Your encode algorithm should in theory work for any size array with any large numbers.

Task is code-golf the encoder program. The decoder does not contribute to your byte count. But you should also include the decoder program for a reference, so we can verify it. (Please include it in the post directly, not only in TIO link.)

Testcases

The output array may vary from answer to answer. So we only include input array here. You can verify your answer by checking if decoder(encoder(input)) may result the original input, and encoder(input) does not contain any numbers in input.

[1]
[10]
[1,2]
[2,1]
[1,1]
[11]
[1,11]
[11,1]
[1,2,3,4,5,6,7,8,9,10]
[93,29,47,3,29,84,19,70]

Answer 1

Python, 29 bytes

lambda l:[x+max(l)for x in l]

Try it online!

Just adds the list maximum to each element, producing values greater than any in the original list. The max of the resulting list is double the original max, so we can invert by lowering each element by half the new max.

decoder=lambda r:[x-max(r)//2 for x in r]

You can encode with sum in place of max (with a different decoder), in case sum is shorter in your language.

• loopy walt: This is probably illegal since it hardcodes the maximal list length (100 as per OP) and returns a generator, but it would save 2 tio.run/##VU/LboMwELz7K1bqxUQbhUcaAhJfQjm44BSri40WJ00v/…

Answer 2

Jelly, 2 bytes

ÆẸ

Decoder:

ÆE

Try it online!

A built-in.

ÆE: Compute the array of exponents of z's prime factorization. Includes zero exponents.

ÆẸ: Inverse of ÆE.

In other words, ÆẸ maps \$[a,b,c,d,\dots]\$ to \2ドル^a 3^b 5^c 7^d \cdots\$.

This trick is also used in the Gödel numbering.

• RARE Kpop Manifesto: this is beyond inefficient, since there are 25 primes under 100. So to encode every number 1-100, you're creating a 25-cell array of mostly zeros (since you said "includes zero exponents" yourself). Even assuming zero over-head in the array structure, and every cell's info can be compressed down to a single-bit using Hogwarts magic, you're still re-encoding 7-bits of info into 25-bits at the very least. Even re-encoding them as 3-byte UTF-8 codepoints could counter-intuitively offer storage savings

Answer 3

Haskell, 13 bytes

map=<<(+).sum

Try it online!

Decoder:

\r->[x-div(sum r)(1+length r)|x<-r]

The code is pointfree for f l=[x+sum l|x<-l], that is f l=map(+sum l)l. It increases each element by the sum of the list. This puts each element above the maximum of the original list. The function sum was used rather than maximum because sum is shorter.

To invert this, note that the resulting list then has sum equal to that of the original list times one plus its length. So, subtracting this recovers the original list.

• Wheat Wizard: Don't think it's worth a full answer: but in hgl this is 8 bytes: m~<pl<fo.

Answer 4

Vyxal, 2 bytes

G+

Try it Online!

Add the maximum of the input list to each number - just like xnor's python answer.

Decoder

G1⁄2vε

Try it Online!

Get the absolute difference of each item and half of the maximum of the list.

Answer 5

Jelly, (削除) 4 (削除ここまで) 2 bytes

-2 bytes from xnor's answer

+Ṁ

Try it online!

+Ṁ -- Encoder
+Ṁ -- Add the Ṁaximum to each value
ṀHạ -- Decoder
ṀH -- Halve of the Ṁaximum
 ạ -- ạbsolute difference between this and each value

• Unrelated String: I'm not entirely sure I understand the spec to begin with, but -1?
• ovs: @UnrelatedString Yes that would've worked for the 4 byte version. I didn't know that builtin

Answer 6

Pari/GP, 13 bytes

a->2*a*lcm(a)

Decoder:

a->a/sqrtint(2*lcm(a))

Try it online!

Inspired by @xnor's Python answer. lcm is shorter than vecsum and vecmax.

• xnor: I wondered if you could get away with adding the lcm to avoid needing to double, but there's collisions like [5, 8] with [9,12].
• alephalpha: @xnor PARI/GP doesn't support adding a vector and a scalar.

Answer 7

Retina 0.8.2, (削除) 10 (削除ここまで) 7 bytes

9
,
00

Try it online! Link includes test cases. Explanation: Inserts 9s everywhere, then changes commas into double zeros.

The decoder is (削除) 12 (削除ここまで) 13 bytes:

00
,
9(.?)
1ドル

Try it online! Link includes encoded test cases.

• pajonk: Looks like the output is the same as input for 1 (and other one-item lists with numbers without 0).
• Neil: @pajonk Thanks; I think a trailing zero fixes that nicely.
• pajonk: Is doubling zeros necessary now? encoder, decoder
• Neil: @pajonk Unfortunately 102 encodes the same way as 1,2 if you don't.
• pajonk: Ah, you're right...

Answer 8

Ruby, 20 bytes

->a{a.map{_1+a.max}}

Try it online

Answer 9

R, 19 bytes

Or R>=4.1, 12 bytes by replacing the word function with a \.

function(v)v+max(v)

Try it online!

Port of @xnor's answer.

Answer 10

Add++, 11 bytes

L,bUMVB]G€+

Try it online!

Decoder:

L,bUM2/VB]dbLGiXz£_€|

Try it online!

Basically, a really convoluted way of porting Python - to encode, add the maximum to each item, and to decode, get the absolute value of subtracting half the maximum from each item

Answer 11

Husk, 4 bytes

m+Σ1

Try it online!

Decoder

Explanation

adds sum to each element

m+Σ1 translates to m+Σ00
 Σ0 sum of input
m 0 for each element in input
 + add the sum
Decoder
ṠṀ-§÷o→LΣ

alternate 4-byte

SM+Σ
S hook: call with input and of input
 M Σ M sum
 M+Σ map + over input with sum as right argument

alternate 6-byte with short decoder

J0MR1Σ [1,2] -> [3, 0, 3, 3]
 1円/ \ 2 /
Decoder
mLx0

Answer 12

JavaScript (Node.js), 23 bytes

a=>a.map(x=>a.join``+x)

Try it online!

a=>a.map(v=>+v.slice(a.join('').length/(a.length+1)))

Answer 13

C (clang), ^{(削除) 65 (削除ここまで) (削除) 57 (削除ここまで)} 56 bytes

i;s;f(*a,n){for(s=i=0;i<n;)s+=a[i++];for(;n--;)a[n]+=s;}

Try it online!

Inputs a pointer to an array of positive integers and its length (becasue pointers in C carry no length info).
Encodes the array in place by adding the sum of all the array elements to each element.

Decoder

i;s;d(*a,n){for(s=i=0;i<n;)s+=a[i++];for(s/=-~n;n--;)a[n]-=s;}

Try it online!

Inputs a pointer to an array of positive integers and its length (becasue pointers in C carry no length info).
Decodes the array in place by subtracting from each element the sum of all the elements divided by the length plus one.

Answer 14

Charcoal, 5 bytes

I+⌈θθ

Try it online! Another port of @xnor's answer. Explanation:

 θ Input array
 θ Input array
 ⌈ Maximum
 + Vectorised sum
I Cast to string
 Implicitly print

Decoder, 7 bytes:

I−θ÷⌈θ2

Try it online! Link is to verbose version of code. Explanation:

 θ Input array
 − Vectorised subtract
 θ Input array
 ⌈ Maximum
 ÷ Integer divided by
 2 Literal integer `2`
I Cast to string
 Implicitly print

Answer 15

brainfuck, 25 bytes

,[>+>+<<-]>[[>.<-]>-.+<,]

Try it online!

If you are working on strings. You can simply encode each character by its ASCII value.

,>>>++<,[<<[->+>-<<]>[-<+>]>[>-.[-]<+]>+<,]

Try it online!

• l4m2: You can somehow skip the first digit