Javascript Sock Merchant Challenge - Solution 2

Another hilarious one:

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

    return pairs
}

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

Nice solution!

@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.

A somewhat faster solution.

const count = (ofValue, ary) => {
  let i = ary.length
  let c = 0
  while(i--){ if(ary[i] === ofValue) {c++} }
  return c
}

const completePairs = (n, Ary) =>
  Array
    .from(new Set(Ary))
    .reduce((acc, v) => acc + ~~(count(v, Ary) / 2), 0)

My hope is that this is more readable and fast enough to satisfy most users.

Hello Ady, thanks for the reply.

I recognize that my solution must look a bit strange on first sight. I was reading on MDN recently about the draft proposal for the pipeline operator aka |> to be added to JavaScript(as yet unsupported).

I also had passed sometime on the egghead.io site
re: egghead.io/courses/professor-frisb... and was intrigued how .map is used here to produce a topdown workflow composing(or piping) one function's result to the next function. What a shame that, as you have discovered, JS is not performant in this way, because, I for one, think this is an elegant and clean workflow that I hope, one day, will be worth using.

Of course speed of execution is always an important issue and so for the moment, atleast, we fall back to the roots of JavaScript and use it's for, for of, while, etc loops. Shame, because I really do like a more declarative style of coding and here I was merely experimenting.

Perhaps you will forgive a quick hack to make my solution a tad more readable(see code below) by placing a pipe method on the Array prototype. Sorry, I can't do anything about JS performance, but I think somewhat less than 10,000 socks to sort would be favourable; that sock merchant needs to keep his house in closer order I think!

Incidentally, please excuse me if I decline the webinar participation; it really is not my thing and you may take this reply as my input to that.

Have a great day.

if(!Array.prototype.pipe) Array.prototype.pipe = Array.prototype.map
const reduce = (fn, init) => xs => Array.prototype.reduce.call(xs, fn, init)

const a = [10, 20, 20, 10, 10, 30, 50, 10, 20]
// [[10, 10, 10, 10], [20, 20, 20], [30], [50]]
// => 3 complete pairs (& 3 odd socks)

const group = (p,c) =>
  (c in p)
    ? {...p, [c]: p[c] + 1}
    : {...p, [c]: 1}

// Note: ~~ is Math.floor in js.
const sumPairs = (acc, x) => acc + ~~(x/2)

// Note: .pipe is function composition. Pipes the result of a function to the next.
// Visit https://egghead.io/lessons/javascript-linear-data-flow-with-container-style-types-box
const completePairs = (n, ary) =>
  [ary]
    .pipe(reduce(group, {}))
    .pipe(Object.values)
    .pipe(reduce(sumPairs,0))
    .pop()

console.log(completePairs(9, a))
// => 3

As a final request, I would be interested in what benchmark timings (in milliseconds) you achieved for my soloution vs your solution for a test array of 10,000 integers.

Thanks, I did and borrowing your concept I found a reducing callback that works, but I think it is going to show what Ady said about functional code in JS with reference execution speed. Array.prototype.reduce is slow compared to other JS imperative looping constructs. However, I am getting somewhere around 30ms for the code below using console.time on a 10k set.

When put in perspective; a blink of an eye is approx 300 - 400ms, roughly a third of a second, so it's still pretty quick.

const sockMerchant = (n, ar) =>
  ar.reduce((acc, colr) => {
    return (colr in acc && acc[colr])
      ? {...acc, [colr]:0, 'pairs':acc['pairs']+1}
      : {...acc, [colr]:1}
  }, {'pairs': 0} ).pairs

Yup, my "highly scientific" browser benchmark also makes it seem that Set is slower:

function socks_set(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
}
function socks_obj(ar) {
  const colors = {}
  let pairs = 0
  for (const color of ar) pairs += !(colors[color] = !colors[color])

  return pairs
}
function* good() {
  let i = 0
  while (i < 100000000) yield i++ >> 1
  return i >> 1
}
function* bad() {
  let i = 0
  while (i < 10000000) yield i++
  return i
}

console.log(socks_set(good()))
console.log(socks_obj(good()))
console.time("good Set")
socks_set(good())
console.timeEnd("good Set")
console.time("good Obj")
socks_obj(good())
console.timeEnd("good Obj")
console.time("good Set")
socks_set(good())
console.timeEnd("good Set")
console.time("good Obj")
socks_obj(good())
console.timeEnd("good Obj")

console.log(socks_set(bad()))
console.log(socks_obj(bad()))
console.time("bad Set")
socks_set(bad())
console.timeEnd("bad Set")
console.time("bad Obj")
socks_obj(bad())
console.timeEnd("bad Obj")
console.time("bad Set")
socks_set(bad())
console.timeEnd("bad Set")
console.time("bad Obj")
socks_obj(bad())
console.timeEnd("bad Obj")