Skip to content

Instantly share code, notes, and snippets.

@JellyWX
Last active February 27, 2019 09:34
Show Gist options
  • Save JellyWX/f94858e38cdbc04886e1a872f3d9a6ca to your computer and use it in GitHub Desktop.
Save JellyWX/f94858e38cdbc04886e1a872f3d9a6ca to your computer and use it in GitHub Desktop.
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())
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment