[Community Puzzle] Murder in the village!

Hi, thanks for the great puzzle @Pluk. However, please consider moving it to Medium difficulty, the problem was not Easy for me.

1 Like

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.

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)

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;

                    }

                }

            }

        }

The most informative and usable data is “has anyone seen him?”.

Only consider people no one saw, it prunes the search a lot.

Then you can check if your lieuAVerif.ocupant.size is not 1 or if your getAvecQui(0) is not “alone”.

1 Like

Thanks,i complete this challenge thanks to your help :).

While the test is rather interesting (even though I hate text-based challenges, but that is just me), I strongly feel this should not be on Easy!

1 Like

hey, quite interesting puzzle you made here. Great work.
however, i managed to pass all the 8 IDE tests, but when i submitted, the test “Validator 1” failed. Could you please give me a hint what this test checks ? Thanks.

I agree with previous posters on the fact that a test is required to eliminate solutions based on counting. Luckily, I could find the flaw in my counting argument quickly, but this may cause a lot of trouble to other people having this failed validator with no clue to debug it.

Hello,

I tried to resolve the problem but I don’t know if it’s the right way.
Please give me your feedback.

I follow the following algorithm :

How many people does you want to ask question (example : 2)
if the user write 2, he should precise the name, the location and with whom he was (example : Lucy Church Mary and Mary Church alone)
I put the values in a list where the first element is Lucy Church Mary and the second element is Mary Church alone

=> How can I compare the two element ? Here is my code :

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
import java.util.Scanner;

public class MurderVillage {


    public static void main(String[] args) {


    System.out.println("How many people are in the village ?");
    Scanner scanner = new Scanner(System.in);

    int scannerInt = scanner.nextInt();
    List<String> myList = new ArrayList<>();


    System.out.println("Where where you ?");

    for (int i =scannerInt; i>=0; i-- ) {

        String row = scanner.nextLine();
        myList.add(row);
    }

    Iterator itr= myList.iterator();

    while (itr.hasNext()) {
        System.out.println("while loop");

        System.out.println(itr.next());

        }

@Pluk Awesome puzzle!

I’m going to push back on some of the comments regarding difficulty. Granted, this puzzle took me a while to figure out, but only from a logistical standpoint. The coding itself was fairly straightforward.

My advice would be to go ahead and start coding the puzzle while concentrating on collecting the information that is presented. A lot of it is obvious, like the name of the villager and the location they claimed to have been at as well as who they claim to have been there with.

Perhaps not so obvious is that you should also collect all the people who have claimed to have been at each location, indexed by location. That was one of the final things I implemented, and then everything started clicking together.

My code has three overall loops. The first collects the data without attempting to make any sense of it since we haven’t collected all the information yet.

The second loops through each of the villagers and checks to see if the list of people they claim to have been with also claims to have been with them. If you find one that doesn’t, then that villager is your answer, and no need to continue to the third loop. If a villagers story is corroborated by another villager, then mark the villager with an “alibi”. If they were alone, they won’t have an alibi, but may not have been the guilty one.

The third and final loop loops through all the villagers who still do not have an alibi. If there is only one, or none, you are done. It was the villager without the alibi or it was you. Otherwise it looks at the location that villager claims to have been at and if there are other people who also claimed to have been there, it checks them to make sure they agree that the villager was there. This resolves the cases where the guilty party claims to have been somewhere alone that others were also at.

Hope this helps future puzzle-solvers!

2 Likes

This puzzle is awesome! Thanks a lot!