Count the Flags

[gavinksong]

(Hello, friends. This is yet another puzzle from BWOC. I don't know the solution to this one yet, so I was thinking we could work on this together.)

You are tasked with designing a robot to explore a large but finite maze. The maze is drawn on a square grid, and walls exist on some of the edges of the square grid. Some of the squares contain a flag.

Your robot may interact with the world in the following ways:

1) Check which of the 4 adjacent edges contain walls.

2) Move to one of the 4 adjacent squares (provided there is no wall in the way).

3) Check if there is a flag on your square.

4) Pick up a flag (provided there is a flag on your square and the robot is not already holding a flag).

5) Put down a flag (provided the robot is holding a flag and there is not already a flag on your square).

6) Generate a random bit.

7) Output a number.

Your robot will be placed in a maze. The maze will contain some number of flags (from 100 to 1000). All flags will be reachable from the robot’s starting position. Your robot is tasked with determining the number of flags. The robot may take as long as it needs, but may only output one number and must output the correct answer eventually, with probability 1.

The catch is that your robot is not Turing complete. It only has a finite amount of memory. You can give your robot as much memory as you need, but it must succeed on arbitrarily large mazes

[gavinksong]

We need some way of testing whether we have found all of the flags, which may yield false negatives but no false positives.

[DejMar]

Is the task then to provide pseudo-code for an algorithm that correctly "maps" the maze using a virtual 'robot' as an exploration tool? And, though it must be preferred, is a most efficient algorithm - with the restraints given - required for the task? 

[gavinksong]

Is the task then to provide pseudo-code for an algorithm that correctly "maps" the maze using a virtual 'robot' as an exploration tool? And, though it must be preferred, is a most efficient algorithm - with the restraints given - required for the task?

However you want to phrase it.

The problem states that you can take as much time and allocate as much memory as you need. I think you will find that it is hard enough just to find something that works.

[bonanova]

One important assumption not to make is that the walls are all connected. There can be islands.

That is, you won't necessarily get through the maze, nor explore all of its area,

simply by keeping a wall on the robot's left or right.

[DejMar]

One important assumption not to make is that the walls are all connected. There can be islands.

That is, you won't necessarily get through the maze, nor explore all of its area,

simply by keeping a wall on the robot's left or right.

 

 

Having referenced the Wikipedia article on "Maze solving algorithm", a possible algorithm to use is the "Pledge algorithm." By tracking the angular sum of the turns made and the current heading, a 'robot' could avoid being trapped in a loop. As the objective of the 'robot' is not to find an exit, but all the flags, the algorithm would need be modified. An important inclusion to the algorithm would be to "map" the grid, so as not to miss any passages or locations. An incorporation of an aspect to "Trémaux's algorithm" could be used to register the visited locations and note any, as of yet, unexplored junctions.

Edited October 25, 2014 by bonanova
Added spoiler

[gavinksong]

 

One important assumption not to make is that the walls are all connected. There can be islands.

That is, you won't necessarily get through the maze, nor explore all of its area,

simply by keeping a wall on the robot's left or right.

Having referenced the Wikipedia article on "Maze solving algorithm", a possible algorithm to use is the "Pledge algorithm." By tracking the angular sum of the turns made and the current heading, a 'robot' could avoid being trapped in a loop. As the objective of the 'robot' is not to find an exit, but all the flags, the algorithm would need be modified. An important inclusion to the algorithm would be to "map" the grid, so as not to miss any passages or locations. An incorporation of an aspect to "Trémaux's algorithm" could be used to register the visited locations and note any, as of yet, unexplored junctions.

Good work, but use spoilers.

Edited October 25, 2014 by bonanova
Added spoiler

[DejMar]

Thanks for adding the spoiler, bonanova. The reason one was not included was the parenthetical opening statement:

 

(Hello, friends. This is yet another puzzle from BWOC. I don't know the solution to this one yet, so I was thinking we could work on this together.)
 

I still am not sure what kind of solution is being asked of the BrainDenizens.

[plasmid]

To make sure the rules about maze size vs memory are clear: Does that mean that we should be able to come up with an algorithm such that, given any maze of finite size, we should be able to define some finite amount of memory that would be sufficient for the robot to find the flags in that maze, but both the maze size and amount of memory could become arbitrarily large? Or is it saying that we should be able to come up with an algorithm that will always succeed with some fixed amount of memory for any arbitrarily large maze, without needing to scale up the memory as the maze gets larger?

 

If it's the former, then the robot could just draw a map of the maze in its memory as it progresses. If it's the latter, then the problem is essentially asking for a strategy along the lines of the "always follow the right-sided wall" where you don't need to keep track of all of the previous moves, but which will get you to every open square of the maze.

[gavinksong]

To make sure the rules about maze size vs memory are clear: Does that mean that we should be able to come up with an algorithm such that, given any maze of finite size, we should be able to define some finite amount of memory that would be sufficient for the robot to find the flags in that maze, but both the maze size and amount of memory could become arbitrarily large? Or is it saying that we should be able to come up with an algorithm that will always succeed with some fixed amount of memory for any arbitrarily large maze, without needing to scale up the memory as the maze gets larger?

If it's the former, then the robot could just draw a map of the maze in its memory as it progresses. If it's the latter, then the problem is essentially asking for a strategy along the lines of the "always follow the right-sided wall" where you don't need to keep track of all of the previous moves, but which will get you to every open square of the maze.

It's the latter.

I can't figure this out.

[CaptainEd]

I assume that

( 1 ) as the number of flags is bounded (between 100 and 1000), we can require enough memory to store a record for each found flag, and can declare how long a record is

( 2 ) a memory cell has finite precision, and that the dimensions of the maze could be arbitrarily greater than the largest value of a cell. So, although we could store some information about each found flag, we could NOT store coordinates. In fact we cannot even store coordinates of one spot (after all, we may have walked a googolplex number of steps in a straight line).

( 3 ) we are NOT permitted to leave anything in a square except a flag, and are not permitted to distinguish the orientation of the flag.

Are these all true assumptions about the rules?

Edited August 25, 2015 by CaptainEd
added an assumption

[CaptainEd]

Gavin, mature reflection suggests to me that my assumptions ( 1 ) and ( 2 ) above are good assumptions, that make an interesting, challenging puzzle, but that ( 3 ) makes it impossible.

( 1 ) makes it possible to keep some information about each flag; ( 2 ) if you had infinite precision arithmetic, then one number could act as all of memory, large enough to contain a map of the entire maze, so restricting to finite sized numbers makes the puzzle interesting; ( 3 ) If the robot could leave breadcrumbs (Tremaux's algorithm, noted by DejMar), then you could imagine a strategy in which the robot uses the maze itself as the unbounded memory, tallying flags that have no breadcrumbs on them, and figuring out a way to determine that it has seen all of the boundary and all of the insides.

So, did you somehow accidentally leave out one of the rules (I doubt it, as you a careful guy, but I can hope...), and the robot IS permitted to leave more than just a flag in a maze cell?

[CaptainEd]

Even more mature reflection suggests that relaxing ( 3 ) is not realistic--you would NOT have left off such a key rule. So, I propose relaxing my interpretation of ( 2 ). Please tell us if this is acceptable:

( 2 ) our memory cells are big enough to hold a small multiple of S (the length of the side of the maze). 

This would allow us to store coordinates, and (in "double precision") perimeter lengths. As ( 1 ) says, we can keep a small amount of information about each flag (up to 1000 flags). But it would not permit us to create a stack of Order ( S ). With this relaxation, we can ( a ) number our starting location as (0,0), ( b ) remember the largest values of (N, S, E, W) and the coordinates of a point for each, ( c ), trace a right-handed path around a circuit, keeping a net turn, so as to determine whether the circuit was an interior island or the exterior wall, ( d ) Eventually be sure of being on the exterior walls. It is not obvious to me how to perform a raster scan of the cells, which is part of the pleasure of this puzzle. 

 

Edited September 15, 2015 by CaptainEd
un-embed the first sentence

[gavinksong]

On September 15, 2015 at 10:29 PM, CaptainEd said:

Even more mature reflection suggests that relaxing ( 3 ) is not realistic--you would NOT have left off such a key rule. So, I propose relaxing my interpretation of ( 2 ). Please tell us if this is acceptable:

Hidden Content

I appreciate the amount of thought you've put into these responses.

Unfortunately, I do believe all three of your original assumptions are correct. Again, I don't know the solution to this problem, so I can't be sure. The basis for my opinion is the following line from the OP:

On October 24, 2014 at 7:05 PM, gavinksong said:

6) Generate a random bit.

I am thus led to believe that "memory" refers to binary memory. This implies that assumption (1) is true as long as each record is a fixed number of bits and that assumption  (2) is true, since instead of arbitrarily precise "memory cells" we have bits. It follows that your proposal for relaxing assumption (2) is likely not intended by the OP.

I think you were on the right track with using the maze itself as a source of boundless memory. The problem certainly seems impossible, but I assure you that this has been a signature of BWOC puzzles. I truly believe that there is a way to solve the problem as we currently understand it.

I suspect that it's necessary to somehow leverage the infinite amount of time we have. The OP states:

On October 24, 2014 at 7:05 PM, gavinksong said:

The robot may take as long as it needs, but may only output one number and must output the correct answer eventually, with probability 1.

"probability 1" suggests that we can converge on it over infinite time. If we could design an algorithm that every now and then has some probability of returning the correct answer with no chance of being incorrect, then over an infinite timeline, the probability of success would converge to 1.

[CaptainEd]

Gavin, I don't see any rules saying where you can put the randomly generated bit. do we imagine that it can be placed into our finite memory? 

I like your suggestion that the random bit might contribute to a Roomba-like exploration :-) of course I don't see how yet.

[gavinksong]

That seems to be a reasonable assumption, CaptainEd.

[CaptainEd]

More thoughts

Let's divide the problem into three parts: I think I see how to solve two of them, but the third suffers from the challenge identified by Gavin.

[spoiler=Carry Flags]once you find one or more flags, drag them behind the roomba. In detail, move the lead flag forward (whatever direction you aim to be moving), and then work your way back in your chain of flags, moving each one forward. Then go the front of the chain and move forward, checking for a new flag. Keep going until you hit a wall.

If you run across a new flag, move it to the back, and put it in a linked list. (Remember that we can pre-establish a fixed amount of memory. Let's allocate, say, 5 memory cells for each of 1000 potential flags. While we can't expect to have cells be large enough to count absolute coordinates, but we can count "local" coordinates, such as distance from one to the next in a chain.) [/spoiler]

 

[spoiler=gather flags on a wall]once you hit a wall, use the standard policy of traversing with your right hand on the wall, and dragging the chain of flags with you. As soon as all of the flags are adjacent to the wall, drop the chain. 

Now continue around the wall until you hit more flags. When you hit a flag, follow the flags to see if you've run into your dropped chain. If the number of flags is different from the chain you dropped, then these are new flags, so drag them back to the dropped chain and concatenate them. Then continue around the wall. 

If the new chain of flags is the same length, and has exactly the same shape as your dropped chain, then let's see if it is the same chain: tweak the chain (by moving the tail element backward, leaving a gap from the rest of the chain, for example). Document the chain you are dragging with you with this tweak, then leave it here and traverse backward until you hit a chain of flags. It must be the first one you dropped. Does it have the same tweak that you just made to the "new chain"? If so, they are the same chain, and you have completely circumnavigated the island. If not, they are separate chains, so bring the first one forward to merge with the new one, and continue forward around the boundary. 

As long as you have two or more flags when you find an island, you'll be able to gather all the flags adjacent to that island, and be sure that you have seen its entire perimeter. [/spoiler]

[Spoiler=Pledge won't work]You can't distinguish the outer boundary from large internal islands. The Pledge algorithm won't work, because the maze can be so large that an internal island can have a spiral so much longer than the side of the maze, that our rotation counter will overflow clockwise before it starts restoring counterclockwise.

Still, we can treat the outer boundary exactly like a large internal island. 

So we can (a) wander around in open space, gathering a chain of flags, (b) attach a chain of flags to an island, and unambiguously gather all flags adjacent to that island. 

[/spoiler]

[spoiler=remaining challenge] Our only challenge remaining is the first one Gavin pointed out: how can we ensure we will wander over the entire reachable space? I dunno. Maybe we have to emulate growing plants: make little directional experiments when wandering open space. Can't specify or prove [/spoiler]. 

[gavinksong]

20 hours ago, CaptainEd said:

Spoiler

we can count "local" coordinates, such as distance from one to the next in a chain.

 

Hmm. Since distances aren't bounded, we can't store them in memory. You could mean...

Spoiler

direction from one to the next in a chain. This works assuming you put the trailing flags adjacent to each other.

Also,

Spoiler

For detecting whether you've run into your chain, you could just check whether you've left a flag at that block. You should have enough information stored in memory to calculate the location of every flag in your chain, unless I've misunderstood.

Spoiler

It's a good point that the pledge algorithm wouldn't work.

 

2 minutes ago, gavinksong said:

Hmm. Since distances aren't bounded, we can't store them in memory. You could mean...

  Reveal hidden contents

direction from one to the next in a chain. This works assuming you put the trailing flags adjacent to each other.

 

On further reflection, it appears that you are right.

Spoiler

If we assume that consecutive flags in our chain are adjacent to each other, we lose the ability to travel through our own chain, which could cause the robot to get stuck. Thus, we need to be able to put consecutive flags in our chain farther apart - but never by more than 1000 squares, which allows us to represent their relative positions in bounded memory.

 

[CaptainEd]

my apology, yes I intended that I would drag the flags along in a contiguous chain, although as you point out, they could be spread out a bit.  Separately, I don't believe the rules prevent me from moving through a cell that contains a flag. In fact I believe I can carry a flag through a cell that contains a flag.

[gavinksong]

1 hour ago, CaptainEd said:

 

  Hide contents

my apology, yes I intended that I would drag the flags along in a contiguous chain, although as you point out, they could be spread out a bit.  Separately, I don't believe the rules prevent me from moving through a cell that contains a flag. In fact I believe I can carry a flag through a cell that contains a flag.

 

Spoiler

Sorry, I wasn't very clear. There's nothing that stops us from passing through a cell with a flag. I meant that when we trail flags behind the robot and store their positions in a linked list, if we set the rule that flags with consecutive indices in the linked list are adjacent to each other spatially, we could not pass through a cell that contains an old flag without breaking this rule (since we would not be able to move the lead flag forward due to the square already being occupied by the old flag). Thus, to avoid obstructing our own movements, we need to allow the chain to pass through itself by occasionally allowing gaps between flags.

 

Edited August 11, 2017 by gavinksong

[CaptainEd]

Gavin, I agree, a permeable chain is necessary. Here’s a simplified (and still incomplete) proposal:

I like carrying around all the flags in a permeable chain. I am no longer enamoured of parking the chain on an island, appending any additional flags found adjacent to the island, and then marooning them in search of more flags and islands. If the roomba revisits the island later, It won’t recognise it as already seen, as there could be several islands with exactly the same patterned chain (improbable, but not impossible). So, I recommend carrying all the flags around all the time.

I still don’t see how to create a randomised path that is certain to visit every reachable cell. AND I don’t even see what form of condition would cause the roomba to announce its final total. It can’t count the steps in its run. It can’t even count the number of steps since the most recent flag discovery.