20
\$\begingroup\$

For this challenge, you need to compress a diff. A diff is some data that represents the difference between two strings. For this challenge, you need to provide one or more programs that can:

  1. Input A and B, and output a diff, C
  2. Input A and C, and output B
  3. Input B and C, and output A

The goal is to make the diff, C, as small as possible. The diff can be anything: a string, a number, a blob of data. We just care about the size (number of bytes).

I have 50 test cases that can found on Github. Each test case consists of two space-separated URLs which point to the 2 files you need to diff. (These test cases originated from PPCG members' Github profiles. Thanks all!)

All three tasks above should take under a minute to run on a reasonably powered computer (for each test case).

Your score is equal to the total size (in bytes) of all 50 diffs, lower is better. Hardcoding diffs in your program is not allowed (I reserve the right to change the test cases to prevent hardcoding). Builtins that produce a diff (like diffutils) are not allowed.

\$\endgroup\$
  • 4
    \$\begingroup\$ What precisely is a diff? \$\endgroup\$ – Conor O'Brien Aug 2 '16 at 16:54
  • \$\begingroup\$ Anything you want it to be, really. Informally, its a string that represents the differences between A and B \$\endgroup\$ – Nathan Merrill Aug 2 '16 at 16:56
  • 1
    \$\begingroup\$ More link rot: numbering test case pairs by 1-base line index; both pairs of test cases 3, 13, 14, 15, 16, 17, 18, 19, 20, 21 are all 404. Outside of these, I managed to retrieve every other case. \$\endgroup\$ – H Walters Jan 16 '17 at 3:10
  • 3
    \$\begingroup\$ I'm closing this question because it is largely unanswered and many of the old links I was using as test cases no longer work. Feel free to update the question and reopen if you wish. \$\endgroup\$ – Nathan Merrill Jan 17 '17 at 16:10
  • 1
    \$\begingroup\$ Done. The GIST is gist.github.com/sethhillbrand/64066935e3f8c0fac75d75edd43c9ef8 The second file is a uuencoded archive of the 40 remaining pairs of test cases. \$\endgroup\$ – Seth Jan 17 '17 at 18:44
0
\$\begingroup\$

Is my answer valid?

set f [open commits.txt]
while {![eof $f]} {scan [gets $f] %s\ %s a b; puts [string compare $a $b]}
close $f

testable on: http://www.tutorialspoint.com/execute_tcl_online.php?PID=0Bw_CjBb95KQMNmd4QkxvQUFsTnM

\$\endgroup\$
  • 1
    \$\begingroup\$ You need to provide multiple programs (both a diff equivalent and a patch equivalent). If string compare diffs strings, it violates the "no builtins" rule. If it only compares strings (like the name suggests), it doesn't leave enough information to recreate a patch. \$\endgroup\$ – user62131 Jan 16 '17 at 22:50
  • \$\begingroup\$ @ais523: builtins I understood it as command line commands. I know that string compare does not generate info to create a page, but there is no place in the question asking for it. \$\endgroup\$ – sergiol Jan 16 '17 at 22:54
  • \$\begingroup\$ From the question, "2. Input A and C, and output B". This is something that your submitted program can't do, and that in fact no program could do (as it doesn't have enough information). \$\endgroup\$ – user62131 Jan 16 '17 at 22:56
  • \$\begingroup\$ @ais523: OK I misunderstood. \$\endgroup\$ – sergiol Jan 16 '17 at 23:03
  • \$\begingroup\$ @ais523: I don't think your statement is correct "in fact no program could do". If C is the diff between A and B, then given C and A, B is calculable. Maybe I missed your exact point \$\endgroup\$ – Seth Jan 17 '17 at 17:43

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