The SQL of Scrabble and Rapping

Preamble

Sometimes, when you tackle a different problem in SQL, one can hit on techniques that come in handy in all sorts of other contexts. This is the theme of this article, which uses a bank of all common words of the English language.

Cheating at Scrabble

I was playing Scrabble the other day and faced, as usual with an impossible hand. Scrabble is, as you probably know, a game where you pick tiles from a sack, and each tile has a letter written on it. You are allowed up to seven tiles at a time, and you have to place these, made up into words, on a game board marked with a 15-by-15 grid. The words are formed across and down in crossword fashion, and must be real words in common use. Each letter is scored individually, but the score is boosted by special squares on the board that give you double, or triple, word, or letter, scores.

It occurred to me, as it must have done to many others, that one could cheat at this game with a surreptitious iPhone or iPod and a simple word bank.

If you based this application on SQL Server, using a simple HTML interface, it would be easy to find all the words that could be made up from your seven tiles. Because you will need to link in with another word, that will come to eight letters. In some denser games, even more than eight-letter words are made as more existing words are crossed.

The first exercise will be to find all the permutation of the characters in your hand. Actually, if you are being subtle, you can restrict yourself to a subset, since only a small number of the combination of vowels and consonants are actually allowed in English. We won’t be subtle here: we’ll use the brute-force attack to the problem. The simplest way is to do a series of joins to a table of letters, but I’ll try a more flexible approach that uses a variation of the card-sharper’s shuffle instead. To do this, you will firstly need a number table. This number table is used frequently in SQL and you may already have one in your test database. If you haven’t, this stored procedure will deal with the task of creating and populating the number table.

IF EXISTS ( SELECT 'found'

FROM sys.objects

WHERE name='MaybeBuildNumberTable' )

DROP PROCEDURE MaybeBuildNumberTable

CREATE PROCEDURE [dbo].[MaybeBuildNumberTable]

BEGIN

SET NOCOUNT ON

IF NOT EXISTS ( SELECT *

FROM dbo.sysobjects

WHERE id=OBJECT_ID(N'[dbo].[Numbers]')

AND OBJECTPROPERTY(id, N'IsUserTable')=1 )

BEGIN

CREATE TABLE [dbo].[Numbers]

(

[number] [int],

CONSTRAINT [Index_Numbers] PRIMARY KEY CLUSTERED ([number] ASC)

ON [PRIMARY]

)

ON [PRIMARY]

END

IF NOT EXISTS(SELECT 1 FROM numbers WHERE number=99999)

BEGIN

TRUNCATE TABLE numbers

;WITH Digits(i)

AS (SELECT i

FROM (VALUES (1), (2), (3), (4), (5), (6), (7), (8), (9), (0)) AS X(i))

INSERT INTO numbers(number)

SELECT (D5.i*100000 + D4.i*10000 + D3.i * 1000 + D2.i * 100

+ D1.i * 10 + D0.i + 1) AS seq

FROM Digits AS D0, Digits AS D1, Digits AS D2, Digits AS D3,

Digits AS D4, Digits AS D5

END

Execute MaybeBuildNumberTable

With these basics out of the way, we can now create the Table-Valued Function that returns the permutations in sequence of the characters you give it. This will work with any ASCII character and can be altered to deal with unicode, of course. All we are doing here is creating an empty table of the right size and then filling it with all the permutations of the characters you supply to the function. Normally, permutations will be done with a series of self-joins to a table with all the characters, one per row, but here we want something that will be useful when you do not know the length of the string in advance. (Permutations are great for doing many of the ‘graph’ problems, such as finding the shortest route, network routing, or time-tabling)

if exists (select 'found' from sys.objects where name ='PermutationsOf')

drop function PermutationsOf

CREATE FUNCTION PermutationsOf (@String VARCHAR(10))

/**

summary: >

returns a simple table of all the permutations of a string of up to

eight characters. (one can do more if you are prepared to wait a bit)

The algorithm is based on the idea of a cunjurors shuffle which

guarantees to return the pack to its original order. In this case,

it shuffles the string to every combination.

It uses the 'quirky update' in order to do the shuffle.

example:

- code: --test for correctness

Select count(*),string

from dbo.PermutationsOf ('12345678')

group by string having count(*)>1

- code: Select * from dbo.PermutationsOf ('physical')

- code: Select * from dbo.PermutationsOf (null)

returns: a table listing all the alternative permutations of the

letters. If you gibe a string like '111' then all

permutations will be the same

**/

RETURNS @alternatives TABLE

(

number INT primary key,

String VARCHAR(10)

)

BEGIN

DECLARE @LenString INT

DECLARE @Iterations INT

SELECT @LenString=LEN(@String),

@iterations=CASE @Lenstring

WHEN 1 THEN 1

WHEN 2 THEN 2

WHEN 3 THEN 6

WHEN 4 THEN 24

WHEN 5 THEN 120

WHEN 6 THEN 720

WHEN 7 THEN 5040

WHEN 8 THEN 40320

ELSE NULL

END

IF @iterations IS NULL

BEGIN

INSERT INTO @alternatives ( number,string)

SELECT 1,'Sorry' UNION

SELECT 2,'String' UNION

SELECT 3,'wrong' UNION

SELECT 4,'length'

RETURN

END

INSERT INTO @alternatives (Number, string)

SELECT number,

FROM numbers

WHERE number<=@iterations

UPDATE @alternatives --progressively shuffle the string

SET @string=string

=CASE WHEN number=0 THEN @string

WHEN number%5040=0

THEN SUBSTRING(@string, 8, 1)+SUBSTRING(@string, 7, 1)

+SUBSTRING(@string, 6, 1)+SUBSTRING(@string, 5, 1)

+SUBSTRING(@string, 4, 1)+SUBSTRING(@string, 2, 1)

+LEFT(@string, 1)+SUBSTRING(@string, 3, 1)

+SUBSTRING(@string, 9, @lenstring-4)

WHEN number%720=0

THEN SUBSTRING(@string, 7, 1)+SUBSTRING(@string, 6, 1)

+SUBSTRING(@string, 5, 1)+SUBSTRING(@string, 4, 1)

+SUBSTRING(@string, 2, 1)+LEFT(@string, 1)

+SUBSTRING(@string, 3, 1)+SUBSTRING(@string, 8, @lenstring-4)

WHEN number%120=0

THEN SUBSTRING(@string, 6, 1)+SUBSTRING(@string, 5, 1)

+SUBSTRING(@string, 4, 1)+SUBSTRING(@string, 2, 1)

+LEFT(@string, 1)+SUBSTRING(@string, 3, 1)

+SUBSTRING(@string, 7, @lenstring-4)

WHEN number%24=0

THEN SUBSTRING(@string, 5, 1)+SUBSTRING(@string, 4, 1)

+SUBSTRING(@string, 2, 1)+LEFT(@string, 1)

+SUBSTRING(@string, 3, 1)+SUBSTRING(@string, 6, @lenstring-4)

WHEN number%6=0

THEN SUBSTRING(@string, 4, 1)+SUBSTRING(@string, 2, 1)

+LEFT(@string, 1)+SUBSTRING(@string, 3, 1)

+SUBSTRING(@string, 5, @lenstring-4)

WHEN number%3 IN (1, 2)

THEN SUBSTRING(@string, 2, 2)+LEFT(@String, 1)

+RIGHT(@String, @lenstring-3)

ELSE SUBSTRING(@string, 2, 1)+LEFT(@string, 1)

+RIGHT(@String, @lenstring-2)

END

RETURN

END

Now we have this working, we’ll need all the common words of English. We first create the table of words and stock it from our word bank that I provide in the downloads at the bottom of the article.

IF EXISTS ( SELECT 'found'

FROM information_Schema.tables

WHERE Table_Name='AllWords' )

DROP TABLE AllWords

CREATE TABLE AllWords

(

String VARCHAR(25) NOT NULL,

CONSTRAINT [PK_CommonWords] PRIMARY KEY CLUSTERED ([String] ASC)

ON [PRIMARY]

)

ON [PRIMARY]

now we'll insert all the words into our dictionary table */

DECLARE @commonwords TABLE (Word VARCHAR(255))

INSERT INTO @CommonWords

EXECUTE master..xp_cmdshell 'type wordlist.txt'

INSERT INTO AllWords (String)

SELECT left(word,25)

FROM @commonwords

WHERE word IS NOT NULL

You would have to alter the path to the word list before using this, of course. I usually find that my seven tiles consist mostly of vowels so I couldn’t resist extracting lists of handy words with at least four consecutive vowels, just to make sure that everything was loaded properly

Declare @list Varchar(Max)

SELECT @List=coalesce(@list+', ','')+string FROM allwords

WHERE PATINDEX('%[aeiou][aeiou][aeiou][aeiou]%',string) >0

Select @List

/*aqueous, gooier, gooiest, obsequious, obsequiously, obsequiousness, onomatopoeia, pharmacopoeia, pharmacopoeias, plateaued, plateauing, queue, queued, queueing, queues, queuing, sequoia, sequoias

Though my favourite has five consecutive vowels

SELECT string FROM allwords

WHERE PATINDEX('%[aeiou][aeiou][aeiou][aeiou][aeiou]%',string) >0

--queueing

Good grief, if you are short of vowels, there is plenty you can do, as there are words with seven or more consonants in a row (if you include Y as a consonant) …

Declare @list Varchar(Max)

SELECT @List=coalesce(@list+', ','')+string FROM allwords

WHERE PATINDEX('%[^aeiou][^aeiou][^aeiou][^aeiou][^aeiou][^aeiou][^aeiou]%',string) >0

Select @List

/* biorhythms, encrypts, rhythms, strychnine */

But most of the time, it is a shortage of vowels

/* you can quickly find the words with the most vowels (10 seems to be the highest) but these are in words like internationalization(10) and interdenominational (9)

SELECT string,LEN(string)-LEN(REPLACE(REPLACE(REPLACE(REPLACE(REPLACE(String,'a',''), 'e',''), 'i',''), 'o',''), 'u',''))

FROM

allwords

ORDER BY LEN(string)-LEN(REPLACE(REPLACE(REPLACE(REPLACE(REPLACE(String,'a',''), 'e',''), 'i',''), 'o',''), 'u',''))DESC

/* but it is more useful to have the ones with the highest proportion of vowels to consonants! */

DECLARE @list VARCHAR(MAX)

SELECT @List=COALESCE(@list+', ','')+string FROM

(

SELECT TOP 60 string FROM

allwords

ORDER BY ((LEN(string)-LEN(REPLACE(REPLACE(REPLACE(REPLACE(REPLACE(String,'a',''), 'e',''), 'i',''), 'o',''), 'u','')))*100.00) /LEN(string) DESC

SELECT @List

oi, adieu, aerie, audio, eerie, queue, aeon, aide, aloe, aqua, area, aria, aura, auto, beau, ciao, ease, epee, euro, idea, iota, luau, oboe, ooze, ouzo, amoebae, anaemia, aquaria, aqueous, aureole, evacuee, sequoia, aah, acacia, ace, adagio, adieus, adieux, aerate, aerial, aeries, age, ago, aha, aid, ail, aim, air, airier, ale, amebae, amoeba, anemia, ape, apiece, apogee, are, arouse, ate, audacious*/

Now we have a function that will provide a table with all the permutation of between two and eight letters, we can use it to find those common words that can be built with your list of letters. Here we have an effective way of cheating at Scrabble. You’d have to use something like iWebKit to knock together a little application.

if exists (select 'found' from sys.objects where name ='ValidWordsInLetters')

drop function ValidWordsInLetters

CREATE FUNCTION ValidWordsInLetters (@String VARCHAR(10))

/**

summary: >

example:

- code: Select String from dbo.ValidWordsInLetters('CoFartua')

returns: a table listing up to the first hundred words

that can be made with the letters you supply. Good for

Scrabble where you have SQL Server handy.

**/

RETURNS @words TABLE

(

number INT identity(1,1) primary key,

String VARCHAR(10)

)

BEGIN

DECLARE @rowcount INT, @ii INT, @LenString int

Declare @Strings Table (

number INT identity(1,1) primary key,

String VARCHAR(10)

)

insert into @strings(string)

Select distinct string

from dbo.PermutationsOf (@String)

SELECT @Rowcount=0, @LenString=LEN(@String),

@ii=@LenString

WHILE @ii>2

AND @rowcount<100

BEGIN

INSERT INTO @words

SELECT distinct TOP 100

allwords.string

FROM Allwords

INNER JOIN @Strings a

ON LEFT(a.string, @ii)=allwords.string

SELECT @Rowcount=@rowcount+@@Rowcount,

@ii=@ii-1

END

return

end

Select String from dbo.ValidWordsInLetters('CoFartua')

Rapping and doggerel.

Rhyming dictionaries aren’t new. they are simply dictionaries that are ordered by the word written backwards. It starts with Baa and ends in Fuzz. The most famous one is probably Walkers Rhyming Dictionary. Every poet has one. Whilst they are useful, they are a bit hit and miss to use. We’ll

be slightly more ambitious and try to give to a better rhyme. We’ll extract up to two of the final syllables of the word and match them to all other words with the same two syllables. We are actually not getting syllables as such but the sonorant/coda combinations. (syllables usually have an initial consonant) This seems to get a better set of rhymes

So, for Phil Factor, we have the rhymes …

actor,benefactor,chiropractor,contractor,detractor,extractor,malefactor,protractor,subcontractor,tractor

… We could soon be rapping with this lot

So as to get a quick response, and keep the code manageable, we’ll create a special table for our rhyming dictionary.

drop TABLE dbo.RhymingWords

CREATE TABLE dbo.RhymingWords(

String varchar(30) NOT NULL,

PenultimateSyllable varchar(30) not null default '',

WithoutFinalSyllable varchar(30) not null default '',

FinalSyllable varchar(30) not null default '',

CONSTRAINT [PK_RhymingWords] PRIMARY KEY CLUSTERED

(

[String] ASC

) ON [PRIMARY]

/*We start by inserting all the words from our dictionary. */

insert into dbo.RhymingWords (String) select String from allwords

/* and now we extract the final syllable into its own column */

UPDATE RhymingWords --add in the final syllable

SET WithoutFinalSyllable=LEFT(r.String, LEN(r.String)-endingSyllable),

FinalSyllable=RIGHT(r.String, endingsyllable)

FROM RhymingWords r

INNER JOIN -- could be a monophthong, diphthong, or triphthong,

(SELECT String, syllable+case when PATINDEX('[aeiou]%',REVERSE(LEFT(String, LEN(String)-syllable)))=0 then 0

else PATINDEX('%[aeiou][^aeiou]%',

REVERSE(LEFT(String, LEN(String)-syllable))+'x') end AS Endingsyllable

FROM

(SELECT String, --pick out the last vowel-consonant transition

PATINDEX('%[^aeiou][aeiou]%',--to get the coda

REVERSE(String))+1 AS syllable

FROM RhymingWords

WHERE PATINDEX('%[^aeiou][aeiou]%',

REVERSE(String))>0 ---where it is possible!

) f

) g ON g.String=r.String

UPDATE RhymingWords --add in the penultimate syllable

SET PenultimateSyllable=RIGHT(r.WithoutFinalSyllable, syllableIndex)

FROM RhymingWords r

INNER JOIN -- could be a monophthong, diphthong, or triphthong,

(SELECT String, syllable+case when PATINDEX('[aeiou]%',REVERSE(LEFT(WithoutFinalSyllable, LEN(WithoutFinalSyllable)-syllable)))=0 then 0

else PATINDEX('%[aeiou][^aeiou]%',

REVERSE(LEFT(WithoutFinalSyllable, LEN(WithoutFinalSyllable)-syllable))+'x')end AS syllableIndex

FROM

(SELECT String, WithoutFinalSyllable,--pick out the last vowel-consonant transition

PATINDEX('%[^aeiou][aeiou]%',--to get the coda

REVERSE(WithoutFinalSyllable))+1 AS syllable

FROM RhymingWords

WHERE PATINDEX('%[^aeiou][aeiou]%',

REVERSE(WithoutFinalSyllable))>0 ---where it is possible!

) f

) g ON g.String=r.String

--for short words ending in vowels

UPDATE RhymingWords

SET FinalSyllable= right(String,patindex('%[^aeiouy]%',reverse(String)+'x')-1) from Rhymingwords

where FinalSyllable ='' and reverse(String)like '%[aeiouy]%'

--for words with only Ys

UPDATE RhymingWords

SET FinalSyllable= right(String,patindex('%[aeiouy]%',reverse(String)+'x')) from Rhymingwords

where FinalSyllable =''

--no vowels

UPDATE RhymingWords

SET FinalSyllable= String

where FinalSyllable =''

Now, we are in the position to create a function that takes any word and gives you the rhymes to it. You need to beware, because I have not yet programmed in automatic translation of homophones. English spelling is so inconsistent that rhyming dictionaries will never tell you all the rhymes. You have to use some artistry to get the best out of a Rhyming dictionary. ‘Rhyme’, rhymes with ‘chime’, even though the word endings are spelt differently. You need to search all the alternative spellings of the final syllable to get all the rhymes.

No subtlety could, for a moment, attract her,
Until she succumbed to the charms of Phil Factor

You see? No easy programming would have given you that rhyme.

100

101

102

IF EXISTS ( SELECT 'found'

FROM sys.objects

WHERE name='RhymesWith' )

DROP FUNCTION RhymesWith

CREATE FUNCTION RhymesWith (@String VARCHAR(30))

/**

summary: >

returns a table with the best rhymes it can with whatever valid word

you pass to it. Because some syllables are written differently but

sound alike (Homophonic syllables) you may need to feed in words

that you know rhyme but have their last syllable(s) spelt differently.

e.g. eye and spy,

example:

- code: select * from dbo.RhymesWith('sand')

- code: select * from dbo.RhymesWith('Phill')

- code: select * from dbo.RhymesWith('technology')

returns: a table of one varchar column listing all the Rhymes.

There once was an IT contractor

who went by the name of 'Phil Factor'

He makes no apology

for his technology

for he's a consummate actor

**/

RETURNS @alternatives TABLE

(

number INT IDENTITY(1, 1)

PRIMARY KEY,

String VARCHAR(30)

)

AS BEGIN

DECLARE @Coda INT

DECLARE @FinalSyllable VARCHAR(30)

DECLARE @PenultimateSyllable VARCHAR(30)

DECLARE @RestofWord VARCHAR(30)

SELECT @PenultimateSyllable=PenultimateSyllable,

@FinalSyllable=FinalSyllable

FROM RhymingWords

WHERE String=@String

if @@Rowcount=0

BEGIN

SELECT @Coda=PATINDEX('%[^aeiou][aeiou]%',--to get the coda

REVERSE(@String))

SELECT @Coda=@Coda+PATINDEX('%[aeiou][^aeiou]%',

REVERSE(LEFT(@String,

LEN(@String)-@Coda))+'x')

SELECT @RestOfWord=LEFT(@String, LEN(@String)-@Coda),

@FinalSyllable=RIGHT(@String, @Coda)

SELECT @Coda=PATINDEX('%[^aeiou][aeiou]%',--to get the coda

REVERSE(@RestOfWord))+1

SELECT @Coda=CASE WHEN @Coda=1 THEN 0

ELSE @Coda

END

IF PATINDEX('[aeiou]%',

REVERSE(LEFT(@RestOfWord, LEN(@RestOfWord)-@Coda)))>0

SELECT @Coda=@Coda+PATINDEX('%[aeiou][^aeiou]%',

REVERSE(LEFT(@RestOfWord,

LEN(@RestOfWord)

-@Coda))+'x')

SELECT @PenultimateSyllable=RIGHT(@RestOfWord, @Coda)

IF @FinalSyllable=''

AND REVERSE(@String) LIKE '%[aeiouy]%'

SET @FinalSyllable=RIGHT(@String,

PATINDEX('%[^aeiouy]%',

REVERSE(@String)+'x')-1)

--for words with only Ys

IF @FinalSyllable=''

SET @FinalSyllable=RIGHT(@String,

PATINDEX('%[aeiouy]%',

REVERSE(@String)+'x'))

--no vowels

IF @FinalSyllable=''

SET @FinalSyllable=@String

END

INSERT INTO @alternatives (String)

SELECT String

FROM RhymingWords

WHERE PenultimateSyllable+FinalSyllable=@PenultimateSyllable

+@FinalSyllable

AND String<>@String

IF @@Rowcount<10

INSERT INTO @alternatives (String)

SELECT String

FROM RhymingWords

WHERE FinalSyllable=@FinalSyllable

AND String<>@String

RETURN

END

Rap up

So here we are with a word-bank that allows you to cheat at Scrabble and rap, or make up doggerel. More to the point, it has illustrated, in the ‘permutation’ function, how to use a numbers table to create a table, and the ‘quirky update’ method of filling a table with permutation, or any other data you need. We’ve also illustrated some techniques of using the built-in, and rather primitive, character pattern-matching techniques of SQL Server.

A Parting Competition

To end up with: here is a simple competition, that I will award a Christmas prize of a $50 Amazon voucher for.

Given that Scrabble is scored to the following table:

How fast can you score all common words according to their Scrabble scores, so as to list them in order.?
Find all the words that can’t ever be used in Scrabble? (Blank tiles can mean any letter). Scrabble contains…
- 2 blank tiles (scoring 0 points) that can represent any letter
- 1 point: E ×12, A ×9, I ×9, O ×8, N ×6, R ×6, T ×6, L ×4, S ×4, U ×4
- 2 points: D ×4, G ×3
- 3 points: B ×2, C ×2, M ×2, P ×2
- 4 points: F ×2, H ×2, V ×2, W ×2, Y ×2
- 5 points: K ×1
- 8 points: J ×1, X ×1
- 10 points: Q ×1, Z ×1

Register for Simple Talk

The SQL of Scrabble and Rapping

Preamble

Cheating at Scrabble

Rapping and doggerel.

Rap up

A Parting Competition

About the author

Phil Factor

Phil Factor's contributions

Articles

Books

Top topics

Phil Factor's latest contributions:

Data Documents and Common Sense

AI and Databases

Storing and Retrieving the Initialization and Configuration Data for Applications

Preamble

Cheating at Scrabble

Rapping and doggerel.

Rap up

A Parting Competition

Recommended

About the author

Phil Factor

Phil Factor's contributions

Articles

Books

Top topics

Phil Factor's latest contributions:

Data Documents and Common Sense

AI and Databases

Storing and Retrieving the Initialization and Configuration Data for Applications