day12/pathfinder.sh

   1 #!/bin/bash
   2
   3 set -u
   4
   5 filename="${1:-small-example-p1_10.txt}"
   6
   7 exec 3<"$filename"
   8
   9 declare -A links
  10
  11 while read -u 3 line; do
  12     a=${line%-*}
  13     b=${line#*-}
  14
  15     # we actually want it to go both ways, so we'll
  16     # do that
  17     if [ "${links[$a]+abc}" ]; then
  18         links[$a]+=" $b"
  19     else
  20         links[$a]=$b
  21     fi
  22
  23     if [ "${links[$b]+abc}" ]; then
  24         links[$b]+=" $a"
  25     else
  26         links[$b]=$a
  27     fi
  28 done
  29
  30 declare -A paths
  31
  32 do_path() {
  33     local point=$1
  34     shift
  35     local -a previous_points=("$@")
  36     local -a new_previous_path=()
  37     local path
  38
  39     local -A __previous_points
  40
  41     for temp_point in "${previous_points[@]}"; do
  42         __previous_points[$temp_point]=1
  43     done
  44
  45     path="${previous_points[@]}"
  46
  47     if [ "${point}" == "${point,,}" ]; then
  48         # if it's lower case, and we've already been there
  49         # return
  50         if [ "${__previous_points[$point]+abc}" ]; then
  51             return 0
  52         fi
  53     fi
  54
  55     if [ "${point}" == "end" ]; then
  56         path="$path $point"
  57         if [ ! "${paths[$path]+abc}" ]; then
  58             paths["$path"]=1
  59         fi
  60     else
  61         new_previous_path=("${previous_points[@]}")
  62         new_previous_path+=($point)
  63         for new_point in ${links[$point]}; do
  64             do_path $new_point "${new_previous_path[@]}"
  65         done
  66     fi
  67 }
  68
  69 # start at start and then work through all possible paths
  70 for thing in ${links["start"]}; do
  71     do_path $thing start
  72 done
  73
  74 for path in "${!paths[@]}"; do
  75     echo "Got path: $path"
  76 done
  77
  78 echo "Total paths: ${#paths[@]}"