Checking neighbour elements in flat array
ok. Here we go. Because i found this question interesting to be implemented in bash i just wrote an implementation of conway's game of life.
The main part to answer your question is probably: how to access neighbours for a position in a matrix if it is linearized?.
So you can access an element in a flatted matrix by
(row*fieldwidth)+columnoffset.
Every neighbour then can be accessed by adjusting row and columnoffset by +/-1 starting with row and columnoffset at 0.
Have a look at the getnextstate function to view the specialcases.
So here is the implementation.
You are able to provide a file as input containing just CELLALIVEMARKER,CELLDEADMARKER and spaces. If the length for the flatted matrix does not fit the width/height parameter for the FIELD it just pads with random values.
#!/bin/bash
# system values
BASENAME="/usr/bin/basename"
ECHO="/bin/echo"
SLEEP="/bin/sleep"
TPUT="/usr/bin/tput"
GREP="/bin/grep"
WC="/usr/bin/wc"
CAT="/bin/cat"
if [ "${#}" != "4" -a "${#}" != "5" ]; then
${ECHO} "USAGE: ./$(${BASENAME} ${0}) FIELDWIDTH FIELDHEIGHT RULESALIVE RULESDEAD [LINSTARTMATRIX]"
${ECHO} "EXAMPLES: ./$(${BASENAME} ${0}) 50 50 \"2 3\" \"3\""
${ECHO} " ./$(${BASENAME} ${0}) 50 50 \"2 3\" \"3\"" init.mtx
exit
fi
# field values
FWIDTH=${1}
FHEIGHT=${2}
# number of living neighbours for a living cell to stay alive in the next generation
RULESALIVE=($(${ECHO} ${3}))
# number of living neighbours for a dead cell to become alive in the next generation
RULESDEAD=($(${ECHO} ${4}))
CELLALIVEMARKER="o"
CELLDEADMARKER="."
FIELD=() # flatted matrix representation
# if there are just marker values or spaces in the file it is a valid one
${CAT} ${5} | ${GREP} -oq '[^\'${CELLALIVEMARKER}'\'${CELLDEADMARKER}'\ ]'
isvalid="${?}"
if [ "${5}" != "" ] && [ "${isvalid}" == "1" ]; then
FIELD=($(${CAT} ${5}))
# fill up with randoms if the length won't fit the dimension parameters
if [ "${#FIELD[@]}" != "$((${FWIDTH}*${FHEIGHT}))" ]; then
${ECHO} "I: Padding matrix with random values."
# fill up field with randoms if its too short
for((i=${#FIELD[@]}; i<${FWIDTH}*${FHEIGHT}; i=$((${i}+1)))); do
cell="${CELLALIVEMARKER}"
alive=$((${RANDOM}%2))
if [ "x${alive}" == "x1" ]; then
cell="${CELLDEADMARKER}"
fi
FIELD[${#FIELD[@]}]="${cell}"
done
fi
else
# fill random field
for((i=0; i<${FWIDTH}*${FHEIGHT}; i=$((${i}+1)))); do
cell="${CELLALIVEMARKER}"
alive=$((${RANDOM}%2))
if [ "x${alive}" == "x1" ]; then
cell="${CELLDEADMARKER}"
fi
FIELD[${#FIELD[@]}]="${cell}"
done
fi
# evaluate rules and get the next state for the cell
getnextstate() {
local i="${1}" # row
local j="${2}" # col
local neighbours=""
# left upper
if [ "${i}" -eq "0" -a "${j}" -eq "0" ]; then
neighbours="${FIELD[$(((${i}*${FWIDTH})+(${j}+1)))]} ${FIELD[$((((${i}+1)*${FWIDTH})+${j}))]} ${FIELD[$((((${i}+1)*${FWIDTH})+(${j}+1)))]}"
# right upper
elif [ "${i}" -eq "0" -a "${j}" -eq "$((${FWIDTH}-1))" ]; then
neighbours="${FIELD[$(((${i}*${FWIDTH})+(${j}-1)))]} ${FIELD[$((((${i}+1)*${FWIDTH})+(${j}-1)))]} ${FIELD[$((((${i}+1)*${FWIDTH})+${j}))]}"
# left bottom
elif [ "${i}" -eq "$((${FHEIGHT}-1))" -a "${j}" -eq "0" ]; then
neighbours="~${FIELD[$((((${i}-1)*${FWIDTH})+${j}))]} ${FIELD[$((((${i}-1)*${FWIDTH})+(${j}+1)))]} ${FIELD[$(((${i}*${FWIDTH})+(${j}+1)))]}"
# right bottom
elif [ "${i}" -eq "$((${FHEIGHT}-1))" -a "${j}" -eq "$((${FWIDTH}-1))" ]; then
neighbours="?${FIELD[$((((${i}-1)*${FWIDTH})+(${j}-1)))]} ${FIELD[$((((${i}-1)*${FWIDTH})+${j}))]} ${FIELD[$(((${i}*${FWIDTH})+(${j}-1)))]}"
# upper
elif [ "${i}" -eq "0" -a "${j}" -gt "0" ]; then
neighbours="-${FIELD[$(((${i}*${FWIDTH})+(${j}-1)))]} ${FIELD[$(((${i}*${FWIDTH})+(${j}+1)))]} ${FIELD[$((((${i}+1)*${FWIDTH})+(${j}-1)))]} ${FIELD[$((((${i}+1)*${FWIDTH})+${j}))]} ${FIELD[$((((${i}+1)*${FWIDTH})+(${j}+1)))]}"
# bottom
elif [ "${i}" -eq "$((${FHEIGHT}-1))" -a "${j}" -gt "0" ]; then
neighbours="=${FIELD[$((((${i}-1)*${FWIDTH})+(${j}-1)))]} ${FIELD[$((((${i}-1)*${FWIDTH})+${j}))]} ${FIELD[$((((${i}-1)*${FWIDTH})+(${j}+1)))]} ${FIELD[$(((${i}*${FWIDTH})+(${j}-1)))]} ${FIELD[$(((${i}*${FWIDTH})+(${j}+1)))]}"
# right
elif [ "${i}" -gt "0" -a "${j}" -eq "0" ]; then
neighbours="#${FIELD[$((((${i}-1)*${FWIDTH})+${j}))]} ${FIELD[$((((${i}-1)*${FWIDTH})+(${j}+1)))]} ${FIELD[$(((${i}*${FWIDTH})+(${j}+1)))]} ${FIELD[$((((${i}+1)*${FWIDTH})+${j}))]} ${FIELD[$((((${i}+1)*${FWIDTH})+(${j}+1)))]}"
# left
elif [ "${i}" -gt "0" -a "${j}" -eq "$((${FWIDTH}-1))" ]; then
neighbours="_${FIELD[$((((${i}-1)*${FWIDTH})+(${j}-1)))]} ${FIELD[$((((${i}-1)*${FWIDTH})+${j}))]} ${FIELD[$(((${i}*${FWIDTH})+(${j}-1)))]} ${FIELD[$((((${i}+1)*${FWIDTH})+(${j}-1)))]} ${FIELD[$((((${i}+1)*${FWIDTH})+${j}))]}"
# center
else
neighbours="@${FIELD[$((((${i}-1)*${FWIDTH})+(${j}-1)))]} ${FIELD[$((((${i}-1)*${FWIDTH})+${j}))]} ${FIELD[$((((${i}-1)*${FWIDTH})+(${j}+1)))]} ${FIELD[$(((${i}*${FWIDTH})+(${j}-1)))]} ${FIELD[$(((${i}*${FWIDTH})+(${j}+1)))]} ${FIELD[$((((${i}+1)*${FWIDTH})+(${j}-1)))]} ${FIELD[$((((${i}+1)*${FWIDTH})+${j}))]} ${FIELD[$((((${i}+1)*${FWIDTH})+(${j}+1)))]}"
fi
# count neighbours alive
ncnt=$(${ECHO} ${neighbours} | ${GREP} -o ${CELLALIVEMARKER} | ${WC} -l)
# evaluate rules
local next=""
if [ "${FIELD[$(((${i}*${FWIDTH})+${j}))]}" == "${CELLALIVEMARKER}" ] && [[ "$(${ECHO} ${RULESALIVE[@]})" =~ ${ncnt} ]]; then
next="${CELLALIVEMARKER}"
elif [ "${FIELD[$(((${i}*${FWIDTH})+${j}))]}" == "${CELLDEADMARKER}" ] && [[ "$(${ECHO} ${RULESDEAD[@]})" =~ ${ncnt} ]]; then
next="${CELLALIVEMARKER}"
else
next="${CELLDEADMARKER}"
fi
${ECHO} ${next}
}
firstrun=1
while [ true ]; do
# print lines
FIELD_UPDATE=()
for((i=0; i<${FHEIGHT}; i=$((${i}+1)))); do
line=""
# calculate lines
for((j=0; j<${FWIDTH}; j=$((${j}+1)))); do
if [ "${firstrun}" == "1" ]; then
line="${line}${FIELD[$(((${i}*${FWIDTH})+${j}))]} "
# start calculation just after the first print
elif [ "${firstrun}" == "0" ]; then
line="${line}$(getnextstate ${i} ${j}) "
fi
done
FIELD_UPDATE=($(${ECHO} ${FIELD_UPDATE[@]}) $(${ECHO} ${line}))
${ECHO} ${line}
done
FIELD=(${FIELD_UPDATE[@]})
${SLEEP} 2
# refresh lines in the field
for((i=0; i<${FHEIGHT}; i=$((${i}+1)))); do
# refresh lines
${TPUT} cuu1
${TPUT} el
done
firstrun=0
done
So providing the file init.mtx containing the following matrix
. o . . . . . . . .
. . o . . . . . . .
o o o . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
you are able to create a simple glider (from the upper left to the bottom right)
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . o o
. . . . . . . . o o
using Conway's default rules by running this script as follows:
./gameoflife 10 10 "2 3" "3" init.mtx
Hope this helps.
And btw it was fun to implement this in bash :)
Finding neighbours in a two-dimensional array
(pseudo-code)
row_limit = count(array);
if(row_limit > 0){
column_limit = count(array[0]);
for(x = max(0, i-1); x <= min(i+1, row_limit); x++){
for(y = max(0, j-1); y <= min(j+1, column_limit); y++){
if(x != i || y != j){
print array[x][y];
}
}
}
}
Of course, that takes almost as many lines as the original hard-coded solution, but with this one you can extend the "neighborhood" as much as you can (2-3 or more cells away)
Python Numpy Array geht values of neighbours
You can take advantage of python indexing wrapping around for negative indices.
def wrap_nb(x,i,j):
return x[np.ix_(*((z-1, z, z+1-S) for z,S in zip((i,j), x.shape)))].ravel()
This requires i and j to be nonnegative and less than the shape of x.
If that is not guaranteed:
def wrap_nb(x,i,j):
return x[np.ix_(*(np.r_[z-1:z+2]%S for z,S in zip((i,j), x.shape)))].ravel()
Examples:
>>> wrap_nb(x,1,-2)
array([ 2, 3, 4, 6, 7, 8, 10, 11, 12])
>>> wrap_nb(x,0,-1)
array([15, 16, 13, 3, 4, 1, 7, 8, 5])
>>> wrap_nb(x,0,0)
array([16, 13, 14, 4, 1, 2, 8, 5, 6])
How to determine neighboring elements from a 1D array?
determine the logic to do this
- A 1-d array with 6 items has the indices -
[0,1,2,3,4,5] - A proposed shape is 2 rows and 3 columns -
M,N = 2,3. - for any item's index (
i) its row and column arec,r = divmod(i,M) - The neighbor column,row indices will be
cplus,cminus = c + 1, c - 1
rplus, rminus = r + 1, r - 1
cplus,r
cminus,r
c,rplus
c,rminus
cplus,rplus
cplus,rminus
cminus,rplus
cminus,rminus
- those 2d indices need to be converted to 1d indices with
(col * M) + row
For example
[0,1,2,3,4,5]
M,N = 2,3
'''
0 2 4
1 3 5
'''
item 4's 2d index is
c,r = divmod(4,M)-->(2,0)(col,row)one of its neighbor's 2d index is
c,rplus-->(2,1)that neighbor's 1d index is
(2 * M) + 1-->5after converting the neighbors' 2d indices to 1d you will need to check for and discard some that don't make sense.
- item 4 is in the top-right a corner and doesn't have some neighbors like
c,rminuswhich would be(2,-1)which does not make sense. Orcplus,r...(3,0)which also does not make sense.
- item 4 is in the top-right a corner and doesn't have some neighbors like
Caveat - I did NOT try to thoroughly test this.
Here is a function that returns a callable.
import operator
def get_neighbors(index, shape=(M,N)):
'''Returns a callable.
(M,N) --> (number_of_rows, number_of_columns)
'''
M, N = shape
# 2d index
c, r = divmod(index, M)
print(f'2d index: {(c,r)}')
# neighbors
cplus, cminus = c + 1, c - 1
rplus, rminus = r + 1, r - 1
# dot product of (c,cplus,cminus) and (r,rplus,rminus)?
neighbors = [
(cminus, rminus),
(cminus, r),
(cminus, rplus),
(c, rplus),
(cplus, rplus),
(cplus, r),
(cplus, rminus),
(c, rminus),
]
# print(neighbors)
# validate/filter
neighbors = [
(col, row) for col, row in neighbors if (0 <= col < N) and (0 <= row < M)
]
# print(neighbors)
# 1d indices
one_d = [(col * M) + row for col,row in neighbors]
# print(one_d)
return operator.itemgetter(*one_d)
Try it out.
>>> a = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't']
>>> M,N = 4,5 # nrows, ncols
'''
[['a' 'e' 'i' 'm' 'q']
['b' 'f' 'j' 'n' 'r']
['c' 'g' 'k' 'o' 's']
['d' 'h' 'l' 'p' 't']]
'''
>>> # i's neighbors
>>> q = get_neighbors(a.index('i'),(M,N))
2d index: (2, 0)
>>> q(a)
('e', 'f', 'j', 'n', 'm')
>>>
>>> # k's neighbors
>>> q = get_neighbors(a.index('k'),(M,N))
2d index: (2, 2)
>>> q(a)
('f', 'g', 'h', 'l', 'p', 'o', 'n', 'j')
>>>
>>> # q's neighbors
>>> q = get_neighbors(a.index('q'),(M,N))
2d index: (4, 0)
>>> q(a)
('m', 'n', 'r')
>>>
i's neighbors for different shapes
>>> M,N = 5,4
>>> q = get_neighbors(a.index('i'),(M,N))
2d index: (1, 3)
>>> q(a)
('c', 'd', 'e', 'j', 'o', 'n', 'm', 'h')
>>> M,N = 10,2
>>> q = get_neighbors(a.index('i'),(M,N))
2d index: (0, 8)
>>> q(a)
('j', 't', 's', 'r', 'h')
>>> M,N = 2,10
>>> q = get_neighbors(a.index('i'),(M,N))
2d index: (4, 0)
>>> q(a)
('g', 'h', 'j', 'l', 'k')
>>>
There is a nice discussion in the Numpy docs about making/treating a 1d thing as a Nd thing - Internal memory layout of an ndarray
The way you depicted your 1d --> 2d transformation used a column major scheme. I'm used to thinking row-major - I wrote the function to accept/expect a (nrows,ncols) shape argument but inside the function I kinda switched to column major processing. I was having to be careful so maybe that was a bad design.
Check neighbor values in a matrix, Matlab
In my opinion, using two nested loops in this case is a good approach. Retrieving the surrounding values of a matrix element is always tricky, but it can be accomplished with some efforts. Here is the solution I propose you:
A = [
0 1 0 1 1 0;
1 0 1 0 0 1;
1 1 0 1 1 1;
0 0 1 0 0 0;
0 1 0 0 0 1;
1 1 1 0 0 1
];
A_rows = size(A,1);
A_cols = size(A,2);
for i = 1:A_rows
for j = 1:A_cols
% Retrieve the current center...
value = A(i,j);
% Retrieve the neighboring column and row offsets...
c = bsxfun(@plus,j,[-1 0 1 -1 1 -1 0 1]);
r = bsxfun(@plus,i,[-1 -1 -1 0 0 1 1 1]);
% Filter the invalid positions...
idx = (c > 0) & (c <= A_cols) & (r > 0) & (r <= A_rows);
% Transform the valid positions into linear indices...
idx = (((idx .* c) - 1) .* A_rows) + (idx .* r);
idx = reshape(idx.',1,numel(idx));
% Filter the invalid linear indices...
idx = idx(idx > 0);
% Find the center neighbors and their sum...
neighbors = A(idx);
neighbors_sum = sum(neighbors);
% Apply the transformation criterions to A...
if (value == 0)
if (neighbors_sum == 3)
A(i,j) = 1;
end
else
if (neighbors_sum <= 1) || (neighbors_sum >= 3)
A(i,j) = 0;
end
end
end
end
The final output for the given example is:
A =
0 1 1 0 0 0
0 0 0 1 0 1
0 0 1 0 0 0
0 1 0 0 0 0
0 0 1 0 0 0
0 1 1 0 0 0
I just have a few doubts about the whole process you described.
The first one concerns the criterions to apply when the center value is equal to 1. Two of them seem to be contradictory:
-If the neighbor cells of the center value contains in total 3 or more 1's, it converts from 1 to 0.
-And if the neighbor cells contain in total 2 or 3 number 1's, it keeps being 1.
When the neighbors sum is equal to 3... which condition should be applied? The first one or the second one?
The second one concerns the original matrix A. Should it be updated inside the loop? I mean, in the current code, the values of A change when certain conditions are met... but this also means that the conditions are influenced by the outcome of the previous iterations. Maybe your goal is to keep A static while updating a clone of it instead?
Anyway, both issues are easy to deal with and you should be able to adapt my code to your needs without any problem.
How do I check the neighbors of the cells around me in a 2D array (C++)?
You can use nested loops
int sum{0};
for (int x{std::max(xPosition, 1) - 1}; x < std::min(xPosition + 2, columns); ++x) {
for (int y{std::max(yPosition, 1) - 1}; y < std::min(xPosition + 2, rows); ++y) {
if (x == xPosition && y == yPosition) continue;
sum += array[x][y];
}
}
Related Topics
How to Add a Linker or Compile Flag in a Cmake File
How to Generate a Random Number in C++
How to Call ::Std::Make_Shared on a Class With Only Protected or Private Constructors
How to Properly Overload the ≪≪ Operator For an Ostream
How to See a C/C++ Source File After Preprocessing in Visual Studio
Take the Address of a One-Past-The-End Array Element Via Subscript: Legal by the C++ Standard or Not
How Does Dereferencing of a Function Pointer Happen
How to Execute a Functor or a Lambda in a Given Thread in Qt, Gcd-Style
Is It Okay to Inherit Implementation from Stl Containers, Rather Than Delegate
Subclass/Inherit Standard Containers
Why Can In-Class Initializers Only Use = or {}
Why Is the Use of Rand() Considered Bad
What Is the Easiest Way to Initialize a Std::Vector With Hardcoded Elements
Is There a Standard Sign Function (Signum, Sgn) in C/C++