C++ Beginner Algorithm Assignment

Question

I've got an assignment, which sounds like this : "An archer has black and white arrows, and he can only shoot white ducks with white arrows and black ducks only with black arrows. The ducks come in groups, which grow in size like this : one, then two, then three, then five, eight, etc., so basically Fibonacci numbers. The ducks in those groups are ordered so that you won't find two ducks of the same colour near each other, and each group starts with a white duck(for example, for the group which has 5 ducks in it: white black white black white). The archer can only kill the ducks if he can kill the entire group."

Being given the number of white arrows(ka) and black arrows(kb) I must say how many groups has the archer killed and how many arrows of each type has he got left.

int ka, kb;
cin >> ka >> kb;

int total_rows{0};
for(int current_group{1}, previous_group{1}; ka+kb >= current_group; ++total_rows)
{
    //see which of the arrows he shoots
    for(int i=1; i <= current_group; ++i)
    {
        if(i%2 == 1)
            --ka;
        else
            --kb;
    }

    // swap the 2 fib numbers so we can get the next one
    swap(current_group, previous_group);

    current_group += previous_group;
}

cout << total_rows << ' ' << ka << ' ' << kb;

If I typed, for example, 9 and 10, I should get 4,2,6. I'm getting something which has nothing to do with that...

Are you using `{1}` as an alternative to `= 1`? If so, that's really irregular. You could also skip the XOR dance and use a temporary. — tadman, Dec 08 '17 at 19:04
Why? Isn't it just a regular uniform initialization? I use the xor because it's faster. — Semetg, Dec 08 '17 at 19:06
`int i{1};` is unusual just because it is kind of new. It will become regular if more people start to use it. So setting a trend? :-) — Bo Persson, Dec 08 '17 at 19:08
It's not 1970 where your 4MHz CPU is barely able to swap two numbers, the speed difference is irrelevant. Do the simplest thing and let the compiler take over. If you have a measurable performance problem *then* optimize. Unless this iterates over a billion items I doubt you'd be able to benchmark the difference between the temp solution and this one. The standard initializer is `= 1` not `{1}`, a notation often reserved for bitfields or structure initializers. — tadman, Dec 08 '17 at 19:09
Yeah I know it's a new syntax but I don't think that's the problem here :)) — Semetg, Dec 08 '17 at 19:10
The way to debug code is to get all the *strange* stuff out of the way so the problem becomes more obvious. Overly baroque code is hard to debug. — tadman, Dec 08 '17 at 19:11
@Semetg Did you consider [using the debugger](http://idownvotedbecau.se/nodebugging/) to find what the problem actually is? — user0042, Dec 08 '17 at 19:11
@BoPersson I really hope not. This flies in the face of decades of convention and offers nothing in the way of benefits. — tadman, Dec 08 '17 at 19:12
@tadman Get back under your rock :-P ... (I mean the one you seem to have been living under the last decade(s)). — user0042, Dec 08 '17 at 19:12
@tadman https://github.com/isocpp/CppCoreGuidelines/blob/master/CppCoreGuidelines.md#Res-list — Galik, Dec 08 '17 at 19:15
@user0042 Hey, I've written a lot of C++ code under this here rock by the glow of this amber glass terminal! — tadman, Dec 08 '17 at 19:15
@Semetg - A good change. It is known that the "smart" xor-swap is actually a lot slower than `std::swap`. :-) [Swapping two variable values without using third variable](https://stackoverflow.com/questions/1826159/swapping-two-variable-value-without-using-third-variable) — Bo Persson, Dec 08 '17 at 19:16
@Galik That's an interesting recommendation, thanks for the link, but it does seem to be veering off into the direction of some really odd syntax. — tadman, Dec 08 '17 at 19:18
Let's please forget about the small things and look for the major flaws of my code, if there are any :)) — Semetg, Dec 08 '17 at 19:18
@Semetg We're just chatting here because we're expecting you'll step through this code in a debugger to see where it runs off the rails. I'd solve this on paper first, then check your computed solution to that step by step. — tadman, Dec 08 '17 at 19:19
@tadman oh okay I was just hoping that someone might be able to come up with something better... — Semetg, Dec 08 '17 at 19:21
If your code works, that's great. If it doesn't work you'll need to try and identify the flaw. If you're stumped on where the flaw is, but you've narrowed it down to a particular malfunction, let us know. For algorithmic theory there's the [CS site](http://cs.stackexchange.com) and for code-review there's the [code review](http://codereview.stackexchange.com) site, each of which are geared towards more specific aspects of coding. — tadman, Dec 08 '17 at 19:22
Sorry guys, I didn't even know that debugging was so important, or what it really did, thanks for bearing with me :)) — Semetg, Dec 08 '17 at 19:34

score 0 · Accepted Answer · answered Dec 08 '17 at 19:58

Maybe a slightly different approach on calculating how many arrows will be used, that the one you are using. As we know the ducks are alternating, this means that for the odd group you will need extra white arrow, otherwise the number used will be N/2 for each color

#include <iostream>

int next_group()
{
    static int prev = 0;
    static int next = 1;

    int res = prev + next;
    prev = next;
    next = res;

    return next;
}

int main()
{
    int white, black;
    std::cin >> white >> black;

    int groups = 0;
    while (true)
    {
        int n = next_group();
        int arrows = n % 2 == 0 ? n / 2 : (n - 1) / 2;

        if (n % 2 == 0)
        {
            if (arrows > white || arrows > black)
                break;
        }
        else
        {
            if (arrows + 1 > white || arrows > black)
                break;

            white--;
        }

        white -= arrows;
        black -= arrows;
        groups++;

    }

    std::cout 
        << "Complete groups eliminated: " << groups 
        << "\nWhite arrows left: " << white 
        << "\nBlack arrows left: " << black 
        << std::endl;



    system("pause");
    return 0;
}

Thanks a lot, apparently the algorithm was much simpler than I thought :)) — Semetg, Dec 08 '17 at 20:03
Just a quick question, you used static in the function to keep the previous values of the size of the groups? — Semetg, Dec 08 '17 at 20:07
@Semetg You don't have to use static, you can make both vars global and declare them outside of the function, or move the body of the function inside the loop if you want to. I just made the next_group function self contained so with every call to it it produces next number in sequence. — Killzone Kid, Dec 08 '17 at 20:10

C++ Beginner Algorithm Assignment

1 Answers1