Compare the Triplets

See the original problem on HackerRank.

Solutions

This is clearly an easy problem we can experiment with.

The easiest way to write the solution in C++ is:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
array<int, 3> a, b;
copy_n(istream_iterator<int>(cin), 3, begin(a));
copy_n(istream_iterator<int>(cin), 3, begin(b));

int alice_points = 0;
int bob_points = 0;

for(int i = 0; i < 3; i++)
{
    if (a[i] > b[i])
        alice_points++;
    if (a[i] < b[i])
        bob_points++;
}

A little more efficient: else if

1
2
3
4
5
6
7
8
9
void compare_triplets(int* a, int* b, int* points) {
  for (size_t i = 0; i < 3; i++) {
    if (a[i] > b[i]) {
      ++points[0];
    } else if (a[i] < b[i]) {
      ++points[1];
    }
  }
}

An alternative is to use the result of the comparison to select which point to update. Even though this solution doesn’t use branches (if), on x86 with compiler optimizations on, this is about 7x slower than the if solution above. Loop is unrolled on both programs.

1
2
3
4
5
void compare_triplets(int* a, int* b, int* points) {
  for (size_t i = 0; i < 3; i++) {
    points[a[i] < b[i]] += a[i] != b[i];
  }
}

This, instead, is as fast as the else if above:

1
2
3
4
void compare_triplets3(int* a, int* b, int* points) {
  points[0] = (a[0] > b[0]) + (a[1] > b[1]) + (a[2] > b[2]);
  points[1] = (a[0] < b[0]) + (a[1] < b[1]) + (a[2] < b[2]);
}

We can use inner_product to exploit the zip | map | reduce pattern:

1
2
3
4
5
6
array<int, 3> a, b;
copy_n(istream_iterator<int>(cin), 3, begin(a));
copy_n(istream_iterator<int>(cin), 3, begin(b));
cout << inner_product(begin(a), end(a), begin(b), 0, plus<int>(), greater<int>()) << " " 
     << inner_product(begin(b), end(b), begin(a), 0, plus<int>(), greater<int>());
}

A Java alternative:

1
2
3
pointsAlice = ((a0>b0)?1:0) + ((a1>b1)?1:0) + ((a2>b2)?1:0);
pointsBob = ((a0<b0)?1:0) + ((a1<b1)?1:0) + ((a2<b2)?1:0);
System.out.println(pointsAlice + " " + pointsBob);
We've worked on this challenge in these gyms: modena 
comments powered by Disqus