xkcd 1313

[Erik Rantapaa]

MN Haskellers,

It was nice seeing everyone at Verdant Tea last night and I'm very much looking forward to more meetups.

Lately I've been playing around with Haskell solutions to the regex golf problem posed by xkcd 1313. It's been in the news lately with Peter Norvig writing a blog post about how to solve it in Python:

    http://nbviewer.ipython.org/url/norvig.com/ipython/xkcd1313.ipynb?utm_medium=App.net&utm_source=PourOver

and here is the HN discussion:

    https://news.ycombinator.com/item?id=7015132

Looking at his solution you'll notice that it is very "functional" and therefore quite amenable to a more-or-less direct translation to Haskell. So if you're looking for an intermediate programming challenge you might try transcribing his Python code. I found it an enjoyable exercise, and perhaps this is something we can discuss more either on the mailing list or at a meetup.

Erik

[Kyle Marek-Spartz]

Norvig discusses the cases which the generated solutions are not optimal. I wonder if there is an efficient way to generate optimal regexes using suffix tries? That’s one strategy for this sort of thing I’ve seen before, though it usually only uses a target set and not a reject set.

One could construct a suffix trie with special stop symbols for accept and reject, and then pare it down using rewrite rules… hmm.

--
Kyle Marek-Spartz