day12/pathfinder2.sh

   1 #!/bin/bash
   2
   3 set -u
   4
   5 filename="${1:-small-example-p2_36.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     if [ "$a" == "start" ] || [ "$b" == "end" ]; then
  16         if [ "${links[$a]+abc}" ]; then
  17             links[$a]+=" $b"
  18         else
  19             links[$a]="$b"
  20         fi
  21         continue
  22     fi
  23
  24     if [ "$a" == "end" ] || [ "$b" == "start" ]; then
  25         if [ "${links[$b]+abc}" ]; then
  26             links[$b]+=" $a"
  27         else
  28             links[$b]="$a"
  29         fi
  30         continue
  31     fi
  32
  33     # we actually want it to go both ways, so we'll
  34     # do that
  35     if [ "${links[$a]+abc}" ]; then
  36         links[$a]+=" $b"
  37     else
  38         links[$a]="$b"
  39     fi
  40
  41     if [ "$a" != "start" ]; then
  42         if [ "${links[$b]+abc}" ]; then
  43             links[$b]+=" $a"
  44         else
  45             links[$b]="$a"
  46         fi
  47     fi
  48 done
  49
  50 declare -A paths=()
  51
  52 do_path() {
  53     local point=$1
  54     shift
  55     local -a previous_points=("$@")
  56     local -a new_previous_path=()
  57     local path
  58
  59     local have_dupe_lowercase=0
  60
  61     local -A __previous_points
  62
  63     for temp_point in "${previous_points[@]}"; do
  64         if [ "${__previous_points[$temp_point]+abc}" ]; then
  65             ((__previous_points[$temp_point]+=1))
  66             if [ "${temp_point}" == "${temp_point,,}" ]; then
  67                 # at least 2 of this point
  68                 have_dupe_lowercase=1
  69             fi
  70         else
  71             __previous_points[$temp_point]=1
  72         fi
  73     done
  74
  75     path="${previous_points[@]}"
  76
  77     if [ "${point}" == "${point,,}" ]; then
  78         if [ "${__previous_points[$point]+abc}" ]; then
  79             if [ $have_dupe_lowercase -eq 1 ]; then
  80                 # can only go through one lowercase point twice
  81                 return 0
  82             fi
  83         fi
  84     fi
  85
  86     if [ "${point}" == "end" ]; then
  87         path="$path $point"
  88         if [ ! "${paths[$path]+abc}" ]; then
  89             paths["$path"]=1
  90         fi
  91     else
  92         new_previous_path=("${previous_points[@]}")
  93         new_previous_path+=($point)
  94         for new_point in ${links[$point]}; do
  95             do_path $new_point "${new_previous_path[@]}"
  96         done
  97     fi
  98 }
  99
 100 # start at start and then work through all possible paths
 101 for thing in ${links["start"]}; do
 102     do_path $thing start
 103 done
 104
 105 for path in "${!paths[@]}"; do
 106     echo "Got path: $path"
 107 done
 108
 109 echo "Total paths: ${#paths[@]}"