https://www.codingame.com/training/easy/murder-in-the-village
Send your feedback or ask for help here!
Created by @Pluk,validated by @Crypticsy,@Tiramon and @SeebOmega.
If you have any issues, feel free to ping them.
Who is a villager? What is the definition of it?
As I understand it, a villager is any person who is not the murder.
2 Likes
My code passes all the test cases but fails at the validator #4 and thus, getting %87. I wish test cases were more comprehensive. Text cases include few people; it would be much better if a village of size larger than 10 was also added as a test case. How can I debug my code now?
I think being a “killer” and “villager” is not mutually exclusive. A person can be both a killer and a villager; whereas, the question text assumes this is not the case. In my humble opinion, question text needs to be clarified.
1 Like
When you’re looking for the murderer, do you stop as soon as you find one?
If yes, you could try to continue your loop.
As there is only one possible solution, you must not find someone else. But, who knows…
1 Like
Hi @IIIThinkAboutIt,
You’re totally right about the confusion with regards to “killer” vs “villager”.
I actually chose these names due to the very popular trope used in games like Mafia, Werewolves, Salem, etc.
I’ll see if I can change the description to be more clear.
2 Likes
I have finally solved the puzzle. It is one of the most thought provoking puzzles I have seen.
I believe it has more room for improvement as far as the test cases are concerned. My feedback about more comprehensive test cases is still valid. More specifically, I would suggest a test case about “No non-killer can claim to be with the killer”. Sometimes the names of the test cases are also helpful. You can also update the test names if you wish.
Thank you for clarifying the “villager” term. Now it is crystal clear.
I would argue if this is an “Easy” puzzle or not.
In any case, it is one of the best I think. Thank you for all of your efforts.
3 Likes
Hi, thanks for the great puzzle @Pluk. However, please consider moving it to Medium difficulty, the problem was not Easy for me.
2 Likes
I very simple alibi counting method (which does not take into account any contradictions or locations) passes all ide tests, fails only the last validator. I recommend adding more test cases to rule out such over-simplified and inherently bad solution even before submit.
yes I had a hard time with one validator as well. It was probably the same as you, my inital approach was alibi counting.
Hi guys, thanks for the feedback.
Although I do understand the urge to create a “over-simplified and inherently bad solution” as you put it, the validators are there to catch such bad solutions, right?
I’m honestly not sure where the line between “easy”, “medium” and “hard” puzzles lies, but I’m guessing that there is a lot of elitism in the ranks of the judges, so I figured that the largest chance of actually passing was to assume that every judge would call this an “easy” challenge.
Usually the best practice is that for any error which a validator catches, the corresponding ide test should also fail. For this puzzle I knew from start that my original solution is incorrect just gave it a try. But imagine someone passes all IDE tests, submits and receives 85% instead of 100% and has no clue what went wrong because validator test input is not accessible. This easily leads to bad user experience. Modifying or adding more IDE test cases helps to avoid such situation a lot. I meant it merely an improvement suggestion, otherwise your puzzle is quite fine, the topic and problem is interesting.
4 Likes
Both the last test and validator were added to target that problem after I mentioned the counting solution on the contribution - the only difference between them is order of statements. I’m guessing when you have multiple options for the killer you output one of them and get lucky with the test?
The simple solution I mentioned just counted alibis, so yes may it was simply lucky.
I also have a proper solution that also checks contradictions and passes all tests & validators.
My code passes all the test cases but fails at the validator #3 and thus, getting %87. Can somebody tell me what validator #3 is? and how to solve it?
One of the locations has the same name as one of the people, and one of the people has a location’s name. Hopefully that’s your issue.
1 Like
Thanks for your reply, but it can’t be this issue because the name and the location in my code are declared
separately. I can’t mix them.
1 Like
Maybe your approach was not the good one but you were lucky on testcases.
Basically, the killer must verify these two conditions:
- No one saw him
- He didn’t say he’s alone in a place no one else mentionned (cause if he did, that would explain why no one saw him)
1 Like
Here a part of my code who shearch if the killer is in a place,
for(int i=0;i<lieuAVerif.ocupant.size();i++) {
if(lieuAVerif.ocupant.size() == 1) { // if a personne is alone in a place
if((lieuAVerif.ocupant.get(i).getAvecQui(0).equals("alone")) ==false ) { // if he say he is not alone
reponse = lieuAVerif.ocupant.get(i).getNom();
break;
}
}
else if(lieuAVerif.ocupant.size() == 2) { // if 2 personne is in a place
if((lieuAVerif.ocupant.get(0).getAvecQui(0).equals("alone"))) { //if the ocupant 1 said he is alone
reponse = lieuAVerif.ocupant.get(1).getNom(); // the killer is then the ocupant 2
break;
}
else if((lieuAVerif.ocupant.get(1).getAvecQui(0).equals("alone"))) { //if the ocupant 2 said he is alone
reponse = lieuAVerif.ocupant.get(0).getNom(); // the killer is then the ocupant 1
break;
}
}
else if(lieuAVerif.ocupant.get(i).voitCombienPers == lieuAVerif.ocupant.size()-2 ) { // if more than 2 people are in a place and someone see less people in a room than the real number of people in the room
for(int j=0;j<lieuAVerif.ocupant.size();j++) {
if(lieuAVerif.ocupant.get(j).voitCombienPers != lieuAVerif.ocupant.size()-2 ||lieuAVerif.ocupant.get(j).getAvecQui(0).equals("alone")) { // if a personne see an other number of people then he is the killer
reponse = lieuAVerif.ocupant.get(j).getNom();
break;
}
}
}
}