A full description of the problem can be found at codingdojo.org; there are also hints, tips and a few acceptance tests with which to test your solution. Essentially, your program must calculate the minimum price for a basket of books. The books all belong to a magical, wizarding series and each costs £8. However, there are group discounts when you buy different volumes together:
- 2 volumes: 5%
- 3 volumes: 10%
- 4 volumes: 20%
- 5 volumes: 25%
So, if you bought 4 books from the series, 3 of which were different volumes, you would get a 10% discount on those 3 and pay full price for the last one.
My first approach was to implement a naive, greedy algorithm that maximised the number of large groupings:
let price array = array |> Array.sort |> Array.scan (fun (_, previous) current -> (current - previous, current)) (0, 0) |> Array.map2 (fun groupPrice (num,_) -> groupPrice * System.Convert.ToDouble num) [|0.; 30.; 25.6; 21.6; 15.2; 8.|] |> Array.fold (+) 0.
This price method takes an array representing the basket of books grouped by title. For the above example, this could be
[|0; 0; 2; 1; 1;|] to represent 2 copies of the third title and 1 copy of titles four and five. Operation by operation, it then:
- Sorts the array into ascending orderOutput:
[|0; 0; 1; 1; 2|]
- Scans the array to output the location and size of quantity increases. This gives us a grouping for the books that maximises the number of larger groups.Output:
[|(0,0); (0,0); (0,0); (1,1); (0,1); (1,2)|]We can see from the first parts of the pairs that there is 1 group of three titles and 1 individual book.Note: Array.scan gives a sixth element in the array, at the beginning, which is the initial value of the state.
- Uses Array.map2 to combine the grouping pairs with an array of group prices.Output:
[|0; 0; 0; 21.6; 0; 8.|]
- Folds a total through the array, using the + operator, to give us the result.Output:
This solution works in most cases. Although, it does not satisfy one of the acceptance tests:
51.2 = price [|1; 1; 2; 2; 2|]
Our algorithm gives
51.60. What’s going on here?
The answer lies in the marginal cost of each volume when the discount is applied. If you buy all 5 volumes, the marginal cost of the first book is £8.00; the second book, £7.20; the third, £6.40; the forth, £4.00. However, the fifth book is £4.40. So the marginal cost of the forth book is less than the marginal cost of the fifth. Our algorithm should maximise groups of 4, rather than groups of 5, to give the largest discount.
The acceptance test prices
[|1; 1; 2; 2; 2|] as 2 groups of four, rather than a group of three and a group of five, to save the additional £0.40.
We can work this into our algorithm using F#’s pattern matching:
fun array -> match array with | [|0; g5; g4; g3; g2; g1|] -> let min3and5 = min g5 g3; [|0; g5 - min3and5; g4 + 2 * min3and5; g3 - min3and5; g2; g1|] | _ -> [||]
In the full solution, this matching function acts on the array of groupings found by the greedy algorithm. Notionally, it moves as many books as possible from 5-groups to 3-groups, in order to maximise the number of 4-groups and achieve the largest discount.
With this change, our algorithm prices
[|1; 1; 2; 2; 2|] correctly, as £51.20.