SitePoint Sponsor

User Tag List

Results 1 to 11 of 11
  1. #1
    SitePoint Member
    Join Date
    Jan 2009
    Posts
    5
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)

    complex grouping of array data

    I've been hitting the wall for the last 4 days on this one, and would appreciate any ideas that anyone may have regarding it.

    Here's the overview:

    Imagine a puzzle, where groups of pieces should theoretically be able to be snapped together outside of the final resting place. To make it simple to understand lets just say that it is a 5 x 5 grid labeled A - Y like this:
    a b c d e
    f g h i j
    k l m n o
    p q r s t
    u v w x y

    a should be able to snap to b and f but no others
    b should be able to snap to a,c,and g but no others
    ...etc.


    OK now I have all the things worked out that I thought would be difficult, when a piece is layed down, it checks to see if that piece is in the correct place relative to the other pieces on the board, and i have it creating an array of all pieces that are in the correct spot, as well as a large multi demensional array containing all of the possible joins for each of the pieces (a connects to b or f, etc)

    The problem lies when more than 2 clusters are correct on the board.
    For an example, lets say that pieces a,b,c,u,v,w are all in the correct spot relative to each other, and an array is returned with these pieces.

    I now need to loop through them all and determine that a,b,c belong together and u,v,w belong together. (and ideally create an array for each letter saying all pieces that should be joined to it.. example :
    cluster[a] = b,c
    cluster[b] = a,c

    Here's he basic code I have been working with:

    Code:
    //clus= all pieces that are candidates to be clustered together
    for(i=0;i<clus.length;i++){
    	clusters[clus[i]] = [];
    	thiscluster = new Array();
    	//cluster = an array containing all of the possible matches for each piece
    	for(a in cluster[clus[i]]){
                   //in_array = same as php in_array funtion .. rreturns true if the item is found in the array
    		if(in_array(cluster[clus[i]][a],clus)){
    			thiscluster[thiscluster.length] = cluster[clus[i]][a];
    		}	
    		else{
    			for(m in clus){	
    				if(in_array(clus[i],cluster[clus[m]]) || in_array(clus[m],cluster[clus[i]])){
    					thiscluster[thiscluster.length] = clus[m];
    				}
    			}
    		}
    	}
    	clusters[clus[i]] = thiscluster;
    }
    I have a few 100 different variations on the above, but basically this has been my plan of attack, and it's ok for one or two pieces in a cluster, and only one cluster, but if there are multiple clusters/multiple pieces in each cluster, it gets really buggy...

    It's one of those problems that seems so simple, yet once you dig into it, seems like it can not be done.

    If anyone has any ideas on a better method to attack this, I would be forever grateful.

  2. #2
    Unobtrusively zen silver trophybronze trophy
    paul_wilkins's Avatar
    Join Date
    Jan 2007
    Location
    Christchurch, New Zealand
    Posts
    14,729
    Mentioned
    104 Post(s)
    Tagged
    4 Thread(s)
    This sounds like a jigsaw puzzle where each piece is allowed to lock correctly into only one connector.

    Is it possible for each piece to have four properties into which pieces are allowed to snap on to.

    Each piece could be an individual object which contains the necessary logic to determine if a certain piece is allowed to snap on to it at a certain point.
    They could also be able to report on which pieces are currently attached to it.
    Programming Group Advisor
    Reference: JavaScript, Quirksmode Validate: HTML Validation, JSLint
    Car is to Carpet as Java is to JavaScript

  3. #3
    SitePoint Member
    Join Date
    Jan 2009
    Posts
    5
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    hi pmw .. thank you for the post ...

    your are correct, it is similar to a jigsaw puzzle in functionality, just slightly less proportional ... some pieces could have 9 or 10 neighboring pieces. But for simplicity's sake, I just went with a simple grid like example since the logic should in essence be the same.

    I do have definitions in place for each piece as an individual object, but can not put a finger on how to determine if abc should be clustered apart from xyz, while running the data through the loops.

    I know it seems simple but if you disect it a little bit you may see where my problem is occuring:

    example:
    a,b,c found as positioned correctly on the board now we need to run through those pieces to find out which ones should be grouped:

    1) loop through each piece and use the object join definitions
    a) Piece a - can be joined to "piece b" .. match .. but not a match for "piece c" -- would return false
    b) Piece b - can be joined to both a and c .. match .. return true
    c)Piece c -- can only be joined to piece b but not piece a .. return false..

    This is a very simple example .. and I have a solution for it if this was merely my problem, but imagine if 20 pieces were in the cluster, and it needed to form 3 or 4 separate clusters...

    Still seems simple in my mind, but I cannot create a function to answer all possibilities

  4. #4
    Unobtrusively zen silver trophybronze trophy
    paul_wilkins's Avatar
    Join Date
    Jan 2007
    Location
    Christchurch, New Zealand
    Posts
    14,729
    Mentioned
    104 Post(s)
    Tagged
    4 Thread(s)
    What is the purpose of these clusters, for perhaps with a better idea of what it's intended for, it might spark an idea from someone about already created solutions for that particular problem.
    Programming Group Advisor
    Reference: JavaScript, Quirksmode Validate: HTML Validation, JSLint
    Car is to Carpet as Java is to JavaScript

  5. #5
    SitePoint Member
    Join Date
    Jan 2009
    Posts
    5
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    Thanks for the advise pmw. I know how difficult it is to try and follow someone elses train of thought, and while I know exactly what I am talking about, I'm sure that no one else does..

    if we go back to the jig saw puzzle example .. imagine as if you are assembling the puzzle in stages one "cluster" at a time .. you need to be able to move the whole cluster independently into the correct position as one whole.

    The logic I am using to determine the pieces that fit together, is basically using the position of the active element and checking that position relative to the final resting place. Then iterating through all pieces on the board to see if any other piece is in the same relative position based on the active piece. That part is good, and it returns an array of all pieces that are correctly positioned relative to the active piece.

    Next logical step is to iterate through all pieces and check the "join" definitions to see which pieces are allowed to fit together, since I need to produce clusters based on the pieces that are physically connected to one another.

    a b c
    d e f
    g h i
    j k l

    So in the example above if a,b,c,j,k are all positioned correctly relative to the active piece, I will have an array with all of those pieces in it.

    Now there are two obvious clusters a,b,c and j,k

    but I can't find a way to determine this without running through 15 loops, and I am sure that there is a way to run a match like this more productively, I am just drawing a complete blank on it.. just running in circles.

    If anyone has any thoughts at all, even if you think it's a bad idea, please let me know... It may spark something that will finally let me finish this project.

  6. #6
    Unobtrusively zen silver trophybronze trophy
    paul_wilkins's Avatar
    Join Date
    Jan 2007
    Location
    Christchurch, New Zealand
    Posts
    14,729
    Mentioned
    104 Post(s)
    Tagged
    4 Thread(s)
    This sounds like you require some kind of binary tree solution.

    What ultimately are you wanting to achieve. Is it, from a set of correctly placed and joined elements, you want know how many groups (clusters) they contain and what each group is made up of?
    Programming Group Advisor
    Reference: JavaScript, Quirksmode Validate: HTML Validation, JSLint
    Car is to Carpet as Java is to JavaScript

  7. #7
    SitePoint Wizard bronze trophy
    Join Date
    Jul 2008
    Posts
    5,757
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    Quote Originally Posted by rheziel View Post
    ... some pieces could have 9 or 10 neighboring pieces.
    Can you elaborate?
    There is more than a single distinct peice which can be joined directly to the left(or right/top/bottom) of a given peice? eg in abc I would think the only thing that could be joined to the left of b would be a. Or is there no such restriction on which side another peice must reside on, it just needs to touch it, in order to be joined?

    A cluster can only fit together in a precise predefined order, in order for all the peices in the cluster to be joined?

    Off Topic:

    I wish sitepoint got more intresting questions like this
    Last edited by crmalibu; Jan 20, 2009 at 09:27.

  8. #8
    Unobtrusively zen silver trophybronze trophy
    paul_wilkins's Avatar
    Join Date
    Jan 2007
    Location
    Christchurch, New Zealand
    Posts
    14,729
    Mentioned
    104 Post(s)
    Tagged
    4 Thread(s)
    Here's how I would think about solving this:

    1. Start with a selection pool of pieces that are in their correct location.
    2. Create a new empty array for the pieces that we're going to find.
    3. Start with the first piece from the pool
    4. Increase a "numberOfClusters" variable by one
    5. Add that piece to the found array and discover attached pieces
    6. For each attached piece, if it's not already in the found array, go back to step 5
    7. When all pieces have been processed from that first piece, move on to the next piece
    8. If that next piece isn't in the found array, go back to step 4


    So it seems like you're looking at recursion for your solution.
    Programming Group Advisor
    Reference: JavaScript, Quirksmode Validate: HTML Validation, JSLint
    Car is to Carpet as Java is to JavaScript

  9. #9
    Unobtrusively zen silver trophybronze trophy
    paul_wilkins's Avatar
    Join Date
    Jan 2007
    Location
    Christchurch, New Zealand
    Posts
    14,729
    Mentioned
    104 Post(s)
    Tagged
    4 Thread(s)
    I've put together a quick proof of concept. It does use some global variables, which I'm not too pleased about, but the general idea is there and can be refined from what we have.

    We'll start with a simple form so that we can enter in the pieces that are correct on the board.

    Code html4strict:
    <form id="selectPieces">
    <p>
    	<input type="checkbox" name="a"> A
    	<input type="checkbox" name="b"> B
    	<input type="checkbox" name="c"> C
    </p>
    <p>
    	<input type="checkbox" name="d"> D
    	<input type="checkbox" name="e"> E
    	<input type="checkbox" name="f"> F
    </p>
    <p>
    	<input type="checkbox" name="g"> G
    	<input type="checkbox" name="h"> H
    	<input type="checkbox" name="i"> I
    </p>
    <p>
    	<input type="checkbox" name="j"> J
    	<input type="checkbox" name="k"> K
    	<input type="checkbox" name="l"> L
    </p>
    <p><input type="submit" name="Find number of clusters"></p>
    </form>

    The script will be checking if values exist in an array, so we should use the Array.indexOf method to make things easier for us. Some web browsers (I'm looking at you, IE) still don't support this, so here's some compatability code from Array.indexOf to help things out.

    Code javascript:
    if (!Array.prototype.indexOf)
    {
      Array.prototype.indexOf = function(elt /*, from*/)
      {
        var len = this.length;
     
        var from = Number(arguments[1]) || 0;
        from = (from < 0)
             ? Math.ceil(from)
             : Math.floor(from);
        if (from < 0)
          from += len;
     
        for (; from < len; from++)
        {
          if (from in this &&
              this[from] === elt)
            return from;
        }
        return -1;
      };
    }

    When the form is submitted, we'll walk through each form element and if the checkbox is set, we'll add the name of that checkbox to the pieces array.

    Code javascript:
    var form = document.getElementById('selectPieces');
    form.onsubmit = processForm;
     
    function processForm(form) {
    	var pieces = [];
    	var i, el;
    	for (i = 0; i < form.elements.length; i += 1) {
    		el = form.elements[i];
    		if (el.type === 'checkbox' && el.checked === true) {
    			pieces.push(el.name);
    		}
    	}
    	findClusters(pieces);
    }

    When we search through the different pieces, we'll need some way of figuring out what are valid connections.

    Code javascript:
    // a b c
    // d e f
    // g h i
    // j k l
    window.connectors = {
    	'a': ['b', 'd'],
    	'b': ['a', 'c', 'e'],
    	'c': ['b', 'f'],
    	'd': ['a', 'e', 'g'],
    	'e': ['b', 'd', 'f', 'h'],
    	'f': ['c', 'e', 'i'],
    	'g': ['d', 'h', 'j'],
    	'h': ['e', 'g', 'i', 'k'],
    	'i': ['f', 'h', 'l'],
    	'j': ['g', 'k'],
    	'k': ['h', 'j', 'l'],
    	'l': ['i', 'k']
    };

    And now we're ready to find the clusters.

    For each piece that hasn't already been processed, we'll increase the cluster number and find all of the connections in that cluster.

    Code JavaScript:
    function findClusters(pieces) {
    	window.pieces = pieces;
    	window.foundPieces = [];
    	var clusters = 0;
        var piece, i;
        for (i = 0; i < window.pieces.length; i += 1) {
    		piece = window.pieces[i];
    		if (window.foundPieces.indexOf(piece) === -1) {
    			clusters += 1;
    			window.foundPieces.push(piece);
    			findConnections(piece);
    		};
    	}
    	alert ('Total clusters: ' + clusters);
    }

    Finding the connections is pretty easy too, we use the connectors array to to get all of the possible valid connections, and for each of the unprocessed connections, we add them to the found array before putting that piece in to be searched for more unprocessed connections.

    Code JavaScript:
    function findConnections(piece) {
    	var connections = window.connectors[piece];
    	var i;
    	for (i = 0; i < connections.length; i += 1) {
    	    piece = connections[i];
    		if (window.pieces.indexOf(piece) > -1) {
    			if (window.foundPieces.indexOf(piece) === -1) {
    				window.foundPieces.push(piece);
    				findConnections(piece);
    			}
    		}
    	}
    }

    Here is the full code for the test page.

    Code html4strict:
    <html>
    <head>
    	<title>Cluster test</title>
    </head>
    <body>
    <form id="selectPieces">
    <p>
    	<input type="checkbox" name="a"> A
    	<input type="checkbox" name="b"> B
    	<input type="checkbox" name="c"> C
    </p>
    <p>
    	<input type="checkbox" name="d"> D
    	<input type="checkbox" name="e"> E
    	<input type="checkbox" name="f"> F
    </p>
    <p>
    	<input type="checkbox" name="g"> G
    	<input type="checkbox" name="h"> H
    	<input type="checkbox" name="i"> I
    </p>
    <p>
    	<input type="checkbox" name="j"> J
    	<input type="checkbox" name="k"> K
    	<input type="checkbox" name="l"> L
    </p>
    <p><input type="submit" name="Find number of clusters"></p>
    </form>
    <script type="text/javascript">
    if (!Array.prototype.indexOf)
    {
      Array.prototype.indexOf = function(elt /*, from*/)
      {
        var len = this.length;
     
        var from = Number(arguments[1]) || 0;
        from = (from < 0)
             ? Math.ceil(from)
             : Math.floor(from);
        if (from < 0)
          from += len;
     
        for (; from < len; from++)
        {
          if (from in this &&
              this[from] === elt)
            return from;
        }
        return -1;
      };
    }
     
    var form = document.getElementById('selectPieces');
    form.onsubmit = processForm;
    function processForm() {
        var form = this;
    	var pieces = [];
    	var i, el;
    	for (i = 0; i < form.elements.length; i += 1) {
    		el = form.elements[i];
    		if (el.type === 'checkbox' && el.checked === true) {
    			pieces.push(el.name);
    		}
    	}
    	findClusters(pieces);
    }
     
    // a b c
    // d e f
    // g h i
    // j k l
    window.connectors = {
    	'a': ['b', 'd'],
    	'b': ['a', 'c', 'e'],
    	'c': ['b', 'f'],
    	'd': ['a', 'e', 'g'],
    	'e': ['b', 'd', 'f', 'h'],
    	'f': ['c', 'e', 'i'],
    	'g': ['d', 'h', 'j'],
    	'h': ['e', 'g', 'i', 'k'],
    	'i': ['f', 'h', 'l'],
    	'j': ['g', 'k'],
    	'k': ['h', 'j', 'l'],
    	'l': ['i', 'k']
    };
    function findClusters(pieces) {
    	window.pieces = pieces;
    	window.foundPieces = [];
    	var clusters = 0;
        var piece, i;
        for (i = 0; i < window.pieces.length; i += 1) {
    		piece = window.pieces[i];
    		if (window.foundPieces.indexOf(piece) === -1) {
    			clusters += 1;
    			window.foundPieces.push(piece);
    			findConnections(piece);
    		};
    	}
    	alert ('Total clusters: ' + clusters);
    }
    function findConnections(piece) {
    	var connections = window.connectors[piece];
    	var i;
    	for (i = 0; i < connections.length; i += 1) {
    	    piece = connections[i];
    		if (window.pieces.indexOf(piece) > -1) {
    			if (window.foundPieces.indexOf(piece) === -1) {
    				window.foundPieces.push(piece);
    				findConnections(piece);
    			}
    		}
    	}
    }
    </script>
    </body>
    </html>
    Programming Group Advisor
    Reference: JavaScript, Quirksmode Validate: HTML Validation, JSLint
    Car is to Carpet as Java is to JavaScript

  10. #10
    SitePoint Member
    Join Date
    Jan 2009
    Posts
    5
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    Quote Originally Posted by crmalibu View Post
    Can you elaborate?
    There is more than a single distinct peice which can be joined directly to the left(or right/top/bottom) of a given peice? eg in abc I would think the only thing that could be joined to the left of b would be a. Or is there no such restriction on which side another peice must reside on, it just needs to touch it, in order to be joined?

    A cluster can only fit together in a precise predefined order, in order for all the peices in the cluster to be joined?
    Hi Malibu,
    thanks for the input..
    for simplicity sake, I just explained it as a simple jigsaw puzzle... while in fact it is a bit more complex.. the pieces are all of varying sizes, and shapes, so some may have a scenario like the right side of a piece may have 4 pieces that fit to it, the top may have 2 pieces that fit, the left may have 0 pieces, and the bottom may have 1..

    I have a a page load function that determines all of these joins for each piece, and creates an object for each piece with all possible joins. So I have all of the definitions in place, all of the functions in place to determine which pieces are candidates for clusters, (which in my opinion seemed like it would be the hardest part of the project) and am stuck on what I thought would be the simplest part, which is running each piece through the definitions to find out which "clusters" belong together...

    On a side note ... taking both your and pmw's advise, I did come up with a working solution, although it is completely inefficient, and I am a little embarrassed to show it here, but it does work, and maybe someone would have some advise on how to make it a little better...

    a new example :
    a b c
    d e f
    g h i
    j k l

    pieces, a,b,c,d,j,k,l
    are all determined to be placed on the board correctly..
    now we need to determine the clusters...

    1) run a function testing each piece individually (which will return all simple joins based on the "join definitions")

    Code:
    //for each of the "good pieces on the board" (array clus)
    for(i=0;i<clus.length;i++){
    	clusters[clus[i]] = [];
    	thiscluster = new Array();
            //run through each piece again
    	for(b=0;b<clus.length;b++){
                    //is_linked checks if the piece is linked per the object definitions
    		if(is_linked(clus[i],clus[b])){
    			thiscluster.push( clus[b]);
    		}
    	}
    }
    a) this will give us a join array for each piece like this:

    Code:
    //cluster[piece on the board] = 'pieces in that cluster';
    thiscluster[a] = 'b','d'; 
    thiscluster[b] = 'a','c';
    thisthiscluster[c] = 'b';
    thisthiscluster[d] = 'a';
    thiscluster[j] = 'k';
    thiscluster[k] = 'j','l';
    thiscluster[l] = 'k';
    Next.. the only way I could come up to check to see if a should also belong to c, and d also belongs to c&b. etc.. is to just keep running this function over and over enough times to ensure that all levels are accounted for .. (in this simple example.. maybe only twice would cover all pieces on the board, but in mine, I need to run it through at least 10 times to make sure all joins are caught, otherwise, some are always missed.)

    Here is my (very inefficient) code:
    Code:
    //set up an array to store those pieces already checked so that we don't keep checking the same one over and over
    checked = new Array();
    for(c=0;c<10;c++){
    	for(s in thiscluster){
    		if(!in_array(thiscluster[s],checked)){
    			for(t in clus){
                                    //another check just to see if it's already in this clusters array so we can skip it
    				if(!in_array(clus[t],thiscluster)){
    					if(is_linked(thiscluster[s],clus[t])){
    						thiscluster[thiscluster.length]=clus[t];
    					}
    			         }
    			}
    		}
    		checked.push(thiscluster[s]);
    	}
    }
    This does the trick although it is not pretty...

    I am not an especially gifted javascript programmer, PHP is my cup of tea, so I use PHP mentality alot in my javascripts and it is sometimes detramental, so I may be overthinking the whole process, and may not know of a super slick javascript method, that makes something like this more achievable.

    Anyway, thanks for your help ,and if there are any comments on how to make this system more efficient, I would love to hear any thoughts.

    Thanks,Rheziel

  11. #11
    SitePoint Member
    Join Date
    Jan 2009
    Posts
    5
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    wow pmw ... we must have been posting at the same time ... as soon as I posted mine, I saw your excellent post... I'm going to run through it now, and see if I can understand it completely.

    Thank you for your help.


Bookmarks

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •