I’ve found this interview question at GeeksForGeeks and decided to actually code it in C++. The program currently prints the “value” of the horses (which is inaccessible by the coder so they can’t just look up who is number 1) and then proceeds to sort them and find the position of numbers 1,2 and 3 in a 5x5 matrix with the solution being a minimum of 7 races.

Here’s the Github repo: https://github.com/Shroomerian/HorseRacing

  • chief_x86@beehaw.orgEnglish
    4·
    1 year ago

    I saw that problem a few weeks ago on a youtube thumbnail, it’s quite a nice problem and I think it gets even more interesting if you start to consider 5^3 or even 5^N horses. Cool that you actually coded a solution for it! I like the idea of hiding the actual values to prevent the developer from cheating :)

    I haven’t really checked whether you program does exactly what I’d expect it to do since I had a hard time to understand what’s happening. I think a few comments here and there would help to understand what exactly is going on and maybe some better names would hep, too (example: number_matrix - what does it do? I see from the type that it is a 2d array of ints but what does it contain and how does it relate to horse_matrix). I still have some general recommendations for you how you could improve your code:

    1. You seem to use OS specific random numbers, there is a C++ api for that nowadays (std::random_device / std::mt19937)
    2. You call rand() % 26 and check against 0, in that case you reroll - you could instead directly calculate rand() % 25 + 1
    3. As alternative to that manual rand() approach, you could look into std::shuffle
    4. Take a look at sets (e.g. std::unordered_set), they have a containts() function that tells you whether a value is in the set or not. It’s not a big issue here but using vectors with std::count when all you want to do is check whether an element is in a set will not scale well
    5. Consider using an enum instead of the char option. I’d go with something like enum class Option { kRow, kColumn };. If you want to stay with a char, I’d recommend not using a preprocessor directive for this (#define) but instead go with a regular constant (e.g. constexpr char kRow = 'r')
    6. Consider using std::unique_ptr<MatrixPosition> instead of returning a raw pointer - that way you avoid memory leaks.
    7. ignore_count and ignore_vector are only used in one function, so they don’t have to be members of the class. InitializeMatrix probably does not need to be a class in the first place.
    8. Consider not using using namespace std. For small projects that’s not an issue for bigger ones you’ll find your namespace polluted.

    Something that you might also not be aware of is that std::endl automatically flushes buffers and makes sure that your line is printed immediately. If you don’t need this you can just use \n instead which is a little bit faster. But that’s more of a “fun fact” than a general recommendation.

    Hope that helps and doesn’t sound too harsh, I know how code reviews can feel sometimes…

    • ShroomerOPEnglish
      2·
      1 year ago

      Thank you. Just the fact that you took all the effort into commenting is enough for me, thank you.

      I didn’t really implement comments since I didn’t think it would expand that much (same goes for the namespace). As for some things which are unclear, number_matrix is a matrix I used to randomly generate the numbers that each horse would have to represent how fast they go, I didn’t know exactly how to create a random matrix where each number was unique using random, so I just added each previous number into a vector and checked if that number already exists there. The reason I did this (at the time) was because I REALLY didn’t want for the programmer to have access to the numbers, so I’d rather them being in a class that they can’t even access (protected constructor) and otherwise the numbers were hidden in the Horse private structure with the only way to interact with them being the two Race function (essentially sort functions)

      Also, I didn’t use sets, because I remember doing a problem in LeetCode and when I used them there the Memory part of the submission was so bad that it essentially said that it only beats 0.5%, when I replaced them with a vector for the same function the memory recuperated back to 56% (I know that really the difference is only a few KBs of memory, but it still traumatized me haha )

      I’ll try to adress these issues and then I’ll try to make another release on Github, although you might think that might be a waste of time on such a problem, I have nothing better to do since it’s summer vacation.

      I’m trying to learn programming, and it’s more of a hobby for now since I’m still not in University yet, although this year might be if they accept me (still waiting for admission results)

      • chief_x86@beehaw.orgEnglish
        2·
        1 year ago

        My personal preference is to leave comments where it’s not directly clear what the code does. Using “good” variable & function names can make the code usually somewhat self-documenting, but that’s not always enough.

        I didn’t know exactly how to create a random matrix where each number was unique using random, so I just added each previous number into a vector and checked if that number already exists there

        Yeah I understood why you used that approach, and I’m not a c++ expert myself, just wanted to point out some other options.

        I’d rather them being in a class that they can’t even access (protected constructor)

        It makes no difference visibility-wise if you have a variable that is local to a function vs a private member of a class that’s just used by said function.

        Also, I didn’t use sets, because I remember doing a problem in LeetCode and when I used them there the Memory part of the submission was so bad that it essentially said that it only beats 0.5%

        Huh, that sounds odd. Never done anything with LeetCode, but would be interested into seeing what was going on there. If you want to use sets, check whether you need ordering (most likely you don’t) and go with std::unordered_map.

        although you might think that might be a waste of time on such a problem

        Absolutely not. I see lots of value of optimizing and cleaning up code, there is so much to learn which will help you write better code in the future. I have a bunch of programming projects that I never fully finished and you could also call them a waste of time - who would play with my gameboy emulator without gui etc? No one besides me :) But it was more about the journey and learning things. So go for it and code things you find interesting, that’s a good way to stay motivated.

        I’m trying to learn programming, and it’s more of a hobby for now since I’m still not in University yet, although this year might be if they accept me (still waiting for admission results)

        Good luck with admissions. Putting effort into it in your spare time and as a hobby is great and shows dedication, exposing your code to “the internet” and asking others for feedback is also a great way to grow - way to go!

        • ShroomerOPEnglish
          1·
          1 year ago

          Thank you. Also about point number 1, I realized that the rand() function is actually part of <cstdlib> and not <random> so it turns out I included it for nothing.

    • ShroomerOPEnglish
      1·
      1 year ago

      After a few hours of work, I was able to improve the code by following your recommendations. I was genuinely surprised at how removing boilerplate code that I created at the beginning helped me see where the problems are and allowed me to see better solutions to problems.

      For example: instead of copying each value into a temporary int array, sorting that array and then changing the original, I was able to just use C++ STL sort() with a function parameter to automatically sort structs based on their values when it came to the rows.

      I touched on every point that you’ve made and made changes accordingly, some things like the char option I just removed and checked for the conditions in the function instead of waiting for the programmer to give the correct answer. The only thing left for me is to relax a bit since I was at it for a lot of time, and then properly comment the code.

  • Double_A@discuss.tchncs.deEnglish
    3·
    1 year ago

    I really hate those kind of questions. They mostly have nothing to do with coding, and are really just a mathematical puzzle. Also most people are not able to figure those out on their own, and then everyone just ends up memorizing things.