 |
AutoHotkey Community
Let's help each other out
|
| View previous topic :: View next topic |
| Author |
Message |
adamrgolf
Joined: 28 Dec 2006
Posts: 440
|
 Posted: Wed Mar 10, 2010 12:06 pm Post subject: Searching diagonally? |
 |
|
I'm curious the best way to search a group of letters diagonally, like in a word search puzzle. Obviously it is easy to search forwards and backwards by simply reversing a string, but diagonally seems much harder to figure out.
Assume this is the puzzle:
And I want to find the word "DOG" and return the starting and end positions. D would be (3,1) and G would be (1,3).
I want to create a function that does not assume that forwards is the only option nor that all puzzles are only 3 characters wide/tall, so it should also work with this puzzle:
| Code: | A B C D
E G G H
I J O L
M N O D |
etc...
Would anyone like to help me out with this? This type of thing is probably easier than it looks; but for me, I can't seem to wrap my head around it.
Thanks for any help!
Adam |
|
| Back to top |
|
 |
any0ne
Guest
|
| Posted: Wed Mar 10, 2010 2:35 pm Post subject: |
|
|
We AHKers call that a Laszlo challenge!!  |
|
| Back to top |
|
|
adamrgolf
Joined: 28 Dec 2006
Posts: 440
|
| Posted: Wed Mar 10, 2010 2:37 pm Post subject: |
|
|
| any0ne wrote: | | We AHKers call that a Laszlo challenge!! |
hehe, I also just realized that searching up and down might be just as hard. That should be considered as well. Hmm.... |
|
| Back to top |
|
|
adamrgolf
Joined: 28 Dec 2006
Posts: 440
|
| Posted: Wed Mar 10, 2010 2:43 pm Post subject: |
|
|
I figured out a way to "rotate" the puzzle to allow searching up and down:
| Code: | Letters=
(
R H H V M A Y Q C U Q D P R H B K D
D P X G H S V O D W C P M L U G L K
Z Q S I X S G O U I C K O R B K K X
W K Z H T V P N V J P Q L N G D M A
W X A S I R U S Y R X E C I V T B Z
A F E R E L U R D J Z G R U V U V Y
O J K E C V A B R Y M S O B O Z F B
I Y H N Y A E C T K A S N K Z V H Q
T C Z I O E D M I M J J C Q H S O I
L S I I Z I W E L M T O F X B C Z U
S Q U O H N T F S E O P O Z Z X P S
T O C H D Z R A S S E C H D S Y W W
C H A G R I N N X I A P D L K D G G
U O M V Z C U J U A X R J F T N B R
M E N L M S S V L U L W G X A C H L
K D M N W S T G D Z L E B U Z G C L
D X X B S K I L L F V I R B U U W F
D V C P R C D I V E R S I O N K U Z
)
StringReplace,Letters,Letters,%A_Space%,,All
Loop,Parse,Letters,`n
{
Loop,Parse,A_LoopField
var%A_Index% := var%A_Index% A_LoopField
}
Letters_R := var1 "`n" var2 "`n" var3 "`n" var4 "`n" var5 "`n" var6 "`n" var7 "`n" var8 "`n" var9 "`n" var10 "`n" var11 "`n" var12 "`n" var13 "`n" var14 "`n" var15 "`n" var16 "`n" var17 "`n" var18
MsgBox % Letters_R |
|
|
| Back to top |
|
|
answer4u
Guest
|
| Posted: Wed Mar 10, 2010 3:03 pm Post subject: |
|
|
| Perhaps an oversimplified answer, but if you break the data down into a 2D Grid/Array, then it becomes sheer mathematics on extracting the letters in a diagonal format to check for words. I would recommend AHKL for its object support here. |
|
| Back to top |
|
|
adamrgolf
Joined: 28 Dec 2006
Posts: 440
|
| Posted: Wed Mar 10, 2010 3:12 pm Post subject: |
|
|
| answer4u wrote: | | Perhaps an oversimplified answer, but if you break the data down into a 2D Grid/Array, then it becomes sheer mathematics on extracting the letters in a diagonal format to check for words. I would recommend AHKL for its object support here. |
Yea, I thought about AHKL too, but its figuring out the mathematics that is confusing too...  |
|
| Back to top |
|
|
adamrgolf
Joined: 28 Dec 2006
Posts: 440
|
| Posted: Wed Mar 10, 2010 3:51 pm Post subject: |
|
|
Well, this definetly is not very pretty, but I've figured out a way to rearrange the letters into diagonal lines:
| Code: | #SingleInstance,Force
Letters=
(
R H H V M A Y Q C U Q D P R H B K D
D P X G H S V O D W C P M L U G L K
Z Q S I X S G O U I C K O R B K K X
W K Z H T V P N V J P Q L N G D M A
W X A S I R U S Y R X E C I V T B Z
A F E R E L U R D J Z G R U V U V Y
O J K E C V A B R Y M S O B O Z F B
I Y H N Y A E C T K A S N K Z V H Q
T C Z I O E D M I M J J C Q H S O I
L S I I Z I W E L M T O F X B C Z U
S Q U O H N T F S E O P O Z Z X P S
T O C H D Z R A S S E C H D S Y W W
C H A G R I N N X I A P D L K D G G
U O M V Z C U J U A X R J F T N B R
M E N L M S S V L U L W G X A C H L
K D M N W S T G D Z L E B U Z G C L
D X X B S K I L L F V I R B U U W F
D V C P R C D I V E R S I O N K U Z
)
StringReplace,Letters,Letters,%A_Space%,,All
Loop,Parse,Letters,`n
{
space =
Loop % A_Index - 1
space := space A_Tab
B_Letters := B_Letters space A_LoopField "`n"
}
StringTrimRight,B_Letters,B_Letters,1
Loop,Parse,B_Letters,`n
{
Loop,Parse,A_LoopField
var%A_Index% := var%A_Index% A_LoopField ; or var%A_Index% := A_LoopField var%A_Index%
}
Loop,35
Letters_D := Letters_D var%A_Index% "`n"
StringReplace,Letters_D,Letters_D,%A_Tab%,,All
StringTrimRight,Letters_D,Letters_D,1
Letters_D2 := AddSpaces(Letters_D)
msgbox '%Letters_D2%'
Return
AddSpaces(x) {
return RegExReplace(x, "(?(?<=\.)(*COMMIT)(*FAIL))\w(?=(\w{1})+(\W|$))", "$0 ")
} |
|
|
| Back to top |
|
|
answer4u
Guest
|
| Posted: Wed Mar 10, 2010 3:57 pm Post subject: |
|
|
Quick Example: | Code: | Letters=
(
R H H V M A Y Q C U Q D P R H B K D
D P X G H S V O D W C P M L U G L K
Z Q S I X S G O U I C K O R B K K X
W K Z H T V P N V J P Q L N G D M A
W X A S I R U S Y R X E C I V T B Z
A F E R E L U R D J Z G R U V U V Y
O J K E C V A B R Y M S O B O Z F B
I Y H N Y A E C T K A S N K Z V H Q
T C Z I O E D M I M J J C Q H S O I
L S I I Z I W E L M T O F X B C Z U
S Q U O H N T F S E O P O Z Z X P S
T O C H D Z R A S S E C H D S Y W W
C H A G R I N N X I A P D L K D G G
U O M V Z C U J U A X R J F T N B R
M E N L M S S V L U L W G X A C H L
K D M N W S T G D Z L E B U Z G C L
D X X B S K I L L F V I R B U U W F
D V C P R C D I V E R S I O N K U Z
)
table := Grid( letters )
MsgBox, % table.diagonalup( 16 ) ; param is row number
Return
Grid( data ) {
obj := object( "diagonalup", "diagonalup" )
array := object( "base", obj )
Loop, Parse, data, `n, `r
{
n := A_Index
Loop, Parse, A_LoopField, %A_Space%
array[ n, A_Index ] := A_LoopField
}
Return, array
}
DiagonalUp( obj, row ) {
If ( row > obj._MaxIndex() )
Return, "ERROR"
Loop, %row%
string .= obj[ row-A_Index+1, A_Index ]
Return, string
} |
|
|
| Back to top |
|
|
da_boogie_man
Guest
|
| Posted: Wed Mar 10, 2010 5:17 pm Post subject: |
|
|
What if you were to assign each letter to a variable "array"?
var_%row%_%col%
Then you would have your word list:
wrdList =
(
top
dog
banana
auto
hot
key
rocks
)
"Loop, Parse" the list and search for the first letter, when it finds a match use your array to search for the 2nd letter in the surrounding letters. If it's found the 3rd letter should be in the same direction.
Dang it! Now I have to try this! 
DBM |
|
| Back to top |
|
|
Guest
|
| Posted: Wed Mar 10, 2010 6:33 pm Post subject: |
|
|
instead of searching surroundings
shouldnt it be easier to produce 4 list? (might need some brain to produce the equation)
example:
can produce:
1. abcdefg
2. adgbehcfi
3. adbgechfi
4. cbfaeidhg
and then search the string
if found, then check position |
|
| Back to top |
|
|
adamrgolf
Joined: 28 Dec 2006
Posts: 440
|
| Posted: Wed Mar 10, 2010 6:35 pm Post subject: |
|
|
| Anonymous wrote: | instead of searching surroundings
shouldnt it be easier to produce 4 list? (might need some brain to produce the equation)
example:
can produce:
1. abcdefg
2. adgbehcfi
3. adbgechfi
4. cbfaeidhg
and then search the string
if found, then check position |
This is what I did (partially) in my example. |
|
| Back to top |
|
|
adamrgolf
Joined: 28 Dec 2006
Posts: 440
|
| Posted: Wed Mar 10, 2010 7:02 pm Post subject: |
|
|
Here is an example that does not require generating/rearranging multiple lists, I'm sure this can be shortened dramatically, but it works...
| Code: | #SingleInstance,Force
Letters=
(
R H H V M A Y Q C U Q D P R H B K D
D P X G H S V O D W C P M L U G L K
Z Q S I X S G O U I C K O R B K K X
W K Z H T V P N V J P Q L N G D M A
W X A S I R U S Y R X E C I V T B Z
A F E R E L U R D J Z G R U V U V Y
O J K E C V A B R Y M S O B O Z F B
I Y H N Y A E C T K A S N K Z V H Q
T C Z I O E D M I M J J C Q H S O I
L S I I Z I W E L M T O F X B C Z U
S Q U O H N T F S E O P O Z Z X P S
T O C H D Z R A S S E C H D S Y W W
C H A G R I N N X I A P D L K D G G
U O M V Z C U J U A X R J F T N B R
M E N L M S S V L U L W G X A C H L
K D M N W S T G D Z L E B U Z G C L
D X X B S K I L L F V I R B U U W F
D V C P R C D I V E R S I O N K U Z
)
StringReplace,Letters,Letters,%A_Space%,,All
StringReplace,Letters,Letters,`n,,All
Word := "DIVERSION"
pos := SearchNorm(Word)
If InStr(pos,"0`,0")
pos := SearchNorm(Flip(Word))
If InStr(pos,"0`,0")
pos := SearchDiag(Word)
If InStr(pos,"0`,0")
pos := SearchDiag(Flip(Word))
msgbox %Word% found at: %pos%
Word := "GRASS"
pos := SearchNorm(Word)
If InStr(pos,"0`,0")
pos := SearchNorm(Flip(Word))
If InStr(pos,"0`,0")
pos := SearchDiag(Word)
If InStr(pos,"0`,0")
pos := SearchDiag(Flip(Word))
msgbox %Word% found at: %pos%
Return
SearchNorm(Word) {
Global Letters
fp := RegExMatch(Letters,Word)
If fp=0
pos := "(0`,0)"
If (fp <= 18) AND (fp > 0)
pos := "(1," fp ")"
if fp > 18
{
bp := fp
Loop,
{
b_index := A_Index + 1
bp := bp - 18
If bp <=18
Break
}
Pos :="(" b_index "," Mod(fp,18) ")"
}
If ! InStr(pos,"0`,0")
Return pos
String=
Loop,parse,Word
String := String A_LoopField "\w{17}"
StringTrimRight,String,String,6
fp := RegExMatch(Letters,String)
If fp=0
pos := "(0`,0)"
If (fp <= 18) AND (fp > 0)
pos := "(1," fp ")"
if fp > 18
{
bp := fp
Loop,
{
b_index := A_Index + 1
bp := bp - 18
If bp <=18
Break
}
Pos :="(" b_index "," Mod(fp,18) ")"
}
If ! InStr(pos,"0`,0")
Return pos
Return pos
}
SearchDiag(Word) {
Global Letters
String=
Loop,parse,Word
String := String A_LoopField "\w{18}"
StringTrimRight,String,String,6
fp := RegExMatch(Letters,String)
If fp=0
pos := "(0`,0)"
If (fp <= 18) AND (fp > 0)
pos := "(1," fp ")"
if fp > 18
{
bp := fp
Loop,
{
b_index := A_Index + 1
bp := bp - 18
If bp <=18
Break
}
Pos :="(" b_index "," Mod(fp,18) ")"
}
If ! InStr(pos,"0`,0")
Return pos
String=
Loop,parse,Word
String := String A_LoopField "\w{16}"
StringTrimRight,String,String,6
fp := RegExMatch(Letters,String)
If fp=0
pos := "(0`,0)"
If (fp <= 18) AND (fp > 0)
pos := "(1," fp ")"
if fp > 18
{
bp := fp
Loop,
{
b_index := A_Index + 1
bp := bp - 18
If bp <=18
Break
}
Pos :="(" b_index "," Mod(fp,18) ")"
}
If ! InStr(pos,"0`,0")
Return pos
Return pos
}
Flip( Str) {
Loop, Parse, Str
nStr=%A_LoopField%%nStr%
Return nStr
} |
|
|
| Back to top |
|
|
jethrow
Joined: 24 May 2009
Posts: 1907
Location: Iowa, USA
|
| Posted: Thu Mar 11, 2010 3:50 am Post subject: |
|
|
So I spent way to long trying this, but here's an example bridging off a previous post - where the variable "letters" is the same as in the previous posts ( requires AHKL ):
| Code: | table := Grid( letters )
MsgBox, 0, % "Row, Col", % table.word( "sunset" )
MsgBox, 0, % "Row, Col", % table.word( "DIVERSION" )
Return
Grid( data ) { ; separates data into 2D Array/Object
obj := object( "row", "row"
, "column", "column"
, "diagonal", "diagonal"
, "diagonalcoord", "diagonalcoord"
, "word", "word" )
array := object( "base", obj )
Loop, Parse, data, `n, `r
{
n := A_Index
Loop, Parse, A_LoopField, %A_Space%
array[ n, A_Index ] := A_LoopField
}
array.rows := array._MaxIndex(), array.columns := array[1]._MaxIndex()
array.diagonals := array.rows+array.columns-1
Return, array
}
Row( obj, item, rev=0 ) { ; returns row string
Loop, % obj.columns
string .= rev ? obj[ item, obj.columns-A_Index+1 ] : obj[ item, A_Index ]
Return, string
}
Column( obj, item, rev=0 ) { ; returns columns string
Loop, % obj.rows
string .= rev ? obj[ obj.rows-A_Index+1, item ] : obj[ A_Index, item ]
Return, string
}
Diagonal( obj, item ) { ; gets a diagonals string of letters
If ( item > obj.diagonals )
Return, "ERROR"
Loop, % obj.diagonals
string .= item>0 ? obj[ item-A_Index+1, A_Index ] : obj[ A_Index, obj.columns+item+A_Index ]
Return, string
}
DiagonalCoord( obj, item, pos ) { ; returns the "R,C" position of a position in a diagonal string
If ( item > obj.diagonals )
Return, "ERROR"
If ( item>0 )
If ( item <= obj.rows )
row := item-pos+1, col := pos
Else
row := obj.rows-pos+1, col := pos + ( item-obj.rows )
Else
If ( item >= -1*obj.columns )
row := pos, col := obj.columns+item+pos
Else
row := pos + ( -1*obj.columns-item ), col := pos
Return, row>0 && row<=obj.rows && col>0 && col<=obj.columns
? row "," col : "Invalid Parameters"
}
Word( obj, word ) { ; searches for a word
If ( word = "" )
Return, "No Word"
Loop, % obj.rows ; horizontal search
If pos := InStr( obj.row( A_Index ), word )
Return, A_Index "," pos
Else If pos := InStr( obj.row( A_Index, "Reverse" ), word )
Return, A_Index "," obj.columns-pos+1
Loop, % obj.columns ; vertical search
If pos := InStr( obj.column( A_Index ), word )
Return, pos "," A_Index
Else If pos := InStr( obj.column( A_Index, "Reverse" ), word )
Return, obj.rows-pos+1 "," A_Index
While( !item && A_Index<=obj.diagonals ) { ; diagonal search
string := obj.diagonal( A_Index )
string2 := obj.diagonal( -1 * A_Index )
If pos := InStr( string, word )
item := A_Index
Else If pos := InStr( Flip(string), word )
item := A_Index, pos := StrLen(string)-pos+1
Else If pos := InStr( string2, word )
item := -1 * A_Index
Else If pos := InStr( Flip(string2), word )
item := -1 * A_Index, pos := StrLen(string)-pos+1
}
Return, item ? obj.diagonalCoord( item, pos ) : "N\A"
}
Flip(in) { ; http://www.autohotkey.com/forum/topic46040.html&start=5
VarSetCapacity(out, n:=StrLen(in))
Loop %n%
out .= SubStr(in, n--, 1)
return out
} |
Also, if anyone cares, the numbering of the diagonal strings is like this: | Code: | Going up/right Going down/right
1 -4 -3 -2 -1
2 -5
3 -6
4 5 6 7 -7
|
_________________
- in case I forgot to smile
Basic Webpage Controls
COM Object Reference |
|
| Back to top |
|
|
|
|
You can post new topics in this forum
You can reply to topics in this forum
|
Powered by phpBB © 2001, 2005 phpBB Group
|
FAQ
Search
Memberlist
Register
Profile
Log in to check your private messages
Log in
