Hacker News Reader

Comment by singingfish | Hacker News Reader

This regex that took about 10 minutes to generate was amazingly effective and helped me earn my highest ever daily rate https://gist.github.com/dr-kd/d43c884fbac0089d8523

View on HN

>that took about 10 minutes to generate

How?

I'm assuming:

    1. Generate a list of suburbs names separated by |
    2. Simplify the regex:
    2.1. Convert to a NFA
    2.2. Turn it into a DFA
    2.3. Merge redundant states
    2.4. Turn it back into a regex

nfa? dfa?

Nondeterministic finite automaton and deterministic finite automaton. The theory behind state machines.

Thank you

https://gist.github.com/dr-kd/36df691fa395567cb73d1368e4345c...

How is that better than just checking against a list of suburb names?

The regex is a compressed representation which saves memory, and it's also likely to be quite a bit faster which saves cycles. I consider it a clever bit of optimisation.

It's also handling what state the suburb is in, and can deal with various kinds of bad data (e.g. lack of uniformity of spacing and capitalisation).

Do they ever coin new suburb names? What happens then?

Yes they do. This was good for the early/mid 2000s - new suburbs are going to be a problem as australia post no longer give the list away for free.

How did you generate this?

perl module Regexp::Assemble

Reply on news.ycombinator.com