It is currently Sat Dec 07, 2019 8:34 am

All times are UTC + 1 hour




Post new topic Reply to topic  [ 11 posts ] 
Author Message
 Post subject: Scrabble word finder permutations
PostPosted: Sat Nov 30, 2019 5:32 am 
Offline
Addict
Addict
User avatar

Joined: Fri Sep 21, 2007 5:52 am
Posts: 3421
Location: New Zealand
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:
;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())



Top
 Profile  
Reply with quote  
 Post subject: Re: Scrabble word finder permutations
PostPosted: Sat Nov 30, 2019 9:50 am 
Offline
PureBasic Expert
PureBasic Expert

Joined: Sun Aug 08, 2004 5:21 am
Posts: 3542
Location: Netherlands
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.

_________________
macOS 10.15 Catalina, PB 5.71 x64


Top
 Profile  
Reply with quote  
 Post subject: Re: Scrabble word finder permutations
PostPosted: Sat Nov 30, 2019 10:25 am 
Offline
Addict
Addict

Joined: Fri Nov 09, 2012 11:04 pm
Posts: 1707
Location: Uttoxeter, UK
Yes. Interesting....
Thank you.

_________________
DE AA EB


Top
 Profile  
Reply with quote  
 Post subject: Re: Scrabble word finder permutations
PostPosted: Sat Nov 30, 2019 1:11 pm 
Offline
Addict
Addict
User avatar

Joined: Fri Sep 21, 2007 5:52 am
Posts: 3421
Location: New Zealand
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.


Top
 Profile  
Reply with quote  
 Post subject: Re: Scrabble word finder permutations
PostPosted: Sat Nov 30, 2019 9:03 pm 
Offline
Addict
Addict
User avatar

Joined: Sun Nov 05, 2006 11:42 pm
Posts: 4542
Location: Lyon - France
Works great
Thanks for sharing 8)

_________________
ImageThe happiness is a road...
Not a destination


Top
 Profile  
Reply with quote  
 Post subject: Re: Scrabble word finder permutations
PostPosted: Sun Dec 01, 2019 4:19 pm 
Offline
Addict
Addict
User avatar

Joined: Thu Feb 09, 2006 11:27 pm
Posts: 2452
Did use regular expressions for Scrabble filters, not that slow...

Here's the windows program (Screenshot) with a german dictionary (around 750.000 words)


Top
 Profile  
Reply with quote  
 Post subject: Re: Scrabble word finder permutations
PostPosted: Sun Dec 01, 2019 10:39 pm 
Offline
Addict
Addict
User avatar

Joined: Fri Sep 21, 2007 5:52 am
Posts: 3421
Location: New Zealand
I expect it would scale better with regular expressions suffix trees.


Top
 Profile  
Reply with quote  
 Post subject: Re: Scrabble word finder permutations
PostPosted: Tue Dec 03, 2019 6:42 am 
Offline
PureBasic Expert
PureBasic Expert

Joined: Sun Aug 08, 2004 5:21 am
Posts: 3542
Location: Netherlands
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 ?

_________________
macOS 10.15 Catalina, PB 5.71 x64


Top
 Profile  
Reply with quote  
 Post subject: Re: Scrabble word finder permutations
PostPosted: Tue Dec 03, 2019 7:04 am 
Offline
Addict
Addict
User avatar

Joined: Thu Jun 07, 2007 3:25 pm
Posts: 3715
Location: Berlin, Germany
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

_________________
Please excuse my flawed English. My native language is PureBasic.
Search
RSBasic's backups


Top
 Profile  
Reply with quote  
 Post subject: Re: Scrabble word finder permutations
PostPosted: Tue Dec 03, 2019 8:03 am 
Offline
PureBasic Expert
PureBasic Expert

Joined: Sun Aug 08, 2004 5:21 am
Posts: 3542
Location: Netherlands
Thanks Little John.
Interesting to know :)

_________________
macOS 10.15 Catalina, PB 5.71 x64


Top
 Profile  
Reply with quote  
 Post subject: Re: Scrabble word finder permutations
PostPosted: Tue Dec 03, 2019 9:27 am 
Offline
Addict
Addict
User avatar

Joined: Fri Sep 21, 2007 5:52 am
Posts: 3421
Location: New Zealand
that's quite a long move, wake me up in 7000 hrs after !8*(26^3)


Top
 Profile  
Reply with quote  
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 11 posts ] 

All times are UTC + 1 hour


Who is online

Users browsing this forum: No registered users and 8 guests


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum

Search for:
Jump to:  

 


Powered by phpBB © 2008 phpBB Group
subSilver+ theme by Canver Software, sponsor Sanal Modifiye