检查平面数组中的相邻元素

Question

问题描述：
我想遍历一个数组（现在展平 2D --> 1D 数组）并继续检查它最近的邻居。由此我想确定它们是否是 dead/alive（'X' 或 '.'）并根据我的规则（简化的康威规则）更改它们的状态。

我的网格看起来像这样例如：

...............
...........X...
.X.......X...X.
...............
....X..........
....X..........
...............
.....XX........
..........X....
...............
Cells alive: 9

但我将此数组展平为一维数组以对其进行迭代。所以基本上它变成了这样的东西：....X...X....X. 等等。把它写在纸上后，我认为有几个案例可以检查这个 "grid":

TopLeft 元素 (i = 0) - 第一个元素，3 neighbours/cases 要检查
TopRight 元素 (i = nColumns - 1)，如上
BottomLeft 元素 (i = nColumns * nRows - nColumns)，如上
BottomRight 元素 (i = nColumns * nRows - 1) - 最后一个元素，如上
"Border" 个元素（5 个邻居，每个没有角元素）
有 8 个邻居的中间元素

但是用一些 if 和 case 语句来检查它似乎完全愚蠢。如果我可以使用真正的二维数组，我想我可以创建偏移量 (-1, 1)、(0, 1)... 等数组。但我想不出如何用我的代码处理这个问题。任何tips/examples等等我都会很高兴。

到目前为止我的代码：

cellsAlive=0

#STDIN variables
geneFile=
nRows= 
nColumns=
let "cells = $nRows * $nColumns" 
declare -i tick_rate # instead maybe use watch or sleep

readarray -t geneArr < $geneFile # -t removes a trailing newline from each line read.
elementsCounts=${#geneArr[@]}

echo -e "--- Coordinates ---"
for (( i = 0; i < $elementsCounts; i++ )); do
    echo "${geneArr[$i]}" #| cut -d' ' -f2 $geneFile | head -2
done

echo -e "\n--- Grid ---"
#file must end with a newline
[[ $geneFile && -f $geneFile && -r $geneFile ]] || { printf >&2 'arg must be readable file.\n'; exit; }

array=()
for ((i=0; i<nRows*nColumns; ++i)); do
    array+=( '.' )
done
printf "\n"

while read -r x y; do 
    [[ $x && $y ]] || continue
    [[ $x = +([[:digit:]]) && $y = +([[:digit:]]) ]] || continue
    ((x=10#$x,y=10#$y)) #10 digit base
    (( x<nRows && y<nColumns )) || continue
    array[x+y*nRows]='X' 
    if [[ ${array[x+y*nRows]} == 'X' ]]; then
        let "cellsAlive += 1"
    fi
done < "$geneFile"

# print to stdout and to file
for((i=0;i<nColumns;++i)); do
    printf '%s' "${array[@]:i*nRows:nRows}" $'\n'
done | tee currentState 

arrayCopy=("${array[@]}")  
printf "Cells alive: %d" $cellsAlive ; printf "\n"

# printf "\n"

for (( i = 0; i < ${#arrayCopy[@]}; i++ )); do 
    #neighboursCount=0
    case $i in

        "0") if [[ ${arrayCopy[$(($i - 1))]} == 'X' ]] || [[ ${arrayCopy[$(($i + $nColumns))]} == 'X' ]] || [[ ${arrayCopy[$(($i + $nColumns + 1))]} == 'X' ]] ; then #TopLeft
            echo "That is just ridiculous way to check it..."
        fi ;;
        "$(($nColumns - 1))") printf "${arrayCopy[$i]}" ;; #TopRight
        "$(($nColumns*$nRows-1))") printf "${arrayCopy[$i]}" ;; #BottomRight
        "$(($nColumns*$nRows-$nColumns))") printf "${arrayCopy[$i]}" ;; #BottomLeft
        *) ;; #Middle elements with 8 neighbours
    esac
done
printf "\n"

在此先感谢您的帮助。

示例geneFile.txt（在末尾添加空格）：

Answer 1

好的。开始了。因为我发现在 bash 中实现这个问题很有趣，所以我刚刚编写了康威生命游戏的实现。

回答您的问题的主要部分可能是：如果矩阵是线性化的，如何访问矩阵中某个位置的邻居？。

因此您可以通过

访问扁平矩阵中的元素

(row*fieldwidth)+columnoffset.

然后可以通过调整 row 和 columnoffset 来访问每个邻居，方法是 +/-1 从 0 处的行和列偏移量开始。

查看 getnextstate 函数以查看特殊情况。

所以这里是实现。您可以提供一个仅包含 CELLALIVEMARKER、CELLDEADMARKER 和空格的文件作为输入。如果扁平矩阵的长度不适合 FIELD 的 width/height 参数，它只是用随机值填充。

#!/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} [=11=]) FIELDWIDTH FIELDHEIGHT RULESALIVE RULESDEAD [LINSTARTMATRIX]"
  ${ECHO} "EXAMPLES: ./$(${BASENAME} [=11=]) 50         50          \"2 3\"    \"3\""
  ${ECHO} "          ./$(${BASENAME} [=11=]) 50         50          \"2 3\"    \"3\""    init.mtx
  exit
fi

# field values
FWIDTH=
FHEIGHT=
# number of living neighbours for a living cell to stay alive in the next generation
RULESALIVE=($(${ECHO} ))
# number of living neighbours for a dead cell to become alive in the next generation
RULESDEAD=($(${ECHO} ))
CELLALIVEMARKER="o"
CELLDEADMARKER="."
FIELD=() # flatted matrix representation
# if there are just marker values or spaces in the file it is a valid one
${CAT}  | ${GREP} -oq '[^\'${CELLALIVEMARKER}'\'${CELLDEADMARKER}'\ ]'
isvalid="${?}"
if [ "" != "" ] && [ "${isvalid}" == "1" ]; then
  FIELD=($(${CAT} ))
  # 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="" # row
  local j="" # 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

因此提供包含以下矩阵的文件init.mtx

. o . . . . . . . .
. . o . . . . . . .
o o o . . . . . . .
. . . . . . . . . .
. . . . . . . . . . 
. . . . . . . . . . 
. . . . . . . . . . 
. . . . . . . . . . 
. . . . . . . . . . 
. . . . . . . . . .

您可以创建一个简单的滑翔机（从左上角到右下角）

. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . . 
. . . . . . . . . . 
. . . . . . . . . . 
. . . . . . . . . . 
. . . . . . . . o o 
. . . . . . . . o o

通过运行这个脚本使用Conway的默认规则如下：

./gameoflife 10 10 "2 3" "3" init.mtx

希望这对您有所帮助。顺便说一句，在 bash 中实现它很有趣 :)

检查平面数组中的相邻元素

Checking neighbour elements in flat array

arrays

bash

conways-game-of-life