Horse Racing Duals puzzle discussion

Puzzles
#55

Just implemented a solution in bash, it worked ok.

Then i tried

python -c "some one liner to solve this"

and it actually worked. Is this intended?

2 Likes
#56

Vraiment obliger Ă  utiliser le bash -_-
J’ai tentĂ© tout ce qui me passait par la tĂȘte mais rien n’y fait j’ai soit un problĂšme de performance soit des erreurs que je ne comprends pas.
Quelqu’un pourrait il m’éclairer sur le sens de cette erreur :
/tmp/Answer.sh: line 19: minDistB = - : syntax error: operand expected (error token is "- ")at Answer.sh. on line 19
la ligne :
        ((minDistB = ${tab[${i}]}-${tab[${j}]} ))

Merci

#57

Essaye de chercher un peu sur google, avec les termes: “substract shell script” je suis tombĂ© sur ça et lĂ  tu as plein d’infos.

Bon courage pour finir le bash rider :wink:

#58

Merci mais déjà lu
Si j’ai postĂ©, c’est que ca fait dĂ©jĂ  bien plusieurs heures que je regarde.
J’ai fini par regarder les forum car je pensais avoir manquĂ© une idĂ©e d’algorythme.

Je suis super déçu de me rendre compte que non il n’y a pas d’idĂ©e nouvelle.

Juste Ă©crire soit mĂȘme un tri n’est pas performant ( au great je ne m’y attendais pas
)

Ca m’ennerve assez de me prendre la tĂȘte sur un problĂšme liĂ© au langage
Je suis parti dans le man du sort mais sérieux 
 pourquoi lié une récompense à un langage -_-
Surtout du bash quoi


Du coup je suis Ă  la recherche de la fameuse page stackoverflow qui donne la solution pour le sort
Ou de tout exemple de comment utiliser la fonction sort sur un tableau

Merci d’avance

[EDIT] Bon ben finalement mĂȘme avec un tri fait par un sort, ca ne passe pas au niveau temps

Je seche
mon tri :
readarray -t sorted < <(for a in “${tab[@]}”; do echo “$a”; done | sort -n)

#59

what is bash rider?

#60

I was stuck on the Bash version for awhile. That is, the large data set problem was too slow. After much frustration, I was able to narrow down the problem. I hope this is a help to someone.

Array access can be very problematic in Bash, for a number of reasons. This seems to be especially true when using any kind arithmetic in your index. For example:

${val[$n-1]} seems perfectly reasonable. But here’s the experience I had.

I rigged my test to always print out 47 at the bottom, then I started tweaking the loop variable to see how many pieces of data I could process and still get to the end before timing out. That is, instead of i < N, my loop was i < 10000. (N in this case is 99999) After some tinkering around, I found that my code could do about 36,000 iterations and still make it to the end in time. So I needed to cut that run time to about a third. (Mind you, this was the bash version of the same solution I had no trouble with in C++.)

I don’t want to give anything away, so I’m just going to give an abstract of a part of the solution in pseudo code.

for i < N, i++
{
read P
for j > 0, j–
{
if(val[j-1] < whatever) etc
}

x = val[j-1] - y
}

As I said, I had to lower N to 36000 to get this code to work. Here’s where things got weird. I tried removing the arithmetic from that last line, making it:

x = val[j] - y

This had no problem at all executing up to 99999. Simply changing that j-1 to j tripled my speed. (In case you’re wondering, this was all happening inside a condition wherein j was greater than 0.) That gave me the idea to try something a little odd:

j–
x = val[j] - y

That gave me the decrement I wanted, and took the arithmetic out of the indexer. But still, the performance dropped back to the 36000 level. After many frustrated and convoluted attempts to make Bash do roughly the same thing, this is the solution that for whatever reason gave me the performance I needed:

for i < N, i++
{
read P
for j > 0, j–
{
if(val[j-1] < whatever) etc
data = val[j-1]
}

x = data - y
}

So the moral of the story is:

  1. I’m stupid.
  2. Bash is stupid.
  3. When using Bash, avoid any form of nested arithmetic wherever possible, because (See 2).

I can’t tell you why certain things worked and certain things didn’t. Just be very careful how you access arrays in Bash, because they’re in reality linked lists, and Bash can be weird about how it parses variables, since they’re all in reality strings.

6 Likes
#62

C’est assez malin ça :slight_smile:

Par contre j’ai dĂ» utilisĂ© tail pour que ça passe

#63

whats the problem with my code
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <math.h>

/**

  • Auto-generated code below aims at helping you parse

  • the standard input according to the problem statement.
    **/
    int main()
    {int h=999;
    int N=2;
    int c=0;
    int s;
    for (int i = 0; i <N; i++) {
    int Pi;

    scanf("%d", &Pi);

    if (i>0)
{
   
    c=(Pi-s);
   
    if(h >c){h=c;}

    } s=Pi;

}

printf("%d \n",h );

//return 0;
}

#64

In some tests, horses aren’t sorted. You have to sort them before seeking the minimal difference.

#65

Dire que c’était marquĂ© sous mon nez :smiley:

Bon en revanche ca ne suffit pas de mon cĂŽtĂ© :’(

Est ce que let est plus lent que (( )) ?
Je ne sais pas trop comment ca fonctionne mais un jour il veut bien (()) un jour il ne veut plus. Aujourd’hui j’ai du repasser avec let car plus moyen d’utiliser les parenthùse 


#66

Hi all !

Just for fun :
I struggled to get the last test case with the numerous horses in bash
 I didn’t understand why my algorithm was slow.

So, I tried something I never thought about before : if compilers like gcc and g++ were available from the bash interpreter, then all I had to do was to compile a C/C++ program and then run it.
So, I did something like this :

#!/bin/bash

read N
g++ -o horses -x c++ - <<CODE
/* Here document with your C++ code */
// 

CODE

./horses

And the “Ah moment” ! It worked !!! :slight_smile:

PS : I know it’s dirty. And admins may soon want to restrict the use of external programs


6 Likes
#67

Hah, I had the exact same solution, except I used python instead of C++.

I don’t see how they could restrict the use of external programs, as bash is basically 99% “external programs” and is useless without them.

#69

Did someone manage to do 100% in c++? I’m stuck at 63% just because my code is ‘slow’.
Djiiz method is not working for me.

#70

Yes i did, and seriously? C++ has strong sorting function and is pretty fast most of the time. So if you can’t manage it, then you don’t have found the key to that puzzle :wink:

Keep trying :thumbsup:

1 Like
#71

Are you trying to solve it in Bash or in “legit” C++? Because Djiiz method is a kind of hack for the Bash achievement.

@CvxFous: This kind of puzzle has a different timeout depending on the language. As PHP interpreter is written in C, standard functions like sorting are actually really fast too and gives you way more time for the rest of your algorithm than in C++.

#72

I didn’t knew it @NewboO, thanks :wink:

#73

Hello everybody.

I would try in “pure” Bash at first, but on hudge datas number it was a shame of slow.

Thanks to Sparshong and Libe4 's ideas. I switched my mind, and also use the Bash best friends commands : sed, sort and awk.

I have to say that in this exercice I learned more about awk than i expected. Usually, i uesed awk to print some field, and that’s all (usually, in my Bash script, i don’t care about time speed ^^).

Becarefull, according to code in Awk, there is a fields size limit in tis Awk version (mine hasn’t this).
I had to transform the string into an array.

#74

Hello,

J’ai le mĂȘme problĂšme, as tu trouvĂ© pourquoi ce test ne passe pas ?

Merci.

#75

Si on te donne un indice, c’est presque la solution

Mais tu fais une action deux fois, alors qu’une seule suffirait.
:wink:

#76

hi every one
my code complete every cases except many horses
 i use java and use hashset to store inputs and with every inputs my code computes its difference with previous numbers and find min and so on till last number, i believe it has not any overflow but it would not accept it and say Process has timed out
i would be appreciate if any one can help
for (int i = 0; i < N; i++) {
get current number from input
for(every member of the hashset){
if ( diff(current number and member) < min)
min=diff(number and member)
if(min==0)break;
}
hash set add current number
if(min==0)break;
}