Story

Hello? This is Mr. White speaking...

...

You don't know who I am?

...

Not at all? Protector of the world? White light? Monster killer Mr. White? You don't know who I am?

...

Godammit. Well I still need your help, and fast. I'm on a mission to... whatever, you don't need the details. Point is, I'm about to enter an elevator with some real bad people in it, "monsters", we might call them. There are also going to be some innocents in the elevator. I know it's weird, but the innocents and the "monsters" play this game here. I need you to help me solve the puzzle of who is a monster, and who is innocent. These guys are purposefully ambiguous though, so you might not be able to deduce everybody's identity; just do your best and identify as many as you can.

Problem

The elevator is a rectangular grid of width w and length l, so there are w * l people in it. Each person knows all the identities of the people adjacent to them, not diagonal. Each person on the grid will be represented by a non-negative integer number k, which means that that person said:

there are at least k "monsters" adjacent to me.

To further complicate things, monsters always lie and innocents always tell the truth. Let's look at an example:

• the people in the elevator are represented by the list: [1, 1, 4, 1, 3, 1, 1, 1, 1]
• w is 3
• l is 3

Therefore, we know that the elevator looks like this:

• 1 1 4
• 1 3 1
• 1 1 1

Now, try solving this puzzle to find out people's identities (monster or human, "M" or "H")!

To show the answer, we will create a parallel list identities = ["M", "H", "M", "H", "M", "H", "M", "H", "M"]

Formatting this, we see that the the identities of the elevator look like this:

• M H M
• H M H
• M H M

If you still don't understand why, look in the Hints section below.

Details

You must write a function, identify_monsters, which takes as parameters:

• a list people of size w * l, which contains non-negative integers representing what the person in that spot says (described above in Problem). Remember that monsters always lie and innocents always tell the truth!
• w
• l

and returns a parallel list identities of size w * l consisting of three values:

• "H" if that person is innocent
• "M" if that person is a "monster"
• "?" if it is impossible to know if the corresponding person is innocent or a "monster"

Since the tests are random, you once might get something similar to the following values passed into your function:

• people = [0, 0, 0, 1, 0, 1, 0, 0, 0]
• w = 3
• l = 3

Try solving this puzzle on a piece of paper and see what happens and then come back!

Now that you've solved it, you can see that it's a paradox. the people who are represented by 1 are both innocent and "monster". In this case, your function should return the following statement (exactly):

• "Situation is paradoxical"

Hints

The people list contains values from 0 to infinity, in theory. Think about what it means for a value to be 0. What does it tell you about the identity of the person saying (and the identities of the people adjacent to them):

there are at least 0 "monsters" adjacent to me

Think about what it means for a value to be higher than 4. If someone says:

there are at least 5 "monsters" adjacent to me

what can you deduce about their identity?

Consider the number of adjacencies for different spots in the elevator:

• on a corner, there are only 2 adjacent spots
• on an edge...
• in the middle...

With that, goodluck, and look at the example test cases for more help!

NOTE: you don't need any libraries for this problem.