Landmarks

This is Mike's problem so I'll simply get out of the way and let him describe it.

Bangkok, like many big cities, is fairly easy to get lost in. Everywhere looks much the same and it is easy to get disoriented in unfamiliar parts of the city, especially if there are no English signs. Imagine if we could simply make a list of the things nearby, and then give this to a program which could tell us not only our location but the direction we are facing, based on its map. How might such a system work?

First, let's simplify the problem a bit:

Imagine that we treat the city as an m x n grid. Assume everything fits in one grid square.

• We are standing in the middle of a single grid square.
• We can be facing one of four directions, north, south, east, or west.
• We don't know which direction we are facing.
• We list the 8 things around us, starting from the thing in front of us.

To make it usable by idiots who don't know clockwise from anticlockwise, we can list things in either direction. We don't say what we are standing on.

The program only knows about a few types of things. Initially it only understands:

1. Road
2. Shop
3. House
4. Other

We assume that the database and map are already built into the system. We accept that sometimes it won't have enough information be able to give us an exact answer.

We tell the system what we see and it converts this into a code, which it uses to look up our location from a table:

Landmark BeerCamp puzzle For example, we are standing near the corner of a road, we could say:

I see a shop(2), a house(3), a road(1), a park(other - 4), a house(3), road(1), road(1), and a shop(2).

This gives the code 23143112. However, because we could have started facing a different way, this is equivalent to 14311223, also to 31122314 and 12231431. Because it doesn't know if we turned clockwise or anticlockwise, it is also equivalent to 22113413, 11341322, 34132211 and 13221134. So the system must see all these as the same. Based on which version of the code it had to use to find the answer, it can tell us which direction we are facing.

Questions:

1. Given all this, how many different places could the system distinguish?
2. Obviously this is too simple and wouldn't be able to distinguish enough places to be useful. Let's say we need to be able to distinguish 100,000 different places. We can only increase the number of different types of things the program understands, for example, we could add more types of things - cafes, schools, parks, types of shops - 7-11, FamilyMart, Big C, types of abode - house, condo, hotel etc. What is the minimum number of different types of things for it to be able to distinguish at least 100,000 places?