Help the bookseller

https://www.codewars.com/kata/54dc6f5a224c26032800005c

Instructions

A bookseller has lots of books classified in 26 categories labeled A, B, ... Z. Each book has a code c with randomized sizes of characters. The 1st character of a code is a capital letter which defines the book category.

In the bookseller's stocklist each code c is followed by a space and by a positive integer n (int n >= 0) which indicates the quantity of books of this code in stock.

For example an extract of a stocklist could be:

1
L = {"ABART 20", "CDXEF 50", "BKWRK 25", "BTSQZ 89", "DRTYM 60"}.
2
or
3
L = ["ABART 20", "CDXEF 50", "BKWRK 25", "BTSQZ 89", "DRTYM 60"] or ....

You will be given a stocklist (e.g. : L) and a list of categories in capital letters e.g :

1
M = {"A", "B", "C", "W"}
2
or
3
M = ["A", "B", "C", "W"] or ...

and your task is to find all the books of L with codes belonging to each category of M and to sum their quantity according to each category.

For the lists L and M of example you have to return the string (in Haskell/Clojure/Racket/Prolog a list of pairs):

1
(A : 20) - (B : 114) - (C : 50) - (W : 0)

where A, B, C, W are the categories, 20 is the sum of the unique book of category A, 114 the sum corresponding to "BKWRK" and "BTSQZ", 50 corresponding to "CDXEF" and 0 to category 'W' since there are no code beginning with W.

If L or M are empty return string is "" (Clojure/Racket/Prolog should return an empty array/list instead).

Notes: In the result codes and their values are in the same order as in M. See "Samples Tests" for the return.

First iteration

The algorithm is simple. We need to iterate over the stocklist and check if the first letter of the code is in the categories list. If it is, we sum the quantity of books.

1
function stockList(books = [], categories = []) {
2
  if (books.length === 0) return "";
3
  const categoriesStock = new Map();
4
  for (const category of categories) {
5
    categoriesStock.set(category, 0);
6
  }
7
  for (const book of books) {
8
    const [cat, stock] = book.split(" ");
9
    categoriesStock.set(cat[0], categoriesStock.get(cat[0]) + parseInt(stock));
10
  }
11

12
  return [...categoriesStock.entries()]
13
    .filter(([k]) => categories.includes(k))
14
    .map(([k, v]) => `(${k} : ${v})`)
15
    .join(" - ");
16
}

Second iteration

The plan is to remove the overhead of a map. Maps seems O(1) at first glance, but they are not. In general they are O(c*n) where c is the number of categories and n is the number of books, also maps checks for the key existence.

Watch this video: https://www.youtube.com/watch?v=Rxd3W1wnlEc if you want to know more about the performance of Hashsets (some concepts also applies for maps).

1
function stockList(books = [], categories = []) {
2
  if (books.length === 0) return "";
3

4
  const stock = [...categories].fill(0);
5

6
  for (let i = 0; i < categories.length; i++) {
7
    for (const book of books) {
8
      if (book[0] === categories[i]) {
9
        let j = book.length - 1;
10
        while (j > 0 && book[j - 1] !== " ") {
11
          j--;
12
        }
13
        stock[i] += parseInt(book.slice(j));
14
      }
15
    }
16
  }
17

18
  return categories
19
    .map((cat, index) => `(${cat} : ${stock[index]})`)
20
    .join(" - ");
21
}

This solution is 21% faster than the first one on average.

Third iteration

This Third iteration is the same as the second one, but creating a map instead of an array to store the stock values of each category allows us to remove the inner loop and transform the algorithm into O(n) complexity (sort of).

This solution is ~40% faster than the second one on average and ~60% faster than the first one (check the benchmark below).

1
function stockList(books = [], categories = []) {
2
  if (books.length === 0 || categories.length === 0) return "";
3

4
  const stock = {};
5

6
  for (const book of books) {
7
    const category = book[0];
8
    const quantity = parseInt(book.split(" ")[1]);
9
    if (stock[category]) {
10
      stock[category] += quantity;
11
    } else {
12
      stock[category] = quantity;
13
    }
14
  }
15

16
  return categories.map((cat) => `(${cat} : ${stock[cat] || 0})`).join(" - ");
17
}

Benchmark