4
\$\begingroup\$

Let N be the set of nonnegative integers, i.e. {0, 1, 2, 3, ...}.

Let c0(N) be the set of all infinite sequences in N that converge to 0, i.e. { (xn) ∈ NN | xn → 0 as n → ∞}.

c0(N) can be equivalently written as the set of all finite sequences of natural numbers, such that there are no trailing zeroes. The infinite sequence of all zeroes (corresponding to a finite sequence of length 0) is an element of c0(N).

Your task is to implement a bijection in your language between N and c0(N), in as few characters as possible. This means every number in N corresponds to a unique item of c0(N), and vice versa. Do this by defining two functions: f, going from N and c0(N); and g, the inverse of f. The length in bytes of these two definitions is your score.

You may use the largest internal integer and list types of your language, even if they aren't bignums or capable of handling infinite length. However, they should theoretically still be able to terminate with the right answer if the language was modified with a suitable bignum or lazy/infinite list type.

Some suggestions for ways to pack are below. Note that these aren't quite solutions yet and could need some tweaking to work; they're mostly to get the blood flowing.

  • f(1463616) = f(2^6 * 3^3 * 5^0 * 7^1 * 11^2) = [6, 3, 0, 1, 2] - Factorize the number into primes and read off exponents to get the sequence.
  • f(64971) = f(0b1111110111001011) = [6, 3, 0, 1, 2] - Expand the number in binary and use 0 as a separator to read strings of ones, representing the sequence in unary.

While this is a and the shortest answer will win, creative and interesting solutions are encouraged and may be subject to a bounty.

\$\endgroup\$
  • \$\begingroup\$ You must mean “positive” — it is simpler, by the way. The integer 0 is negative. \$\endgroup\$ – Nicolas Barbulesco May 4 '14 at 10:47
  • 3
    \$\begingroup\$ @NicolasBarbulesco In maths Zero is not positive or negative. That's why there is a difference between "positive" (excluding zero) and nonnegative (including zero.) Some floating point representations allow for a "postive zero and negative zero" which, while mathematically incorrect, can be convenient in programming for avoiding loss of information in certain cases. \$\endgroup\$ – Level River St May 4 '14 at 11:25
  • \$\begingroup\$ @steveverrill — Not “in maths”. In the maths I learnt (in France), zero is positive and negative. -0 = +0 = 0. ℤ₊ is the set of positive integers, and ℤ₋ is the set of negative integers. To exclude 0, we say strictly positive (ℤ₊*) or strictly negative (ℤ₋*). This is simple, and logical. And this makes many theorems work. In the UK, I have encountered your conception of things, and the convoluted vocabulary it needs. \$\endgroup\$ – Nicolas Barbulesco May 4 '14 at 15:21
  • 1
    \$\begingroup\$ @NicolasBarbulesco: In none of the four languages I read have I ever seen this definition of positivity. While I agree that the French definition might be simpler (for monotone functions, I prefer increasing and strictly increasing to non-decreasing and increasing as well), it's certainly not commonplace. \$\endgroup\$ – Dennis May 4 '14 at 15:36
2
\$\begingroup\$

GolfScript, 41 bytes

{[2base[0]/{,}/]-1%}:f{:|;-1{).f|=!}do}:g

Function “f”

[
  2base       # Push the digits of the argument in base 2.
  [0]/        # Split the digits around the 0's. This leaves sequences of 1's.
  {,}/        # Compute the lengths of those sequences.
]-1%          # Reverse the array of the lengths.

The binary expansion of any given non-negative integer in its canonical form may have trailing 0's, but not leading 0's.

Thus, reversing the array is necessary and sufficient to comply with the specification.

Function “g”

:|;           # Save the argument in variable “|” and pop it from the stack.
-1            # Push the integer “-1”.
{             #
  )           # Increment the integer.
  .f|=        # Check whether it is the preimage of “|”.
  !           # If it is not,
}do           # repeat the loop.

Function “g” (alternative)

An alternative, straightforward and efficient implementation of g is

{[-1%{0\{1}*}/]2base}:g

The brute-force approach is much slower, but it is four bytes shorter.

[
  -1%         # Reverse the order of the integer sequence.
  {           # For each integer “N”,
    0         # push 0,
    \{1}*     # followed by “N” 1's.
  }/          #
]             # Convert this bit sequence into an array.
2base         # Convert the array into an integer.

Example

  • 1250 is 10011100010 in base 2.

  • The lengths of the sequences of consecutive 1's are 1,0,3,0,0,1,0.

  • Thus, the sequence corresponding to 1250 is 0,1,0,0,3,0,1.

Proof of work

10000,(;      # Push an array of all integers from 1 to 9999.
{             # For each integer “N”,
  f-1=0=      # if “f(N)” has a trailing zero,
  {0p}*       # print a message.
}/

leaves nothing on the stack, so f is well-defined.

1000,.        # Push the array of all integers from 0 to 999 and duplicate it.
[             #     
  {f g}/      # For each integer “N”, push “g(f(N))”.
]=            # Check if the array of the images matches the original array.

leaves 1 on the stack (using either definition of g).

This means that g is a left inverse of f, so f is injective.

[
  1000,.      # Push the array of all integers from 0 to 999 and duplicate it.
  10%-        # Remove the integers with trailing 0's.
  {           # For each integer “N”,
    10base    # push the array of its digits in base 10,
    .0\+.0\+  # and create copies with one and two leading 0's.
  }/          #
].            # Collect all sequences in an array and duplicate it.
[             #     
  {g f}/      # For each sequence “S”, push “f(g(S))”.
]=            # Check if the array of the images matches the original array.

leaves 1 on the stack (using the second definition of g).

This means that g is a right inverse of f, so f is surjective.

\$\endgroup\$
  • \$\begingroup\$ Would it save a character to define f inside g, like {:|;-1{).{[2base[0]/{,}/]-1%}:f|=!}do}:g? \$\endgroup\$ – algorithmshark May 5 '14 at 13:16
  • \$\begingroup\$ Sadly, that won't work. Inside g, the block defining f is pushed on the stack, but it doesn't get executed. You'd need to append ~ to :f to fix this. Also, f won't be defined until g has been executed at least once. \$\endgroup\$ – Dennis May 5 '14 at 14:29
5
\$\begingroup\$

J - 17 char

g=:(f=:_ q:>:)inv

We implement the prime exponent idea with this bijection—that's what the _ q: is doing, getting a list of the exponents of the primes of a number—except we also increment the input number by one before doing so, with >:, so that we don't forget 0, who doesn't have its own prime factorization.

For the definition of g, it's exactly what it looks like: instead of writing it ourselves, we just tell J to take the inverse of f. Arguably this is cheating, or just not interesting, but I think that the ability to do this is what makes J such an interesting language: J can often figure things out for you, allowing you to focus on expressing your solution instead of implementing it.

   i. 20
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
   f i. 20  NB. J pads with zeroes on right
0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0
0 1 0 0 0 0 0 0
2 0 0 0 0 0 0 0
0 0 1 0 0 0 0 0
1 1 0 0 0 0 0 0
0 0 0 1 0 0 0 0
3 0 0 0 0 0 0 0
0 2 0 0 0 0 0 0
1 0 1 0 0 0 0 0
0 0 0 0 1 0 0 0
2 1 0 0 0 0 0 0
0 0 0 0 0 1 0 0
1 0 0 1 0 0 0 0
0 1 1 0 0 0 0 0
4 0 0 0 0 0 0 0
0 0 0 0 0 0 1 0
1 2 0 0 0 0 0 0
0 0 0 0 0 0 0 1
2 0 1 0 0 0 0 0
   g f i. 20
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

Proving that this is a bijection is straightforward: the injectivity of this f is a well known fact and, if you assume that J's automagical inverse is correct (which it is), then this is trivial.

If you don't want to take it on faith that J knows how to take the inverse of f, we can inspect its automatic inverse for _&q::

   _&q: b. _1
(p:@i.@# */ .^ ])"1 :.(_&q:)

and then check the definition:

(p:@i.@# */ .^ ])"1 :.(_&q:)  NB. the alleged inverse of _&q:
                    :.(_&q:)  NB. defining _&q:inv inv to be _&q:
(               )"1           NB. operate on rows of the argument
       #                      NB. length of argument
    i.@                       NB. nonnegative integers less than
 p:@                          NB. n-th prime for each integer n
               ]              NB. the argument again
            .^                NB. pointwise exponentiation
         */                   NB. product

and then confirm that J's inverse of f gives the decrement of the result of this:

   >: b. _1  NB. inverse of increment is decrement
<:
   f b. _1   NB. ([: f g) is one way of writing f composed with g
[: <: (p:@i.@# */ .^ ])"1 :.(_&q:)
\$\endgroup\$
  • 3
    \$\begingroup\$ Function inverse as a built-in. I'm speechless. \$\endgroup\$ – Dennis May 8 '14 at 18:23
  • \$\begingroup\$ @Dennis J can also take derivatives. \$\endgroup\$ – algorithmshark May 8 '14 at 20:55
2
\$\begingroup\$

Jelly, 7 + 3 = 10 or 11 bytes, language postdates question

JÆN*¹P’
‘ÆE

Try it online!

Defines an packing function 1Ŀ and an unpacking function 2Ŀ. These could be defined in two separate programs, but if you define them both in a single program, you need a newline to separate the definitions. Thus I'm not 100% sure how to count it.

Explanation

This packs the sequence into a product of primes, which was one of the suggestions in the question.

Packing

JÆN*¹P’
J         Replace each element of {the input} by its index
 ÆN       Replace each index n by the nth prime number
   *      Raise each element to the power of
    ¹       {the original input}
     P    Take the product of all the elements
      ’   Subtract 1 (so that some sequence maps to 0, making a bijection)

Unpacking

‘ÆE
‘         Add 1 (undo the subtraction earlier)
 ÆE       Output the number of times each prime divides the current value

As can be seen, unpacking is very simple here due to the builtin ÆE, which is why I selected this format. There's no builtin to do the packing, but it has a fairly terse implementation too.

Jelly, 3 + 3 = 6 or 7 bytes, with some help from @Dennis

OK, apparently there is a builtin to do the packing…

ÆẸ’
‘ÆE

Try it online!

The explanation above still works; it's just that all of JÆN*¹P have been replaced by a builtin.

\$\endgroup\$
  • \$\begingroup\$ Jelly fact: This challenge is why those built-ins exist in the first place. \$\endgroup\$ – Dennis Feb 21 '17 at 2:33
  • \$\begingroup\$ Oh, hmm, in that case this answer probably violates a standard loophole (unintentionally). Postdated languages are fair enough, but languages features that were added for a challenge are invalid. (ÆE is useful for other things, though; however, I'm not sure ÆẸ is.) \$\endgroup\$ – user62131 Feb 21 '17 at 2:37
  • \$\begingroup\$ Considering that you couldn't have possibly known this, there is no problem. Most built-ins of golfing languages were inspired by older challenges. \$\endgroup\$ – Dennis Feb 21 '17 at 2:39
  • \$\begingroup\$ Right, but I was going along the lines of "if I see lots of challenges where a particular builtin helps, that builtin will likely come in useful in the future". For example, A Pear Tree's checksums were inspired by several specific past challenges, but I had a hunch that they'd come in useful on future challenges too, so they did. I haven't gone back to those past challenges and submitted A Pear Tree answers, though, because that would likely be cheating. \$\endgroup\$ – user62131 Feb 21 '17 at 2:41
  • \$\begingroup\$ It's not that ÆE isn't used in other challenges; I've used it plenty of times. But every since I saw the OP's answer to this challenge, I knew that if I ever made a language, it would include this built-in. In any case, the loophole exists to prevent people from making up a language to win every challenge. Posting the answer myself woyld have been a bit iffy, but since you discovered a general-purpose built-in that happens to work particularly well for this challenge, it's fine. \$\endgroup\$ – Dennis Feb 21 '17 at 2:44
1
\$\begingroup\$

Python, 257 265B

from itertools import*
T=lambda i:[list(a)for l in range(i)for a in product(range(i-l+3),repeat=l+1)if a[-1]>0and sum(a)==i-l]
def f(N):
 A,i=[[0]],0
 while len(A)<=N:A+=T(i);i+=1
 return A[N]
def g(t):
 A,i=[[0]],0
 while t not in A:A+=T(i);i+=1
 return A.index(t)

To list every sequence, for each integer i, for each length l

0 :  1
1 :  2
2 :  0 1
3 :  3
4 :  0 2
5 :  1 1
6 :  0 0 1
7 :  4
8 :  0 3
9 :  1 2
10 :  2 1
11 :  0 0 2
12 :  0 1 1
13 :  1 0 1
14 :  0 0 0 1
15 :  5
16 :  0 4
17 :  1 3
18 :  2 2
19 :  3 1
20 :  0 0 3
21 :  0 1 2
22 :  0 2 1
23 :  1 0 2
24 :  1 1 1
25 :  2 0 1
26 :  0 0 0 2
27 :  0 0 1 1
28 :  0 1 0 1
29 :  1 0 0 1
30 :  0 0 0 0 1

so f(256)=[9], and g([4,2,0,3])=2254. NB that this is SLOW for large numbers.

\$\endgroup\$
  • \$\begingroup\$ This answer is not quite right: in this question we consider 0 an element of N, so you have to account for the empty sequence and non-trailing zeroes in the sequences. Perhaps map 0 to [] and subtract one from every element except the last in the result of f? \$\endgroup\$ – algorithmshark May 4 '14 at 14:10
  • \$\begingroup\$ Oh yes I can do - sorry at uni N always meant N+ and we wrote Nu{0} for that so i was on autopilot. it'll actually save me a few digits when i get round to fixing it \$\endgroup\$ – alexander-brett May 4 '14 at 18:02
0
\$\begingroup\$

MATL, 8+3 = 11 bytes

Function f

QYF

Nice and simple, outputs the exponents of the prime factor decomposition of the input+1, for instance input of 1752922079 gives [5, 3, 1, 4, 0, 2]

Function g

Takes a finite vector of non-negative integers and outputs a single non-negative integer.

n:YqG^pq

Explanation

n       % find the length of the input
:       % make a range that long
Yq      % use the range to find the first n primes
G       % paste the input vector again
^       % take powers element wise
p       % product of elements
q       % decrement by 1 so 0 is included
        % (implicit) convert to string and display

For instance, input [5, 3, 1, 4, 0, 2] first pushes the vector [2, 3, 5, 7, 11, 13], then combines them into [32, 27, 5, 2401, 1, 169] before taking the product, giving 1752922080 and decrementing to give the final answer 1752922079.

\$\endgroup\$
  • \$\begingroup\$ The question asks for the functions to be defined, that is, assigned to some variable or name in the function namespace. (Preferably called f and g but some languages cough Jelly cough can't do the usual names.) I don't know how MATL works, but it doesn't look like this answer has done that. \$\endgroup\$ – algorithmshark Feb 21 '17 at 8:05
  • \$\begingroup\$ @algorithmshark Oh! Sorry about that... You're right, this answer hasn't done that - and to be honest I don't know if MATL allows it. I suspect not, since matlab functions must be defined in their own, separate, file and I don't know of support for anonymous functions in MATL. \$\endgroup\$ – B. Mehta Feb 21 '17 at 11:53

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.