Dungeon Designer

Statement

Goal

Topics: Maze creation algorithm, Pseudo-random number generator, Longest path search, Shortest path search, Path intersection

The adventurers have raided the dungeon. They've destroyed almost everything with multiple fireballs: doors, traps and monsters. And they've stolen the treasure! Their levels were probably too high.
Luckily, at the last moment the Dungeon Master invoked gigantic cavern trolls that slew those pesky adventurers in order to secure the stolen gold. But in the battle, the rest of the dungeon has collapsed.

The Dungeon Master asks you, his trusted servant, to redesign the dungeon. He wants to better hide the treasure, so there is more time to react the next time the dungeon is raided.

The dungeon has a rectangular shape, W cells wide by H cells high, with the adventurers' entrance in the north west corner, so it's a good fit to create a labyrinth in.

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.

After designing this labyrinth, you need to find the location furthest away from the adventurers' entrance : that's where the treasure T will be hidden. Then you need to mark with an X the spot where the garrisoned monsters can easily intercept any adventurer : the point of the entrance-treasure path closest to the barracks. If the closest point is already the treasure's location, place only a T.

Your Master will be proud of you.

Note 1: You are asked to draw the maze formed from a W‍×‍H cell grid. Each cell of the grid may have a wall # to the north, east, west or south, which leads to a (2×H+1)‍×‍(2×W+1) map:

Grid 2×2  Map 5×5
           #.###
   .T      #.#T#
   .X      #.#.#
           #..X#
           ###.#

Note 2: For the reproducibility of the map across languages, you are given two primes P and Q, and a seed R, and you will generate pseudo-random numbers using the Blum Blum Shub algorithm (its name goes well with the theme… more information here: https://en.wikipedia.org/wiki/Blum_Blum_Shub )
Tossing a coin in (x,y) (where (0,0) is the top left corner): compute (R^(2^(x+y×W+1) mod lcm(P-1,Q-1)) mod P×Q).
If odd (“heads”) build a wall to the east; if even (“tails”) build a wall to the south.

Note 3: Take care that the expression given above for Blum Blum Shub, taken literally, involves numbers greater than can fit in 64 bits. You are invited to optimize it. :-)

Input

Line 1: Size of the labyrinth W and H as integers
Line 2: Random number generator arguments P, Q and R

Output

2×H+1 lines: The labyrinth map, with . for empty passage, # for a wall, T for the treasure, and X for the monster's intersection with the adventurers' way back.
There is wall all around the maze, except for an empty passage . on the north of cell 0,0, and to the south of cell W-1, H-1.

Constraints

0 < H, W ≤ 40
1000 < P, Q ≤ 3000
0 < R ≤ 100000
There is only one position where the treasure is furthest away from the entrance.
The treasure is forbidden from being in the entrance or in the passage to the monsters' barracks.

Example

Input

3 2
1723 1579 100000

Output

#.#####
#.#.#T#
#.#.#.#
#....X#
#####.#

Tags

Difficulty

Test cases

Small one Test

Input

3 2 1723 1579 100000

Output

#.##### #.#.#T# #.#.#.# #....X# #####.#

Validator 1 Validator

Input

3 2 1723 1667 100000

Output

#.##### #.#T..# #.###.# #....X# #####.#

Verrry smal one Test

Input

1 1 1619 1699 100000

Output

#.# #T# #.#

Validator 2 Validator

Input

1 1 1747 1783 1000000

Output

#.# #T# #.#

Bigger one Test

Input

5 5 1619 1607 100000

Output

#.######### #.#.#T#...# #.#.#.###.# #.#.#.....# #.#.#####.# #.#.#.#.#.# #.#.#.#.#.# #.#.#.#...# #.#.#.###.# #........X# #########.#

Validator 3 Validator

Input

5 5 1619 1663 100000

Output

#.######### #...#...#.# ###.###.#.# #.....#.#.# #####.#.#.# #.....#.#.# #####.#.#.# #T#.#.....# #.#.#####.# #........X# #########.#

Rectangular - X not in front of barracks Test

Input

6 10 1619 1663 100000

Output

#.########### #...#T..#...# ###.###.###.# #...#.#.....# ###.#.#####.# #.#.#.#.#.#.# #.#.#.#.#.#.# #...#...#...# ###.###.###.# #.......#.#.# #######.#.#.# #.....#.#...# #####.#.###.# #...#.#.#.#.# ###.#.#.#.#.# #..........X# ###########.# #.#...#.....# #.###.#####.# #...........# ###########.#

Validator 4 Validator

Input

10 6 1867 1831 100000

Output

#.################### #.#...#T....#.....#.# #.###.#####.#####.#.# #.........#...#...#.# #########.###.###.#.# #...#.......#...#.#.# ###.#######.###.#.#.# #.#...#.#...#.#...#.# #.###.#.###.#.###.#.# #.#...#.#...#.....#.# #.###.#.###.#####.#.# #................X..# ###################.#

Big Test

Input

18 12 1619 1699 100000

Output

#.################################### #.#.#...#.#...#.#.#.#T#.#.#.#.#.#...# #.#.###.#.###.#.#.#.#.#.#.#.#.#.###.# #.........#.......#.#.#.#.#.#.#.#.#.# #########.#######.#.#.#.#.#.#.#.#.#.# #.#.........#.#.....#.......#.#...#.# #.#########.#.#####.#######.#.###.#.# #.#.#.#.#.#.#.........#.......#.#.#.# #.#.#.#.#.#.#########.#######.#.#.#.# #.....#.....#...#.....#...#.#.#.....# #####.#####.###.#####.###.#.#.#####.# #.#.......#...#.......#.#.........#.# #.#######.###.#######.#.#########.#.# #.#.#...#.......#.#.#.#...#...#.#...# #.#.###.#######.#.#.#.###.###.#.###.# #.....#.........#.....#.#.....#...#.# #####.#########.#####.#.#####.###.#.# #...#.#.#...#.#.....#.#.......#.....# ###.#.#.###.#.#####.#.#######.#####.# #.#...#.#.#.....#.#.#...#.#...#...#.# #.###.#.#.#####.#.#.###.#.###.###.#.# #.#...#.#...#.#.....#.......#.#...#.# #.###.#.###.#.#####.#######.#.###.#.# #..................................X# ###################################.#

Validator 5 Validator

Input

19 11 1747 1811 100000

Output

#.##################################### #.....#.#T..#.#.#.......#.........#.#.# #####.#.###.#.#.#######.#########.#.#.# #.#.#...#.#.#.....#...#.........#.....# #.#.###.#.#.#####.###.#########.#####.# #.#.#...#.#.#.......#.#.#.....#.#.#...# #.#.###.#.#.#######.#.#.#####.#.#.###.# #...#.#.#.....#.#.#.#.#...#.#.#...#.#.# ###.#.#.#####.#.#.#.#.###.#.#.###.#.#.# #...#.#...#...........#.#.#.....#.#...# ###.#.###.###########.#.#.#####.#.###.# #...#.#.....#.#...#.#.............#.#.# ###.#.#####.#.###.#.#############.#.#.# #.....#.#...#...#.#.......#.#.#.......# #####.#.###.###.#.#######.#.#.#######.# #.#.........#.....#.#.#.#.........#...# #.#########.#####.#.#.#.#########.###.# #.#...#.#.#...#.#.....#.......#.#.#...# #.###.#.#.###.#.#####.#######.#.#.###.# #.#.#.#.....#...#.#.....#.#.....#...#.# #.#.#.#####.###.#.#####.#.#####.###.#.# #....................................X# #####################################.#

Corridor | Test

Input

1 7 1747 1811 100000

Output

#.# #.# #.# #.# #.# #.# #.# #.# #.# #.# #.# #.# #.# #T# #.#

Validator 6 Validator

Input

1 8 1747 1811 100000

Output

#.# #.# #.# #.# #.# #.# #.# #.# #.# #.# #.# #.# #.# #.# #.# #T# #.#

Corridor - Test

Input

7 1 1831 1667 100000

Output

#.############# #............T# #############.#

Validator 7 Validator

Input

8 1 1747 1811 100000

Output

#.############### #..............T# ###############.#

Solution language

Solution

Stub generator input

Rate this contribution

Make the contribution public (lvl 20+)

Comments

15 Comments

JBM Unnamed CodinGamer

over 6 years ago

Ok, I'm back. I've tried to solve it again, but it appears it's not quite ready for that yet :/ The easy fixes: - "face" -> "heads" (plural) - some note that BBS requires ints larger than 2^64 would be appreciated (it's not obvious from the first case, and makes for hellish debug once you think it's ok) - it seems like the validators refuse to have the treasure on the entrance and exit, but it's not really obvious to me from the statement. - the [[variable]] formatting makes for completely unreadable formulas, be it in map dimensions or BBS. (well at least they're copy-pastable, but still). I'd suggest not using it there. And now the hellish part that made it so hard to get right: - W and L are neither usual (in CG puzzles) nor correctly used here. In math, W/L could make sense describing a generic rectangle, with W <= L. This isn't the case here, we've got cases where W > L. - made worse by the fact the first examples are square, and the first rectangle happens to also be a big one, so it can more easily time out than serve as a debugging help at that point. Suggestions: - back to H (there's actually one left in te statement) - make the first case a rectangle - find some terminology to more naturally disambiguate the parts of the statements where coordinates refer to the W*H maze, and where they refer to the (2W+1)(2H+1) graphical representation of it. Still a great problem idea. I'm almost ready to approve.

JBM Unnamed CodinGamer

over 6 years ago

And I'm now ready to validate when the statement improves.

Arglanir Unnamed CodinGamer

over 6 years ago

I updated the puzzle in order to get rid of the distance. What the master wants is not the distance that the adventurers will have, but where he can stop them. I added a "Topics" section in order to show what is addressed in this puzzle (so you see directly at first that you have to write a PRNG)

JBM Unnamed CodinGamer

over 6 years ago

Sorry, looks like I'm the first to comment, so you get JBM-style notes as first feedback: * "slained"? I'm not (really) an english native, but I think you've really got to choose one between "slayed" and "slain". * "in order to" twice in the same sentence is a bit much * "depth H" ?! * the alg description paragraph is a bit hard to read. I'd suggest expressing the maze-edge case with words instead of math. * it's not obvious to me why the algorithm results in long corridors in south and east. Especially with the example * (at second reading) may be due to the highly unusual match between the w/h input and the (2w+1)(2h+1) output * "distance SD" errr... why? * PRNG: it's vital to the program validity, it's weird (to me) to have to find it in a "Notes" section * and it's not that readable. I'll try and help. * without clicking on the links, I have interest in the PRNG one, but don't spontaneously understand why the maze-generation one would be relevant. That seems like a lot. I do like: - the theme - you thought of guaranteeing solution unicity before I came along and complained about it. Kudos! It's nothing too innovative as far as the CG platform goes, but it's a nice fit for a subproblem complexity combination, and it's well set. I'd like to see this approved.

Arglanir Unnamed CodinGamer

over 6 years ago

Thank you for your feedback. Depth H : H for height (in output) but depth because in reality it is not a height. SD for shortest distance "he algorithm results in long corridors in south and east" because no wall is being created in cells at h-1 or w-1. It's in fact a binary tree. I will rephrase a little and remove SD (not useful) and better use the barracks. We do see on CG a lot of mazes to solve, but no algorithm to create a maze.

Arglanir Unnamed CodinGamer

over 6 years ago

Sadly I cannot store in "Output" a maze bigger than 18x12 because of the maxlength="1000" in the textarea. Is it normal ? For "Input" we are limited to maxlength="10000". Such an injustice :-)

aropan Unnamed CodinGamer

about 7 months ago

Why not print full maze for small tests and print coordinate of treasure and coordinate of intercept only for big maze?

ABOUT US CAREERS PRIVACY FAQ BLOG

The #1 tech hiring platform

SCREENING INTERVIEWING