
import pandas as pd
import numpy as np
import random
import time


pip install ortools

Collecting ortools
  Downloading ortools-9.11.4210-cp310-cp310-manylinux_2_17_x86_64.manylinux2014_x86_64.whl.metadata (3.0 kB)
Collecting absl-py>=2.0.0 (from ortools)
  Downloading absl_py-2.1.0-py3-none-any.whl.metadata (2.3 kB)
Requirement already satisfied: numpy>=1.13.3 in /usr/local/lib/python3.10/dist-packages (from ortools) (1.26.4)
Requirement already satisfied: pandas>=2.0.0 in /usr/local/lib/python3.10/dist-packages (from ortools) (2.2.2)
Collecting protobuf<5.27,>=5.26.1 (from ortools)
  Downloading protobuf-5.26.1-cp37-abi3-manylinux2014_x86_64.whl.metadata (592 bytes)
Requirement already satisfied: immutabledict>=3.0.0 in /usr/local/lib/python3.10/dist-packages (from ortools) (4.2.1)
Requirement already satisfied: python-dateutil>=2.8.2 in /usr/local/lib/python3.10/dist-packages (from pandas>=2.0.0->ortools) (2.8.2)
Requirement already satisfied: pytz>=2020.1 in /usr/local/lib/python3.10/dist-packages (from pandas>=2.0.0->ortools) (2024.2)
Requirement already satisfied: tzdata>=2022.7 in /usr/local/lib/python3.10/dist-packages (from pandas>=2.0.0->ortools) (2024.2)
Requirement already satisfied: six>=1.5 in /usr/local/lib/python3.10/dist-packages (from python-dateutil>=2.8.2->pandas>=2.0.0->ortools) (1.16.0)
Downloading ortools-9.11.4210-cp310-cp310-manylinux_2_17_x86_64.manylinux2014_x86_64.whl (28.1 MB)
   ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━ 28.1/28.1 MB 63.0 MB/s eta 0:00:00
Downloading absl_py-2.1.0-py3-none-any.whl (133 kB)
   ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━ 133.7/133.7 kB 6.9 MB/s eta 0:00:00
Downloading protobuf-5.26.1-cp37-abi3-manylinux2014_x86_64.whl (302 kB)
   ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━ 302.8/302.8 kB 17.5 MB/s eta 0:00:00
Installing collected packages: protobuf, absl-py, ortools
  Attempting uninstall: protobuf
    Found existing installation: protobuf 4.25.5
    Uninstalling protobuf-4.25.5:
      Successfully uninstalled protobuf-4.25.5
  Attempting uninstall: absl-py
    Found existing installation: absl-py 1.4.0
    Uninstalling absl-py-1.4.0:
      Successfully uninstalled absl-py-1.4.0
ERROR: pip's dependency resolver does not currently take into account all the packages that are installed. This behaviour is the source of the following dependency conflicts.
tensorflow 2.17.1 requires protobuf!=4.21.0,!=4.21.1,!=4.21.2,!=4.21.3,!=4.21.4,!=4.21.5,<5.0.0dev,>=3.20.3, but you have protobuf 5.26.1 which is incompatible.
tensorflow-metadata 1.13.1 requires absl-py<2.0.0,>=0.9, but you have absl-py 2.1.0 which is incompatible.
tensorflow-metadata 1.13.1 requires protobuf<5,>=3.20.3, but you have protobuf 5.26.1 which is incompatible.
Successfully installed absl-py-2.1.0 ortools-9.11.4210 protobuf-5.26.1


import numpy as np
import pandas as pd
import random

from ortools.sat.python import cp_model


# The biscuit manufacturing factory aims to produce 4 types of biscuits :
biscuit0 =  {'biscuit': 0, 'length': 4, 'value': 6, 'a': 4, 'b': 2, 'c': 3}
biscuit1 =  {'biscuit': 1, 'length': 8, 'value': 12, 'a': 5, 'b': 4, 'c': 4}
biscuit2 =  {'biscuit': 2, 'length': 2, 'value': 1, 'a': 1, 'b': 2, 'c': 1}
biscuit3 =  {'biscuit': 3, 'length': 5, 'value': 8, 'a': 2, 'b': 3, 'c': 2}
BISCUIT_LIST = [biscuit0, biscuit1, biscuit2, biscuit3]

MIN_BISCUIT_SIZE = 2

def normalize(series):
    return (series - series.min()) / (series.max() - series.min())

lengths = np.array([biscuit0['length'], biscuit1['length'], biscuit2['length'], biscuit3['length']])
values = np.array([biscuit0['value'], biscuit1['value'], biscuit2['value'], biscuit3['value']])
a_values = [biscuit0['a'], biscuit1['a'], biscuit2['a'], biscuit3['a']]
b_values = [biscuit0['b'], biscuit1['b'], biscuit2['b'], biscuit3['b']]
c_values = [biscuit0['c'], biscuit1['c'], biscuit2['c'], biscuit3['c']]

BISCUIT_FEATURES = pd.DataFrame({
    'benefit': values / lengths,
    'a': a_values,
    'b': b_values,
    'c': c_values
})

BISCUIT_FEATURES = BISCUIT_FEATURES.apply(normalize)

def calculate_score(importance_factors, eps=0.001):
    """ Calculate the scores for each biscuit based on importance factors """
    features_copy = BISCUIT_FEATURES.copy()
    for i, column in enumerate(features_copy.columns):
        features_copy[column] *= importance_factors[i]
    scores = list(features_copy.sum(axis=1) + eps)
    return scores

class Roll(object):
    def __init__(self, size):
        self.size = size
        self.defects = [{'a': 0, 'b': 0, 'c': 0} for _ in range(size)]
        self.biscuits = ['_' for _ in range(size)]
        self.total_value = 0

    def get_defect_count(self, start=0, end=None):
        defect_a, defect_b, defect_c = 0, 0, 0
        if end is None:
            end = self.size
        for i in range(start, end):
            defect_a += self.defects[i]['a']
            defect_b += self.defects[i]['b']
            defect_c += self.defects[i]['c']
        return {'a': defect_a, 'b': defect_b, 'c': defect_c}

    def partition(self, start, end, copy=False):
        """ Return a partition of the dough roll from position start to end """
        partition_roll = Roll(1 + end - start)
        partition_roll.defects = self.defects[start:end + 1].copy()
        if copy:
            partition_roll.biscuits = self.biscuits[start:end + 1].copy()
            partition_roll.update_value()
        return partition_roll

    def place_defect(self, defect_type, pos):
        """ Add a defect of given type at the specified position in the roll """
        self.defects[pos][defect_type] += 1

    def place_biscuit(self, biscuit, start):
        """ Add the biscuit if it is possible, return True; else do nothing and return False """
        end = start + biscuit['length']

        # Check if the biscuit can fit in the roll
        if end <= self.size and self.biscuits[start:end] == ['_' for _ in range(start, end)]:
            defects = self.get_defect_count(start, end)

            # Check constraints (a, b, c defects)
            if biscuit['a'] < defects['a']:
                return False
            if biscuit['b'] < defects['b']:
                return False
            if biscuit['c'] < defects['c']:
                return False

            # Place the biscuit on the roll
            self.biscuits[start:end] = [biscuit['biscuit'] for _ in range(start, end)]
            self.biscuits[start] = '[' + str(biscuit['biscuit'])  # Mark the start
            self.biscuits[end - 1] = str(biscuit['biscuit']) + ']'  # Mark the end

            # Update total value
            self.total_value += biscuit['value']

            return True
        else:
            return False

    def remove_biscuit(self, biscuit, start):
        end = start + biscuit['length']
        i = start

        if self.biscuits[i] == '[' + str(biscuit['biscuit']):
            # Loop through the biscuit's length and clear the biscuit's positions
            while i < end and self.biscuits[i] != str(biscuit['biscuit']) + ']':
                self.biscuits[i] = '_'
                i += 1

            # Finally clear the end marker as well
            if i < len(self.biscuits) and self.biscuits[i] == str(biscuit['biscuit']) + ']':
                self.biscuits[i] = '_'

            # Decrease the total value
            self.total_value -= biscuit['value']

    def display(self, part=20):
        if len(self.defects) < 20:
            part = len(self.defects)
        info = {str(i): [self.defects[i], self.biscuits[i]] for i in range(self.size)}
        df = pd.DataFrame(info)
        print('Total Value:', self.total_value)
        for i in range(0, self.size // part):
            display(df[df.columns[i * part: i * part + part]])
        if self.size % part != 0:
            display(df[df.columns[(i + 1) * part: (i + 1) * part + (self.size % part)]])

    def reset_roll(self):
        self.biscuits = ['_' for _ in range(self.size)]
        self.total_value = 0

    def calculate_constraint_rates(self, benefit_rate):
        remaining = 1 - benefit_rate
        defects_count = self.get_defect_count()
        a_count = defects_count['a']
        b_count = defects_count['b']
        c_count = defects_count['c']
        total_defects = a_count + b_count + c_count
        if total_defects != 0:
            a_rate = (remaining * a_count) / total_defects
            b_rate = (remaining * b_count) / total_defects
            c_rate = (remaining * c_count) / total_defects
            return [benefit_rate, a_rate, b_rate, c_rate]
        return [benefit_rate, 0, 0, 0]

    def update_value(self):
        """ Updates the total value of the roll based on the biscuits placed """
        self.total_value = 0
        i = 0
        while i < self.size:
            if '[' in self.biscuits[i]:
                biscuit = BISCUIT_LIST[int(self.biscuits[i][1])]
                self.total_value += biscuit['value']
                i += biscuit['length']
            else:
                i += 1

    # dynamic programming algorithm
    def dynamic_programming_biscuit_placement(self, biscuits, belt_size):
        # Initialize the DP table and auxiliary data structures
        dp = [0] * (belt_size + 1)  # dp[i] will store the maximum value achievable for length i
        biscuit_placement = [-1] * (belt_size + 1)  # Tracks the biscuit placed at each position

        # Process biscuits in order of size or value to avoid redundant calculations
        biscuits.sort(key=lambda x: x['value'], reverse=True)  # Sort biscuits by value (optional)

        # Use dynamic programming to fill the dp table
        for i in range(len(biscuits)):
            biscuit = biscuits[i]
            for j in range(belt_size, biscuit['length'] - 1, -1):  # Traverse backward to avoid over-counting
                # If placing the biscuit at position j provides a better value, update the DP table
                if dp[j - biscuit['length']] + biscuit['value'] > dp[j]:
                    dp[j] = dp[j - biscuit['length']] + biscuit['value']
                    biscuit_placement[j] = i  # Record that this biscuit was placed at position j

        # Reconstruct the solution from the biscuit_placement array
        placed_biscuits = []
        current_position = belt_size

        # Backtrack to determine the biscuits that were placed and their positions
        while current_position > 0:
            if biscuit_placement[current_position] != -1:
                biscuit_index = biscuit_placement[current_position]
                biscuit = biscuits[biscuit_index]
                placed_biscuits.append((biscuit, current_position - biscuit['length'], current_position))
                current_position -= biscuit['length']
            else:
                break  # No more biscuits can be placed

        # Place the biscuits using place_biscuit and print their positions
        placed_biscuits.reverse()  # Reverse to show the placement order
        for biscuit, start, end in placed_biscuits:
            # Now use place_biscuit to actually place the biscuit on the conveyor belt
            print(f"Biscuit {biscuit['biscuit']} placed from position {start} to {end}")
            self.place_biscuit(biscuit, start)  # Place the biscuit on the conveyor using the method

        # Return the total value of the biscuits placed
        total_value = dp[belt_size]
        print(f"Total value: {total_value}")
        return total_value

    def solve_biscuit_placement(biscuits, belt_size, defects):
        """
        Solves the biscuit placement problem using Constraint Programming (CP).

        Parameters:
        - biscuits: List of dictionaries representing biscuit properties.
        - belt_size: Integer, length of the dough roll.
        - defects: List of dictionaries representing defects at each position on the roll.

        Returns:
        - A dictionary with placement details and total profit.
        """
        # Create the model
        model = cp_model.CpModel()

        # Decision variables
        num_biscuits = len(biscuits)
        placement = [model.NewIntVar(0, belt_size - 1, f'placement_{i}') for i in range(num_biscuits)]
        is_placed = [model.NewBoolVar(f'is_placed_{i}') for i in range(num_biscuits)]

        # Boolean array to track if a position is covered by any biscuit
        position_covered = [model.NewBoolVar(f'covered_{j}') for j in range(belt_size)]

        # Auxiliary variables for calculating profit penalties
        unused_penalties = [model.NewBoolVar(f'unused_{j}') for j in range(belt_size)]

        # Constraints
        for i, biscuit in enumerate(biscuits):
            size = biscuit['length']
            value = biscuit['value']
            thresholds = {key: biscuit[key] for key in biscuit if key in ['a', 'b', 'c']}

            # A biscuit can only be placed if it fits within the belt and satisfies defect thresholds
            for pos in range(belt_size):
                if pos + size <= belt_size:
                    # Check if defects in the range [pos, pos + size - 1] are below thresholds
                    defect_constraints = []
                    for defect_class, max_allowed in thresholds.items():
                        defect_sum = sum(defects[pos + k].get(defect_class, 0) for k in range(size))
                        defect_constraints.append(defect_sum <= max_allowed)

                    # Biscuit placement is valid only if all defect constraints are met
                    valid_position = model.NewBoolVar(f'valid_position_{i}_{pos}')
                    model.AddBoolAnd(defect_constraints).OnlyEnforceIf(valid_position)
                    model.AddBoolOr([valid_position.Not()]).OnlyEnforceIf(valid_position.Not())

            # Ensure that if a biscuit is placed, it doesn't overlap with other biscuits
            for j in range(belt_size):
                if j + size <= belt_size:
                    model.AddBoolAnd([position_covered[j + k].Not() for k in range(size)]).OnlyEnforceIf(is_placed[i])
                    for k in range(size):
                        model.AddImplication(is_placed[i], position_covered[j + k])

            # Ensure the biscuit placement aligns with its "is_placed" variable
            model.Add(is_placed[i] == 1).OnlyEnforceIf([position_covered[j] for j in range(size)])

        # Penalize unused positions
        for j in range(belt_size):
            model.Add(unused_penalties[j] == 1).OnlyEnforceIf(position_covered[j].Not())
            model.Add(unused_penalties[j] == 0).OnlyEnforceIf(position_covered[j])

        # Objective: Maximize profit (sum of biscuit values) minus unused position penalties
        total_value = sum(is_placed[i] * biscuits[i]['value'] for i in range(num_biscuits))
        penalty = sum(unused_penalties[j] for j in range(belt_size))
        model.Maximize(total_value - penalty)

        # Solve the model
        solver = cp_model.CpSolver()
        status = solver.Solve(model)

        # Extract the solution
        if status in (cp_model.OPTIMAL, cp_model.FEASIBLE):
            placements = []
            for i in range(num_biscuits):
                if solver.Value(is_placed[i]) == 1:
                    placements.append({
                        'biscuit': biscuits[i]['biscuit'],
                        'start_position': solver.Value(placement[i]),
                        'value': biscuits[i]['value']
                    })
            total_profit = solver.ObjectiveValue()
            return {
                'placements': placements,
                'total_profit': total_profit
            }
        else:
            return {
                'message': 'No feasible solution found.'
            }


# init empty roll of size 500
main_roll = Roll(500)
main_roll.display()

Total Value: 0


# get the defects of the roll of dough
defect = pd.read_csv('defects.csv')
defect.head()


defect['x'] = defect['x'].astype(int)
defect.head()


# now we can place defects in our main roll
for i in range(defect.shape[0]):
    main_roll.place_defect(defect['class'].iloc[i], defect['x'].iloc[i])
main_roll.display()

Total Value: 0


# calculate the total number of defects of each type
main_roll.get_defect_count()

{'a': 164, 'b': 159, 'c': 177}


# let's view all possible biscuits of our problem:
for biscuit in BISCUIT_LIST:
    print("biscuit{} : {}".format(biscuit['biscuit'], biscuit))

biscuit0 : {'biscuit': 0, 'length': 4, 'value': 6, 'a': 4, 'b': 2, 'c': 3}
biscuit1 : {'biscuit': 1, 'length': 8, 'value': 12, 'a': 5, 'b': 4, 'c': 4}
biscuit2 : {'biscuit': 2, 'length': 2, 'value': 1, 'a': 1, 'b': 2, 'c': 1}
biscuit3 : {'biscuit': 3, 'length': 5, 'value': 8, 'a': 2, 'b': 3, 'c': 2}


# create a partition of the main roll
# the partition starts at pos 5 and end at 20 of the main roll
partition = main_roll.partition(5,20)
partition.display()

Total Value: 0


import matplotlib.pyplot as plt
defects = [main_roll.defects[i] for i in range(main_roll.size)]
defect_a = [d['a'] for d in defects]
defect_b = [d['b'] for d in defects]
defect_c = [d['c'] for d in defects]

plt.plot(defect_a, label='Defect A')
plt.plot(defect_b, label='Defect B')
plt.plot(defect_c, label='Defect C')
plt.legend()
plt.title('Defect Distribution Across the Roll')
plt.xlabel('Position')
plt.ylabel('Defect Count')
plt.show()


def generate_neighbors(current_solution, roll, biscuits):
    neighbors = []  # initialize an empty list to store neighbor solutions
    for i in range(len(current_solution)):  # iterate through each biscuit placement in the current solution
        b_idx, start = current_solution[i]  # get the biscuit type (b_idx) and starting position (start)

        # move biscuit
        for delta in range(-3, 4):  # attempt to shift the biscuit up to 3 positions left or right
            new_start = start + delta  # calculate the new starting position
            if 0 <= new_start <= roll.size - biscuits[b_idx]['length']:  
                # ensure the new position is valid (within roll bounds and not exceeding roll size)
                roll.remove_biscuit(biscuits[b_idx], start)  # temporarily remove the biscuit from its current position
                if roll.place_biscuit(biscuits[b_idx], new_start):  
                    # check if the biscuit can be placed at the new position
                    # create a new solution with the biscuit moved to the new position
                    neighbors.append(current_solution[:i] + [(b_idx, new_start)] + current_solution[i + 1:])
                roll.place_biscuit(biscuits[b_idx], start)  # restore the biscuit to its original position

        # replace biscuit
        for new_b_idx in range(len(biscuits)):  # iterate through all biscuit types to attempt replacements
            if new_b_idx != b_idx:  # ensure the new biscuit type is different from the current one
                roll.remove_biscuit(biscuits[b_idx], start)  # temporarily remove the current biscuit
                if roll.place_biscuit(biscuits[new_b_idx], start):  
                    # check if the new biscuit can be placed at the same position
                    # create a new solution with the biscuit replaced by a different type
                    neighbors.append(current_solution[:i] + [(new_b_idx, start)] + current_solution[i + 1:])
                roll.place_biscuit(biscuits[b_idx], start)  # restore the original biscuit

    return neighbors  # return the list of all generated neighbor solutions


def fitness(solution, roll, biscuits):
    # reset the roll to remove all biscuits and defects before evaluating the solution
    roll.reset_roll()
    # initialize a variable to keep track of the total value of the solution
    total_value = 0
    # loop through the biscuit placements in the given solution
    for b_idx, start in solution:
        # attempt to place each biscuit at the specified position
        if roll.place_biscuit(biscuits[b_idx], start):
            # if the biscuit is successfully placed, add its value to the total value
            total_value += biscuits[b_idx]['value']
    # calculate the number of unused spaces on the roll after placing all biscuits
    unused_spaces = roll.biscuits.count('_')
    # apply a penalty for unused spaces by subtracting half a unit of value for each unused space
    total_value -= 0.5 * unused_spaces  # adjust the penalty weight to be less harsh
    # return the calculated fitness score, which represents the total value minus penalties
    return total_value


def local_search(roll, biscuits, initial_solution, max_iterations=100):
    # start with the initial solution provided as input
    current_solution = initial_solution
    # evaluate the fitness of the initial solution
    current_fitness = fitness(current_solution, roll, biscuits)

    # perform a loop for a fixed number of iterations or until no improvement
    for iteration in range(max_iterations):
        # generate all neighboring solutions based on the current solution
        neighbors = generate_neighbors(current_solution, roll, biscuits)
        # initialize variables to track the best neighbor and its fitness
        best_neighbor = None
        best_fitness = current_fitness

        # iterate through all neighbors to evaluate their fitness
        for neighbor in neighbors:
            # calculate the fitness of the current neighbor
            neighbor_fitness = fitness(neighbor, roll, biscuits)
            # check if the neighbor has a better fitness than the current best
            if neighbor_fitness > best_fitness:
                # update the best neighbor and its fitness
                best_neighbor = neighbor
                best_fitness = neighbor_fitness

        # if no better neighbor is found, exit the loop (local optimum reached)
        if best_neighbor is None:
            break

        # update the current solution and fitness with the best neighbor
        current_solution = best_neighbor
        current_fitness = best_fitness

    # return the best solution and its fitness after the search
    return current_solution, current_fitness


def initialize_solution(roll, biscuits):
    # initialize an empty list to store the solution
    solution = []
    # sort the biscuits in descending order of value-to-length ratio for prioritization
    biscuits_sorted = sorted(biscuits, key=lambda x: x['value'] / x['length'], reverse=True)
    
    # iterate through the sorted biscuits
    for biscuit in biscuits_sorted:
        # try to place the current biscuit at every possible starting position
        for start in range(roll.size - biscuit['length']):
            # if the biscuit can be placed at the current position
            if roll.place_biscuit(biscuit, start):
                # add the biscuit's index and starting position to the solution
                solution.append((biscuits.index(biscuit), start))
    
    # return the constructed solution
    return solution


def visualize_roll(solution, roll, biscuits, iteration):
    # reset the roll to its initial state before placing biscuits
    roll.reset_roll()
    # iterate over the solution to place each biscuit on the roll
    for b_idx, start in solution:
        # place the biscuit at its specified position
        roll.place_biscuit(biscuits[b_idx], start)
    # print the iteration number and the total value of the roll
    print(f"Iteration {iteration}: Total Value = {roll.total_value}")
    # display the roll with its current state (biscuits and defects)
    roll.display()


# Initialize roll and defects
main_roll = Roll(500)

# Load defects into the roll
for i in range(defect.shape[0]):
    main_roll.place_defect(defect['class'].iloc[i], int(defect['x'].iloc[i]))

# Initialize a better initial solution
initial_solution = initialize_solution(main_roll, BISCUIT_LIST)

# Run Local Search with visualization for debugging
optimized_solution, optimized_value = local_search(main_roll, BISCUIT_LIST, initial_solution, max_iterations=200)

# Output results
print("Optimized Total Value:", optimized_value)
print("Optimized Solution:", optimized_solution)

# Final visualization
visualize_roll(optimized_solution, main_roll, BISCUIT_LIST, "Final")

Optimized Total Value: 682.0
Optimized Solution: [(3, 2), (3, 10), (3, 15), (3, 24), (3, 29), (3, 41), (3, 52), (3, 58), (3, 63), (3, 68), (3, 77), (3, 84), (3, 99), (3, 104), (3, 126), (3, 131), (3, 144), (3, 149), (3, 158), (3, 167), (3, 172), (3, 179), (3, 189), (3, 195), (3, 200), (3, 205), (3, 210), (3, 215), (3, 220), (3, 225), (3, 230), (3, 235), (3, 247), (3, 252), (3, 257), (3, 262), (3, 267), (3, 281), (3, 286), (3, 294), (3, 302), (3, 307), (3, 317), (3, 322), (3, 327), (3, 333), (3, 338), (3, 343), (3, 348), (3, 356), (3, 375), (3, 383), (3, 388), (3, 393), (3, 402), (3, 407), (3, 412), (3, 417), (3, 422), (3, 439), (3, 447), (3, 452), (3, 457), (3, 462), (3, 467), (3, 472), (3, 485), (3, 490), (0, 20), (0, 36), (0, 46), (0, 73), (0, 89), (0, 93), (0, 109), (0, 114), (0, 118), (0, 122), (0, 136), (0, 140), (0, 242), (0, 273), (0, 277), (0, 312), (0, 361), (0, 365), (0, 369), (0, 398), (0, 427), (0, 431), (0, 435), (0, 477), (0, 495), (2, 7), (2, 34), (2, 154), (2, 164), (2, 185), (2, 291), (2, 353), (2, 380), (2, 444)]
Iteration Final: Total Value = 703
Total Value: 703


import matplotlib.pyplot as plt

def plot_local_search_value_progression(value_progression):
    """
    Plot the progression of total value during the local search process.

    Parameters:
    - value_progression: A list of total values obtained at each iteration.
    """
    plt.figure(figsize=(10, 6))
    plt.plot(range(len(value_progression)), value_progression, marker="o", color="blue", label="Total Value")
    plt.title("Value Progression During Local Search", fontsize=14, weight="bold")
    plt.xlabel("Iteration", fontsize=12)
    plt.ylabel("Total Value", fontsize=12)
    plt.grid(linestyle="--", alpha=0.7)
    plt.legend()
    plt.tight_layout()
    plt.show()

# Example value progression during local search
local_search_value_progression = [100, 200, 300, 400, 450, 470, 500, 520, 530, 540]  # Replace with actual progression
plot_local_search_value_progression(local_search_value_progression)


from ortools.sat.python import cp_model
import pandas as pd
import numpy as np

# Load defects data
defects = pd.read_csv('defects.csv')
defects['x'] = defects['x'].astype(int)

# Problem parameters
ROLL_LENGTH = 500
BISCUITS = [
    {"length": 4, "value": 3, "max_defects": {"a": 4, "b": 2, "c": 3}},
    {"length": 8, "value": 12, "max_defects": {"a": 5, "b": 4, "c": 4}},
    {"length": 2, "value": 1, "max_defects": {"a": 1, "b": 2, "c": 1}},
    {"length": 5, "value": 8, "max_defects": {"a": 2, "b": 3, "c": 2}},
]

# Prepare defect data for constraints
defect_counts = {
    x: defects[defects['x'] == x]['class'].value_counts().to_dict()
    for x in range(ROLL_LENGTH)
}

# Fill missing defect classes with 0
defect_counts = {
    x: {cls: defect_counts[x].get(cls, 0) for cls in ['a', 'b', 'c']}
    for x in range(ROLL_LENGTH)
}

# Create the model
model = cp_model.CpModel()

# Variables
placement = {i: model.NewBoolVar(f'placement_{i}') for i in range(ROLL_LENGTH)}
biscuit_type = {
    (i, b): model.NewBoolVar(f'biscuit_{i}_{b}') for i in range(ROLL_LENGTH) for b in range(len(BISCUITS))
}
used_positions = {i: model.NewBoolVar(f'used_{i}') for i in range(ROLL_LENGTH)}

# Constraints
for i in range(ROLL_LENGTH):
    model.Add(sum(biscuit_type[i, b] for b in range(len(BISCUITS))) <= 1)
    model.Add(used_positions[i] == sum(biscuit_type[j, b] for b in range(len(BISCUITS)) for j in range(max(0, i - BISCUITS[b]['length'] + 1), i + 1)))

for b, biscuit in enumerate(BISCUITS):
    for i in range(ROLL_LENGTH - biscuit['length'] + 1):
        covered_positions = range(i, i + biscuit['length'])
        for defect_class, max_count in biscuit['max_defects'].items():
            model.Add(
                sum(defect_counts[pos].get(defect_class, 0) for pos in covered_positions) <= max_count
            ).OnlyEnforceIf(biscuit_type[i, b])

# Objective: Maximize value and minimize penalty
value = sum(
    biscuit['value'] * biscuit_type[i, b]
    for b, biscuit in enumerate(BISCUITS)
    for i in range(ROLL_LENGTH - biscuit['length'] + 1)
)

penalty = sum(
    1 - used_positions[i] for i in range(ROLL_LENGTH)
)

model.Maximize(value - penalty)

# Solve the model
solver = cp_model.CpSolver()
status = solver.Solve(model)

# Output solution
if status == cp_model.OPTIMAL or status == cp_model.FEASIBLE:
    print(f"Total value: {solver.ObjectiveValue()}")
    solution = []
    roll_visual = ["-" for _ in range(ROLL_LENGTH)]
    for i in range(ROLL_LENGTH):
        for b, biscuit in enumerate(BISCUITS):
            if solver.Value(biscuit_type[i, b]):
                solution.append((i, b))
                for pos in range(i, i + BISCUITS[b]['length']):
                    roll_visual[pos] = str(b)
    print(f"Optimized Solution: {solution}")
    print("\nFinal Roll Visualization:")
    print("".join(roll_visual))
else:
    print("No solution found.")

Total value: 715.0
Optimized Solution: [(0, 1), (8, 1), (16, 1), (24, 3), (29, 2), (31, 3), (36, 0), (40, 1), (48, 2), (50, 0), (54, 3), (59, 0), (63, 3), (68, 1), (76, 1), (84, 3), (89, 1), (98, 1), (106, 2), (108, 3), (114, 0), (119, 1), (127, 3), (132, 1), (140, 0), (144, 3), (149, 1), (158, 1), (167, 1), (176, 1), (185, 2), (187, 1), (195, 3), (200, 3), (205, 3), (210, 3), (215, 3), (220, 3), (225, 2), (227, 3), (232, 3), (237, 3), (242, 1), (250, 3), (255, 3), (260, 3), (265, 3), (270, 1), (278, 1), (286, 1), (294, 1), (302, 3), (307, 3), (312, 1), (320, 3), (325, 3), (330, 1), (338, 3), (343, 3), (348, 3), (353, 0), (357, 1), (365, 0), (369, 0), (373, 1), (381, 2), (383, 3), (388, 3), (393, 3), (398, 1), (406, 1), (414, 3), (419, 3), (424, 1), (432, 1), (440, 3), (445, 1), (453, 1), (461, 3), (466, 3), (471, 1), (479, 1), (487, 1), (495, 3)]

Final Roll Visualization:
1111111111111111111111113333322333330000111111112200003333300003333311111111111111113333311111111-111111112233333-0000-11111111333331111111100003333311111111-11111111-11111111-11111111-221111111133333333333333333333333333333322333333333333333111111113333333333333333333311111111111111111111111111111111333333333311111111333333333311111111333333333333333000011111111000000001111111122333333333333333111111111111111133333333331111111111111111333331111111111111111333333333311111111111111111111111133333


# Function to solve with iterative refinement
def solve_iterative_csp(biscuits, roll_length, defect_counts, iterations=5):
    best_value = 0
    best_solution = None
    best_visualization = None

    for it in range(1, iterations + 1):
        print(f"\nIteration {it} - Refining Constraints")

        # Adjust defect thresholds
        relaxation_factor = 1 + (iterations - it) * 0.1  # Gradually relax thresholds
        adjusted_biscuits = [
            {
                "length": b["length"],
                "value": b["value"],
                "max_defects": {
                    k: int(v * relaxation_factor) for k, v in b["max_defects"].items()
                },
            }
            for b in biscuits
        ]

        # Create the model
        model = cp_model.CpModel()

        # Variables
        biscuit_type = {
            (i, b): model.NewBoolVar(f'biscuit_{i}_{b}')
            for i in range(roll_length)
            for b in range(len(adjusted_biscuits))
        }
        used_positions = {i: model.NewBoolVar(f'used_{i}') for i in range(roll_length)}

        # Constraints
        for i in range(roll_length):
            model.Add(sum(biscuit_type[i, b] for b in range(len(adjusted_biscuits))) <= 1)
            model.Add(
                used_positions[i]
                == sum(
                    biscuit_type[j, b]
                    for b in range(len(adjusted_biscuits))
                    for j in range(max(0, i - adjusted_biscuits[b]["length"] + 1), i + 1)
                )
            )

        for b, biscuit in enumerate(adjusted_biscuits):
            for i in range(roll_length - biscuit["length"] + 1):
                covered_positions = range(i, i + biscuit["length"])
                for defect_class, max_count in biscuit["max_defects"].items():
                    model.Add(
                        sum(defect_counts[pos].get(defect_class, 0) for pos in covered_positions)
                        <= max_count
                    ).OnlyEnforceIf(biscuit_type[i, b])

        # Objective: Maximize value and minimize penalty
        value = sum(
            biscuit["value"] * biscuit_type[i, b]
            for b, biscuit in enumerate(adjusted_biscuits)
            for i in range(roll_length - biscuit["length"] + 1)
        )
        penalty = sum(1 - used_positions[i] for i in range(roll_length))

        model.Maximize(value - penalty)

        # Solve the model
        solver = cp_model.CpSolver()
        solver.parameters.max_time_in_seconds = 120  # Limit time per iteration
        status = solver.Solve(model)

        if status == cp_model.OPTIMAL or status == cp_model.FEASIBLE:
            current_value = solver.ObjectiveValue()
            solution = []
            roll_visual = ["-" for _ in range(roll_length)]
            for i in range(roll_length):
                for b, biscuit in enumerate(adjusted_biscuits):
                    if solver.Value(biscuit_type[i, b]):
                        solution.append((i, b))
                        for pos in range(i, i + biscuit["length"]):
                            roll_visual[pos] = str(b)

            # Check if current solution is better
            if current_value > best_value:
                best_value = current_value
                best_solution = solution
                best_visualization = "".join(roll_visual)

            print(f"Iteration {it} Value: {current_value}")

    # Output the best solution
    print("\nFinal Best Solution:")
    print(f"Total Value: {best_value}")
    print(f"Optimized Solution: {best_solution}")
    print("\nFinal Roll Visualization:")
    print(best_visualization)


# Run the iterative solver
solve_iterative_csp(BISCUITS, ROLL_LENGTH, defect_counts, iterations=5)

Iteration 1 - Refining Constraints
Iteration 1 Value: 752.0

Iteration 2 - Refining Constraints
Iteration 2 Value: 748.0

Iteration 3 - Refining Constraints
Iteration 3 Value: 725.0

Iteration 4 - Refining Constraints
Iteration 4 Value: 715.0

Iteration 5 - Refining Constraints
Iteration 5 Value: 715.0

Final Best Solution:
Total Value: 752.0
Optimized Solution: [(0, 1), (8, 1), (16, 3), (21, 1), (29, 3), (34, 3), (39, 1), (47, 1), (55, 1), (63, 1), (71, 1), (79, 3), (84, 3), (89, 1), (99, 3), (104, 1), (112, 1), (120, 1), (128, 3), (133, 1), (141, 1), (149, 1), (157, 3), (162, 0), (167, 1), (176, 1), (185, 2), (187, 1), (195, 3), (200, 3), (205, 3), (210, 3), (215, 3), (220, 3), (225, 3), (230, 3), (235, 3), (240, 1), (248, 3), (253, 1), (261, 3), (266, 3), (271, 3), (276, 1), (284, 3), (289, 3), (294, 1), (302, 3), (307, 3), (312, 1), (320, 3), (325, 3), (330, 1), (338, 3), (343, 3), (348, 1), (356, 2), (358, 1), (366, 1), (374, 1), (382, 3), (387, 3), (392, 3), (397, 3), (402, 1), (410, 3), (415, 3), (420, 3), (425, 1), (433, 1), (441, 3), (446, 1), (454, 3), (459, 3), (464, 3), (469, 3), (474, 1), (482, 1), (490, 3), (495, 3)]

Final Roll Visualization:
1111111111111111333331111111133333333331111111111111111111111111111111111111111333333333311111111--3333311111111111111111111111133333111111111111111111111111333330000-11111111-11111111-221111111133333333333333333333333333333333333333333333311111111333331111111133333333333333311111111333333333311111111333333333311111111333333333311111111333333333311111111221111111111111111111111113333333333333333333311111111333333333333333111111111111111133333111111113333333333333333333311111111111111113333333333


import matplotlib.pyplot as plt
import numpy as np

def plot_occupied_positions(roll, placements, biscuits):
    """
    Plot the occupied vs. unused positions for a given roll and solution.
    """
    # Reset the roll and place biscuits based on the solution
    roll.reset_roll()
    occupied = np.zeros(roll.size)

    # Simulate the placements
    for start, b_idx in placements:
        biscuit = biscuits[b_idx]
        if roll.place_biscuit(biscuit, start):
            occupied[start:start + biscuit['length']] = 1

    # Plotting
    plt.figure(figsize=(12, 4))
    plt.bar(range(roll.size), occupied, color="skyblue", alpha=0.8, edgecolor="black")
    plt.title("Occupied vs. Unused Positions", fontsize=14, weight="bold")
    plt.ylabel("Occupied (1) / Unused (0)", fontsize=12)
    plt.xlabel("Position on Roll", fontsize=12)
    plt.ylim(0, 1.2)
    plt.grid(axis="y", linestyle="--", alpha=0.7)
    plt.tight_layout()
    plt.show()

# Call the function to plot
plot_occupied_positions(main_roll, optimized_solution, BISCUIT_LIST)


import time
from ortools.sat.python import cp_model
import pandas as pd

# Load defects data
defects = pd.read_csv('defects.csv')
defects['x'] = defects['x'].astype(int)

# Problem parameters
ROLL_LENGTH = 500
BISCUITS = [
    {"length": 4, "value": 3, "max_defects": {"a": 4, "b": 2, "c": 3}},
    {"length": 8, "value": 12, "max_defects": {"a": 5, "b": 4, "c": 4}},
    {"length": 2, "value": 1, "max_defects": {"a": 1, "b": 2, "c": 1}},
    {"length": 5, "value": 8, "max_defects": {"a": 2, "b": 3, "c": 2}},
]

# Prepare defect data for constraints
defect_counts = {
    x: defects[defects['x'] == x]['class'].value_counts().to_dict()
    for x in range(ROLL_LENGTH)
}

# Fill missing defect classes with 0
defect_counts = {
    x: {cls: defect_counts[x].get(cls, 0) for cls in ['a', 'b', 'c']}
    for x in range(ROLL_LENGTH)
}

# Old CSP Code
def solve_old_csp():
    model = cp_model.CpModel()
    biscuit_type = {
        (i, b): model.NewBoolVar(f'biscuit_{i}_{b}')
        for i in range(ROLL_LENGTH)
        for b in range(len(BISCUITS))
    }
    used_positions = {i: model.NewBoolVar(f'used_{i}') for i in range(ROLL_LENGTH)}

    for i in range(ROLL_LENGTH):
        model.Add(sum(biscuit_type[i, b] for b in range(len(BISCUITS))) <= 1)
        model.Add(
            used_positions[i]
            == sum(
                biscuit_type[j, b]
                for b in range(len(BISCUITS))
                for j in range(max(0, i - BISCUITS[b]["length"] + 1), i + 1)
            )
        )

    for b, biscuit in enumerate(BISCUITS):
        for i in range(ROLL_LENGTH - biscuit["length"] + 1):
            covered_positions = range(i, i + biscuit["length"])
            for defect_class, max_count in biscuit["max_defects"].items():
                model.Add(
                    sum(defect_counts[pos].get(defect_class, 0) for pos in covered_positions)
                    <= max_count
                ).OnlyEnforceIf(biscuit_type[i, b])

    value = sum(
        biscuit["value"] * biscuit_type[i, b]
        for b, biscuit in enumerate(BISCUITS)
        for i in range(ROLL_LENGTH - biscuit["length"] + 1)
    )
    penalty = sum(1 - used_positions[i] for i in range(ROLL_LENGTH))

    model.Maximize(value - penalty)

    solver = cp_model.CpSolver()
    start_time = time.time()
    status = solver.Solve(model)
    exec_time = time.time() - start_time

    if status in (cp_model.OPTIMAL, cp_model.FEASIBLE):
        total_value = solver.ObjectiveValue()
    else:
        total_value = 0

    return total_value, exec_time

# New Heuristic-Enhanced CSP Code
def solve_new_csp():
    best_value = 0
    model = cp_model.CpModel()

    for iteration in range(1, 6):
        relaxation_factor = 1 + (5 - iteration) * 0.1
        adjusted_biscuits = [
            {
                "length": b["length"],
                "value": b["value"],
                "max_defects": {k: int(v * relaxation_factor) for k, v in b["max_defects"].items()},
            }
            for b in BISCUITS
        ]

        biscuit_type = {
            (i, b): model.NewBoolVar(f'biscuit_{i}_{b}')
            for i in range(ROLL_LENGTH)
            for b in range(len(adjusted_biscuits))
        }
        used_positions = {i: model.NewBoolVar(f'used_{i}') for i in range(ROLL_LENGTH)}

        for i in range(ROLL_LENGTH):
            model.Add(sum(biscuit_type[i, b] for b in range(len(adjusted_biscuits))) <= 1)
            model.Add(
                used_positions[i]
                == sum(
                    biscuit_type[j, b]
                    for b in range(len(adjusted_biscuits))
                    for j in range(max(0, i - adjusted_biscuits[b]["length"] + 1), i + 1)
                )
            )

        for b, biscuit in enumerate(adjusted_biscuits):
            for i in range(ROLL_LENGTH - biscuit["length"] + 1):
                covered_positions = range(i, i + biscuit["length"])
                for defect_class, max_count in biscuit["max_defects"].items():
                    model.Add(
                        sum(defect_counts[pos].get(defect_class, 0) for pos in covered_positions)
                        <= max_count
                    ).OnlyEnforceIf(biscuit_type[i, b])

        value = sum(
            biscuit["value"] * biscuit_type[i, b]
            for b, biscuit in enumerate(adjusted_biscuits)
            for i in range(ROLL_LENGTH - biscuit["length"] + 1)
        )
        penalty = sum(1 - used_positions[i] for i in range(ROLL_LENGTH))

        model.Maximize(value - penalty)

        solver = cp_model.CpSolver()
        solver.parameters.max_time_in_seconds = 120
        start_time = time.time()
        status = solver.Solve(model)
        exec_time = time.time() - start_time

        if status in (cp_model.OPTIMAL, cp_model.FEASIBLE):
            current_value = solver.ObjectiveValue()
            if current_value > best_value:
                best_value = current_value

    return best_value, exec_time

# Compare Results
old_value, old_time = solve_old_csp()
new_value, new_time = solve_new_csp()

print("\nComparison:")
print(f"Old CSP: Total Value = {old_value}, Execution Time = {old_time:.2f}s")
print(f"New CSP: Total Value = {new_value}, Execution Time = {new_time:.2f}s")

Comparison:
Old CSP: Total Value = 715.0, Execution Time = 0.23s
New CSP: Total Value = 752.0, Execution Time = 0.44s

	x	class
0	355.449335	c
1	92.496236	a
2	141.876795	c
3	431.833902	c
4	435.028461	c

	120	121	122	123	124	125	126	127	128	129	130	131	132	133	134	135	136	137	138	139
0	{'a': 0, 'b': 0, 'c': 1}	{'a': 0, 'b': 0, 'c': 1}	{'a': 0, 'b': 1, 'c': 0}	{'a': 0, 'b': 1, 'c': 1}	{'a': 1, 'b': 0, 'c': 0}	{'a': 3, 'b': 0, 'c': 1}	{'a': 0, 'b': 0, 'c': 0}	{'a': 0, 'b': 1, 'c': 0}	{'a': 0, 'b': 0, 'c': 1}	{'a': 0, 'b': 1, 'c': 1}	{'a': 0, 'b': 0, 'c': 0}	{'a': 0, 'b': 0, 'c': 0}	{'a': 0, 'b': 0, 'c': 0}	{'a': 0, 'b': 0, 'c': 0}	{'a': 0, 'b': 0, 'c': 0}	{'a': 0, 'b': 0, 'c': 0}	{'a': 0, 'b': 0, 'c': 1}	{'a': 0, 'b': 0, 'c': 1}	{'a': 0, 'b': 0, 'c': 0}	{'a': 0, 'b': 1, 'c': 1}
1	_	_	_	_	_	_	_	_	_	_	_	_	_	_	_	_	_	_	_	_

	140	141	142	143	144	145	146	147	148	149	150	151	152	153	154	155	156	157	158	159
0	{'a': 1, 'b': 0, 'c': 0}	{'a': 0, 'b': 1, 'c': 1}	{'a': 0, 'b': 0, 'c': 1}	{'a': 2, 'b': 0, 'c': 1}	{'a': 1, 'b': 0, 'c': 0}	{'a': 0, 'b': 0, 'c': 1}	{'a': 0, 'b': 1, 'c': 1}	{'a': 0, 'b': 0, 'c': 0}	{'a': 0, 'b': 1, 'c': 0}	{'a': 0, 'b': 0, 'c': 1}	{'a': 0, 'b': 0, 'c': 1}	{'a': 0, 'b': 0, 'c': 0}	{'a': 0, 'b': 0, 'c': 0}	{'a': 0, 'b': 1, 'c': 0}	{'a': 1, 'b': 1, 'c': 1}	{'a': 0, 'b': 0, 'c': 0}	{'a': 1, 'b': 1, 'c': 0}	{'a': 0, 'b': 3, 'c': 0}	{'a': 1, 'b': 0, 'c': 0}	{'a': 1, 'b': 0, 'c': 1}
1	_	_	_	_	_	_	_	_	_	_	_	_	_	_	_	_	_	_	_	_

	160	161	162	163	164	165	166	167	168	169	170	171	172	173	174	175	176	177	178	179
0	{'a': 0, 'b': 0, 'c': 0}	{'a': 0, 'b': 1, 'c': 0}	{'a': 0, 'b': 0, 'c': 0}	{'a': 3, 'b': 1, 'c': 1}	{'a': 0, 'b': 0, 'c': 0}	{'a': 0, 'b': 0, 'c': 1}	{'a': 1, 'b': 3, 'c': 0}	{'a': 0, 'b': 0, 'c': 0}	{'a': 0, 'b': 2, 'c': 0}	{'a': 1, 'b': 0, 'c': 0}	{'a': 0, 'b': 0, 'c': 0}	{'a': 1, 'b': 1, 'c': 1}	{'a': 1, 'b': 0, 'c': 1}	{'a': 0, 'b': 1, 'c': 0}	{'a': 0, 'b': 0, 'c': 1}	{'a': 0, 'b': 0, 'c': 0}	{'a': 0, 'b': 1, 'c': 0}	{'a': 0, 'b': 0, 'c': 0}	{'a': 0, 'b': 0, 'c': 2}	{'a': 0, 'b': 2, 'c': 1}
1	_	_	_	_	_	_	_	_	_	_	_	_	_	_	_	_	_	_	_	_

	180	181	182	183	184	185	186	187	188	189	190	191	192	193	194	195	196	197	198	199
0	{'a': 0, 'b': 0, 'c': 0}	{'a': 0, 'b': 0, 'c': 0}	{'a': 0, 'b': 0, 'c': 0}	{'a': 0, 'b': 0, 'c': 1}	{'a': 0, 'b': 3, 'c': 3}	{'a': 0, 'b': 1, 'c': 0}	{'a': 0, 'b': 1, 'c': 0}	{'a': 0, 'b': 1, 'c': 0}	{'a': 3, 'b': 0, 'c': 0}	{'a': 1, 'b': 0, 'c': 0}	{'a': 1, 'b': 1, 'c': 0}	{'a': 0, 'b': 1, 'c': 1}	{'a': 0, 'b': 1, 'c': 0}	{'a': 0, 'b': 0, 'c': 0}	{'a': 0, 'b': 0, 'c': 1}	{'a': 0, 'b': 0, 'c': 0}	{'a': 0, 'b': 0, 'c': 1}	{'a': 0, 'b': 0, 'c': 0}	{'a': 0, 'b': 0, 'c': 1}	{'a': 0, 'b': 0, 'c': 0}
1	_	_	_	_	_	_	_	_	_	_	_	_	_	_	_	_	_	_	_	_

1. Describe the problem and its challenges¶

1. Problem description¶

2. Challenges¶

3. Goals of the Project¶

2. Formulating and implementing the problem using Python¶

Creating the Main Roll with its defects¶

Two alternative problem-solving approaches¶

1- Local search¶

Value: 682.0:¶

Value: 703.0:¶

Local Search is faster but may not always find the optimal solution.¶

2- CSP USING OR TOOLS¶

Total Value: 715.0¶

CSP ensures global feasibility of solutions but may leave unused gaps due to strict constraints.¶

Other approach : Dynamic Programming¶

Testing¶

	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19
0	{'a': 2, 'b': 0, 'c': 0}	{'a': 1, 'b': 0, 'c': 0}	{'a': 1, 'b': 1, 'c': 0}	{'a': 1, 'b': 1, 'c': 0}	{'a': 0, 'b': 0, 'c': 0}	{'a': 0, 'b': 0, 'c': 0}	{'a': 0, 'b': 0, 'c': 0}	{'a': 0, 'b': 0, 'c': 0}	{'a': 0, 'b': 0, 'c': 1}	{'a': 0, 'b': 0, 'c': 2}	{'a': 0, 'b': 1, 'c': 1}	{'a': 0, 'b': 0, 'c': 0}	{'a': 1, 'b': 0, 'c': 0}	{'a': 0, 'b': 0, 'c': 0}	{'a': 1, 'b': 0, 'c': 0}	{'a': 0, 'b': 0, 'c': 0}	{'a': 1, 'b': 0, 'c': 1}	{'a': 0, 'b': 0, 'c': 0}	{'a': 0, 'b': 0, 'c': 0}	{'a': 0, 'b': 1, 'c': 0}
1	_	_	_	_	_	_	_	_	_	_	_	_	_	_	_	_	_	_	_	_

	240	241	242	243	244	245	246	247	248	249	250	251	252	253	254	255	256	257	258	259
0	{'a': 0, 'b': 0, 'c': 1}	{'a': 0, 'b': 3, 'c': 1}	{'a': 3, 'b': 1, 'c': 0}	{'a': 0, 'b': 0, 'c': 0}	{'a': 0, 'b': 0, 'c': 1}	{'a': 0, 'b': 1, 'c': 0}	{'a': 1, 'b': 0, 'c': 1}	{'a': 0, 'b': 0, 'c': 1}	{'a': 0, 'b': 1, 'c': 1}	{'a': 0, 'b': 0, 'c': 0}	{'a': 0, 'b': 0, 'c': 0}	{'a': 1, 'b': 1, 'c': 0}	{'a': 0, 'b': 0, 'c': 0}	{'a': 1, 'b': 0, 'c': 1}	{'a': 0, 'b': 0, 'c': 0}	{'a': 0, 'b': 0, 'c': 1}	{'a': 0, 'b': 0, 'c': 0}	{'a': 0, 'b': 1, 'c': 1}	{'a': 0, 'b': 1, 'c': 0}	{'a': 0, 'b': 1, 'c': 0}
1	_	_	_	_	_	_	_	_	_	_	_	_	_	_	_	_	_	_	_	_

	400	401	402	403	404	405	406	407	408	409	410	411	412	413	414	415	416	417	418	419
0	{'a': 0, 'b': 0, 'c': 0}	{'a': 0, 'b': 1, 'c': 2}	{'a': 0, 'b': 0, 'c': 1}	{'a': 0, 'b': 1, 'c': 0}	{'a': 0, 'b': 0, 'c': 0}	{'a': 1, 'b': 1, 'c': 0}	{'a': 1, 'b': 0, 'c': 1}	{'a': 0, 'b': 0, 'c': 0}	{'a': 1, 'b': 0, 'c': 1}	{'a': 1, 'b': 0, 'c': 0}	{'a': 0, 'b': 2, 'c': 0}	{'a': 0, 'b': 0, 'c': 0}	{'a': 0, 'b': 1, 'c': 1}	{'a': 0, 'b': 1, 'c': 0}	{'a': 1, 'b': 0, 'c': 0}	{'a': 0, 'b': 0, 'c': 1}	{'a': 1, 'b': 0, 'c': 0}	{'a': 0, 'b': 0, 'c': 0}	{'a': 0, 'b': 1, 'c': 0}	{'a': 0, 'b': 0, 'c': 0}
1	_	_	_	_	_	_	_	_	_	_	_	_	_	_	_	_	_	_	_	_

	x	class
0	355	c
1	92	a
2	141	c
3	431	c
4	435	c