<jupyter_start><jupyter_text>**Bin Packing Code Tutorial**    In this tutorial we present an example of solving the bin packing problem. The example is divided into three sections:  Reading input data, applying a heuristic and printing the output.  Let's start by describing the state. A state consists of a number of quadratic bins (containers), boxes (2D rectangles) in the bins and unused boxes. Also, the state contains the total covered and uncoverd points.  Uncovered points are the potential placement points.  Applying a bin packing algorithm to a state transforms a state to a new condition.  Where putting a new box in a bin produces a new state. ![state.png](attachment:state.png) **Example**  The following example shows a state that contains a single bin of 6x6 dimensions. In this bin 5 boxes are packed and they cover an area of 25 points leaving 11 uncovered points.    Bin number: 1  Total uncovered points: 11  Total covered points: 25  Number of boxes: 5  Unused boxes: 0  Bin size:  6 6    Boxes (width, height) not in some bins:    Boxes (width, height, x_position, y_position, bin_id) in bins:  3 2 0 3 0  3 4 3 0 0  1 2 0 1 0  1 1 0 0 0  2 2 1 0 0    The x_position and y_position in the output file indicate the bottom left corner of the corresponding box.  These states are saved in text files, and in the following we describe the structure of input files and I/O functions.   ![plot.png](attachment:plot.png) **Code Structure** ![main.png](attachment:main.png)<jupyter_code>import Base.bp2DState
from Base.bp2DSimpleHeuristics import single_type_heuristic, first_fit, next_fit, most_enclosed_position, max_rest, \
    best_fit, first_fit_decreasing, next_fit_decreasing, get_all_heuristics, random_fit
from Base.bp2DState import State
from Base.bpReadWrite import ReadWrite
from Base.bp2DBox import Box
from Base.bpStateGenerators import random_state_generator, state_generator<jupyter_output><empty_output><jupyter_text>**Reading input data**  The input file has the following structure:The first line contains two integers *bin_width* and *bin_height* representing the bin dimensions.This is followed by *n* lines *(1<=n)* indicating that there are *n* boxes, each line containing two integers *box_width* and *box_height* representing each box dimensions.The *n* lines can also contain the following 5 integers: *box_width*, *box_height*, *box_x*, *box_y*, *bin_id*.An example is the following input file called *input* which exists in the folder *test_instances*:    6 6  1 1  2 2  3 2 0 3 0  3 4 3 0 0  1 2 0 1 0      The previous example means that we have a bin of size (6,6) and five boxes of the sizes [(1,1),(2,2),(3,2),(3,4),(1,2)].  To read this input state, we use the function *read_state* which is defined in the class *ReadWrite*. This function takes as input the file path and the returned state will be saved in the instance 'state'.<jupyter_code>state = ReadWrite.read_state("test_instances/state_small")<jupyter_output><empty_output><jupyter_text>We could also generate a new state by giving the boxes explicitely as in the following example:<jupyter_code>state_generator(path="test_instances/state_small", bin_size=(10, 10),
box_list=[(1, (1, 10)), (1, (1, 9)), (1, (9, 1)), (1, (1, 8)), (1, (8, 1)),
(1, (1, 7)), (1, (7, 1)), (1, (1, 6)), (1, (6, 6))])<jupyter_output><empty_output><jupyter_text>After reading the input, the initial state now is ready to apply a bin packing algorithm on.  **Applying a heuristic**  The second step is applying a packing heuristic to our state in order to solve the bin packing problem. We execute the *single_type_heuristic* function and assign the value True to the argument *plot_result* to trigger the *plot_packing_state* function.<jupyter_code>single_type_heuristic(state,heuristic_step=best_fit, plot_result=True)<jupyter_output><empty_output><jupyter_text>Some simple heuristics are implemented in the bp2DSimpleHeuristics.py file such as *best_fit*, *max_rest*, *random_fit*, *next_fit* and *first_fit*. Also, we can sort the boxes in a state using *sort_boxes_in_state* function.  Applying the heuristic results in a new state, and the following section shows how the outputs are written in the result file.     **Outputting the solution**The output state is saved in a text file by applying the function *write_state* and specifing the name of the output file.<jupyter_code>ReadWrite.write_state(path=f"test_instances/solution", state=state)<jupyter_output><empty_output><jupyter_text>The output file contains the state of the bin packing problem, as follows:  State of a bin packing problem:   Bin number: 1  Total uncovered points: 11  Total covered points: 25  Number of boxes: 5  Unused boxes: 0  Runtime: 0.22507309913635254    Bin size:  6 6    Boxes (width, height) not in some bins:    Boxes (width, height, x_position, y_position, bin_id) in bins:  3 2 0 3 0  3 4 3 0 0  1 2 0 1 0  1 1 0 0 0  2 2 1 0 0     In order to illustrate the solution, the plot function outputs an image saved in the vis folder.  The following figure shows the packing solution that corresponds to the previous output file.   ![plot.png](attachment:plot.png) **Feasible actions**  You can also check the validation of the solution state by applying *is_valid* function. This function:  1. verifies whether any open boxes are still without packing.  2. checks for any ovrelapping between the packed boxes.  3. checks for any intersection between the boxes and the bin wall.  4. checks if the state violates the law of physics.  5. compares the original state with the solution state.  This function returns true if the solution is valid, otherwise it returns false.   Requirements:To install the necessary requirements, we provide a environment.yml file that can be used with [anaconda](https://anaconda.org/). Of course you can use any other means of installing the requirements listed in this file. The required packages are:  ```matplotlib=3.4.2```  ```numpy=1.20.3```  The code could run using older versions as well. Conda Environment To create an environment ```autumn2021``` with the required packages, run the following command:  ```conda env create -f environment.yml```  To activate the environment and start coding, run:```conda activate autumn2021``` Jupyter NotebookIf you like to run a jupyter notebook server, just as we did, you may need to install it in your current (conda) environment.The classic Jupyter Notebook can be installed with conda:  ```conda install -c conda-forge notebook```If you use pip, you can install it with:  ```pip install notebook```To run the notebook, run the following command at the Terminal:  ```jupyter notebook```  A Large ExampleAnd now some code that runs a whole bunch of heuristics<jupyter_code>import os

import Base.bp2DState
from Base.bp2DSimpleHeuristics import single_type_heuristic, first_fit, next_fit, most_enclosed_position, max_rest, \
    best_fit, first_fit_decreasing, next_fit_decreasing, get_all_heuristics, random_fit
from Base.bp2DState import State
from Base.bpReadWrite import ReadWrite
from Base.bp2DBox import Box
from Base.bpStateGenerators import random_state_generator, state_generator


def main():
    if not os.path.exists("./vis"):
        os.mkdir("./vis")

    # Simple examples for read and write
    state = ReadWrite.read_state(path="test_instances/test_1_input")
    ReadWrite.write_state(path="test_instances/test_1_output", state=state)
    single_type_heuristic(state, heuristic_step=first_fit_decreasing)
    ReadWrite.write_state(path="test_instances/test_1_solution", state=state)

    state = ReadWrite.read_state(path="test_instances/test_1_input")
    solution = ReadWrite.read_state(path="test_instances/test_1_solution")

    # Comparison of heuristics on small state with boxes explicitely given
    state_generator(path="test_instances/state_small", bin_size=(10, 10),
                    box_list=[(1, (1, 10)), (1, (1, 9)), (1, (9, 1)), (1, (1, 8)), (1, (8, 1)),
                              (1, (1, 7)), (1, (7, 1)), (1, (1, 6)), (1, (6, 6))], seed=10)
    for name, heuristic in get_all_heuristics():
        state = ReadWrite.read_state("test_instances/state_small")
        single_type_heuristic(state, heuristic, plot_result=True, plot_name=name)
        ReadWrite.write_state(path=f"test_instances/solution_small_{name}", state=state)

        state = ReadWrite.read_state("test_instances/state_random_big")
        solution = ReadWrite.read_state(path=f"test_instances/solution_big_{name}")
        print(f"Is solution of {name} valid? {solution.is_valid(state)}!")

    # Comparison of heuristics on random state
    random_state_generator(path="test_instances/state_random_big", bin_size=(10, 10), box_width_min=2,
                           box_num=1000)
    for name, heuristic in get_all_heuristics():
        state = ReadWrite.read_state("test_instances/state_random_big")
        single_type_heuristic(state, heuristic)
        ReadWrite.write_state(path=f"test_instances/solution_big_{name}", state=state)

        state = ReadWrite.read_state("test_instances/state_random_big")
        solution = ReadWrite.read_state(path=f"test_instances/solution_big_{name}")
        print(f"Is solution of {name} valid? {solution.is_valid(state)}!")

if __name__ == '__main__':
    main()<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.08699860200021507, 'fraction_numerical': 0.025594149908592323, 'mean_word_length': 4.787181082762912, 'pattern_counts': {'":': 0, '<': 26, '<?xml version=': 0, '>': 25, 'https://': 1, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 1, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '6', 'dir': 'jupyter-structured-clean-dedup', 'id': '236552', 'license': 'MIT', 'n_tokens_mistral': 2935, 'n_tokens_neox': 2706, 'n_words': 1104, 'path': 'Tutorial.ipynb', 'repo_name': 'ML2R-center/autumn2021-base', 'size': '9299'}