defmodule Jido.Evolve.Examples.Knapsack do
  @moduledoc """
  Knapsack Problem: Select items to maximize value without exceeding weight capacity.

  ## Problem Description

  You have a knapsack with limited weight capacity and a collection of items,
  each with a weight and value. The goal is to select items that maximize total
  value without exceeding the weight limit.

  This demonstrates why genetic algorithms excel:
  - **Building blocks**: Good item combinations can be inherited
  - **Crossover value**: Mixing two good solutions often produces better offspring
  - **Selection pressure**: Invalid solutions (too heavy) are penalized

  ## Genome Representation

  Binary vector where 1 = item included, 0 = item excluded:

      [1, 0, 1, 1, 0, 1]  # Items 0, 2, 3, 5 selected

  ## Fitness Evaluation

  - If weight ≤ capacity: fitness = total value
  - If weight > capacity: fitness = total value - penalty * overage

  ## Usage

      iex> Jido.Evolve.Examples.Knapsack.run()
      # Evolution progress shown...
      # Final solution near optimal value

  ## Expected Results

  Converges to near-optimal solution in 50-100 generations, demonstrating
  how crossover combines good item selections from different parents.
  """

  @items [
    %{name: "Laptop", weight: 4, value: 2000},
    %{name: "Camera", weight: 3, value: 1500},
    %{name: "Phone", weight: 2, value: 1000},
    %{name: "Tablet", weight: 3, value: 900},
    %{name: "Headphones", weight: 1, value: 400},
    %{name: "Charger", weight: 1, value: 150},
    %{name: "Book", weight: 2, value: 100},
    %{name: "Sunglasses", weight: 1, value: 250},
    %{name: "Watch", weight: 2, value: 600},
    %{name: "Shoes", weight: 3, value: 850},
    %{name: "Jacket", weight: 4, value: 1100},
    %{name: "Umbrella", weight: 2, value: 200},
    %{name: "Water Bottle", weight: 1, value: 180},
    %{name: "Snacks", weight: 1, value: 220},
    %{name: "Power Bank", weight: 1, value: 350}
  ]

  @capacity 15
  @penalty_multiplier 1000

  use Jido.Evolve.Fitness

  @impl true
  def evaluate(genome, context) do
    items = context.items
    capacity = context.capacity
    penalty_multiplier = context.penalty_multiplier

    {total_weight, total_value} =
      genome
      |> Enum.with_index()
      |> Enum.reduce({0, 0}, fn {selected, idx}, {weight, value} ->
        if selected == 1 do
          item = Enum.at(items, idx)
          {weight + item.weight, value + item.value}
        else
          {weight, value}
        end
      end)

    overage = max(0, total_weight - capacity)
    penalty = penalty_multiplier * overage
    score = total_value - penalty

    {:ok, score}
  end

  @impl true
  def batch_evaluate(genomes, context) do
    results =
      Enum.map(genomes, fn genome ->
        {:ok, score} = evaluate(genome, context)
        {genome, score}
      end)

    {:ok, results}
  end

  def run(opts \\ []) do
    population_size = Keyword.get(opts, :population_size, 50)
    generations = Keyword.get(opts, :generations, 100)
    verbose = Keyword.get(opts, :verbose, true)

    # Random binary genomes matching item count
    initial_population =
      Enum.map(1..population_size, fn _ ->
        Enum.map(@items, fn _ -> Enum.random([0, 1]) end)
      end)

    context = %{
      items: @items,
      capacity: @capacity,
      penalty_multiplier: @penalty_multiplier
    }

    optimal = calculate_optimal_value()

    if verbose do
      IO.puts("\nKnapsack Problem Demo")
      IO.puts("=" |> String.duplicate(50))
      IO.puts("Items: #{length(@items)}")
      IO.puts("Capacity: #{@capacity}kg")
      IO.puts("Optimal value: $#{optimal}  (brute force calculation)\n")
    end

    {:ok, config} =
      Jido.Evolve.Config.new(
        population_size: population_size,
        generations: generations,
        mutation_rate: 0.15,
        crossover_rate: 0.65,
        elitism_rate: 0.02,
        selection_strategy: Jido.Evolve.Selection.Tournament,
        mutation_strategy: Jido.Evolve.Mutation.Binary,
        crossover_strategy: Jido.Evolve.Crossover.Uniform,
        termination_criteria: [target_fitness: optimal]
      )

    result =
      Jido.Evolve.evolve(
        initial_population: initial_population,
        config: config,
        fitness: __MODULE__,
        context: context
      )
      |> Stream.with_index()
      |> Stream.map(fn {state, _generation} ->
        if verbose do
          print_generation(state)
        end

        state
      end)
      |> Stream.take_while(fn state ->
        state.best_score < optimal and state.generation < generations
      end)
      |> Enum.to_list()
      |> List.last()

    if result && verbose do
      print_final_solution(result)
    end

    result
  end

  defp print_generation(state) do
    {weight, value, items} = decode_solution(state.best_entity)
    valid = if weight <= @capacity, do: "[OK]", else: "[OVERWEIGHT]"

    IO.puts(
      "Gen #{String.pad_leading(to_string(state.generation), 3)}: " <>
        "Value=$#{String.pad_leading(to_string(value), 4)} " <>
        "Weight=#{String.pad_leading(to_string(weight), 2)}kg " <>
        "Items=#{length(items)} #{valid}"
    )
  end

  defp print_final_solution(state) do
    {weight, value, items} = decode_solution(state.best_entity)

    IO.puts("\n" <> ("=" |> String.duplicate(50)))
    IO.puts("Final Solution (Generation #{state.generation})")
    IO.puts("=" |> String.duplicate(50))
    IO.puts("Total Value: $#{value}")
    IO.puts("Total Weight: #{weight}kg / #{@capacity}kg")
    IO.puts("\nSelected Items:")

    Enum.each(items, fn item ->
      IO.puts("  - #{item.name}: #{item.weight}kg, $#{item.value}")
    end)

    IO.puts("")
  end

  defp decode_solution(genome) do
    {weight, value, items} =
      genome
      |> Enum.with_index()
      |> Enum.reduce({0, 0, []}, fn {selected, idx}, {w, v, items} ->
        if selected == 1 do
          item = Enum.at(@items, idx)
          {w + item.weight, v + item.value, [item | items]}
        else
          {w, v, items}
        end
      end)

    {weight, value, Enum.reverse(items)}
  end

  defp calculate_optimal_value do
    # Brute force for small problem (2^10 = 1024 combinations)
    0..(Integer.pow(2, length(@items)) - 1)
    |> Enum.map(fn combination ->
      genome =
        0..(length(@items) - 1)
        |> Enum.map(fn idx ->
          if Bitwise.band(combination, Bitwise.bsl(1, idx)) > 0, do: 1, else: 0
        end)

      {weight, value, _} = decode_solution(genome)
      if weight <= @capacity, do: value, else: 0
    end)
    |> Enum.max()
  end
end