undefined | Better HN

0 pointsdsp123411y ago0 comments

Start drawing random lines.

I got this on my first try:

  +------------------+--+---+
  |                   - |   |
  |                    -|   |
  |                     +   |
  |                     |- -|
  |                     | + |
  |                     |- -|
  |                     +   +
  |                    -|   |
  |                   - |   |
  |                  -  |   |
  |                 -   |   
  +----------------+----+---+

I got that by drawing an exterior square with a single entrance in the bottom right hand corner. I then drew a line from the top wall to the bottom wall parallel to the left and right walls. I then drew a diagonal line from about a quarter of the way down the right wall left and downwards towards the bottom wall. I then drew a diagonal line from about three quarters of the way down the right wall, up and to left towards the top wall. This blocks off most of the maze. So I'm not sure the algorithm works as has been described.

0 comments

jfoutz11y ago

Ah! Each wall is one continuous line, regardless of twists and turns. Connecting the top to the bottom is what got you stuck.

Edit

I guess each wall can only be anchored at one end. Trying to think about how to restate it in a clear way.

dsp1234OP11y ago

This additional twist makes the original statement of:

without the need for backtracking or bookkeeping

appear to be misleading. You have to do some bookkeeping in order to know if the wall that your line just hit is connected to the start point, or any midpoint of the line you are drawing. The complexity is just hidden behind simpler words (They may only cross some other line at most once.).

Also, I'm not sure how the backtracking is missing. Once you've hit a new wall with your line, and check connectivity, if it's actually connected, then you have to backtrack that line until it's back to a place where it's no longer connected. Connectivity could be checked right before hitting a wall, but then it's just backtracking by another name. So I'm really not understanding how this would be implemented in an simpler and/or faster way.

1 more reply

j / k navigate · click thread line to collapse