Take the 2-minute tour ×
Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It's 100% free, no registration required.

Challenge

For any given input Y of length >= 1024 bytes:

  • sort in ascending or descending order -- your choice
  • generate output Q, where Q = [sorted data] + [restore information]
  • restore Y using Q as input

Sorting Example

 input: [2, 5, 119, 0, 1, 223, 0, 118, ...]
output: [0, 0, 1, 2, 5, 118, 119, 223, ...] + [restore information]

Restore Example

 input: [0, 0, 1, 2, 5, 118, 119, 223, ...] + [restore information]
output: [2, 5, 119, 0, 1, 223, 0, 118, ...]

Winning

The program that generates the least amount of information in order to restore to original state wins, however it must work within a reasonable amount of time on modern hardware, less than 10 minutes.

UPDATE 1

You may use any third party libraries that are open-source if you so desire.

UPDATE 2

The [restore information] size is measured in bytes, it's your choice what it contains.

UPDATE 3

In case it's not yet clear, the input Y is a stream of bytes, you shouldn't care what it contains, all you care is to sort the values of the bytes in the order you prefer while also generating the necessary data in order to restore to Y from Q.

share|improve this question
    
Are third party libraries allowed? I'd rather not write my own implementation of arithmetic coding –  James_pic Aug 2 at 13:13
    
@James_pic yes, so long as the libs are open-source, I've updated the post. –  ComputerSaysNo Aug 2 at 13:22
    
Is the information amount measured in bytes, characters or values? –  Sieg Aug 2 at 13:31
    
@Sieg in bytes, I've updated post. –  ComputerSaysNo Aug 2 at 13:37
    
Can the program be given a flag to differentiate when it should sort or restore? It's impossible to detect otherwise. –  Sieg Aug 2 at 15:37

6 Answers 6

up vote 6 down vote accepted

Python

The restore information is just the original list. n bytes of restore information for an n byte list.

def sort(Y):
  return (sorted(Y), Y)

def restore(Q):
  return Q[1]
share|improve this answer
    
ha-ha, this is wicked!! I like how you took the simplest approach (: –  ComputerSaysNo Aug 2 at 15:59
1  
Indeed, I think this is the most efficient solution in the long run (actually a Huffman encoded version could beat it) –  Sieg Aug 2 at 16:20
    
I agree, in the general case I don't think you can beat a (compressed) copy of the original data. –  Matteo Italia Aug 2 at 17:45
    
You can certainly beat a compressed copy of the original data. Making a separate copy wastes all the information the sorted list gives you about how many of each byte are in the list. –  user2357112 Aug 2 at 17:53
4  
Well, there are 256^n unsorted lists of bytes. There are only about choose(n, 256) ~ n^256 sorted lists of bytes. That's exponential vs. polynomial. So asymptotically knowing the sorted list doesn't help reconstruct the unsorted list. –  Keith Randall Aug 2 at 21:11

Python 2.x - Score ?

I acrually have no idea how to calculate the score in this case. I use bubble sort and log the swaps along the way. Now, these swaps can then be applied in reversed order to get the original list back. Give the program a -r flag when restoring (ie. file.py -r)

I have a feeling the most optimal way in the long run is to just save the indexes for each value. But that isn't fun.

import sys
import binascii

def sort(data):
    swaps = ''
    swapped = True
    while swapped:
        swapped = False
        for i in xrange(len(data)-1):
            if data[i] > data[i+1]:
                temp = data[i]
                data[i] = data[i+1]
                data[i+1] = temp
                swapped = True
                swaps += '1'
            else:
                swaps += '0'
    swaps = swaps[:-len(data)+1]
    swaps += '0'
    while len(swaps) % 8 != 0:
        swaps += '1'
    swaps = int(swaps, 2)
    swaps = binascii.unhexlify('%x' % swaps)
    return ''.join(map(chr, data)) + swaps + binascii.unhexlify('%08x' % len(swaps))

def unsort(data, swaps):
    swaps = bin(int(binascii.hexlify(swaps), 16))[2:]
    swaps = swaps[::-1]
    while swaps[0] != '0':
        swaps = swaps[1:]
    swaps = swaps[1:]
    datalen = len(data) - 2
    i = datalen
    for s in swaps:
        if s == '1':
            temp = data[i]
            data[i] = data[i+1]
            data[i+1] = temp
        i -= 1
        if i < 0:
            i = datalen
    return ''.join(map(chr, data))

if __name__ == '__main__':
    if len(sys.argv) > 1 and sys.argv[1] == '-r':
        data = sys.stdin.read()
        size = int(binascii.hexlify(data[-4:]), 16)
        swaps = data[-size-4:-4]
        data = map(ord, data[:-size-4])
        print unsort(data, swaps)
    else:
        data = map(ord, sys.stdin.read())
        sys.stdout.write(sort(data))
        sys.stdout.flush()

Example:

In:  94731
Out: 13479 ÷╚⌂

-r flag
In:  13479 ÷╚⌂
Out: 94731
share|improve this answer
    
this doesn't work for me, with python 2.7.8, I've ran [python test.py < sample.txt] where sample.txt is a text file that contains 1024 bytes, each byte is 0x31 or ASCII '1' and got as output: Traceback (most recent call last):/File "test.py", line 50, in <module>/print "%s + %s" % sort(data)/File "test.py", line 8, in sort/for i in xrange(len(data)-1):/TypeError: object of type 'long' has no len() –  ComputerSaysNo Aug 2 at 14:57
    
@ComputerSaysNo Note that the input format you specified starts with a [ and ends with a ]. I'm not sure what else could cause that. –  Sieg Aug 2 at 15:12
    
the '[' and ']' are just for illustration purposes, these characters may or may not be present within the input which is basically a stream of bytes to be sorted, I've modified my sample file to include the chars and added 0x32 or ASCII '2' as the first byte after '[', i.e. '[2111111111...1]' and it doesn't put '2' as last value in the print, would have expected '[111111...12]' as output, yet the output was the same as the input with the [restore info] data. –  ComputerSaysNo Aug 2 at 15:26
    
@ComputerSaysNo You should edit your question. At the moment it doesn't say that the input is a byte stream, yet it shows an example with a normal array/list. I thought the input would be given in similar lists, in similar format. –  Sieg Aug 2 at 15:28
    
I've updated the post, however, the question starts with [For any given input Y of length >= 1024 bytes:], I thought it was clear, but I realize now that it's clear only to me, sorry for confusion! –  ComputerSaysNo Aug 2 at 15:34

Scala + Arithmetic coding

Once we sort the data, all we're left with is the frequencies of the bytes within the original. Conveniently, this is exactly what we need for efficient adaptive arithmetic coding. We use arithmetic coding on the frequencies of the remaining elements of the data. I suspect this is information theoretically optimal, for random data.

I've used nayuki's arithmetic coding library.

import nayuki.arithcode._
import java.io.ByteArrayOutputStream
import java.io.ByteArrayInputStream
import java.nio.charset.StandardCharsets.UTF_8

object Unsort {
  def mkTable(data: Array[Byte]) = {
    val frequencyMap = data.groupBy(identity).mapValues(_.size)
    val frequencyArray = (0 to 255).map(i => frequencyMap.getOrElse(i.toByte, 0)).toArray
    new RemainingFrequencies(frequencyArray)
  }

  def sort(data: Array[Byte]) = {
    val freqTable = mkTable(data)
    val output = new ByteArrayOutputStream
    val bitOutput = new BitOutputStream(output)
    val encoder = new ArithmeticEncoder(bitOutput)
    for (b <- data) {
      val i = b.toInt & 0xff
      encoder.write(freqTable, i)
      freqTable.decrement(i)
    }
    encoder.finish()
    bitOutput.close()
    (data.sorted, output.toByteArray)
  }

  def unsort(dataAndMetadata: (Array[Byte], Array[Byte])) = {
    val (data, metadata) = dataAndMetadata
    val freqTable = mkTable(data)
    val input = new ByteArrayInputStream(metadata)
    val bitInput = new BitInputStream(input)
    val decoder = new ArithmeticDecoder(bitInput)
    (for (_ <- 0 until data.length) yield {
      val x = decoder.read(freqTable)
      freqTable.decrement(x)
      x.toByte
    }).toArray
  }

  def main(args: Array[String]) = {
    val stringData = args.reduce(_ + " " +_)
    val data = stringData.getBytes(UTF_8)
    val (sorted, metadata) = sort(data)
    val unsorted = unsort((sorted, metadata))
    val unsortedString = new String(unsorted, UTF_8)
    println(s"""Received "${stringData}"""")
    println(s"""Sorted to ${sorted.toList} + ${metadata.toList}""")
    println(s"""(${sorted.length} bytes of data, ${metadata.length} bytes of metadata)""")
    println(s"""Unsorted to "$unsortedString"""")
  }
}

class RemainingFrequencies(private val frequencies: Array[Int]) extends FrequencyTable {
  override val getSymbolLimit = 256
  override def get(symbol: Int) = frequencies(symbol)
  override def set(symbol: Int, freq: Int) = ???
  override def increment(symbol: Int) = ???
  override def getTotal = frequencies.sum
  override def getLow(symbol: Int) = frequencies.slice(0, symbol).sum
  override def getHigh(symbol: Int) = frequencies.slice(0, symbol + 1).sum
  def decrement(symbol: Int) = frequencies(symbol) -= 1
}

As an example of the output, here's what happens when we run it against the first paragraph of Franz Kafka's Metamorphosis:

Received "One morning, when Gregor Samsa woke from troubled dreams, he found himself transformed in his bed into a horrible vermin. He lay on his armour-like back, and if he lifted his head a little he could see his brown belly, slightly domed and divided by arches into stiff sections. The bedding was hardly able to cover it and seemed ready to slide off any moment. His many legs, pitifully thin compared with the size of the rest of him, waved about helplessly as he looked."
Sorted to List(32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 44, 44, 44, 44, 44, 44, 45, 46, 46, 46, 46, 71, 72, 72, 79, 83, 84, 97, 97, 97, 97, 97, 97, 97, 97, 97, 97, 97, 97, 97, 97, 97, 97, 97, 97, 97, 97, 97, 97, 97, 97, 98, 98, 98, 98, 98, 98, 98, 98, 98, 98, 99, 99, 99, 99, 99, 99, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 101, 101, 101, 101, 101, 101, 101, 101, 101, 101, 101, 101, 101, 101, 101, 101, 101, 101, 101, 101, 101, 101, 101, 101, 101, 101, 101, 101, 101, 101, 101, 101, 101, 101, 101, 101, 101, 101, 101, 101, 101, 101, 101, 101, 101, 101, 101, 102, 102, 102, 102, 102, 102, 102, 102, 102, 102, 102, 102, 102, 103, 103, 103, 103, 103, 104, 104, 104, 104, 104, 104, 104, 104, 104, 104, 104, 104, 104, 104, 104, 104, 104, 104, 104, 104, 104, 104, 105, 105, 105, 105, 105, 105, 105, 105, 105, 105, 105, 105, 105, 105, 105, 105, 105, 105, 105, 105, 105, 105, 105, 105, 105, 105, 105, 105, 105, 105, 107, 107, 107, 107, 108, 108, 108, 108, 108, 108, 108, 108, 108, 108, 108, 108, 108, 108, 108, 108, 108, 108, 108, 108, 108, 108, 108, 109, 109, 109, 109, 109, 109, 109, 109, 109, 109, 109, 109, 109, 109, 109, 110, 110, 110, 110, 110, 110, 110, 110, 110, 110, 110, 110, 110, 110, 110, 110, 110, 110, 110, 110, 110, 111, 111, 111, 111, 111, 111, 111, 111, 111, 111, 111, 111, 111, 111, 111, 111, 111, 111, 111, 111, 111, 111, 111, 111, 111, 111, 111, 112, 112, 112, 114, 114, 114, 114, 114, 114, 114, 114, 114, 114, 114, 114, 114, 114, 114, 114, 114, 114, 114, 114, 115, 115, 115, 115, 115, 115, 115, 115, 115, 115, 115, 115, 115, 115, 115, 115, 115, 115, 115, 115, 115, 115, 115, 115, 116, 116, 116, 116, 116, 116, 116, 116, 116, 116, 116, 116, 116, 116, 116, 116, 116, 116, 116, 116, 116, 117, 117, 117, 117, 117, 117, 118, 118, 118, 118, 119, 119, 119, 119, 119, 119, 121, 121, 121, 121, 121, 121, 121, 121, 121, 121, 122) + List(53, -2, -48, 47, 98, -11, -73, 89, 24, -16, 122, -22, -52, -112, 110, -5, -47, -93, 33, -78, 30, 101, -75, 105, 48, -118, 86, -94, -111, 6, 99, 80, 123, 106, 114, -94, -106, -56, -14, 85, -81, -111, 4, -65, 10, -38, -56, -83, 73, 51, -80, 34, -116, 112, -125, -89, -107, 77, 69, -123, -121, -55, 104, 24, 105, 93, 60, -88, 50, -117, 21, -17, 119, 56, 51, -53, 63, 116, -48, 13, -35, 67, -3, -73, -126, 58, -117, 19, -24, -18, -18, -73, -108, -3, -100, 30, 47, -32, -52, -22, -108, 37, 110, 79, -37, -78, -2, 72, 99, -42, 30, 102, -70, -33, -52, -32, -109, -37, 104, 26, 126, 67, 80, 101, 15, 1, -101, 21, -38, -95, 32, -24, 12, -75, -92, 28, 124, -65, 39, -58, 68, -58, 70, -90, -17, -29, -12, 1, 37, 84, 91, 61, 13, -28, 73, -112, -47, 42, -12, 64, -21, -95, 67, -113, -109, 28, 67, 35, -13, 81, -109, -49, 63, -20, -98, -112, 64, -53, 51, -96, -49, -111, 28, 46, 97, 77, -115, 78, -61, 110, 105, -4, -88, 0, -127, -66, -59, -65, -4, -105, -120, 53, 49, 2, 60, -7, -83, -102, -128, -118, -77, 77, 28, -126, 58, 16, 4, 70, 28, 91, 96, -73, 29, -126, -6, 8, 112, 122, 40, 48, -45, 0, 24, -91, -5, -59, 61, 122, -96)
(468 bytes of data, 239 bytes of metadata)
Unsorted to "One morning, when Gregor Samsa woke from troubled dreams, he found himself transformed in his bed into a horrible vermin. He lay on his armour-like back, and if he lifted his head a little he could see his brown belly, slightly domed and divided by arches into stiff sections. The bedding was hardly able to cover it and seemed ready to slide off any moment. His many legs, pitifully thin compared with the size of the rest of him, waved about helplessly as he looked."

It's only 468 bytes, but still an interesting test. The metadata used to unsort it is 239 bytes.

When I tested it against 4096 bytes of random data (not shown), the metadata was 3967 bytes.

share|improve this answer
    
wow, I wasn't expecting this, very good job! it would be interesting to see the metadata size if, for example, the input would contain random bytes from 0 to 255, I expect somewhere around 80%+ of original data. –  ComputerSaysNo Aug 3 at 8:17
1  
@ComputerSaysNo That'd be my expectation as well, for the simple reason that the sorted version tells us very little about the sequence in that case - it tells us there are roughly equal numbers of each character. I'll try it with some random data when I get chance. –  James_pic Aug 3 at 9:56

Theoretical solution:

Will work, but chances for it to complete within the time limit are pretty low.

Through brute-force search I try to find any random seed that, when used to shuffle of the original indexes, happens to create exactly the ordered list.

Sample output:

Input: [185, 60, 253, 77, 64, 146, 155, 66]
Sorted: [60, 64, 66, 77, 146, 155, 185, 253] 7099

Now if I could just figure out how to speed this up a little... ;)

public class SortRestore {

  public static void main(String[] args) {
    final Random rnd = new Random(123);
    final int[] input = IntStream.iterate(rnd.nextInt(256), s -> rnd.nextInt(256)).limit(2048).toArray();
    System.out.println("Input: " + Arrays.toString(input));
    final int[] sorted = Arrays.copyOf(input, input.length);
    Arrays.parallelSort(sorted);
    System.out.print("Sorted: " + Arrays.toString(sorted) + " ");
    final List<Integer> indexBase = IntStream.range(0, input.length).boxed().collect(Collectors.toList());

    IntStream.rangeClosed(0, Integer.MAX_VALUE).parallel()
            .filter(seed -> {
              final List<Integer> indexes = new ArrayList<>(indexBase);
              Collections.shuffle(indexes, new Random(seed));
              for (int i = 0; i < input.length; ++i) {
                if (input[i] != sorted[indexes.get(i)]) {
                  return false;
                }
              }
              return true;
            }).limit(1)
            .forEach(System.out::println);
  }
}
share|improve this answer
    
You'll be limited by the number of bits in your seed. Most RNGs take a fixed size seed - often between 64 and 1024 bits. A 1024 byte input will have 8192 bits, so most RNGs won't have a seed for every possibility –  James_pic Aug 3 at 20:33

Performs selection sort and records all the swaps.

Input: [15, 18, 1, 6, 2, 16, 13]

Output: [1, 2, 6, 13, 15, 16, 18] [(0, 2), (1, 4), (2, 3), (3, 6), (4, 6)]

Also: list == restore(*sort(list))

def swap(l, indexes):
    l[indexes[0]], l[indexes[1]] = l[indexes[1]], l[indexes[0]]

def sort(l):
    restore = []
    for i in range(len(l)-1):
        m = min(l[i+1:])
        if l[i] > m:
            restore.append((i,l.index(m)))
            swap(l, restore[-1])

    return l, restore

def restore(l, restore):
    restore.reverse()
    for i in restore:
        swap(l,i)
    return l
share|improve this answer

J

Not sure how this should be scored, but it's a simple deal with J.

  • /:~ sorts the list.
  • A.@/:@/: gives the restoration information, an integer less than N! for a list of length N, which can be coded into ceil(log256 N!) bytes or less, using (256#.3&u:)inv, and decoded with (256#.3&u:).

  • ((A.i.@#){]) takes the restoration integer on the left and the sorted array on the right.

The integer is literally a permutation number—that's what the A. is doing, converting between permutations and permutation numbers.

If you need a single program that can convert between the two, you're probably looking at something like:

(/:~;4 u:256#.inv A.@/:@/:) :(]{~i.@#@]A.~256#.3 u:[)

which sorts and gives the restore if it's used with one argument, or takes the restoration on the left and the sorted array on the right to fix it.

For the record, the J equivalent of Python's trivial solution, where the restoration information is the array itself, is the simple (;~/:~) :[.

share|improve this answer
    
+1 like your answer, not making much sense of the code logic -- read your comments, but still difficult to parse. –  ComputerSaysNo Aug 8 at 19:13

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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