10
\$\begingroup\$

preface

In a very heated situation you have to go even further with golfing.
(e.g. in a challenge where your answer is 100 characters long and it is just embarrassing that you couldn't make it 99)
In that case, from now on you use the winner's algorithm of this challenge :)

goal

You have to write a program that takes an uint32 and returns the most compressed form.

$ mathpack 147456
9<<14
  • There will be multiple solutions for a number. Pick the shortest one
  • If the compressed form is longer or equal to the original number, return the original number

rules

  • write in any language - output in any language
  • i'm aware of that in C 'abc' is 6382179 and you can achieve pretty good results with this conversion. but languages are separated in this challenge so don't lose heart
  • it is prohibited to use external variables. only operators and literals and math related functions!

scoring

here are the test cases: pastebin.com/0bYPzUhX
your score (percent) will be the ratio of
byte_size_of_your_output / byte_size_of_the_list without line breaks.
(you have to do this by yourself as i'll just verify the best codes just in case)
winners will be chosen by score and language of output!

examples:

$ mathpack 147456 | mathpack 97787584 |  mathpack 387420489
            9<<14 |           9e7^9e6 |            pow(9,9)
\$\endgroup\$
  • \$\begingroup\$ Lovely challenge, but you should add in a rule against hard coding. \$\endgroup\$ – ɐɔıʇǝɥʇuʎs Jul 7 '14 at 15:31
  • \$\begingroup\$ y-you mean hardcoding 10k cases? although i would be glad to get some support on how to refine this challenge \$\endgroup\$ – bebe Jul 7 '14 at 15:33
  • \$\begingroup\$ edited (again and again...) for clarity. thanks for the advices. \$\endgroup\$ – bebe Jul 7 '14 at 16:18
  • \$\begingroup\$ Wouldn't this also be [rosetta-stone]? Also: write in any language - output in any language - the two languages can be different, right? \$\endgroup\$ – ɐɔıʇǝɥʇuʎs Jul 7 '14 at 19:26
  • \$\begingroup\$ @ɐɔıʇǝɥʇuʎs [rosetta-stone] is actually about you solving it in as many languages as possible. And yes to your latter question - that has been edited in response to me asking that same question. \$\endgroup\$ – Martin Ender Jul 7 '14 at 20:07
1
\$\begingroup\$

Code: Mathematica, Output: C, ~62.1518% (12674/20392)

I thought I'd also give C a try because of those funny character literals. Currently this is the only thing this answer is trying, and it's working quite well.

mathpack[n_] := Module[{versions, charLiteral},
   charLiteral = "'" <> StringReplace[Map[
        Switch[#,
          (*d_ /; d < 32,
          "\\" <> IntegerString[#, 8],*)
          10,
          "\\n",
          13,
          "\\r"
          39,
          "\\'",
          92 ,
          "\\\\",
          _,
          FromCharacterCode@#] &,
        FromDigits[#, 
           2] & /@ (Partition[PadLeft[IntegerDigits[n, 2], 32], 
            8] //. {{0 ..} .., x__} :> {x})
        ] <> "",
      {(*"\\10" -> "\\b",
       "\\11" -> "\\t",
       "\\13" -> "\\v",
       "\\14" -> "\\f",*)
       RegularExpression["(?!<=\?)\?\?(?=[=/()!<>-]|$)"] -> "?\\?"
       }
      ] <> "'";
   versions = {ToString@n, charLiteral};
   SortBy[versions, StringLength][[1]]
 ];

I hope I didn't miss anything, but this answer makes sure to escape backslashes, single quotation marks as well as trigraphs. There is some commented out code that uses octal or other escape sequences for non-printable characters, but I don't think that's actually necessary, because C should be able to deal with any bytes in character literals, afaik (please correct me if I'm wrong).

As with the other submission, test this with

input = StringSplit[Import["path/to/benchmark.txt"]];
numbers = ToExpression /@ input;
output = mathpack /@ numbers;
N[StringLength[output <> ""]/StringLength[input <> ""]]
\$\endgroup\$
  • \$\begingroup\$ (On my system at least) GCC will accept any byte in single quotes except 10 (\n) and 13 (\r). A zero byte will compile OK, but with the error message warning: null character(s) preserved in literal. \$\endgroup\$ – squeamish ossifrage Jul 8 '14 at 16:53
  • \$\begingroup\$ @squeamishossifrage Thanks, fixed! \$\endgroup\$ – Martin Ender Jul 8 '14 at 19:24
3
\$\begingroup\$

Code: Mathematica, Output: Julia, ~98.9457% (20177/20392 bytes)

optimise[n_] := 
  Module[{bits, trimmedBits, shift, unshifted, nString, versions, 
    inverted, factorised, digits, trimmedDigits, exponent, base, 
    xored, ored, anded},
   nString = ToString@n;
   versions = {nString};

   (* Try bitshifting *)
   bits = IntegerDigits[n, 2];
   trimmedBits = bits /. {x___, 1, 0 ..} :> {x, 1};
   shift = ToString[Length[bits] - Length[trimmedBits]];
   unshifted = ToString@FromDigits[trimmedBits, 2];
   AppendTo[versions, unshifted <> "<<" <> shift];

   (* Try inverting *)
   inverted = ToString@FromDigits[1 - PadLeft[bits, 32], 2];
   AppendTo[versions, "~" <> inverted];

   (* Try invert/shift/invert *)
   trimmedBits = bits /. {x___, 0, 1 ..} :> {x, 1};
   shift = ToString[Length[bits] - Length[trimmedBits]];
   unshifted = ToString@FromDigits[trimmedBits, 2];
   AppendTo[versions, "~(~" <> unshifted <> "<<" <> shift <> ")"];

   (* Try factoring *)
   factorised = Riffle[
      FactorInteger[n]
        /. {a_, 1} :> ToString@a
       /. {a_Integer, b_Integer} :> ToString[a] <> "^" <> ToString[b]
      , "+"] <> "";
   AppendTo[versions, factorised];

   (* Try scientific notation *)
   digits = IntegerDigits[n, 10];
   trimmedDigits = digits /. {x___, d_ /; d > 0, 0 ..} :> {x, d};
   exponent = ToString[Length[digits] - Length[trimmedDigits]];
   base = ToString@FromDigits[trimmedDigits, 10];
   AppendTo[versions, base <> "e" <> exponent];

   (* Don't try hexadecimal notation. It's never shorter for 32-bit uints. *)
   (* Don't try base-36 or base-62, because parsing those requires 12 characters for
      parseint("...") *)

   SortBy[versions, StringLength][[1]]
  ];

mathpack[n_] := 
 Module[{versions, increments},
  increments = Range@9;
  versions = Join[
    optimise[#2] <> "+" <> ToString@# & @@@ ({#, n - #} &) /@ 
      Reverse@increments,
    {optimise@n},
    optimise[#2] <> "-" <> ToString@# & @@@ ({#, n + #} &) /@ 
      increments,
    optimise[#2] <> "*" <> ToString@# & @@@ 
      Cases[({#, n / #} &) /@ increments, {_, _Integer}],
    optimise[#2] <> "/" <> ToString@# & @@@ ({#, n * #} &) /@ 
      increments
    ];
  SortBy[versions, StringLength][[1]]
 ];

The function takes a number and returns the shortest string it finds. Currently it applies four simple optimisations (I might add more tomorrow).

You can apply it to the entire file (to measure its score) as follows:

input = StringSplit[Import["path/to/benchmark.txt"]];
numbers = ToExpression /@ input;
output = mathpack /@ numbers;
N[StringLength[output <> ""]/StringLength[input <> ""]]

Note that some of these optimisations assume that you're on a 64-bit Julia, such that integer literals give you an int64 by default. Otherwise, you'll be overflowing anyway for integers greater than 231. Using that assumption we can apply a few optimisations whose intermediate steps are actually even larger than 232.

EDIT: I added the optimisation suggested in the OP's examples to bitwise xor two large numbers in scientific notation (actually, for all of xor, or and and). Note that extending the xormap, ormap and andmap to include operands beyond 232 might help finding additional optimisations, but it doesn't work for the given test cases and only increases run time by something like a factor of 10.

EDIT: I shaved off another 16 bytes, by checking all n-9, n-8, ..., n+8, n+9 for whether any of those can be shortened, in which case I represented the number based on that, adding or subtracting the difference. There are a few cases, where one of those 18 numbers can be represented with 3 or more characters less than n itself, in which case I can make some extra savings. It takes about 30 seconds now to run it on all test cases, but of course, if someone actually "used" this function, he'd only run it on a single number, so it's still well under a second.

EDIT: Another incredible 4 bytes by doing the same for multiplication and division. 50 seconds now (the divided ones don't take as long, because I'm only checking these if the number is actually divisible by the factor of interest).

EDIT: Another optimisation that doesn't actually help with the given test set. This one could save a byte for things like 230 or 231. If we had uint64s instead, there'd be a lot of numbers where this could be a huge saving (basically, whenever the bit representation ends in a lot of 1s).

EDIT: Removed the xor, or, and optimisations altogether. I just noticed they don't even work in Julia, because (quite obviously) scientific notation gives you a float where bit-wise operators are not even defined. Interestingly, one or more of the newer optimisations seem to catch all of the cases that were shortened by these optimisations, because the score didn't change at all.

\$\endgroup\$
1
\$\begingroup\$

J to C (untested, but works in most cases, kind of a baseline answer.)

    f=:(,~ (($&0) @: (8&-) @: (8&|) @: #)) @: #:
    g=:($~ ((,&8) @: (%&8) @: #))@:f
    toCString=:({&a.)@:#.@:g
    toCString 6382179
abc    

Outputs an string literal that, if entered in C, represents the number (as mentioned in the OP). This is not a serious submission, but rather something to strengthen my J skills, that I thought I'd share.

Alternative one-liner:

toCString=:({&a.) @: #. @: ($~ ((,&8) @: (%&8) @: #))@: (,~ (($&0) @: (8&-) @: (8&|) @: #)) @: #:

What J tries to make of this when you input it:

{&a.@:#.@:($~ ,&8@:(%&8)@:#)@:(,~ $&0@:(8&-)@:(8&|)@:#)@:#:

Thanks a bunch, J. Also, for those in 'the know' about J, visio rocks for creating more complex functions:

enter image description here

\$\endgroup\$
  • \$\begingroup\$ Since I can't read any of it: what does this do if the character is non-printable, or if the character is \ , ? or '? \$\endgroup\$ – Martin Ender Jul 8 '14 at 15:07
  • \$\begingroup\$ @m.buettner Nothing (yet), I still have to build something for that \$\endgroup\$ – ɐɔıʇǝɥʇuʎs Jul 8 '14 at 15:18
  • \$\begingroup\$ Instead of m&u@:v, use m u v to save precious characters and to enhance readability. Applying this to your code, we get f =: [: (,~ 0 $~ 8 - 8 | #) #: and g =: [: ($~ 8 ,~ # % 8:) f and lastly toCString =: a. {~ [: #. g. All combined we get a. {~ [: #. [: ($~ 8 ,~ # % 8:) [: (,~ 0 $~ 8 - 8 | #) #:, which is really easy to read. \$\endgroup\$ – FUZxxl Mar 14 '15 at 17:22

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.