Random walk 10x10 array in bash

Question

Problem: Write a program that generates a "random walk" across a 10 x 10 array. The array will contain characters (all '.' initially). The program must randomly "walk" from element to element, always going up, down, left or right by one element. The elements visited by the program will be labeled with the letters A through Z, in the order visited. Here's an example of the desired output:

A . . . . . . . . .
B C D . . . . . . .
. F E . . . . . . .
H G . . . . . . . .
I . . . . . . . . .
J . . . . . . . Z .
K . . R S T U V Y .
L M P Q . . . W X .
. N O . . . . . . .
. . . . . . . . . .

Before performing a move, check that (a) it won't go outside the array, and (b) it doesn't take us to an element that already has a letter assigned. If either condition is violated, try moving in another direction. If all four directions are blocked, the program must terminate. Here's an example of premature termination:

A B G H I . . . . .
. C F . J K . . . .
. D E . M L . . . .
. . . . N O . . . .
. . W X Y P Q . . .
. . V U T S R . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .

Y is blocked on all four sides, so there's no place to put Z.

expected output:

A . . . . . . . . .
B C D . . . . . . .
. F E . . . . . . .
H G . . . . . . . .
I . . . . . . . . .
J . . . . . . . Z .
K . . R S T U V Y .
L M P Q . . . W X .
. N O . . . . . . .
. . . . . . . . . .

actual output:

.abcdefghi
.abcdefghi
.abcdefghi
.abcdefghi
.abcdefghi
.abcdefghi
.abcdefghi
.abcdefghi
.abcdefghi
.abcdefghi

This is C language exercise but I`m trying to write it in bash

my code which doesnt want to work

#!/bin/bash
#set -x
rows=10
cols=10
UP=0
DOWN=1
RIGHT=2
LEFT=3
i=0
b=0
#initialising and filling array with "."
while [ $i -lt $rows ]; do
    while [ $b -lt $cols ]; do
    my_array[$i,$b]='.'
    ((b++))
    done
    b=0
    ((i++))
done

#initialising array with letters from alphabet in each element in ascending order
abc=({a..z})

b=0
r=0
c=0
#set -x
#core section where movements are done with checking boundaries of array and neighboring elements
while [ "$b" -lt "${#abc[@]}" ]; do
move=$(($RANDOM % 4))
case $move in
$UP) if [ $(($r+1)) -lt $rows ] && [ "${my_array[$r+1,$c]}" == "." ]; then
     ((r++))
     my_array[$r,$c]=${abc[$b]}
     ((b++))
     elif [ $(($r-1)) -ge 0 ] && [ "${my_array[$r-1,$c]}" == "." ]; then
     ((r--))
     my_array[$r,$c]=${abc[$b]}
     ((b++))
     elif [ $(($c+1)) -lt $cols ] && [ "${my_array[$r,$c+1]}" == "." ]; then
     ((c++))
     my_array[$r,$c]=${abc[$b]}
     ((b++))
     elif [ $(($c-1)) -ge 0 ] && [ "${my_array[$r,$c-1]}" == "." ]; then
     ((c--))
     my_array[$r,$c]=${abc[$b]}
     ((b++))
     else
     b=${#abc[@]}
     fi;;
$DOWN) if [ $(($r-1)) -ge 0 ] && [ "${my_array[$r-1,$c]}" == "." ]; then
    ((r--))
    my_array[$r,$c]=${abc[$b]}
    ((b++))
    elif [ $(($r+1)) -lt $rows ] && [ "${my_array[$r+1,$c]}" == "." ]; then
    ((r++))
    my_array[$r,$c]=${abc[$b]}
    ((b++))
    elif [ $(($c+1)) -lt $cols ] && [ "${my_array[$r,$c+1]}" == "." ]; then
    ((c++))
    my_array[$r,$c]=${abc[$b]}
    ((b++))
    elif [ $(($c-1)) -ge 0 ] && [ "${my_array[$r,$c-1]}" == "." ]; then
    ((c--))
    my_array[$r,$c]=${abc[$b]}
    ((b++))
    else 
    b=${#abc[@]}
    fi;;
$RIGHT) if [ $(($c+1)) -lt $cols ] && [ "${my_array[$r,$c+1]}" == "." ]; then
    ((c++))
    my_array[$r,$c]=${abc[$b]}
    ((b++))
    elif [ $(($c-1)) -ge 0 ] && [ "${my_array[$r,$c-1]}" == "." ]; then
    ((c--))
    my_array[$r,$c]=${abc[$b]}
    ((b++))
    elif [ $(($r+1)) -lt $rows ] && [ "${my_array[$r+1,$c]}" == "." ]; then
    ((r++))
    my_array[$r,$c]=${abc[$b]}
    ((b++))
    elif [ $(($r-1)) -ge 0 ] && [ "${my_array[$r-1,$c]}" == "." ]; then
    ((r--))
    my_array[$r,$c]=${abc[$b]}
    ((b++))
    else
    b=${#abc[@]}
    fi;;
$LEFT) if [ $(($c-1)) -ge 0 ] && [ "${my_array[$r,$c-1]}" == "." ]; then
    ((c--))
    my_array[$r,$c]=${abc[$b]}
    ((b++))
    elif [ $(($c+1)) -lt $cols ] && [ "${my_array[$r,$c+1]}" == "." ]; then
    ((c++))
    my_array[$r,$c]=${abc[$b]}
    ((b++))
    elif [ $(($r+1)) -lt $rows ] && [ "${my_array[$r+1,$c]}" == "." ]; then
    ((r++))
    my_array[$r,$c]=${abc[$b]}
    ((b++))
    elif [ $(($r-1)) -ge 0 ] && [ "${my_array[$r-1,$c]}" == "." ]; then
    ((r--))
    my_array[$r,$c]=${abc[$b]}
    ((b++))
    else
    b=${#abc[@]}
    fi;;
*) echo "Something went wrong..."
   exit 1;;
esac
done

i=0
b=0
#set -x

#printing whats in the array
while [ $i -lt $rows ]; do
   b=0
    while [ $b -lt $cols ]; do
    echo -n "${my_array[$i,$b]}"
    ((b++))
    done
    echo
    ((i++))
done

exit 0

EDIT: solved the problem forgot to explicitly declare assosiative array "declare -A my_array" forgot to use $(($r+n)) in my_array when checking moves

wouldnt mind to see more efficient code. readability doesnt matter

Answer 1

My take:

#!/usr/bin/env bash

declare -A ary
declare -r size=10

main() {
    local char=65       # ASCII A
    local cell=0,0

    make_array

    while true; do
        ary[$cell]=$(chr $char)
        if ! cell=$(next_cell "$cell") || ((++char > 90)); then
            break
        fi
    done

    print_array
}

make_array() {
    local x y
    for ((x=0; x < size; x++)); do
        for ((y=0; y < size; y++)); do
            ary[$x,$y]='.'
        done
    done
}

chr() {
    printf "\x$(printf "%x" "$1")"
}

next_cell() {
    local cell=$1
    local x y xx yy dx dy
    local free_neighbours=()
    IFS=',' read -r x y <<<"$cell"
    for dx in -1 1; do
        ((xx = x + dx))
        if ((0 <= xx && xx < size)) && [[ ${ary[$xx,$y]} == '.' ]]; then
            free_neighbours+=( "$xx,$y" )
        fi
    done
    for dy in -1 1; do
        ((yy = y + dy))
        if ((0 <= yy && yy < size)) && [[ ${ary[$x,$yy]} == '.' ]]; then
            free_neighbours+=( "$x,$yy" )
        fi
    done
    if (( ${#free_neighbours[@]} == 0 )); then
        return 1
    else
        local idx=$(( RANDOM % ${#free_neighbours[@]} ))
        echo "${free_neighbours[idx]}"
    fi
}

print_array() {
    local row x y
    for ((x=0; x < size; x++)); do
        row=()
        for ((y=0; y < size; y++)); do
            row+=( "${ary[$x,$y]}" )
        done
        echo "${row[*]}"
    done
}

main "$@"

Answer 2

bash does not have multidimensional arrays. my_array[$i,$b]='.' behaves like my_array[$b]='.'; consequently, you only have an array of 10 elements, not 10x10.

On bash 4.0+, you have access to associative arrays (basically Python's dict). You need to declare it beforehand:

declare -A my_array

This is somewhat similar to saying my_array = {} in Python. With that, my_array[$i,$b]='.' will behave like Python's my_array[f"{i},{b}"] = '.'.

However, this means you no longer have integral indices, so ${my_array[$r-1,$c]} will behave like Python's my_array[f"{r}-1,{c}"] — i.e. if $r=5 and $c=3, it will try to access the element under the key 5-1,3 instead of 4,3. The correct way to do this would be ${my_array[$((r-1)),$c]}.

Alternately, you can work with a single-dimensional array of strings, such that ${my_array[0]} is "..........". It is still a bit awkward given that bash does not let you change individual characters. This would work on an older bash as well (like the one that comes by default on a Mac OS). Here is a bash 3.2 compatible implementation:

#!/bin/bash
rows=10
cols=10

# make a prototypal row (`$rows` dots)
# https://stackoverflow.com/a/5349796/240443
dots=$(printf "%${rows}s" | tr ' ' .)
# make an array by repeating the row `$rows` times
read -d '' -r -a my_array < <(yes "$dots" | head -n "$rows")

abc=({a..z})

b=0
r=0
c=0

# start with the first letter
# can't directly change string at index, so we have to do some cutting
prefix="${my_array[r]:0:c}"
suffix="${my_array[r]:c+1}"
letter="${abc[b++]}"
my_array[r]="$letter$suffix"

while [ "$b" -lt "${#abc[@]}" ]
do
  # random order of the four directions, plus the case when they all fail
  for move in $(shuf -e UP DOWN LEFT RIGHT) ELSE
  do
    # calculate the new coordinates
    case $move in
      UP)
        nr=$((r-1))
        nc=$c
        ;;
      DOWN)
        nr=$((r+1))
        nc=$c
        ;;
      LEFT)
        nr=$r
        nc=$((c-1))
        ;;
      RIGHT)
        nr=$r
        nc=$((c+1))
        ;;
      ELSE)
        # no valid move left
        break 2
        ;;
    esac
    # skip invalid coordinates
    if [[
      $nc -ge $cols || $nc -lt 0 || $nr -ge $rows || $nr -lt 0 ||
      ${my_array[nr]:nc:1} != .
    ]]
    then
      continue
    fi
    # move, then set the letter
    r="$nr"
    c="$nc"
    prefix="${my_array[r]:0:c}"
    suffix="${my_array[r]:c+1}"
    letter="${abc[b++]}"
    my_array[r]="$prefix$letter$suffix"
    # no need to try other moves
    break
  done
done

for row in "${my_array[@]}"
do
  echo $row
done

Answer 3

If you are looking to learn a higher-level language than C to solve problems like this, you would be much better off learning Python than Bash, or any of the other legacy Unix tools. The legacy Unix tools haven't advanced significantly since the 1980s. Tool support is poor, training material is poor, and most available code (including code in accepted and much-upvoted answers on Stack Overflow) is very bad. Time spent learning Python will almost certainly be much better rewarded.

If you are interested in a Bash solution anyway, try this Shellcheck-clean (except for a spurious warning about dirsteps not being used) pure Bash (2+) code:

#! /bin/bash -p

readonly kSIZE=10

# All possible sequences of directions to try (0:RIGHT, 1:LEFT, 2:DOWN, 3:UP)
tries=( 0123 0132 0213 0231 0312 0321 1023 1032 1203 1230 1302 1320
        2013 2031 2103 2130 2301 2310 3012 3021 3102 3120 3201 3210 )

# Populate a bordered array (size (kSIZE+2)x(kSIZE+2).
# Central elements contain the "real" array where we want to place letters and
# are initialized with a '.'.
# Border elements (first and last rows, first and last columns) are left
# unitialized to indicate that they are unavailable.
# Simulate a two-dimensional array in a linear array by placing element
# [row,col] at offset [row*kBSIZE+col].
readonly kBSIZE=$((kSIZE+2))
readonly kBMAX=$((kBSIZE-1))
barray=()
for ((row=1; row<kBMAX; row++)); do
    for ((col=1; col<kBMAX; col++)); do
        barray[row*kBSIZE+col]='.'
    done
done

# Array of steps within the array corresponding to moves in each direction
dirsteps=( 1 -1 "$kBSIZE" "-$kBSIZE" )

# Add letters to the bordered array
declare -i pos='kBSIZE+1' newpos
for lett in {A..Z}; do
    barray[pos]=$lett

    try=${tries[RANDOM%${#tries[*]}]}
    for ((i=0; i<${#try}; i++)); do
        newpos="pos+dirsteps[${try:i:1}]"
        if [[ ${barray[newpos]-} == '.' ]]; then
            pos=newpos
            continue 2  # Place for a letter is found so move to next letter
        fi
    done
    break   # Could not find a place for a letter so give up on other letters
done

# Print the real array
for ((row=1; row<kBMAX; row++)); do
    printf '%s' "${barray[@]:row*kBSIZE+1:kSIZE}"
    printf '\n'
done

• I tested this (lightly) with Bash 5.2 and Bash 3.2, but I think it might work with versions back to 2.0.