Mathematica Stack Exchange is a question and answer site for users of Mathematica. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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


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.
share|improve this question
To close or not to close... hmmm. – R. M. Jul 30 '12 at 1:31
@R.M Close it if you please, but don' delete tags :) – Dr. belisarius Jul 30 '12 at 1:35
So... the shortest marriage wins? ;) – R. M. Jul 30 '12 at 1:36
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... :) – cormullion Jul 30 '12 at 21:42
@cormullion You forgot to set the undocumented $Patience = Infinity before executing. Your kernel will now crash and there is no undo. – R. M. Jul 30 '12 at 22:27
up vote 5 down vote accepted

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. ;-)

share|improve this answer
Silly or not, you got the bounty. Congrats! – Dr. belisarius Aug 24 '12 at 22:45
I couldn't work out how to do it properly, let alone golf it. :-/ – wxffles Aug 26 '12 at 20:36

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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