day3/wires.sh

   1 #!/bin/bash
   2
   3 set -u
   4 set -e
   5
   6 # these wires should give 6
   7 #wire_1=(R8 U5 L5 D3)
   8 #wire_2=(U7 R6 D4 L4)
   9
  10 # these wires should get 159
  11 #wire_1=(R75 D30 R83 U83 L12 D49 R71 U7 L72)
  12 #wire_2=(U62 R66 U55 R34 D71 R55 D58 R83)
  13
  14 # these wires should get 135
  15 wire_1=(R98 U47 R26 D63 R33 U87 L62 D20 R33 U53 R51)
  16 wire_2=(U98 R91 D20 R16 D67 R40 U7 R15 U6 R7)
  17
  18 # read in data from file instead
  19 #exec 3<input.txt
  20 #IFS="," read -u 3 -a wire_1
  21 #IFS="," read -u 3 -a wire_2
  22
  23 get_min_max() {
  24     local -n wire=$1
  25     horz_min=0
  26     horz_max=0
  27     vert_min=0
  28     vert_max=0
  29     cur_horz=0
  30     cur_vert=0
  31     for instruction in "${wire[@]}"; do
  32         direction=${instruction:0:1}
  33         amount=${instruction:1}
  34         case $direction in
  35             U)
  36                 cur_vert=$((cur_vert+$amount))
  37                 if [ $cur_vert -gt $vert_max ]; then
  38                     vert_max=$cur_vert
  39                 fi
  40                 ;;
  41             D)
  42                 cur_vert=$((cur_vert-$amount))
  43                 if [ $cur_vert -lt $vert_min ]; then
  44                     vert_min=$cur_vert
  45                 fi
  46                 ;;
  47             R)
  48                 cur_horz=$((cur_horz+$amount))
  49                 if [ $cur_horz -gt $horz_max ]; then
  50                     horz_max=$cur_horz
  51                 fi
  52                 ;;
  53             L)
  54                 cur_horz=$((cur_horz-$amount))
  55                 if [ $cur_horz -lt $horz_min ]; then
  56                     horz_min=$cur_horz
  57                 fi
  58                 ;;
  59         esac
  60     done
  61
  62     echo "$horz_min,$horz_max,$vert_min,$vert_max"
  63 }
  64
  65 trace_wire() {
  66     local -n w=$1
  67     local -n b=$2
  68     local -n c=$3
  69     min_left=$4
  70     cur_vert=0
  71     cur_horz=0
  72     moved=0
  73     last_replace_char="-"
  74
  75     for operation in "${w[@]}"; do
  76         direction=${operation:0:1}
  77         amount=${operation:1}
  78         case $direction in
  79             U)
  80                 operator=+
  81                 ;;
  82             D)
  83                 operator=-
  84                 ;;
  85             L)
  86                 operator=-
  87                 ;;
  88             R)
  89                 operator=+
  90                 ;;
  91         esac
  92
  93         case $direction in
  94             U|D)
  95                 last_replace_char="|"
  96                 offset=$((0-$min_left))
  97                 offset=$((offset+$cur_horz))
  98                 for (( moved=1; moved <= $amount; moved++ )); do
  99                     cur_vert=$((cur_vert${operator}1))
 100                     cur_line=${b[$cur_vert]}
 101                     cur_char=${cur_line:$offset:1}
 102                     replace_char="|"
 103                     if [ $cur_char = "-" ] || [ $cur_char = "|" ]; then
 104                         replace_char="X"
 105                         c+=($cur_horz,$cur_vert)
 106                     fi
 107                     if [ $moved -eq $amount ]; then
 108                         replace_char="+"
 109                     fi
 110                     if [ $cur_vert -eq 0 ] && [ $cur_horz -eq 0 ]; then
 111                         replace_char='o'
 112                     fi
 113                     new_line="${cur_line:0:$((offset))}${replace_char}${cur_line:$((offset+1))}"
 114                     b[$cur_vert]=$new_line
 115                 done
 116                 ;;
 117             L|R)
 118                 last_replace_char="-"
 119                 # this could change multiple characters in the line
 120                 for (( moved=1; moved <= $amount; moved++ )); do
 121                     cur_horz=$((cur_horz${operator}1))
 122                     offset=$((0-$min_left))
 123                     offset=$((offset+$cur_horz))
 124                     cur_line=${b[$cur_vert]}
 125                     cur_char=${cur_line:$offset:1}
 126                     replace_char="-"
 127                     if [ $cur_char = "-" ] || [ $cur_char = "|" ]; then
 128                         replace_char="X"
 129                         c+=($cur_horz,$cur_vert)
 130                     fi
 131                     if [ $moved -eq $amount ]; then
 132                         replace_char="+"
 133                     fi
 134                     if [ $cur_vert -eq 0 ] && [ $cur_horz -eq 0 ]; then
 135                         replace_char='o'
 136                     fi
 137                     new_line="${cur_line:0:$((offset))}${replace_char}${cur_line:$((offset+1))}"
 138                     b[$cur_vert]=$new_line
 139                 done
 140                 ;;
 141         esac
 142     done
 143
 144     cur_line=${b[$cur_vert]}
 145     offset=$((0-$min_left))
 146     offset=$((offset+$cur_horz))
 147     if [ ${cur_line:$offset:1} != 'X' ]; then
 148         new_line="${cur_line:0:$((offset))}${last_replace_char}${cur_line:$((offset+1))}"
 149         b[$cur_vert]=$new_line
 150     fi
 151     echo
 152 }
 153
 154 make_board() {
 155     local -n mm=$1
 156     local -n b=$2
 157
 158     min_horz=${mm[0]}
 159     if [ $min_horz -gt 0 ]; then
 160         min_horz=0
 161     fi
 162
 163     min_vert=${mm[2]}
 164     if [ $min_vert -gt 0 ]; then
 165         min_vert=0
 166     fi
 167
 168     max_horz=${mm[1]}
 169     total_horz=$(($max_horz - $min_horz))
 170
 171     max_vert=${mm[3]}
 172
 173     cur_vert=${min_vert}
 174     blank_string=$(printf ".%.0s" $(eval echo '{0..'$total_horz'}'))
 175     while [[ $cur_vert -le ${max_vert} ]]; do
 176         if [[ $cur_vert -eq 0 ]]; then
 177             offset=$((0-${mm[0]}))
 178             line="${blank_string:0:$offset}o${blank_string:$((offset+1))}"
 179             b[$cur_vert]=$line
 180         else
 181             b[$cur_vert]=$blank_string
 182         fi
 183         cur_vert=$((cur_vert+1))
 184     done
 185 }
 186
 187 echo "Getting board boundaries"
 188 IFS="," read -a min_max < <(get_min_max wire_1)
 189 IFS="," read -a min_max_2 < <(get_min_max wire_2)
 190
 191 # do the minimums first
 192 for pos in 0 2; do
 193     if [ ${min_max[$pos]} -gt ${min_max_2[$pos]} ]; then
 194         min_max[$pos]=${min_max_2[$pos]}
 195     fi
 196 done
 197
 198 # now the maximums
 199 for pos in 1 3; do
 200     if [ ${min_max[$pos]} -lt ${min_max_2[$pos]} ]; then
 201         min_max[$pos]=${min_max_2[$pos]}
 202     fi
 203 done
 204
 205 echo "  ${min_max[@]}"
 206
 207 # we now know exactly how big the grid is, which is handy, as we'll use it to do offsets
 208 declare -A board
 209 declare -a cross_wires
 210 echo "Building board"
 211 make_board min_max board
 212 echo "Tracing first wire"
 213 trace_wire wire_1 board cross_wires ${min_max[0]}
 214 echo "Tracing second wire"
 215 trace_wire wire_2 board cross_wires ${min_max[0]}
 216
 217 for (( a=${min_max[3]}; a>=${min_max[2]}; a-- )); do
 218     echo ${board[$a]}
 219 done
 220
 221 echo "Wires cross at:"
 222 min_distance=-1
 223 for cross in "${cross_wires[@]}"; do
 224     echo "  $cross"
 225     horz=${cross%,*}
 226     horz=${horz//-/}
 227     vert=${cross#*,}
 228     vert=${vert//-/}
 229     distance=$((horz+$vert))
 230     if [ $min_distance -lt 0 ] || [ $min_distance -gt $distance ]; then
 231         min_distance=$distance
 232     fi
 233 done
 234
 235 echo Min distance: $min_distance