7
$\begingroup$

We all know a conspicuous member of our community got hitched recently. As most of us are not in Malta, and weren't able to fly there, I thought of a celebration question. Sort of.

The challenge is golfing a function (Mma only) that finds a prefix free encoding for the letters of two sentences.

The trick is that both sentences (given as parameters) must share the same encoding, with one of them written backwards.

The number of available symbols for the encoding is also a parameter for the function (always less than 10), and the function should attempt to find the shortest encoding for that number of symbols. There is no a-priori guarantee that a solution exists for every parameter set.

As an example, related to our celebration:

we wish you the best

and 

sz is the handsomest groom

Inspiration was taken from this question (which does not require a prefix free code), but is a good explanation of what is required.

Happy wedding and golfing!

Shortest code wins!

PS: A bounty of 100, a wedding garter and the party leftovers to the winner

EDIT Clarifications. To be updated as comments and answers arise

  1. No caps. Only lowercase.
  2. No need to encode whitespaces, special chars or punctuation (skip them and consider only lowercase letters)
  3. Your solution should be able to show up results before they are back from the honeymoon.
Improve this question
$\endgroup$
9
  • 5
    $\begingroup$ To close or not to close... hmmm. $\endgroup$
    – rm -rf ♦
    Commented Jul 30, 2012 at 1:31
  • 1
    $\begingroup$ @R.M Close it if you please, but don' delete tags :) $\endgroup$
    – Dr. belisarius
    Commented Jul 30, 2012 at 1:35
  • 1
    $\begingroup$ So... the shortest marriage wins? ;) $\endgroup$
    – rm -rf ♦
    Commented Jul 30, 2012 at 1:36
  • 4
    $\begingroup$ I'd love to do something for this, but I don't understand the question (not your fault - too advanced for me), but I can use the rest of this comment to wish the man good luck and this advice: marriage is like Mathematica, the more you put in, the more you get out... :) $\endgroup$
    – cormullion
    Commented Jul 30, 2012 at 21:42
  • 5
    $\begingroup$ @cormullion You forgot to set the undocumented $Patience = Infinity before executing. Your kernel will now crash and there is no undo. $\endgroup$
    – rm -rf ♦
    Commented Jul 30, 2012 at 22:27

1 Answer 1

Reset to default
5
+100
$\begingroup$

Here's my obligatory silly answer:

f[s_, t_, e_] := With[{r = #[[1]] -> #[[2]] & /@ e},
  StringReplace[s, r] != StringReverse[StringReplace[t, r]]]
p[{s_, t_}] := StringMatchQ[s, t ~~ ___] || StringMatchQ[t, s ~~ ___]
p[e_] := Or @@ p /@ Subsets[#[[2]] & /@ e, {2}]
m[s_, t_, k_] := Module[{h = Union @@ Characters /@ {s, t}, e, b = True},
  While[b, e = h /. c_String :> {c, 
   StringJoin[ToString /@ RandomInteger[k - 1, RandomInteger[{1, 10^6}]]]};
   b = p[e] || f[s, t, e]]; e]

Example usage:

m["We wish you the best", "Sz is the handsomest groom", 3]

It will return a list representing the encoding, such as:

{{"W", "012"}, {"e", "2111"}, ...}

Description: Creates a random encoding e of all the characters while it is prefixed p[e] or doesn't encode the strings to be the reverse of each other f[s, t, e].

It'll probably work, but I wouldn't try to run it.

I'm not particularly good at golf, but if you take my handicap into consideration, I'm sure I stand a good chance. ;-)

Improve this answer
$\endgroup$
2
  • $\begingroup$ Silly or not, you got the bounty. Congrats! $\endgroup$
    – Dr. belisarius
    Commented Aug 24, 2012 at 22:45
  • 1
    $\begingroup$ I couldn't work out how to do it properly, let alone golf it. :-/ $\endgroup$
    – wxffles
    Commented Aug 26, 2012 at 20:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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