Day 15 - p2 is brute force, there must be a nicer algorithm that I can't see

diff --git a/day15/input.txt b/day15/input.txt
new file mode 100644 (file)
index 0000000..1f8b084
--- /dev/null
+++ b/day15/input.txt
@@ -0,0 +1 @@
+2,0,1,7,4,14,18

diff --git a/day15/memory.sh b/day15/memory.sh
new file mode 100755 (executable)
index 0000000..4f16b3b
--- /dev/null
+++ b/day15/memory.sh
@@ -0,0 +1,78 @@
+#!/bin/bash
+
+set -u
+
+read_file() {
+    filename="$1"
+    local IFS=","
+    exec 3<"$filename"
+    read -u 3 -a data
+}
+
+get_answer() {
+    local number=$1
+    local count=$2
+    if [ ${lastseen[$number]+a} ]; then
+        answers[$count]=$((count-${lastseen[$number]}-1))
+    else
+        answers[$count]=0
+    fi
+}
+
+do_nothing() {
+    return
+}
+
+error_echo() {
+    echo "$@" >&2
+}
+
+DEBUG="${DEBUG:-}"
+debug_func=do_nothing
+
+if [ -n "$DEBUG" ]; then
+    debug_func="error_echo"
+fi
+
+filename="${1:-p1_436.txt}"
+
+read_file "$filename"
+
+declare -A lastseen
+declare -a answers
+
+current_answer=-1
+last_answer=-1
+count=0
+
+for number in ${data[@]}; do
+    count=$((count+1))
+    last_answer=$current_answer
+    if [ $last_answer -ge 0 ]; then
+        lastseen[$last_answer]=$((count-1))
+    fi
+    answers[$count]=$number
+    current_answer=$number
+done
+
+while [ $count -lt 2020 ]; do
+    count=$((count+1))
+    get_answer $current_answer $count
+    last_answer=$current_answer
+    lastseen[$last_answer]=$((count-1))
+    current_answer=${answers[$count]}
+    $debug_func "$count: ${answers[$count]}"
+done
+
+echo "Part 1: ${answers[$count]}"
+
+while [ $count -lt 30000000 ]; do
+    count=$((count+1))
+    get_answer $current_answer $count
+    last_answer=$current_answer
+    lastseen[$last_answer]=$((count-1))
+    current_answer=${answers[$count]}
+    $debug_func "$count: ${answers[$count]}"
+done
+
+echo "Part 2: ${answers[$count]}"

diff --git a/day15/p1_1.txt b/day15/p1_1.txt
new file mode 100644 (file)
index 0000000..12d2be1
--- /dev/null
+++ b/day15/p1_1.txt
@@ -0,0 +1 @@
+1,3,2

diff --git a/day15/p1_436.txt b/day15/p1_436.txt
new file mode 100644 (file)
index 0000000..c84ffe7
--- /dev/null
+++ b/day15/p1_436.txt
@@ -0,0 +1 @@
+0,3,6