Bash bot for The Great Escape codingame.com competition

# Auto-generated code below aims at helping you parse
# the standard input according to the problem statement.

push_queue () {
    local element=$1;
    queue=(${queue[@]} $element);
    elems_queue=$((elems_queue+1));
    #echo "queue after push: "${queue[*]} >&2;
}

pop_queue () {
    ret=${queue[$read_iter]};
    read_iter=$((read_iter+1));
    #queue=(${queue[@]:1});
    #echo "queue after pop: "${queue[*]} >&2;
}

process_next () {
    local xnext=$1;
    local ynext=$2;
    local dir=$3;
    local dist=$4;
    if [ ${vis[$xnext,$ynext]} == "0" ]; then
        vis[$xnext,$ynext]=$dist;
        fb[$xnext,$ynext]=$((($dir+2)%4));
        element=$xnext$ynext;
        #echo "pushing "$element" at "$dist >&2;
        push_queue $element;
    fi
}

can_pass () {
    local curx=$1;
    local cury=$2;
    local dx=${DIRX[$3]};
    local dy=${DIRY[$3]};
    #echo "pass test: "$curx" "$cury" "$dx" "$dy >&2;
    if [ $dx == -1 ]; then
        if [ $curx == 0 ] || [ ${wV[$curx,$cury]} == 1 ]; then
            return 1;
        fi
    elif [ $dx == 1 ]; then
        if [ $curx == 8 ] || [ ${wV[$((curx+1)),$cury]} == 1 ]; then
            return 1;
        fi
    elif [ $dy == -1 ]; then
        if [ $cury == 0 ] || [ ${wH[$curx,$cury]} == 1 ]; then
            return 1;
        fi
    else
        if [ $cury == 8 ] || [ ${wH[$curx,$(($cury+1))]} == 1 ]; then
            return 1;
        fi
    fi
    return 0;
}

declare -A vis;
declare -A fb;

bfs_goal_reached() {
    local x=$1;
    local y=$2;
    if [ $goal == 1 ] && [ $x == 0 ]; then
        return 0;
    elif [ $goal == 2 ] && [ $y == 8 ]; then
        return 0;
    elif [ $goal == 3 ] && [ $x == 8 ]; then
        return 0;
    fi
    return 1;
}


#do bfs from the player location filling a distance and a path matrix
#my bash skills are awesome so this can be used at most 2 or 3 times per turn
#before timing out, so no chance to explore the game tree in any depth :)
bfs () {
    local x=$1;
    local y=$2;

    for (( i=0; i<9; i++ )) do
        for (( j=0; j<9; j++ )) do
            vis[$i,$j]=0;
            fb[$i,$j]=0;
        done
    done

    queue=($x$y);
    read_iter=0;
    elems_queue=1;
    while [ $elems_queue != $read_iter ]
    do
        pop_queue;
        #echo $ret >&2;
        xbfs=${ret:0:1};
        ybfs=${ret:1:1};
        dist=${vis[$xbfs,$ybfs]};
        dist=$((dist+1));
        for (( i=0; i<4; i++ )) do
            if can_pass $xbfs $ybfs $i; then
                xnext=$((xbfs+${DIRX[$i]}));
                ynext=$((ybfs+${DIRY[$i]}));
                if [ $xnext != $x ] || [ $ynext != $y ]; then
                    process_next $xnext $ynext $i $dist;
                    if bfs_goal_reached $xnext $ynext; then
                        return 0;
                    fi
                fi
            fi
        done
    done
    return 1;
}

#backtrack on the path matrix to find the optimal direction from the bot's current location
get_optimal_dir_post_bfs () {
    local x=$xnext;
    local y=$ynext;
    while [ ${vis[$x,$y]} != 0 ]
    do
        dir=${fb[$x,$y]};
        x=$(($x+${DIRX[$dir]}));
        y=$(($y+${DIRY[$dir]}));
    done
    optimal_dir=$((($dir+2)%4));
}

#if the player is at x and 1 move from scoring, 1 means block x and x+1 0 means block x-1 and x
#these values are selected to ensure the opponent has to do the largest number of moves assuming
#he/she is following a shortest path and there are no other blocking walls
strat1=(1 0 1 0 1 1 0 1 0)
strat2=(1 0 0 1 0 0 1 1 0)

place_v () {
    local x=$1;
    local y=$2;
    local next=$3;
    local ox=$x;
    if [ $ox == 1 ]; then
        ox=0;
    fi
    if [ $next == 1 ]; then
        if [ ${wV[$x,$((y+1))]} == 0 ] && [ ${wH[$ox,$((y+1))]} == 0 ]; then
            echo $x" "$y" V eat bricks :)";
            return 0;
        fi
    else
        if [ ${wV[$x,$((y-1))]} == 0 ] && [ ${wH[$ox,$y]} == 0 ]; then
            echo $x" "$(($y-1))" V eat bricks :)";
            return 0;
        fi
    fi
    return 1;
}



will_block_0 () {
    if [ ${px[0]} == 7 ]; then
        if [ ${wV[8,${py[0]}]} == 0 ]; then
            v=${py[0]}
            if place_v 8 $v ${strat1[$v]} 8; then
                return 0;
            elif place_v 8 $v ${strat2[$v]} 8; then
                return 0;
            fi
        fi
    fi
    return 1;
}



will_block_1 () {
    if [ ${px[1]} == 1 ]; then
        if [ ${wV[1,${py[1]}]} == 0 ]; then
            v=${py[1]}
            if place_v 1 $v ${strat1[$v]} 0; then
                return 0;
            elif place_v 1 $v ${strat2[$v]} 0; then
                return 0;
            fi
        fi
    fi
    return 1;
}

place_h () {
    local x=$1;
    local y=$2;
    local next=$3;
    if [ $next == 1 ]; then
        if [ ${wH[$(($x+1)),$y]} == 0 ] && [ ${wV[$(($x+1)),$y]} == 0 ]; then
            echo $x" 8 H eat bricks :)";
            return 0;
        fi
    else
        if [ ${wH[$(($x-1)),$y]} == 0 ] && [ ${wV[$x,$y]} == 0 ]; then
            echo $(($x-1))" 8 H eat bricks :)";
            return 0;
        fi
    fi
    return 1;
}

will_block_2 () {
    if [ ${py[2]} == 7 ]; then
        if [ ${wH[${px[2]},8]} == 0 ]; then
            v=${px[2]}
            if place_h $v 8 ${strat1[$v]}; then
                return 0;
            elif place_h $v 8 ${strat2[$v]}; then
                return 0;
            fi
        fi
    fi
    return 1;
}


# w: width of the board
# h: height of the board
# playerCount: number of players (2 or 3)
# myId: id of my player (0 = 1st player, 1 = 2nd player, ...)
read w h playerCount myId
if [ $myId -eq 0 ]; then
    goal=3;
fi
if [ $myId -eq 1 ]; then
    goal=1;
fi
if [ $myId -eq 2 ]; then
    goal=2;
fi

DIRS=("UP" "LEFT" "DOWN" "RIGHT")
DIRX=(0 -1 0 1)
DIRY=(-1 0 1 0)
WINS=("See ya suckers :P" "Bye losers ;)" "So long and thanks for all the walls :D")
# game loop
while true; do
    px=(0 0 0)
    py=(0 0 0)
    for (( i=0; i<playerCount; i++ )); do
        # x: x-coordinate of the player
        # y: y-coordinate of the player
        # wallsLeft: number of walls available for the player
        read x y wallsLeft
        px[$i]=$x;
        py[$i]=$y;
        if [ $i -eq $myId ]; then
            tx=$x
            ty=$y
            mwalls=$wallsLeft
        fi
    done

    #wall storage
    declare -A wH
    declare -A wV
    for (( i=0; i<9; i++ )) do
        for (( j=0; j<9; j++ )) do
            wH[$i,$j]=0;
            wV[$i,$j]=0;
        done
    done

    # wallCount: number of walls on the board
    read wallCount
    for (( i=0; i<wallCount; i++ )); do
        # wallX: x-coordinate of the wall
        # wallY: y-coordinate of the wall
        # wallOrientation: wall orientation ('H' or 'V')
        read wallX wallY wallOrientation
        if [ ${wallOrientation} == "H" ]; then
            wH[$wallX,$wallY]=1;
            wH[$(($wallX+1)),$wallY]=1;
        else
            wV[$wallX,$wallY]=1;
            wV[$wallX,$(($wallY+1))]=1;
        fi
    done

    #determine the shortest path to exit
    xstart=$tx;
    ystart=$ty;
    bfs $tx $ty;
    get_optimal_dir_post_bfs;
    d=$optimal_dir;

    #if I don't have more walls to place, take shortest path
    if [ $mwalls == 0 ]; then
        echo ${DIRS[$d]}" No blocking for me no more...";
        continue;
    fi

    #eif the next move will win the game for me, make it
    if [ $d == $goal ]; then
        x=$RANDOM
        let "x %= 3"
        message=${WINS[$x]};
        if [ ${DIRS[$d]} == "DOWN" ] && [ $ty == 7 ]; then
            echo "DOWN "$message;
            continue;
        elif [ ${DIRS[$d]} == "LEFT" ] && [ $tx == 1 ]; then
            echo "LEFT "$message;
            continue;
        elif [ ${DIRS[$d]} == "RIGHT" ] && [ $tx == 7 ]; then
            echo "RIGHT "$message;
            continue;
        fi
    fi

    #try to block players that are almost scoring,
    #attempt to block the next player to move, first
    if [ $myId == 0 ]; then
        if will_block_1; then
            continue;
        elif will_block_2; then
            continue;
        fi
    elif [ $myId == 1 ]; then
        if will_block_2; then
            continue;
        elif will_block_0; then
            continue;
        fi
    else
        if will_block_0; then
            continue;
        elif will_block_1; then
            continue;
        fi
    fi

    #if no wall was used, follow shortest path
    echo ${DIRS[$d]} # action: LEFT, RIGHT, UP, DOWN or "putX putY putOrientation" to place a wall
done