Re: Anagrams
Posted: 16 Jul 2017, 08:32
by wolf_II
version 1.23
I have updated the first post.- added: SkipList
- changed: Max_Input_Length := 26
- changed: comment in Combination() to reflect design change
- changed: time is displayed (in seconds with 3 decimals) in the status bar
- changed: renamed global variable String -> Input
- added: global variable InputLength, rather than re-use "WordLength"
- changed: SkipList is worded better
Code: Select all
;-------------------------------------------------------------------------------
; Anagrams.ahk
; by wolf_II
;-------------------------------------------------------------------------------
; simple Anagram searcher
; written with massive help by Helgef from AHK forum
; https://autohotkey.com/boards/viewtopic.php?p=158284#p158284
;-------------------------------------------------------------------------------
;-------------------------------------------------------------------------------
AutoExecute: ; auto-execute section of the script
;-------------------------------------------------------------------------------
#NoEnv ; don't check empty variables
#SingleInstance, Force ; kill old instance
;---------------------------------------------------------------------------
SetBatchLines, -1 ; run script at maximum speed
SetWorkingDir, %A_ScriptDir% ; consistent directory
SplitPath, A_ScriptName,,,, AppName ; get AppName from file name
;---------------------------------------------------------------------------
Version := "1.23"
;===========================================================================
Max_Input_Length := 26
SkipList := "use all"
Loop, 9
SkipList .= "|use all but " A_Index
;---------------------------
; display GUI while loading
;---------------------------
Try Menu, Tray, Icon, %AppName%.ico
Menu, Tray, Icon ; show
Gui, New, -MinimizeBox, %AppName% v%Version%
Gui, Font, s11, Consolas ; xm=13, ym=8
Gui, Add, Text, w310, Search anagrams for this:
Gui, Add, Edit, wp vInput Disabled Center
Gui, Add, Text, xm y+12, Use minimum letters:
Gui, Add, ComboBox, x+m yp-4 w137 vSkip AltSubmit gShowAnagrams, %SkipList%
Gui, Add, ListBox, xm r15 w310 vLBox
Gui, Add, Progress, xp+1 yp+1 wp-2 hp-2 vLoading Vertical
Gui, Font ; default
Gui, Add, StatusBar
SB_SetParts(70, 70, 100)
SB_SetText("Length:", 1)
SB_SetText("Count:", 2)
Gui, Show
;--------------------------
; make DICT from text file
;--------------------------
FileRead, Dictionary, Words.txt
StrReplace(Dictionary, "`n",, WordCount), WordCount++
WA := A_IsUnicode ? 2 : 1
DICT := []
Loop, Parse, Dictionary, `n, `r
{
If (Percent := Round(100 * A_Index / WordCount)) > Prev_Percent {
GuiControl,, Loading, %Percent%
GuiControl,, Input, %Percent% `%
}
Prev_Percent := Percent
WordLength := StrLen(A_LoopField)
If Not IsObject(DICT[WordLength])
DICT[WordLength] := []
; allow Bob, English and I in Words.txt
StringLower, Keyword, A_LoopField
Keyword := make_Keyword(Keyword)
If Not IsObject(DICT[WordLength, Keyword])
DICT[WordLength, Keyword] := []
;-----------------------------------------------------------------------
; Each word in Dictionary gets pushed into the respective DICT[L, K].
; Push() function returns the index of the most recently pushed value.
; We then use this index to correct the size downwards,
; i.e. save space or adjust the capacity of a field in DICT[L, K].
;-----------------------------------------------------------------------
; E.g. let's say we pushed the 7th word to DICT[L, K] not knowing the 7.
; Push() gives us back the index = 7, and we can adjust the 7th field
; of DICT[L, K] to ByteSize = # characters (respecting ANSI/Unicode)
;-----------------------------------------------------------------------
; We do this exercise on each word in Dictionary,
; impact on performance is negligible, but:
; impact on memory used is noticeable (129 MB vs. 96 MB) on 370 k words
; impact on memory used is noticeable ( 40 MB vs. 30 MB) on 110 k words
;-----------------------------------------------------------------------
index := DICT[WordLength, Keyword].Push(A_LoopField)
DICT[WordLength, Keyword].SetCapacity(index, (WordLength + 1) * WA)
}
; save more space
Dictionary := ""
For each, WordLength_Obj in DICT
WordLength_Obj.SetCapacity(0)
;-----------------
; loading is done
;-----------------
SB_SetText("Words: " prettify_Number(WordCount), 3)
GuiControl, Hide, Loading
GuiControl, -Center -Disabled +gShowAnagrams, Input
GuiControl, Choose, Skip, 6
GuiControl, Focus, Input
GuiControl,, Input
Return ; end of auto-execute section
GuiClose:
ExitApp
;-------------------------------------------------------------------------------
ShowAnagrams: ; live display all anagrams of Input found in Dictionary
;-------------------------------------------------------------------------------
GuiControlGet, Input
GuiControlGet, Skip
GuiControlGet, LBox
InputLength := StrLen(Input)
SB_SetText("Length: " InputLength, 1)
If (InputLength > 12) { ; reduce flashing
GuiControl, +Disabled, Input
GuiControl, +Disabled, Skip
GuiControl, +Disabled, LBox
}
If (InputLength > Max_Input_Length) {
GuiControl,, LBox, |Input too long
GuiControl, -Disabled, Input
GuiControl, -Disabled, Skip
GuiControl, -Disabled, LBox
GuiControl, Focus, Input
Return
}
WordList := "", Count := 0
Start := QPC()
For each, Keyword in Combinations(Input, Skip)
For each, Anagram in DICT[StrLen(Keyword) // 2 + 1, Keyword]
WordList .= WordList ? "|" Anagram : Anagram, Count++
Sort, WordList, D| F LengthSort
TimeTaken := QPC() - Start ; time in s
GuiControl,, TimeTaken, %TimeTaken%
GuiControl, Hide, LBox
GuiControl,, LBox, % "|" (WordList ? WordList : "no anagrams for " Input)
GuiControl, Show, LBox
SB_SetText("Count: " Count, 2)
SB_SetText("Time: " Round(TimeTaken, 3) " s", 4)
GuiControl, -Disabled, Input
GuiControl, -Disabled, Skip
GuiControl, -Disabled, LBox
GuiControl, Focus, Input
Return
;-------------------------------------------------------------------------------
LengthSort(a, b) { ; word length specific custom sort
;-------------------------------------------------------------------------------
; Compacting this function to a one-liner, similar to the examples
; in the help file, runs about 20% faster than before.
;---------------------------------------------------------------------------
; primary criterion is string length, otherwise sort alphabetically
Return, StrLen(a) < StrLen(b) ? 1 : StrLen(a) > StrLen(b) ? -1
: a > b ? 1 : a < b ? -1 : 0
}
;-------------------------------------------------------------------------------
Combinations(String, Skip) { ; return an array with the sub-keywords
;-------------------------------------------------------------------------------
; sub-keywords are the keywords of all the substrings of String
;---------------------------------------------------------------------------
Keyword := make_Keyword(String) ; the only call here to make_Keyword()
Store := []
Store[0] := []
Store[0, Keyword] := True
Result := [Keyword]
Loop, % Skip - 1 {
Store[n := A_Index] := [] ; array of n* shortened strings
For ShortKey in Store[n - 1] {
Loop, % StrLen(ShortKey) // 2 + 1 {
; split the ShortKey and get next shorter keyword
Split1 := SubStr(ShortKey, 1, 2 * A_Index - 2) ; keep delim
Split3 := SubStr(ShortKey, 2 * A_Index + 1) ; drop delim
NextShorter := RTrim(Split1 Split3, ",") ; trim delim
If Not Store[n].HasKey(NextShorter) {
Store[n, NextShorter] := True
Result.Push(NextShorter)
}
}
}
}
Return, Result
}
;-------------------------------------------------------------------------------
make_Keyword(String) { ; return a sorted, comma separated string of chars
;-------------------------------------------------------------------------------
Keyword := LTrim(RegExReplace(String, "(.)", ",$1"), ",")
Sort, Keyword, D,
Return, Keyword
}
;-------------------------------------------------------------------------------
prettify_Number(n, s := ",") { ; insert thousand separators into a number
;-------------------------------------------------------------------------------
; credit for the RegEx goes to AHK forum user infogulch
; https://autohotkey.com/board/topic/50019-add-thousands-separator/
;---------------------------------------------------------------------------
IfLess, n, 0, Return, "-" prettify_Number(SubStr(n, 2), s)
Return, RegExReplace(n, "\G\d+?(?=(\d{3})+(?:\D|$))", "$0" s)
}
;-------------------------------------------------------------------------------
QPC() { ; microseconds precision
;-------------------------------------------------------------------------------
static Freq, init := DllCall("QueryPerformanceFrequency", "Int64P", Freq)
DllCall("QueryPerformanceCounter", "Int64P", Count)
Return, Count / Freq
}
/*--------- end of file --------------------------------------------------------
Note: The code will always display full length anagrams, e.g. 4-letter anagrams for "east", even if 4 or more letters are to be excluded.
That's caused by Result := [Keyword] in Combinations(). I like it, I leave it in, it's a feature!!
@Helgef: Thank you for the suggestion. Much better.