advent-of-code/2024/day-11/solution-2-2.sh

#!/usr/bin/env bash

FILE=input

# Get max num size by squaring the largest number
MAX_NUM_SIZE=0
while read -r NUM
do
  if [[ ${#NUM} -gt $MAX_NUM_SIZE ]]
  then
    MAX_NUM_SIZE=${#NUM}
  fi
done <<< "$( < input tr " " "\n" )"
(( MAX_NUM_SIZE*=2 ))

# Just pre-compute a large number of digits
{
  # Rule 1
  printf "0 1 \n"
  
  # Rule 2 : If even number of digits, split half half
  for (( i=10 ; i<100; i+=1 ))
  do
    DIGIT_COUNT=${#i}
    HALF=$(( DIGIT_COUNT / 2 ))
    printf "%s %s %s \n" "$i" "$(( 10#${i:0:$HALF} ))" "$(( 10#${i:$HALF} ))"
  done
  for (( i=1000 ; i<10000; i+=1 ))
  do
    DIGIT_COUNT=${#i}
    HALF=$(( DIGIT_COUNT / 2 ))
    printf "%s %s %s \n" "$i" "$(( 10#${i:0:$HALF} ))" "$(( 10#${i:$HALF} ))"
  done
  
  # Rule 3
  for (( i=1; i<10; i+=1 ))
  do
    printf "%s %s \n" "$i" "$(( i * 2024 ))"
  done 
  for (( i=100; i<1000; i+=1 ))
  do
    printf "%s %s \n" "$i" "$(( i * 2024 ))"
  done 
} | sort -n > kv-cache
printf "Cache built. KV size: %s \n" "$( wc -l kv-cache )" 

# Load cache file
declare -A KV_CACHE
while read -r KEY VALUE
do
  KV_CACHE[$KEY]="$VALUE"
done < kv-cache

# Use this function for cache misses
NUM=0
get_num () {

  NUM=$1

  # Rule 1 : Convert 0 to 1
  if [[ $NUM -eq 0 ]]
  then
    printf "%s 1 \n" "$OCCUR"
    return
  fi

  # Rule 2 : If even number of digits, split half half
  DIGIT_COUNT=${#NUM}
  if [[ $(( DIGIT_COUNT % 2 )) -eq 0 ]]
  then
    HALF=$(( DIGIT_COUNT / 2 ))
    printf "%s %s \n" "$OCCUR" "$(( 10#${NUM:0:$HALF} ))"
    printf "%s %s \n" "$OCCUR" "$(( 10#${NUM:$HALF} ))"
    return
  fi

  # Rule 3 : Multiply by 2024
  printf "%s %s \n" "$OCCUR" "$(( NUM * 2024 ))"
  return
}

# Start the loop
tr " " "\n" < "$FILE" | sort -n | uniq -c > temp-input
for (( i=0; i<750; i++ ))
do
  printf "%s Position %s\n" "$( date )" "$i"
  #cat temp-input
  while read -r OCCUR NUM
  do
    if [[ -v KV_CACHE[$NUM] ]]
    then
      for VAL in ${KV_CACHE[$NUM]}
      do
        printf "%s %s \n" "$OCCUR" "$VAL"
      done
    else
      get_num "$NUM"
    fi
  done < temp-input |
  tee temp-output |
  sort -n -k2 |
  uniq -c |
  awk '{sums[$3] += $1 * $2 } END {for (i in sums) {print sums[i], i}}' |
  sponge temp-input
done
printf "Final count: %s\n" "$( awk '{print $1}' < temp-input | paste -s -d "+" | bc )"