Discussion on: Javascript Sock Merchant Challenge - Solution 2

View post

Replies for: I'd write the provided code as follows: function stockAndCount( n, arr ) { const colors = {} for (const color of arr) if (colors[color])...

Theofanis Despoudis • Apr 30 '19 • Edited

I don't think you even need the last reducer. Just keep a running counter.

function sockMerchant(n, ar) {
    const colors = {}
    let pairs = 0;
    for (const color of ar)
        if (colors[color]) {
            colors[color] = 0;
            pairs += 1;
        } else {
            colors[color] = 1;
        }

    return pairs;
}

Most of the times it reports submillisecond cost with 10000 elements

Call to sockMerchant took 0.22000004537403584 milliseconds.

@Ady can you check this?

Ady Ngom • Apr 30 '19

Hi Theofanis, thanks for adding to the discussion. I totally agree that the last reducer is not needed and when it comes to performance, the for loop is always going to outperform the functional methods for large datasets. What is more interesting is the possibility to make it in one pass and that's where I believe your solution shines the most.

I even took a stab at that approach in one of my previous solutions, see code below.

function sockMerchant(n, ar) {
    let _colors = {};
    let pairs = 0;
    for(let i = 0; i < n; i++) {
        _colors[ar[i]] = (!!_colors[ar[i]]) ? _colors[ar[i]] + 1 : 1;
        // do it in one pass
        if( (_colors[ar[i]] % 2) == 0 ) pairs +=1;
    }
    return pairs;
}

const n = 9;
const socks = [10, 20, 20, 10, 10, 30, 50, 10, 20];

console.group('Sorted and counted');
    console.log(`There is a total of ${sockMerchant(n, socks)} pairs`);
console.groupEnd();

The difference with yours ultimately is that your colors value can only be 1, 2 or 0 which I believe for the context of this exercise - just counting the pairs - is perfect.

The one above since it's keep adding to the total of stocked socks, needs to do a division by 2 anytime a new sock is added.
I will of course run all against the benchmark and since JS Perf is back up and running, I'll put them all there and make a public share of the results for documentation purpose.

Cheers

John • May 1 '19

Nice solution!

Mihail Malo • May 2 '19

@theodesp this was just me commenting on the code without changing the algorithm at all.
My own solution (which does use a counter) was posted separately:

Mihail Malostanidis

Apr 27

My own solution would be:

function stockAndCount( n, arr ) {
  let pairs = 0
  const unpaired = new Set()

  for (const color of arr)
    if (unpaired.has(color)) {
      pairs++
      unpaired.delete(color)
    } else unpaired.add(color)

  return pairs
}

This doesn't iterate again over the colors encountered, and uses the minimal memory required for the task: The running total of pairs and the unpaired colors, encountering which again would be the completion of a pair.

Mihail Malo • May 2 '19 • Edited

Another hilarious one:

function sockMerchant(n, ar) {
    const colors = {}
    let pairs = 0
    for (const color of ar) pairs += !(colors[color] = !colors[color])

    return pairs
}

John • May 2 '19

... and just when I thought it could not get better...

Sweet!

Ady Ngom • May 3 '19

Nice indeed 😀

John • May 3 '19

MM has come up with some JS wizardry here ... flipping those 1's and 0's ... I would'nt have come up with it myself, but hats off to him; it's a cracker!

I wonder if he plays code golf?