16
\$\begingroup\$

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]
\$\endgroup\$
1
  • \$\begingroup\$ Edit is welcomed if the description words is confusing... \$\endgroup\$
    – tsh
    Jan 5 at 9:04

15 Answers 15

14
\$\begingroup\$

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.

\$\endgroup\$
1
10
\$\begingroup\$

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.

\$\endgroup\$
6
\$\begingroup\$

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.

\$\endgroup\$
1
  • 1
    \$\begingroup\$ Don't think it's worth a full answer: but in hgl this is 8 bytes: m~<pl<fo. \$\endgroup\$
    – Wheat Wizard
    Jan 5 at 10:12
6
\$\begingroup\$

Vyxal, 2 bytes

G+

Try it Online!

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

Decoder

G½vε

Try it Online!

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

\$\endgroup\$
5
\$\begingroup\$

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
\$\endgroup\$
2
  • \$\begingroup\$ I'm not entirely sure I understand the spec to begin with, but -1? \$\endgroup\$ Jan 5 at 9:36
  • 1
    \$\begingroup\$ @UnrelatedString Yes that would've worked for the 4 byte version. I didn't know that builtin \$\endgroup\$
    – ovs
    Jan 5 at 9:54
5
\$\begingroup\$

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.

\$\endgroup\$
2
  • 1
    \$\begingroup\$ 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]. \$\endgroup\$
    – xnor
    Jan 5 at 11:22
  • \$\begingroup\$ @xnor PARI/GP doesn't support adding a vector and a scalar. \$\endgroup\$
    – alephalpha
    Jan 5 at 11:23
5
\$\begingroup\$

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.

\$\endgroup\$
7
  • \$\begingroup\$ Looks like the output is the same as input for 1 (and other one-item lists with numbers without 0). \$\endgroup\$
    – pajonk
    Jan 5 at 12:53
  • \$\begingroup\$ @pajonk Thanks; I think a trailing zero fixes that nicely. \$\endgroup\$
    – Neil
    Jan 5 at 14:00
  • \$\begingroup\$ Is doubling zeros necessary now? encoder, decoder \$\endgroup\$
    – pajonk
    Jan 5 at 14:37
  • \$\begingroup\$ @pajonk Unfortunately 102 encodes the same way as 1,2 if you don't. \$\endgroup\$
    – Neil
    Jan 5 at 18:37
  • \$\begingroup\$ Ah, you're right... \$\endgroup\$
    – pajonk
    Jan 5 at 19:54
4
\$\begingroup\$

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.

\$\endgroup\$
4
\$\begingroup\$

Ruby, 20 bytes

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

Try it online

\$\endgroup\$
2
\$\begingroup\$

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

\$\endgroup\$
2
\$\begingroup\$

Husk, 4 bytes

m+Σ¹

Try it online!

Decoder

Explanation

adds sum to each element

m+Σ¹   translates to m+Σ⁰⁰
  Σ⁰   sum of input
m   ⁰  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

J0MR¹Σ  [1,2] -> [3, 0, 3, 3]
                 \1/    \ 2 /

Decoder
mLx0
\$\endgroup\$
2
\$\begingroup\$

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)))
\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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⁻θ÷⌈θ²

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

  θ     Input array
 ⁻      Vectorised subtract
     θ  Input array
    ⌈   Maximum
   ÷    Integer divided by
      ² Literal integer `2`
I       Cast to string
        Implicitly print
\$\endgroup\$
1
\$\begingroup\$

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!

\$\endgroup\$
1

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.