Skip to content

Instantly share code, notes, and snippets.

@ArthurN
Created February 28, 2024 16:18
Show Gist options
  • Save ArthurN/6c78409a9650624688eb16c0ea23c2fc to your computer and use it in GitHub Desktop.
Save ArthurN/6c78409a9650624688eb16c0ea23c2fc to your computer and use it in GitHub Desktop.
Knapsack Elixir
# 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)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment