mathpack numeric literals

Question

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)

Answer 1

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 2³¹. Using that assumption we can apply a few optimisations whose intermediate steps are actually even larger than 2³².

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 2³² 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 2³⁰ or 2³¹. 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.

Answer 2

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 <> ""]]

Answer 3

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: