Scrabble word finder permutations

Share your advanced PureBasic knowledge/code with the community.
User avatar
idle
Always Here
Always Here
Posts: 5042
Joined: Fri Sep 21, 2007 5:52 am
Location: New Zealand

Scrabble word finder permutations

Post by idle »

crude example of a scrabble word finder, returns a list of words largest 8 letters down to 2 letter words from the given input of 8 letters,

Code: Select all

;idle scrabble word finder words up to 8 letters 
;returns a list of words from given input set from largest words to smallest words  
;thanks Marco for your dictonary work :-)

EnableExplicit 

Global NewMap Dict.i(90000) 

Structure PemDic
    Map one.s()
    Map two.s()
    Map three.s()
    Map four.s()
    Map five.s()
    Map six.s()
    Map seven.s()
    Map eight.s()
EndStructure    

Procedure LoadDicFile(Dicfile.s) 
  Protected fn,fm,pos,word.s 
  fn = ReadFile(#PB_Any,Dicfile) 
  If fn 
    fm = ReadStringFormat(fn) 
    While Not Eof(fn) 
      word = ReadString(fn,fm,-1) 
      pos = FindString(word,"/") 
      If pos > 0 
        word = Left(word,pos-1)
      EndIf 
      word = LCase(word) 
      Dict.s(word)=Len(word) 
    Wend 
    CloseFile(fn) 
  EndIf 
EndProcedure 

Prototype.s pCbPermute(out.s,len,*user) 

Procedure Permute(*v,start,len,*cb.pCBPermute,*user)
  Protected i.i,sout.s,tw.c,tmpc.c,sz.i
  If start = len-1
    If *v
      sout.s
      For i = 0 To len -1
         tw.c = PeekC(*v+(i* SizeOf(Character)))
         sout + Chr(tw) 
      Next
      If *cb 
        *cb(sout,len,*user)
      EndIf   
    EndIf
  Else
    sz = SizeOf(Character)
    For i = start To len -1
      tmpc.c = PeekC(*v+(i*sz))
      PokeC(*v+(i*sz),PeekC(*v+(start*sz)));
      PokeC(*v+(start*sz),tmpc)
      permute(*v,start+1,len,*cb,*user);
      PokeC(*v+(start*sz),PeekC(*v+(i*sz)))
      PokeC(*v+(i*sz),tmpc);
    Next
  EndIf
EndProcedure

Procedure cbPermute(out.s,len,*user) 
  Protected inp.s,*pem.pemdic 
  
  *pem = *user 
  
  If len >= 2 
    inp = Right(out,2)
    If FindMapElement(dict(),inp)
      *pem\two(inp) = inp
    EndIf 
  EndIf 
  If len >= 3 
    inp = Right(out,3)
    If FindMapElement(dict(),inp)
      *pem\three(inp)=inp 
    EndIf 
  EndIf 
  If len >= 4 
    inp = Right(out,4)
    If FindMapElement(dict(),inp)
      *pem\four(inp) = inp 
    EndIf 
  EndIf 
  If len >= 5 
    inp = Right(out,5)
    If FindMapElement(dict(),inp)
      *pem\five(inp)=inp 
    EndIf 
  EndIf 
  If len >= 6 
    inp = Right(out,6)
    If FindMapElement(dict(),inp)
      *pem\six(inp)=inp 
    EndIf 
  EndIf  
  If len >= 7
    inp = Right(out,7)
    If FindMapElement(dict(),inp)
      *pem\seven(inp)= inp 
    EndIf 
  EndIf 
  If len >= 8
    inp = Right(out,8)
    If FindMapElement(dict(),inp)
      *pem\eight(inp)= inp 
    EndIf 
  EndIf 
  
EndProcedure 

Procedure GenListWords(*pem.PemDic,List words.s()) 
  
  ForEach *pem\eight() 
    AddElement(words()) 
    words() = *pem\eight() 
  Next 
  ForEach *pem\seven() 
    AddElement(words()) 
    words() = *pem\seven() 
  Next 
  ForEach *pem\six() 
   AddElement(words()) 
    words() =  *pem\six()
  Next 
  ForEach *pem\five()
    AddElement(words()) 
    words() =  *pem\five()
  Next 
  ForEach *pem\four()
    AddElement(words()) 
    words() = *pem\four() 
  Next 
  ForEach *pem\three()
    AddElement(words()) 
    words() =  *pem\three()
  Next 
  ForEach *pem\two() 
    AddElement(words()) 
    words() = *pem\two() 
  Next   
  
EndProcedure   

Procedure GetWords(input.s,List words.s()) 
  Protected *pem = AllocateStructure(pemdic) 
  If Len(input) < 9 
    Permute(@input,0,Len(input),@cbPermute(),*pem) 
    GenListWords(*pem,words())
  EndIf   
  FreeStructure(*pem) 
EndProcedure   

Global path.s = GetTemporaryDirectory()+"en-GB.dic"
Global NewList words.s() 

InitNetwork() 

If ReceiveHTTPFile("https://raw.githubusercontent.com/marcoagpinto/aoo-mozilla-en-dict/master/en_GB%20(Marco%20Pinto)/en-GB.dic",path)
  loadDicfile(path.s)  
Else 
  MessageRequester("BOFH","failed to download") 
  End 
EndIf   
 
GetWords("permutes",words())  

ForEach words() 
  Debug words() 
Next   

ClearList(words()) 

Windows 11, Manjaro, Raspberry Pi OS
Image
wilbert
PureBasic Expert
PureBasic Expert
Posts: 3870
Joined: Sun Aug 08, 2004 5:21 am
Location: Netherlands

Re: Scrabble word finder permutations

Post by wilbert »

Interesting topic. :)

I wonder what would be faster ...
Taking all permutations and check for each permutation if the word exists or the other way around; take each word and check if you can make it with the letters you got.
Windows (x64)
Raspberry Pi OS (Arm64)
davido
Addict
Addict
Posts: 1890
Joined: Fri Nov 09, 2012 11:04 pm
Location: Uttoxeter, UK

Re: Scrabble word finder permutations

Post by davido »

Yes. Interesting....
Thank you.
DE AA EB
User avatar
idle
Always Here
Always Here
Posts: 5042
Joined: Fri Sep 21, 2007 5:52 am
Location: New Zealand

Re: Scrabble word finder permutations

Post by idle »

wilbert wrote:Interesting topic. :)

I wonder what would be faster ...
Taking all permutations and check for each permutation if the word exists or the other way around; take each word and check if you can make it with the letters you got.
I did say it was lazy :P
Once the number of combinations exceed the dictionary size I'm sure the later would be faster, permutations are very expensive

!n
1: 1
2: 2
3: 6
4: 24
5: 120
6: 720
7: 5040
8: 40320
9: 362880
10: 3628800
11: 39916800
12: 479001600

the question this came from was using a random method to fill a map with a range from a set but it failed when the set had the same letter more than once and it wouldn't complete but otherwise it was a good strategy for looking up all occurrences of a range from a set. (!n / !(n-r)) is a lot cheaper to do.
Windows 11, Manjaro, Raspberry Pi OS
Image
User avatar
Kwai chang caine
Always Here
Always Here
Posts: 5342
Joined: Sun Nov 05, 2006 11:42 pm
Location: Lyon - France

Re: Scrabble word finder permutations

Post by Kwai chang caine »

Works great
Thanks for sharing 8)
ImageThe happiness is a road...
Not a destination
User avatar
Michael Vogel
Addict
Addict
Posts: 2666
Joined: Thu Feb 09, 2006 11:27 pm
Contact:

Re: Scrabble word finder permutations

Post by Michael Vogel »

Did use regular expressions for Scrabble filters, not that slow...

Here's the windows program (Screenshot) with a german dictionary (around 750.000 words)
User avatar
idle
Always Here
Always Here
Posts: 5042
Joined: Fri Sep 21, 2007 5:52 am
Location: New Zealand

Re: Scrabble word finder permutations

Post by idle »

I expect it would scale better with regular expressions suffix trees.
Windows 11, Manjaro, Raspberry Pi OS
Image
wilbert
PureBasic Expert
PureBasic Expert
Posts: 3870
Joined: Sun Aug 08, 2004 5:21 am
Location: Netherlands

Re: Scrabble word finder permutations

Post by wilbert »

Just out of curiosity ...
Scrabble contains two blanks that can be any letter.
Would it be possible to calculate the amount of possibilities if you have for example 6 normal letters and a blank ?
Windows (x64)
Raspberry Pi OS (Arm64)
Little John
Addict
Addict
Posts: 4519
Joined: Thu Jun 07, 2007 3:25 pm
Location: Berlin, Germany

Re: Scrabble word finder permutations

Post by Little John »

Given
r = number of letters
b = number of blanks (A blank can be any of x letters; x = 26 in English.)

Looked for
n = number of possibilities

Result
n = (r+b)! * x^b
wilbert
PureBasic Expert
PureBasic Expert
Posts: 3870
Joined: Sun Aug 08, 2004 5:21 am
Location: Netherlands

Re: Scrabble word finder permutations

Post by wilbert »

Thanks Little John.
Interesting to know :)
Windows (x64)
Raspberry Pi OS (Arm64)
User avatar
idle
Always Here
Always Here
Posts: 5042
Joined: Fri Sep 21, 2007 5:52 am
Location: New Zealand

Re: Scrabble word finder permutations

Post by idle »

that's quite a long move, wake me up in 7000 hrs after !8*(26^3)
Windows 11, Manjaro, Raspberry Pi OS
Image
Post Reply