Knapsack Elixir

knapsack.exs

# mostly Copilot generated, have not tested/verified

defmodule ImagePlacement do
  def place_images(images, canvas_width, canvas_height) do
    # Sort images by size in descending order
    sorted_images = Enum.sort_by(images, &image_area(&1), &>=/2)

    # Initialize the canvas with the first image
    canvas = %{x: 0, y: 0, width: image_width(hd(sorted_images)), height: image_height(hd(sorted_images))}

    # Place the remaining images on the canvas
    Enum.reduce(tl(sorted_images), canvas, fn image, canvas ->
      {x, y} = find_best_position(image, canvas, canvas_width, canvas_height)
      new_canvas = %{canvas | x: x, y: y, width: image_width(image), height: image_height(image)}
      merge_canvas(canvas, new_canvas)
    end)
  end

  defp image_width(image), do: elem(image, 0)
  defp image_height(image), do: elem(image, 1)
  defp image_area(image), do: image_width(image) * image_height(image)

  defp find_best_position(image, canvas, canvas_width, canvas_height) do
    # Find the best position with minimal overlap
    Enum.reduce(0..canvas_height - image_height(image), {nil, nil, :infinity}, fn y, {best_x, best_y, min_overlap} ->
      Enum.reduce(0..canvas_width - image_width(image), {best_x, best_y, min_overlap}, fn x, {best_x, best_y, min_overlap} ->
        overlap = calculate_overlap(image, canvas, x, y)
        if overlap < min_overlap do
          {x, y, overlap}
        else
          {best_x, best_y, min_overlap}
        end
      end)
    end)
  end

  defp calculate_overlap(image, canvas, x, y) do
    # Calculate the overlap between the image and the canvas

    overlap_x = max(0, x + image_width(image) - canvas[:x] - canvas[:width])
    overlap_y = max(0, y + image_height(image) - canvas[:y] - canvas[:height])
    overlap_x * overlap_y
  end

  defp merge_canvas(canvas1, canvas2) do
    # Merge two canvas regions
    x = min(canvas1[:x], canvas2[:x])
    y = min(canvas1[:y], canvas2[:y])
    width = max(canvas1[:x] + canvas1[:width], canvas2[:x] + canvas2[:width]) - x
    height = max(canvas1[:y] + canvas1[:height], canvas2[:y] + canvas2[:height]) - y
    %{x: x, y: y, width: width, height: height}
  end
end

# Usage example
images = [
  {100, 200},  # Image 1 with width 100 and height 200
  {150, 150},  # Image 2 with width 150 and height 150
  {200, 100}   # Image 3 with width 200 and height 100
]

canvas_width = 800
canvas_height = 600

canvas = ImagePlacement.place_images(images, canvas_width, canvas_height)
IO.inspect(canvas)