#!/usr/bin/env python3 """ Solveur OR-Tools avec Support de Rotation 3D Programmation par Contraintes avec 6 orientations possibles par coli """ import sys from ortools.sat.python import cp_model def solve_ortools(): """Solveur CP-SAT avec support de rotation""" # --- LECTURE --- input_data = sys.stdin.read().split() if not input_data: return iterator = iter(input_data) try: L_truck = int(next(iterator)) W_truck = int(next(iterator)) H_truck = int(next(iterator)) M = int(next(iterator)) except StopIteration: return item_original_dims = [] item_orders = [] for i in range(M): l = int(next(iterator)) w = int(next(iterator)) h = int(next(iterator)) d = int(next(iterator)) item_original_dims.append((l, w, h)) item_orders.append(d) # Générer toutes les rotations possibles pour chaque coli # Pour chaque coli, on a 3 rotations uniques principales def get_rotations(dims): l, w, h = dims # 3 rotations principales (les 3 axes X, Y, Z) return [ (l, w, h), (l, h, w), (w, l, h), ] all_rotations = [get_rotations(dims) for dims in item_original_dims] max_vehicles = M # --- MODÈLE CP-SAT --- model = cp_model.CpModel() # VARIABLES # Pour chaque coli, on doit choisir une rotation ET une position # Approach 1 : Créer des variables pour chaque rotation possible # is_rotation[i][r] = True si coli i utilise rotation r item_vehicle = [] item_x = [] item_y = [] item_z = [] item_rotation = [] # Index de rotation utilisée for i in range(M): # Véhicule assigné v_id = model.NewIntVar(0, max_vehicles - 1, f'v_id_{i}') item_vehicle.append(v_id) # Rotation choisie (index dans all_rotations[i]) rot_idx = model.NewIntVar(0, len(all_rotations[i]) - 1, f'rot_{i}') item_rotation.append(rot_idx) # Les dimensions dépendent de la rotation, donc on force manuellement # Pour simplifier, on crée des variables pour chaque dimension possible # et on force le choix via disjonction max_dim = max(max(d) for d in all_rotations[i]) item_x.append(model.NewIntVar(0, L_truck - 1, f'x_{i}')) item_y.append(model.NewIntVar(0, W_truck - 1, f'y_{i}')) item_z.append(model.NewIntVar(0, H_truck - 1, f'z_{i}')) # Variables : "véhicule utilisé" vehicle_used = [model.NewBoolVar(f'v_used_{v}') for v in range(max_vehicles)] # Assignation unique for i in range(M): is_in_vehicle = [model.NewBoolVar(f'in_v{v}_i{i}') for v in range(max_vehicles)] model.Add(sum(is_in_vehicle) == 1) for v in range(max_vehicles): model.Add(item_vehicle[i] == v).OnlyEnforceIf(is_in_vehicle[i]) # Activer vehicle_used model.Add(vehicle_used[v] == True).OnlyEnforceIf(is_in_vehicle[i]) # CONTRAINTES # A. Contraintes géométriques avec rotation for i in range(M): for rot_idx, (l, w, h) in enumerate(all_rotations[i]): is_this_rotation = model.NewBoolVar(f'is_rot_{i}_{rot_idx}') # Lier la variable booléenne à l'index de rotation model.Add(item_rotation[i] == rot_idx).OnlyEnforceIf(is_this_rotation) model.Add(item_rotation[i] != rot_idx).OnlyEnforceIf(is_this_rotation.Not()) # Si cette rotation est choisie, appliquer les bornes model.Add(item_x[i] + l <= L_truck).OnlyEnforceIf(is_this_rotation) model.Add(item_y[i] + w <= W_truck).OnlyEnforceIf(is_this_rotation) model.Add(item_z[i] + h <= H_truck).OnlyEnforceIf(is_this_rotation) # B. Non-chevauchement (simplifié : approximation 2D sur axe X-Y) # Note: Full 3D no-overlap est complexe avec rotations en CP-SAT for i in range(M): for j in range(i + 1, M): same_vehicle = model.NewBoolVar(f'same_{i}_{j}') model.Add(item_vehicle[i] == item_vehicle[j]).OnlyEnforceIf(same_vehicle) # Pour chaque paire de rotations, créer les contraintes de séparation for rot_i in range(len(all_rotations[i])): for rot_j in range(len(all_rotations[j])): l_i, w_i, h_i = all_rotations[i][rot_i] l_j, w_j, h_j = all_rotations[j][rot_j] both_rotations = (model.NewBoolVar(f'both_rot_{i}_{rot_i}_{j}_{rot_j}')) model.Add(item_rotation[i] == rot_i).OnlyEnforceIf(both_rotations) model.Add(item_rotation[j] == rot_j).OnlyEnforceIf(both_rotations) # Si ces rotations, forcer la séparation left = model.NewBoolVar(f'{i}_left_{j}_{rot_i}_{rot_j}') right = model.NewBoolVar(f'{i}_right_{j}_{rot_i}_{rot_j}') behind = model.NewBoolVar(f'{i}_behind_{j}_{rot_i}_{rot_j}') front = model.NewBoolVar(f'{i}_front_{j}_{rot_i}_{rot_j}') below = model.NewBoolVar(f'{i}_below_{j}_{rot_i}_{rot_j}') above = model.NewBoolVar(f'{i}_above_{j}_{rot_i}_{rot_j}') model.Add(item_x[i] + l_i <= item_x[j]).OnlyEnforceIf([left, both_rotations]) model.Add(item_x[j] + l_j <= item_x[i]).OnlyEnforceIf([right, both_rotations]) model.Add(item_y[i] + w_i <= item_y[j]).OnlyEnforceIf([behind, both_rotations]) model.Add(item_y[j] + w_j <= item_y[i]).OnlyEnforceIf([front, both_rotations]) model.Add(item_z[i] + h_i <= item_z[j]).OnlyEnforceIf([below, both_rotations]) model.Add(item_z[j] + h_j <= item_z[i]).OnlyEnforceIf([above, both_rotations]) # Si même véhicule, au moins une séparation doit être vraie model.AddBoolOr([left, right, behind, front, below, above]).OnlyEnforceIf([same_vehicle, both_rotations]) # C. Symmetry Breaking for v in range(max_vehicles - 1): model.Add(vehicle_used[v] >= vehicle_used[v+1]) model.Add(item_vehicle[0] == 0) # D. Contrainte LIFO for i in range(M): for j in range(M): if i == j: continue if item_orders[i] != -1 and item_orders[j] != -1 and item_orders[i] < item_orders[j]: same_v = model.NewBoolVar(f'same_lifo_{i}_{j}') model.Add(item_vehicle[i] == item_vehicle[j]).OnlyEnforceIf(same_v) # i doit être devant j (x_i plus grand) model.Add(item_x[i] >= item_x[j]).OnlyEnforceIf(same_v) # OBJECTIF model.Minimize(sum(vehicle_used)) # --- RÉSOLUTION --- solver = cp_model.CpSolver() solver.parameters.max_time_in_seconds = 20.0 status = solver.Solve(model) if status == cp_model.OPTIMAL or status == cp_model.FEASIBLE: print("SAT") for i in range(M): v = solver.Value(item_vehicle[i]) x = solver.Value(item_x[i]) y = solver.Value(item_y[i]) z = solver.Value(item_z[i]) rot_idx = solver.Value(item_rotation[i]) l, w, h = all_rotations[i][rot_idx] print(f"{v} {x} {y} {z} {x+l} {y+w} {z+h}") else: print("UNSAT") if __name__ == "__main__": solve_ortools()