--- /dev/null
+#!/bin/bash
+
+set -u
+
+filename=${1:-input.txt}
+verbose=${2:- 0}
+exec 3<"$filename"
+OLDIFS=$IFS
+IFS="," read -u 3 -a instructions
+IFS=$OLDIFS
+
+basedir=$(dirname $(readlink -f ${BASH_SOURCE}))
+
+. $basedir/computer.sh
+
+coproc computer (run_program instructions 2>/dev/null)
+comp_pid=${computer_PID}
+comp_stdin=${computer[1]}
+comp_stdout=${computer[0]}
+
+cur_x=0
+cur_y=0
+declare -A map=( [$cur_x,$cur_y]=".")
+min_x=0
+max_x=0
+min_y=0
+max_y=0
+
+refind_home=0
+declare -a oxygen_location=()
+declare -A directions=( [n]=1 [s]=2 [w]=3 [e]=4 )
+declare -A direction_names=( [1]="North" [2]="South" [3]="West" [4]="East" )
+
+if [ "$verbose" == "0" ]; then
+ echo_verbose() { echo "$@"; }
+else
+ echo_verbose() { true ; }
+fi
+
+# use left hand rule, if we can go left, go left, if we can't, go straight, if
+# that fails, go right, and if that fails, go back on ourselves
+cur_direction=${directions[w]}
+
+change_direction() {
+ case $cur_direction in
+ ${directions["n"]})
+ cur_direction=${directions["w"]}
+ ;;
+ ${directions["e"]})
+ cur_direction=${directions["n"]}
+ ;;
+ ${directions["s"]})
+ cur_direction=${directions["e"]}
+ ;;
+ ${directions["w"]})
+ cur_direction=${directions["s"]}
+ ;;
+ esac
+}
+
+wall_change() {
+ case $cur_direction in
+ ${directions["n"]})
+ cur_direction=${directions["e"]}
+ ;;
+ ${directions["e"]})
+ cur_direction=${directions["s"]}
+ ;;
+ ${directions["s"]})
+ cur_direction=${directions["w"]}
+ ;;
+ ${directions["w"]})
+ cur_direction=${directions["n"]}
+ ;;
+ esac
+}
+
+calc_best_route() {
+ declare -A tentative=( [0,0]=0 )
+ declare -A lowest_cost=()
+
+ total_x=$((max_x - $min_x))
+ total_y=$((max_y - $min_y))
+ total_points=$((total_x*total_y))
+ cur_x=0
+ cur_y=0
+
+ while [ ! "${lowest_cost[${oxygen_location[0]},${oxygen_location[1]}]+abc}" ]; do
+ echo -ne "\rProgress: "
+ printf "%2d" $((((${#lowest_cost[@]}*100) / $total_points)))
+ echo -n "%"
+ lowest_cost[$cur_x,$cur_y]="${tentative["$cur_x,$cur_y"]}"
+ unset tentative[$cur_x,$cur_y]
+
+ # go left / right / up / down from our point to get new tentatives
+ for test_x in $((cur_x-1)) $((cur_x+1)); do
+ if [ "${map[$test_x,$cur_y]+abc}" ] && [[ "${map[$test_x,$cur_y]}" =~ [\.O] ]]; then
+ if [ ! "${lowest_cost[$test_x,$cur_y]+abc}" ]; then
+ new_cost=${lowest_cost[$cur_x,$cur_y]}
+ ((new_cost+=1)) # always 1 step from where we were previously
+ if [ "${tentative[$test_x,$cur_y]+abc}" ]; then
+ if [ $new_cost -lt ${tentative[$test_x,$cur_y]} ]; then
+ tentative[$test_x,$cur_y]=$new_cost
+ fi
+ else
+ tentative[$test_x,$cur_y]=$new_cost
+ fi
+ fi
+ fi
+ done
+ for test_y in $((cur_y-1)) $((cur_y+1)); do
+ if [ "${map[$cur_x,$test_y]+abc}" ] && [[ "${map[$cur_x,$test_y]}" =~ [\.O] ]]; then
+ if [ ! "${lowest_cost[$cur_x,$test_y]+abc}" ]; then
+ new_cost=${lowest_cost[$cur_x,$cur_y]}
+ ((new_cost+=1)) # always 1 step from where we were previously
+ if [ "${tentative[$cur_x,$test_y]+abc}" ]; then
+ if [ $new_cost -lt ${tentative[$cur_x,$test_y]} ]; then
+ tentative[$cur_x,$test_y]=$new_cost
+ fi
+ else
+ tentative[$cur_x,$test_y]=$new_cost
+ fi
+ fi
+ fi
+ done
+
+ # find the new lowest tentative
+ new_location=""
+ new_value=-1
+
+ for location in "${!tentative[@]}"; do
+ if [ -z "$new_location" ]; then
+ new_location=$location
+ new_value=${tentative[$location]}
+ elif [ ${tentative[$location]} -lt $new_value ]; then
+ new_location=$location
+ new_value=${tentative[$location]}
+ fi
+ done
+
+ if [ -z "$new_location" ]; then
+ break
+ fi
+ cur_x=${new_location%,*}
+ cur_y=${new_location#*,}
+ done
+ echo -e "\rProgress: 100%"
+
+ echo "Lowest route cost: ${lowest_cost[${oxygen_location[0]},${oxygen_location[1]}]}"
+}
+
+# fill the room with oxygen, this could take a few iterations
+oxygen_fill() {
+ rounds=0
+ declare -A oxygen_locations=( [${oxygen_location[0]},${oxygen_location[1]}]=0 )
+ declare -a spread_points=( "${oxygen_location[0]},${oxygen_location[1]}" )
+ declare -a new_spread_points=()
+
+ while [ "${#spread_points[@]}" -gt 0 ]; do
+ ((rounds+=1))
+ for spread_point in "${spread_points[@]}"; do
+ # check round the point, left, right, up and down, and if they haven't already got O
+ # add them to the oxygen_locations, and the new_spread_points, if they're on the map
+ spread_x=${spread_point%,*}
+ spread_y=${spread_point#*,}
+ for test_x in $((spread_x-1)) $((spread_x+1)); do
+ if [ "${map[$test_x,$spread_y]+abc}" ]; then
+ if [ "${map[$test_x,$spread_y]}" == "." ]; then
+ if [ ! ${oxygen_locations[$test_x,$spread_y]+abc} ]; then
+ oxygen_locations[$test_x,$spread_y]=$rounds
+ new_spread_points+=( "$test_x,$spread_y" )
+ fi
+ fi
+ fi
+ done
+ for test_y in $((spread_y-1)) $((spread_y+1)); do
+ if [ "${map[$spread_x,$test_y]+abc}" ]; then
+ if [ "${map[$spread_x,$test_y]}" == "." ]; then
+ if [ ! "${oxygen_locations[$spread_x,$test_y]+abc}" ]; then
+ oxygen_locations[$spread_x,$test_y]=$rounds
+ new_spread_points+=( "$spread_x,$test_y" )
+ fi
+ fi
+ fi
+ done
+ done
+ if [ ${#new_spread_points[@]} -eq 0 ]; then
+ ((rounds-=1))
+ fi
+ unset spread_points
+ declare -a spread_points=()
+ for spread_point in "${new_spread_points[@]}"; do
+ spread_points+=( "$spread_point" )
+ done
+ unset new_spread_points
+ declare -a new_spread_points=()
+ done
+
+ echo "It'd take $rounds minutes to fill the maze with oxygen"
+}
+
+declare -a spinner=( '-' '\' '|' '/' )
+spinner_offset=0
+
+update_spinner() {
+ echo -ne "\r${spinner[$spinner_offset]}"
+ ((spinner_offset+=1))
+ if [ $spinner_offset -gt $((${#spinner[@]} - 1)) ]; then
+ spinner_offset=0
+ fi
+}
+
+display_map() {
+ echo "min_x $min_x max_x $max_x min_y $min_y max_y $max_y"
+ for (( a=$max_y; a >= $min_y; a-- )); do
+ for (( b=$min_x; b <= $max_x; b++ )); do
+ marker=${map[$b,$a]:-" "}
+ if [ $a -eq 0 ] && [ $b -eq 0 ]; then
+ marker="S"
+ fi
+ if [ $a -eq $cur_y ] && [ $b -eq $cur_x ]; then
+ marker="D"
+ fi
+ echo -n "$marker"
+ done
+ echo
+ done
+ echo
+}
+
+while ps -p $comp_pid > /dev/null 2>/dev/null; do
+ read -u $comp_stdout prompt
+ if [ "$prompt" != "input:" ]; then
+ echo_verbose "We has no input!"
+ exit 2
+ fi
+ echo $cur_direction >&$comp_stdin
+ new_x=$cur_x
+ new_y=$cur_y
+ case $cur_direction in
+ ${directions["n"]})
+ ((new_y+=1))
+ if [ $new_y -gt $max_y ]; then
+ max_y=$new_y
+ fi
+ ;;
+ ${directions["s"]})
+ ((new_y-=1))
+ if [ $new_y -lt $min_y ]; then
+ min_y=$new_y
+ fi
+ ;;
+ ${directions["e"]})
+ ((new_x+=1))
+ if [ $new_x -gt $max_x ]; then
+ max_x=$new_x
+ fi
+ ;;
+ ${directions["w"]})
+ ((new_x-=1))
+ if [ $new_x -lt $min_x ]; then
+ min_x=$new_x
+ fi
+ ;;
+ esac
+ echo_verbose "x: $cur_x, new_x: $new_x, y: $cur_y, new_y: $new_y, direction: ${direction_names[$cur_direction]}"
+ read -u $comp_stdout status
+ case $status in
+ "0")
+ echo_verbose "Hit a wall"
+ map[$new_x,$new_y]="#"
+ wall_change
+ ;;
+ "1")
+ echo_verbose "Moved ${direction_names[$cur_direction]}"
+ if [ ! ${map[$cur_x,$cur_y]+abc} ]; then
+ map[$cur_x,$cur_y]="."
+ fi
+ cur_x=$new_x
+ cur_y=$new_y
+ if [ $refind_home -eq 1 ] && [ $new_x -eq 0 ] && [ $new_y -eq 0 ]; then
+ break
+ fi
+ change_direction
+ ;;
+ "2")
+ echo_verbose "Found oxygen system"
+ map[$cur_x,$cur_y]="."
+ map[$new_x,$new_y]="O"
+ cur_x=$new_x
+ cur_y=$new_y
+ refind_home=1
+ echo -ne '\r \r'
+ display_map
+ oxygen_location=( $cur_x $cur_y )
+ ;;
+ *)
+ echo_verbose "Weird response '$status'"
+ ;;
+ esac
+ update_spinner
+done
+
+echo -ne '\r \r'
+display_map
+
+echo "Calculating best route."
+
+calc_best_route
+oxygen_fill
+
+echo 0 >&$comp_stdin
projects / advent-of-code-2019.git / blobdiff