day12/nbody.sh

   1 #!/bin/bash
   2
   3 set -u
   4
   5 filename=${1:-example.txt}
   6 steps=${2:-10}
   7 display_steps=${3:-1}
   8
   9 declare -A moons
  10 moon_number=1
  11 moon_count=0
  12 declare -A states
  13 declare -A cycles
  14
  15 parse_line() {
  16     # data per line is like this:
  17     # <x=val, y=val, z=val>
  18     local line=$1
  19
  20     line=${line%>}
  21     line=${line#<}
  22     line=${line//, / }
  23
  24     echo "$line"
  25 }
  26
  27 read_file() {
  28     exec 3<$filename
  29     declare -g -A moons
  30     local IFS=$'\n'
  31     local -a vals
  32     local pair
  33     local key
  34     local val
  35
  36     while read -u 3 line; do
  37         IFS=" "
  38         vals=( $(parse_line "$line") )
  39         IFS=$'\n'
  40         for pair in "${vals[@]}"; do
  41             key=${pair%=*}
  42             val=${pair#*=}
  43             moons["${moon_number}_${key}"]=$val
  44             # also set the velocity of each to 0
  45             moons["${moon_number}_${key}v"]=0
  46         done
  47         let moon_number+=1
  48         let moon_count+=1
  49     done
  50
  51     add_states 0
  52 }
  53
  54 apply_gravity() {
  55     local a
  56     local b
  57     local key
  58     local val1
  59     local val2
  60     for (( a=1; a<=$moon_count; a++ )); do
  61         for (( b=1; b<=$moon_count; b++ )); do
  62             if [ $a -eq $b ]; then
  63                 continue
  64             fi
  65             # to make our brain not hurt we only do
  66             # the calculation for the velocity on $a
  67             # it's not as efficient as doing both $a
  68             # and $b, but that also then needs a way
  69             # to skip already done pair calcs
  70             for key in x y z; do
  71                 val1=${moons[${a}_${key}]}
  72                 val2=${moons[${b}_${key}]}
  73                 if [ $val1 -gt $val2 ]; then
  74                     moons[${a}_${key}v]=$((${moons[${a}_${key}v]}-1))
  75                 elif [ $val1 -lt $val2 ]; then
  76                     moons[${a}_${key}v]=$((${moons[${a}_${key}v]}+1))
  77                 fi
  78             done
  79         done
  80     done
  81 }
  82
  83 apply_velocity() {
  84     local a
  85     local key
  86
  87     for (( a=1; a<=$moon_count; a++ )); do
  88         for key in x y z; do
  89             let moons[${a}_${key}]+=${moons[${a}_${key}v]}
  90         done
  91     done
  92 }
  93
  94 display_moons_gravity_and_velocity() {
  95     for (( a=1; a<=$moon_count; a++ )); do
  96         echo -n "pos=<x=${moons[${a}_x]}, y=${moons[${a}_y]}, z=${moons[${a}_z]}>, "
  97         echo "vel=<x=${moons[${a}_xv]}, y=${moons[${a}_yv]}, z=${moons[${a}_zv]}>"
  98     done
  99 }
 100
 101 get_energy() {
 102     local moon=$1
 103     local suffix=${2:-}
 104     local temp
 105     local -a vals
 106     local val
 107     local sum=0
 108
 109     temp="${moons[${moon}_x${suffix}]} ${moons[${moon}_y${suffix}]} ${moons[${moon}_z${suffix}]}"
 110     temp=${temp//-}
 111     vals=( $temp )
 112     for val in "${vals[@]}"; do
 113         let sum+=$val
 114     done
 115
 116     echo $sum
 117 }
 118
 119 get_potential_energy() {
 120     get_energy $1
 121 }
 122
 123 get_kinetic_energy() {
 124     get_energy $1 v
 125 }
 126
 127 add_states() {
 128     local step=$1
 129     local -i got_states=0
 130     add_state $step x || got_states+=1
 131     add_state $step y || got_states+=1
 132     add_state $step z || got_states+=1
 133
 134     if [ $got_states -eq 3 ]; then
 135         return 1
 136     fi
 137 }
 138
 139 add_state() {
 140     local step=$1
 141     local key=$2
 142     local state=
 143
 144     if [ ${cycles[$key]+a} ]; then
 145         return 1
 146     fi
 147
 148     state="$(get_state_string $key)$(get_state_string ${key}v)"
 149
 150     if [ ${states[${key}_${state}]+a} ]; then
 151         if [ ${states[${key}_${state}]} -eq 0 ]; then
 152             cycles[$key]="$step"
 153             return 1
 154         fi
 155     fi
 156     states["${key}_${state}"]=$step
 157 }
 158
 159 get_state_string() {
 160     local key=$1
 161     local state="|"
 162     local moon
 163
 164     for (( moon=1; moon<=$moon_count; moon++ )); do
 165         state+="${moons[${moon}_${key}]}|"
 166     done
 167
 168     echo "$state"
 169 }
 170
 171 get_lcm() {
 172     local -a values=( $@ )
 173     local -A factor_counts
 174     local -a factors
 175     local factor
 176     local value
 177     local power
 178     local -i lcm=1
 179
 180     for value in ${values[@]}; do
 181         local -a factors
 182         factors=( $(get_prime_factors $value) )
 183         local -A temp_factor_counts
 184         for factor in ${factors[@]}; do
 185             if [ ${temp_factor_counts[$factor]+a} ]; then
 186                 temp_factor_counts[$factor]=$((${temp_factor_counts[$factor]}+1))
 187             else
 188                 temp_factor_counts[$factor]=1
 189             fi
 190         done
 191         # loop through temp_factor_counts before we clear it
 192         for factor in ${!temp_factor_counts[@]}; do
 193             if [ ${factor_counts[$factor]+a} ]; then
 194                 if [ ${temp_factor_counts[$factor]} -gt ${factor_counts[$factor]} ]; then
 195                     factor_counts[$factor]=${temp_factor_counts[$factor]}
 196                 fi
 197             else
 198                 factor_counts[$factor]=${temp_factor_counts[$factor]}
 199             fi
 200         done
 201         unset temp_factor_counts
 202         unset factors
 203     done
 204
 205     for factor in "${!factor_counts[@]}"; do
 206         power=${factor_counts[$factor]}
 207         value=$(($factor**$power))
 208         let lcm=$lcm*$value
 209     done
 210
 211     echo $lcm
 212 }
 213
 214 get_prime_factors() {
 215     local val=$1
 216     local -a factors
 217
 218     # start with the biggest prime, work down until we hit a prime
 219     for (( a=$((${#primes[@]}-1)); a>=0; a-- )); do
 220         prime=${primes[$a]}
 221         while [ $(( val % $prime )) -eq 0 ]; do
 222             factors+=( $prime )
 223             val=$((val/$prime))
 224         done
 225         if [ $val -eq 1 ]; then
 226             break
 227         fi
 228     done
 229
 230     echo "${factors[@]}"
 231 }
 232
 233 calculate_primes_required() {
 234     local vals=( $@ )
 235     local highest=${vals[0]}
 236     declare -g -a primes=( 2 )
 237
 238     # get highest val
 239     for val in ${vals[@]}; do
 240         if [ $val -gt $highest ]; then
 241             highest=$val
 242         fi
 243     done
 244
 245     for (( a=3; a<=$highest; a++ )); do
 246         for prime in ${primes[@]}; do
 247             if [ $((a%prime)) -eq 0 ]; then
 248                 continue 2
 249             fi
 250         done
 251         primes+=( $a )
 252     done
 253 }
 254
 255 read_file
 256
 257 echo Step 0
 258 display_moons_gravity_and_velocity
 259 echo
 260
 261 for (( step=1; step<=$steps; step++ )); do
 262     apply_gravity
 263     apply_velocity
 264     add_states $step
 265     if [ $((step % $display_steps)) -eq 0 ]; then
 266         echo Step $step
 267         display_moons_gravity_and_velocity
 268         echo
 269     fi
 270 done
 271
 272 # get the kinetic and potential energy for each moon
 273 # and the whole system
 274 total_energy=0
 275 for (( moon=1; moon<=$moon_count; moon++ )); do
 276     pe=$(get_potential_energy $moon)
 277     ke=$(get_kinetic_energy $moon)
 278     te=$(($pe*$ke))
 279     let total_energy+=$te
 280     echo "Moon $moon: PE=$pe, KE=$ke, TE=$te"
 281 done
 282
 283 echo "System total energy: $total_energy"
 284
 285 echo "Looking for duplicate state, this could take a while"
 286 spinner_parts=( '-' '/' '|' '\' )
 287
 288 printf '\r%s' ${spinner_parts[$(($step%4))]}
 289
 290 keep_going=1
 291 matched_state=0
 292 while [ $keep_going -eq 1 ]; do
 293     printf '\r%s' ${spinner_parts[$(($step%4))]}
 294     apply_gravity
 295     apply_velocity
 296     if ! add_states $step; then
 297         keep_going=0
 298     fi
 299     let step+=1
 300 done
 301
 302 printf '\r      \r'
 303 for key in ${!cycles[@]}; do
 304     echo "${key} cycles every ${cycles[$key]} steps"
 305 done
 306 echo "Calculating primes..."
 307 calculate_primes_required "${cycles[@]}"
 308 echo "Calculating repeat cycle..."
 309 repeat_cycle="$(get_lcm ${cycles[@]})"
 310 echo "Steps to get to a repeat: $repeat_cycle"