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 :slight_smile:
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… :stuck_out_tongue:


#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. :grin:
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. :sunglasses:

Best,

Corné


#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. :slightly_smiling:


#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? :worried:


#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 :grinning:
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?