2
\$\begingroup\$

Problem

Given the following data:

[
  {
    "users": [
      {
        "id": "07bde76f-aff0-407d-9241-a12b323d4af8",
        "transactions": [
          {
            "category": "purchase"
          },
          {
            "category": "unknown"
          }
        ]
      },
      {
        "id": "40aa040f-7961-4e06-a31b-32052be67fcc",
        "transactions": [
          {
            "category": "sale"
          },
          {
            "category": "unknown"
          }
        ]
      }
    ],
    "groups": [
      {
        "id": "00c61181-b133-4be9-9d44-dc3c224b3beb",
        "transactions": [
          {
            "category": "atm"
          },
          {
            "category": "cash"
          }
        ]
      },
      {
        "id": "eb959ff1-da1d-41e5-b5b7-45fef3dbc2df",
        "transactions": [
          {
            "category": "atm"
          },
          {
            "category": "cash"
          }
        ]
      }
    ]
  },
  {
    "users": [
      {
        "id": "af095f1c-fe43-43fb-9571-dabe2dd56bcf",
        "transactions": [
          {
            "category": "bill"
          }
        ]
      }
    ],
    "groups": [
      {
        "id": "c5bafe16-c5ec-428e-8c7c-30cbd9963750",
        "transactions": [
          {
            "category": "fee"
          },
          {
            "category": "cash"
          }
        ]
      }
    ]
  }
]

... I want to produce the following output:

{
  "groups_atm": 2,
  "groups_fee": 1,
  "groups_cash": 3,
  "users_purchase": 1,
  "users_unknown": 2,
  "users_bill": 1,
  "users_sale": 1
}

Implementation

I've approached this by first mapping over transactions and summing their occurrences:

const sum = (transactions) =>
    transactions.map((transaction) => transaction.category).reduce((acc, transactionCategory) => {
        return {
            ...acc,
            [transactionCategory]: (acc[transactionCategory] || 0) + 1,
        };
    }, tally);

... then aggregating by scope ("user", "group") per element of the data list and merge the counts by category:

const aggregate = (datum, tally) =>
    ['user', 'group'].reduce((acc, scope) => {
        const aggregates = datum[`${scope}s`].reduce(
            (agg, data) => sum(agg, data.transactions),
            {},
        );

        return {
            ...acc,
            [scope]: acc[scope] ? merge(acc[scope], aggregates) : aggregates,
        };
    }, tally);

const difference = (arrA, arrB) => arrA.filter((x) => !arrB.includes(x));
const intersection = (arrA, arrB) => arrA.filter((x) => arrB.includes(x));

const merge = (objA, objB) => {
    const acc = {};
    const aKeys = Object.keys(objA);
    const bKeys = Object.keys(objB);
    intersection(aKeys, bKeys).forEach((key) => (acc[key] = objA[key] + objB[key]));
    difference(aKeys, bKeys).forEach((key) => (acc[key] = objA[key]));
    difference(bKeys, aKeys).forEach((key) => (acc[key] = objB[key]));
    return acc;
};

... then re-reducing over the whole dataset:

const aggregates = data.reduce((acc, datum) => aggregateScope(datum, acc), {});

... and finally reformatting the aggregates to match the expected output:

const format = (aggregates) =>
    Object.keys(aggregates).reduce((acc, scope) => {
        Object.keys(aggregates[scope]).forEach((category) => {
            acc[`${scope}_${category}`] = aggregates[scope][category];
        });
        return acc;
    }, {});

Questions

  1. what are alternative ways of breaking down the problem?
  2. what is it's Big O complexity? Can it be reduced?
  3. can merge be avoided?
  4. are there language features (JS/ES6) that can make this more idiomatic?
  5. is "aggregation" the correct terminology?
\$\endgroup\$

1 Answer 1

Reset to default
1
\$\begingroup\$

Way way too complex

One way to help workout how to solve a problem is to solve it in your head (or on paper) first. That way you know the problem from the top to the bottom. Then use that approach in your script.

The code looks like you started at the top with no clear idea of the solution, and solve many separate problems as you encountered them. The result is unreadable and way to complex.

I could not make a good assessment due to its complexity and bugs.

Your code does not run.

  • The name aggregateScope in aggregates should be aggregate
  • sum throws TypeError map is not a function

Patching those problems it still did not run.

The hell of a zillion iterators is not easy to traverse so I stopped trying to work it out at that point.

Questions.

You have some questions.

what are alternative ways of breaking down the problem?

Its just a set of nested arrays and named objects. The names are fixed, so its just a process of stepping over each array in turn storing the counts in a named map (see example)

what is it's Big O complexity?

I am guessing its It more than \$O(n)\$ and less than or equal to \$O(n^2)\$ where \$n\$ is the number of category items. As there is only a small sample dataset and the code does not work I can not give a accurate evaluation.

I did count 18 different iteration function calls throughout your code. With 2 or 7 iterations each, nested to about 6 levels. If I use that and average (2 + 7) / 2 = 4.5 per iterator then its 4.56 approx steps, so that's a big \$O(n^3)\$ for the given dataset of 11 category items

Can it be reduced?

Yes, it can be O(n) as there is no need to search, and no need to compare items (see example).

are there language features (JS/ES6) that can make this more idiomatic?

  • Use for of loops to iterate.
  • Use bracket notations to create named properties.
  • Keep your functions ordered. From bottom to top, it makes it easier to locate functions and follow the code.
  • No more than one iterator per line. You quickly lose track of how complex it gets.

Is all that comes to mind, that and K.I.S.S.

An alternative example solution

I am not that conventional when it comes to code, so not quite idiomatic. less is good in my book and helps find the optimal \$O(n)\$ solution.

function aggregateTransactionCategories(data, types) {
  const result = {};
  const mapCategories = (type, transactions) => {
    for (const cats of transactions) { 
      const name = type + "_" + cats.category;
      result[name] = result[name] ? result[name] + 1 : 1;
    }    
  }
  for (const type of types) {
    for (const entries of data) { 
      for (const entry of entries[type]) { 
        mapCategories(type, entry.transactions);
      }
    }
  }
  return result;
}

setTimeout(() =>
    log(aggregateTransactionCategories( data,  ["groups", "users"]))
    ,0
);




const data = [{
    users: [
      { id: "07bd", transactions: [{category: "purchase"}, {category: "unknown"}] },
      { id: "40aa", transactions: [{category: "sale"}, {category: "unknown"}] }
    ],
    groups: [
      { id: "00c6", transactions: [{category: "atm"}, {category: "cash"}] },
      { id: "eb95", transactions: [{category: "atm"}, {category: "cash"}] }
    ]
  }, {
    users: [
      { id: "af09", transactions: [{category: "bill"}] }
    ],
    groups: [
      { id: "c5ba", transactions: [{category: "fee"}, {category: "cash"}] }
    ]
  }
];


//Just displays the result and not related to the problem
function log(data) {
  for(const [name, value] of Object.entries(data)) {
    displayResult.appendChild(Object.assign(
      document.createElement("div"),{ 
        textContent : name + ": " + value + ","
      }
    ))
  }
}
<code id="displayResult"></code>

\$\endgroup\$
1
  • \$\begingroup\$ This is an excellent response. Thanks for taking the time to write it. You're correct in the way I approached this; I tried to break it down into smaller problems, lost sight of the overall problem and then awkwardly tried to piece it back together. The code did run in my environment, but I mistranscribed it here. Thanks! \$\endgroup\$ Commented Jan 17, 2019 at 10:40

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.