0

This was a question proposed by a friend of mine. Define an algorithm that, given 40 unique integers in the range 1-1000, returns 41 unique integers in this range. Given these 41 integers, we must then be able to map them back to our original 40.

Does anyone have any insights? I have an idea, but it definitely isn't eloquent.

Thanks!

EDIT: I think I may need to clarify with an example. One naive solution would be: find the largest number in the set of 40. Increment it by 1 and this is your 41st number. When converting back, just get rid of the largest number. This obviously fails when the largest number in the set is 1000.

  • To be clear, we're dealing with sets rather than sequences and therefore there is no order? – user7043 Jan 25 '14 at 18:36
  • Is this a real problem or should it be on Code Golf? – Aaronaught Jan 25 '14 at 20:49
  • Despite having written an answer, this question lacks crucial information: Does the original set have to be included in the result set? Are these sets or ordered lists? – Blrfl Jan 26 '14 at 0:48
  • It's not a real problem, only theoretical. Take it loosely. The original set doesn't have to be included in the result set, it just has to be reversible. Order doesn't matter either. – Championcake Jan 26 '14 at 2:05
  • If order can be preserved, you could implement wrapping (1000+1=1), and then the new generated digit could actually be a check digit! Add all the numbers together, mod 1000, and if it isn't unique you +1 until it is. Put it in a set position (always the last number, for instance), and then the answer is even easier. – BrianH Jan 26 '14 at 2:29
4

It is possible, there are 960/41 more sets of 41 numbers than sets of 40 numbers. Decide of any arbitrary mapping.

As and example of algorithmic mapping, we will consider an extended problem: adding N numbers starting from M to a set (the original problem can be solved by adding 1 number starting from 1 to the set).

If M is not present in the set, add M to the set and then add N-1 numbers starting from M+1 to the set. If M is present in the set, remove M from the set and add N+1 numbers starting from M+1 to the set.

To decode, we have to remove N numbers starting from M from a set (the original problem can be solved by removing 1 number starting from 1).

If M is present in the set, remove M from the set and then remove N-1 numbers starting from M+1. If M is not present in the set, add M to the set and then remove N+1 numbers starting from M+1.

Another way of seeing this, is to consider the set as a bit set. Then the encode and decode procedure are the same: flip the bits from the first one until you get the number of element you want in the set.

Here is a lisp encoder

(defun encode (l)
  (helper 1 1 l nil))

(defun decode (l)
  (helper -1 1 l nil))

(defun helper (cnt cur rem res)
  (cond
   ((= cnt 0)
    (append res rem))
   ((or (null rem) (/= cur (car rem)))
    (helper (- cnt 1) (+ cur 1) rem (append res (list cur))))
   (t
    (helper (+ cnt 1) (+ cur 1) (cdr rem) res))))

and what you get when starting from a set of 3 elements.

(1 2 3) -> (4 5 6 7)
(1 2 4) -> (3 5 6 7)
(1 2 5) -> (3 4 6 7)
(1 2 a) -> (3 4 5 a)
(1 3 4) -> (2 5 6 7)
(1 3 5) -> (2 4 6 7)
(1 3 a) -> (2 4 5 a)
(1 a b) -> (2 3 a b)
(a b c) -> (1 a b c)
  • How will this work when all 40 numbers are last numbers of the 1000? – Euphoric Jan 25 '14 at 22:40
  • It will just add 1 to set. – AProgrammer Jan 25 '14 at 22:43
  • @poke Nowhere does it say that. You just simplified that. – Euphoric Jan 25 '14 at 22:45
  • I like the bit set explanation, much easier to imagine. Also, you can simplify this by flipping from first bit (eg number 1) instead of first number in set. Then you don't have to worry about overflow. – Euphoric Jan 25 '14 at 22:50
  • This is similar the the solution I came up with, but way more elegant. I was basically shifting the lowest number by 1. If a collision occurs, shift the lowest 2 numbers by 2, and so on. This generalized way of looking at it is excellent. – Championcake Jan 26 '14 at 2:13
1

You can order all 40-sets, like:

{1,2,...,40}
{1,2,...,38,39,41}
...
{961,...,1000}

You can order all 41-sets as well (there is more of them).

So just count the order of your 40-set, and return the 41-set at the same position.

(code to perform it is not trivial to make, but should not be really hard with some playing with multiplications and modulus)

1

Edit: This answer is based on the incorrect assumption that the OP wanted the original 40 integers to be included in the set of 41. As such, it's wrong but I am leaving it for now because it adds an interesting twist to the problem.

I don't know if this is possible with a set of 40 numbers, but it is possible to add an unique integer to sets of one or two numbers and get it back out. Here's the decoding logic for these two cases:

Set of 1: If the numbers in the encoded set are consecutive, the added number is the larger number, else the added number is the smaller of the two.

Set of 2: If any two numbers in the encoded set are separated by a gap of one or less, the added number is the number that is not part of this pair, else the added number is the one that falls between the smallest and largest numbers.

It might be possible able construct encoding/decoding logic for sets of 3, 4, 5 ... 998. It is not possible to creating decoding logic for a set of 999. 999 Doesn't work because there is only one missing number in its set and the encoded set will fill in that one missing number, resulting in a set containing every number from 1 to 1000.

That's about as far my little brain can take it. The folks over at https://cs.stackexchange.com/ might be able to come up with a formal proof and method for determining exactly how large a set can be and still be reversible for your range of 1 to 1000.

0

Let's think about 4 unique integers in the range 1–10 first. We get the input set I = {1, 2, 3, 4}. We have to produce an output set O with |O| = |I| + 1. The most trivial solution is to return the input set and the smallest unused number n:

n = min([1, ..., 10] \ I)
O = I u {n}

This is now a mapping I → O. The reverse operation can be implemented by remembering the pair (I, O) and looking the other set up. There is no way to get the original set without storing this connection!

If we want to have a mapping o → i forall o in O with i in I, then we can map each number to itself except n which could map to the lowest number in I. This means we have to remember the n separately.

As Python code:

numbers = range(1, 10+1)
def create_mapping(I):
  for n in numbers:
    if not n in I:
      break
  return (I + [n], n)

def map_back(mapping, x):
  O, n = mapping
  if x == n:
    return min(O)
  if x in O:
    return x
  return None

I = range(1, 5)
mapping = create_mapping(I)
back =  [map_back(mapping, x) for x in range(1, 10+1)]
assert back == [1, 2, 3, 4, 1, None, None, None, None, None]

Also:

O, _ = mapping
assert set(I) == set(map_back(mapping, x) for x in O)

which means that the mapping is reversible

  • So your solution is correct, but I'm specifically talking about the case that no state is kept between the two operations. Given our set O, we do not know what the original input I is. The question is more about deriving some algorithm that could map the input to an output such that the output could be mapped back without any other information. – Championcake Jan 25 '14 at 17:10
  • @Championcake In principle, there's a lot of information transported by the numbers which you didn't choose. One might be able to choose the n so cleverly that some properties of the unchosen numbers tell us the location, something like asserting the sum is even/odd... I have to run some errands right now but I'm going to think about it. – amon Jan 25 '14 at 17:20
0

Edit: This answer assumes the set of 41 has to include the original set of 40.


You really have two problems:

Finding a 41st Number

What you're looking for here is a gap where you can sneak in a new number, so the first thing you'll need to do is sort it.

With your sorted list in hand, the easy shortcuts are to see if there's a gap at the beginning (first number is greater than 1) or the end (last number is less than 1,000). If either of those is true, the 41st item can be 1 or a 1,000 depending on which it is. You're done.

If the sorted list contains 1 and 1,000, you have to traverse it until you find two adjacent numbers that have a difference greater than one. The space between those two numbers represent the gap, and the 41st item is some number in that gap. The easiest thing to do would be one greater than the lesser of the two numbers of one less than the greater.

Restoring the Original 40 Numbers

Your friend's problem has a flaw in that it doesn't provide any information about how the original set of 40 numbers are provided (unordered set, list, etc.) or how the set containing the 41st number should be returned.

If the sets provided and returned are actually a 40-item ordered (just ordered, not necessarily sorted) list, the new number can be appended as the 41st item and then lopped off later to get back to the original.

If the sets are unordered, there's no way to figure out which item has to be removed to restore the original 40. You just don't know what was added.

You might think there's some clever way of giving the number you add some intelligence that will reveal the identity of the added number when you're handed a set of 41 later, but there isn't. Someone who knows your algorithm could construct a valid set of 40 that will result in a set of 41 that yields the wrong answer when cut back to 40.

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.