Day 12

[advent-of-code-2021.git] / day12 / pathfinder.sh

diff --git a/day12/pathfinder.sh b/day12/pathfinder.sh
new file mode 100755 (executable)
index 0000000..d93d996
--- /dev/null
+++ b/day12/pathfinder.sh
@@ -0,0 +1,78 @@
+#!/bin/bash
+
+set -u
+
+filename="${1:-small-example-p1_10.txt}"
+
+exec 3<"$filename"
+
+declare -A links
+
+while read -u 3 line; do
+    a=${line%-*}
+    b=${line#*-}
+
+    # we actually want it to go both ways, so we'll
+    # do that
+    if [ "${links[$a]+abc}" ]; then
+        links[$a]+=" $b"
+    else
+        links[$a]=$b
+    fi
+
+    if [ "${links[$b]+abc}" ]; then
+        links[$b]+=" $a"
+    else
+        links[$b]=$a
+    fi
+done
+
+declare -A paths
+
+do_path() {
+    local point=$1
+    shift
+    local -a previous_points=("$@")
+    local -a new_previous_path=()
+    local path
+
+    local -A __previous_points
+
+    for temp_point in "${previous_points[@]}"; do
+        __previous_points[$temp_point]=1
+    done
+
+    path="${previous_points[@]}"
+
+    if [ "${point}" == "${point,,}" ]; then
+        # if it's lower case, and we've already been there
+        # return
+        if [ "${__previous_points[$point]+abc}" ]; then
+            return 0
+        fi
+    fi
+
+    if [ "${point}" == "end" ]; then
+        path="$path $point"
+        if [ ! "${paths[$path]+abc}" ]; then
+            paths["$path"]=1
+        fi
+    else
+        new_previous_path=("${previous_points[@]}")
+        new_previous_path+=($point)
+        for new_point in ${links[$point]}; do
+            do_path $new_point "${new_previous_path[@]}"
+        done
+    fi
+}
+
+# start at start and then work through all possible paths
+for thing in ${links["start"]}; do
+    do_path $thing start
+done
+
+for path in "${!paths[@]}"; do
+    echo "Got path: $path"
+done
+
+echo "Total paths: ${#paths[@]}"