How To Solve The Sock Merchant Challenge

How To Solve The Sock Merchant Code Challenge

Problem

The Sock Merchant challenge is basically the concentration card game but discarding the extras and just counting the pairs:

  • AR is a single string of spaced numbers with values ranging between 1 and 100 — ex 10 11 20 31
  • N is the number of values in AR between 1 and 100 (which could be useless if we’re just calculating the array length)

Goal

Write a function or functions that returns the total number of pairs found in the in the string (AR)

Covering Our Bases

Covering our bases, we need to make sure that:

  • Number of item (values) of AR is in between 1 and 100
  • N is an integer, between 1 and 100
  • N = the total number of values of AR

Counting The Values Of AR

In order to get a better sense of how many values are in AR we need to convert the string to an array and count it.

function sockMerchant(n, ar) {
// setting the constraints
const min = 1;
const max = 100;

// if it's a string convert it to an array
// ex "10 31 11" = ["10", "31", "11"]
ar = (typeof ar === "string") ? ar.split(' ') : ar;
// check if ar meets the requirements
if (ar.length >= min && ar.length <= max) {
// continue
}
}

Validating N

Next we need to make sure that N is an integer and matches the same number of values of AR.

function sockMerchant(n, ar) {
// setting the constraints
const min = 1;
const max = 100;

// if it's a string convert it to an array
// ex "10 31 11" = ["10", "31", "11"]
ar = (typeof ar === "string") ? ar.split(' ') : ar;
// check if ar meets the requirements
if (ar.length >= min
&& ar.length <= max
&& n === parseInt(n, 0)
&& n >= min
&& n <= max
&& n === ar.length) {
// continue
}
}

Understanding The Problem

At first look at this, it looks like an array that I’m going to continue searching through for matches, which would lead me to believe that we’ll need to write a recursive function to continually go through. The concept would be to take the first value of the array, remove it from the equation for searching, and search the rest of the array for the next sequential pairing of that number.

Finding A Match

// Example 1 - Assuming
// N = 7
// AR = ("1 2 1 2 1 3 2").split(' ');
// ["1", "2", "1", "2", "1", "3", "2"]
// set the default number of pairs to count
let pairs = 0;
// get first value
let find = ar[0]; // "1"
// create new array but remove the first value
let newArr = ar.slice(1); // ["2", "1", "2", "1", "3", "2"]
// find if there match sequentiall
if (newArr.indexOf(find) > -1) { // index 1
// a match was found, increment pairs
pairs++;
}

Removing The Pair

Now that we found a match, let’s remove that match from the array, to make it ready to be searched again.

// Example 1 - Assuming
// N = 7
// AR = ("1 2 1 2 1 3 2").split(' ');
// ["1", "2", "1", "2", "1", "3", "2"]
// set the default number of pairs to count
let pairs = 0;
// get first value
let find = ar[0]; // "1"
// create new array but remove the first value
let newArr = ar.slice(1); // ["2", "1", "2", "1", "3", "2"]
// find if there match sequential
if (newArr.indexOf(find) > -1) { // index 1
// a match was found, increment pairs
pairs++;
}
// removing the match, but creating a new array
newArr = [ ...newArr.slice(0, newArr.indexOf(find)), ...newArr.slice(newArr.indexOf(find) + 1)];
// ["2", "2", "1", "3", "2"]

Repeating The Process

Now that we have the new array, we’re ready to search through it again.

// Example 1 - Assuming
// N = 7
// AR = ("1 2 1 2 1 3 2").split(' ');
// ["1", "2", "1", "2", "1", "3", "2"]
// set the default number of pairs to count
let pairs = 0;
// get first value
let find = ar[0]; // "1"
// create new array but remove the first value
let newArr = ar.slice(1); // ["2", "1", "2", "1", "3", "2"]
// find if there match sequential
if (newArr.indexOf(find) > -1) { // index 1
// a match was found, increment pairs
pairs++; // 1
}
// removing the match, but creating a new array
newArr = [ ...newArr.slice(0, newArr.indexOf(find)), ...newArr.slice(newArr.indexOf(find) + 1)];
// ["2", "2", "1", "3", "2"]
// get first value
find = newArr[0]; // "2"
// create new array but remove the first value
newArr = newArr.slice(1); // ["2", "1", "3", "2"];
// find if there match sequential
if (newArr.indexOf(find) > -1) { // index 1
// a match was found, increment pairs
pairs++; // 2
}

Already we see that there is pattern here of performing the same process, with that we can already assume that this will now be in a function.

Refactoring For Recursion

Not only should we refactor this as a function, but because we are making the array smaller and smaller, we can refactor this as a recursive function.

Before

// Example 1 - Assuming
// N = 7
// AR = ("1 2 1 2 1 3 2").split(' ');
// ["1", "2", "1", "2", "1", "3", "2"]
// set the default number of pairs to count
let pairs = 0;
// get first value
let find = ar[0]; // "1"
// create new array but remove the first value
let newArr = ar.slice(1); // ["2", "1", "2", "1", "3", "2"]
// find if there match sequential
if (newArr.indexOf(find) > -1) { // index 1
// a match was found, increment pairs
pairs++; // 1
}
// removing the match, but creating a new array
newArr = [ ...newArr.slice(0, newArr.indexOf(find)), ...newArr.slice(newArr.indexOf(find) + 1)];
// ["2", "2", "1", "3", "2"]
// get first value
find = newArr[0]; // "2"
// create new array but remove the first value
newArr = newArr.slice(1); // ["2", "1", "3", "2"];
// find if there match sequential
if (newArr.indexOf(find) > -1) { // index 1
// a match was found, increment pairs
pairs++; // 2
}

After

// Example 1 - Assuming
// N = 7
// AR = ("1 2 1 2 1 3 2").split(' ');
// ["1", "2", "1", "2", "1", "3", "2"]
// the 3 values that keep repeating are
// the array, the value to search, and the counted pairs
function findPairs(ar, find, pairs) {
// if there is still parts of the array left to search through
if (ar.length > 0) {
// assuming that the first ar would be ar.slice(1)
// we can assume that
let newArr = ar;

// we don't need to define find because we can assume
// that the first find is being send to us find = ar[0]

// find if there match sequential
if (newArr.indexOf(find) > -1) { // index 1
// a match was found, increment pairs
pairs++; // 1
}

// 1. next we need to create new array
// but remove the first value
// 2. send the new find = newArr[0]
// 3. continue passing pairs to make sure it increments
return findPairs(
[ ...newArr.slice(0, newArr.indexOf(find)),
...newArr.slice(newArr.indexOf(find) + 1)],
// ["2", "2", "1", "3", "2"]
newArr[0], // "2"
pairs
);
}

// ultimate value we are returning
return pairs;
}

Looks good, right? Not quite. What about when we don’t find a pair, how would I function work?

Finding The Bug

// Example 1 - Assuming
// N = 7
// AR = ("1 2 1 2 1 3 2").split(' ');
// ["1", "2", "1", "2", "1", "3", "2"]
findPairs(AR.slice(1), AR[0], 0);// ar = ["2", "1", "2", "1", "3", 2"]
// find = "1"
// pairs = 1
// [ ...ar.slice(0.. = ["2", "2", "1", "3", "2"]
// find = ar[0] = "2"
// pairs = 2
// [ ...ar.slice(0.. = ["2", "1", "3", "2"] (Something went wrong)
// find = ar[0] = "2" (Don't think should be right)
// pairs = 3 (Wait, what?)
// [ ...ar.slice(0.. = ["1", "3", "2"]
// find = ar[0] = "2"
// pairs = 4 (Very wrong)
// [ ...ar.slice(0.. = ["1", "3"]
// find = ar[0] = "1"
// pairs = 5 (That doesn't make sense)
// [ ...ar.slice(0.. = ["3"]
// find = ar[0] = "1"
// pairs = 5 (Still wrong)
// [ ...ar.slice(0.. = ["3"] (This should be gone)
// find = ar[0] = "3" (This is wrong)
// pairs = 6 (Still wrong)
// Results = 6 pairs vs expected 2 (very wrong)

So where did we go wrong? Let’s look at the last instance just before things go wrong and walkthrough it.

// [ ...ar.slice(0.. = ["2", "2", "1", "3", "2"]
// find = ar[0] = "2" (This is where things go wrong)
// pairs = 2

Two (2) should be removed from the AR slice, not just the item we just found (1). We need to refactor this as:

Before

...
// 1. next we need to create new array
// but remove the first value
// 2. send the new find = newArr[0]
// 3. continue passing pairs to make sure it increments
return findPairs(
[ ...newArr.slice(0, newArr.indexOf(find)),
...newArr.slice(newArr.indexOf(find) + 1)],
newArr[0], // "2"
pairs
);
...

After

...
// 1. next we need to create new array
// but remove the first value
// 1b. remove all the new first index "2"
// 2. send the new find = newArr[0]
// 3. continue passing pairs to make sure it increments

newArr = [ ...newArr.slice(0, newArr.indexOf(find)),
...newArr.slice(newArr.indexOf(find) + 1)]


return findPairs(
newArr.slice(1),
newArr[0], // "2"
pairs
);
...

Run it again:

// Example 1 - Assuming
// N = 7
// AR = ("1 2 1 2 1 3 2").split(' ');
// ["1", "2", "1", "2", "1", "3", "2"]
findPairs(AR.slice(1), AR[0], 0);// ar = ["2", "1", "2", "1", "3", "2"]
// find = "1"
// pairs = 1
// ar.slice(1) = ["2", "1", "3", "2"]
// find = "2"
// pairs = 2
// ar.slice(1) = ["3", "2"]
// find = "1"
// pairs = 2
// ar.slice(1) = ["3", "2"] (Somethings not right)
// find = "3" (Going wrong)
// pairs = 3 (Very wrong)

We’ve gotten closer, but we’re missing one last thing.

Handling No Pair Found

The part where it went wrong is when there was no pair found and we needed to pass through the array again. Based on our redeclaration of newArr, it’s based on finding a value that isn’t found:

// Example 1 - Assuming
// N = 7
// AR = ("1 2 1 2 1 3 2").split(' ');
// ["1", "2", "1", "2", "1", "3", "2"]
...
// ar.slice(1) = ["3", "2"]
// find = "1"
// pairs = 2
...
newArr = [ ...newArr.slice(0, newArr.indexOf(find)),
...newArr.slice(newArr.indexOf(find) + 1)];
// gives us
// ["3", "3", "2"]

// expected
// ["2"]

If we have the array, what we should be really sending is:

newArr = newArr.slice(1);// gives us
// ["2"]

So we need to account for this only in the case that the find is not found in newArr.

Before

...
// find if there match sequential
if (newArr.indexOf(find) > -1) { // index 1
// a match was found, increment pairs
pairs++;
}

newArr = [ ...newArr.slice(0, newArr.indexOf(find)),
...newArr.slice(newArr.indexOf(find) + 1)];
...

After

...
// find if there match sequential
if (newArr.indexOf(find) > -1) { // index 1
// a match was found, increment pairs
pairs++;
// 1. next we need to create new array
// but remove the first value
// 2. send the new find = newArr[0]
// 3. continue passing pairs to make sure it increments
newArr = [ ...newArr.slice(0, newArr.indexOf(find)),
...newArr.slice(newArr.indexOf(find) + 1)];

} else {
newArr = newArr.slice(1);
}

...

But wait, are we doing newArr.slice(1) already in the return?

After again:

...
// find if there match sequential
if (newArr.indexOf(find) > -1) { // index 1
// a match was found, increment pairs
pairs++;
// 1. next we need to create new array
// but remove the first value
// 2. send the new find = newArr[0]
// 3. continue passing pairs to make sure it increments
newArr = [ ...newArr.slice(0, newArr.indexOf(find)),
...newArr.slice(newArr.indexOf(find) + 1)];

}

return findPairs(
newArr.slice(1),
newArr[0],
pairs
);
...

Run it again:

// Example 1 - Assuming
// N = 7
// AR = ("1 2 1 2 1 3 2").split(' ');
// ["1", "2", "1", "2", "1", "3", "2"]
findPairs(AR.slice(1), AR[0], 0);// ar = ["2", "1", "2", "1", "3", "2"]
// find = "1"
// pairs = 1
// ar.slice(1) = ["2", "1", "3", "2"]
// find = "2"
// pairs = 2
// ar.slice(1) = ["3", "2"]
// find = "1"
// pairs = 2
// ar.slice(1) = ["2"]
// find = "3"
// pairs = 2
// Returns = 2 (Correct solution)

Solution

Now that we figured it out, let’s put everything together:

function findPairs(ar, find, pairs) {
if (ar.length > 0) {
let newArr = ar;

if (newArr.indexOf(find) > -1) {
pairs++;
newArr = [ ...newArr.slice(0, newArr.indexOf(find)),
...newArr.slice(newArr.indexOf(find) + 1)];
}
return findPairs(
newArr.slice(1),
newArr[0],
pairs
);
}

return pairs;
}
function sockMerchant(n, ar) {
const min = 1;
const max = 100;

ar = (typeof ar === "string") ? ar.split(' ') : ar;

if (arar.length >= min
&& ar.length <= max
&& n === parseInt(n, 0)
&& n >= min
&& n <= max
&& n === ar.length) {
return findPairs(ar.slice(1), ar[0], 0);
}

// if does not meet criteria return 0
return 0;
}

Test Cases

// N = 9, AR = "10 20 20 10 10 30 50 10 20", Expected 3
// N = 15, AR = "6 5 2 3 5 2 2 1 1 5 1 3 3 3 5", Expected 6
// N = 1, AR = "100", Expected 0
// N = 1, AR = "101 100", Expected 0
// N = 0, AR = "", Expected 0
// N = 101, AR = "10000", Expected 0
sockMerchant(9, "10 20 20 10 10 30 50 10 20"); // 3 ✅
sockMerchant(15, "6 5 2 3 5 2 2 1 1 5 1 3 3 3 5"); // 3 ✅
sockMerchant(1, "100"); // 0✅
sockMerchant(1, "101 100"); // 0✅
sockMerchant(0, ""); // 0 ✅
sockMerchant(101, "10000"); // 0✅

Our code passed the test case scenarios, meets the requirements, and ultimately passes the challenge.

Feedback?

If you have any tips or recommendations on how this can be solved better or optimized, I would love to talk in the comments and welcome any feedback.

If you got value from this, please give this article some applause 👏 and share it on twitter 🐦 or other social media platforms. Thanks again for reading. 🙏

Please also follow me on twitter: @codingwithmanny and instagram at @codingwithmanny.

--

--

--

Web Application / Full Stack JavaScript Developer & Aspiring DevOps

Love podcasts or audiobooks? Learn on the go with our new app.

Recommended from Medium

Blog Post 5

Deploying ReactJS With Docker

Tezos Domains for Developers #1: Resolving Domains

Applying the Liskov Substitution Principle in React

Devices on desk

Redux State Management in LWC (Lightning Web Components)

async/await in NodeJS

Better know your NPM package bundles

Quiz App with React (Class components ) and Redux

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Manny

Manny

Web Application / Full Stack JavaScript Developer & Aspiring DevOps

More from Medium

How to solve npm ERR! cb() never called

Simple Cipher Solution

Coding — The Artist’s Unusual Ally

[Leetcode practice] 17. Letter Combinations of a Phone Number