Your Siblings – Donation Allocation in Python

donation_allocation.py

#-*- encoding: utf-8 -*-
"""
This program is pseudo code that happens to be Python. It’s intended to
demonstrate how the algorithm works that we use to allocate donations
to projects. The actual implementation is bound to be more complex,
of course, but the principle is the same.
"""

from decimal import Decimal, ROUND_DOWN


class Project(object):

    def __init__(self, name, total, received):
        self.name = name
        self.total = total
        self.received = received

    def get_share(self, projects):
        """
        Returns the fraction of the total money needed by the project
        in the total across a list of projects.
        """
        return (
            float(self.total) /
            float(sum(project.total for project in projects))
        )


class YourSiblings(object):
    """That’s us."""

    def __init__(self):
        self.projects = []

    def add_project(self, project):
        self.projects.append(project)

    def allocate(self, donation_total):
        """
        We have a donation that needs to be allocated to our projects
        in a just and justifiable way. This algorithm does just that.

        In prose: Each project has a total, unchanging amount of money that
        it requires to achieve its ends. The larger this total is, the larger
        its share in the donation. However, no project should receive more
        money than it requires. Any extraneous money is collected and allocated
        to the remaining projects the same way.

        Often, a few cents cannot be allocated because each project would
        receive less than a cent. This unallocatable money is returned. We will
        collect it and try to allocate it again at a later time.
        """
        class Donation(object):

            def __init__(s, project):
                s.project = project
                s.amount = Decimal("0.00")
                s.ideal_amount = Decimal("0.00")

            def is_sufficient(s):
                return s.amount + s.project.received >= s.project.total

        # This list of Donation objects serves as a receptacle for all
        # information about donations that needs to be saved.
        donations = [Donation(p) for p in self.projects]
        remaining_donations = donations

        remainder = donation_total
        i = 0
        while remainder > 0:
            i += 1
            # Weeding out fully funded projects.
            remaining_donations = [
                d
                for d in remaining_donations
                if not d.is_sufficient()
            ]
            print
            print "Iteration %s:" % i
            print "    Money remaining: %s" % remainder
            print "    Ideal allocation:"
            # Calculating the ideal amount each project would receive if
            # projects could receive more money than they require.
            for donation in remaining_donations:
                donation.ideal_amount = (
                    Decimal(str(
                        donation.project.get_share(
                            [d.project for d in remaining_donations]
                        )
                    )) * remainder
                ).quantize(Decimal(".01"), ROUND_DOWN)
                print "        %s: %s" % (
                    donation.project.name,
                    donation.ideal_amount
                )
            # Break, if all projects have been fully funded (empty list) or
            # the remainder cannot be divided into portions of which at least
            # one is greater than zero cents.
            if all(d.ideal_amount == 0 for d in remaining_donations):
                break
            print "    Actual allocation:"
            for donation in remaining_donations:
                # The money that is still needed to fully fund the project.
                still_needed = d.project.total - d.project.received - d.amount
                # The donation is the ideal donation (see above) if it can
                # accommodate the complete ideal amount. Otherwise, if the
                # ideal donation exceeds the project’s needs, it receives
                # exactly as much as it requires.
                new_donation = min(donation.ideal_amount, still_needed)
                print "        %s: %s" % (donation.project.name, new_donation)
                remainder -= new_donation
                donation.amount += new_donation

        # Checking that every cent is accounted for.
        money_allocated = sum(d.amount for d in donations)
        assert money_allocated + remainder == donation_total, \
            "Allocated %s with remainder of %s, but donation was %s." % (
                money_allocated,
                remainder,
                donation_total
            )
        # Checking that no project receives more money than it requires.
        for donation in donations:
            assert donation.project.total >= \
                donation.project.received + donation.amount, \
                "%s would receive %s, but needs only %s." % (
                    donation.project.name,
                    donation.amount,
                    donation.project.total - donation.project.received
                )

        print
        print "Final allocation:"
        # Transferring the money to the projects.
        for d in donations:
            print "    %s: %s" % (d.project.name, d.amount)
            d.project.received += d.amount

        # Returning the unallocatable amount.
        return remainder


def test(donation):
    yoursiblings = YourSiblings()

    yoursiblings.add_project(Project(
        name="Project 1",
        total=Decimal("600.00"),
        received=Decimal("500.00")
    ))

    yoursiblings.add_project(Project(
        name="Project 2",
        total=Decimal("200.00"),
        received=Decimal("0.00")
    ))

    yoursiblings.add_project(Project(
        name="Project 3",
        total=Decimal("1000.00"),
        received=Decimal("900.00")
    ))

    remainder = yoursiblings.allocate(donation)

    print
    print "Unallocatable money: %s" % remainder

    print
    for project in yoursiblings.projects:
        print project.name, "has now received", project.received

if __name__ == "__main__":
    test(Decimal("200.00"))