From b36973b3e08e6d1f8a7d42a6984249486d0cebfe Mon Sep 17 00:00:00 2001 From: Igor Pashev Date: Thu, 22 Jun 2017 12:24:49 +0300 Subject: Initial commit --- doc/plot.md | 312 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 312 insertions(+) create mode 100644 doc/plot.md (limited to 'doc') diff --git a/doc/plot.md b/doc/plot.md new file mode 100644 index 0000000..4f1139e --- /dev/null +++ b/doc/plot.md @@ -0,0 +1,312 @@ +# 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! -- cgit v1.2.3