day15/run.sh

   1 #!/bin/bash
   2
   3 set -u
   4
   5 filename=${1:-input.txt}
   6 verbose=${2:- 0}
   7 exec 3<"$filename"
   8 OLDIFS=$IFS
   9 IFS="," read -u 3 -a instructions
  10 IFS=$OLDIFS
  11
  12 basedir=$(dirname $(readlink -f ${BASH_SOURCE}))
  13
  14 . $basedir/computer.sh
  15
  16 coproc computer (run_program instructions 2>/dev/null)
  17 comp_pid=${computer_PID}
  18 comp_stdin=${computer[1]}
  19 comp_stdout=${computer[0]}
  20
  21 cur_x=0
  22 cur_y=0
  23 declare -A map=( [$cur_x,$cur_y]=".")
  24 min_x=0
  25 max_x=0
  26 min_y=0
  27 max_y=0
  28
  29 refind_home=0
  30 declare -a oxygen_location=()
  31 declare -A directions=( [n]=1 [s]=2 [w]=3 [e]=4 )
  32 declare -A direction_names=( [1]="North" [2]="South" [3]="West" [4]="East" )
  33
  34 if [ "$verbose" == "0" ]; then
  35     echo_verbose() { echo "$@"; }
  36 else
  37     echo_verbose() { true ; }
  38 fi
  39
  40 # use left hand rule, if we can go left, go left, if we can't, go straight, if
  41 # that fails, go right, and if that fails, go back on ourselves
  42 cur_direction=${directions[w]}
  43
  44 change_direction() {
  45     case $cur_direction in
  46         ${directions["n"]})
  47             cur_direction=${directions["w"]}
  48             ;;
  49         ${directions["e"]})
  50             cur_direction=${directions["n"]}
  51             ;;
  52         ${directions["s"]})
  53             cur_direction=${directions["e"]}
  54             ;;
  55         ${directions["w"]})
  56             cur_direction=${directions["s"]}
  57             ;;
  58     esac
  59 }
  60
  61 wall_change() {
  62     case $cur_direction in
  63         ${directions["n"]})
  64             cur_direction=${directions["e"]}
  65             ;;
  66         ${directions["e"]})
  67             cur_direction=${directions["s"]}
  68             ;;
  69         ${directions["s"]})
  70             cur_direction=${directions["w"]}
  71             ;;
  72         ${directions["w"]})
  73             cur_direction=${directions["n"]}
  74             ;;
  75     esac
  76 }
  77
  78 calc_best_route() {
  79     declare -A tentative=( [0,0]=0 )
  80     declare -A lowest_cost=()
  81
  82     total_x=$((max_x - $min_x))
  83     total_y=$((max_y - $min_y))
  84     total_points=$((total_x*total_y))
  85     cur_x=0
  86     cur_y=0
  87
  88     while [ ! "${lowest_cost[${oxygen_location[0]},${oxygen_location[1]}]+abc}" ]; do
  89         echo -ne "\rProgress: "
  90         printf "%2d" $((((${#lowest_cost[@]}*100) / $total_points)))
  91         echo -n "%"
  92         lowest_cost[$cur_x,$cur_y]="${tentative["$cur_x,$cur_y"]}"
  93         unset tentative[$cur_x,$cur_y]
  94
  95         # go left / right / up / down from our point to get new tentatives
  96         for test_x in $((cur_x-1)) $((cur_x+1)); do
  97             if [ "${map[$test_x,$cur_y]+abc}" ] && [[ "${map[$test_x,$cur_y]}" =~ [\.O] ]]; then
  98                 if [ ! "${lowest_cost[$test_x,$cur_y]+abc}" ]; then
  99                     new_cost=${lowest_cost[$cur_x,$cur_y]}
 100                     ((new_cost+=1)) # always 1 step from where we were previously
 101                     if [ "${tentative[$test_x,$cur_y]+abc}" ]; then
 102                         if [ $new_cost -lt ${tentative[$test_x,$cur_y]} ]; then
 103                             tentative[$test_x,$cur_y]=$new_cost
 104                         fi
 105                     else
 106                         tentative[$test_x,$cur_y]=$new_cost
 107                     fi
 108                 fi
 109             fi
 110         done
 111         for test_y in $((cur_y-1)) $((cur_y+1)); do
 112             if [ "${map[$cur_x,$test_y]+abc}" ] && [[ "${map[$cur_x,$test_y]}" =~ [\.O] ]]; then
 113                 if [ ! "${lowest_cost[$cur_x,$test_y]+abc}" ]; then
 114                     new_cost=${lowest_cost[$cur_x,$cur_y]}
 115                     ((new_cost+=1)) # always 1 step from where we were previously
 116                     if [ "${tentative[$cur_x,$test_y]+abc}" ]; then
 117                         if [ $new_cost -lt ${tentative[$cur_x,$test_y]} ]; then
 118                             tentative[$cur_x,$test_y]=$new_cost
 119                         fi
 120                     else
 121                         tentative[$cur_x,$test_y]=$new_cost
 122                     fi
 123                 fi
 124             fi
 125         done
 126
 127         # find the new lowest tentative
 128         new_location=""
 129         new_value=-1
 130
 131         for location in "${!tentative[@]}"; do
 132             if [ -z "$new_location" ]; then
 133                 new_location=$location
 134                 new_value=${tentative[$location]}
 135             elif [ ${tentative[$location]} -lt $new_value ]; then
 136                 new_location=$location
 137                 new_value=${tentative[$location]}
 138             fi
 139         done
 140
 141         if [ -z "$new_location" ]; then
 142             break
 143         fi
 144         cur_x=${new_location%,*}
 145         cur_y=${new_location#*,}
 146     done
 147     echo -e "\rProgress: 100%"
 148
 149     echo "Lowest route cost: ${lowest_cost[${oxygen_location[0]},${oxygen_location[1]}]}"
 150 }
 151
 152 # fill the room with oxygen, this could take a few iterations
 153 oxygen_fill() {
 154     rounds=0
 155     declare -A oxygen_locations=( [${oxygen_location[0]},${oxygen_location[1]}]=0 )
 156     declare -a spread_points=( "${oxygen_location[0]},${oxygen_location[1]}" )
 157     declare -a new_spread_points=()
 158
 159     while [ "${#spread_points[@]}" -gt 0 ]; do
 160         ((rounds+=1))
 161         for spread_point in "${spread_points[@]}"; do
 162             # check round the point, left, right, up and down, and if they haven't already got O
 163             # add them to the oxygen_locations, and the new_spread_points, if they're on the map
 164             spread_x=${spread_point%,*}
 165             spread_y=${spread_point#*,}
 166             for test_x in $((spread_x-1)) $((spread_x+1)); do
 167                 if [ "${map[$test_x,$spread_y]+abc}" ]; then
 168                     if [ "${map[$test_x,$spread_y]}" == "." ]; then
 169                         if [ ! ${oxygen_locations[$test_x,$spread_y]+abc} ]; then
 170                             oxygen_locations[$test_x,$spread_y]=$rounds
 171                             new_spread_points+=( "$test_x,$spread_y" )
 172                         fi
 173                     fi
 174                 fi
 175             done
 176             for test_y in $((spread_y-1)) $((spread_y+1)); do
 177                 if [ "${map[$spread_x,$test_y]+abc}" ]; then
 178                     if [ "${map[$spread_x,$test_y]}" == "." ]; then
 179                         if [ ! "${oxygen_locations[$spread_x,$test_y]+abc}" ]; then
 180                             oxygen_locations[$spread_x,$test_y]=$rounds
 181                             new_spread_points+=( "$spread_x,$test_y" )
 182                         fi
 183                     fi
 184                 fi
 185             done
 186         done
 187         if [ ${#new_spread_points[@]} -eq 0 ]; then
 188             ((rounds-=1))
 189         fi
 190         unset spread_points
 191         declare -a spread_points=()
 192         for spread_point in "${new_spread_points[@]}"; do
 193             spread_points+=( "$spread_point" )
 194         done
 195         unset new_spread_points
 196         declare -a new_spread_points=()
 197     done
 198
 199     echo "It'd take $rounds minutes to fill the maze with oxygen"
 200 }
 201
 202 declare -a spinner=( '-' '\' '|' '/' )
 203 spinner_offset=0
 204
 205 update_spinner() {
 206     echo -ne "\r${spinner[$spinner_offset]}"
 207     ((spinner_offset+=1))
 208     if [ $spinner_offset -gt $((${#spinner[@]} - 1)) ]; then
 209         spinner_offset=0
 210     fi
 211 }
 212
 213 display_map() {
 214     echo "min_x $min_x max_x $max_x min_y $min_y max_y $max_y"
 215     for (( a=$max_y; a >= $min_y; a-- )); do
 216         for (( b=$min_x; b <= $max_x; b++ )); do
 217             marker=${map[$b,$a]:-" "}
 218             if [ $a -eq 0 ] && [ $b -eq 0 ]; then
 219                 marker="S"
 220             fi
 221             if [ $a -eq $cur_y ] && [ $b -eq $cur_x ]; then
 222                 marker="D"
 223             fi
 224             echo -n "$marker"
 225         done
 226         echo
 227     done
 228     echo
 229 }
 230
 231 while ps -p $comp_pid > /dev/null 2>/dev/null; do
 232     read -u $comp_stdout prompt
 233     if [ "$prompt" != "input:" ]; then
 234         echo_verbose "We has no input!"
 235         exit 2
 236     fi
 237     echo $cur_direction >&$comp_stdin
 238     new_x=$cur_x
 239     new_y=$cur_y
 240     case $cur_direction in
 241         ${directions["n"]})
 242             ((new_y+=1))
 243             if [ $new_y -gt $max_y ]; then
 244                 max_y=$new_y
 245             fi
 246             ;;
 247         ${directions["s"]})
 248             ((new_y-=1))
 249             if [ $new_y -lt $min_y ]; then
 250                 min_y=$new_y
 251             fi
 252             ;;
 253         ${directions["e"]})
 254             ((new_x+=1))
 255             if [ $new_x -gt $max_x ]; then
 256                 max_x=$new_x
 257             fi
 258             ;;
 259         ${directions["w"]})
 260             ((new_x-=1))
 261             if [ $new_x -lt $min_x ]; then
 262                 min_x=$new_x
 263             fi
 264             ;;
 265     esac
 266     echo_verbose "x: $cur_x, new_x: $new_x, y: $cur_y, new_y: $new_y, direction: ${direction_names[$cur_direction]}"
 267     read -u $comp_stdout status
 268     case $status in
 269         "0")
 270             echo_verbose "Hit a wall"
 271             map[$new_x,$new_y]="#"
 272             wall_change
 273             ;;
 274         "1")
 275             echo_verbose "Moved ${direction_names[$cur_direction]}"
 276             if [ ! ${map[$cur_x,$cur_y]+abc} ]; then
 277                 map[$cur_x,$cur_y]="."
 278             fi
 279             cur_x=$new_x
 280             cur_y=$new_y
 281             if [ $refind_home -eq 1 ] && [ $new_x -eq 0 ] && [ $new_y -eq 0 ]; then
 282                 break
 283             fi
 284             change_direction
 285             ;;
 286         "2")
 287             echo_verbose "Found oxygen system"
 288             map[$cur_x,$cur_y]="."
 289             map[$new_x,$new_y]="O"
 290             cur_x=$new_x
 291             cur_y=$new_y
 292             refind_home=1
 293             echo -ne '\r \r'
 294             display_map
 295             oxygen_location=( $cur_x $cur_y )
 296             ;;
 297         *)
 298             echo_verbose "Weird response '$status'"
 299             ;;
 300     esac
 301     update_spinner
 302 done
 303
 304 echo -ne '\r \r'
 305 display_map
 306
 307 echo "Calculating best route."
 308
 309 calc_best_route
 310 oxygen_fill
 311
 312 echo 0 >&$comp_stdin