Add practice exercise Zebra Puzzle

[rajatnai49]

issue number: #779

[rajatnai49]

Okay I will work on that👍

[vaeng]

Thanks for the update!

Do you think we could have the details of the story in the test file? So the result is not always the same and students cannot just answer "Norwegian"?

So that we have a custom test case, where we give another story? I will ask the other maintainers if they did that. What do you think @siebenschlaefer ?

It is possible a bigger rewrite and I think you should get more than the standard 12 reputation for that, if you want to continue.

[siebenschlaefer]

Hej @rajatnai49,

I'm a little bit torn. The example solution still contains a lot of "human reasoning", e.g. why the first house is yellow is deduced from facts 6, 15, and 2 and then hard-coded (houses[0].color = YELLOW;)
I would prefer an example solution that does that as little as possible, let your program find the answer.

For example, you could use five nested loops (for the nationality, the color, ...), try all permutations, and skip a particular permutation as soon as possible when it doesn't match the facts. Or you could try to implement a completely different approach, that's up to you.
If you need inspiration you could look at the solutions of this exercise in other tracks or at rosettacode. And if you need help, let me know, either here or on our Discord server.

And two small things:

• Why are drinks_water() and owns_zebra() member functions of a class? Unless that class has some state I'd suggest defining them as free functions instead.
• For constants use const or constexpr variables instead of macros. That's a broadly accepted best practice.

[rajatnai49]

Sorry @siebenschlaefer for disappointment😞, and I know that all permutation solution but I think it will be good if we just first remove that and after that try every possible cases for perticular conditions, and it is much efficient than trying all permutation But, I understood your point that you want code to do every work, so fine I will work And also I will take note of those practices this time around!!

[siebenschlaefer]

Sorry @siebenschlaefer for disappointment😞

No worries, please! As vaeng wrote earlier this is not an easy exercise. And maybe we maintainer should have communicated more clearly what kind of example solutions we're looking for.

And if you need any help, let us know.

[siebenschlaefer]

@rajatnai49 Are you still working on this? Is there anything we can do to help you?

[rajatnai49]

Hey, @siebenschlaefer sorry for delay but we are organizing the Hackathon in the university so I didn't have much time to work on the issue so I will give you update in next week for sure!!

[rajatnai49]

@siebenschlaefer I added the solution as you explained earlier, review that and if any other requirements are there then let me know !

[siebenschlaefer]

Much better, this is now an algorithmic solution.

---

But it takes a really long time to run because it tries all potential solutions and finds the correct solution after more than 171 million permutations. On my computer it runs in a a little bit more than one minute. Students wouldn't be able to submit this example solution because it would not complete the tests within the allowed time (I think the test runner has a limit of 20 or 30 seconds.)
We need to bring that time down because we want an example solution that could be successfully submitted.

There are five nested loops (for the cigarettes, drinks, pets, nationalities, and colors). Currently the innermost loop assigns values to the members of the houses and checks whether that's a valid solution.

Instead you could assign assign the values to the houses as soon as possible, i.e. the .cigarette in the outer loop, the .drink in the first inner loop, the .pet in the second inner loop, the .nationality in the third inner loop, and the .color in the innermost loop. That alone cuts the runtime in half (at least on my computer).

Instead of checking the complete solution in the innermost loop you could check each of the 14 clauses as soon as possible and continue if they don't hold. For example the outermost loop creates permutations of the cigarette brands, the first inner loop creates permutations of the drinks. You could check clauses 8 ("Milk is drunk in the middle house") and 12 ("The Lucky Strike smoker drinks orange juice.") right there, in the first inner loop. That would allow you to skip generating all the permutations of pets, nationalities, and colors when you know that the will never create a valid solution because houses[2].drink is not Milk or because the Lucky Strike smoker does not drink OJ. If you do that for all clauses (check each clause in the outermost possible loop) you can reduce the runtime drastically, on my computer it runs in under one second.

---

And some smaller nitpicks:

Four of the five std::map instances are not used at all. I'd suggest deleting them. That makes the code easier to read and to maintain.

As far as I can see the return statement in line 159 is the only one that is not indented by a multiple of four spaces.

---

And finally a more general question where @vaeng might also want to weigh in:

Currently the tests require two separate and free functions that answer the two questions. But is that really the best structure for this problem? It basically forces the students to write some helper function that solves the problem and gets called by the two "public" functions, and it will force the test runner to solve the puzzle twice (unless the students implement some caching) without a clear benefit.

How about a single function that returns both answers at the same time? That's how the Go track does it.

[vaeng]

How about a single function that returns both answers at the same time? That's how the Go track does it.

We could also go the class way and generate the puzzle solution on construction and have the answers in variables ... Might be ugly :D

[siebenschlaefer]

We could also go the class way and generate the puzzle solution on construction and have the answers in variables ... Might be ugly :D

Right, that's another option. (although personally I'm not a fan)

[rajatnai49]

@siebenschlaefer totally understood ☺️, working on that. and both single function or class construction approaches are great because there is a only one particular answer for the zebra puzzle, so solving puzzle two time, like in the python track will not be add any value, So let me know on which path we are going.

[vaeng]

So let me know on which path we are going.

a single function that returns both answers at the same time.

[rajatnai49]

@vaeng @siebenschlaefer can you please give me the status/review of this PR, anything required?

[vaeng]

@rajatnai49 The exercise is going to be featured in two weeks. Can you cover siebenschläfer's suggestions in the next days, so we can have it online soon?

[vaeng]

Clang is not happy with the formatting

[vaeng]

This is it. Thaks a lot for all the work in this exercise @siebenschlaefer and especially @rajatnai49!