inventory_optimizer.py

# -*- coding: utf-8 -*-
"""EFT_Inventory_Optimizer.ipynb

Automatically generated by Colaboratory.

Original file is located at
    https://colab.research.google.com/drive/12QiwXiPWXfNVpIoROfjCaby7awa3Vdp1
"""

import numpy as np
import matplotlib.pyplot as plt
import random
import itertools
from tqdm import tqdm

def rotate_block(block):
    return (block[1], block[0])

def place_block(grid, x, y, block):
    block_width, block_height = block
    if x + block_width > grid.shape[0] or y + block_height > grid.shape[1]:
        return False
    if np.any(grid[x:x + block_width, y:y + block_height]):
        return False
    grid[x:x + block_width, y:y + block_height] = 1
    return True

def sort_blocks_by_size(blocks):
    return sorted(blocks, key=lambda block: block[0] * block[1], reverse=True)

def flood_fill(grid, x, y, visited):
    if x < 0 or x >= grid.shape[0] or y < 0 or y >= grid.shape[1] or visited[x, y] or grid[x, y] != 0:
        return 0
    visited[x, y] = True
    return 1 + flood_fill(grid, x + 1, y, visited) + flood_fill(grid, x - 1, y, visited) + flood_fill(grid, x, y + 1, visited) + flood_fill(grid, x, y - 1, visited)

def find_largest_empty_zone(grid):
    visited = np.zeros_like(grid, dtype=bool)
    largest_zone = 0

    for i in range(grid.shape[0]):
        for j in range(grid.shape[1]):
            if grid[i, j] == 0 and not visited[i, j]:
                zone_size = flood_fill(grid, i, j, visited)
                largest_zone = max(largest_zone, zone_size)

    return largest_zone

# def evaluate_grid(grid):
#     empty_cells = np.sum(grid == 0)
#     num_empty_zones = empty_cells
#     largest_empty_zone = 1 if empty_cells > 0 else 0
#     return num_empty_zones, largest_empty_zone

def evaluate_grid(grid):
    empty_cells = np.sum(grid == 0)
    num_empty_zones = empty_cells
    largest_empty_zone = find_largest_empty_zone(grid)
    return num_empty_zones, largest_empty_zone

def find_placement_for_block(grid, block):
    for x in range(grid.shape[0]):
        for y in range(grid.shape[1]):
            if place_block(grid.copy(), x, y, block):
                return x, y, False  # False indicates no rotation
            rotated_block = rotate_block(block)
            if place_block(grid.copy(), x, y, rotated_block):
                return x, y, True  # True indicates rotation
    return None

def optimize_block_placement(blocks, iterations=100, grid_size = (30, 10)):
    best_grid = None
    best_score = float('inf')
    best_block_positions = []

    for _ in tqdm(range(iterations)):
        if random.random() < 0.2:
            blocks = sort_blocks_by_size(blocks)
        else:
            random.shuffle(blocks)

        grid = np.zeros((grid_size[0], grid_size[1]), dtype=int)
        block_positions = []
        all_blocks_placed = True

        for block in blocks:
            placement = find_placement_for_block(grid, block)
            if placement:
                x, y, rotated = placement
                place_block(grid, x, y, block if not rotated else rotate_block(block))
                block_positions.append((x, y, block[0], block[1], rotated))  # Include rotation info
            else:
                all_blocks_placed = False
                break

        if all_blocks_placed:
            num_empty_zones, largest_empty_zone = evaluate_grid(grid)
            score = num_empty_zones - largest_empty_zone
            if score < best_score:
                best_score = score
                best_grid = grid.copy()
                best_block_positions = block_positions.copy()

    return best_grid, best_block_positions

def plot_grid_with_blocks_and_labels(grid, block_positions):
    fig, ax = plt.subplots(figsize=(12, 6))

    colors = itertools.cycle(['red', 'green', 'blue', 'orange', 'purple', 'brown', 'pink', 'cyan', 'magenta', 'yellow'])
    color_map = {}

    for position in block_positions:
        x, y, w, h, rotated = position
        if rotated:
            w, h = h, w
        if (w, h) in color_map:
            color = color_map[(w, h)]
        else:
            color = next(colors)
            color_map[(w, h)] = color

        rect = plt.Rectangle((y-0.5, x-0.5), h, w, fill=False, edgecolor=color, lw=2)
        ax.add_patch(rect)
        ax.text(y + h/2, x + w/2, f"{w}x{h}", ha='center', va='center', color='black')

    grid[grid == 0] = 1
    ax.imshow(grid, cmap="Greys", alpha=0.3)

    plt.title("Жадный алгоритм сортировки вещей")
    plt.show()



Колво_попыток = 250

# Область на которой разместить предметы
Размер_Контейнера = (65, 10)

#Размер и кол-во предметов (размер Х, размер У, кол-во предметов такого размера)
Список_Предметов = [
    (2, 2, 12),
    (3, 3, 10),
    (4, 4, 5),
    (2, 3, 2),
    (4, 3, 7),
    (6, 5, 3),
    (7, 5, 1),
    (5, 5, 4),
    ]

output_blocks = [(x, y) for x, y, amount in Список_Предметов for _ in range(amount)]
x, y = optimize_block_placement(output_blocks, Колво_попыток, Размер_Контейнера)
plot_grid_with_blocks_and_labels(x, y)