path: root/doc/plot.md

# 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:

| Name of Bill                                           | Category | Funds Needed |
| ------------------------------------------------------ | -------- | ------------ |
| An Act to Construct the Great Wall of Malodivo         | Defense  | ₡200,000     |
| An Act to Construct Shelters for the Homeless          | Welfare  | ₡40,000      |
| An Act to Fund the Development of Longer-Lasting Paper | Science  | ₡14,000      |
| An Act to Increase Retirement Benefits for Veterans    | Welfare  | ₡90,000      |

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:

| District                      | Total Available Funds |
| ----------------------------- | --------------------- |
| District of Palolene          | ₡200,000              |
| District of Southern Palolene | ₡150,000              |
| District of Lakos             | ₡400,000              |

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:

| Category | Funding Provided to *Each* Bill In This Category |
| -------- | ------------------------------------------------ |
| Defense  | ₡1,000                                           |
| Welfare  | ₡3,000                                           |
| Science  | ₡5,000                                           |

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

| Name of Bill                                           | Category | Funding Provided         |
| ------------------------------------------------------ | -------- | ------------------------ |
| An Act to Construct the Great Wall of Malodivo         | Defense  | Use default for category |
| An Act to Construct Shelters for the Homeless          | Welfare  | Use default for category |
| An Act to Fund the Development of Longer-Lasting Paper | Science  | ₡7,500                   |
| An Act to Increase Retirement Benefits for Veterans    | Welfare  | ₡500                     |

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:

| Ministry | Maximum Funding Provided To All Bills In This Category |
| -------- | ------------------------------------------------------ |
| Defense  | ₡3,000                                                 |
| Welfare  | ₡3,199                                                 |
| Science  | ₡15,000                                                |

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:

```js
{
    "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!