Puzzle from comp.lang.c++

[NMTop40]

Thought I might bring this here as a bit of fun:

Hi

I recently had to write a small code in a competition ,but my code was
rejected cause it failed in 1 of test cases.


The problm was .....we are given vector of strings....each string
consists of either 1 or 2("12122" 0r "2121" so on..)...i had to find
the that string where percentage of '1' is minimum.Now the problem and
solution both are trivial but i was told that comparing double with <
or > sign doesn't ensure a correct solution always ie it fails for
number differing by a very small value.


Also if two string have indentical small percentage of '1 then the
smallest indexed string is to be returned(ie string of index 0 in
vector is identical with index 4 then 0 is to be returned.)


The code goes something like this.....

#include<iostream> 
#include<string> 
#include<sstream> 
#include<vector> 

using namespace std; 


class Elections
{ 
public: 
        int visit(vector<string> like); 
}; 

int Elections::visit(vector<string>like) 
{ 
        double min=1000,temp=0; 
        int index=0; 

        for(int i=0;i<like.size();i++) 
        { 
                temp=0; 
                for(int j=0;j<like.size();j++) 
                        if(like[i][j]=='1') 
                                temp++; 

                        temp=temp/like[i].size(); 

                        if(min>temp) 
                        { 
                                min=temp; 
                                index=i; 
                        } 
        } 
        return index; 
}

The test case for which my solution fails is
{"11122211222111111112121", "11122211222111111112121",
"11122211222111111112121", "11122211222111111112121",
"11122211222111111112121", "11122211222111111112121",
"11122211222111111112121", "11122211222111111112121",
"11122211222111111112121", "11122211222111111112121"}

The above case has all equal string yet it returned 9(index instead of
0) according to the system test they carried out.
I tried running the above code in a different compiler and the answer i
got was correct.(ie 0)


I am not sure , besides the floating point comparison ambiguity what
other reason could have led to different results in two different
compilers.


thanks in advance


Somesh

[manish_velankani]

Its working and in my case with gnu v 3.3 its giving correct output with index 0.

Probably we can try using float instead of double.

[Vedam Shashank]

I have one question.

Why use double, When you could have done using just integers?

Which is how I would have done.

[upashu2]

I doubt whether it is safe to apply >,<, == and != operators on double & floats (including in this case). it is better to find out what accuracy you want, is it 0.0000001 or 1e-32 or something else. If there are two double d1 and d2, then instead of doing d1 > d2, it is better to do ( d1 - d2) > MY_ACCURACY. where MY_ACCURACY is also double and consists our accuracy value- (the least value which bothers us or max value which don't bother us), say MY_ACCURACY = 0.0001.

I have also doubt that dividing two same numbers always will give the same output(in case of double & float), as per my experiance on doubles & float, i found answers somethimes 1.9999999998 and some times 2.0000000001 or something else, for same operation on same numbers.
It happens since IEEE representations are not exact representions of double & float numbers, they are only approximations of double & float.

[NMTop40]

I posted a solution on comp.lang.c++ which didn't use double at all. Instead I generated a struct which number of 1s and number of 2s (could have used std:air but I added other featuers as well).

I then cteated a transformer so I could do std::transform() on a string and then I used min_element on my struct.

As the struct:
[code]
struct pair12
{
int num1s;
int num2s;
pair12() : num1s( 0 ), num2s( 0 ) {}

pair12& operator() ( char ch )
{
switch ( ch )
{
case '1': ++num1s; break;
case '2': ++num2s; break;
// default: do nothing but could throw exception or warning
}
return *this;
}
};

As a comparison I simply did:

operator < ( const pair12 & left, const pair12 & right )
{
   return left.num1s * right.num2s < left.num2s * right.num1s;
}

Now the transformer;

struct pair12FromString
{
   pair12 operator() ( const std::string & s ) const
   {
       return std::for_each( s.begin(), s.end(), pair12() );
   }
};

You could also use std::accumulate instead of std::for_each, and use operator += and operator + to add characters to pair12 instead of operator().

Now we'll put our transformer into action.

std::vector<pair12>::size_type minPosition( const std::vector< std::string > & v )
{
   std::vector< pair12 > vTemp;
   vTemp.reserve( v.size() );
   std::transform( v.begin(), v.end(), std::back_inserter( vTemp ), pair12FromString() );
   return std::distance
        ( 
           vTemp.begin(),  
           std::min_element
                ( vTemp.begin(), vTemp.end() ) 
        );
}

[NMTop40]

I doubt whether it is safe to apply >,<, == and != operators on double & floats (including in this case). it is better to find out what accuracy you want, is it 0.0000001 or 1e-32 or something else. If there are two double d1 and d2, then instead of doing d1 > d2, it is better to do ( d1 - d2) > MY_ACCURACY. where MY_ACCURACY is also double and consists our accuracy value- (the least value which bothers us or max value which don't bother us), say MY_ACCURACY = 0.0001.

I have also doubt that dividing two same numbers always will give the same output(in case of double & float), as per my experiance on doubles & float, i found answers somethimes 1.9999999998 and some times 2.0000000001 or something else, for same operation on same numbers.
It happens since IEEE representations are not exact representions of double & float numbers, they are only approximations of double & float.

It is true that they are not accurate, but if you divide 4.0 by 9.0 twice you should get the same result. You should probably also get the same result if you divide 8.0 by 18.0 or any two integers where the ratio is 4/9.

[RoboTact]

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

bool scmp(const string &s1,const string &s2)
{
    int n11=count(s1.begin(),s1.end(),'1');
    int n12=count(s1.begin(),s1.end(),'2');
    int n21=count(s2.begin(),s2.end(),'1');
    int n22=count(s2.begin(),s2.end(),'2');
    return n11*n22-n12*n21<0;
}

int main()
{
    vector<string> test;
    test.push_back("1121121");
    test.push_back("1221121");
    test.push_back("1111121");
    
    cout<<distance(test.begin(),min_element(test.begin(),test.end(),scmp))<<endl;
    return 0;
}

[NMTop40]

yours uses less code but mine is probably more efficient as it only has to count the strings once.

[Yves M]

What was the conclusion from comp.lang.c++ then? The thing is that it can fail if:
1) The FPU is faulty (Pentium bug e.g.)
2) The compiler doesn't put the FPU back into the same state each time

Let's discard 1), so 2) is the only option. Is that compiler correct then? I would doubt it. The thing is that there are only two floating point operations and the operands are guaranteed to be the same between different vector indexes. Both temp and like[i].size() are always the same. The only way temp would not be the same each time would be if you were overflowing the exact representation range and that definitely doesn't happen here. So what messes up? The division or the comparison? Probably the division, since a floating point comparison is "exact" (i.e. if the numbers have equal bits, a < b will always be false).

What was the test system (CPU/FPU and compiler)?