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.

Improve this question
\$\endgroup\$
23
  • 4
    \$\begingroup\$ What precisely is a diff? \$\endgroup\$
    – Conor O'Brien
    Aug 2, 2016 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, 2016 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, 2017 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, 2017 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, 2017 at 18:44

1 Answer 1

Reset to default
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

Improve this answer
\$\endgroup\$
7
  • 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, 2017 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, 2017 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, 2017 at 22:56
  • \$\begingroup\$ @ais523: OK I misunderstood. \$\endgroup\$
    – sergiol
    Jan 16, 2017 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, 2017 at 17:43

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