Solved

MySQL regexp / regular expressions help - scrabble solver

Posted on 2009-04-13
7
954 Views
Last Modified: 2013-12-12
I'm trying to build a scrabble solver - I can make it work, but not the way I want it to - basically I get all words less than or equal to the length of the input string, then walk through the restultset in my php script checking against the letter array built from the input string.

I know this is a bad - and slow - way to do it, and I'm sure there is a way to do it just from the query, but I'm struggling with this.

The example below assumes the input string is ABCDE, so finds all words which are 5 characters or less and only use the letters ABCDE - but the two problems with this are it allows letters to be repeated (which needs to be dependent on the input string), and it can't handle wildcards.

SELECT WORD FROM WORDLIST WHERE CHARACTER_LENGTH(WORD) <= 5 AND WORD NOT REGEXP '[^ABCDE]'

It would be quick enough to get the resultset and then filter out any words that use letters more than once (except of course if the input string contained eg. more than one 'A' and this is allowed), but this doesn't solve the wildcard problem.

I've looked at the mysql reference and I'm sure there must be a way to do this, but I've tried what seems like every combination and I'm not getting anywhere.

Does anyone have any suggestions? Is this actually possible through mysql alone?
0
Comment
Question by:rockers07
7 Comments
 
LVL 17

Expert Comment

by:akshah123
ID: 24130599
You should try following ...

SELECT WORD 

FROM WORDLIST 

WHERE WORD REGEXP '^[ABCDE]{5}$'

Open in new window

0
 

Author Comment

by:rockers07
ID: 24130627
Thanks, but that only selects 5 letter words, and doesn't solve the duplicate letters or wildcard problems...
0
 
LVL 17

Expert Comment

by:akshah123
ID: 24130798
You will not be able to solve the duplication problem within the query.  That's just not possible unless you want to provide all possible combinations.  

IF you need to solve this problem multiple times, it might make more sense to have this data in memory instead.  

In any case, your only option is to take care of that in php.
0
Efficient way to get backups off site to Azure

This user guide provides instructions on how to deploy and configure both a StoneFly Scale Out NAS Enterprise Cloud Drive virtual machine and Veeam Cloud Connect in the Microsoft Azure Cloud.

 

Author Comment

by:rockers07
ID: 24131201
Duplication problem solved:

SELECT WORD FROM WORDLIST
WHERE CHARACTER_LENGTH(WORD) <= 5
AND WORD NOT REGEXP '[^ABCDE]'
AND LENGTH(WORD) - LENGTH(REPLACE(WORD, 'A', '')) <= 1
AND LENGTH(WORD) - LENGTH(REPLACE(WORD, 'B', '')) <= 1
AND LENGTH(WORD) - LENGTH(REPLACE(WORD, 'C', '')) <= 1
AND LENGTH(WORD) - LENGTH(REPLACE(WORD, 'D', '')) <= 1
AND LENGTH(WORD) - LENGTH(REPLACE(WORD, 'E', '')) <= 1

And change to <= 2 if the letter can appear twice etc.

Not sure that this is the most efficient method though - easy enough to process the duplications in PHP using substr_count(), and this is feasible if the result has already been filtered to the right length and characters - but it still feels like this should be possible through regexp.

I'm also still left with the wildcard problem.....
0
 
LVL 41

Expert Comment

by:HonorGod
ID: 24131846
Use a GADDAG data structure...

http://www.cs.ubc.ca/local/reading/proceedings/spe91-95/spe/vol24/issue2/spe880.pdf

Which is a way of storing the entire (US English) Scrabble dictionary in such a way as to:

- consume lots less space
- make is very quick to search
0
 

Accepted Solution

by:
ee_auto earned 0 total points
ID: 24372348
Question PAQ'd, 500 points refunded, and stored in the solution database.
0

Featured Post

PRTG Network Monitor: Intuitive Network Monitoring

Network Monitoring is essential to ensure that computer systems and network devices are running. Use PRTG to monitor LANs, servers, websites, applications and devices, bandwidth, virtual environments, remote systems, IoT, and many more. PRTG is easy to set up & use.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

As a database administrator, you may need to audit your table(s) to determine whether the data types are optimal for your real-world data needs.  This Article is intended to be a resource for such a task. Preface The other day, I was involved …
Things That Drive Us Nuts Have you noticed the use of the reCaptcha feature at EE and other web sites?  It wants you to read and retype something that looks like this.Insanity!  It's not EE's fault - that's just the way reCaptcha works.  But it is …
The viewer will learn how to look for a specific file type in a local or remote server directory using PHP.
This tutorial will teach you the core code needed to finalize the addition of a watermark to your image. The viewer will use a small PHP class to learn and create a watermark.

930 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

18 Experts available now in Live!

Get 1:1 Help Now