Anagrams for TV show "Countdown"

Ask gaming related questions
wolf_II
Posts: 2688
Joined: 08 Feb 2015, 20:55

Anagrams for TV show "Countdown"

08 Jul 2017, 07:34

Maybe offtopic, but closely related:
I have made an attempt at getting all permutations of a word (anagram candidates?) and I wonder: Is there a clever way to do that?
I use a stupid-brute-force recursive approach, which returns n! (factorial) members (unsorted, allows repeats) in an array.

Example:
  • (Word length = 8) => get permutations in 0.2 sec, dict lookup = 0.02 sec
  • (Word length = 9) => get permutations in 6.3 sec, dict lookup = 0.2 sec
  • (Word length = 10) => get permutations in 480 sec, dict lookup = 2 sec
There must be a better way?!
Permutations()
Edit: corrected typo
Last edited by wolf_II on 09 Jul 2017, 17:50, edited 1 time in total.
Helgef
Posts: 4307
Joined: 17 Jul 2016, 01:02
Contact:

Re: Alternatives to RegExMatch?

08 Jul 2017, 07:55

That is a nice function wolf_II. :thumbup:
Although I'm not sure I like the permutation + look-up method for finding anagrams. At least one should have separate dictionaries for each word length.
Helgef
Posts: 4307
Joined: 17 Jul 2016, 01:02
Contact:

Re: Alternatives to RegExMatch?

08 Jul 2017, 08:26

Suggestion, make a list of all anagrams, then look up in that list, you only have to do it once.

Code: Select all

setbatchlines,-1
listlines,off
#noenv
dictionary=
(
Bruce
Arnold
ceBru
Dolph
Dollp
Chuck
Chukc
Cuhkc
)
dict:=[]
Loop, Parse, dictionary, `n, `r 							; Put all words in an array dict, at dict[wordLength, wordLettersSorted, entryNumber]
{
	keyword:=A_LoopField
	len:=strlen(A_LoopField)
	keyword:=Ltrim(RegExReplace(keyword,"(.)",",$1"),",")
	Sort,keyword,D,											; Make a keyword, eg, Dallas -> a,a,D,l,l,s
	if !IsObject(dict[len,keyword])
		dict[len,keyword]:=[]
	dict[len,keyword].push(A_LoopField)						; Put the word in the keyword slot, all permutations will get the same keyword and end up in this slot
}
allAnagrams:=[]
for len, lengthGroup in dict {
	for keyword, anagrams in lengthGroup
		if (anagrams.length()>1)							; For each keyword which has more than entry, there is anagrams, save those
			allAnagrams.push(anagrams)
}
str:="Anagram list:`n"										; Print result
for k, anagrams in allAnagrams {
	str.= "Anagram set`t" k ":`t"
	for l, anagram in anagrams
		str.=anagram  "`t" 
	str.= "`n" 
}
gui, font,,courier new										; Show result
gui,add,edit,w1000 r40, % str
gui,show
Edit: The len key in dict only serves the purpose of getting the list in descending length order, you can remove it if you want.
Edit 2: Results, found 7577 anagram sets in ~1.3 seconds,
result.txt
(276.02 KiB) Downloaded 59 times
Searched in wordlist consisting of circa 100000 words:
wl2.txt
(1020.27 KiB) Downloaded 56 times
Example,

Code: Select all

Anagram set	2106:	capers	casper	crapes	escarp	pacers	parsec	recaps	scrape	spacer	
wolf_II
Posts: 2688
Joined: 08 Feb 2015, 20:55

Re: Alternatives to RegExMatch?

08 Jul 2017, 08:57

(written before Helgef's most recent post)
Are you talking personal preference or raw performance?
In case I can not improve the (most significant) Permutations() function, How much of a benefit would you expect?
My test with WordLength = 9 doesn't show much benefit (dictionary text file has 370,101 words, max length = 31).
T1 (get permutation) still 6.0 sec, T2 (lookup) still 0.2 sec
wolf_II
Posts: 2688
Joined: 08 Feb 2015, 20:55

Re: Alternatives to RegExMatch?

08 Jul 2017, 09:26

:bravo: Blimey, I think I get it now! Holy Handgranade, this is awsome. :thumbup:
You are not calculating permutations, you just make the dictionary your bitch. (sorry for foul language)

I am ... speechless.
:dance: :dance: :dance:

Thank you for sharing this.
wolf_II
Posts: 2688
Joined: 08 Feb 2015, 20:55

Re: Alternatives to RegExMatch?

08 Jul 2017, 10:29

@littlegandhi1199: Sorry for hijacking your thread.
Anagrams.ahk
Helgef
Posts: 4307
Joined: 17 Jul 2016, 01:02
Contact:

Re: Alternatives to RegExMatch?

08 Jul 2017, 11:31

Nice script :thumbup:
It performs well enough to have a live search, added gosub

Code: Select all

;-------------------------------------------------------------------------------
CountLetters: ; live display
;-------------------------------------------------------------------------------
	GuiControlGet, Word
	SB_SetText("Length: " WordLength := StrLen(Word), 1)
	Gosub, ButtonGetAnagrams
Return
This will give false results, for example when you type dda it will list add and dad, but that could be considered a feature. I.e, given a permutation of letters, find all real word anagrams for it.
wolf_II
Posts: 2688
Joined: 08 Feb 2015, 20:55

Re: Alternatives to RegExMatch?

08 Jul 2017, 12:21

@Helgef: I have taken out the button completely, thanks for the suggestion. My original code does not even resemble the current script any longer. :D
And we are definitely off topic now, no more RegExMatch(), very much explored alternatives though. I hope that counts.

Re. feature: The thought never crossed my mind, that Input might not be a valid word, I took it for granted, that it wouldn't. I was thinking about a TV Show called "Countdown", but my script would not be able to find a 7 or 8 letter word from any given 9 letters. For now, let's call it a feature of the script, with a TODO item?

EDIT:
:?: And that brings back the question: Can a Permutations() function be made faster than O(n^2) :?: I'm not even sure it's O(n^2), I only know it's bad. It might be O(n!) if such a thing exists.

EDIT2: I reported my first post in this thread as off topic, and hope the discussion that followed afterwards will be moved to a separate thread. I don't wish to annoy any futher, but I wish to continue the discussion. I hope that's OK for everybody?
Version 1.06
Helgef
Posts: 4307
Joined: 17 Jul 2016, 01:02
Contact:

Re: Alternatives to RegExMatch?

08 Jul 2017, 16:20

I agree there is some off-topic here, sorry :offtopic:
I think Anagrams.ahk should live in Scripts and functions.
Regarding the permutations() function, it is clearly O(n!) w.r.t the number of function calls. However, I have no better ideas, I think it is very nice as is, very readable, and it could live in Scripts and functions too. :thumbup:

Return to “Gaming”

Who is online

Users browsing this forum: No registered users and 41 guests