moviemadnessman Posted April 27, 2006 Share Posted April 27, 2006 (edited) Hi. My friend wants me to make him a program where he enters a string of number pairs, and it will tell him if it makes a valid tree graph or not. I've included a picture of a valid and invalid input, just to show an example.untitled.zip I gather there cannot be any cycles, since you can only go through a prticular block one time. Entering the number string 1 2 2 3 3 5 5 2, for example, would make the whole thing not a tree, as you would have a loop through 2->3->5 and back to 2. Likewise, each number can only go to one other number. My thinking was to make a GUI requesting the input, then potentially make use of arrays of some sort to make sure each number only goes to one place and there are no cycles, however, I can't say I understand AutoIT enough to do that, so any help would be appreciated. It's for some puzzle game or something that he has, and he hopes to use this to maximize his path through it, since you can't backtrack to any place you have already been. Don't remember the game. [EDIT] The spaces are necessary to correctly identify between the numbers and the pairs, since the numbers are between 1 and 999. Edited April 27, 2006 by moviemadnessman Link to comment Share on other sites More sharing options...
PsaltyDS Posted April 28, 2006 Share Posted April 28, 2006 Hi. My friend wants me to make him a program where he enters a string of number pairs, and it will tell him if it makes a valid tree graph or not. I've included a picture of a valid and invalid input, just to show an example.untitled.zipI gather there cannot be any cycles, since you can only go through a prticular block one time. Entering the number string 1 2 2 3 3 5 5 2, for example, would make the whole thing not a tree, as you would have a loop through 2->3->5 and back to 2. Likewise, each number can only go to one other number. My thinking was to make a GUI requesting the input, then potentially make use of arrays of some sort to make sure each number only goes to one place and there are no cycles, however, I can't say I understand AutoIT enough to do that, so any help would be appreciated.It's for some puzzle game or something that he has, and he hopes to use this to maximize his path through it, since you can't backtrack to any place you have already been. Don't remember the game.[EDIT] The spaces are necessary to correctly identify between the numbers and the pairs, since the numbers are between 1 and 999. I don't get it. Any node you reuse makes it invalid, so can't you just test every new destination to see if it has been used before? Is that all there is to it? Valuater's AutoIt 1-2-3, Class... Is now in Session!For those who want somebody to write the script for them: RentACoder"Any technology distinguishable from magic is insufficiently advanced." -- Geek's corollary to Clarke's law Link to comment Share on other sites More sharing options...
moviemadnessman Posted April 28, 2006 Author Share Posted April 28, 2006 I don't get it. Any node you reuse makes it invalid, so can't you just test every new destination to see if it has been used before? Is that all there is to it? The problem is that the destination can be used multiple times, but there can't be any loop arounds. Like, I could use the numbers 1-9 and have all the pairs go to 4, for example. I don't know how to explain what I'm looking for...the picture might help show the idea a little better, because I don't know how to convey the idea correctly.I haven't actually seen this game; the picture that is attached is one they sent me. I know it could be done, but I'm not sure how. Link to comment Share on other sites More sharing options...
Simucal Posted April 28, 2006 Share Posted April 28, 2006 (edited) Personally, If you want to post pictures I would goto www.imageshack.us and upload them there, then use the IMG tags in your post. If I have to download a zip file and then open the picture... I'll be a lot less likely to want to bother looking at it. But maybe that is just me and I'm lazy. Edited April 28, 2006 by Simucal AutoIt Scripts:Aimbot: Proof of Concept - PixelSearching Aimbot with several search/autoshoot/lock-on techniques.Sliding Toolbar - Add a nice Sliding Toolbar to your next script. Click the link to see an animation of it in action!FontInfo UDF - Get list of system fonts, or search to see if a particular font is installed.Get Extended Property UDF - Retrieve a files extended properties (e.g., video/image dimensions, file version, bitrate of song/video, etc) Link to comment Share on other sites More sharing options...
PsaltyDS Posted April 28, 2006 Share Posted April 28, 2006 (edited) The problem is that the destination can be used multiple times, but there can't be any loop arounds. Like, I could use the numbers 1-9 and have all the pairs go to 4, for example. I don't know how to explain what I'm looking for...the picture might help show the idea a little better, because I don't know how to convey the idea correctly.I haven't actually seen this game; the picture that is attached is one they sent me. I know it could be done, but I'm not sure how.I looked at your diagram (next time just post it as a gif or jpg, a zipped bmp is a pain). First thing I notice is the input does not define the 'tree' structure, only movement through it. Second thing is that the input does not show all steps, so the program has to determine the route for itself. This all means that the 'tree' is predefined somehow. Can you post that? If you contend the 'tree' is not predefined, but to be determined from the input, then how are you supposed to know from the sequence "3 5 6" that you have to go through node 2 to get from 5 to 6 (which is against the arrows of directionality, btw)?The "trees" and sequences given:4 | | v 3 --> 5 --> 2 --> 7 ^ ^ | | | | 1 6 Input = "3 5 6 2 5 2 1 5 4 2 7 2" Output = "Tree"3 <---------+ ^ | | | | | 1 --> 2 --> 4 --> 6 | ^ | | v | 5 ----+ Input = "1 2 5 6 2 3 6 3 4 5 2 4 4 6" Output = "Not a tree"Obviously, I'm not a programmer, so maybe I'm missing some beutiful "Tree Theory Logic" here... Edited April 28, 2006 by PsaltyDS Valuater's AutoIt 1-2-3, Class... Is now in Session!For those who want somebody to write the script for them: RentACoder"Any technology distinguishable from magic is insufficiently advanced." -- Geek's corollary to Clarke's law Link to comment Share on other sites More sharing options...
Matt Houston Posted April 28, 2006 Share Posted April 28, 2006 If i understand the picture correctly it's just about 3->5, 6->2... and not 3->5->6->2->5...! So no number is allowed as "starting point" more than once... But that sounds too easy...Look what i mean:Working example: 3 5 6 2 5 2 1 5 4 2 7 2This would be 6 pairs: (3->5, 6->2, 5->2, 1->5, 4->2, 7->2)Non-Working example: 1 2 5 6 2 3 6 3 4 5 2 4 4 6This would be 7 pairs: (1->2, 5->6, 2->3, 6->3, 4->5, 2->4, 4->6)So on the red and on the orange position we have the errors, because the same number is used twice. So you would only need to check if a number is on the first spot more than once... If missed something here - please don't blame me... It's been a really long working day for me - just ignore me then... BTW: What kind of game could that be? MattHouston Link to comment Share on other sites More sharing options...
moviemadnessman Posted April 28, 2006 Author Share Posted April 28, 2006 (edited) I looked at your diagram (next time just post it as a gif or jpg, a zipped bmp is a pain).My bad. I'll remember for next time.First thing I notice is the input does not define the 'tree' structure, only movement through it. Second thing is that the input does not show all steps, so the program has to determine the route for itself. This all means that the 'tree' is predefined somehow. Can you post that?The tree is not pre defined. If you contend the 'tree' is not predefined, but to be determined from the input, then how are you supposed to know from the sequence "3 5 6" that you have to go through node 2 to get from 5 to 6 (which is against the arrows of directionality, btw)?The "trees" and sequences given:4 | | v 3 --> 5 --> 2 --> 7 ^ ^ | | | | 1 6 Input = "3 5 6 2 5 2 1 5 4 2 7 2" Output = "Tree"3 <---------+ ^ | | | | | 1 --> 2 --> 4 --> 6 | ^ | | v | 5 ----+ Input = "1 2 5 6 2 3 6 3 4 5 2 4 4 6" Output = "Not a tree"Obviously, I'm not a programmer, so maybe I'm missing some beutiful "Tree Theory Logic" here... Well, in the case of knowing from the sequence "3 5 6" that you have to go through node 2 to get from 5 to 6, it would be written 3 5 5 2 2 6. Thus, it would know to go through node 2 to reach node 6 from node 5.If i understand the picture correctly it's just about 3->5, 6->2... and not 3->5->6->2->5...! So no number is allowed as "starting point" more than once... But that sounds too easy...No, that's correct. The numbers are entered in a long chain, but read as pairs.Look what i mean:Working example: 3 5 6 2 5 2 1 5 4 2 7 2This would be 6 pairs: (3->5, 6->2, 5->2, 1->5, 4->2, 7->2)Non-Working example: 1 2 5 6 2 3 6 3 4 5 2 4 4 6This would be 7 pairs: (1->2, 5->6, 2->3, 6->3, 4->5, 2->4, 4->6)So on the red and on the orange position we have the errors, because the same number is used twice. So you would only need to check if a number is on the first spot more than once... If missed something here - please don't blame me... It's been a really long working day for me - just ignore me then... BTW: What kind of game could that be? MattHoustonBasically, I can't figure out how to get AutoIT to determine if the starting number has been used multiple times. The idea of the tree is that you can enter 5 or 5000 pairs, and there will only be one possible route through all the numbers; no choice, in other words. If there is a choice in paths, then it is not a tree.As to what type of game it is, I have no real knowledge of it myself. But the concept would be the same as say a haunted house, where there is only 1 way through the house.Ah, the joys of programming for a person 3,000 miles away. Nothing like it... Edited April 28, 2006 by moviemadnessman Link to comment Share on other sites More sharing options...
PsaltyDS Posted April 29, 2006 Share Posted April 29, 2006 (edited) Getting closer. This version produces a list of limbs of the tree, and a list of nodes that include connected nodes. Just need to put it together for loop detection. expandcollapse popup; TreeDetect.au3 ; ; Tree or Loop? ; The input is a long string of node ID pairs. ; Node IDs are space delimited, pairs are also space delimited. ; Node pairs define limbs ; Output is either "Tree" or "Not a tree", base on if the limbs form a loop or not. #include<array.au3> $Input_1 = "3 5 6 2 5 2 1 5 4 2 7 2"; Should be a tree $Input_2 = "1 2 5 6 2 3 6 3 4 5 2 4 4 6"; Should not be a tree (contains a loop) _TreeDetect($Input_1) _TreeDetect($Input_2) Func _TreeDetect($sInput) ; Split input string into array and test for valid pairs ; $avPoints[0] = count of points Local $avPoints = StringSplit($sInput, " ") If $avPoints[0] < 2 Or Mod($avPoints[0], 2) <> 0 Then MsgBox(16, "Tree Detect", "Error: Input string too short or has odd number of elements!" Return 0 EndIf ;Create list of unique nodes from the input points ; $avNodes[0] = count of unique nodes ; [$n] = node ID Local $avNodes[2] $avNodes[0] = 1 $avNodes[1] = $avPoints[1] For $p = 2 To $avPoints[0] For $n = 1 To $avNodes[0] If $avPoints[$p] = $avNodes[$n] Then ContinueLoop 2 Next _ArrayAdd($avNodes, $avPoints[$p]) $avNodes[0] = UBound($avNodes) - 1 Next ; Put pairs of points into 2D arrays of Limbs ; $avLimbs[0][0] = count of pairs ; [n][0] = 'from' node id ; [n][1] = 'to' node id Local $avLimbs[ ($avPoints[0] / 2) + 1][2] $avLimbs[0][0] = UBound($avLimbs) - 1 For $n = 1 To $avLimbs[0][0] $avLimbs[$n][0] = $avPoints[ ($n * 2) - 1] $avLimbs[$n][1] = $avPoints[$n * 2] Next ; Display resulting limbs Local $sMsg = "Result: " & $avLimbs[0][0] & " input limbs:" For $n = 1 To $avLimbs[0][0] $sMsg = $sMsg & @CRLF & @TAB & "From " & $avLimbs[$n][0] & " to " & $avLimbs[$n][1] Next MsgBox(64, "Tree Detect", $sMsg) ; Create tree map listing all known paths from each node ; $avTreeMap[0][0] = count of mapped nodes ; [n][0] = node id ; [n][1] = "Node_1,Node_2,...,Node_n" list of connected nodes Local $avTreeMap[$avNodes[0] + 1][2] $avTreeMap[0][0] = $avNodes[0] For $n = 1 To $avTreeMap[0][0] $avTreeMap[$n][0] = $avNodes[$n] $avTreeMap[$n][1] = "" For $l = 1 To $avLimbs[0][0] If $avTreeMap[$n][0] = $avLimbs[$l][0] Then If Not StringInStr($avTreeMap[$n][1], $avLimbs[$l][1]) Then $avTreeMap[$n][1] = $avTreeMap[$n][1] & "," & $avLimbs[$l][1] EndIf Else If $avTreeMap[$n][0] = $avLimbs[$l][1] Then If Not StringInStr($avTreeMap[$n][1], $avLimbs[$l][0]) Then $avTreeMap[$n][1] = $avTreeMap[$n][1] & "," & $avLimbs[$l][0] EndIf EndIf EndIf If StringLeft($avTreeMap[$n][1], 1) = "," Then $avTreeMap[$n][1] = StringTrimLeft($avTreeMap[$n][1], 1) Next Next ; Display resulting tree map $sMsg = "Resulting tree map:" For $n = 1 To $avTreeMap[0][0] $sMsg = $sMsg & @TAB & @CRLF & "Node ID: " & $avTreeMap[$n][0] & " Connected nodes: " & $avTreeMap[$n][1] Next MsgBox(64, "Tree Detect", $sMsg) EndFunc ;==>_TreeDetect Edited April 29, 2006 by PsaltyDS Valuater's AutoIt 1-2-3, Class... Is now in Session!For those who want somebody to write the script for them: RentACoder"Any technology distinguishable from magic is insufficiently advanced." -- Geek's corollary to Clarke's law Link to comment Share on other sites More sharing options...
PsaltyDS Posted April 29, 2006 Share Posted April 29, 2006 Getting closer. This version produces a list of limbs of the tree, and a list of nodes that includes connected nodes. Just need to put it together for loop detection. Oops. Meant to edit and update the demo script in parent and replaced it instead. Anyway, arrived at new assumptions and tweaked the script. It seems now the input strings could not have come from a player path through a game, or a mouse-bot wandering a maze. Stopped looking for paths in the input string and only used them to define the limbs. Still work'n it... (good educational drill for me) Valuater's AutoIt 1-2-3, Class... Is now in Session!For those who want somebody to write the script for them: RentACoder"Any technology distinguishable from magic is insufficiently advanced." -- Geek's corollary to Clarke's law Link to comment Share on other sites More sharing options...
PsaltyDS Posted April 29, 2006 Share Posted April 29, 2006 Aha! Came to me while walking the dog... If it is a tree, then utimately all branches end in a dead end. So once I have my $avTreeMap array, I just need to recursively prune dead-end limbs until there are no limbs left, or there are only limbs that are not dead ends. At that point the only limbs left form (at least one) loop. Code attempt coming... Valuater's AutoIt 1-2-3, Class... Is now in Session!For those who want somebody to write the script for them: RentACoder"Any technology distinguishable from magic is insufficiently advanced." -- Geek's corollary to Clarke's law Link to comment Share on other sites More sharing options...
moviemadnessman Posted April 30, 2006 Author Share Posted April 30, 2006 Aha!Came to me while walking the dog... If it is a tree, then utimately all branches end in a dead end. So once I have my $avTreeMap array, I just need to recursively prune dead-end limbs until there are no limbs left, or there are only limbs that are not dead ends. At that point the only limbs left form (at least one) loop.Code attempt coming... Tested the current existing code...it is very close to what I need. I think this step will, ultimately, end up being the breakthrough. While it is cool to actually see the tree, adding the pruning code to determine what, if any, loops occur will allow the program to also tell the user if the number pairs are a successful tree or not a successful tree. I'll also probably add a small GUI so that the user can enter the number combinations themselves, as well as giving them the option to turn off the visual tree if they so desire not to see it.Thanks you greatly for your help...the arrays were definately throwing me off. Glad that you are using this as a learning experiance as well, and I can't wait to see the finished product. I'm sure my friend will appreciate your help as much as I do. Link to comment Share on other sites More sharing options...
Uten Posted April 30, 2006 Share Posted April 30, 2006 (edited) EDIT: Nope, this was not the answer as I focused to much on the img and not enough on the text. Would have to detected closed loops in the given number sequence, to be correct. If I understod your explanation, in the pictur, then your are not alowed to use a note as a starting point more than once (as in and point to another node twice). So basicaly all you have to do is to make a assosiative array and count occurances of a starting node? Local $dataErr = "1 2 5 6 2 3 6 3 4 5 2 4 4 6" Local $dataOK = "3 5 6 2 5 2 1 5 4 2 7 2" TreeTest($dataErr) TreeTest($dataOK) exit Func TreeTest($data) Local $arrFoo = TreeValidator($data) if $arrFoo[0] > 0 then ConsoleWrite('NOT A TREE: $data:=' & $data & @LF) Else ConsoleWrite('IS A TREE: $data:=' & $data & @LF) Endif EndFunc Func TreeValidator($data) ; $data is pattern of type <start> <to> <start> <to> <start> <to> $arrData = StringSplit($data, " ") Local $arrTree[9999]; making 9999 the node limit, Culd optimise with some kind of sparse array Local $arrFailingNodes[100] Local $i For $i = 1 to $arrData[0] Step 2 ConsoleWrite($arrData[$i] & @LF) $arrTree[$arrData[$i]] += 1 If $arrTree[$arrData[$i]] > 1 then ConsoleWrite("Failing node " & $arrData[$i] & " count:=" & $arrTree[$arrData[$i]] & @LF) $arrFailingNodes[0] += 1 ;TODO Check and handel array overflow (grow if nescasarry) $arrFailingNodes[$arrFailingNodes[0]] = $arrData[$i] EndIf Next Redim $arrFailingNodes[$arrFailingNodes[0] + 1] Return $arrFailingNodes EndFunc Probably not exactly what you wanted, but I'l make it my contribution Edited April 30, 2006 by Uten Please keep your sig. small! Use the help file. Search the forum. Then ask unresolved questions :) Script plugin demo, Simple Trace udf, TrayMenuEx udf, IOChatter demo, freebasic multithreaded dll sample, PostMessage, Aspell, Code profiling Link to comment Share on other sites More sharing options...
moviemadnessman Posted April 30, 2006 Author Share Posted April 30, 2006 EDIT: Nope, this was not the answer as I focused to much on the img and not enough on the text. Would have to detected closed loops in the given number sequence, to be correct. If I understod your explanation, in the pictur, then your are not alowed to use a note as a starting point more than once (as in and point to another node twice). So basicaly all you have to do is to make a assosiative array and count occurances of a starting node? Local $dataErr = "1 2 5 6 2 3 6 3 4 5 2 4 4 6" Local $dataOK = "3 5 6 2 5 2 1 5 4 2 7 2" TreeTest($dataErr) TreeTest($dataOK) exit Func TreeTest($data) Local $arrFoo = TreeValidator($data) if $arrFoo[0] > 0 then ConsoleWrite('NOT A TREE: $data:=' & $data & @LF) Else ConsoleWrite('IS A TREE: $data:=' & $data & @LF) Endif EndFunc Func TreeValidator($data) ; $data is pattern of type <start> <to> <start> <to> <start> <to> $arrData = StringSplit($data, " ") Local $arrTree[9999]; making 9999 the node limit, Culd optimise with some kind of sparse array Local $arrFailingNodes[100] Local $i For $i = 1 to $arrData[0] Step 2 ConsoleWrite($arrData[$i] & @LF) $arrTree[$arrData[$i]] += 1 If $arrTree[$arrData[$i]] > 1 then ConsoleWrite("Failing node " & $arrData[$i] & " count:=" & $arrTree[$arrData[$i]] & @LF) $arrFailingNodes[0] += 1 ;TODO Check and handel array overflow (grow if nescasarry) $arrFailingNodes[$arrFailingNodes[0]] = $arrData[$i] EndIf Next Redim $arrFailingNodes[$arrFailingNodes[0] + 1] Return $arrFailingNodes EndFunc Probably not exactly what you wanted, but I'l make it my contribution I can't confirm or deny anything regarding your code. When I run it on my machine, nothing happens. Link to comment Share on other sites More sharing options...
Uten Posted May 1, 2006 Share Posted May 1, 2006 I can't confirm or deny anything regarding your code. When I run it on my machine, nothing happens.What do you mean "nothing happens". It does not flash and beep if thats what your after Any how, as I wrote in my edit of the first attempt it would not cut it. Have been sleeping on it now and here is the second atempt. It will probably flash and beep WARNING: It is not clever or optimized. This is how it works: 1: Create a array with all starting nodes. Each starting node points to one or more nodes. 2: In the data array find starting nodes pointing to two or more nodes (we have two or more walking paths to follow) 3: When a node is found wallk all its paths, record all nodes we pass on the way. 4: In the resulting recording of passed nodes check if we pass any of them more than once. expandcollapse popup#include <Array.au3> Local $dataErr = "1 2 5 6 2 3 6 3 4 5 2 4 4 6" Local $dataOK = "3 5 6 2 5 2 1 5 4 2 7 2" ConsoleWrite("=== EXPECT 2 and 4 ===" & @LF) Local $arrData = MakeStructure($dataErr) TreeCheck($arrData) ;DataDump($arrData) ConsoleWrite("=== EXPECT NONE ===" & @LF) Local $arrData = MakeStructure($dataOK) TreeCheck($arrData) ;DataDump($arrData) ;TreeTest($dataOK) exit Func MakeStructure($data, $delimiter = " ") local $arrData = StringSplit($data, $delimiter) local $arrM[10000][10]; BIG and UGLY 9999 and 0 [?][0] = counter, [?][...] = node pointers local $i For $i = 1 to $arrData[0] Step 2 $arrM[$arrData[$i]][0] += 1 $arrM[$arrData[$i]][$arrM[$arrData[$i]][0]] = $arrData[$i + 1] Next Return $arrM EndFunc Func TreeCheck(ByRef $arrData) Local $i For $i = 1 to UBound($arrData) -1 if $arrData[$i][0] > 1 Then ConsoleWrite("Walking: " & $i & " : " ) $pasedNodes = TreeWalk($arrData, $i) & " " ConsoleWrite("$pasedNodes:=" & $pasedNodes & @LF) Local $arrFoo = StringSplit($pasedNodes, " ") for $foo = 1 to $arrFoo[0] If StringInStr($pasedNodes, " " & $arrFoo[$foo] & " ",0,2) Then ConsoleWrite("CYCLIC: $nodeID:=" & $i & " : " & $pasedNodes & @LF) Beep() msgbox(16, "WARNING CYCLIC NODE: $nodeID:=" & $i, "Passed nodes on walk: " & $pasedNodes & @LF) ExitLoop EndIf Next EndIf Next EndFunc Func TreeWalk(ByRef $arrData, $nodeID) Local $i Local $ret For $i = 1 to $arrData[$nodeID][0] $ret = $ret & " " & $arrData[$nodeID][$i] if $arrData[$arrData[$nodeID][$i]][0] > 1 Then ; TODO: Could end up in never ending loop $ret = $ret & TreeWalk($arrData, $arrData[$nodeID][$i]) Else $ret = $ret & " " & $arrData[$arrData[$nodeID][$i]][1] EndIf Next Return $ret EndFunc Func ArrayDump($arr, $header = "ArrayDump") Local $i, $ii for $i = 0 to Ubound($arr) - 1 if $arr[$i][0] <> 0 then ConsoleWrite($i & "(" & $arr[$i][0] & ") : ") for $ii = 1 to 9 if NOT $arr[$i][$ii] Then ExitLoop ConsoleWrite(" " & $arr[$i][$ii]) Next ConsoleWrite(@LF) endif Next EndFunc Please keep your sig. small! Use the help file. Search the forum. Then ask unresolved questions :) Script plugin demo, Simple Trace udf, TrayMenuEx udf, IOChatter demo, freebasic multithreaded dll sample, PostMessage, Aspell, Code profiling Link to comment Share on other sites More sharing options...
PsaltyDS Posted May 5, 2006 Share Posted May 5, 2006 OK, I have not been able to work on this for a few days, but it has been a worthwhile learning exercise and I'm back at it. Here is what I have so far. It works with the inputs provided, and detects loops pretty quickly. The next thing to do is simplify it (probably could use single dimension arrays throughout, to begin with), but it is fully functional now. I looked at the discussion of "walking the tree", but I don't think that is required, and is bound to be slower if the node count is really high. My solution went this way: 1. Split input string into node ID pairs. 2. Create a table of unique node IDs. 3. For each node ID, create a list of other nodes connected to it. 4. Any node ID with only one other node connected is a "deadend", and gets pruned out. 5. Repeat above pruning until: a. No node pairs are left - means no loop, or b. There are node pairs left, but no more deadends - means one or more loops The node IDs, BTW, do not have to be nubers, but the original post specified they are space delimited and must be in pairs. This is my current LoopDetect.au3: expandcollapse popup;============================================================================== ; LoopDetect.au3 ; ; Version 1.0 dated 04 May, 2006 ; By PsaltyDS at the AutoIT3 Support Forum ; ; Loop Detector Exercise ; The input is a long string of node ID pairs. ; Node IDs are space delimited, pairs are not delimited. ; Node pairs define limbs. ; Limbs are not necesarily in order, and may or may not form a single tree. ; Purpose is to determine if the limbs form a loop or not. ;============================================================================== #include<array.au3> ;============================================================================== ; This section provides test inputs to the _LoopDetect() function ;============================================================================== Dim $InputArray[1] ; Just add more _ArrayAdd() lines to try more inputs _ArrayAdd($InputArray, "3 5 6 2 5 2 1 5 4 2 7 2"); Should be a tree _ArrayAdd($InputArray, "1 2 5 6 2 3 6 3 4 5 2 4 4 6"); Should not be a tree (contains a loop) $InputArray[0] = UBound($InputArray) - 1 For $In = 1 To $InputArray[0] If _LoopDetect($InputArray[$In]) Then $TreeMsg = "At least one loop detected in the following string!" Else $TreeMsg = "No loop present in the following string." EndIf MsgBox(64, "Tree Detection Complete", $TreeMsg & @CRLF & _ "Input string was: " & $InputArray[$In]) Next ;============================================================================== ;======================================================== ; Function _LoopDetect($sInput) ; Receives a string of node ID pairs, space delimited ; Returns 1 for a loop detected or 0 for no loop ;======================================================== Func _LoopDetect($sInput) ; Split input string into array and test for valid pairs ; $avPoints[0] = count of points Local $avPoints = StringSplit($sInput, " ") If $avPoints[0] < 2 Or Mod($avPoints[0], 2) <> 0 Then MsgBox(16, "Tree Detect", "Error: Input string too short or has odd number of elements!") Return 0 EndIf ;Create list of unique nodes from the input points ; $avNodes[0] = count of unique nodes ; [$n] = node ID Local $avNodes[2] $avNodes[0] = 1 $avNodes[1] = $avPoints[1] For $p = 2 To $avPoints[0] For $n = 1 To $avNodes[0] If $avPoints[$p] = $avNodes[$n] Then ContinueLoop 2 Next _ArrayAdd($avNodes, $avPoints[$p]) $avNodes[0] = UBound($avNodes) - 1 Next ; Put pairs of points into 2D arrays of Limbs ; $avLimbs[0][0] = count of pairs ; [n][0] = 'from' node id ; [n][1] = 'to' node id Local $avLimbs[ ($avPoints[0] / 2) + 1][2] $avLimbs[0][0] = UBound($avLimbs) - 1 For $n = 1 To $avLimbs[0][0] $avLimbs[$n][0] = $avPoints[ ($n * 2) - 1] $avLimbs[$n][1] = $avPoints[$n * 2] Next ; Create tree map listing all known paths from each node ; $avTreeMap[0][0] = count of mapped nodes ; [n][0] = node id ; [n][1] = "Node_1,Node_2, ..., Node_n" list of connected nodes, comma delimited Local $avTreeMap[$avNodes[0] + 1][2] $avTreeMap[0][0] = $avNodes[0] For $n = 1 To $avTreeMap[0][0] $avTreeMap[$n][0] = $avNodes[$n] $avTreeMap[$n][1] = "" For $l = 1 To $avLimbs[0][0] If $avTreeMap[$n][0] = $avLimbs[$l][0] Then If Not StringInStr($avTreeMap[$n][1], $avLimbs[$l][1]) Then $avTreeMap[$n][1] = $avTreeMap[$n][1] & "," & $avLimbs[$l][1] EndIf Else If $avTreeMap[$n][0] = $avLimbs[$l][1] Then If Not StringInStr($avTreeMap[$n][1], $avLimbs[$l][0]) Then $avTreeMap[$n][1] = $avTreeMap[$n][1] & "," & $avLimbs[$l][0] EndIf EndIf EndIf If StringLeft($avTreeMap[$n][1], 1) = "," Then $avTreeMap[$n][1] = StringTrimLeft($avTreeMap[$n][1], 1) Next Next ; This while loop continues until no deadends are left or no nodes are left While 1 ; Remove limbs with only 1 connecting node (deadends) ; $avTreeMap[0][1] will hold cound of non-deadend limbs Local $iDeadEnd = 0 $avTreeMap[0][1] = $avTreeMap[0][0] For $l = 1 To $avTreeMap[0][0] Local $avNodes = StringSplit($avTreeMap[$l][1], ",") If $avNodes[0] < 2 Then ; Deadend limb found, $avTreeMap[$l][0] is the deadend node ; The other end's node is in $avTreeMap [$l][1] $iDeadEnd = 1 ; Need to search for the other node ID and remove the deadend node from its list For $n = 1 To $avTreeMap[0][0] If $avTreeMap[$n][0] = $avTreeMap[$l][1] Then ; Remove the deadend node from the list for this node $avNodes = StringSplit($avTreeMap[$n][1], ",") $avTreeMap[$n][1] = "" If $avNodes[0] > 1 Then For $x = 1 To $avNodes[0] If $avNodes[$x] <> $avTreeMap[$l][0] Then If $avTreeMap[$n][1] = "" Then $avTreeMap[$n][1] = $avNodes[$x] Else $avTreeMap[$n][1] = $avTreeMap[$n][1] & "," & $avNodes[$x] EndIf EndIf Next EndIf ExitLoop EndIf Next ; Null the entries for the deadend node $avTreeMap[$l][0] = "" $avTreeMap[$l][1] = "" ; Reduce the count of non-deadends $avTreeMap[0][1] = $avTreeMap[0][1] - 1 EndIf Next ; Test for done, if there are no nodes left, then no loops If $avTreeMap[0][1] = 0 Then Return 0 ; Test for done, there are nodes left, if no deadends were found, there is at least one loop If $iDeadEnd = 0 Then Return 1 ; Not done, delete null (pruned) entries from the table Local $avInterim[$avTreeMap[0][1] + 1][2] $avInterim[0][0] = $avTreeMap[0][1] $x = 1 For $n = 1 To $avTreeMap[0][0] If $avTreeMap[$n][0] <> "" Then $avInterim[$x][0] = $avTreeMap[$n][0] $avInterim[$x][1] = $avTreeMap[$n][1] $x = $x + 1 EndIf Next $avTreeMap = $avInterim WEnd EndFunc ;==>_LoopDetect ;======================================================== Trying to learn... Valuater's AutoIt 1-2-3, Class... Is now in Session!For those who want somebody to write the script for them: RentACoder"Any technology distinguishable from magic is insufficiently advanced." -- Geek's corollary to Clarke's law Link to comment Share on other sites More sharing options...
moviemadnessman Posted May 5, 2006 Author Share Posted May 5, 2006 OK, I have not been able to work on this for a few days, but it has been a worthwhile learning exercise and I'm back at it. Here is what I have so far. It works with the inputs provided, and detects loops pretty quickly. The next thing to do is simplify it (probably could use single dimension arrays throughout, to begin with), but it is fully functional now. I looked at the discussion of "walking the tree", but I don't think that is required, and is bound to be slower if the node count is really high. My solution went this way: 1. Split input string into node ID pairs. 2. Create a table of unique node IDs. 3. For each node ID, create a list of other nodes connected to it. 4. Any node ID with only one other node connected is a "deadend", and gets pruned out. 5. Repeat above pruning until: a. No node pairs are left - means no loop, or b. There are node pairs left, but no more deadends - means one or more loops The node IDs, BTW, do not have to be nubers, but the original post specified they are space delimited and must be in pairs. This is my current LoopDetect.au3: expandcollapse popup;============================================================================== ; LoopDetect.au3 ; ; Version 1.0 dated 04 May, 2006 ; By PsaltyDS at the AutoIT3 Support Forum ; ; Loop Detector Exercise ; The input is a long string of node ID pairs. ; Node IDs are space delimited, pairs are not delimited. ; Node pairs define limbs. ; Limbs are not necesarily in order, and may or may not form a single tree. ; Purpose is to determine if the limbs form a loop or not. ;============================================================================== #include<array.au3> ;============================================================================== ; This section provides test inputs to the _LoopDetect() function ;============================================================================== Dim $InputArray[1] ; Just add more _ArrayAdd() lines to try more inputs _ArrayAdd($InputArray, "3 5 6 2 5 2 1 5 4 2 7 2"); Should be a tree _ArrayAdd($InputArray, "1 2 5 6 2 3 6 3 4 5 2 4 4 6"); Should not be a tree (contains a loop) $InputArray[0] = UBound($InputArray) - 1 For $In = 1 To $InputArray[0] If _LoopDetect($InputArray[$In]) Then $TreeMsg = "At least one loop detected in the following string!" Else $TreeMsg = "No loop present in the following string." EndIf MsgBox(64, "Tree Detection Complete", $TreeMsg & @CRLF & _ "Input string was: " & $InputArray[$In]) Next ;============================================================================== ;======================================================== ; Function _LoopDetect($sInput) ; Receives a string of node ID pairs, space delimited ; Returns 1 for a loop detected or 0 for no loop ;======================================================== Func _LoopDetect($sInput) ; Split input string into array and test for valid pairs ; $avPoints[0] = count of points Local $avPoints = StringSplit($sInput, " ") If $avPoints[0] < 2 Or Mod($avPoints[0], 2) <> 0 Then MsgBox(16, "Tree Detect", "Error: Input string too short or has odd number of elements!") Return 0 EndIf ;Create list of unique nodes from the input points ; $avNodes[0] = count of unique nodes ; [$n] = node ID Local $avNodes[2] $avNodes[0] = 1 $avNodes[1] = $avPoints[1] For $p = 2 To $avPoints[0] For $n = 1 To $avNodes[0] If $avPoints[$p] = $avNodes[$n] Then ContinueLoop 2 Next _ArrayAdd($avNodes, $avPoints[$p]) $avNodes[0] = UBound($avNodes) - 1 Next ; Put pairs of points into 2D arrays of Limbs ; $avLimbs[0][0] = count of pairs ; [n][0] = 'from' node id ; [n][1] = 'to' node id Local $avLimbs[ ($avPoints[0] / 2) + 1][2] $avLimbs[0][0] = UBound($avLimbs) - 1 For $n = 1 To $avLimbs[0][0] $avLimbs[$n][0] = $avPoints[ ($n * 2) - 1] $avLimbs[$n][1] = $avPoints[$n * 2] Next ; Create tree map listing all known paths from each node ; $avTreeMap[0][0] = count of mapped nodes ; [n][0] = node id ; [n][1] = "Node_1,Node_2, ..., Node_n" list of connected nodes, comma delimited Local $avTreeMap[$avNodes[0] + 1][2] $avTreeMap[0][0] = $avNodes[0] For $n = 1 To $avTreeMap[0][0] $avTreeMap[$n][0] = $avNodes[$n] $avTreeMap[$n][1] = "" For $l = 1 To $avLimbs[0][0] If $avTreeMap[$n][0] = $avLimbs[$l][0] Then If Not StringInStr($avTreeMap[$n][1], $avLimbs[$l][1]) Then $avTreeMap[$n][1] = $avTreeMap[$n][1] & "," & $avLimbs[$l][1] EndIf Else If $avTreeMap[$n][0] = $avLimbs[$l][1] Then If Not StringInStr($avTreeMap[$n][1], $avLimbs[$l][0]) Then $avTreeMap[$n][1] = $avTreeMap[$n][1] & "," & $avLimbs[$l][0] EndIf EndIf EndIf If StringLeft($avTreeMap[$n][1], 1) = "," Then $avTreeMap[$n][1] = StringTrimLeft($avTreeMap[$n][1], 1) Next Next ; This while loop continues until no deadends are left or no nodes are left While 1 ; Remove limbs with only 1 connecting node (deadends) ; $avTreeMap[0][1] will hold cound of non-deadend limbs Local $iDeadEnd = 0 $avTreeMap[0][1] = $avTreeMap[0][0] For $l = 1 To $avTreeMap[0][0] Local $avNodes = StringSplit($avTreeMap[$l][1], ",") If $avNodes[0] < 2 Then ; Deadend limb found, $avTreeMap[$l][0] is the deadend node ; The other end's node is in $avTreeMap [$l][1] $iDeadEnd = 1 ; Need to search for the other node ID and remove the deadend node from its list For $n = 1 To $avTreeMap[0][0] If $avTreeMap[$n][0] = $avTreeMap[$l][1] Then ; Remove the deadend node from the list for this node $avNodes = StringSplit($avTreeMap[$n][1], ",") $avTreeMap[$n][1] = "" If $avNodes[0] > 1 Then For $x = 1 To $avNodes[0] If $avNodes[$x] <> $avTreeMap[$l][0] Then If $avTreeMap[$n][1] = "" Then $avTreeMap[$n][1] = $avNodes[$x] Else $avTreeMap[$n][1] = $avTreeMap[$n][1] & "," & $avNodes[$x] EndIf EndIf Next EndIf ExitLoop EndIf Next ; Null the entries for the deadend node $avTreeMap[$l][0] = "" $avTreeMap[$l][1] = "" ; Reduce the count of non-deadends $avTreeMap[0][1] = $avTreeMap[0][1] - 1 EndIf Next ; Test for done, if there are no nodes left, then no loops If $avTreeMap[0][1] = 0 Then Return 0 ; Test for done, there are nodes left, if no deadends were found, there is at least one loop If $iDeadEnd = 0 Then Return 1 ; Not done, delete null (pruned) entries from the table Local $avInterim[$avTreeMap[0][1] + 1][2] $avInterim[0][0] = $avTreeMap[0][1] $x = 1 For $n = 1 To $avTreeMap[0][0] If $avTreeMap[$n][0] <> "" Then $avInterim[$x][0] = $avTreeMap[$n][0] $avInterim[$x][1] = $avTreeMap[$n][1] $x = $x + 1 EndIf Next $avTreeMap = $avInterim WEnd EndFunc ;==>_LoopDetect ;======================================================== Trying to learn... That works exactly as it is needed to (except a user input, but that's easy enough to add). Thank you to everyone who helped with this, I hope everyone learned something from it. I know that I'll use this code to furthur understand arrays. Thanks again, guys. And especially PsaltyDS - thank you very much. Link to comment Share on other sites More sharing options...
Recommended Posts
Create an account or sign in to comment
You need to be a member in order to leave a comment
Create an account
Sign up for a new account in our community. It's easy!
Register a new accountSign in
Already have an account? Sign in here.
Sign In Now