RouteWord: An Interesting Diversion
Subject:   Solver?
Date:   2003-11-27 04:29:55
From:   bazzargh

The first thing I thought of when I saw this was about how to write a solver (something that matches a wordlist); I reckon its fair game to mention this on a programming site. Writing one is trivial in Perl[1], however I'm interested in whether there's a better way. I believe you can't represent these puzzles as standard regular expressions (because of the cycles and recursion) but regexps in the P* languges aren't standard regexps any more, it may be possible to do better.

The solution below uses n + 2 regexps for n edges. I was wondering if it was possible to describe these things in less?


[1] You can write a straightforward recursive matcher, or eval generated code like this, taking the "david" example:
# ensure only the letters given appear
# and that the word is at least as long
# as the set of letters.
next unless $word=~/^[avid]{4,}$/;

# ensure only the edges given appear
# build regex looping over letters
next if $word=~/a[^dav]|v[^ai]|i[^vd]|d[^ai]/

# ensure all the edges given appear
next unless $word=~/ad|da/
# ...repeat above for each edge

1 to 1 of 1
  1. Solver?
    2003-11-27 04:46:27  bazzargh [View]

    • Solver?
      2004-02-06 12:48:17  kirk_donovan [View]

1 to 1 of 1