From 4a5c20b059b7bb679c75feb38d77352a8597761f Mon Sep 17 00:00:00 2001 From: Brett Parker Date: Wed, 9 Dec 2020 21:33:05 +0000 Subject: [PATCH] Day 12 2019 before part2 finished running --- day12/example-output.txt | 65 ++++++++ day12/example.txt | 4 + day12/example2.txt | 4 + day12/input.txt | 4 + day12/nbody.sh | 310 +++++++++++++++++++++++++++++++++++++++ day12/notes.txt | 1 + 6 files changed, 388 insertions(+) create mode 100644 day12/example-output.txt create mode 100644 day12/example.txt create mode 100644 day12/example2.txt create mode 100644 day12/input.txt create mode 100755 day12/nbody.sh create mode 100644 day12/notes.txt diff --git a/day12/example-output.txt b/day12/example-output.txt new file mode 100644 index 0000000..75c0672 --- /dev/null +++ b/day12/example-output.txt @@ -0,0 +1,65 @@ +After 0 steps: +pos=, vel= +pos=, vel= +pos=, vel= +pos=, vel= + +After 1 step: +pos=, vel= +pos=, vel= +pos=, vel= +pos=, vel= + +After 2 steps: +pos=, vel= +pos=, vel= +pos=, vel= +pos=, vel= + +After 3 steps: +pos=, vel= +pos=, vel= +pos=, vel= +pos=, vel= + +After 4 steps: +pos=, vel= +pos=, vel= +pos=, vel= +pos=, vel= + +After 5 steps: +pos=, vel= +pos=, vel= +pos=, vel= +pos=, vel= + +After 6 steps: +pos=, vel= +pos=, vel= +pos=, vel= +pos=, vel= + +After 7 steps: +pos=, vel= +pos=, vel= +pos=, vel= +pos=, vel= + +After 8 steps: +pos=, vel= +pos=, vel= +pos=, vel= +pos=, vel= + +After 9 steps: +pos=, vel= +pos=, vel= +pos=, vel= +pos=, vel= + +After 10 steps: +pos=, vel= +pos=, vel= +pos=, vel= +pos=, vel= diff --git a/day12/example.txt b/day12/example.txt new file mode 100644 index 0000000..89cc805 --- /dev/null +++ b/day12/example.txt @@ -0,0 +1,4 @@ + + + + diff --git a/day12/example2.txt b/day12/example2.txt new file mode 100644 index 0000000..1078293 --- /dev/null +++ b/day12/example2.txt @@ -0,0 +1,4 @@ + + + + diff --git a/day12/input.txt b/day12/input.txt new file mode 100644 index 0000000..878c62d --- /dev/null +++ b/day12/input.txt @@ -0,0 +1,4 @@ + + + + diff --git a/day12/nbody.sh b/day12/nbody.sh new file mode 100755 index 0000000..4c1f804 --- /dev/null +++ b/day12/nbody.sh @@ -0,0 +1,310 @@ +#!/bin/bash + +set -u + +filename=${1:-example.txt} +steps=${2:-10} +display_steps=${3:-1} + +declare -A moons +moon_number=1 +moon_count=0 +declare -A states +declare -A cycles + +parse_line() { + # data per line is like this: + # + local line=$1 + + line=${line%>} + line=${line#<} + line=${line//, / } + + echo "$line" +} + +read_file() { + exec 3<$filename + declare -g -A moons + local IFS=$'\n' + local -a vals + local pair + local key + local val + + while read -u 3 line; do + IFS=" " + vals=( $(parse_line "$line") ) + IFS=$'\n' + for pair in "${vals[@]}"; do + key=${pair%=*} + val=${pair#*=} + moons["${moon_number}_${key}"]=$val + # also set the velocity of each to 0 + moons["${moon_number}_${key}v"]=0 + done + let moon_number+=1 + let moon_count+=1 + done + + add_states 0 +} + +apply_gravity() { + local a + local b + local key + local val1 + local val2 + for (( a=1; a<=$moon_count; a++ )); do + for (( b=1; b<=$moon_count; b++ )); do + if [ $a -eq $b ]; then + continue + fi + # to make our brain not hurt we only do + # the calculation for the velocity on $a + # it's not as efficient as doing both $a + # and $b, but that also then needs a way + # to skip already done pair calcs + for key in x y z; do + val1=${moons[${a}_${key}]} + val2=${moons[${b}_${key}]} + if [ $val1 -gt $val2 ]; then + moons[${a}_${key}v]=$((${moons[${a}_${key}v]}-1)) + elif [ $val1 -lt $val2 ]; then + moons[${a}_${key}v]=$((${moons[${a}_${key}v]}+1)) + fi + done + done + done +} + +apply_velocity() { + local a + local key + + for (( a=1; a<=$moon_count; a++ )); do + for key in x y z; do + let moons[${a}_${key}]+=${moons[${a}_${key}v]} + done + done +} + +display_moons_gravity_and_velocity() { + for (( a=1; a<=$moon_count; a++ )); do + echo -n "pos=, " + echo "vel=" + done +} + +get_energy() { + local moon=$1 + local suffix=${2:-} + local temp + local -a vals + local val + local sum=0 + + temp="${moons[${moon}_x${suffix}]} ${moons[${moon}_y${suffix}]} ${moons[${moon}_z${suffix}]}" + temp=${temp//-} + vals=( $temp ) + for val in "${vals[@]}"; do + let sum+=$val + done + + echo $sum +} + +get_potential_energy() { + get_energy $1 +} + +get_kinetic_energy() { + get_energy $1 v +} + +add_states() { + local step=$1 + local -i got_states=0 + add_state $step x || got_states+=1 + add_state $step y || got_states+=1 + add_state $step z || got_states+=1 + + if [ $got_states -eq 3 ]; then + return 1 + fi +} + +add_state() { + local step=$1 + local key=$2 + local state= + + if [ ${cycles[$key]+a} ]; then + return 1 + fi + + state="$(get_state_string $key)$(get_state_string ${key}v)" + + if [ ${states[${key}_${state}]+a} ]; then + if [ ${states[${key}_${state}]} -eq 0 ]; then + cycles[$key]="$step" + return 1 + fi + fi + states["${key}_${state}"]=$step +} + +get_state_string() { + local key=$1 + local state="|" + local moon + + for (( moon=1; moon<=$moon_count; moon++ )); do + state+="${moons[${moon}_${key}]}|" + done + + echo "$state" +} + +get_lcm() { + local -a values=( $@ ) + local -A factor_counts + local -a factors + local factor + local value + local power + local -i lcm=1 + + for value in ${values[@]}; do + local -a factors + factors=( $(get_prime_factors $value) ) + local -A temp_factor_counts + for factor in ${factors[@]}; do + if [ ${temp_factor_counts[$factor]+a} ]; then + temp_factor_counts[$factor]=$((${temp_factor_counts[$factor]}+1)) + else + temp_factor_counts[$factor]=1 + fi + done + # loop through temp_factor_counts before we clear it + for factor in ${!temp_factor_counts[@]}; do + if [ ${factor_counts[$factor]+a} ]; then + if [ ${temp_factor_counts[$factor]} -gt ${factor_counts[$factor]} ]; then + factor_counts[$factor]=${temp_factor_counts[$factor]} + fi + else + factor_counts[$factor]=${temp_factor_counts[$factor]} + fi + done + unset temp_factor_counts + unset factors + done + + for factor in "${!factor_counts[@]}"; do + power=${factor_counts[$factor]} + value=$(($factor**$power)) + let lcm=$lcm*$value + done + + echo $lcm +} + +get_prime_factors() { + local val=$1 + local -a factors + + # start with the biggest prime, work down until we hit a prime + for (( a=$((${#primes[@]}-1)); a>=0; a-- )); do + prime=${primes[$a]} + while [ $(( val % $prime )) -eq 0 ]; do + factors+=( $prime ) + val=$((val/$prime)) + done + if [ $val -eq 1 ]; then + break + fi + done + + echo "${factors[@]}" +} + +calculate_primes_required() { + local vals=( $@ ) + local highest=${vals[0]} + declare -g -a primes=( 2 ) + + # get highest val + for val in ${vals[@]}; do + if [ $val -gt $highest ]; then + highest=$val + fi + done + + for (( a=3; a<=$highest; a++ )); do + for prime in ${primes[@]}; do + if [ $((a%prime)) -eq 0 ]; then + continue 2 + fi + done + primes+=( $a ) + done +} + +read_file + +echo Step 0 +display_moons_gravity_and_velocity +echo + +for (( step=1; step<=$steps; step++ )); do + apply_gravity + apply_velocity + add_states $step + if [ $((step % $display_steps)) -eq 0 ]; then + echo Step $step + display_moons_gravity_and_velocity + echo + fi +done + +# get the kinetic and potential energy for each moon +# and the whole system +total_energy=0 +for (( moon=1; moon<=$moon_count; moon++ )); do + pe=$(get_potential_energy $moon) + ke=$(get_kinetic_energy $moon) + te=$(($pe*$ke)) + let total_energy+=$te + echo "Moon $moon: PE=$pe, KE=$ke, TE=$te" +done + +echo "System total energy: $total_energy" + +echo "Looking for duplicate state, this could take a while" +spinner_parts=( '-' '/' '|' '\' ) + +printf '\r%s' ${spinner_parts[$(($step%4))]} + +keep_going=1 +matched_state=0 +while [ $keep_going -eq 1 ]; do + printf '\r%s' ${spinner_parts[$(($step%4))]} + apply_gravity + apply_velocity + if ! add_states $step; then + keep_going=0 + fi + let step+=1 +done + +printf '\r \r' +for key in ${!cycles[@]}; do + echo "${key} cycles every ${cycles[$key]} steps" +done +echo "Calculating primes..." +calculate_primes_required "${cycles[@]}" +echo "Calculating repeat cycle..." +repeat_cycle="$(get_lcm ${cycles[@]})" +echo "Steps to get to a repeat: $repeat_cycle" diff --git a/day12/notes.txt b/day12/notes.txt new file mode 100644 index 0000000..6a3f3e6 --- /dev/null +++ b/day12/notes.txt @@ -0,0 +1 @@ +Annoyingly, we can't just use bash, we run out of integer space - throw lcm at the lcm function of apcalc instead -- 2.30.2