Using your Head is Permitted

January 2009 riddle

I had lots of fun with last month's riddle, and decided to make this month's riddle a follow-up to it. For this reason, this month's riddle starts with a warning:

Spoiler alert: The following description contains hints regarding the solution of last month's riddle. If you still mean to tackle that other riddle, you may want to hold on before you continue to this one.

The solution to last month's riddle had, at its core, the ability to pack the data from many integers into a single integer. For example, if we have an array of X0, ..., Xn-1 non-negative integers, we can encode all of it into a single integer as the sum of Xi*2i*width, once an appropriate value of width is chosen. For a person knowing n and width the information in the sum is equivalent to the information in the entire array.

Last month's riddle asked for a sorting procedure that sorts n integers in O(n) under a specified computational model. This month's riddle continues to use the same model (described there in full), and asks the question of whether O(n) really is the best one can hope for.

On the face of it, the obvious answer is "yes": one needs O(n) time merely to read the input array and to output the result array. However, this problem can be circumvented: if the information from an entire array can be packed into a single integer, this integer can be read/written in O(1).

Consider, therefore, the following procedure, given here in Python code:

def sorting(array):
  size=len(array)
  if size==0:
    return []
  minimum=min(array)
  nonnegative_array=[x-minimum for x in array]
  maximum=max(nonnegative_array)
  width=int(log(max(maximum,1))/log(2))+1
  encoded_array=encode(nonnegative_array,width)
  encoded_sorted_array=fast_sorting(encoded_array,size,width)
  sorted_array=decode(encoded_sorted_array,size,width)
  return [x+minimum for x in sorted_array]

def encode(array,width):
  encoded_array=0
  for i in range(len(array)):
    encoded_array+=array[i]<<(width*i)
  return encoded_array

def decode(array,size,width):
  decoded_array=[0]*size
  for i in range(size):
    decoded_array[i]=array & ((1<<width)-1)
    array>>=width
  return decoded_array
This implementation of "sorting" encodes an array as an integer, sends it to "fast_sorting", then gets a result and decodes it into an output array. Given an appropriate implementation of "fast_sorting", what the function "sorting" does is to sort the input array. Effectively, "fast_sorting" is the sorting routine, and all else is just code to handle reformatting of its input and output. Regardless of how much time it takes "sorting" to run, there is no reason to assume "fast_sorting" can't have a lower complexity than O(n).

This month's riddle: design an algorithm for "fast_sorting" n integers that takes O(1) time.

List of solvers:

Marcos Simões (8 January 21:54)

Elegant solutions can be submitted to the puzzlemaster at riddlesbrand.scso.com. Names of solvers will be posted on this page. Notify if you don't want your name to be mentioned.

The solution will be published at the end of the month.

Enjoy!

To solution

Back to main page