How to Solve a Problem 5: Horse-Racing Duals and HyperDuals

 Let us take a look at one of the competitors to HackerRank... CodeWars, and one of the puzzles on it. This one is called Horse-Racing Duals, and a harder version called HyperDuals. But one thing at a time. 

You can access the problem here:  Link

Read the problem very carefully. Noticed that it lists "external resources: Sorting, Lists"? Clearly, you will need to sort the solution. 

I am going to do this in JavaScript, which is pretty universal. 

First, they did NOT create any data structure(s) for you, so you have to create your own. I simply called mine horses. And I added a line in the readline loop to load the number into the array. 

const N = parseInt(readline());

var horses= []

horses.length=N;

for (let i = 0; i < N; i++) {

    const pi = parseInt(readline());

    horses[i]=pi

}

But what do we do now? Let's look at the requirements again: We need to find two horses in the horses array that are the "closest" in strength. 

Clearly, we are meant to sort the array (by strength), then go through it again, looking for the smallest difference. 

Sorting is easy if you have been reading this blog... You can call the built-in "sort" method in JavaScript. 

horses.sort((a,b) => a-b); // sorted

Now, how do we find the smallest difference? By going through the entire array, keep calculating differences and keeping the smallest one so far. 

let diff = 10000000 // max possible

for (let j = 1; j< N; j++) {

    if ((horses[j]-horses[j-1])<diff) {

        diff=horses[j]-horses[j-1]

    }

}

And that's it. We have the answer. 

Now, how about a hyperdual?  Instead of a 1-dimensional array, we now have an array of 2-dimensional vectors. 

As this is now 2-dimensional selection, it is NOT possible to calculate a universal strength and sort the array. You are welcome to try, but you cannot get the right answer this way. I've actually tried V^2+E^2, V+E, abs(V-E), and so on. They all break one case or another. 

When you visualize it in your head, you realize that the problem cannot be solved with a single loop. It is time to just loop the loop. 

Consider that if you have 4 items in the array, you need to make how many comparisons? 

The answer is 6 times. Or in this case, (n-1)!  (n=4)

So given the max n=600, it is actually at most, a few thousand comparisons. That's actually not too bad. 

So how do you construct the loop? Again, let us use the n=4 example... [1,2,3,4]  I know we're working with vectors, but we are figuring out the loop(s) involved. 

For an array of 4, we need to make the following comparisons... (1,2), (1,3), (1,4), (2,3), (2,4), (3.4)

Thus the loop is, let's use j and k as we used i for the initialization:

for j from 0 to arr.length-1

    for k from i to arr.length-1 

        do the comparison based on the distance formula given

        if that's the smallest so far, keep it

    endor

endfor

This is pseudocode, and it will go through all the combinations to figure out the minimum distance between the two. 

Now, all we need to do is put all this into code. And that, I leave up to you.