AoC 2023 day 5 part 2

aoc_day_5_part_2.sh

#!/usr/bin/env bash

set -euo pipefail

MODE=${1:-real}

function usage {
  echo "Usage:"
  echo
  echo "  $0 [mode]"
  echo
  echo "Arguments:"
  echo "  mode: either 'real' or 'test'. Decides which input file to load. Default: 'real'"
  echo
  exit 1
}

function input_file { # TESTED
  if [ "$1" != "real" ] && [ "$1" != "test" ] && [ "$1" != "test2" ]; then
    usage
  fi

  echo "input/1-${1}.txt"
}

SEEDS_TO_PLANT=()
# shellcheck disable=SC2034 # This map is accessed using a declared name ref
declare -A seed_map
# shellcheck disable=SC2034 # This map is accessed using a declared name ref
declare -A soil_map
# shellcheck disable=SC2034 # This map is accessed using a declared name ref
declare -A fertilizer_map
# shellcheck disable=SC2034 # This map is accessed using a declared name ref
declare -A water_map
# shellcheck disable=SC2034 # This map is accessed using a declared name ref
declare -A light_map
# shellcheck disable=SC2034 # This map is accessed using a declared name ref
declare -A temperature_map
# shellcheck disable=SC2034 # This map is accessed using a declared name ref
declare -A humidity_map
INTERSECTING_RANGES=()
NEXT_STAGE_SOURCE_RANGES=()
NEXT_STAGE_DESTINATION_RANGES=()
SPLIT_RANGES=()
SPLIT_RANGES_INTERSECTING=()
SPLIT_RANGES_NON_INTERSECTING=()
SOURCE_RANGES=()

function parse_seeds_to_plant { # TESTED
  # Takes the required seeds input line and populates the SEEDS_TO_PLANT array
  # 
  # Args:
  #   $1: The line to parse
  local TMP=()
  [[ "$1" =~ seeds:' '([0-9 ]+) ]]
  #readarray -d ' ' -t TMP < <(printf '%s' "${BASH_REMATCH[1]}") # <<<"${BASH_REMATCH[1]}"
  readarray -d ' ' -t TMP <<<"${BASH_REMATCH[1]}"

  local COUNT=0
  while [ $COUNT -lt ${#TMP[@]} ]; do
    local RANGE_START=${TMP[$COUNT]}
    local RANGE_LENGTH=${TMP[$((COUNT + 1))]}

    SEEDS_TO_PLANT+=("$RANGE_START $RANGE_LENGTH")

    COUNT=$((COUNT + 2))
  done
}

function range_wholly_contained { # TESTED
  # Given 2 ranges, checks if the first range is wholly encompassed by the second range.
  #
  # Args:
  #   $1: Source range start
  #   $2: Source range end
  #   $3: Destination range start
  #   $4: Destination range end
  if [ "$1" -ge "$3" ] && [ "$2" -le "$4" ]; then
    return 0
  fi

  return 1
}

function parse_map_name { # TESTED
  # Takes the line that defines the map name and parses INPUT, populates
  # the NEXT_MAP map with a KEY of source, and a VALUE of destination.
  #
  # Args:
  #   $1: The line to parse
  #
  # Outputs:
  #   <map_name>
  #   
  [[ "$1" =~ ^([^-]+)-to- ]]
  echo "${BASH_REMATCH[1]}"
}

function build_ranges { # TESTED
  # Parses args 2..n for seed map entries and populates the seed map named $1_map
  #
  # Args:
  #   $1: The current stage name to build the ranges for (e.g. seed, soil, fertilizer)
  #   $2..N: The Lines to parse
  local STAGE="$1"

  for MAP in "${@:2}"; do
    [[ "$MAP" =~ ^([0-9]+)' '([0-9]+)' '([0-9]+)$ ]]
    local DEST_START=${BASH_REMATCH[1]}
    local SOURCE_START=${BASH_REMATCH[2]}
    local RANGE_SIZE=${BASH_REMATCH[3]}
    local DEST_END=$((DEST_START + RANGE_SIZE - 1))
    local SOURCE_END=$((SOURCE_START + RANGE_SIZE - 1))

    declare -n map_name="${STAGE}_map"

    # shellcheck disable=SC2034 # The map is being accessed with a nameref so shellcheck can't tell that it is used later
    map_name["$SOURCE_START $SOURCE_END"]="$DEST_START $DEST_END"
  done
}

function get_all_intersecting_ranges { # TESTED
  # Given a source range, returns all destination ranges which
  # intersect the source range at all
  #
  # Args:
  #   $1: Source range first number
  #   $2: Source range last number
  #   $3: name of the current stage e.g. seed, fertilizer, light
  declare -n MAP="${3}_map"
  INTERSECTING_RANGES=()
  local SOURCE_START=$1
  local SOURCE_END=$2

  for SOURCE_RANGE in "${!MAP[@]}"; do
    [[ "$SOURCE_RANGE" =~ ([0-9]+)' '([0-9]+) ]]
    local RANGE_START=${BASH_REMATCH[1]}
    local RANGE_END=${BASH_REMATCH[2]}

    # Start is within range
    if [ "$SOURCE_START" -ge "$RANGE_START" ] && [ "$SOURCE_START" -le "$RANGE_END" ]; then
      INTERSECTING_RANGES+=("$SOURCE_RANGE")
      continue
    fi

    # End is within range
    if [ "$SOURCE_END" -ge "$RANGE_START" ] && [ "$SOURCE_END" -le "$RANGE_END" ]; then
      INTERSECTING_RANGES+=("$SOURCE_RANGE")
      continue
    fi

    # Start is before range and End if after range
    if [ "$SOURCE_START" -lt "$RANGE_START" ] && [ "$SOURCE_END" -gt "$RANGE_END" ]; then
      INTERSECTING_RANGES+=("$SOURCE_RANGE")
      continue
    fi
  done
}

function get_destination_num { # TESTED
  # Given a seed number, and the name of the current map
  # will get the destination seed number for the next stage
  #
  # Args:
  #   $1: seed number
  #   $2: name of the current stage "e.g. seed, fertilizer, light"
  local SEED_NUM=$1
  declare -n MAP="${2}_map"
  for SOURCE_RANGE in "${!MAP[@]}"; do
    [[ "$SOURCE_RANGE" =~ ^([0-9]+)' '([0-9]+)$ ]]
    local SOURCE_START=${BASH_REMATCH[1]}
    local SOURCE_END=${BASH_REMATCH[2]}

    if [ "$SEED_NUM" -ge "$SOURCE_START" ] && [ "$SEED_NUM" -le "$SOURCE_END" ]; then
      local DEST_RANGE="${MAP[$SOURCE_RANGE]}"
      [[ "$DEST_RANGE" =~ ^([0-9]+)' ' ]]
      local DEST_START=${BASH_REMATCH[1]}

      local DEST_SEED=$((DEST_START + (SEED_NUM - SOURCE_START)))
      echo "$DEST_SEED"
      return
    fi
  done

  echo "$SEED_NUM"
}

function add_to_next_stage_ranges { # TESTED
  # Given a start and end seed, will add to NEXT_STAGE_<SOURCE|DESTINATION>_RANGES
  # but will avoid duplicates
  #
  # Args:
  #   $1: Source range start
  #   $2: Source range end
  #   $3: <SOURCE|DESTINATION> (Used to set either NEXT_STAGE_SOURCE_RANGES or NEXT_STAGE_DESTINATION_RANGES)
  local SOURCE_START=$1
  local SOURCE_END=$2

  declare -n NEXT_RANGES="NEXT_STAGE_${3}_RANGES"

  for RANGE in "${NEXT_RANGES[@]}"; do
    [[ "$RANGE" =~ ([0-9]+)' '([0-9]+) ]]
    local EXISTING_RANGE_START="${BASH_REMATCH[1]}"
    local EXISTING_RANGE_END="${BASH_REMATCH[2]}"

    if range_wholly_contained $SOURCE_START $SOURCE_END $EXISTING_RANGE_START $EXISTING_RANGE_END; then
      return
    fi
  done

  NEXT_RANGES+=("$SOURCE_START $SOURCE_END")
}

function calculate_source_ranges { # TESTED
  # Given: A source range, and a stage name (e.g. seed, fertilizer, light)
  # will populate NEXT_STAGE_SOURCE_RANGES with all the ranges to translate
  # with the destination map. Will also populate NEXT_STAGE_DESTINATION_RANGES
  # with any source range which has no intersecting destination ranges
  #
  # Args:
  #   $1: Source range start
  #   $2: Source range end
  #   $3: Stage name (e.g. seed, fertilizer, light)
  local FIRST_SEED=$1
  local END_SEED=$2
  local STAGE=$3

  split_range_on_intersecting_ranges "$FIRST_SEED" "$END_SEED" "$STAGE"
  for RANGE in "${SPLIT_RANGES_NON_INTERSECTING[@]}"; do
    [[ "$RANGE" =~ ([0-9]+)' '([0-9]+) ]]
    local RANGE_START="${BASH_REMATCH[1]}"
    local RANGE_END="${BASH_REMATCH[2]}"

    add_to_next_stage_ranges "$RANGE_START" "$RANGE_END" "DESTINATION"
  done
  SPLIT_RANGES_NON_INTERSECTING=()

  for RANGE in "${SPLIT_RANGES_INTERSECTING[@]}"; do
    [[ "$RANGE" =~ ([0-9]+)' '([0-9]+) ]]
    local RANGE_START="${BASH_REMATCH[1]}"
    local RANGE_END="${BASH_REMATCH[2]}"

    add_to_next_stage_ranges "$RANGE_START" "$RANGE_END" "SOURCE"
  done
  SPLIT_RANGES_INTERSECTING=()
}

function translate_ranges { # TESTED
  # Will take all ranges in NEXT_STAGE_SOURCE_RANGES and 
  # add their translated counterparts into NEXT_STAGE_DESTINATION_RANGES
  #
  # Args:
  #   $1: Stage name (e.g. seed, fertilizer, light)
  local STAGE="$1"

  for SOURCE_RANGE in "${NEXT_STAGE_SOURCE_RANGES[@]}"; do
    [[ "$SOURCE_RANGE" =~ ([0-9]+)' '([0-9]+) ]]
    local SOURCE_START=${BASH_REMATCH[1]}
    local SOURCE_END=${BASH_REMATCH[2]}

    get_all_intersecting_ranges "${SOURCE_START}" "${SOURCE_END}" "$STAGE"
    if [ ${#INTERSECTING_RANGES[@]} -eq 0 ]; then
      NEXT_STAGE_DESTINATION_RANGES+=("$SOURCE_START $SOURCE_END")
      continue
    fi

    # Find the offset 
    local DEST_START=$(get_destination_num "$SOURCE_START" "$STAGE")

    local RANGE_OFFSET=$((SOURCE_START - DEST_START))

    NEXT_STAGE_DESTINATION_RANGES+=("$((SOURCE_START - RANGE_OFFSET)) $((SOURCE_END - RANGE_OFFSET))")
  done
  NEXT_STAGE_SOURCE_RANGES=()
}

function split_range_on_intersecting_ranges { # TESTED
  # Given a range, and a stage name will completely split the source
  # range into non-intersecting, and intersecting ranges.
  # Populates SPLIT_RANGES_INTERSECTING and SPLIT_RANGES_NON_INTERSECTING
  #
  # Args:
  #   $1: range start
  #   $2: range end
  #   $3: stage name (e.g. seed, fertilizer, light)
  local REMAINING_RANGES_TO_SPLIT=("$1 $2")
  local STAGE=$3
  local TMP_RANGES=()
  while [ "${#REMAINING_RANGES_TO_SPLIT[@]}" -gt 0 ]; do
    for RANGE_TO_SPLIT in "${REMAINING_RANGES_TO_SPLIT[@]}"; do
      [[ "$RANGE_TO_SPLIT" =~ ([0-9]+)' '([0-9]+) ]]
      local RANGE_TO_SPLIT_START=${BASH_REMATCH[1]}
      local RANGE_TO_SPLIT_END=${BASH_REMATCH[2]}

      get_all_intersecting_ranges "$RANGE_TO_SPLIT_START" "$RANGE_TO_SPLIT_END" "$STAGE"
      if [ "${#INTERSECTING_RANGES[@]}" -eq 0 ]; then
        SPLIT_RANGES_NON_INTERSECTING+=("$RANGE_TO_SPLIT_START $RANGE_TO_SPLIT_END")
        continue
      else
        [[ "${INTERSECTING_RANGES[0]}" =~ ([0-9]+)' '([0-9]+) ]]
        local INTERSECTING_RANGE_START=${BASH_REMATCH[1]}
        local INTERSECTING_RANGE_END=${BASH_REMATCH[2]}

        if range_wholly_contained "$RANGE_TO_SPLIT_START" "$RANGE_TO_SPLIT_END" "$INTERSECTING_RANGE_START" "$INTERSECTING_RANGE_END"; then
          SPLIT_RANGES_INTERSECTING+=("$RANGE_TO_SPLIT_START $RANGE_TO_SPLIT_END")
        else
          split_range "$RANGE_TO_SPLIT_START" "$RANGE_TO_SPLIT_END" "$INTERSECTING_RANGE_START" "$INTERSECTING_RANGE_END"
          for SPLIT_RANGE in "${SPLIT_RANGES[@]}"; do
            [[ "${SPLIT_RANGE[0]}" =~ ([0-9]+)' '([0-9]+) ]]
            local SPLIT_RANGE_START=${BASH_REMATCH[1]}
            local SPLIT_RANGE_END=${BASH_REMATCH[2]}

            if range_wholly_contained "$SPLIT_RANGE_START" "$SPLIT_RANGE_END" "$INTERSECTING_RANGE_START" "$INTERSECTING_RANGE_END"; then
              SPLIT_RANGES_INTERSECTING+=("$SPLIT_RANGE_START $SPLIT_RANGE_END")
            else
              TMP_RANGES+=("$SPLIT_RANGE_START $SPLIT_RANGE_END")
            fi
          done
        fi
      fi
    done

    REMAINING_RANGES_TO_SPLIT=()
    for RANGE in "${TMP_RANGES[@]}"; do
      REMAINING_RANGES_TO_SPLIT+=("$RANGE")
    done
    TMP_RANGES=()
  done
}

function split_range { # TESTED
  # Given a source range and a destination range, will split_range
  # the source range into multiple ranges, one of which will be wholly
  # contained by the destination range, and either one or two other
  # ranges which do not intersect with the destination range
  #
  # Note: This function assumes the source and destination intersect
  #
  # Args:
  #   $1: Source range start
  #   $2: Source range end
  #   $3: Destination range start
  #   $4: Destination range end
  SPLIT_RANGES=()
  local SOURCE_START=$1
  local SOURCE_END=$2
  local DEST_START=$3
  local DEST_END=$4

  if [ "$SOURCE_START" -lt "$DEST_START" ] && [ "$SOURCE_END" -gt "$DEST_END" ]; then
    SPLIT_RANGES+=(
      "$SOURCE_START $((DEST_START - 1))"
      "$DEST_START $DEST_END"
      "$((DEST_END + 1)) $SOURCE_END"
    )
  elif [ "$SOURCE_START" -lt "$DEST_START" ]; then
    SPLIT_RANGES+=(
      "$SOURCE_START $((DEST_START - 1))"
      "$DEST_START $SOURCE_END"
    )
  elif [ "$SOURCE_END" -gt "$DEST_END" ]; then
    SPLIT_RANGES+=(
      "$SOURCE_START $DEST_END"
      "$((DEST_END + 1)) $SOURCE_END"
    )
  fi
}

function copy_next_destination_to_source_ranges { # TESTED
  # Empties SOURCE_RANGES and then copies NEXT_STAGE_DESTINATION_RANGES
  # into SOURCE_RANGES
  SOURCE_RANGES=()

  for RANGE in "${NEXT_STAGE_DESTINATION_RANGES[@]}"; do
    SOURCE_RANGES+=("$RANGE")
  done
}

function initialise {
  # Initialise seeds to plant and maps from file
  #
  # Args:
  #   $1: Input file to load
  local LINES=()
  readarray -t LINES <"$1"

  parse_seeds_to_plant "${LINES[0]}"

  local MAP_NAME=
  local COUNT=2
  local ACC=()
  while [ "$COUNT" -lt "${#LINES[@]}" ]; do
    local CURR_LINE="${LINES[$COUNT]}"

    if [[ "$CURR_LINE" =~ map ]]; then
      MAP_NAME=$(parse_map_name "$CURR_LINE")
      COUNT=$((COUNT + 1))
      continue
    fi

    if [[ -z "$CURR_LINE" ]]; then
      build_ranges "$MAP_NAME" "${ACC[@]}"
      ACC=()

      COUNT=$((COUNT + 1))
      continue
    fi

    ACC+=("$CURR_LINE")

    COUNT=$((COUNT + 1))
  done

  build_ranges "$MAP_NAME" "${ACC[@]}"
}

function calculate_lowest {
  local LOWEST_DESTINATION=""
  for seed in "${SEEDS_TO_PLANT[@]}"; do
    >&2 echo -n "."
    [[ "$seed" =~ ([0-9]+)' '([0-9]+) ]]
    local FIRST_SEED=${BASH_REMATCH[1]}
    local TOTAL_SEEDS=${BASH_REMATCH[2]}
    local END_SEED=$((FIRST_SEED + TOTAL_SEEDS - 1))

    SOURCE_RANGES=()

    NEXT_STAGE_SOURCE_RANGES=()
    NEXT_STAGE_DESTINATION_RANGES=()
    calculate_source_ranges "$FIRST_SEED" "$END_SEED" "seed"
    translate_ranges "seed"
    copy_next_destination_to_source_ranges

    for STAGE in soil fertilizer water light temperature humidity; do
      NEXT_STAGE_SOURCE_RANGES=()
      NEXT_STAGE_DESTINATION_RANGES=()
      for SOURCE_RANGE in "${SOURCE_RANGES[@]}"; do
        [[ "$SOURCE_RANGE" =~ ([0-9]+)' '([0-9]+) ]]
        FIRST_SEED=${BASH_REMATCH[1]}
        END_SEED=${BASH_REMATCH[2]}

        calculate_source_ranges "$FIRST_SEED" "$END_SEED" "$STAGE"
      done
      translate_ranges "$STAGE"
      copy_next_destination_to_source_ranges
    done

    for SOURCE_RANGE in "${SOURCE_RANGES[@]}"; do
      [[ "$SOURCE_RANGE" =~ ([0-9]+)' '([0-9]+) ]]
      LOCATION="${BASH_REMATCH[1]}"

      if [ -z "$LOWEST_DESTINATION" ] || [ "$LOCATION" -lt "$LOWEST_DESTINATION" ]; then
        LOWEST_DESTINATION="$LOCATION"
      fi
    done
  done

  >&2 echo
  echo "$LOWEST_DESTINATION"
}

function run_main {
  INPUT_FILE=$(input_file "$MODE")

  initialise "$INPUT_FILE"

  calculate_lowest
}

if [[ "${BASH_SOURCE[0]}" == "${0}" ]]; then
  echo
  echo "Lowest Destination: $(run_main)"
fi