[Community Puzzle] Murder in the village!

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!

This explanaition was a lot of help. Although my algorithm was a bit different and probably not as elegeant it brought me into the right direction of checking for the locations. For some weird reason I managed to get the last test correct without looking at those and consequently failed at the solution.

Now I have a 100% just minutes before I get off work for the weekend. :slight_smile:

1 Like

Did anyone else couldn’t pass validator 1 and 4 despite passing every IDE tests?

After failing a first time like that, I came here and rewrited my code with an algorithm very close to TheSwine’s one (only difference is that I check if any alone people say they are in a location where someone else was in the same loop).

But I get the same result :s.

You may consider this earlier comment for a start; it includes a hint or two which may be relevant to you :wink:

2 Likes

Thanks! Indeed my algorithm was dependent on ordering of statements. I simply checked for people alone after checking for everyone that stated they were with someone and it worked :slight_smile:

If someone ends up with the same issue as me, I’m pretty sure validator 1 and 4 have a situation where a villager says he was alone before the statement of the killer where he says he was at the same location!

1 Like

Incomprehensible situation. If there is only one clue: “Tom: I was in church alone.” What’s the correct answer - “Tom did it!” or “It was me!” ?

The constraints state that the minimum number of people/clues is 2. There is no test case or validator with only one clue.

1 Like

I just solved it. I like the fact that there is a simple idea to find most of the innocents, and for those remaining, it’s rather easy to tell if they are guilty or not.
But after having this idea, you have to deal with the way inputs are given. It’s so tedious to deal with those sentences, removing the “and”, the “,”, the “.” . I have the solution! Why should you torture me with this!
Would it be possible to simplify the inputs, so that dealing with these would be easier, because it takes time and it’s not the real issue this problem deals with.
(Hope my english is not so bad, i don’t practise a lot).

Hi,
I’m passing all tests, but 3 and 8 are still failing on submission. As advised in previous notes, not stopping the check if I found 1, looping though all, but still fails.

My logic was as follows:

  • First eliminating alone innocents from usual suspects.
    * if alone one not in any location mentioned by other, then he/she is innocent.
    * If only 2 suspect remained (1 is alone), and their locations are same, alone one is innocent.
  • Then for non alone testimonies: If 2 persons testimony for “with whom” points each other and location is same, eliminating both of them from usual suspects.
  • In case of complex testimony “with whom” is several persons, then looking for person who is not mentioned in any “with whom” list

any suggestion to finish?

Try creating custom cases to test your code. Here are some ideas for your custom cases:

Validator 3: It is similar to test case 3 except that only 4 people/statements are involved. Also, one of the person’s name is a place name at the same time.

Validator 8: It is almost the same as test case 8 except that the people’s names, the places and the order of the statements are different.

1 Like

thanks @5DN1L .
I wasn’t aware Validators can be different than test cases, it is good to know.
I will try some more cases locally :slight_smile:

1 Like