'''
I am organizing a holiday tour and I've got a lot of families registered, each family consists of 1-10 people
We will be traveling by vans, and each van can fit a maximum of 10 people.
The family members cannot be separated.
To save on cost, I want to hire as few vans as possible.
How do I write the code to determine the number of vans to hire, and which families travel together in the same van?
I was thinking to brute force it, as in sort the number of members in a family from smallest to largest, then add the largest to it. However, seems to be wrong on certain scenarios.
For example this scenario:

[2, 2, 4, 4, 4, 4, 5, 5]
based on that logic, it will be solved as follows
[2, 5, 2]
[4, 5]
[4, 4]
[4]

but the optimal way would be
[5, 5]
[4, 4, 2]
[4, 4, 2]
'''

from random import randint

NUMBER_OF_FAMILIES = 10

class Family():
    '''
    This class holds data for a family.

    name    -> string - auto-generated by the Organiser class
    members -> int    - number of family members

    '''
    def __init__(self, name, members):
        self.name = name
        self.members = members

    def __gt__(self, other):
        if self.members > other.members:
            return True
        else:
            return False

    def __lt__(self, other):
        if self.members <  other.members:
            return True
        else:
            return False

class Van():
    '''
    This class handles individual vans.

    name     -> string                 - auto-generated by the Organiser class
    spaces   -> int                    - 10 by default
    fmailies -> list of Family objects - all the Families who got in this Van
    '''
    def __init__(self, name):
        self.name = name
        self.spaces = 10
        self.families = []

    def get_passengers(self):
        '''
        Lists all the families in the van.
        '''
        print("Name: {} Spaces taken: {}\n\tFamilies in van:".format(self.name, 10-self.spaces))
        for family in self.families:
            print("\t\tFamily: {} Number of passengers: {}".format(family.name, family.members))

    def has_space(self, family):
        '''
        family -> Family object - the family who tries to get in the Van

        Returns True if the Family can fit in the Van
        '''
        if self.spaces - family.members >= 0:
            return True
        else:
            return False

    def add_passengers(self, family):
        '''
        family -> a Family object - the family who tries to get in the Van
        If Family can fit in the Van it adds it to self.families
        and returns True.
        '''
        if not self.has_space(family):
            return False
        else:
            # add Family and subtract their number from the available spaces
            self.families.append(family)
            self.spaces -= family.members
            return True

    def __gt__(self, other):
        if self.spaces > other.spaces:
            return True
        else:
            return False

    def __lt__(self, other):
        if self.spaces <  other.spaces:
            return True
        else:
            return False


class Organiser():
    '''
    This class is a collection of different methods to organise families into vans.
    It's instantiated with the number of fmailies to accomodate.
    '''
    def __init__(self, num_families):
        self.num_families = num_families

        # generating families
        self.families = []
        for i in range(1, self.num_families+1):
            self.families.append(Family('Family'+str(i), randint(1,10)))
        self.families.sort(reverse=True)

    def brute_organise(self):
        '''
        This method will get a new van as soon as it couldn't put a family into the last one.
        It means that it will not try to find another van with sufficient space.
        For example if we have 3 vans with 4, 8, and 6 people and a family of 6 comes next it won't
        realise that they can fit in the first one but it will order another empty van.
        '''
        ####### set up variables
        vans = [] # all the vans that we ordered
        full_vans = [] # vans that we've already filled up
        van_number = 0 # id for vans
        no_van_available = True # whether the last try to insert a family into a van was successful

        ####### start sorting families
        while True:
            # if it's the first time this loop runs or the last
            # or the current can doesn't have free space for the last family
            # we order a new van
            if no_van_available:
                van_number += 1
                vans.append(Van("Van"+str(van_number)))

            vans.sort()
            # current van
            van = vans.pop()

            # if there are no more families to insert
            # we print the results and end
            if len(self.families) == 0:
                print("No more families.")
                # adding incomplete vans to full_vans
                full_vans.append(van) # current van
                for v in vans:
                    if v.spaces < 10:
                        full_vans.append(v)
                # print all vans
                for fv in full_vans:
                    fv.get_passengers()
                break
            else:
                # get next family
                family = self.families.pop()
                # find out whether they fit
                got_in = van.add_passengers(family)
                # if they do we don't necessarily need a new van
                if got_in:
                    no_van_available = False
                    print("{} with {} members get in {} which has {} spaces".format(family.name, family.members, van.name, van.spaces))
                else:
                    self.families.append(family)
                    no_van_available = True
                # if van is full we put it in the full_vans
                # and ask for another one
                if van.spaces == 0:
                    full_vans.append(van)
                    no_van_available = True
                    print("{} is full.".format(van.name))
                else:
                    # if not full we put it back in the basket
                    vans.append(van)

if __name__ == '__main__':
    org = Organiser(NUMBER_OF_FAMILIES)
    org.brute_organise()