# Horse Racing Duals puzzle discussion

#159

Try google too, `sort array bash` gives a fine answer. (1st link)

#160

Parentheses are missing: `arr2=( \$(sort -g) )`

#161

I tried google, I have readed everything I found on stackoverflow and nothing is optimized enoughâŠ

This code doesnât works with me but `sorted=(\$(printf '%s\n' "\${array[@]}"|sort))` works

I donât know what I can optimize because I picked up so many differents solutions on google that I doesnât know what I can do know because nothing has worked with me

#162

on stackoverflow, I tried both this:

``````IFS=\$'\n' sorted=(\$(sort <<<"\${array[*]}"))
``````

and this:

``````sorted=(\$(printf '%s\n' "\${array[@]}"|sort))
``````

and both works to get 100%

#163

Ok @CvxFous, thank you but with this I canât get 100%, the problem may come from the second loop, after having sort the array, I did this to find the smallest :

``````    smallest=-1
for (( i=2; i<N; i++));do
Â Â Â  j=\$(( \$i-1 ))
Â Â Â  a=\${sorted[i]}
Â Â Â  b=\${sorted[j]}
Â Â Â  diff=\$((a-b))
Â Â Â  if [ \$smallest -eq -1 ] || [ \$diff -lt \$smallest ]; then
Â Â Â Â Â Â Â  smallest=\$diff
Â Â Â  fi
Â Â Â  if [ \$smallest -eq 0 ]; then
Â Â Â Â Â Â Â  break
Â Â Â  fi
done
``````

What do you think ? This not optimized enough ?

#164
``````j=\$(( \$i-1 ))
a=\${sorted[i]}
b=\${sorted[j]}
``````

merge those three lines together, each time you use `\$` is expensive, and then

``````smallest=-1
``````

start with something like smallest=500000000 so you donât have to do two conditions each time.

#165

I see, so now I have this :

`````` smallest=5000
for (( i=2; i<N; i++));do
Â Â Â  diff=\$((\${sorted[i]}-\${sorted[i-1]}))
Â Â Â  if [ \$diff -lt \$smallest ]; then
Â Â Â Â Â Â Â  smallest=\$diff
Â Â Â  fi
done
``````

But still too slow, can it be a bug ? Because in python it was immediate

#166

I found my way here : Find the minimum difference between numbers in a sorted array in bash and it works
Thank you all for your help !

#167

If youâre using Java, just go with the ArrayList, and thatâs all for Horses in disorder

#168

Hi,
Iâm interested in that tip tooâŠ I donât know if it is something with the input or with the time of excecution, or whateverâŠ

#169

Hi all,

I had great issues in bash with optimization too. All tests would pass except the âMany horsesâ and âHorses in disorderâ.
Turned out that sorting was not the main issue.
Performance was.
Try to keep the if statements as short as possible and optimize the way you read Pi into an array where my key elements.
Too bad this forum has no spoilers option otherwise i could give some tips that would be invisible for those who do not want to see them.

I read Pi into an array with:
`myar+=( \$Pi )`

Use the constraints given for the puzzle:
`0<Pi=<10000000 # how big can the difference between two numbers be?`

Hope this helps some of you.

Best,

#170

Hello people,

I managed to finish this puzzle 100% using VB.NET but when I try to do the same in LUA I canât sort the array with the data for Pi because the zeros seem to vanish! Instead of getting (0 5 8 9) for the Simple case I get (5 8 9).

Can anyone explain that behaviour?

#171

Note that this problem can be solved in O(N) using integer sorting algorithm.
You need to instantiate an array as big as the input range, in this case 1000000 bit array.
Each bit represent if the relative value is present in the input data.

The first step is to parse the input and set the bits, so for example if the value 123 is present in the input you set the 123th bit to 1. This will take O(n) where n is the number of inputs.
Second step is to check the smaller consecutive number of zeros you can find in the array starting from the first one and finishing on the last one. This will take O(m) where m is the input range.

#172

Hi there, (for java only)
to this puzzle , I forced myself to do all the processing with one stream.
I managed, but I wonder if anyone else tried to do, to share some problem or simply to see another implementation with only one stream .

Cya =)

#173

You can do a little trick, while scanning the input, you can check if horses already are in an order. So if they are, you can skip the part where you put them in order, thus saving some time. I noticed the 3rd test has a lot of horses, and they seem to be in an order already.

#174

What the hell is wrong with this âOperation timeoutâ error msg ???
It tells that âYour code is not optimized !!!?â, what kind of optimization do you need !!!?
I have this f**king problem in 2 puzzles !!!
Can anyone help me with this plzzzzzz?

#175

The problem is that your code is too slow.

#176

Trying to get my code to pass all the tests for this puzzle, but it wonât pass test 6 âhorses in disorderâ. Using Python 3. Itâs a pain that I canât see the data the code is being run on. As the name hints, I presume the dataâs not ordered, but that shouldnât matter because my code sorts it before iterating over it. Any ideas?

#177

I did it at last !!! with a little trick !!!
I changed the sorting order from big to small !!! and it worked
But I think itâs not right to solve problems in this way !!!

#178

Guys I am really struggling with the C# solution. Iâm passing all of the validation tests apart from the âhorses in disorderâ one so Iâm guessing the fault lies within the performance of my sorting algorithm.

Iâm using the SortedSet - as I parse each line, I throw it into the SortedSet. Then I run a For Each over the SortedSet, performing the comparison of strengths, and get the minimum. Any ideas where Iâm going wrong?