Проверка соседних элементов в плоском массиве

Описание проблемы:
Я хочу перебрать массив (плоский 2D -> 1D массив прямо сейчас) и продолжать проверять его ближайших соседей. Исходя из этого, я хочу определить, являются ли они мертвыми / живыми ('X' или '.'), И изменить их состояние в соответствии с моими правилами (упрощенные правила Конвея).

Моя сетка выглядит так, например:

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

Но у меня этот массив сведен к массиву 1D для итерации по нему. Так что в основном это выглядит примерно так: ....X...X....X. и т. д. После записи этого на бумаге, я думаю, есть несколько случаев, чтобы проверить в этой "сетке":

  • Элемент TopLeft (i = 0) - первый элемент, 3 соседей / случая для проверки
  • Элемент TopRight (i = nColumns - 1), как указано выше
  • Элемент BottomLeft (i = nColumns * nRows - nColumns), как указано выше
  • Элемент BottomRight (i = nColumns * nRows - 1) - последний элемент, как указано выше
  • "Граничные" элементы (5 соседей без угловых элементов)
  • Средние элементы с 8 соседями

Но, кажется, совершенно глупо проверять это с некоторыми утверждениями if и case. Если бы я мог использовать реальные 2D-массивы, я думаю, что я мог бы просто создать массив смещения (-1, 1), (0, 1)... и так далее. Но я не могу придумать, как справиться с этим с помощью моего кода. Буду очень рад любым советам / примерам и так далее.

Мой код до сих пор:

cellsAlive=0

#STDIN variables
geneFile=$1
nRows=$2 
nColumns=$3
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 (добавить пробел, как в конце):

1 2
4 5
6 7
13 2
5 7
4 4
9 2
11 1
10 8
Источник

1 ответ

Решение

Хорошо. Вот так. Поскольку я нашел этот вопрос интересным для реализации в bash, я просто написал реализацию игры жизни Конвея.

Вероятно, основная часть ответа на ваш вопрос: как получить доступ к соседям для позиции в матрице, если она линеаризована?,

Таким образом, вы можете получить доступ к элементу в плоской матрице

(row*fieldwidth)+columnoffset.

Доступ к каждому соседу можно получить, настроив row а также columnoffset от +/-1 начиная с row и columnoffset в 0,

Посмотрите на getnextstate функция для просмотра специальных случаев.

Итак, вот реализация. Вы можете предоставить файл в качестве входных данных, содержащий только CELLALIVEMARKER,CELLDEADMARKER и пробелы. Если длина для выровненной матрицы не соответствует параметру ширины / высоты для FIELD это просто колодки со случайными значениями.

#!/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

Таким образом, предоставляя файл init.mtx содержащий следующую матрицу

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

Вы можете создать простой планер (от верхнего левого до нижнего правого)

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

используя правила Конвея по умолчанию, запустив этот скрипт следующим образом:

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

Надеюсь это поможет. И, кстати, было весело реализовать это в Bash:)

Источник
Другие вопросы по тегам