Potter kata

At the time of writing, I just had, with the Software Crafters Lyon a coding dojo earlier this week.

It was a random kata meaning, each group got a random code kata, we have got Potter.

We did not get to the end of it, and I did not like it.

Let's get the revenge.

The idea of the kata can be sum up with this:

• There are 5 books in the Harry Potter collections
• Each individual book cost 8 EUR
• Partial collections of 2 different books got a 5% discount, 3 books got 10%, 4 books got 20%, and 5 books got 25%
• Partials collections have to be made so they give the smallest amount

Let's start with some boilerplate:

spec :: Spec
spec =
  describe "Potter" $ do
    it "no book should be 0" $
      priceOf [] `shouldBe` 0

data Book = B1 | B2 | B3 | B4 | B5
  deriving stock (Eq, Ord, Enum, Show)

newtype Price
  = Price {unPrice :: Double}
  deriving newtype (Eq, Ord, Num)

instance Show Price where
  show x = show x.unPrice <> " EUR"

priceOf :: [Book] -> Price
priceOf _ = 0

Then, we have to handle individual book, as follows:

-- forM_ [B1 .. B5] $ \b ->
--   it ("one book (" <> show b <> ") should be 8") $
--     priceOf [b] `shouldBe` 8

priceOf :: [Book] -> Price
priceOf bs = if null bs then 0 else 8

A bit naive and solved handling purchases of the same book multiple times, as follows:

-- forM_ [(2, 16), (3, 24), (4, 32)] $ \(b, p) ->
--   it (show b <> " books should be " <> show p) $
--     priceOf (replicate b B1) `shouldBe` p

priceOf :: [Book] -> Price
priceOf bs = fromIntegral (length bs) * 8

This code simply count the number of books, and multiply them by 8.

Then next step, I have tried to delay, is distinguish collections.

In order to do so, we have to group them by book, which give a matrix, then transpose it (swap rows and columns) to have collections, step by step, it gives the following:

Input

[1, 1, 2, 2, 3]

Grouping

[ [1, 1],
  [2, 2],
  [3]
]

Transposing

[ [1, 2, 3],
  [1, 2]
]

Which gives:

-- forM_ [(2, 15.2), (3, 21.60), (4, 25.60), (5, 30)] $ \(b, p) ->
--   it ("a collection of " <> show b <> " books should be " <> show p) $
--     priceOf (take b [B1 .. B5]) `shouldBe` p

priceOf :: [Book] -> Price
priceOf = sum . map bundlePrice . transpose . group . sort
  where
    bundlePrice bs =
      case length bs of
        5 -> 5 * 8 * 0.75
        4 -> 4 * 8 * 0.80
        3 -> 3 * 8 * 0.90
        2 -> 2 * 8 * 0.95
        1 -> 8
        _ -> error "impossible"

It also work with multiple partial collections as follows:

-- forM_
--   [ ([B1, B1, B2], 23.20),
--     ([B1, B1, B2, B2], 30.40),
--     ([B1, B1, B2, B3, B3, B4], 40.80),
--     ([B1, B2, B2, B3, B4, B5], 38)
--   ]
--   $ \(b, p) ->
--     it (show b <> " books should be " <> show p) $
--       priceOf b `shouldBe` p

Lastly, we have to balance collections to have the lowest price.

Given the actual discounts, the idea is to remove one book from a 5-books collection to put it in a 3-books collection, to create two 4-books collections:

• 5-books collection (5 * 8 * 0.75 = 30 EUR) + 3-books collection (3 * 8 * 0.90 = 21.60 EUR) = 51.60 EUR
• 2 * 4-books collection (4 * 8 * 0.80 = 25.60 EUR) = 51.20 EUR

To do so, we need the frequency of collection sizes.

Transposed collection:

[ [1, 2, 3, 4, 5],
  [1, 2, 3],
  [1, 2, 3],
  [1, 2]
]

Frequencies

[ 5,
  3,
  3,
  1
]

Indexed frequencies:

[ 5 => 1,
  3 => 2,
  1 => 1
]

Balanced indexed frequencies:

[ 4 => 2,
  3 => 1,
  1 => 1
]

Step by step, it gives the following piece of code:

-- forM_
--   [ ([B1, B1, B2, B2, B3, B3, B4, B5], 51.20),
--     (replicate 5 B1 <> replicate 5 B2 <> replicate 4 B3 <> replicate 5 B4 <> replicate 4 B5, 141.20)
--   ]
--   $ \(b, p) ->
--     it (show b <> " books should be " <> show p) $
--       priceOf b `shouldBe` p

priceOf :: [Book] -> Price
priceOf =
  sum
    . map (\(bs, freq) -> bundlePrice bs * freq)
    . Map.toList
    . balance
    . Map.fromListWith (+)
    . map ((,1) . length)
    . transpose
    . group
    . sort
  where
    bundlePrice bs =
      case bs of
        5 -> 5 * 8 * 0.75
        4 -> 4 * 8 * 0.80
        3 -> 3 * 8 * 0.90
        2 -> 2 * 8 * 0.95
        1 -> 8
        _ -> error "impossible"
    balance bs =
      let common4Books = Map.findWithDefault 0 5 bs `min` Map.findWithDefault 0 3 bs
          upsert n = Map.alter (Just . maybe n (+ n))
       in upsert (2 * common4Books) 4 $ upsert (-common4Books) 3 $ upsert (-common4Books) 5 bs

And, we are done... or not!

This snippet has two issues: it is partial (see the error case), and, there are branches.

Two remove both, we have to linearize frequencies (done by fetching frequencies for each collection size) and discounts as follows:

Balanced indexed frequencies:

[ 4 => 2,
  3 => 1,
  1 => 1
]

Linearized fequencies:

[1, 0, 1, 2, 0]

Collection discounts:

[0, 0.05, 0.10, 0.20, 0.25]

Collection discounted unit prices:

[1, 0.95, 0.90, 0.80, 0.75]

Once done, we can zip and multiply both lists, which gives us the final branchless code:

priceOf :: [Book] -> Price
priceOf =
  sum
    . zipWith (*) collectionDiscount
    . collectionFrequencies
    . balance
    . Map.fromListWith (+)
    . map ((,1) . length)
    . transpose
    . group
    . sort
  where
    collectionDiscount = (8 *) <$> [1, 0.95, 0.90, 0.80, 0.75]
    collectionFrequencies bs = [fromIntegral n * Map.findWithDefault 0 n bs | n <- [1 .. 5]]
    balance bs =
      let common4Books = Map.findWithDefault 0 5 bs `min` Map.findWithDefault 0 3 bs
          upsert n = Map.alter (Just . maybe n (+ n))
       in upsert (2 * common4Books) 4 $ upsert (-common4Books) 3 $ upsert (-common4Books) 5 bs