--- /dev/null
+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>
--- /dev/null
+#!/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"
projects / advent-of-code-2019.git / commitdiff