Horse Racing Duals puzzle discussion

Thanks! This little change allowed me to pass the third test case. (y)

Thank you, it really helped me. :kiss:

Yeah, when I tried it in Bash had the same test not passing (ā€œfirst two horsesā€).
Turned out to be I was using just sort, when I used sort -n it worked!!
Thanks for the heads up.

For information, itā€™s a bit tricky, but the Horse Racing puzzle is doable with a 100% score in pure bash without using any external tool like sort, awk, etc.

Python

import array

pi = array.array(ā€œIā€) #unsigned integer array, much faster than normal list.

#append horse_pi data to pi array
#sort
#do diff between pairs
#find min

Just finished in Bash with the 3 achievements. Iā€™ve never used Bash before. It took me hours of trial and error. If you are struggling with this puzzle in Bash, donā€™t think that there is something wrong with you because this is really tough. Trying to process 100,000 numbers in the time given made me want to hurt my keyboard.

Thanks a lot to the people on this thread, in particular Yakuā€™s tip on not needing to compare the difference between every two elements in a sorted array with the current minimum difference really helped. For some reason creating a second sorted array containing the differences and the answer being the first element in that array worked in Bash. Itā€™s a horrible algorithm but it worked.

I tried with an elegant solution that only iterated over the elements once but it never worked quickly enough for me in Bash.

dgo_ponciano thanks for the reminder about ā€œsort -nā€ for doing a numeric sort.

The most useful web page for me was this: sorting arrays

1 Like

Never would have thought that the positioning of the incrementation would effect performance. Now Iā€™m a curious at what the underlying bit code differences are.

Actually, for Bash:

  1. sort -n isnā€™t really a bottleneck at all. It finishes pretty quick relative to everything else. On my laptop with only 2 cores, itā€™s about .12 seconds. Fun fact: the hostā€™s computer uses 8.
  2. No need for an array at all. Just work with the sorted string. Scan one line at a time, keep the old one in memory. Easy day.

Anyway, it finishes in about 1.35s on my laptop, less than a tenth of which is spent sorting. Not spectacular(?), but good enough.

Hi Iā€™ve given some thoughts on this question. But so far the only solution Iā€™ve come up with is to sort the array which records all the pi of the house the compare the pairs as well.

Am I missing anything to find a better solution?

I used sort :smile:

# remove first line of stdin and get me the rest sorted (as numbers)
for val in `tail -n +2 < /dev/stdin | sort -g`; do
    # ...
done
3 Likes

(c++) Ca roule parfaitement chez moi avec qsort pour le tri. Il y a juste un test que je nā€™arrive pas a valider, cā€™est pour les 2 derniers chevaux pourtant il me semble aue je traite tout (jā€™ai verifie 6 fois).

Hey, guys

The second test is not reading the first input ā€œ10ā€.
I asked for help on the chat and they told me I may had found a bug. I donā€™t really know.
The input reading algorithm was the default, I didnā€™t write it, and it works for all other cases.
EDIT:NO FULL CODE

Thank you

The first (10) input is read, Itā€™s the number N that you used for the for-loop. You didnā€™t find a good algo yet and itā€™s pure luck that you pass the test 1 and 3.

In the first test the strength input is 5,8,9 and the diff is 1.
In the second test the input is: 5,15,17,3,8,11,28,6,55,7. The strongest is 55 and the second strongest is 28 and the aktual diff is two, but it says :
Fail
Found: ā€œ2ā€
Expected: ā€œ1ā€

I am confused now, is this a bug or hav i misunderstood the question?

I was also puzzled with this at first.

Issue is that you should not find top 2 horses but horses with smallest difference however they are ranked.

Here it is difference between 6 and 7 (hence 1)

Ohhhh :smiley:

Thank you

Hey guys, Iā€™m doing this level in bash (yeah stupid, ik), and after 2 weeks of trial and error, i finally managed to find a way to sort rapidly and pass all 3 tests using it.
The problem now lies with the other validatorsā€¦ i canā€™t pass the ā€˜2 horsesā€™ validator for example, but when i hardcoded a template with 2 horses to test my code out there were no problems whatsoever; (there are 3 other validators i donā€™t understand alsoā€¦ >.<).
Hereā€™s my code (i commented most lines for those not really BASH savvy #worst_syntax_ever :

http://pastebin.com/UQazQmkJ (code with error prints)
http://pastebin.com/TSMma3HB (code without)

Any help of any kind would be immensly appreciated, been stuck on it for quite a while.

Thanks.

1 Like

Solve ā€œHorse-racing Dualsā€ problem in Bash and get a 100% score. Does this mean I need to change my default programming language(JS) to acheive this? If yes then I will loose my other pending games?

Enlighten me :smile:

Yes, the achievement is for solving this puzzle in a special language called bash^^.
You can switch between language, you can solve puzzles in different languages several time, the code is saved, the editor always shows the last submitted code of the currently picked language.

1 Like

I have used the same approach, but when written as for loop it seems to be slower then expected by test case. So I passed generator (which computes diffs of pairs) to min function and all tests passes. So time is really the key for that test.