X-Git-Url: https://git.sommitrealweird.co.uk/advent-of-code-2019.git/blobdiff_plain/09b6a3fd0fae26e58acfcfb024ab535829651a9d..f14e299af2b72a96621361be9d5ef6fdf1b7d4bc:/day15/run.sh

diff --git a/day15/run.sh b/day15/run.sh
new file mode 100755
index 0000000..bfb8d2d
--- /dev/null
+++ b/day15/run.sh
@@ -0,0 +1,312 @@
+#!/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