Capital Match Hiring Coding Challenge

Introduction

Archaeologists and anthropologists would have a hard time believing that millenia ago, there was already a healthy and booming democracy. Yet recent evidence surfaced suggested that in the ancient Kingdom of Malodivo, the democratic way of life was the norm, even though it is a bit peculiar by modern standards. Not much was known about this Kingdom; about the only thing we have fully figured out was its parliamentary system of governance, owing to the fact that the sole piece of written evidence was the Kingdom's Parliamentary Gazette, a document recording the discussions and resolutions of the various bills in its Parliament.

Reading through the Gazette, we can now piece together a few tidbits of the workings of the Parliament. The Parliament apparently meets every once in a while (the exact frequency is unknown because we have not yet figured out conversions between the Gregorian calendar and the calendar system used in the Kingdom), and the members, who represent the constituents in districts, submit bills for discussion and debate. The implementation of a bill requires funding, naturally. Such funding is provided by the taxes paid by the members of the parliament which ultimately comes from their constituents. In other words, instead of each citizen paying taxes individually to a central authority, each citizen pays the taxes to their elected members of the Parliament.

Different members of the parliament have different priorities and have different levels of support for each bill. They signal their varying degrees of support through funding decisions: they would pledge different amounts of their constituents' tax dollars to each bill. It would be easy if the sum of the funds needed by all bills is equal to all the taxes collected; in this case, the members' wishes could be fulfilled exactly. However, more often than not, this does not happen. Owing to a booming economy, the total amount of funding required for all bills is often less than the total tax paid by all members. In this case, a widely cherished Article in the Tax Code of the Kingdom of Malodivo comes into effect:

Article XIV. All taxes collected by the Government but not used for the implementation of any bill shall be refunded.

Since the Parliament usually cannot pass enough bills to deplete the total taxes it collected, it will simply reduce the amount of tax paid, and the members will have a leftover amount. The citizens are happy because their effective tax rate is reduced. It is important that once the Parliament has decided on the funding needed for a bill, the bill cannot legally receive extra funds; it is however possible that a bill will receive less funds than the Parliament decides.

Your task, is to write a program to determine the best combination of the funds from each member of the Parliament that go to each bill.

Scenario

Suppose in the 137th Parliamentary Session of the Kingdom of Malodivo, four bills were introduced and passed:

As one could calculate, the total fund needed to implement these bills is ₡344,000. Although in this example the sum happens to be a multiple of a thousand, generally the funds needed could be any nonnegative integer. (It's quite trivial to handle a bill that needs no funding: every member of the Parliament simply contributes ₡0 to the bill.)

Each member of the Parliament also has a total amount of taxes collected:

For each member of the parliament, the member has listened to his/her constituents in a district and has decided how much of the taxes should go to each category. There is a bijection between each member and each district, so these two terms may be used interchangeably. For example, the District of Palolene has the following table of funds allocation:

However, the district could also provide specific funding amount for each bill:

As you can see, the District of Palolene does not have a large population of veterans, so the constituents have collectively decided to provide fewer funds for this bill. In certain cases, the constituents may even decide to provide zero funding to a bill they vehemently dislike. On the other hand, the District decides that a durable writing medium is so important that it will allocate ₡7,500 instead of ₡5,000 to the bill. Indeed a district could support a bill so enthusiastically that it will decide to provide a higher amount than the default for the category. However in any case the amount will never be negative.

Usually the total funding as decided above across all districts for a particular bill will exceed the amount required for that bill. In this case, you should reduce the contribution by each district proportionally. In other words, the proportions of the actual contribution among each district should be as similar as possible as the amount each district originally decides to provide. For example if a bill needs ₡10, but there are two districts and they are willing to provide ₡400 and ₡600 respectively, then these two districts will actually contribute only ₡4 and ₡6, satisfying the principle of proportionality. Again, since only the smallest unit of currency in this Kingdom is ₡1, all amounts are integers, and so suitable rounding needs to be performed.

It should further be noted that the example above shows a prosperous year, when the citizens have made good money and have a lot of taxes to pay. It is quite possible that during a depression, the total available funds could dwindle to such small amount that they could not fund all the bills the Parliament has passed. In this case, the same principle of proportionality applies. For example if there are two bills and a district wishes to provide ₡200 for one bill and ₡500 for another, but it only has ₡7 in total tax dollar collected, then it should contribute only ₡2 and ₡5 respectively towards these two bills. The issue with rounding also applies.

Different categories of the bills will generally be implemented by different Ministries. For example the Ministry of Defense will receive the funds for the bills in the Defense category, etc. (There is a bijection between the categories of the bills and the ministries, so they could also be used interchangeably.) However, the citizens of the Kingdom of Malodivo are generally suspicious of corruption. They are worried that giving too much money to a particular Ministry will tempt its Ministers and staff to be corrupt and misuse the funds. Therefore, each District also has upper limits on how much money they will provide for each Ministry. The following table shows the limits for the District of Palolene:

For example, the maximum funding for all bills in the Welfare category is capped at ₡3,199. Yet for the two bills in the Welfare category, the District of Palolene has decided to fund ₡500 for one of them and ₡3,000 for the other. The sum, ₡3,500, exceeds the maximum funding limit, ₡3,199. In this case, the maximum funding limit takes precedence; the actual funding provided will sum to ₡3,199, and ideally should be ₡457 and ₡2,742 respectively due to the principle of proportionality. It goes without saying that rounding issues also apply.

The interaction between the three principles of proportionality may not always work out so well. It is your choice which proportionality is prioritized, or you can even devise a better principle of proportionality that takes into account all three in a balanced way.

In the unlikely event that across all members, the total funding provided to a certain Ministry is capped so low that bills could not receive the full funding, the situation should be left as is. The Ministry will simply have less funds available to implement the bill. For example, suppose that the suspicion towards the Ministry of Welfare is widespread, and other members have similarly low caps for Welfare bills, then it is quite possible that the Ministry of Welfare could not receive enough funds; it'll just have to make do with that and heed this warning to reduce corruption, or potentially face the deprivation of funds and the Minister could be forced to resign.

Requirement

Your program will read the above data in the format of a JSON document, perform computation, and write the result in a JSON document.

You have the freedom to decide the schema for your input and output JSON documents.

As an example, you can use the following as a starting point but feel free to change things as you see fit:

{
    "bills": [{
        "name": "An Act to Construct the Great Wall of Malodivo",
        "category": "Defense",
        "amount": 200000
    },
    {
        "name": "An Act to Construct Shelters for the Homeless",
        "category": "Welfare",
        "amount": 40000
    },
    {
        "name": "An Act to Fund the Development of Longer-Lasting Paper",
        "category": "Science",
        "amount": 14000
    },
    {
        "name": "An Act to Increase Retirement Benefits for Veterans",
        "category": "Welfare",
        "amount": 90000
    }],
    "districts": [{
        "name": "Palolene",
        "availableFunds": 200000,
        "categoryDefaultFunding": [{
            "category": "Defense",
            "amount": 1000
        },
        {
            "category": "Welfare",
            "amount": 3000
        },
        {
            "category": "Science",
            "amount": 5000
        }],
        "billSpecificFunding": [{
            "bill": "An Act to Increase Retirement Benefits for Veterans",
            "amount": 500
        },
        {
            "bill": "An Act to Fund the Development of Longer-Lasting Paper",
            "amount": 7500
        }],
        "caps": [{
            "category": "Defense",
            "amount": 3000
        },
        {
            "category": "Welfare",
            "amount": 3199
        },
        {
            "category": "Science",
            "amount": 15000
        }]
    }]
}

The schema for the output is entirely decided by you, but at the very least you should include the actual amounts that go towards each bill by each district. You may optionally include other helpful information such as whether a bill is fully funded, or the remaining balance of each district, or anything else that you see fit.

A Simplification

It should also be noted that there are very few hard requirements. In fact there are only two:

1. reading and writing data must be done in JSON;

2. the program must be written in Haskell, but feel free to use any GHC extensions or open-source Haskell libraries.

As long as you fulfill these two requirements, we are interested in taking a look at your code and having further discussions.

Besides these two, you should exercise your liberty in trying to follow the description above. If you deviate from the above (likely), you should document them either as comments in the program or in a separate writeup.

Efficiency is not a primary concern here. We do not expect any particular Big-O complexity, but rather ask that your program finishes running in a reasonable human-scale of time, i.e. at most a minute or two.

For your convenience, we have also provided a simplification of the problem that could serve as a nice starting point:

• You may assume there are no maximum funding limits or bill-specific amounts;

• There is only one bill;

• It just so happens that the amount for the bill (i.e. funds needed) is greater than or equal to the sum of the amounts for each district (i.e. total funds provided).

You should first get this simplification working, and then gradually add more features and more complexities. Choose which features to implement according to your taste. It's perfectly fine even if you do not implement everything. We just want to see some working code, your design decisions, and your thought processes.

Unspecified Behavior

You should have noticed that this document does not specify every detail. For example it specifies that the actual proportion should be as similar as possible to the specified proportions, but the precise measure of similarity is not specified here. You may use a widely used metric such as the L2 norm, but also feel free to come up with your own. For many places where the document is vague, it could very well be intentional and please pick anything that is reasonable.

Submission

You are given a week to ponder and solve this. If you finish early, feel free to tell us; if you need a bit of extra time, also feel free to tell us so we can arrange an extension.

Once you are done, please put your code in a private GitHub/Bitbucket repository or email us the code. We will look through your code. If we like what you have written, we will then schedule a chat over Hangouts or Skype and we will have further discussions about the code; otherwise we will provide written feedback to let you know why we think you are not a good fit for the role.

Good luck!