5
\$\begingroup\$

This challenge is inspired by a problem I encountered recently out in the real-world, though ultimately I cheated and found a workaround.

Challenge

The input is a space-separated table of characters (each line is a row, and every line will have the same number of columns). Your challenge is to group together co-occurring column values and output a 'compressed' table, and there may be duplicate rows. Let's look at an example:

input:

A X I
B X I
A Y I
B X I
B Y I

output:

AB XY I

The output is parsed as the cartesian product between each column:

AB XY = A X, B X, A Y, B Y

The union of cartesian products of columns in each output row must exactly match the set of all unique input rows. In other words, no skipping input rows and no specifying input rows that don't exist!

For further exampling, note that if the third column contained anything other than I, this would be harder to compress:

input:

A X I
B Y I
A Y $
B X I
B Y I

output:

A X I
A Y $
B XY I

Rules

  • no non-standard libraries or calls to high-level compression functions. The spirit of the question is to write the algorithm yourself!
  • output must be in the same format as inputs (zipping your output files is cheating)
  • no hard-coding the answers of each test file. Your program needs to be able to handle arbitrary (correct) inputs.

Scoring (lowest wins)

  • Size of your program in bytes (you may count the name of the input as a single byte)
  • Plus the size (in bytes) of all of your output files on the given tests.
  • -10% bonus if you have the fastest program (as it runs on my machine). Speed will be measured as the average time on 10 randomly generated test cases using generate.py 6 8 4 6 5 (the same 10 files for each program of course)

Test Files

These files are generated with this python script. The answer keys aren't guaranteed to be the minimum compression - you may be able to do better!

\$\endgroup\$
  • \$\begingroup\$ So... if a person takes the output generated by one of these programs, they should be able to recreate each unique row of data, and nothing more, correct? \$\endgroup\$ – Not that Charles May 7 '14 at 16:54
  • \$\begingroup\$ And... do I need to use a similar compression form, or will any form work provided a person can follow an algorithm to generate each unique row of data and nothing more? E.g., can my output for your example 2 look like 3:AXI|Y$;BXI|YI \$\endgroup\$ – Not that Charles May 7 '14 at 16:56
  • 1
    \$\begingroup\$ Yes, all unique rows of input can be generated from the output (which is how the generate script works). And no you may not use a different format for the output. Standardization. \$\endgroup\$ – wrongu May 7 '14 at 17:05
  • \$\begingroup\$ And "fastest program" on which benchmark file? The sum of the three given ones? \$\endgroup\$ – Martin Ender May 7 '14 at 17:14
  • 1
    \$\begingroup\$ This problem is known as Boolean tensor factorization. Finding the minimum number of output rows needed (Boolean tensor rank) is known to be NP-hard. \$\endgroup\$ – xnor May 8 '14 at 0:40
3
\$\begingroup\$

I'll start things off with the simplest possible answer.. According to my own specifications, the input file qualifies as a 'compression' of itself (albeit not a very efficient one).

Python: 22+3359+183735+239 with 10% bonus = 168619.5

print open('testfile').read()
\$\endgroup\$
  • \$\begingroup\$ This answer won't count for the 10% bonus once other answers are posted. That would be silly. \$\endgroup\$ – wrongu May 7 '14 at 17:07
  • 1
    \$\begingroup\$ it should, unless someone writes something actually faster (assembly, anyone?) \$\endgroup\$ – AJMansfield May 7 '14 at 18:03

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.