Assert death and deduction on Osmos

The Code Jam Round 1B 2013 Problem A is nicknamed Osmos. Writing googletest test cases for it, I found a way to call once the ASSERT_DEATH macro. Implementing the function, I have also used the template argument deduction. Hence the fancy name for this post.

We have in input an integer representing the weight of our mote (think of a mote like a greedy little sort-of-living organism), and a bunch of integers representing all the other motes in the neighborhood. We want our mote to survive. To do that, it has to absorb all the smaller motes (growing its weight in the process). We could help it in two ways, adding motes that it could swallow to increase its size, and removing motes that are too big for it. Besides, we are lazy. We want to minimize the number of our adding/removing actions.

Test cases would help to clarify the matter. I am using C++11 by GCC 4.8 on a Linux machine. Test cases are written in the xUnit way, using the gtest framework.

unsigned osmos(unsigned myMote, std::vector<unsigned>& motes); // 1

TEST(TestOsmos, CaseSample1) // 2
{
  const unsigned myMote = 2;
  std::vector<unsigned> motes { 2, 1 };

  ASSERT_EQ(0, osmos(myMote, motes));
}

TEST(TestOsmos, CaseSample2) // 3
{
  const unsigned myMote = 2;
  std::vector<unsigned> motes { 2, 1, 1, 6 };

  ASSERT_EQ(1, osmos(myMote, motes));
}

TEST(TestOsmos, CaseSample3) // 4
{
  const unsigned myMote = 10;
  std::vector<unsigned> motes { 25, 20, 9, 100 };

  ASSERT_EQ(2, osmos(myMote, motes));
}

TEST(TestOsmos, CaseSample4) // 5
{
  const unsigned myMote = 1;
  std::vector<unsigned> motes { 1, 1, 1, 1 };

  ASSERT_EQ(4, osmos(myMote, motes));
}

TEST(TestOsmos, CaseBigger) // 6
{
  const unsigned myMote = 42;
  std::vector<unsigned> motes { 1, 40, 12, 7 };

  ASSERT_EQ(0, osmos(myMote, motes));
}

TEST(TestOsmos, CaseMixed) // 7
{
  const unsigned myMote = 2;
  std::vector<unsigned> motes { 8, 15, 30, 40, 60 };

  ASSERT_EQ(3, osmos(myMote, motes));
}

TEST(TestOsmos, CaseBadMote) // 8
{
  const unsigned myMote = 0;
  std::vector<unsigned> motes { 8, 15, 30, 40, 60 };

  ASSERT_DEATH(osmos(myMote, motes),"Assertion .* failed.");
}

1. My osmos function gets in input my mote weight, and all the other motes ones. It gives back the number of adjustments I had to perform to the environment to help my mote. It is not clearly stated in the problem, but any mote weight shouldn't be less than one, and we can assume it would fit in an int.
2. There are four examples provided with the original problem, I have converted them in test cases. In the first one we expect our mote (sized two) to happily eat its smaller brother (one) so to get bigger enough (three) to eat the other one (sized two). No help is required from us, so the function should return zero.
3. My mote has no problem (even no ethical ones) to eat the tiny twins weighting one each, getting in this way big enough to eat the mote two, but it can't eat its brother six. We need to interfere once, either to remove six from the list, or to add a smaller mote so that our mote could absorb it, growing big enough to complete its job.
4. Eat nine, become nineteen. It is not enough to eat twenty, so I provide a eighteen mote, that would immediately be eaten by my mote that grows to a spectacular thirty seven. Eat twenty, twenty five, becomes eighty three. Again not enough to assimilate one hundred, so I need to help a second time, removing the big fish or adding another small mote to the list.
5. My mote is so small that it can't eat any other mote. I can only remove all the competitors.
6. I added a few more test for cases that jumped to my mind, here is the first one. If my mote is the biggest mote in town, there is no game for the other ones.
7. Similar to CaseSample3.
8. What if the user insert a ethereal mote with no weight? That should never occur, so I think it is right to assert on the mote value. That means that I am so unhappy of such an input that I terminate the program as soon as I spot it. You know as an assertion works, if it fails it terminates the execution outputting a string. The ASSERT_DEATH ensures termination and tests the returned string against the passed regular expression. Here I'm saying that I expect "Assertion (whatever) failed.", with anything instead of "(whatever)", accordingly to the compiler you are using you could get a different result.

There is a tiny nuisance here. On many platform googletest (at least up to version 1.6) issues a warning when calling ASSERT_DEATH, saying that it can't detect the current number of threads. You can easily get rid of this message, at least if you are working on Linux, following a suggestion you can find on stackoverflow.

And here is how I have implemented the function:

unsigned osmos(unsigned myMote, std::vector<unsigned>& motes)
{
  assert(myMote); // 1

  if(myMote == 1) // 2
    return motes.size();

  std::sort(motes.begin(), motes.end()); // 3

  if(myMote > motes.back()) // 4
    return 0;

  unsigned removing = motes.size(); // 5
  unsigned adding = 0; // 6
  for(unsigned i = 0; i < motes.size(); ++i) // 7
  {
    if(myMote <= motes[i]) // 8
    {
      removing = std::min<unsigned>(removing, adding + motes.size() - i); // 9
      while(myMote <= motes[i]) // 10
      {
        myMote += myMote - 1;
        ++adding;
      }
    }
    myMote += motes[i]; // 11
  }

  return std::min(removing, adding); // 12
}

1. It just can't happen that my mote is zero. If I detect it, something completely crazy is happening here, I don't know what to do anymore, and I do not expect the caller, its caller, any grand-caller knowing what to do. I do not have any alternative to terminate here the program execution. If you see it as a bit of an overstating, you would probably throw an exception instead.
2. My mote is so small, it can't ever eat anything. I have only one way of completing the job, removing all the motes from the passed collection. So I return the collection size.
3. Having the motes ordered by size, I could more efficiently determine which one my mote can eat. It costs a O(N log N) time complexity, but it is worthy.
4. Check the right-side mote in the collection (after sorting, the biggest one) against my mote. If my mote is bigger, it would surely eat all of them in a whiff, with no need of any help from my side.
5. Worst case scenario, I would need to remove all the motes to let my mote to win.
6. Best case scenario, I don't have to add anything.
7. Let's loop on all the motes.
8. My mote is not big enough to eat the current guy. We need to check if it is cheaper to add smaller motes or remove it.
9. The motes that I still have to process are the size of the collection minus the current position. In the worst case I should assume I have to remove all of them. Besides, I should remember that I could have already added a few motes to arrive in this position. I am interested in the less expensive solution, so I compare the previous worst case with the current one, and I choose the smallest one.
To make my choice, I use the STL min() template function. Usually I don't need to specify the parameter type, because the compiler is smart enough to deduct it automatically. But this is not the case, so I need to explicitly pass it the type I want to use.
10. Calculate how many motes I have to feed to my mote to make it big enough.
11. In any case my mote eats the current mote, growing up.
12. Let's compare if it is cheaper to remove or add motes, and return it. In this case the call to min() doesn't need any hint to understand that I want to use the unsigned int version.

Full C++ source code on github.