This can be a good interview question for Google to screw people over.
I was asked to write a code to generate maze (100x100) with the constraints that it should neither be easy not it should be hard. This was for L6 position.
That's a very interesting. I am curious to hear what your answer was :D
Here's my thoughts on what a solution would need:
1. At least one path from source to target.
2. Some quantification of hardness. No of steps in optimal path? Number of turns in optimal path? Number of paths? Some weighted combination of all three?
Some preliminaries:
Finding optimal path, and finding number of paths can both be down in O(N^2) using DP. Finding number of turns is then trivial.
Now the Algos for 1:
Algo for 1: Naive backtracking, i.e., randomly generate paths until there are no paths. Evaluate each maze using the heuristic and output best one. Run for some fixed time t. This is exp time.
Another algo for 1. Generate a path as following: select K points on the grid, with the start and end being the first and last; then finding optimal paths in sequence (notice that this guarantees not cyclical path). Next, generate fresh path on an empty grid and overlay on the previous path. Keep repeating for some M paths. Now fill in non path pixels. Pick the best grid among these M steps. This is O(M*N^2).
Last Algo for 1: Throw the grid into an ILP solver and optimize the heuristic (exp time).
Well, I addressed the "neither easy nor hard part" upfront. My take was there has to be a solution and that too 1 solution. In other words, it had to be fair.
Second was the degree of false paths (term I made-up). This essentially governs the branching of each false path. Higher the degree higher the branching and higher the backtracking. This would make the maze harder.
So my algo was
1. To generate a valid path from top-left to bottom-right. (this is simple bfs/dfs walk). This is illustrated as path 1-2-3-4-5-6-7..-10 below. This ensures we have a fair maze.
2. Now from each number below, generate path in an outward manner till it hits walls. These are false paths. The "degree" mentioned above will dictate if there are further branching out of these paths.
1 * * * * *
2 3 * * * *
* 4 5 6 * *
* * * 7 * *
* * * 8 9 10
In the step #1 we note the row,col in a dict/hashmap. We use these in step #2 to ensure the dfs walk dont step on these row,col.
This is all I could conjure-up in 45 min including a code in python. I was labelled lean-no hire.
Thanks for sharing the challenge and so cool to see the follow up and your actual answer.
Here's a linear solution I came up with, before I took a look at the rest of the thread:
1. Think of the 100x100 as pixels on a black background, all set to 0, i.e. all open space.
2. Now, draw a white square border all the way round by setting all the outer pixels to 1. No one can get in.
3. Leave a pixel gap and draw another square border within and then another and so on, like Russian dolls, with a pixel passage way between them. No one can get in.
4. Now, for each square border choose 1 random pixel and open it up by setting it back to 0. Now we're guaranteed of a solution, but it's too easy.
5. Let's make it a little harder, so between each square border let's drop a single pixel of "rubble" to block each passage way at one point. Provided we don't drop it directly in front of an opening in the adjacent square borders, I believe (unless I made a mistake somewhere!) we know the maze remains solve-able, and we don't need to do any iteration or "walk through the maze" to check that.
6. So far the runtime is pretty good. Nice and linear in the number of pixels drawn. We know the maze can be solved. And it's not too easy and not too hard.
7. (optional) We can make it harder still by tentatively dropping another pixel of rubble in a random passage way, and then walking through the passage to check that we can still reach the next inner opening. This is still better runtime than solving the whole maze, and can be tuned by the difficulty factor.
The insight is simply not to attempt to explore paths at all, i.e. not to try and "solve the maze" but only to "generate the maze", unless 7 is chosen, but that's probably not essential to the challenge.
I guess this could either be fixed up later with a simple check at the end, also linear, just in case it ever happens, or even just a condition whilst placing gates, that they can't be directly opposite the last gate placed but must be some x/y distance away.
Even without any check though, with a 100x100 grid, this is highly unlikely to happen often, as all 50 or so square borders would need to have their gate on the same side of the square, and at exactly the same position.
That's a few probabilities that would all need to intersect, i.e. I believe somewhere on the order of 1 in Math.pow(1/(100*4), 50) unless my probability theory is way off.
---------
This can be a good interview question for Google to screw people over.
I was asked to write a code to generate maze (100x100) with the constraints that it should neither be easy not it should be hard. This was for L6 position.