Women in Technology

Hear us Roar



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


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?


-Baz


[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

Main Topics Oldest First

Showing messages 1 through 1 of 1.

  • Solver?
    2003-11-27 04:46:27  bazzargh [View]

    oops - second regexp was supposed to be
    next if $word=~/a[^adv]|v[^vai]|i[^ivd]|d[^dai]/

    the one I posted didn't allow all the possible doubled letters.