Initial commit0.0.0

15 files changed, 830 insertions, 0 deletions

diff --git a/.gitignore b/.gitignore
new file mode 100644
index 0000000..dbaee1d
--- /dev/null
+++ b/.gitignore
@@ -0,0 +1,4 @@
+/.stack-work
+/dist
+/dist-newstyle
+cabal.*.local
diff --git a/ChangeLog.md b/ChangeLog.md
new file mode 100644
index 0000000..eb7aca3
--- /dev/null
+++ b/ChangeLog.md
@@ -0,0 +1,5 @@
+0.0.0
+=====
+
+  * Initial version. Can only process one bill with no constains.
+
diff --git a/LICENSE b/LICENSE
new file mode 100644
index 0000000..c6c7def
--- /dev/null
+++ b/LICENSE
@@ -0,0 +1,13 @@
+        DO WHAT THE FUCK YOU WANT TO PUBLIC LICENSE
+                    Version 2, December 2004
+
+ Copyright (C) 2004 Sam Hocevar <sam@hocevar.net>
+
+ Everyone is permitted to copy and distribute verbatim or modified
+ copies of this license document, and changing it is allowed as long
+ as the name is changed.
+
+            DO WHAT THE FUCK YOU WANT TO PUBLIC LICENSE
+   TERMS AND CONDITIONS FOR COPYING, DISTRIBUTION AND MODIFICATION
+
+  0. You just DO WHAT THE FUCK YOU WANT TO.
diff --git a/README.md b/README.md
new file mode 100644
index 0000000..dd87c22
--- /dev/null
+++ b/README.md
@@ -0,0 +1,74 @@
+Malodivo
+========
+
+Budget planning in a fairy Kingdom of Malodivo.
+For the whole story read the [plot](./doc/plot.md).
+
+
+Requirements
+============
+
+Malodivo is written in Haskell with [GHC](http://www.haskell.org/ghc/).
+All required Haskell libraries are listed in [malodivo.cabal](malodivo.cabal).
+Use [cabal-install](http://www.haskell.org/haskellwiki/Cabal-Install) to fetch
+and build all pre-requisites automatically.
+
+
+Command-line utility
+====================
+
+The command-line utility `malodivo` provides a means to process input JSON
+files and output JSON describing the actual amounts that go towards each bill
+by each district.  This utility reads input JSON data from standard input
+and writes output JSON data to standard output.  _The format of output is
+unstable and subject to change_.
+
+Usage
+-----
+
+```
+Usage: malodivo [options] < input.json > output.json
+
+Options:
+
+  -h, --help               Show this message and exit
+
+```
+
+
+Examples
+--------
+
+We would get this:
+```
+$ malodivo < sample/simpleBudget.json
+[["Lakos",100],["Palolene",66],["SouthernPalolene",133]]
+```
+
+with this file ([sample/simpleBudget.json](sample/simpleBudget.json)):
+```json
+{
+  "bills": [
+    {
+      "name": "An Act to Construct the Great Wall of Malodivo",
+      "ministry": "Defense",
+      "amount": 300
+    }
+  ],
+  "districts": [
+    {
+      "name": "Palolene",
+      "availableFunds": 200
+    },
+    {
+      "name": "SouthernPalolene",
+      "availableFunds": 400
+    },
+    {
+      "name": "Lakos",
+      "availableFunds": 300
+    }
+  ]
+}
+```
+
diff --git a/Setup.hs b/Setup.hs
new file mode 100644
index 0000000..49d3f2f
--- /dev/null
+++ b/Setup.hs
@@ -0,0 +1,10 @@
+{-# LANGUAGE CPP #-}
+
+module Main
+  ( main
+  ) where
+
+import Distribution.Extra.Doctest (defaultMainWithDoctests)
+
+main :: IO ()
+main = defaultMainWithDoctests "doctests"
diff --git a/cmd/Main.hs b/cmd/Main.hs
new file mode 100644
index 0000000..bbc45cb
--- /dev/null
+++ b/cmd/Main.hs
@@ -0,0 +1,76 @@
+{-# LANGUAGE DeriveAnyClass #-}
+{-# LANGUAGE DeriveGeneric #-}
+{-# LANGUAGE QuasiQuotes #-}
+
+module Main
+  ( main
+  ) where
+
+import Control.Arrow ((&&&))
+import Control.Monad (when)
+import Data.Version (showVersion)
+import GHC.Generics (Generic)
+import System.Environment (getArgs)
+import System.Exit (die)
+
+import Data.Aeson (FromJSON, eitherDecode, encode)
+import qualified Data.ByteString.Lazy as L
+import qualified Data.HashMap.Strict as HM
+import qualified System.Console.Docopt.NoTH as O
+import Text.InterpolatedString.Perl6 (qc)
+
+import Malodivo.Budget (manyToOne)
+import Malodivo.Types.Bill (Bill)
+import Malodivo.Types.District (District)
+
+import Paths_malodivo (version) -- from cabal
+
+usage :: String
+usage =
+  "malodivo " ++
+  showVersion version ++
+  " - budget planning tool for the Kingdom of Malodivo" ++
+  [qc|
+
+This utility reads input JSON data from standard input
+and writes output JSON data to standard output.
+
+Usage: malodivo [options] < input.json > output.json
+
+Options:
+
+  -h, --help               Show this message and exit
+
+
+|]
+
+data DistrictInfo = DistrictInfo
+  { name :: District
+  , availableFunds :: Integer
+  } deriving (Generic, FromJSON)
+
+data SimpleInput = SimpleInput
+  { bills :: [Bill]
+  , districts :: [DistrictInfo]
+  } deriving (Generic, FromJSON)
+
+process :: IO ()
+process = do
+  input <- L.getContents
+  case eitherDecode input of
+    Left err -> die err
+    Right si -> do
+      let nbills = length . bills $ si
+          funds =
+            HM.fromListWith (+) . map (name &&& availableFunds) $ districts si
+      when (nbills /= 1) $ die "We needs exactly one bill in input"
+      when (HM.null funds) $ die "We needs at least one district"
+      L.putStr . encode $ manyToOne funds (head . bills $ si)
+
+main :: IO ()
+main = do
+  doco <- O.parseUsageOrExit usage
+  args <- O.parseArgsOrExit doco =<< getArgs
+  if args `O.isPresent` O.longOption "help"
+    then putStrLn $ O.usage doco
+    else process
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!

diff --git a/lib/Malodivo/Budget.hs b/lib/Malodivo/Budget.hs
new file mode 100644
index 0000000..edc0668
--- /dev/null
+++ b/lib/Malodivo/Budget.hs
@@ -0,0 +1,101 @@
+{-|
+
+Budget planning in the Kingdom of Malodivo.
+
+-}
+module Malodivo.Budget
+  ( DistrictFunds
+  , manyToOne
+  ) where
+
+import qualified Data.HashMap.Strict as HM
+
+import qualified Malodivo.Types.Bill as B
+import qualified Malodivo.Types.District as D
+
+-- | Convenient type.
+type DistrictFunds = HM.HashMap D.District Integer
+
+{-|
+
+Trivial case: many districts, one bill, no contraints (wishes,
+limits).  We assume that, with no explicit wishes, each district
+wants to contribute all its funds.
+
+>>> :set -XOverloadedStrings
+>>> import qualified Data.HashMap.Strict as HM
+>>> import qualified Malodivo.Types.Bill as B
+>>> import qualified Malodivo.Types.District as D
+>>> import qualified Malodivo.Types.Ministry as M
+
+>>> let medium = B.Bill { B.amount = 30, B.name = "A medium bill", B.ministry = M.Science }
+>>> let one = B.Bill { B.amount = 1, B.name = "A trivial bill", B.ministry = M.Welfare }
+
+
+If any district can pay the bill, take funds in proportion.  We use
+'HM.lookup', because 'show' of 'HM.HashMap' is not determinate,
+and the test can occasionally fail:
+
+>>> let funds = HM.fromList [(D.Palolene, 100), (D.Lakos, 200)]
+>>> let contribution = manyToOne funds medium
+>>> HM.lookup D.Palolene contribution
+Just 10
+>>> HM.lookup D.Lakos contribution
+Just 20
+
+>>> let funds = HM.fromList [(D.Palolene, 30), (D.Lakos, 30)]
+>>> HM.elems $ manyToOne funds medium
+[15,15]
+
+
+It works with a single district:
+
+>>> let funds = HM.fromList [(D.SouthernPalolene, 500)]
+>>> HM.elems $ manyToOne funds medium
+[30]
+>>> HM.elems $ manyToOne funds one
+[1]
+
+
+__TODO__ It /should/ not have rounding issues. In particular,
+when the bill's amount is bigger than the number of districts,
+/each/ district would contribute some. This problem is known as
+<https://en.wikipedia.org/wiki/Partition_(number_theory) integer partition>.
+
+>>> let funds = HM.fromList [(D.Palolene, 10000), (D.Lakos, 1)]
+>>> B.amount medium > fromIntegral (HM.size funds)
+True
+>>> let contribution = manyToOne funds medium
+>>> let taken = HM.foldl' (+) 0 contribution
+
+
+But at the moment we make use of some freedom coming from the fact
+that \"it is possible that a bill will receive less funds than the
+Parliament decides\", and round down contribution of each district.
+/Thus these two tests show 'False', while should show 'True':/
+
+>>> HM.null $ HM.filter (== 0) contribution
+False
+>>> taken == B.amount medium
+False
+
+
+If all districts together can't pay the bill, take all their money.
+Note that due to the principle of proportionality it is impossible
+that some districts can pay their shares and others can't:
+
+>>> let low = HM.fromList [(D.Palolene, 10), (D.Lakos, 15)]
+>>> manyToOne low medium == low
+True
+
+-}
+manyToOne ::
+     DistrictFunds -- ^ Amounts of available funds per district.
+  -> B.Bill -- ^ A bill requiring funding.
+  -> DistrictFunds -- ^ Contribution of each district.
+manyToOne funds bill = HM.map takeMoney funds
+  where
+    needed = B.amount bill
+    available = sum $ HM.elems funds
+    requested = min needed available
+    takeMoney m = requested * m `div` available
diff --git a/lib/Malodivo/Types/Bill.hs b/lib/Malodivo/Types/Bill.hs
new file mode 100644
index 0000000..336c0fb
--- /dev/null
+++ b/lib/Malodivo/Types/Bill.hs
@@ -0,0 +1,44 @@
+{-|
+
+A bill is a proposed law put before the Parliament to consider and
+possibly implement.  Bills can be encoded to and decoded from JSON.
+
+>>> :set -XOverloadedStrings
+>>> import Data.Aeson (decode, encode)
+>>> import Data.Maybe (fromJust)
+>>> import Malodivo.Types.Ministry (Ministry(..))
+
+>>> let billGreateWall = Bill { name = "The Great Wall of Malodivo", ministry = Defense, amount = 4000 }
+>>> encode billGreateWall
+"{\"amount\":4000,\"name\":\"The Great Wall of Malodivo\",\"ministry\":\"Defense\"}"
+
+>>> let billShelters = fromJust $ decode "{\"amount\":1234,\"name\":\"Shelters for the Homeless\",\"ministry\":\"Welfare\"}"
+>>> billShelters :: Bill
+Bill {name = "Shelters for the Homeless", ministry = Welfare, amount = 1234}
+
+>>> ministry <$> [billShelters, billGreateWall]
+[Welfare,Defense]
+
+>>> sum $ amount <$> [billShelters, billGreateWall]
+5234
+
+-}
+{-# LANGUAGE DeriveAnyClass #-}
+{-# LANGUAGE DeriveGeneric #-}
+
+module Malodivo.Types.Bill
+  ( Bill(..)
+  ) where
+
+import GHC.Generics (Generic)
+
+import Data.Aeson (FromJSON, ToJSON)
+import Data.Text (Text)
+
+import Malodivo.Types.Ministry (Ministry)
+
+data Bill = Bill
+  { name :: Text -- ^ the name of a bill, e. g. \"An Act to Construct the Great Wall of Malodivo\".
+  , ministry :: Ministry -- ^ the ministry getting funds to implement a bill.
+  , amount :: Integer -- ^ the amount of funds required to implement a bill.
+  } deriving (Show, Generic, FromJSON, ToJSON)
diff --git a/lib/Malodivo/Types/District.hs b/lib/Malodivo/Types/District.hs
new file mode 100644
index 0000000..a46628d
--- /dev/null
+++ b/lib/Malodivo/Types/District.hs
@@ -0,0 +1,41 @@
+{-|
+Districts can be encoded to and decoded from JSON:
+
+>>> import Data.Aeson (decode, encode)
+>>> import Data.ByteString.Lazy.Char8 (pack)
+
+>>> encode Palolene
+"\"Palolene\""
+
+>>> encode [ Lakos, SouthernPalolene ]
+"[\"Lakos\",\"SouthernPalolene\"]"
+
+>>> decode . pack $ "[ \"Lakos\" ]" :: Maybe [District]
+Just [Lakos]
+-}
+{-# LANGUAGE DeriveAnyClass #-}
+{-# LANGUAGE DeriveGeneric #-}
+
+module Malodivo.Types.District
+  ( District(..)
+  ) where
+
+import GHC.Generics (Generic)
+
+import Data.Aeson (FromJSON, FromJSONKey, ToJSON, ToJSONKey)
+import Data.Hashable (Hashable)
+
+-- | District of the Kindom of Malodivo.
+data District
+  = Palolene
+  | SouthernPalolene
+  | Lakos
+  deriving ( Eq
+           , Hashable
+           , Show
+           , Generic
+           , FromJSON
+           , FromJSONKey
+           , ToJSON
+           , ToJSONKey
+           )
diff --git a/lib/Malodivo/Types/Ministry.hs b/lib/Malodivo/Types/Ministry.hs
new file mode 100644
index 0000000..c3e315b
--- /dev/null
+++ b/lib/Malodivo/Types/Ministry.hs
@@ -0,0 +1,32 @@
+{-|
+Ministries can be encoded to and decoded from JSON:
+
+>>> import Data.Aeson (decode, encode)
+>>> import Data.ByteString.Lazy.Char8 (pack)
+
+>>> encode Defense
+"\"Defense\""
+
+>>> encode [ Defense, Welfare ]
+"[\"Defense\",\"Welfare\"]"
+
+>>> decode . pack $ "[ \"Science\" ]" :: Maybe [Ministry]
+Just [Science]
+-}
+{-# LANGUAGE DeriveAnyClass #-}
+{-# LANGUAGE DeriveGeneric #-}
+
+module Malodivo.Types.Ministry
+  ( Ministry(..)
+  ) where
+
+import GHC.Generics (Generic)
+
+import Data.Aeson (FromJSON, ToJSON)
+
+-- | Ministry of the Kingdom of Malodivo.
+data Ministry
+  = Defense
+  | Science
+  | Welfare
+  deriving (Show, Generic, FromJSON, ToJSON)
diff --git a/malodivo.cabal b/malodivo.cabal
new file mode 100644
index 0000000..31047be
--- /dev/null
+++ b/malodivo.cabal
@@ -0,0 +1,73 @@
+name: malodivo
+version: 0.0.0
+synopsis: Budget planning in the Kingdom of Malodivo
+description: Once upon a time, in a galaxy far, far away,
+  where no man has gone before.
+license: PublicDomain
+license-file: LICENSE
+author: Igor Pashev
+maintainer: Igor Pashev <pashev.igor@gmail.com>
+copyright: 2017, Igor Pashev <pashev.igor@gmail.com>
+category: Math, Finance, Utils
+build-type: Custom
+cabal-version: >= 1.24
+extra-source-files:
+  ChangeLog.md
+  README.md
+  doc/plot.md
+  sample/*.json
+
+custom-setup
+  setup-depends:
+      base >= 4.9 && < 5
+    , Cabal
+    , cabal-doctest >= 1.0.2
+
+test-suite doctests
+  type: exitcode-stdio-1.0
+  main-is: doctests.hs
+  build-depends:
+      base
+    , doctest >= 0.11.1
+    , bytestring
+  ghc-options: -Wall
+  hs-source-dirs: test
+  default-language: Haskell2010
+
+flag cmd
+  description: Build the command-line utility.
+  default: True
+
+library
+  default-language: Haskell2010
+  ghc-options: -Wall
+  hs-source-dirs: lib
+  build-depends:
+      base >= 4.9 && < 5
+    , aeson
+    , hashable
+    , text
+    , unordered-containers
+  exposed-modules:
+    Malodivo.Budget
+    Malodivo.Types.Bill
+    Malodivo.Types.District
+    Malodivo.Types.Ministry
+
+executable malodivo
+  default-language: Haskell2010
+  ghc-options: -Wall -static
+  hs-source-dirs: cmd
+  main-is: Main.hs
+  if flag(cmd)
+    build-depends:
+        base >= 4.9 && < 5
+      , aeson
+      , bytestring
+      , docopt
+      , interpolatedstring-perl6
+      , malodivo
+      , unordered-containers
+  else
+    buildable: False
+
diff --git a/sample/simpleBudget.json b/sample/simpleBudget.json
new file mode 100644
index 0000000..551898a
--- /dev/null
+++ b/sample/simpleBudget.json
@@ -0,0 +1,23 @@
+{
+  "bills": [
+    {
+      "name": "An Act to Construct the Great Wall of Malodivo",
+      "ministry": "Defense",
+      "amount": 300
+    }
+  ],
+  "districts": [
+    {
+      "name": "Palolene",
+      "availableFunds": 200
+    },
+    {
+      "name": "SouthernPalolene",
+      "availableFunds": 400
+    },
+    {
+      "name": "Lakos",
+      "availableFunds": 300
+    }
+  ]
+}
diff --git a/stack.yaml b/stack.yaml
new file mode 100644
index 0000000..2b0a8d6
--- /dev/null
+++ b/stack.yaml
@@ -0,0 +1,8 @@
+resolver: lts-8.17
+packages:
+- '.'
+
+extra-deps: []
+flags: {}
+extra-package-dbs: []
+
diff --git a/test/doctests.hs b/test/doctests.hs
new file mode 100644
index 0000000..4b5d604
--- /dev/null
+++ b/test/doctests.hs
@@ -0,0 +1,14 @@
+module Main
+  ( main
+  ) where
+
+import Build_doctests (flags, module_sources, pkgs)
+import Data.Foldable (traverse_)
+import Test.DocTest (doctest)
+
+main :: IO ()
+main = do
+  traverse_ putStrLn args
+  doctest args
+  where
+    args = flags ++ pkgs ++ module_sources