From: Brett Parker Date: Tue, 15 Dec 2020 10:05:17 +0000 (+0000) Subject: Day 15 - p2 is brute force, there must be a nicer algorithm that I can't see X-Git-Url: https://git.sommitrealweird.co.uk/advent-of-code-2020.git/commitdiff_plain/17e572f7ac5fde17481f218f91d2d002d7d14f95 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 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 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 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 index 0000000..c84ffe7 --- /dev/null +++ b/day15/p1_436.txt @@ -0,0 +1 @@ +0,3,6