Definition: a set is a datatype which allows testing of inclusion ("does set X contain element Y?") but does not have order. Its size is the number of distinct elements it contains.

Define an efficiently invertible injection from sets of k integers in the range 0 to 1000 inclusive to sets of k+1 integers in the range 0 to 1000 inclusive such that each set maps to a superset of itself. This is not possible for all k: indicate for what range of k your code works. An answer will not be accepted unless it works for at least one k > 4.

Equivalently, provide two functions:

  • f takes a set of integers between 0 and 1000 (inclusive), and outputs a set of integers in the same range. The output set contains all of the elements of the input set and exactly one element not in the input set.

  • g inverts f: that is to say, given the output of f it removes the element which f added, and gives back the input of f.

The winner: The encoder/decoder that can handle the longest input set for all permutations of a set of that length.

For sake of space, it is acceptable to post code for only the encoder or decoder, provided that it is clear that the other half the transcoder works.

Inspired by this question.

Edit:

This should be possible for sets of at least five.

Here is an example for a set of three (800 is an arbitrary number; the encoder's implementation and the actual input set will dictate what it is).

  • Input set: {78, 4, 5}
  • Output of f({78, 4, 5}): {78, 4, 5, 800}
  • Output of g({78, 4, 5, 800}): {4, 5, 78}
  • 3
    Oh, there you go, changing the rules. :( Please use the Sandbox next time. – Kendall Frey Jan 27 '14 at 19:16
  • I have a strong feeling that the new rules are going to make this ridiculously hard, if not impossible. Someone prove me wrong... – Kendall Frey Jan 27 '14 at 19:21
  • @KendallFrey: Sorry for the confusion. It always was my intent to have that that in the challenge; otherwise its way too easy. – poke Jan 27 '14 at 19:24
  • Whether this is possible or not seems to depend on interpretation of some rather vague terms. I think that you can probably define an interface for "set" which makes phase 2 unnecessary and makes the actual challenge rather less ambiguous. – Peter Taylor Jan 27 '14 at 22:19
  • Is there a restriction on the input set length? – php-dev Jan 28 '14 at 17:44

C#

void Encode(HashSet<int> set)
{
    set.Add((set.Single() + 1) % 1001);
}

void Decode(HashSet<int> set)
{
    set.Remove(set.Equals(new HashSet<int>() { 0, 1000 }) ? 0 : set.Max());
}

Works for a set of length 1.

  • I didn't explicitly state the requirement that makes this hard: the added integer must also be between 0 and 1000. Edited question to state this. – poke Jan 27 '14 at 19:16
  • 1
    @poke I've written a new solution. – Kendall Frey Jan 27 '14 at 19:30

C#

void Encode(HashSet<int> set)
{
    int x = set.Sum();
    int add;
    if (x % 2 == 0)
    {
        add = x / 2;
    }
    else
    {
        add = (x + 1001) / 2 % 1001;
    }
    set.Add(add);
}

void Decode(HashSet<int> set)
{
    int x = set.Sum();
    if (x % 3 == 1)
    {
        x += 1001;
    }
    else if (x % 3 == 2)
    {
        x -= 1001;
    }
    int remove = x / 3;
    set.Remove(remove);
}

Works for a set of length 2. This is a special case, and only works because 1001 is not divisible by 2 or 3.

  • Sorry, that fails for 61% of initial sets. – Hand-E-Food Jan 28 '14 at 1:36
  • @Hand-E-Food It worked with the ones I tried. Please provide a counter-example. – Kendall Frey Jan 28 '14 at 3:48
  • {0,3} {4,167} {50,851} {108,159} {512,640} {875,937} are some of them. I tried some of them manually and it looks like some odd numbers could benefit from +/-1001 and some even numbers would be better off without it in Decode. – Hand-E-Food Jan 28 '14 at 4:44
  • This (golfed) function can be used in a foreach loop to test the code against all combinations: IEnumerable<HashSet<int>>EnumerateNumberSet(int size){int[]numbers=new int[size];for(int i=0;i<size;i++)numbers[i]=i;var done=false;while(!done){yield return new HashSet<int>(numbers);for(int j=size-1;j>=0;j--){numbers[j]++;if(numbers[j]<=1000){for(int i=j+1;i<size;i++)numbers[i]=numbers[i-1]+1;break;}if(j==0&&numbers[j]>1000)done=true;}}} – Hand-E-Food Jan 28 '14 at 4:49
  • 1
    @Hand-E-Food The decoder had a bug. It's fixed now. – Kendall Frey Jan 28 '14 at 12:57

Perl 6

Phase 1:

sub add-value(@set) {
    return (0) unless @set.elems >= 1;
    @set .=sort;
    my $sum = [+] @set;
    for ^1009 -> $a {
        my $v = ($sum+$a) % 1009;
        next if $v > 1000;
        next if [or] $v «Z==» @set;
        return (@set, $v) if [and] remove-value((@set, $v)).sort Z== @set
    }
    die "Couldn't find anything for " ~ join(',', @set)
}

Yes, I used the function for phase 3 as extra check in phase 1. It fixes bugs.

Phase 2: Shuffle the set with @set.=pick(*)

Phase 3:

sub remove-value(@set) {
    return () if @set.elems <= 1;
    for ^1009 -> $a {
        for @set.sort -> $b {
            my $sum = 1009 R% [+] $a, @set.grep(* != $b);
            next if $sum > 1000;
            return @set.grep(* != $b) if $sum == $b
        }
    }
    die "Couldn't find anything for " ~ join(',', @set)
}

I lack a bit of processing power to run all combinations atm, but with some 200 random combinations of length 1 through 15 (each) I didn't get any doubles.

Little test script could take about a century or 2 generating roughly 1000! combinations, but will start checking them right after:

for (^1001).combinations -> @set {
    my @newset = add-value(@set);
    @newset = @newset.pick(*);
    my @oldset = remove-value(@newset);
    if not [and] (@oldset.sort() Z== @set.sort()) {
        say "failed for $count, added value $added";
        say join ',', @set.sort;
        say join ',', @oldset.sort;
        die 'bad result';
    }
}

How does it work:

  • first calculate $sum of all values already in the set
  • for 0 .. 1008 -> $a:
    • $v = sum + $a modulo 1009 (yes, I like prime numbers)
    • if the value $v is over 1000, then try the next number
    • if the value exists already in the set, we can't use it, try next number
    • if running the remove phase on this set gives the wrong result, try next number
    • yay, we found number that works!

Decoding:

  • if there's 0 or 1 elements, return empty set
  • sort the set to have consistent results
  • loop again over all numbers to calculate sum, but
    • get all sets with 1 element removed
    • calculate if that number equals the sum of the other numbers
    • if it's equal, we have a winner

The decoding just removes the first number it finds that equals the sum of the other digits. If none is found it finds the first number that equals the sum of the other numbers + 1. If none ... +2, etc.

Some perl6 syntax:

  • ^1009 is same as 0..1008 == (0,1,2,3,4,5,...,1007,1008)
  • [+] @set calculates sum of all elements of @set; [and] is also the and operator applied to a list of boolean values
  • Z is the zip operator, it zips 2 or more lists into a list of tuples: (1,2) Z (3,4) is same as ((1,3), (2,4))
  • Z== applies the == to each pair, giving a list of Booleans
  • 1009 R% $sum == $sum % 1009 standard modulo calculation
  • Can you add some commentary to explain how the algorithm works? – poke Jan 29 '14 at 2:04
  • @poke I've added some explanation and a little warning about the speed of the test script (just calculating and checking 1 solution for the 190-element set 0..89,900..999 takes 6 minutes since for a=1..16 the sum is already in the set, and for a=17..32 the remove function returns the wrong answer, 106 is added btw) – Ayiko Jan 30 '14 at 0:01

366 Characters - Python 2

i=lambda v,c,m,j:[h(s(v,m)+[j],x) for x in range(c+1)]
h=lambda v,c:hash(','.join(map(str,sorted(v)+[c])))%1001
a=lambda v,c=0:v+[h(v,c)] if t(h(v,c),v,c) else a(v,c+1)
s=lambda v,m:[n for n in v if n!=m ]
w=lambda v,c=0:s(v,o(v,c)[0]) if len(o(v,c))==1 else w(v,c+1)
o=lambda v,c:[m for m in v if h(s(v,m),c)==m]
t=lambda j,v,c:all([m not in i(v,c,m,j) for m in v])

Could probably be golfed more, I didn't spend too much time on it. Call a with a list of integers to add a number, and call w with a shuffled version of the new list to remove that number.

Works by appending a loop counter to the sequence, and choosing as the additional number the hash modulo 1001 the concatenated sequence. If the hash generated results in a sequence where there is only one number that can be removed to generate itself for every possible value of the loop counter up to the current one, then output the sequence. Otherwise increment the loop counter and try again. To decode, remove each item from the sequence and see if the hash value of the remaining sequence+loop counter is the removed value. If only one value matches these criteria, it is the solution, otherwise increment the loop counter and try again. This version will hang if faced with an unencodable sequence due to the entire space being taken up by hash collisions, but a check can trivially be added to the a function to simply output that the sequence is unencodable.

Confirmed to work for at least all sets of 2 or less, and works with decreasing probability for larger sets. Higher probabilities might be reachable with a better hash function but that would require more characters. I did some quick random sampling to see what the probability of being able to encode an input sequence of a given size was via this method (you'll notice the precision going down as I got less and less patient):

Size  Probability
  5     100.00%
 10     100.00%
 50     100.00%
100     100.00%
200     98.3%
400     73%
800     8%

Anyone who wants to play with it can use the following version which will output whether a sequence is or is not encodable:

i=lambda v,c,m,j:[h(s(v,m)+[j],x) for x in range(c+1)]
h=lambda v,c:hash(','.join(map(str,sorted(v)+[c])))%1001
a=lambda v,c=0:v+[h(v,c)] if t(h(v,c),v,c) else a(v,c+1) if len(set([n for m in v for n in i(v,c,m,h(v,c))]))<999 else None
s=lambda v,m:[n for n in v if n!=m ]
w=lambda v,c=0:s(v,o(v,c)[0]) if len(o(v,c))==1 else w(v,c+1)
o=lambda v,c:[m for m in v if h(s(v,m),c)==m]
t=lambda j,v,c:all([m not in i(v,c,m,j) for m in v])

if __name__ == "__main__":
    from random import shuffle,randrange,sample
    from operator import eq
    from itertools import combinations
    def random_combination(iterable, r):
        "Random selection from itertools.combinations(iterable, r)"
        pool = tuple(iterable)
        n = len(pool)
        indices = sorted(sample(xrange(n), r))
        return tuple(pool[i] for i in indices)
    valid=invalid=0
    for z in range(100): #change to test more cases
        r=list(sorted(random_combination(range(1001),randrange(1,100)))) #change to test longer sequences
        d=a(r)
        if d is None:
            invalid+=1
            continue
        shuffle(d)
        e=sorted(w(d))
        if not all(map(eq,r,e)):
            raise Exception("Incorrect",r)
        valid+=1
    print "%d Valid, %d Invalid"%(valid,invalid)

APL - 73 89 106+ characters, depending on the set's length

Note: So that it'd be easier for the OP to validate, I combined integer a with set b into set c. This way, he could view the set before phase 3 and after phase 3.

n←[enter set's length here]
z←(n+1)?1000
a←z[⍴z]
b←z[⍳(¯1+⍴z)]
c←a,b
c
c[n?n]←c[n?n]
c
c←c-a
d←¯1001×0⍷c
c←c+d
c←c[⍒c]
c←c+a
e←¯1+⍴c
c←e⍴c
a
b[⍒b]
c

Where n is equal to the set's length. Don't forget to set n at the top!

How it works:

n←[enter set's length here] stores the chosen length for the set as n

z←(n+1)?1000 creates an array called z that contains n + 1 unique random numbers from 0 to 1000. We will use the last number of z as the integer to add to the set of other unique numbers

a←z[⍴z] stores the last number of z, or z[length of z], as a, the number we will add to the set

b←z[⍳(¯1+⍴z)] stores all of the data in z, or z[0 thru length of z - 1], as b the set that a will be added to

c←a,b combines arrays a and b into one array, c

c displays c so the OP can see that I added a

c[n?n]←c[n?n] scrambles the data by swapping cells based on n unique random numbers

c, once again, displays c

c←c-a subtracts a from all of the values in c so as to nullify a, which was our added value

d←¯1001×0⍷c creates a new array by multiplying -1001 by a binary "map" of c (which finds our 0 for us and looks something like this: 0 0 0 1 0, where 1 marks the location of the 0 in c)

c←c+d adds to d to c in order to turn the 0 that used to be a into ¯1001, which is one above the maximum number, 1000

c←c[⍒c] orders our data in c from greatest to least. This pushes our ¯1001 all the way to the right

c←c+a restores our original data from b by reversing the c←c=a we did earlier

e←¯1+⍴c creates a variable, e, that is equal to the length of c - 1

c←e⍴c decreases the length of c by 1 and does so by creating a shape with a length equal to e, that contains the data from c, but does not have what used to be a because the length decreased and a was on the right end

a displays a

b[⍒b] displays b from greatest to least

c displays c

  • The question as posed seems to require that if the initial set is a and the final set is c then a intersect c = a and |c \ a| = 1. From your description, this doesn't seem to satisfy those constraints. – Peter Taylor Jan 30 '14 at 8:39
  • I'm not quite sure what you mean by this; however the program does indeed follow the rules. The first 6 lines of code generate a set of unique integers between 0 and 1000, b, and adds another unique integer to that set, a, which is stored as c. The two lines after that shuffle the set, and the rest of the lines output a new version of c in which a is non existent. – Gandalf the White Jan 30 '14 at 15:00
  • Ah, I misunderstood the part about "creating a shape". I think you've rather missed the point, though: c = b.add(a); d = c.remove(a); assert b.equals(d) is trivial in many languages, so if the question were asking for that it would have been downvoted into oblivion. – Peter Taylor Jan 30 '14 at 15:18

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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