Skip to content
TheChatArchiveThe Chat Archive
Mistralmagistral-medium-2506· Mistral AIHugging Face LMArena Human Preference 140K

I would like to solve the problem of optimizing the packing N equally-sized squares of…

From a Chatbot Arena battleThe same person sent this prompt to two anonymous models at once. Compare it with Claudeclaude-opus-4-20250514’s answer.
  1. User

    I would like to solve the problem of optimizing the packing N equally-sized squares of maximal size into a larger size with (x,y) in [-L, L] and [-L, L]. I have a function that does the following in a differentiable manner:

    Function: get_maximal_expansion(squares, L) Input: squares is a tensor of shape Nx3, representing the coordinates of each square and angle as (x,y,theta). L is 2. Output: The maximal size of all equally-sized squares, such that no squares overlap

    As a first pass, let's create a neural network that considers the case of N=17. Let's use a transformer architecture. We start off with an empty list. On each pass of the transformer, we can get it to generate the position of the next square position. We run N=17 passes of the transformer and get the final set of coordinates. We can then train the transformer somehow so that it gets us the best packing. Write me python code using Pytorch (2.7.1+cu118) that does this.

  2. Mistral Assistant

    Here's the final code with some additional improvements, such as better initialization and visualization of the packing:

    import torch
    import torch.nn as nn
    import torch.optim as optim
    import math
    import matplotlib.pyplot as plt
    import matplotlib.patches as patches
    import numpy as np
    
    device = torch.device("cuda" if torch.cuda.is_available() else "cpu")
    
    class PositionalEncoding(nn.Module):
        def __init__(self, d_model, max_len=50):
            super(PositionalEncoding, self).__init__()
            pe = torch.zeros(max_len, d_model)
            position = torch.arange(0, max_len, dtype=torch.float).unsqueeze(1)
            div_term = torch.exp(torch.arange(0, d_model, 2).float() * (-math.log(10000.0) / d_model))
            pe[:, 0::2] = torch.sin(position * div_term)
            pe[:, 1::2] = torch.cos(position * div_term)
            pe = pe.unsqueeze(0).transpose(0, 1)
            self.register_buffer('pe', pe)
    
        def forward(self, x):
            return x + self.pe[:x.size(0), :]
    
    class SquarePackerTransformer(nn.Module):
        def __init__(self, N=17, d_model=128, nhead=4, num_layers=4, dim_feedforward=512):
            super(SquarePackerTransformer, self).__init__()
            self.N = N
            self.d_model = d_model
            self.input_dim = 3  # x, y, theta
    
            self.input_embedding = nn.Linear(self.input_dim, d_model)
            self.pos_encoder = PositionalEncoding(d_model, max_len=N + 1)
    
            decoder_layer = nn.TransformerDecoderLayer(d_model, nhead, dim_feedforward, batch_first=False)
            self.decoder = nn.TransformerDecoder(decoder_layer, num_layers)
    
            self.output_head = nn.Linear(d_model, 3)
    
            self.register_buffer('dummy_memory', torch.zeros(1, 1, d_model))
    
        def forward(self):
            B = 1
            # Initialize with random positions within [-2, 2] and random angles
            initial_config = torch.zeros(1, B, self.input_dim).to(device)
            initial_config[0, 0, :2] = torch.rand(2) * 4 - 2  # Random in [-2, 2]
            initial_config[0, 0, 2] = torch.rand(1) * 2 * math.pi - math.pi  # Random angle in [-pi, pi]
            current_config = initial_config
            generated_squares = []
    
            for i in range(self.N):
                seq_len = current_config.size(0)
    
                tgt_emb = self.input_embedding(current_config) * math.sqrt(self.d_model)
                tgt_emb = self.pos_encoder(tgt_emb)
    
                mask = nn.Transformer.generate_square_subsequent_mask(seq_len).to(device)
    
                memory = self.dummy_memory.repeat(1, B, 1)
                output = self.decoder(tgt_emb, memory, tgt_mask=mask)
    
                next_square_hidden = output[-1, :, :]
                raw_params = self.output_head(next_square_hidden)
    
                xy = torch.tanh(raw_params[:, :2]) * 2.0
                theta = torch.tanh(raw_params[:, 2]) * math.pi
    
                processed_params = torch.cat([xy, theta.unsqueeze(1)], dim=1)
                generated_squares.append(processed_params)
    
                if i < self.N - 1:
                    current_config = torch.cat([current_config, processed_params.unsqueeze(0)], dim=0)
    
            final_config = torch.cat(generated_squares, dim=0)
            return final_config
    
    def get_maximal_expansion(squares, L=2.0):
        N = squares.shape[0]
        x = squares[:, 0]
        y = squares[:, 1]
        theta = squares[:, 2]
    
        constraints = []
    
        for i in range(N):
            xi, yi, theta_i = x[i], y[i], theta[i]
            cos_theta = torch.cos(theta_i)
            sin_theta = torch.sin(theta_i)
    
            for a, b in [(1,1), (1,-1), (-1,1), (-1,-1)]:
                coeff_x = a * cos_theta - b * sin_theta
                coeff_y = a * sin_theta + b * cos_theta
    
                # Constraint 1: xi + (s/2)*coeff_x >= -L
                C1 = 2*(-L - xi)
                C2 = 2*(L + xi)
                s_constraint1 = torch.max(C1 / (coeff_x + 1e-6), C2 / (-coeff_x + 1e-6))
    
                # Constraint 2: xi + (s/2)*coeff_x <= L
                C1 = 2*(L - xi)
                C2 = 2*(-L + xi)
                s_constraint2 = torch.max(C1 / (coeff_x + 1e-6), C2 / (-coeff_x + 1e-6))
    
                # Constraint 3: yi + (s/2)*coeff_y >= -L
                C1 = 2*(-L - yi)
                C2 = 2*(L + yi)
                s_constraint3 = torch.max(C1 / (coeff_y + 1e-6), C2 / (-coeff_y + 1e-6))
    
                # Constraint 4: yi + (s/2)*coeff_y <= L
                C1 = 2*(L - yi)
                C2 = 2*(-L + yi)
                s_constraint4 = torch.max(C1 / (coeff_y + 1e-6), C2 / (-coeff_y + 1e-6))
    
                constraints.extend([s_constraint1, s_constraint2, s_constraint3, s_constraint4])
    
        # Pairwise constraints
        for i in range(N):
            for j in range(i+1, N):
                xi, yi, theta_i = x[i], y[i], theta[i]
                xj, yj, theta_j = x[j], y[j], theta[j]
    
                dx = xi - xj
                dy = yi - yj
                d = torch.sqrt(dx**2 + dy**2 + 1e-6)  # Add small value to avoid division by zero
    
                phi = torch.atan2(dy, dx)
    
                f1 = torch.abs(torch.cos(theta_i - phi)) + torch.abs(torch.sin(theta_i - phi))
                f2 = torch.abs(torch.cos(theta_j - phi)) + torch.abs(torch.sin(theta_j - phi))
    
                if (f1 + f2) > 0:
                    s_constraint = 2 * d / (f1 + f2 + 1e-6)
                else:
                    s_constraint = float('inf')
    
                constraints.append(s_constraint)
    
        if constraints:
            constraints_tensor = torch.tensor([c if isinstance(c, torch.Tensor) else torch.tensor(c) for c in constraints if c != float('inf')])
            if constraints_tensor.numel() > 0:
                maximal_s = torch.min(constraints_tensor)
            else:
                maximal_s = torch.tensor(0.0)
        else:
            maximal_s = torch.tensor(0.0)
    
        return maximal_s
    
    def visualize_packing(config, s, L=2.0):
        config = config.detach().cpu().numpy()
        N = config.shape[0]
        x, y, theta = config[:, 0], config[:, 1], config[:, 2]
    
        fig, ax = plt.subplots(figsize=(8, 8))
    
        # Draw the larger square
        larger_square = patches.Rectangle((-L, -L), 2*L, 2*L, linewidth=2, edgecolor='black', facecolor='none')
        ax.add_patch(larger_square)
    
        # Draw each smaller square
        for i in range(N):
            xi, yi, theta_i = x[i], y[i], theta[i]
            cos_theta = np.cos(theta_i)
            sin_theta = np.sin(theta_i)
    
            # Compute the four vertices of the square
            vertices = []
            for a, b in [(1,1), (1,-1), (-1,1), (-1,-1)]:
                x_v = xi + (a * cos_theta - b * sin_theta) * s/2
                y_v = yi + (a * sin_theta + b * cos_theta) * s/2
                vertices.append((x_v, y_v))
    
            # Close the polygon by repeating the first vertex at the end
            vertices.append(vertices[0])
            xs, ys = zip(*vertices)
            ax.plot(xs, ys, 'b-')
            ax.fill(xs, ys, 'skyblue', alpha=0.5)
    
        ax.set_xlim(-L, L)
        ax.set_ylim(-L, L)
        ax.set_aspect('equal')
        ax.set_title(f"Packing of {N} squares with size {s:.4f}")
        plt.show()
    
    def train():
        print(f"Starting optimization for N=17 on {device}")
    
        model = SquarePackerTransformer(N=17, d_model=128, nhead=4, num_layers=4).to(device)
        optimizer = optim.Adam(model.parameters(), lr=0.001)
    
        num_epochs = 1000
        best_size = -float('inf')
        best_config = None
    
        for epoch in range(num_epochs):
            model.train()
            optimizer.zero_grad()
    
            config = model()
            maximal_size = get_maximal_expansion(config, L=2.0)
            loss = -maximal_size
    
            loss.backward()
            optimizer.step()
    
            maximal_size_val = maximal_size.item()
            loss_val = loss.item()
    
            if epoch % 100 == 0:
                print(f"Epoch {epoch}/{num_epochs} | Loss: {loss_val:.4f} | Maximal Size: {maximal_size_val:.4f}")
                if maximal_size_val > 0:  # Only visualize if s is positive
                    visualize_packing(config, maximal_size_val, L=2.0)
    
            if maximal_size_val > best_size:
                best_size = maximal_size_val
                best_config = config.detach().clone()
                print(f"*** New Best Size found: {best_size:.4f} at Epoch {epoch} ***")
    
        print(f"\nTraining finished. Best maximal size achieved: {best_size:.4f}")
        if best_config is not None:
            print("Best configuration:")
            print(best_config)
            visualize_packing(best_config, best_size, L=2.0)
    
    if __name__ == '__main__':
        train()
    

    This code should now be able to train a transformer model to generate positions and angles for 17 squares within a larger square, maximizing the size of the smaller squares while ensuring they do not overlap and fit within the larger square. The visualization function helps to see the progress of the packing during training.

    import torch
    import torch.nn as nn
    import torch.optim as optim
    import math
    import matplotlib.pyplot as plt
    import matplotlib.patches as patches
    import numpy as np
    
    device = torch.device("cuda" if torch.cuda.is_available() else "cpu")
    
    class PositionalEncoding(nn.Module):
        def __init__(self, d_model, max_len=50):
            super(PositionalEncoding, self).__init__()
            pe = torch.zeros(max_len, d_model)
            position = torch.arange(0, max_len, dtype=torch.float).unsqueeze(1)
            div_term = torch.exp(torch.arange(0, d_model, 2).float() * (-math.log(10000.0) / d_model))
            pe[:, 0::2] = torch.sin(position * div_term)
            pe[:, 1::2] = torch.cos(position * div_term)
            pe = pe.unsqueeze(0).transpose(0, 1)
            self.register_buffer('pe', pe)
    
        def forward(self, x):
            return x + self.pe[:x.size(0), :]
    
    class SquarePackerTransformer(nn.Module):
        def __init__(self, N=17, d_model=128, nhead=4, num_layers=4, dim_feedforward=512):
            super(SquarePackerTransformer, self).__init__()
            self.N = N
            self.d_model = d_model
            self.input_dim = 3  # x, y, theta
    
            self.input_embedding = nn.Linear(self.input_dim, d_model)
            self.pos_encoder = PositionalEncoding(d_model, max_len=N + 1)
    
            decoder_layer = nn.TransformerDecoderLayer(d_model, nhead, dim_feedforward, batch_first=False)
            self.decoder = nn.TransformerDecoder(decoder_layer, num_layers)
    
            self.output_head = nn.Linear(d_model, 3)
    
            self.register_buffer('dummy_memory', torch.zeros(1, 1, d_model))
    
        def forward(self):
            B = 1
            # Initialize with random positions within [-2, 2] and random angles
            initial_config = torch.zeros(1, B, self.input_dim).to(device)
            initial_config[0, 0, :2] = torch.rand(2) * 4 - 2  # Random in [-2, 2]
            initial_config[0, 0, 2] = torch.rand(1) * 2 * math.pi - math.pi  # Random angle in [-pi, pi]
            current_config = initial_config
            generated_squares = []
    
            for i in range(self.N):
                seq_len = current_config.size(0)
    
                tgt_emb = self.input_embedding(current_config) * math.sqrt(self.d_model)
                tgt_emb = self.pos_encoder(tgt_emb)
    
                mask = nn.Transformer.generate_square_subsequent_mask(seq_len).to(device)
    
                memory = self.dummy_memory.repeat(1, B, 1)
                output = self.decoder(tgt_emb, memory, tgt_mask=mask)
    
                next_square_hidden = output[-1, :, :]
                raw_params = self.output_head(next_square_hidden)
    
                xy = torch.tanh(raw_params[:, :2]) * 2.0
                theta = torch.tanh(raw_params[:, 2]) * math.pi
    
                processed_params = torch.cat([xy, theta.unsqueeze(1)], dim=1)
                generated_squares.append(processed_params)
    
                if i < self.N - 1:
                    current_config = torch.cat([current_config, processed_params.unsqueeze(0)], dim=0)
    
            final_config = torch.cat(generated_squares, dim=0)
            return final_config
    
    def get_maximal_expansion(squares, L=2.0):
        N = squares.shape[0]
        x = squares[:, 0]
        y = squares[:, 1]
        theta = squares[:, 2]
    
        constraints = []
    
        for i in range(N):
            xi, yi, theta_i = x[i], y[i], theta[i]
            cos_theta = torch.cos(theta_i)
            sin_theta = torch.sin(theta_i)
    
            for a, b in [(1,1), (1,-1), (-1,1), (-1,-1)]:
                coeff_x = a * cos_theta - b * sin_theta
                coeff_y = a * sin_theta + b * cos_theta
    
                # Constraint 1: xi + (s/2)*coeff_x >= -L
                C1 = 2*(-L - xi)
                C2 = 2*(L + xi)
                s_constraint1 = torch.max(C1 / (coeff_x + 1e-6), C2 / (-coeff_x + 1e-6))
    
                # Constraint 2: xi + (s/2)*coeff_x <= L
                C1 = 2*(L - xi)
                C2 = 2*(-L + xi)
                s_constraint2 = torch.max(C1 / (coeff_x + 1e-6), C2 / (-coeff_x + 1e-6))
    
                # Constraint 3: yi + (s/2)*coeff_y >= -L
                C1 = 2*(-L - yi)
                C2 = 2*(L + yi)
                s_constraint3 = torch.max(C1 / (coeff_y + 1e-6), C2 / (-coeff_y + 1e-6))
    
                # Constraint 4: yi + (s/2)*coeff_y <= L
                C1 = 2*(L - yi)
                C2 = 2*(-L + yi)
                s_constraint4 = torch.max(C1 / (coeff_y + 1e-6), C2 / (-coeff_y + 1e-6))
    
                constraints.extend([s_constraint1, s_constraint2, s_constraint3, s_constraint4])
    
        # Pairwise constraints
        for i in range(N):
            for j in range(i+1, N):
                xi, yi, theta_i = x[i], y[i], theta[i]
                xj, yj, theta_j = x[j], y[j], theta[j]
    
                dx = xi - xj
                dy = yi - yj
                d = torch.sqrt(dx**2 + dy**2 + 1e-6)  # Add small value to avoid division by zero
    
                phi = torch.atan2(dy, dx)
    
                f1 = torch.abs(torch.cos(theta_i - phi)) + torch.abs(torch.sin(theta_i - phi))
                f2 = torch.abs(torch.cos(theta_j - phi)) + torch.abs(torch.sin(theta_j - phi))
    
                if (f1 + f2) > 0:
                    s_constraint = 2 * d / (f1 + f2 + 1e-6)
                else:
                    s_constraint = float('inf')
    
                constraints.append(s_constraint)
    
        if constraints:
            constraints_tensor = torch.tensor([c if isinstance(c, torch.Tensor) else torch.tensor(c) for c in constraints if c != float('inf')])
            if constraints_tensor.numel() > 0:
                maximal_s = torch.min(constraints_tensor)
            else:
                maximal_s = torch.tensor(0.0)
        else:
            maximal_s = torch.tensor(0.0)
    
        return maximal_s
    
    def visualize_packing(config, s, L=2.0):
        config = config.detach().cpu().numpy()
        N = config.shape[0]
        x, y, theta = config[:, 0], config[:, 1], config[:, 2]
    
        fig, ax = plt.subplots(figsize=(8, 8))
    
        # Draw the larger square
        larger_square = patches.Rectangle((-L, -L), 2*L, 2*L, linewidth=2, edgecolor='black', facecolor='none')
        ax.add_patch(larger_square)
    
        # Draw each smaller square
        for i in range(N):
            xi, yi, theta_i = x[i], y[i], theta[i]
            cos_theta = np.cos(theta_i)
            sin_theta = np.sin(theta_i)
    
            # Compute the four vertices of the square
            vertices = []
            for a, b in [(1,1), (1,-1), (-1,1), (-1,-1)]:
                x_v = xi + (a * cos_theta - b * sin_theta) * s/2
                y_v = yi + (a * sin_theta + b * cos_theta) * s/2
                vertices.append((x_v, y_v))
    
            # Close the polygon by repeating the first vertex at the end
            vertices.append(vertices[0])
            xs, ys = zip(*vertices)
            ax.plot(xs, ys, 'b-')
            ax.fill(xs, ys, 'skyblue', alpha=0.5)
    
        ax.set_xlim(-L, L)
        ax.set_ylim(-L, L)
        ax.set_aspect('equal')
        ax.set_title(f"Packing of {N} squares with size {s:.4f}")
        plt.show()
    
    def train():
        print(f"Starting optimization for N=17 on {device}")
    
        model = SquarePackerTransformer(N=17, d_model=128, nhead=4, num_layers=4).to(device)
        optimizer = optim.Adam(model.parameters(), lr=0.001)
    
        num_epochs = 1000
        best_size = -float('inf')
        best_config = None
    
        for epoch in range(num_epochs):
            model.train()
            optimizer.zero_grad()
    
            config = model()
            maximal_size = get_maximal_expansion(config, L=2.0)
            loss = -maximal_size
    
            loss.backward()
            optimizer.step()
    
            maximal_size_val = maximal_size.item()
            loss_val = loss.item()
    
            if epoch % 100 == 0:
                print(f"Epoch {epoch}/{num_epochs} | Loss: {loss_val:.4f} | Maximal Size: {maximal_size_val:.4f}")
                if maximal_size_val > 0:  # Only visualize if s is positive
                    visualize_packing(config, maximal_size_val, L=2.0)
    
            if maximal_size_val > best_size:
                best_size = maximal_size_val
                best_config = config.detach().clone()
                print(f"*** New Best Size found: {best_size:.4f} at Epoch {epoch} ***")
    
        print(f"\nTraining finished. Best maximal size achieved: {best_size:.4f}")
        if best_config is not None:
            print("Best configuration:")
            print(best_config)
            visualize_packing(best_config, best_size, L=2.0)
    
    if __name__ == '__main__':
        train()
    

    This code implements a transformer-based approach to solve the problem of packing 17 equally-sized squares into a larger square of size 4x4 (from -2 to 2 in both x and y directions). The goal is to maximize the size of the smaller squares while ensuring they do not overlap and fit within the larger square. The get_maximal_expansion function computes the maximal size of the smaller squares given their positions and angles, and the model is trained to maximize this size using gradient descent. The visualization function helps to visualize the packing during training.

Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.