Day 12 2019 before part2 finished running

diff --git a/day12/example-output.txt b/day12/example-output.txt
new file mode 100644 (file)
index 0000000..75c0672
--- /dev/null
+++ b/day12/example-output.txt
@@ -0,0 +1,65 @@
+After 0 steps:
+pos=<x=-1, y=  0, z= 2>, vel=<x= 0, y= 0, z= 0>
+pos=<x= 2, y=-10, z=-7>, vel=<x= 0, y= 0, z= 0>
+pos=<x= 4, y= -8, z= 8>, vel=<x= 0, y= 0, z= 0>
+pos=<x= 3, y=  5, z=-1>, vel=<x= 0, y= 0, z= 0>
+
+After 1 step:
+pos=<x= 2, y=-1, z= 1>, vel=<x= 3, y=-1, z=-1>
+pos=<x= 3, y=-7, z=-4>, vel=<x= 1, y= 3, z= 3>
+pos=<x= 1, y=-7, z= 5>, vel=<x=-3, y= 1, z=-3>
+pos=<x= 2, y= 2, z= 0>, vel=<x=-1, y=-3, z= 1>
+
+After 2 steps:
+pos=<x= 5, y=-3, z=-1>, vel=<x= 3, y=-2, z=-2>
+pos=<x= 1, y=-2, z= 2>, vel=<x=-2, y= 5, z= 6>
+pos=<x= 1, y=-4, z=-1>, vel=<x= 0, y= 3, z=-6>
+pos=<x= 1, y=-4, z= 2>, vel=<x=-1, y=-6, z= 2>
+
+After 3 steps:
+pos=<x= 5, y=-6, z=-1>, vel=<x= 0, y=-3, z= 0>
+pos=<x= 0, y= 0, z= 6>, vel=<x=-1, y= 2, z= 4>
+pos=<x= 2, y= 1, z=-5>, vel=<x= 1, y= 5, z=-4>
+pos=<x= 1, y=-8, z= 2>, vel=<x= 0, y=-4, z= 0>
+
+After 4 steps:
+pos=<x= 2, y=-8, z= 0>, vel=<x=-3, y=-2, z= 1>
+pos=<x= 2, y= 1, z= 7>, vel=<x= 2, y= 1, z= 1>
+pos=<x= 2, y= 3, z=-6>, vel=<x= 0, y= 2, z=-1>
+pos=<x= 2, y=-9, z= 1>, vel=<x= 1, y=-1, z=-1>
+
+After 5 steps:
+pos=<x=-1, y=-9, z= 2>, vel=<x=-3, y=-1, z= 2>
+pos=<x= 4, y= 1, z= 5>, vel=<x= 2, y= 0, z=-2>
+pos=<x= 2, y= 2, z=-4>, vel=<x= 0, y=-1, z= 2>
+pos=<x= 3, y=-7, z=-1>, vel=<x= 1, y= 2, z=-2>
+
+After 6 steps:
+pos=<x=-1, y=-7, z= 3>, vel=<x= 0, y= 2, z= 1>
+pos=<x= 3, y= 0, z= 0>, vel=<x=-1, y=-1, z=-5>
+pos=<x= 3, y=-2, z= 1>, vel=<x= 1, y=-4, z= 5>
+pos=<x= 3, y=-4, z=-2>, vel=<x= 0, y= 3, z=-1>
+
+After 7 steps:
+pos=<x= 2, y=-2, z= 1>, vel=<x= 3, y= 5, z=-2>
+pos=<x= 1, y=-4, z=-4>, vel=<x=-2, y=-4, z=-4>
+pos=<x= 3, y=-7, z= 5>, vel=<x= 0, y=-5, z= 4>
+pos=<x= 2, y= 0, z= 0>, vel=<x=-1, y= 4, z= 2>
+
+After 8 steps:
+pos=<x= 5, y= 2, z=-2>, vel=<x= 3, y= 4, z=-3>
+pos=<x= 2, y=-7, z=-5>, vel=<x= 1, y=-3, z=-1>
+pos=<x= 0, y=-9, z= 6>, vel=<x=-3, y=-2, z= 1>
+pos=<x= 1, y= 1, z= 3>, vel=<x=-1, y= 1, z= 3>
+
+After 9 steps:
+pos=<x= 5, y= 3, z=-4>, vel=<x= 0, y= 1, z=-2>
+pos=<x= 2, y=-9, z=-3>, vel=<x= 0, y=-2, z= 2>
+pos=<x= 0, y=-8, z= 4>, vel=<x= 0, y= 1, z=-2>
+pos=<x= 1, y= 1, z= 5>, vel=<x= 0, y= 0, z= 2>
+
+After 10 steps:
+pos=<x= 2, y= 1, z=-3>, vel=<x=-3, y=-2, z= 1>
+pos=<x= 1, y=-8, z= 0>, vel=<x=-1, y= 1, z= 3>
+pos=<x= 3, y=-6, z= 1>, vel=<x= 3, y= 2, z=-3>
+pos=<x= 2, y= 0, z= 4>, vel=<x= 1, y=-1, z=-1>

diff --git a/day12/example.txt b/day12/example.txt
new file mode 100644 (file)
index 0000000..89cc805
--- /dev/null
+++ b/day12/example.txt
@@ -0,0 +1,4 @@
+<x=-1, y=0, z=2>
+<x=2, y=-10, z=-7>
+<x=4, y=-8, z=8>
+<x=3, y=5, z=-1>

diff --git a/day12/example2.txt b/day12/example2.txt
new file mode 100644 (file)
index 0000000..1078293
--- /dev/null
+++ b/day12/example2.txt
@@ -0,0 +1,4 @@
+<x=-8, y=-10, z=0>
+<x=5, y=5, z=10>
+<x=2, y=-7, z=3>
+<x=9, y=-8, z=-3>

diff --git a/day12/input.txt b/day12/input.txt
new file mode 100644 (file)
index 0000000..878c62d
--- /dev/null
+++ b/day12/input.txt
@@ -0,0 +1,4 @@
+<x=14, y=15, z=-2>
+<x=17, y=-3, z=4>
+<x=6, y=12, z=-13>
+<x=-2, y=10, z=-8>

diff --git a/day12/nbody.sh b/day12/nbody.sh
new file mode 100755 (executable)
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:
+    # <x=val, y=val, z=val>
+    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=<x=${moons[${a}_x]}, y=${moons[${a}_y]}, z=${moons[${a}_z]}>, "
+        echo "vel=<x=${moons[${a}_xv]}, y=${moons[${a}_yv]}, z=${moons[${a}_zv]}>"
+    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 (file)
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