Horse Racing Duals puzzle discussion

I don’t know the commands in question, would you mind pasting just the commands so i check out the manuals and use them ? I would really appreciated it !

Thanks

Hi everyone ! I did 100% on this puzzle but I switch to bash to get the bonus… This is horrible…
I can’t get green on the last test because my solution is not optymised enough, however i did the same algorithm as in python :confused:

Here is what i do in bash:

For i < N
I read
I add it in tab in a way that tab is sorted in ascending order, to do that I do a dichotomic path
I check the difference with this value and the one before, if it’s 0, i break the for loop

If i didn’t find a difference equals to 0, I loop over tab with i and j = i+1 and calcul the difference for each value

And then i print the smallest difference but it takes too much time in bash, can you please give me some help ?

@dunkdesign The key here is to speed up your sort process. Try looking for quicksort or mergesort, in bash what I think you’re doing right now is an insertsort, and it’s not fast enough.

1 Like

I tought it was te fastest way to sort an array :open_mouth :open_mouth: Thank you !

So I did a quicksort with pivot, it works but still not fast enough… Can I share you my code and have your feedback ?

Best tip I can offer: stop listening to CvxFous, he’s evil! Bash is not meant to be used standalone, but as a glue in a UNIX environment offering a useful set of tools… like the “sort” tool per instance.

1 Like

Ok but how do we use it ? I am really a noob x)

I’m not evil! :smiling_imp:

Seriously though, sort(1) is using quicksort you know :slight_smile:

Let me take a look on how I did it.

EDIT: Okay so while it’s true that sort use quicksort, it must be much better implemented than yours, I checked my code and I indeed used sort(1) :stuck_out_tongue: still, my advice wasnt that bad

EDIT2: how to use it? man sort on any good terminal, or on google if you use Windows.

Ok I’m going to look at man sort :slight_smile:
Thanks

More probably some kind of merge sort, but the important point is that it’s fast enough.

1 Like

Well, I want to use it but I don’t really know how to use it in my code…

When I do a sort like this :

arr2=($(
    for el in "${ARRAY[@]}"
    do
        echo "$el"
    done | sort) )

This is what i get :

BEFORE : 5 15 17 3 8 11 28 6 55 7
AFTER : 11 15 17 28 3 5 55 6 7 8  

any idea ?

I figure out the problem but I don’t know how to fix it, 11 < 3 because 1 is before 3 but It doesn’t seems to work with more than 1 number…

EDIT : I added the -g option and it works, but still to slow… I don’t know what to do…
Here is my code : PLEASE DON’T, SINCERELY, CVXFOUS

It’s a string sort, not an integer sort.

The “-n” option is faster than the “-g” option and you don’t need the latter in this problem. In addition, everything you are doing before your call to “sort” is: read input, split on spaces, store, iterate, output with spaces, redirect… Added value: 0.

Still doesn’t work with -n : Process has timed out. This may mean that your solution is not optimized enough to handle some cases.

I don’t get what you mean after “In addition” , what should I do ? When you say the latter, you mean the part where I search for the smallest ?

No, the latter was referring to the “-g” option. The superfluous part in your code extract above is literally everything, save the call to “sort”.

Oh really xD This is really demotivaing because I have no idea of how I should do…

I’m just saying that both pieces of code do the same thing:

for (( i=0; i<N; i++ )); do
   read ARRAY[i]
done

arr2=($(
    for el in "${ARRAY[@]}"
    do
        echo "$el"
    done | sort -g) )

=

arr2=$(sort -g)

That’s a good start to optimize your code.

What I meant by man sort was to read the manual of sort, which means you should have found out about the -n part by yourself:

-n, --numeric-sort
              compare according to string numerical value

It’s on the first lines, really. For the rest, as florent mentionned, you just have to speed up your processing and you’ll be done in no time

That doesn’t works and it removes the first value of my array :frowning: