przedmowa

W bardzo gorącej sytuacji musisz iść jeszcze dalej z golfem.
(np. w wyzwaniu, w którym twoja odpowiedź ma 100 znaków, a żenujące jest to, że nie udało ci się uzyskać 99 znaków).
W takim przypadku od teraz używasz algorytmu zwycięzcy tego wyzwania :)

cel

Musisz napisać program, który pobierze uint32 i zwróci najbardziej skompresowaną formę.

$ mathpack 147456
9<<14

• Będzie wiele rozwiązań dla liczby. Wybierz najkrótszy
• Jeśli skompresowany formularz jest dłuższy lub równy pierwotnemu numerowi, zwróć oryginalny numer

zasady

• pisz w dowolnym języku - wyjście w dowolnym języku
• Jestem świadomy, że C 'abc'jest 6382179i można osiągnąć całkiem dobre wyniki z tej konwersji. ale języki są rozdzielone w tym wyzwaniu, więc nie trać serca
• stosowanie zmiennych zewnętrznych jest zabronione. tylko operatory i literały oraz funkcje matematyczne!

punktacja

Oto przypadki testowe: pastebin.com/0bYPzUhX
Twój wynik (procent) będzie stosunkiem
byte_size_of_your_output / byte_size_of_the_list bez podziału linii .
(musisz to zrobić sam, ponieważ na wszelki wypadek zweryfikuję tylko najlepsze kody)
zwycięzcy zostaną wybrani według wyniku i języka wyjściowego !

przykłady:

$ mathpack 147456 | mathpack 97787584 |  mathpack 387420489
            9<<14 |           9e7^9e6 |            pow(9,9)

Kod: Mathematica, Wyjście: C, ~ 62,1518% (12674/20392)

Myślałem, że spróbuję również C z powodu tych zabawnych literałów postaci. Obecnie jest to jedyna rzecz, na którą próbuje odpowiedzieć ta odpowiedź, i działa całkiem dobrze.

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

Mam nadzieję, że niczego mi nie umknęło, ale ta odpowiedź pozwala uniknąć ukośników odwrotnych, pojedynczych cudzysłowów i kaligrafii. Jest jakiś skomentowany kod, który wykorzystuje ósemkowe lub inne sekwencje specjalne dla znaków niedrukowalnych, ale nie sądzę, żeby to rzeczywiście było konieczne, ponieważ C powinien być w stanie poradzić sobie z dowolnymi bajtami w literałach znaków, afaik (popraw mnie, jeśli ja 'Mylę).

Podobnie jak w przypadku innych zgłoszeń, przetestuj to za pomocą

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

Kod: Mathematica, Wyjście: Julia, ~ 98,9457% (20177/20392 bajtów)

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

Funkcja przyjmuje liczbę i zwraca najkrótszy znaleziony ciąg . Obecnie stosuje cztery proste optymalizacje (mogę dodać więcej jutro).

Możesz zastosować go do całego pliku (aby zmierzyć jego wynik) w następujący sposób:

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

Zauważ, że niektóre z tych optymalizacji zakładają, że korzystasz z 64-bitowej Julii, tak że literały całkowite int64domyślnie dają ci . W przeciwnym razie przepełnisz się i tak dla liczb całkowitych większych niż 2 ³¹ . Korzystając z tego założenia, możemy zastosować kilka optymalizacji, których kroki pośrednie są nawet większe niż 2 ³² .

EDIT: dodałem optymalizacji sugerowanego w przykładach PO do bitowe xor dwie duże liczby w notacji naukowej (faktycznie, dla wszystkich xor , lub i i ). Zauważ, że przedłużające xormap, ormapi andmapzawierać argumenty poza 2 ³² może pomóc w znalezieniu dodatkowe optymalizacje, ale to nie działa dla podanych przypadków testowych, a tylko zwiększa czas pracy przez coś w rodzaju 10-krotnie.

EDYCJA: Ogoliłem kolejne 16 bajtów, sprawdzając wszystkie, n-9, n-8, ..., n+8, n+9czy którekolwiek z nich można skrócić, w którym to przypadku przedstawiłem liczbę na podstawie tej wartości, dodając lub odejmując różnicę. Istnieje kilka przypadków, w których jedną z tych 18 liczb można przedstawić za pomocą 3 lub więcej znaków mniej niż ona nsama, w którym to przypadku mogę uzyskać dodatkowe oszczędności. Teraz zajmuje około 30 sekund, aby uruchomić go na wszystkich przypadkach testowych, ale oczywiście, jeśli ktoś faktycznie „użył” tej funkcji, uruchomiłby ją tylko na jednym numerze, więc jest to znacznie poniżej sekundy.

EDYCJA: Kolejne niesamowite 4 bajty, robiąc to samo dla mnożenia i dzielenia. Teraz 50 sekund (podzielone nie trwają tak długo, ponieważ sprawdzam je tylko wtedy, gdy liczba jest podzielna przez czynnik zainteresowania).

EDYCJA: Kolejna optymalizacja, która tak naprawdę nie pomaga w danym zestawie testowym. Ten może zaoszczędzić bajt na rzeczy takie jak 2 ³⁰ lub 2 ³¹ . Gdybyśmy mieli uint64s, byłoby wiele liczb, w których może to być ogromna oszczędność (w zasadzie za każdym razem, gdy reprezentacja bitowa kończy się na 1).

EDIT: Usunięto xor , lub , i optymalizacje w ogóle. Zauważyłem, że nawet nie działają w Julii, ponieważ (całkiem oczywiste) notacja naukowa daje swobodę, w której operatory bitowe nie są nawet zdefiniowane. Co ciekawe, jedna lub więcej nowszych optymalizacji wydaje się wychwytywać wszystkie przypadki, które zostały skrócone przez te optymalizacje, ponieważ wynik wcale się nie zmienił.

J do C (niesprawdzone, ale działa w większości przypadków, rodzaj odpowiedzi podstawowej).

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

Wypisuje literał łańcuchowy, który po wprowadzeniu w C reprezentuje liczbę (jak wspomniano w PO). To nie jest poważne podporządkowanie, ale raczej coś, co wzmocni moje umiejętności J, które myślałem, że się podzielę.

Alternatywna jednowarstwowa:

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

Co J próbuje z tego zrobić po wprowadzeniu:

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

Wielkie dzięki, J. Ponadto, dla osób znających się na J, Visio Rock za tworzenie bardziej złożonych funkcji: