Day 12

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

diff --git a/day12/pathfinder2.sh b/day12/pathfinder2.sh
new file mode 100755 (executable)
index 0000000..dd66e04
--- /dev/null
+++ b/day12/pathfinder2.sh
@@ -0,0 +1,109 @@
+#!/bin/bash
+
+set -u
+
+filename="${1:-small-example-p2_36.txt}"
+
+exec 3<"$filename"
+
+declare -A links
+
+while read -u 3 line; do
+    a=${line%-*}
+    b=${line#*-}
+
+    if [ "$a" == "start" ] || [ "$b" == "end" ]; then
+        if [ "${links[$a]+abc}" ]; then
+            links[$a]+=" $b"
+        else
+            links[$a]="$b"
+        fi
+        continue
+    fi
+
+    if [ "$a" == "end" ] || [ "$b" == "start" ]; then
+        if [ "${links[$b]+abc}" ]; then
+            links[$b]+=" $a"
+        else
+            links[$b]="$a"
+        fi
+        continue
+    fi
+
+    # 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 [ "$a" != "start" ]; then
+        if [ "${links[$b]+abc}" ]; then
+            links[$b]+=" $a"
+        else
+            links[$b]="$a"
+        fi
+    fi
+done
+
+declare -A paths=()
+
+do_path() {
+    local point=$1
+    shift
+    local -a previous_points=("$@")
+    local -a new_previous_path=()
+    local path
+
+    local have_dupe_lowercase=0
+
+    local -A __previous_points
+
+    for temp_point in "${previous_points[@]}"; do
+        if [ "${__previous_points[$temp_point]+abc}" ]; then
+            ((__previous_points[$temp_point]+=1))
+            if [ "${temp_point}" == "${temp_point,,}" ]; then
+                # at least 2 of this point
+                have_dupe_lowercase=1
+            fi
+        else
+            __previous_points[$temp_point]=1
+        fi
+    done
+
+    path="${previous_points[@]}"
+
+    if [ "${point}" == "${point,,}" ]; then
+        if [ "${__previous_points[$point]+abc}" ]; then
+            if [ $have_dupe_lowercase -eq 1 ]; then
+                # can only go through one lowercase point twice
+                return 0
+            fi
+        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[@]}"