Hello @Arglanir, and thank you for your latest puzzle (https://www.codingame.com/training/expert/dungeon-designer). I enjoyed doing it, but right now, I’m stuck: my code passes all test cases but not validator 5, and I have no way of knowing why. Any hint would be appreciated. Thank you!
I would love to help. The validator 5 uses the following input data:
19 11
1747 1811 100000
Would you try it in your IDE ?
Thank you for your answer. My problem is one of timeout. Although the grid is slightly smaller than in test case 5, it takes a longer time with my code (maybe the labyrinth is harder to solve? I haven’t inquired further yet). I’ll try to find further optimizations. You can edit your post to remove the input data if you like. If the time ratio is the same with your code, maybe switch up the test and validator so that passing one ensures you pass the other?
As long as I do not give the answer I think it should be good 
The returned labyrinth is slightly smaller though than test 5, but the seed number are a little bigger.
Maybe check the way you compute the Pseudo Random Number? what language do you use?
Python 3. Yeah, not the fastest, probably ^^
I think I am not generating the right maps.
For the forst test, w=3 and h=2, I get this:
M_MMMMM
M_M__TM
M_M_MMM
M__X__M
MMMMM.M
For cell 0,2 (top right) I think I should apply x+y×W+1 = 2+03+1 = 3;
and then R^(2^3 mod lcm(1722,1578)) mod 15791723 is 100000^8 mod 2720617 = 2588150,
which is even, so the wall should be built to the south.
But the error indicates the test solution has the wall on the east.
I have tried several variations in the exponent formula, and I can manage
so get thiws map right (it has only two walls), but I haven’t been able to do a large map right.
for (int x = 0; x < w - 1; x++) // compute wall with that formula
you don’t set x=2, that’s the default border.
Thank you very much. Turns out what was misleading me is that in these tests there is a long vertical corridor in both sides, east and west, and i mistook them.
Hello @Arglanir @JBM @Stilgart @CyberLemonade.
Sorry for reviving this thread but there does not seem to be any other discussion thread involving this puzzle and I am having a heck of a time trying to understand some of the requirements. For the purpose of simplicity I will only be referencing the first testcase “Small One”. FYI: I am using Perl, and in the case of the formula given in the instructions, am using bigint.
At this point I have gotten to where I have the dungeon border created around an empty grid, like this:
#.#####
#.....#
#.....#
#.....#
#####.#
To start generating the dungeon, I am thinking I start with the position just below the adventurer’s entrance, which I believe should be 1,1. I’ve tried two ways to calculate my prng, by using the formula given in the instructions, and then also by calculating each nth position of the BBS until I get to the one that I am targeting based on the (x+y*w+1) nth position. Each time I get the same result (2282028) which is even and obviously not correct since the test case indicates I should have gotten an odd result (i.e. put the wall to the east). So that leads me to believe that I am misinterpreting something in the instructions.
I’ll stop there for now and see if any of you can point out anything clearly wrong with my thinking. Based on the instructions, I think there is a possibility I may be confusing grid coordinates with map coordinates, but any other interpretation I’ve come up with just doesn’t make sense. Thanks in advance for any and all assistance!
Can you share your calculation and the results at each step?
Thanks for the quick reply @5DN1L.
Just using the BBS algorithm without making use of the Carmichael shortcut that is presented in the instructions, I start with PRNG[0]=100000 (the seed value). Then I apply the formula “prng[x] = prng[x-1] squared mod m (which is p*q)” until I have enough n positions to cover all the coordinates on the board, which in the first testcases instance is 15 (I think). I determined this by calculating the n position for the last cell in the map that is within the border, which again, I am thinking is 5,3 (just above the monster barracks). 5 + 3 * 3 + 1 = 15
Below are the resulting values for each n postition.
0=100000
1=1732525
2=2463227
3=2588150
4=2247056
5=2282028
6=1806553
7=632928
8=603019
9=2407992
10=1666134
11=1905687
12=133349
13=3089
14=1380070
15=788497
When looking at position 1,1 (1 + 1 * 3 + 1 = 5), that points to the value 2282028.
I also get the same result when I use the Carmichael function as presented in the instructions, so that leads me to believe I am using the formulas correctly. So to me it appears that I am just misinterpreting something in the instructions.
Thanks again!
My code calculates two random numbers only, up to 2=2463227.
It is a bit tricky to interpret, but the statement states:
You find a relatively simple algorithm : in each cell except the eastern and southern ones, the building slaves will toss a coin. If “heads” they will build a wall to the east; if “tails” they will build a wall to the south.
This creates a simple maze, with long corridors in the south and east since no wall is built from x=W-1 or y=H-1. The monsters barracks being on the south east corner, this makes for a perfect confrontation stage.
The coin refers to BBS. Hence no random number generation is required for eastern and southern cells.
Right but I’m not even trying to flip a coin in eastern or southern cells because I’m still working on figuring out why I am wrong about the one in the northwest corner.
I also don’t understand the no wall is built in W-1 or H-1 (other than it is supposed to pertain to the eastern and southern cells) since the dungeon map you created is now twice as large as the original grid plus 1. On some of the larger boards that (W-1, H-1) would be a cell somewhere in the middle of the grid, wouldn’t it?
In your first statement you say you only calculate two random numbers up to the 2nd n position. Not sure why only 2 as that wouldn’t seem very “random”. I’m guessing there is a clue there that I am just not picking up on. Although if you are only using those two values to evaluate the coin flip (there should be four coin flips, I think) then that would be consistent since those two values are odd and all coin flips need to be odd.
Just to be sure, I am calculation the nth position correctly, aren’t I? The formula given in the instructions looks a little wonky (x+y*W+1).
Edit: I just realized that I am a little overkill on figuring n positions since the entire southern row will not be calculated, but the question remains the same.
The wall building process is like this:
Initially:
. . .
. . .
After first BBS random number:
.|. .
. . .
After second BBS random number:
.|.|.
. . .
There are never walls within the southern-most corridor (H-1) and the eastern-most corridor (W-1).
The only remaining wall to build is the outer wall to surround the whole area, except for the top left and the bottom right, hence:
| -----
|.|.|.|
|. . .|
----- -
2 Likes
OK. I think I get it now. I think what I was missing was when they said a wall goes to the east or south, it is NOT just the cell immediately to the east, but also the cell just to the south of that one. Same with a wall to the south, the wall just to the east of it is a wall. So in essence, for every original grid location that we are evaluating, there is ALWAYS a wall just to the southeast on the map. Does that sound like I’ve got it now?
I don’t quite get what you are trying to say 
In the first test case, there are only 6 cells to consider:
- 2 of the cells require BBS to determine whether to build a wall to the east or to the south
- the remaining 4 cells just follow the standard rules applicable to southern corridor / eastern corridor, hence no inner east/south walls
The last step is to surround the whole area with walls except for the entrance and the exit.
1 Like
Correct, but there are four walls inside the borders on the test solution, like so:
#.#####
#.#.#T#
#.#.#.#
#....X#
#####.#
I was having trouble establishing where the two walls right in the middle were coming from. Pretty sure I get it now with help from you. I checked with the other test cases, and my reasoning works in every instance.
Thanks for your help!
2 Likes
I think I am misinterpreting the instructions. It is apparent that the intent is to modify the BBS algorithm (which normally has residual state) to be stateless, and calculate the coin toss for each (x, y) to be deterministic based on x and y regardless of which cell is calculated first. That makes sense. However, in example given, the way I read the calculation is:
(100000^((2^(x+3y+1) mod lcm(1722,1578))) mod (1579 1723)
Now, P and Q are primes, so they are both odd, so P*Q is always even and the mod PQ operation has no effect on evenness/oddness of the result and it can be dropped.
similarly, 2 to any positive power is even, the lcm of two even integers is always even, and 100000 to any positive power is always even.
From this, if R is 100000, the result is always even and all walls are built to the south. This is indeed what my implementation gives.
I know this is a simple misinterpretation, but I’m not sure how.
Update: If I use a standard BBS algorithm (stateful, where the each random number is dependent on the previously generated random number rather than on x, y), and I am careful to call it once for each cell, in row order (x in inner loop and y in outer loop), even for cells that are on the west or south border and do not use the random value, then the resulting maze is consistent with the given example. However, I can’t see how this relates to the stateless formula given that is based only on x, y.