This is a text-only version of the following page on https://raymii.org:
---
Title : Weight for Weight, a coding exercise that kept me busy
Author : Remy van Elst
Date : 12-11-2019
URL : https://raymii.org/s/blog/Weight_for_Weight_a_coding_exersize_that_kept_me_busy.html
Format : Markdown/HTML
---
I'm using [codewars][1] 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][2].
<p class="ad"> <b>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:</b><br><br> <a href="https://leafnode.nl">I'm developing an open source monitoring app called Leaf Node Monitoring, for windows, linux & android. Go check it out!</a><br><br> <a href="https://github.com/sponsors/RaymiiOrg/">Consider sponsoring me on Github. It means the world to me if you show your appreciation and you'll help pay the server costs.</a><br><br> <a href="https://www.digitalocean.com/?refcode=7435ae6b8212">You can also sponsor me by getting a Digital Ocean VPS. With this referral link you'll get $100 credit for 60 days. </a><br><br> </p>
### The kata
[Codewars][1] calls their exercises "kata" ([plural?][3]). [This one][2] 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][4] 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][5] 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][6] 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][7] 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][8]:
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)
### Other solutions
The best part of [codewars][1] is that you get to see other people's solutions
to the same kata. Seeing other code gives you a lot of insight. The solutions
are rated based on `best practices` and `clever` and allow comments.
* Some solutions used the `boost` library to split, join and trim the string.
* Some solutions created a custom sort function which calculated the weights. This
resulted in one single sort function
* One solution used a `std::vector<std::pair<int, std::string>>` and not a `multimap`
* Most solutions created a custom function to calculate the word score instead of a loop
* A few solutions accessed the string and vectors with c-style array code `like[i]` that.
[1]: https://www.codewars.com/r/KjbvJA
[2]: https://www.codewars.com/kata/weight-for-weight/train/cpp
[3]: https://en.wiktionary.org/wiki/kata
[4]: https://stackoverflow.com/questions/4615046/c-get-each-digit-in-int/4615187
[5]: https://en.wikipedia.org/wiki/ASCII#Printable_characters
[6]: https://en.cppreference.com/w/cpp/string/basic_string/basic_string
[7]: /s/snippets/Cpp_std_accumulate.html
[8]: /s/tutorials/Cpp_project_setup_with_cmake_and_unit_tests.html
---
License:
All the text on this website is free as in freedom unless stated otherwise.
This means you can use it in any way you want, you can copy it, change it
the way you like and republish it, as long as you release the (modified)
content under the same license to give others the same freedoms you've got
and place my name and a link to this site with the article as source.
This site uses Google Analytics for statistics and Google Adwords for
advertisements. You are tracked and Google knows everything about you.
Use an adblocker like ublock-origin if you don't want it.
All the code on this website is licensed under the GNU GPL v3 license
unless already licensed under a license which does not allows this form
of licensing or if another license is stated on that page / in that software:
This program is free software: you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation, either version 3 of the License, or
(at your option) any later version.
This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
GNU General Public License for more details.
You should have received a copy of the GNU General Public License
along with this program. If not, see <http://www.gnu.org/licenses/>.
Just to be clear, the information on this website is for meant for educational
purposes and you use it at your own risk. I do not take responsibility if you
screw something up. Use common sense, do not 'rm -rf /' as root for example.
If you have any questions then do not hesitate to contact me.
See https://raymii.org/s/static/About.html for details.