array question

[wolph42]

Given the following array:

Code: Select all

[[0,6],[1,4],[1,2],[3],[0,4],[0,5],[0,6],[7],[7,8]] 
note: I don't think the arrays can be empty, they can however contain more than 2 numbers

Of this array of arrays I want to construct a new array that groups the numbers that are in the same array. In this case the result would be:
[[3],[7,8],[0,1,2,4,5,6]]

take the last group as an example: [0,6] contains 0 and 6.
- (One of) these two number are also found in [0,4] and [0,5] creating [0,4,5,6]
- again these numbers from the last set are found in [1,4]
- this makes [0,1,4,5,6]
- check again to find [1,2]
- making the final total group: [0,1,2,4,5,6]
rinse and repeat for the remainders which result in: [3] and [7,8]

What I need is a routine that does the above automatically.

Any suggestions?

Please note: I don't need fully developed code, just a description of the algorithm is enough.

why

This is part of the random dungeon generator. The numbers correspond with the number of the room and their corridors. E.g. in room 1 (R1) starts corridor 1 (C1). C1 takes of in a random direction until it hits another room in this case R4. From room 4 C4 starts which in this case happened to end up in room 0, etc.

this can end up with all sections connected OR with a couple of dungeon section which are NOT connected. In this example you end up with 3 sections. I need to figure out which is which so I can connect these sections with additional corridors to make the dungeon complete.

You might have noticed that R3 has no corridor, that means that the corridor could not find another room and the process was aborted

total utter failure so far

Code: Select all

<pre>
[array        = "[[7],[0,4],[3],[1,2],[0,6],[7,8],[0,5],[1,4]]"]
[origArray    = array]
[newArray    = "[]"]

[while(!json.isEmpty(origArray)), CODE:{
    [foreach(item,origArray), CODE:{
        <!-- remove item from array so you dont compare with itself -->
        [match        = 0]
        [tmpArray    = json.difference(origArray, json.append("[]", item))]
        [foreach(item1, tmpArray),CODE:{
            [intersect    = !json.isEmpty(json.intersection(item,item1))]
            [if(intersect), CODE:{
                [match        = 1]
                [subArray    = json.union(item, item1)]
                [newArray    = json.append(newArray, subArray)]
                [origArray    = json.difference(origArray, json.append("[]",item, item1))]
                [pause("array", "origArray","newArray","subArray", "item", "item1")]
            ''    
            }]
        ''    
        }]
        [if(!match), CODE:{
            <!-- if an item finds no match at all, add and remove it separately -->
            [newArray    = json.append(newArray, item)]
            [origArray    = json.difference(origArray, json.append("[]",item))]
        ''
        }]
    ''    
    }]
    [pause("array", "origArray","newArray")]
    [origArray    = newArray]
    [newArray    = "[]"]
''    
}]
 

be careful not to end up in an infinite loop (which will exit after the new loop limiter of 10k loops)

[wolph42]

updated OP and still shy of a solution...

[aliasmask]

Here is one idea:

Code: Select all

start: [[7],[0,4],[3],[1,2],[0,6],[7,8],[0,5],[1,4]]
pass 1: [[0,4],[3],[1,2],[0,6],[0,5],[1,4],[7,8]]
final: []
pass 2: [[3],[1,2],[0,6],[0,5],[1,4],[7,8],[0,4,6]]
final: []
pass 3: [[1,2],[0,6],[0,5],[1,4],[7,8],[0,4,6]]
final: [[3]]
pass 4: [[0,6],[0,5],[7,8],[0,4,6],[1,2,4]]
final: [[3]]
pass 5: [[7,8],[0,4,6],[1,2,4],[0,5,6]]
final: [[3]]
pass 6: [[0,4,6],[1,2,4],[0,5,6]]
final: [[3],[7,8]]
pass 6: [[0,5,6],[0,1,2,4,6]]
final: [[3],[7,8]]
pass 7: [[0,1,2,4,5,6]]
final: [[3],[7,8]]
pass 8: []
final: [[3],[7,8],[0,1,2,4,5,6]]

Compare the first array with the other arrays. When a match is found union the two arrays and remove the two matching arrays. Then append the union array to the end. If no match is found then add to final array. Use json.intersection to compare the two arrays and json.union to merge the two (with a json.sort for good measure).

edit: Taking a closer look at your code seems like this is what you were trying to do. I'll see what I come up with.

Code: Select all

@@ @unionArrays
<!-- unionArrays(array): unionArray
   array - a 2 dimensional array of numbers
   unionArray - merged arrays with common values
-->

[H: startArray = "[[7],[0,4],[3],[1,2],[0,6],[7,8],[0,5],[1,4]]"]
[H: finalArray = "[]"]

[H, while(! json.isEmpty(startArray)), code: {
   [H: firstArray = json.get(startArray,0)]
   [H: startArray = json.remove(startArray,0)]
   [H: continue = 1]
   [H: limit = json.length(startArray) -1]
   [H, while(continue && limit >= 0), code: {
      [H: index = roll.count]
      [H: secondArray = json.get(startArray,index)]
      [H: hasMatch = if(! json.isEmpty(json.intersection(firstArray,secondArray)),1,0)]
      [H, if(hasMatch): tempArray = json.sort(json.union(firstArray,secondArray),"a")]
      [H, if(hasMatch): startArray = json.append(json.remove(startArray,index),tempArray)]
      [H, if(hasMatch || index >= limit): continue = 0]
      [H, if(! hasMatch && index >= limit): finalArray = json.append(finalArray,firstArray)]
   }]
}]
[H: finalArray = json.append(finalArray,firstArray)]

[R: finalArray]

!!
 

[wolph42]

Many many thanks. As you can see from the 'total utter failure' in the OP, I was close, but I simply got lost in the final step ("take first and add union as last"). It now works.

For reference, here the working code:

Code: Select all

[h:array        = "[[7],[0,4],[3],[1,2],[0,6],[7,8],[0,5],[1,4]]"]
[h:origArray    = array]
[h:finalArray    = "[]"]

[h,while(!json.isEmpty(origArray)), CODE:{
    [item        = json.get(origArray, 0)]
    <!-- remove item from array so you dont compare with itself -->
    [tmpArray    = json.difference(origArray, json.append("[]", item))]
    [match        = 0]
    [foreach(item1,tmpArray), CODE:{
        [intersect    = !json.isEmpty(json.intersection(item,item1))]
        [if(intersect), CODE:{
            [match        = 1]
            [subArray    = json.union(item, item1)]
            <!-- remove union items from original array -->
            [origArray    = json.difference(origArray, json.append("[]",item, item1))]
            <!-- add new union at the end of the orig array -->
            [origArray    = json.append(origArray, subArray)]
        ''    
        }]
    ''    
    }]
        
    [if(!match), CODE:{
        <!-- if an item finds no match at all, add and remove it separately -->
        [finalArray    = json.append(finalArray, json.sort(item))]
        [origArray    = json.difference(origArray, json.append("[]",item))]
    ''
    }]
''    
}]

[r:array]<br>
[r:finalArray]
 

[Craig]

Edit: looks like I spent too much time writing this up and was beaten

So I wont write this in MT Macro script because well my MT macro script is REALLY rusty... But I will describe the algorithm by showing how it would work through your example.

Assume there is an array called results which holds (not too surprisingly) the results, so in your above example results would end up like
results[0] = [3]
results[1] = [7,8]
results[2] = [0,1,2,4,5,6]

With an inputA = [[0,6],[1,4],[1,2],[3],[0,4],[0,5],[0,6],[7],[7,8]]


This all goes in a loop which starts here...

First step
is to make results[0] equal to something, the first array in the input is a good choice, and remove it from inputA
results[0] = [0,6]
inputA = [[1,4],[1,2],[3],[0,4],[0,5],[0,6],[7],[7,8]]

Next Step, second input,
compare this to all your results, any number matches then add it to that result otherwise create a new one.
Compare [1,4] to results[], neither 1, or 4 matches 0, 6 so create a new results[]
So after second input you have (I know this doesn't look like its getting you where you want but bear with me)
results[0] = [0,6]
results[1] = [1,4]
inputA = [[1,2],[3],[0,4],[0,5],[0,6],[7],[7,8]]

Third input
Compare [1,2] to results[], 1 matches the 1 from [1,4] in results[1] so add it to results[1] (you can sort and make unique if you want it doesn't matter if here or later)
results[0] = [0,6]
results[1] = [1,4,1,2]
inputA = [[3],[0,4],[0,5],[0,6],[7],[7,8]]

Fourth input
Compare [3] to results[], it doesn't match anything so create a new results[]
results[0] = [0,6]
results[1] = [1,4,1,2]
results[2] = [3]
inputA = [[0,4],[0,5],[0,6],[7],[7,8]]

Fifth input
Compare [0,4] to results[], the 0 matches the 0 in [0,6] so it goes into results[0]
results[0] = [0,6,0,4]
results[1] = [1,4,1,2]
results[2] = [3]
inputA = [[0,5],[0,6],[7],[7,8]]


Sixth input
Compare [0,5] to results[], the 0 matches the 0 in [0,6,0,4] so it goes into results[0]
results[0] = [0,6,0,4,0,5]
results[1] = [1,4,1,2]
results[2] = [3]
inputA = [[0,6],[7],[7,8]]


Seventh input
Compare [0,6] to results[], the 0 (or the 6) matches the 0 in [0,6,0,4,0,5] so it goes into results[0]
results[0] = [0,6,0,4,0,5,0,6]
results[1] = [1,4,1,2]
results[2] = [3]
inputA = [[7],[7,8]]


Eighth input
Compare [7] to results[], it doesnt match any so create a new results[]
results[0] = [0,6,0,4,0,5,0,6]
results[1] = [1,4,1,2]
results[2] = [3]
results[3] = [7]
inputA = [[7,8]]

Ninth input
Compare [7,8] to results[], it matches the 7 in results[3] so add it to results[3].
results[0] = [0,6,0,4,0,5,0,6]
results[1] = [1,4,1,2]
results[2] = [3]
results[3] = [7,7,8]
inputA = []

Now you have reached the end of your input array and you have simplified it, but it is still not what you want (it can be simplified further).
So you check, did I have any matches above (i.e is the number of results[] less than the number of arrays in input),
If so put results into inputA and do it again
inputA= [[0,6,0,4,0,5,0,6], [1,4,1,2], [3], [7,7,8]]
results = []


First Input
Make results[0] = first array thing in input
results[0] = [0,6,0,4,0,5,0,6]
inputA=[[1,4,1,2], [3], [7,7,8]]


Second Input
The 4 in [1,4,1,2] matches the 4 in [0,6,0,4,0,5,0,6] so it gets put into results[0]
results[0] = [0,6,0,4,0,5,0,6,1,4,1,2]
inputA=[[3], [7,7,8]]

Third Input
The [3] doesn't match anything so create a new results[]
results[0] = [0,6,0,4,0,5,0,6,1,4,1,2]
results[1] = [3]
inputA=[[7,7,8]]


Third Input
The [7,7,8] doesn't match anything so create a new results[]
results[0] = [0,6,0,4,0,5,0,6,1,4,1,2]
results[1] = [3]
results[1] = [7,7,8]
inputA=[]

Now you have matched again so you will have to go through the loop one more time, but in that pass you will not match anything so you will start with 3 inputs and end with 3 outputs so you know you are done. As I said earlier you can sort/dedupe the arrays at any stage, during merge, after end of loop before putting it back into inputA or at the end of it all it doesn't really matter (from a results perspective), using the json functions to dedupe the arrays as soon as possible will lead to less loops in your inner loop (where you compare each value in the input to each value in results[x])....

There are other ways of doing it, some of which will be faster but given how complicated they would be to implement I think the above is your best bet.

[wolph42]

@Craig
although its 'mustard after the meal' (as we say in Holland), its still appreciated.

What I find funny is that I was working on two separate solutions (getting stuck on both) where the first idea matches with AM (but I couldn't figure out what I was doing wrong) and the second idea matches your idea (and again couldn't figure out where I went wrong).

I think that where I fundamentally went wrong on both occasions is that I immediately started coding, while I should have done what you two did: write it out.

Thanks!

[wolph42]

edit: Taking a closer look at your code seems like this is what you were trying to do. I'll see what I come up with.

as you can see, I came to roughly the same result, however I noticed some things in your code a bit smarter and some less, so I can update mine a bit for efficiency, thank you!

EDIT: combining both (and adding some sprinkles) you get this:

Code: Select all

[h:'<!-- ------------------------- unionArrays(array): unionArray ------------------------------- -->']
<!--    array        - a 2 dimensional array of numbers: [[7],[0,4],[3],[1,2],[0,6],[7,8],[0,5],[1,4]]
      unionArray    - merged arrays with common values: [[3],[7,8],[0,1,2,4,5,6]]
-->

[h:startArray    = arg(0)]
[h:finalArray    = "[]"]

[h,while(!json.isEmpty(startArray)), CODE:{
    <!-- start with first item and remove said item from array so you dont compare with itself -->
    [item        = json.get(startArray, 0)]
    [startArray    = json.difference(startArray, json.append("[]",item))]
    [tmpArray    = startArray]
    [match        = 0]
    
    [foreach(item1,tmpArray), CODE:{
        [intersect    = !json.isEmpty(json.intersection(item,item1))]
        [match        = max(match,intersect)]
        <!-- remove union items from original array and add new union at the end of the orig array -->
        [if(intersect): startArray    = json.append(json.difference(startArray, json.append("[]",item, item1)), json.union(item, item1))]
    }]
    <!-- if an item finds no match at all, add and remove it separately -->
    [if(!match): finalArray    = json.append(finalArray, json.sort(item))]
}]

[h:macro.return    = finalArray]