Raymii.org

Quis custodiet ipsos custodes?
Home | About | All pages | Cluster Status | RSS Feed

Weight for Weight, a coding exercise that kept me busy

Published: 12-11-2019 | Author: Remy van Elst | Text only version of this article

❗ This post is over four years old. It may no longer be up to date. Opinions may have changed.

The kata
My first thoughts
Part 1: input & word scoring
Part 2, sorting the words based on score
Part 3, sorting words with the same score alphabetically
The final submission
Other solutions

I'm using codewars to practice my development skills. The exercise I was working on the past couple of days was a level higher than the 'rank' codewars gives me, so a more difficult exercise. Using the sparse free time I have, this kata took a bit longer to complete, and had me thinking about the problem when I was not doing the exercise. If a problem fascinates me that way, I can't stop thinking about it until I've solved it. In this article I'll walk you through my work on this kata.

Recently I removed all Google Ads from this site due to their invasive tracking, as well as Google Analytics. Please, if you found this content useful, consider a small donation using any of the options below:

I'm developing an open source monitoring app called Leaf Node Monitoring, for windows, linux & android. Go check it out!

Consider sponsoring me on Github. It means the world to me if you show your appreciation and you'll help pay the server costs.

You can also sponsor me by getting a Digital Ocean VPS. With this referral link you'll get $200 credit for 60 days. Spend $25 after your credit expires and I'll get $25!

The kata

Codewars calls their exercises "kata" (plural?). This one is called "Weight for Weight". The exercise is:

My friend John and I are members of the "Fat to Fit Club (FFC)". John is worried because each month a list with the weights of members is published and each month he is the last on the list which means he is the heaviest.

I am the one who establishes the list so I told him: "Don't worry any more, I will modify the order of the list". It was decided to attribute a "weight" to numbers. The weight of a number will be from now on the sum of its digits.

For example 99 will have "weight" 18, 100 will have "weight" 1 so in the list 100 will come before 99. Given a string with the weights of FFC members in normal order can you give this string ordered by "weights" of these numbers? Example:

56 65 74 100 99 68 86 180 90 ordered by numbers weights becomes: 100 180 90 56 65 74 68 86 99

When two numbers have the same "weight", let us class them as if they were strings (alphabetical ordering) and not numbers: 100 is before 180 because its "weight" (1) is less than the one of 180 (9) and 180 is before 90 since, having the same "weight" (9), it comes before as a string.

All numbers in the list are positive numbers and the list can be empty.

(end description)

My first thoughts

Most of the time, I'm rushing in to these kata because my 'level' is set to Fundamentals. Get to know the standard library, reasonable simple problems, string sorting, ordering, containers, lambda's, things you can dive in head first.

For some reason, the level was set to Rank Up for this kata. Not sure if I did that by accident or codewars just thought, you did a few simple kata, now here's a more difficult one.

The first part of the kata is simple. Split the input, score each number by the sum of the digits.

The second part, ordering the numbers by their weights is not that difficult as well. Put them in a std::multimap and they're ordered.

The last part, if the numbers have the same weight, sort them as strings, is what has kept me busy for a few more hours.

Part 1: input & word scoring

A few kata I've worked on gave a std::string as input, which needed to be split into each seperate "word" so to say to do something with that word. In this case it's a sentence of int's.

To split a string and put it into a std::vector I often use the following code:

std::stringstream ss{inputString};
std::string buffer;
std::vector<std::string> numbers;

while (std::getline(ss, buffer, ' '))
{
    numbers.push_back(buffer);
}

The stringstream is initialized with the given input string, then looped over. The result is put into buffer, which in turn is put into the std::vector.

Next up is the scoring of the words. Words, which are given as strings, but are numbers in some sense. Iterating over each digit of an int is hard and includes division, but since we have the "numbers" as string, we can iterate over them and get them as char.

My first solution was to assume ASCII and just substract 48 to get the numeric value.

for (auto const& number : numbers)
{
    int numberScore = 0;
    for (const auto ch : number)
    {
        numberScore += (ch - 48);
    }
}

However messy, this does work but has a lot of assumptions and validating input is hard in this case. What if something other than a number is given?

My second attempt involved a struggle with casting the char back and forth to get std::stoi to work. In the loop the single character is a const char reference and std::stoi only accepts std::strings. The default constructor of std::string does not accept a char to initialize with, my first, again dirty, attemtp was this:

for (auto const& number : numbers)
{
    int numberScore = 0;
    for (const auto ch : numbers)
    {
          std::string strCh {"x"};
          strCh[0] = ch;
          numberScore += std::stoi(strCh);
    }
}

Which lacks bounds checking. I read up on the std::string reference for constructor options and number 4 works:

for (auto const& number : numbers)
{
    int numberScore = 0;
    for (const auto ch : number)
    {
          std::string strCh {ch, 1};
          numberScore += std::stoi(strCh);
    }
}

After a day I had some spare time to work on this kata again, during the day I thougt of my recent article on std::accumulate, which would eliminate this loop. The end result on calculating the word weight score is now this:

for (auto const& number : numbers)
{
    int numberScore = std::accumulate(number.begin(), number.end(), 0,
    [&](int a, const char b) 
        {
          std::string strB {b, 1};
          return a + std::stoi(strB);
        }
    );
}

Part 2, sorting the words based on score

At first, I attempted to put all the words in a std::map with the score as key, to have it auto sort on score:

std::map<int, std::string> score;
# [calculating word score here]
score.insert(std::make_pair(numberScore, number));

I soon found out that the std::map container only has unique keys. Two words with the same score would thus result in only one word in the map. However, we also have std::multimap, which allows duplicate keys:

std::multimap<int, std::string> score;
# [calculating word score here]
score.insert(std::make_pair(numberScore, number));

This code:

  WeightSort::orderWeight("180 9 9 20 11 11");

Results in the following filled std::vector:

for (const auto& i : score)
    std::cout << "score: " << i.first << "; word: " << i.second << "\n";

# output:
score: 2; word: 20
score: 2; word: 11
score: 2; word: 11
score: 9; word: 180
score: 9; word: 9
score: 9; word: 9

This part, the sorting of scores, seems simple, but it doesn't yet account for the last part of the assignment, which is, if the two words have the same score, sort them alphabetically as a string.

Part 3, sorting words with the same score alphabetically

This part, I struggled with for some time. I can get the sorting on word-score done, but sorting a std::multimap by key first, then value seems to be more difficult.

I looked into several ways to sort a std::multimap by value. Some suggestions were to use a std::multiset<std::pair<int, std::string>> or to flip the multimap (from <int, std::string> to <std::string>) and then construct a new map in the correct sort order.

Using that multiset with a pair was horrible.

The latter, with the extra flipped multimap and a std::set, the set to hold the unique number of word scores, since a set is also ordered:

std::set<int> numberScores;
std::multimap<std::string, int> strScore; 
[calculate the word score, after std::accumulate]
score.insert(std::make_pair(numberScore, number));
strScore.insert(std::make_pair(number, numberScore));

With a nested loop using the two new containers allowed me to construct the correctly ordered output string:

std::string buffer;
for (const auto &score : numberScores)
{
    for (const auto &number : strScore)
    {
        if (number.second == score)
            buffer.append(number.first + " ");
    }
}
buffer.pop_back();

This did result in all tests succeeding, but felt a bit messy. Such a double loop is harder to debug. But, I did got an idea on sorting. Since the multimap is sorted alphabetically (since the string is the key) and the set is also sorted (by score), I thought, what would happen if I just sort the std::string vector with the seperate words in them after splitting?

The end result was to add this sort after the insertion of the input string (split on space) into the vector:

std::sort(numbers.begin(), numbers.end());

It works because the input vector of strings is sorted alphabetically. This means that if I supply 9 180 as input, the vector will have this order: 180 9. The insertion into the multimap<int, std::string> is sorted by score (key) on insertion order (which we did to the vector, alphabetically). This results in:

180: 9 //inserted first due to the vector being sorted.
9:   9

The sort makes the double loop and extra set redundant. Much easier to debug and probably uses less resources.

The final submission

I also added a check to see if valid input was supplied. One of the tests gave the string " " as input, which resulted in an empty vector. No need to continue on if that happens. The full code of my solution:

std::string WeightSort::orderWeight(const std::string &strng)
{
    std::string buffer;
    std::vector<std::string> numbers;
    std::stringstream ss{strng};
    std::multimap<int, std::string> intSort;
    while (std::getline(ss, buffer, ' '))
    {
        numbers.push_back(buffer);
    }
    if(numbers.empty())
    {
        return "";
    }
    std::sort(numbers.begin(), numbers.end());
    for (auto const& number : numbers)
    {
        auto numberScore = std::accumulate(
                number.begin(), number.end(), 0,
          [&](int a, const char b)
                    {
                        std::string strB {b, 1};
                        return a + std::stoi(strB);
                    }
        );
        intSort.insert(std::make_pair(numberScore, number));
    }
    buffer.clear();
    for (auto &i : intSort)
    {
        buffer.append(i.second + " ");
    }
    buffer.pop_back();
    return buffer;
}

The last buffer.pop_back(); is to remove the last space.

My unit tests, using googletest:

TEST(kata_orderWeight, test1)
{
    EXPECT_EQ(WeightSort::orderWeight("180 9"), "180 9");
    EXPECT_EQ(WeightSort::orderWeight("103 123 4444 99 2000"), "2000 103 123 4444 99");
    EXPECT_EQ(WeightSort::orderWeight("2000 10003 1234000 44444444 9999 11 11 22 123"), "11 11 2000 10003 22 123 1234000 44444444 9999");
    EXPECT_EQ(WeightSort::orderWeight("3 16 9 38 95 1131268 49455 347464 59544965313 496636983114762 85246814996697"), "3 16 9 38 95 1131268 49455 347464 59544965313 496636983114762 85246814996697");
    EXPECT_EQ(WeightSort::orderWeight("387087 176 351832 100 430372 8 58052 54 175432 120 269974 147 309754 91 404858 67 271476 164 295747 111 40"), "100 111 120 40 8 54 91 164 147 67 176 430372 58052 175432 351832 271476 309754 404858 387087 295747 269974");
    EXPECT_EQ(WeightSort::orderWeight(""), "");
    EXPECT_EQ(WeightSort::orderWeight("136854 88407 348997 18118 82854 195333 145209 208812 147019 39631 427687 26012 371712 236513 378280 76962 471892 117155 255066 474241"), "26012 18118 117155 236513 145209 208812 371712 147019 39631 474241 195333 255066 136854 82854 88407 378280 76962 471892 427687 348997");
}

All pass:

[----------] 1 test from kata_orderWeight
[ RUN      ] kata_orderWeight.test1
[       OK ] kata_orderWeight.test1 (0 ms)
[----------] 1 test from kata_orderWeight (0 ms total)