Pain and suffering part 2 (optimized now :D)

-- These values are per 500mB, since a crystal takes 6000mB to make, we will need to divide everything by 12 later to get their actual increment in values.
---@type table<string, laser_item>
local LASER_VALUES = {}
do
  local function ilv(name, purity, strength, efficiency, max_purity, max_strength, max_efficiency)
    LASER_VALUES[name] = {
      purity = purity or 0,
      strength = strength or 0,
      efficiency = efficiency or 0,
      max_purity = max_purity or 100,
      max_strength = max_strength or 100,
      max_efficiency = max_efficiency or 100
    }
  end

  ilv("minecraft:ender_pearl", 2, 0, 0, 100, 0, 0)
  ilv("minecraft:quartz", -1, 0, 7, 0, 0, 80)
  ilv("minecraft:gunpowder", -5, 8, 4, 0, 70, 60)
  ilv("minecraft:diamond", 5, 0, 0, 100, 0, 0)
  ilv("minecraft:glowstone_dust", -2, 6, 3, 0, 50, 50)
  ilv("minecraft:iron_ingot", 0, -2, 1, 0, 0, 20)
  ilv("rftoolsbase:dimensionalshard", 1, 8, 8, 100, 80, 80)
  ilv("minecraft:prismarine_shard", 0, 3, 3, 0, 30, 30)
  ilv("minecraft:gold_ingot", 0, -1, 1, 0, 0, 30)
  ilv("minecraft:prismarine_crystals", 0, 4, 4, 0, 35, 35)
  ilv("minecraft:coal", -1, -10, 0, 0, 0, 0)             -- Not sure why you'd want to use coal.
  ilv("minecraft:nether_star", -60, 90, 90, 0, 100, 100) -- Very powerful, but also requires a repurification.
  ilv("minecraft:nether_wart", -3, 2, -2, 0, 35, 1)
  ilv("minecraft:redstone", -1, 5, 0, 0, 60, 0)
  ilv("minecraft:slime_ball", 0, 0, -10, 0, 0, 1) -- Not sure why you'd want to use slime balls.
  ilv("minecraft:emerald", 8, 0, 0, 100, 0, 0)    -- May be used as a subsitute to repurification?
  ilv("minecraft:blaze_powder", -6, 5, 5, 0, 70, 70)
  ilv("minecraft:ghast_tear", -20, 25, 15, 0, 100, 100)
  ilv("minecraft:snowball", 1, 0, 1, 30, 0, 40)
end

--- Deep clone a table
---@param t any
---@return any t
local function deep_copy(t)
  if type(t) ~= "table" then return t end

  local out = {}

  for k, v in pairs(t) do
    out[k] = deep_copy(v)
  end

  return out
end

--- This function will do the exact same thing as the original best_item_combo function.
--- However, there will be a few things done to optimize the algorithm, as currently there are just
--- too many combinations to check.
--- We will note, the original description is as follows:
---   This function will bruteforce the best combination of items to use in the lasers.
---   It will return a table of items to use, and the amount of items to use, and in what order.
---   This function only needs to care about strength and efficiency, though we must note purity CANNOT go below 1%
---   This function will also take into account the amount of items we have in the storage chest.
---   We will likely need to use some heavy recursion here.
--- In order to optimize this, we will need to do a few things:
---  1. We will need to sort the items by their type, so we can group them together.
---  2. We will greedily take from each type, until they reach their maximum potency, minimum purity, or run out of items.
--- Hopefully this will be enough to optimize it.
---@param current laser_list? The current list of items we are using, along with the current strength, efficiency, and purity.
---@param item_list short_laser_item[]? The list of items we can use.
---@return table<integer, string> list The best list of items found.
---@return integer strength The strength of the best list of items found.
---@return integer efficiency The efficiency of the best list of items found.
---@return integer purity The purity of the best list of items found.
local function best_item_combo_optimized(current, item_list)
  local x = not current
  -- Initial purity (after leaving the purifier) is 85%, initial strength is 10%, initial efficiency is 10%.
  current = current or { list = {}, used = {}, strength = 10, efficiency = 10, purity = 85 }

  if not item_list then
    -- We will need to initialize the list of items available, searching the storage chest and adding items as we see them.
    -- We should collapse all similar items so all we have are the item names and the amount of items.
    item_list = {}

    local storage = config.peripherals.chests.storage
    local list = smn.call(storage, "list")
    for _, item in pairs(list) do
      local found = false
      for _, item2 in ipairs(item_list) do
        if item.name == item2.name then
          item2.count = item2.count + item.count
          found = true
          break
        end
      end

      if not found then
        table.insert(item_list, { name = item.name, count = item.count })
      end
    end
  end
  -- Coincidentally, the item list is already sorted "enough" here. We don't particularly care about the individual values, just that they are grouped together.

  -- We will need to loop through the item list, and for each item, we will need to greedily add it to the current list, then call this function again.
  -- We will need to keep track of the best item list, and the best strength and efficiency.
  local best_strength = current.strength
  local best_efficiency = current.efficiency
  local best_purity = current.purity
  local best_list = {}

  for _, item in ipairs(item_list) do

    local new_strength, new_efficiency, new_purity = current.strength, current.efficiency, current.purity
    local last_strength, last_efficiency = new_strength, new_efficiency
    local added = 0
    repeat
      -- Check how much of this item remains
      local remaining = item.count - (current.used[item.name] or 0)
      local exit = false

      if remaining > 0 and LASER_VALUES[item.name] then

        -- Add this item to both lists.
        table.insert(current.list, item.name)
        current.used[item.name] = (current.used[item.name] or 0) + 1
        added = added + 1

        -- Calculate the new strength, efficiency, and purity.
        local laser_value = LASER_VALUES[item.name]

        -- If the values are above zero, we cannot go above the maximum.
        -- If the values are below or equal to zero, we can go down essentially forever (to a minimum of zero)
        -- We will also hard-cap each side at 100 and 0, just to ensure nothing goes crazy anywhere.

        if laser_value.strength > 0 then
          new_strength = math.min(new_strength + laser_value.strength / 12, laser_value.max_strength, 100)
        else
          new_strength = math.max(new_strength + laser_value.strength / 12, laser_value.max_strength, 0)
        end

        if laser_value.efficiency > 0 then
          new_efficiency = math.min(new_efficiency + laser_value.efficiency / 12, laser_value.max_efficiency, 100)
        else
          new_efficiency = math.max(new_efficiency + laser_value.efficiency / 12, laser_value.max_efficiency, 0)
        end

        if laser_value.purity > 0 then
          new_purity = math.min(new_purity + laser_value.purity / 12, laser_value.max_purity, 100)
        else
          new_purity = math.max(new_purity + laser_value.purity / 12, laser_value.max_purity, 0)
        end

        -- Check if the values are out of bounds.

        -- Check strength.
        if new_strength >= laser_value.max_strength then
          if last_strength < laser_value.max_strength then
            -- We can keep this item, but we should exit immediately.
            -- Leaving this empty block here for documentation.
          else
            -- We were over the max last time, and we are still over the max, so we should remove this item, then exit.
            table.remove(current.list, #current.list)
            current.used[item.name] = current.used[item.name] - 1
            added = added - 1
          end
          exit = true
        end

        -- Check efficiency.
        if new_efficiency >= laser_value.max_efficiency then
          if last_efficiency < laser_value.max_efficiency then
            -- We can keep this item, but we should exit immediately.
            -- Leaving this empty block here for documentation.
          else
            -- We were over the max last time, and we are still over the max, so we should remove this item, then exit.
            table.remove(current.list, #current.list)
            current.used[item.name] = current.used[item.name] - 1
            added = added - 1
          end
          exit = true
        end

        -- Check purity.
        -- We will need to check if the purity is below 1%.
        if new_purity <= 1.05 then
          -- Purity cannot go below 1% whatsoever, so we will need to remove this item, then exit.
          table.remove(current.list, #current.list)
          current.used[item.name] = current.used[item.name] - 1
          added = added - 1
          exit = true
        end
      else -- No items left of this type (or we can't use this item in the laser), so we will need to exit.
        exit = true
      end
    until remaining <= 0 or exit

    if x then
      print(item.name, added)
    end

    -- If the new strength and efficiency are better than the best, we will need to update the best.
    -- However, if the purity is below or equal to 1%, we will discard this attempt.
    if new_purity > 1 and new_strength >= best_strength then
      -- If the new strength and efficiency are better than the best, we will need to update the best.
      best_strength = new_strength
      best_efficiency = new_efficiency
      best_purity = new_purity
      best_list = deep_copy(current.list)
    end

    local new_current = deep_copy(current)
    new_current.strength = new_strength
    new_current.efficiency = new_efficiency
    new_current.purity = new_purity

    -- To prevent excess looping, we exit if nothing was added.
    if added > 0 then
      -- Now we will recurse, with the new values and list.
      local best_recursed_list, best_recursed_strength, best_recursed_efficiency, best_recursed_purity = best_item_combo_optimized(new_current, item_list)

      -- Then we will need to check if the recursed values are better than the current best.
      -- We will only worry about purity and strength here, since strength determines total RF storage, and purity needs to remain above 1.
      -- We will check for purity above 1.05, to ensure it never goes below 1 due to any rounding errors.
      if best_recursed_purity > 1.05 and best_recursed_strength > best_strength then
        best_strength = best_recursed_strength
        best_efficiency = best_recursed_efficiency
        best_purity = best_recursed_purity
        best_list = best_recursed_list
      end

      -- Now we can remove all the items we added
      for i = 1, added do
        table.remove(current.list, #current.list)
        current.used[item.name] = current.used[item.name] - 1
      end
    end
  end

  return best_list, best_strength, best_efficiency, best_purity
end