4
\$\begingroup\$

Let's say I have a number set like below

// 1,2,3,4,5,6,7,8

Now I want to go from 2 to 5. To go from 2 to 5 there are two ways: one is forwards and another is backwards

forwards: +3
backwards: -5

Backwards is basically going to backside from 2 and reaching 5 from end of numbers

ex

-5 goes like this: 2 -> 1 -> 8 -> 7 -> 6 -> 5

so there are some examples how the function should return

    from  to    max    result
    2     5     8      3
    1     8     8     -1
    8     1     8      1
    7     1     8      2
    8     5     8     -3

I have created one function which is working as expected but I am sure there must be other good ways to achieve the same result. I'm looking for improvement in my function or maybe a full newly created function which is more simple. Thanks in advance

Here is my code

function findClosest(from, to, max) {
    let isReversed = from > to
    if(isReversed) {
        let hold = to
        to = from; from = hold
    }
    let rDiff = max - to,
        forwordDis = to - from,
        backwordDis = from + rDiff,
        result = forwordDis < backwordDis? forwordDis : -backwordDis
    if(isReversed) { result -= result*2 }
    return result
}

console.log(findClosest(2,5,8))
console.log(findClosest(1,8,8))
console.log(findClosest(8,1,8))
console.log(findClosest(7,1,8))
console.log(findClosest(8,5,8))

\$\endgroup\$
2
  • \$\begingroup\$ I have a question, the set you receive as parameter comes always sorted? \$\endgroup\$ Oct 10 '21 at 4:15
  • \$\begingroup\$ yes ................. \$\endgroup\$ Oct 10 '21 at 4:16
1
\$\begingroup\$

I got your initial approach, but I couldn't understand your execution... There are a few things I might add to it and few thing I might remove. My style of writing code always goes after readability first and optimization second. If I can achieve both then that's a bonus...

Your approach my way

Actually I had the same idea as soon as I read your problem statement but well you executed it first so its no longer my idea.

Here is how I interpreted your approach...

The number scale
1-2-3-4-5-6-7-8

Lets choose two variables, in which one will act as a starting node and one will act as the ending node (In other words from and to). I am going with your pick, from = 2 => f and to = 5 => t

1-2-3-4-5-6-7-8
  |     |
  f     t

Now to find the distance I need to find the absolute difference between from and to

1-2-3-4-5-6-7-8
  |     |
  f~~3~~t

Okay, now I have my absolute difference... This means I need to travel three nodes from 2 to reach 5, but I can also travel the other way around. Therefore I will call my absolute difference as forwards

To travel the other way around, I need to know two offsets. One is from the start of my number scale to my from and other is from the end of my number scale to my to

1-2-3-4-5-6-7-8
  |     |
< 1     3 >

Okay... I now have my 2 offsets I will name them leftOffset => 1 and rightOffset => 3

To get the reverse distance,(I shall call it backwards) I need to add my two offsets and one for link between end and start. Therefore backwards = leftOffset + rightOffset + 1 => 5

Okay now that everything is set, I need to find the minimum distance. In this case it will be the forwards variable... But the values of my from and to can vary. So, what if their values are reversed from = 5, to = 2

In this case the variables forwards and backwards exchange their meaning. Therefore I need to react the same way and check if my calculations are correct. To do this I will just negate the final result, if my from is greater than to

Here is my version of your code (I also made it so that you can change your number series, using the min value):

function findClosest(from, to, min, max){
    let smaller = (from > to) ? to : from,
        bigger = (from < to) ? to : from;
    
    let leftOffset = smaller - min,
        rightOffset = max - bigger;
    
    let forwards = bigger - smaller,
        backwards = leftOffset + rightOffset + 1;
    
    let result = (backwards > forwards) ? forwards : -backwards;
    result = (from > to) ? -result: result;
    
    return result
}
console.log("Input: (from, to, min, max), Output: (minimum distance)");
// ---- Your Test Cases ---- //
console.log("Input: (2, 5, 1, 8), Output: " + findClosest(2, 5, 1, 8)); // 3
console.log("Input: (1, 8, 1, 8), Output: " + findClosest(1, 8, 1, 8)); // -1
console.log("Input: (8, 1, 1, 8), Output: " + findClosest(8, 1, 1, 8)); // 1
console.log("Input: (7, 1, 1, 8), Output: " + findClosest(7, 1, 1, 8)); // 2
console.log("Input: (8, 5, 1, 8), Output: " + findClosest(8, 5, 1, 8)); // -3

// -- My custom test case -- //
console.log("Input: (2, 5, 2, 5), Output: " + findClosest(2, 5, 2, 5)); // -1

Now for my next approach

Everything you have seen above remains the same, but now I don't calculate the offsets. Instead I calculate the total number of elements.

Since I have my forwards variable set to my absolute difference... It is actually the length of my line segment from 2 to 5 on my number scale.

Then I can just subtract this segment from number scale to get the reverse distance

1-2-3-4-5-6-7-8
  |     |
  |~~3~~|
  |~seg~|

1-2-3-4-5-6-7-8
|~~~~~~8~~~~~~|
|~ num-scale ~|

seg - num-scale
|~|~ 5 ~|~~~~~|

Everything else remains the same...

Hence here is the code (Yes, I also made this code to be series extensible):

function findClosestTwo(from, to, min, max){
    let smaller = (from > to) ? to : from,
        bigger = (from < to) ? to : from;
    
    let totalNumberOfElements = max - min + 1;
    
    let forwards = bigger - smaller,
        backwards =  totalNumberOfElements - forwards;

    let result = (forwards < backwards) ? forwards : -backwards;
    
    result = (from > to) ? -result : result;

    return result;
}
console.log("Input: (from, to, min, max), Output: (minimum distance)");
// ---- Your Test Cases ---- //
console.log("Input: (2, 5, 1, 8), Output: " + findClosestTwo(2, 5, 1, 8)); // 3
console.log("Input: (1, 8, 1, 8), Output: " + findClosestTwo(1, 8, 1, 8)); // -1
console.log("Input: (8, 1, 1, 8), Output: " + findClosestTwo(8, 1, 1, 8)); // 1
console.log("Input: (7, 1, 1, 8), Output: " + findClosestTwo(7, 1, 1, 8)); // 2
console.log("Input: (8, 5, 1, 8), Output: " + findClosestTwo(8, 5, 1, 8)); // -3

// -- My custom test case -- //
console.log("Input: (2, 5, 2, 5), Output: " + findClosestTwo(2, 5, 2, 5)); // -1

If you are crazy about the optimizations, you can technically compress both the functions in a single line.

Note: I have not used any in-built math functions in JavaScript for performance of course.

Note: These functions should in theory be very convenient for you to use as you never have to deviate and change the min and max values.

Note: You can also increase your number scale to include negative values.

Edit: I just now got the previous answer to your question... His approach is kind of like my second function but different in theory. I did not even read his answer because the names and comments made me dizzy. Its a cool approach though, nice one fam.

\$\endgroup\$
3
  • \$\begingroup\$ i must say you have a really clean code i just understand everything in one read also it is solving the problem flawlessly , previous answer was solving the problem with proper technique to work with negetives also but i liked your code obviously for readability and technique both \$\endgroup\$ Oct 11 '21 at 20:51
  • 1
    \$\begingroup\$ Glad I could help you... I prefer a readable code instead of writing comments. I have a bad habit of not commenting stuff so I try my hardest to make everything readable. The habit of not writing comments has bitten me back a few times now, made me a whole new person. \$\endgroup\$
    – Neopentene
    Oct 12 '21 at 7:16
  • \$\begingroup\$ i think i should follow your practice \$\endgroup\$ Oct 12 '21 at 19:27
1
\$\begingroup\$

Optimization / Simplification

Your code can be converted into the following

// Let X be a subset of Z (the integers) from a to b.
// Calculate the shortest distance between x_a and x_b
// using the forward and backward metrics

// THIS ALGORITHM ASSUMES THAT a < b
function findClosest(a, b, x_a, x_b) {
    // common distance between a and b in the number line
    let l1Norm = Math.abs(x_a - x_b);
    let numberOfElements = b - a + 1;
    let backwardsDistance = numberOfElements - l1Norm;

    let minDist = (l1Norm < backwardsDistance)? l1Norm : -backwardsDistance;

    return x_a < x_b? minDist : -minDist;
}

console.log(findClosest(1, 8, 2, 5))
console.log(findClosest(1, 8, 1, 8))
console.log(findClosest(1, 8, 8, 1))
console.log(findClosest(1, 8, 7, 1))
console.log(findClosest(1, 8, 8, 5))

console.log(findClosest(-7, 8, 4, 5))
console.log(findClosest(-7, 8, 5, 4))

Please note that this solution applies for any integer number set instead of 1 to n sets

The why of this code is more of a resolution using a diagram:

explanation img

It turns out that as the set is an integer one, it's countable.

We are asked to compute the distances forward and backwards, so, our set which usually is represented with a line of numbers, can be converted into a circle. Where we will find that there's a relation between the forward and backward distances through the number of elements in the set.

Sometimes (specially in data structures class) we should draw something to give us an "outside" view about a problem.

Well, I hope this helps you!

\$\endgroup\$
1
  • 1
    \$\begingroup\$ well you have described things quite well i will be accepintg your result after some days to get more answer that graph helped understand well about your version of code thanks for your time and knowledge \$\endgroup\$ Oct 10 '21 at 20:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.