[Community Puzzle] Haunted Manor

In my opinion, this is a very entertaining and original puzzle (https://www.codingame.com/training/expert/haunted-manor). It’s a shame so few people have solved it.
Any ideas why? Is it too hard, too scary looking or is it unpopular for some other reason?

1 Like

Because it’s hard.

As for me, the reason is: the validator 7x7 does not pass for an unknown reason ^^ (all other sample & validator tests are ok)

The 7x7 validator is harder because it contains a new concept: a room that can’t be seen by any of the outside views. You need to populate this room with whatever is leftover. I was one of the people approving this puzzle, and I noticed that this validator had an extra added concept. In hindsight, I should have insisted that all new concepts are introduced in tests, not validators. Sorry for this goof.

• danBhentschel
1 Like

I solve this with brute force backtracking, so even with an hidden room, it should do it ^^ I wonder if it’s a timeout issue ; the 7x7 of the UI is solved in 59 ms.

My solution takes 200ms to bruteforce the 7x7 manor, and passes all validators.

Well, then I dunno ; I reduced to 53 ms using switch instead of series of if.

If you’re interested, I sent you my code, it’s not very long (less than 100 lines), and quite simple, but after a few reviews, I cannot see what’s wrong.

I hate when some validators don’t pass, it’s impossible to debug ; never happened to me in official puzzles, and that’s the fourth time for community puzzles. Frustrating (and means the IDE samples are poorly designed).

For 7x7 case, there are 31(=16+8+7) creatures to be placed in the grid. This results about 2E12 (~=31!/16!/8!/7!) permutations to check. Should I use a deterministic algorithm?

Maybe backtracking?

Pure brute-force is not feasible, but you can always reduce the problem space by use of heuristics or otherwise.

I’d love to see the 7x7 validator too… My code works fine on all IDE tests and also on a custom 3x3 test with a hidden room, it would be nice to know if there is another specific feature of this validator or if the only problem is a timeout.

If it can help, my problem was finally a timeout ; now I solve the IDE 7x7 in 35 µs, and it’s OK for the validator test

There seams to be a Problem in the Java default code of this puzzle

`Exception in thread "main" java.util.InputMismatchException at java.util.Scanner.throwFor on line 864 at java.util.Scanner.next on line 1485 at java.util.Scanner.nextInt on line 2117 at java.util.Scanner.nextInt on line 2076 at Solution.main on line 27`

The `in.nextLine();` in line 28 seams to be to much …

The 7x7 validator has a room that is not visible from any of the outside views. That may be what is biting you?

• danBhentschel

No it’s not, I tested it with a 3x3 custom test.

Though maybe if this specific room is near the top-left corner (or worse, if there are several such rooms), it could make my code slower than needed. I’ll look into it and try to add some heuristics.

Hello, thanks for pointing this out, it will be corrected shortly.

Also, thanks to everybody who is taking an interest in this puzzle of mine
I had no idea I’d introduced a new concept in my 7x7 validator maybe I should add a testcase.
I can help you solve it if you PM me no problem.

Julien

Ok, I don’t know if you changed the validator (there’s no history for community puzzles), but now it passes.

For those interested, what I changed is that I made my code precompute the list of empty rooms instead of looping over the grid and just skipping mirror rooms. It must have given a minor-but-sufficient speed-up.

Thanks for the help guys!

FYI, for anyone who finds themselves in this discussion, I have added a new test case to this puzzle to hopefully help people through Validator #4. See Community puzzle challenge #1 - Haunted Manor.

• danBhentschel