All,
This challenge was posed last night in #perl IRC on freenode.

Given:

Determine which string is the median string and the distance from each string to the median string.

For the purposes of this challenge, distance is the Levenshtein Distance. The median string is the string where the distance between itself and the furthest away string in the list is minimized. In other words, if you were to calculate the distance of the string furthest away for every string in the list, the median string would be the one with the shortest distance.

I recognize that my use of median is likely incorrect. In the event of a conflict, refer to the definition here as the intended one. There may be more than one string that fits the defintion of median string, in this case only 1 such string is required.

If you come up with a great solution that is not very memory efficient feel free to post it but if you can, limit memory consumption to 750MB. I have a feeling a trie may provide for a better solution, but the best I can come up with so far is below:

<Reveal this spoiler or all in this thread>

Update: ysth suggested a number of optimizations that I had already tried. He had the sense to try them together which makes it blazingly fast. While the algorithm is mine, credit for the optimizations go to him.

Cheers - L~R

In reply to Challenge: Find median string in a list by Limbic~Region

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post, it's "PerlMonks-approved HTML":


  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.