bin_fill.py

import random

BIN_SIZE = 26
OBJECT_COUNT = 3000
MAX_OBJECT_SIZE = 25

assert MAX_OBJECT_SIZE <= BIN_SIZE # check that objects cannot be too big

class Result(): # custom result class for handling errors
    def __init__(self, err=None, ok=None, ):
        self._err = err
        self._ok = ok
        self.result = err if err is not None else ok

    def escape(self, ): # method to 'unwrap' a result: raises an error if there is one, otherwise returns the inner value
        if self._err is not None:
            raise self._err

        else:
            return self._ok

    def escape_or(self, _or, ): # method to 'unwrap' or perform a function returning another value
        if self._err is not None:
            return _or()

        else:
            return self._ok

    def is_err(self, ):
        return self._err is not None

    def is_ok(self, ):
        return self._ok is not None


class BinFullError(Exception): # custom exception for when a bin is full
    pass


class Bin(object):
    def __init__(self, bin_size: int, ): # called on initialization
        self.bin_size = bin_size
        self.objects = 0
        self._items = [] # private field containing the objects added

    def __repr__(self, ): # called on conversion to str
        return '{:.1f}% ({}/{}) {{ {}, }}'.format(
                100 * self.objects / self.bin_size,
                self.objects,
                self.bin_size,
                ', '.join(str(x) for x in self._items)
            )

    def add_object(self, size: int, ): # -> Result(ok: int, err: BinFullError)
        if self.objects + size <= self.bin_size:
            self.objects += size
            self._items.append(size)

            return Result(ok=self.objects)

        else:
            return Result(err=BinFullError)


class BinArray(object): # class representing a set of bins
    def __init__(self, ):
        self.bins = []

    def __repr__(self, ): # called on conversion to str
        return '{} bins:\n | '.format(len(self.bins)) + '\n | '.join([str(b) for b in self.bins])

    def stat(self, ): # like __repr__ but only shows stats and not contents
        b = sum(x.objects for x in self.bins)
        return '{} bins (items: {}, fullness: {}%)'.format(len(self.bins), b, 100 * b / (BIN_SIZE * len(self.bins)))

    def _add_bin(self, ): # priv method for adding a new bin
        b = Bin(BIN_SIZE)

        self.bins.append(b)

        return b

    def _iter_add(self, obj, ): # priv method for adding an item to the next bin
        b_iter = iter(self.bins)
        current = Bin(0)

        while current.add_object(o).is_err():
            try:
                current = next(b_iter)
            except StopIteration:
                self._add_bin().add_object(o)
                break

    def add_objects_first_fit(self, objects, ): # first fit method
        for o in objects:
            self._iter_add(o)

    def add_objects_first_fit_desc(self, objects, ): # first fit wrapper that sorts inputs beforehand
        new_objects = sorted(objects, reverse=True)

        self.add_objects_first_fit(new_objects)

    def add_objects_best_fit(self, objects, ): # as with above methods but sorts the bins by fullness each time an item is added
        objects = sorted(objects, reverse=True)

        for obj in objects:
            self._iter_add(obj)

            self.bins.sort(key=lambda x: x.bin_size - x.objects)

    def add_objects_bongo_fit(self, objects, ): # randomly assigns bins 
        objects = sorted(objects, reverse=False)
        while len(objects) > 0:
            rand = objects.pop(random.randint(0, len(objects) - 1))

            b = self._add_bin()
            b.add_object(rand)

            for o in objects:
                if b.add_object(o).is_err():
                    continue
                else:
                    objects.remove(o)
                    break


while True: 
    objects = [random.randint(2, MAX_OBJECT_SIZE) for _ in range(OBJECT_COUNT)]

    binar = BinArray()
    binar.add_objects_first_fit_desc(objects)


    binar2 = BinArray()
    binar2.add_objects_best_fit(objects)

    if len(binar.bins) != len(binar2.bins): # finding cases where the best fit is better than ffd
        print(objects)
        
        print('\nUsing first-fit descending:')
        print(binar.stat())
        
        print('\nUsing best-fit:')
        print(binar2.stat())