Forum Moderators: open
arr=new Array('A','A','B','A','A','B','B','A');
The array is displayed like this:
A A B A
A B B A
I would like a script that can tell if the starting point(2 in the array) is connected (not diagonally) to the end point(5 in the array). The order and start and end point can change, unfortunately. This is for a game, much like PopCap's atomica. Can someone please help me?
I think we need some more info¦clarification:
I would like a script that can tell if the starting point(2 in the array) is connected (not diagonally) to the end point(5 in the array).
1. The 'starting point' is 2 in the array?¨
2. 'connected' - what does that mean exactly? Does in mean 'in the same column', or 'directly below'?
3. 'end point' is 5?
A A 2 A
A 5 6 A
The starting point is 2. This is because of this:
"A","A","2","A".
0 1 2 3
Sorry for not making myself clear. By connected, I mean connected vertically and/or horizontally to the end point, by a string of the same letters. For example. The starting and ending points in this setup are bold:
ZZZZZZZZZZZZZZ
ZZZZAZZZZZZZZZ
ZZZZAAAAAZZZZZ
ZZZZZZZZAZZZZZ
ZZZZAAAAAZZZZZ
ZZZZZZZZZZZZZZ
All the A's are connected through a chain of A's. Again, I apologize for not making myself clear.
Meanwhile, is this a possible arrangement_?:
ZZZZZ[b]AAAA[/b]ZZZZZ
ZZZZ[b]AA[/b]ZZ[b]A[/b]ZZZZZ
ZZZZZZZZ[b]A[/b]ZZZZZ
ZZZZZZZZ[b]A[/b]ZZZZZ
ZZZZ[b]AAAAA[/b]ZZZZZ
ZZZZZZZZZZZZZZ
1. It uses certain global variables. It would be better to work these into local variables of the main array method, or properties of objects. Then, for eg, path searches could be made on different 'grid views' of the same linear array.
2. It doesn't actually return the path - only whether or not it exists.
3. The approach may be overkill.
[pre]
Array.prototype.isConnected = function(iStart, iEnd, nCols)
{
var arr = this;
var nRows = Math.ceil(this.length/nCols);
var node;
var found = false; walk(new Node(iStart));
return found;
function walk(node)
{
if(node.i==iEnd)
found = true;
var neighbs, neighb, k=-1;
var neighbs = node.getNeighbours();
if(neighbs)
{
while(neighb=neighbs[++k])
walk(neighb)
}
}
}
[blue]
/*------------------------------------------------------------------------------
Node type
------------------------------------------------------------------------------*/
[/blue]
function Node(i)
{
if(!ARR[i]) return null;
this.i = i;
// debug only:// this.val = ARR[i];
NODES[i] = this;
}
Node.prototype =
{
getNeighbours :
function()
{
var nCols = NO_COLUMNS,
neighbs = [],
i = this.i;
if(i >= nCols)// .............up (not 1st row)
test(i-nCols,'up');
if((i+1)%nCols)// ............right (not last col)
test(i+1,'right');
if(i < ARR.length - nCols )// down (not last row)
test(i + nCols,'down');
if(i%nCols) //................ left (not 1st col)
test(i-1,'left');
if(!neighbs.length)
return null;
return this.neighbs = neighbs;
//debug only:// var val = this.val;
//----local------------------------
function test(i,drn)
{
if( ARR[i]==CHAR &&!NODES[i]){
//debug://alert(val+'--> '+ARR[i]+': '+drn)
neighbs.push(new Node(i));
}
}
}
}
[blue]
/*------------------------------------------------------------------------------
START
------------------------------------------------------------------------------*/
[/blue]
var CHAR = 'A'; // accepted 'linking character'
var NO_COLUMNS = 14 ;
var NODES = {} ;
[blue]
/*------------------------------------------------------------------------------
Each character in the array is considered a 'node'. A node object is
created for each one encountered. Each object is placed into the global
NODES array by it's array index.
NODES is a 'sparse' array. Its purpose is to prevent nodes being
investigated more than once, and so prevent endless loops.
------------------------------------------------------------------------------*/
[/blue]
var ARR = (''+
'##############'+
'##AAAA###AAAA#'+
'#####A###A##A#'+
'##AAAAAAAAAAAA'+
'AAA##########A'+
'#######AAAAAAA'+
'####AAAA######'+
'##############').split('');
alert(ARR.isConnected(16,88,NO_COLUMNS))[/pre]
why don't u make this puzzle a multilevel array[?]
What do you mean 'a multilevel array'?
The problems are:
1. the path itself isn't returned.
2. The algorithm uses a recursive function. I guess this means that the function stack is built up to the extent of each searched path before it collapses. I have no idea how big the stack can be. This probably isn't a problem if the 'maze' isn't too large.
Re multi-dim arrays: Adni was using a string, so I stuck with it, just splitting it into a single array, rather than a 2D. In the end the algorithm is the same. The same basic idea could be used on just the original string itself.
If it's a classic problem, then I guess the classic solution would be to create a single iterator object that searches the maze, keeping track of the path home. Guaranteeing the shortest path may well be a bigger problem.
