Elven Village Mayor

[HonoreDB]

You've decided to found a new Elven Village, where elves can journey to set up residence and live out their immortal lives free from all those plebeian non-elves. You've picked out a plot of land, surrounded it with an impenetrable wall, and now you keep the sole gate. You've sent out word, and soon elves will begin to arrive.

Your duties will be as follows: you'll spend most of your time at the gate. You expect two kinds of travelers to arrive:

• Immigrants: When an elven immigrant arrives, you must direct her to an available patch of land, and create her home. You have strong house-building magic, so this shouldn't be too hard: you can create buildings of any shape and size, and even start building upwards when your population gets high enough.
• Visitors: Occasionally a visitor will arrive looking for a specific elf. Your job is to direct the messenger to that elf's home.

There's one complication, though. Elven names are ridiculously long. They're so long that writing them down would take up an entire house. They're so long that even an elf can't reliably remember more than one or two at a time. So it's not feasible to maintain a directory of where everybody lives.

What do you do?

Spoiler:

I constructed this puzzle to be equivalent to a certain problem in the discipline of computer science. I'm curious to see if people from outside that discipline come up with novel solutions or recreate the existing ones.

[mfb]

Spoiler:

- Use a hash function, maintain a directory of the hashes. In case of collisions, your village is way too large to be managed by a single person or your hash function is really bad. However, you can handle this with additional data in the directory
- or assign the place within the village according to the hash value itself. In case of collisions, move #2 to a different location based on some algorithm or write this down in the first location
- or build all houses along one path through the entire village volume, let the messenger compare all names along the path

As you probably guessed from my list, the problem is not completely new for me, although I am not "inside that discipline".

[WarDaft]

Spoiler:

We only need to remember enough of a given elf's name to distinguish that elf from all other elves living here. If large chunks of the names tend to be the same, we can simply skip around the name pseudo-randomly and store only those letters that we end up on. Even if two randomly chosen elf names tend to be 99% the same, then we still only need a few hundred characters to ensure that we have a unique tag for each elf. If they are even more similar, such that there are only a few letters different between any two randomly chosen elves, then we can simply take a number of elf names, note the most common letter for each place in the name, and determine a 'base' elf name. Then we only need record the differences from this base name, and where they occur.

You can then use your house building magic to simply build a directory to store these simplified tags and associate them with house locations.

And since 'filling a house' is a pretty weird base unit, I'm just going to assume you only meant very very big, rather than actually assured to fill any house you can build. You can then simply build a very tall house where the bottom n floors is used to store the full name of that particular elf, so that the messenger can verify that they have the right elf on arrival. (The only way they would not is if the elf is not actually living in this village, because by our above tagging specifications, we have 0 collisions between elves living in our colony.)

Note that there is no way to avoid needing the messenger to avoid needing to verify they have the correct elf on arrival, unless your plot of land is 2^(maximum possible number of elf names) in size. Which is rather unlikely if they're that long, and very inefficient.

[SheffJames]

I'm confused. If writing the elf's name down is not feasible and it is also not feasible to remember all the names how is the visitor supposed to identify the elf to whom he wishes to speak? Will they identify them by name? In which case it seems unavoidable to maintain a directory - as any hash table would surely need to contain their name in order to be mapped against something?

I assume I've misunderstood something.

Non Comp Sci person here.

[jestingrabbit]

I'm confused. If writing the elf's name down is not feasible and it is also not feasible to remember all the names how is the visitor supposed to identify the elf to whom he wishes to speak? Will they identify them by name? In which case it seems unavoidable to maintain a directory - as any hash table would surely need to contain their name in order to be mapped against something?

I assume I've misunderstood something.

Non Comp Sci person here.

You have to remember the hash function, and the hashes of who you've placed and where. You never need a directory of the names, just their hashes.

[SheffJames]

Ah, good point.

Well, as is pretty clear I wouldn't have come up with that method

Spoiler:

What I'd do, were I the mayor, is make it the lazy elves' problem if they had a visitor - I don't see why I'm running around after them. Each elf would be expected to check periodically whether a visitor was waiting for them at the gate.

I presume thats translatable into comp-sci-ese and I also presume its less efficient than the hashtable method. But without having read the spoilers, thats what I came up with by my lonesome.

[ConMan]

As long as (a) no-one ever moves out, and (b) visitors don't mind taking a long time to get wherever they're going, then you could implement a linked list. As the gatekeeper, you just have to remember (a) the details of the last immigrant and (b) the next location to build in. Then, you follow a couple of procedures.

For new immigrants,

Spoiler:

tell them where to build their house and the name and address of the previous immigrant. Then you can forget the previous guy and remember the details of the new guy, and work out where the next vacant lot is.

For visitors,

Spoiler:

tell them the name and address of the latest immigrant. They go to that elf's home, who will tell them the name and address of the elf who moved in before them. This continues until they reach the house of the elf they're actually looking for. Of course you start by telling each elf already in the village the name and address of another one in a way that starts the list.

[Лом]

My solution:

Spoiler:

Because I can build houses of any shape, I will presume that I can build really tall houses that will fit any elf.
Even if it is 1x1 cm^2.

So, first I will divide all my land in equal pieces and assign this pieces letter from elven alphabet. I also take some land to special place without letter.
I will live in that place.
I will use simple pattern and shapes equal to the shape of original land.
Each of the piece I will divide again using the same method. And again. And again.

So, elf with the name A will live in the block's A special place.
Elf with name AD will live in block A, subblock D special place, etc.

So, now elf name instantly gives me location of his house.

So what I try to accomplish here is make elf name his address.

P.S. Sorry, English is not native to me, and I think I made several mistakes, but hope idea can be understood.

[tomtom2357]

Assuming that all elvish names are different, you could arrange the houses by name.

[mward]

I'm surprised that nobody has yet mentioned...

Spoiler:

How to deal with hash collisions?

Rather than generate a huge directory, and hope you don't get any any collisions, you only need a modest directory: say the size of a slim telephone directory. The hash of an elf's name gives the page and line number of the elf's address. In the event of a hash collision, instead of the address you have "See Volume 2". Volume 2 of the directory uses a different hash function to avoid re-collisions. In the event of a hash collision in Volume 2, you switch to Volume 3, and so on.

The only difficulty is when a new entry collides with an existing address. Then you have to go to that given address and ask the Elf what his or her name is, so that you can re-hash it using the hash function for the next volume, in order to move that elf and the new one to the next volume. But this won't happen very often.

[mousewiz]

Spoiler:

The solution involving maintaining a hash -> location directory is the most obvious one to me, but it does have a problem. The hash function is likely to run in O(length of name), which is something we are told could be pretty costly. This has potential to create a bottleneck at the gate.

Depending on how the problem is interpreted, you could build a binary search tree. This would rely on taking "remember 1-2 names" to mean "2 names, plus their own name" so maybe it's a stretch, but it seems plausible. The benefit of the binary search tree is that each elf along a path (typically) only has to do a partial comparison of names so you probably won't hit a bottleneck unless the root node is very popular.

A BST does slow individual messengers down though, aside from them having to repeat parts of the name more than once, dereferencing pointers in a town seems like it could be an incredibly slow operation.

[Qaanol]

Here’s the best I’ve come up with:

Spoiler:

First, we refer to a hash of a name as a nickname. Second, my method involves hashing to a linked list.

We will have two methods of assigning nicknames, one that gives fairly short nicknames, and one that gives medium-length nicknames. We assume the medium nicknames are long enough that one wouldn’t want to store them for all the elves. For each type of nickname we have an index sheet and an address book.

The first index sheet stores all the short nicknames and next to each it has the number of elves with that nickname so far. If that number is exactly 1 then it has the line number in the first address book holding that elf’s address. A simple hash lookup.

The second index sheet stores all the medium nicknames of those elves whose short nicknames are not unique. Next to each of those, it has the number of elves with that medium nickname, and the line number in the second address book holding the address of the first of those elves. In that second address book, next to each address there is space to write the line number of the address of the next elf with that same medium nickname. A hash to a linked list.

By choosing a well-designed method of assigning short nicknames, we ensure that we rarely need to store any medium nicknames. And by choosing a well-designed method of assigning medium nicknames, we ensure that the linked lists almost never have more than one element each.

When a particular short nickname is given to a second elf, you will have to go to the address of the first elf with that short nickname, and give that elf a medium nickname. Then transcribe that elf’s address to the second address book.

When a particular medium nickname is given to an nth elf, you go to the line in the second address book with the address of the most recently added one of those elves, and next to it write the line number where the newest elf’s address will go. Or, if you like, you can build the linked list “backwards”, and have each address point to the previous, with the index page pointing to the most recent. That way you don’t have to traverse the whole list just to find its end, and you don’t have to add stuff to any existing address entry.

When a visitor comes looking for someone by name, you turn that name into a short nickname. If it’s unique, you look up the address and give it to the visitor. If not, you turn that name into a medium nickname, and write out a list of addresses of all elves with that medium nickname (which should be only one, or very few) and give that list to the visitor. If the list has more than one address, the visitor will have to compare full names at each one, but that should be extremely rare.

We could, of course, do away with the first address book, and just have a single hash to linked lists. That works too, but the tradeoff is that it requires a longer hash to get the same performance, so you have to store more information yourself as gatekeeper.

Whereas mward uses arbitrarily-many hash functions, I’m stopping at 2. There should be so few collisions that performance is barely reduced, and with mward’s method there is no upper bound on the number of hash functions that might be required—it’s not even bounded by the population of the village, because you don’t know if a given hash function actually distinguishes among any of the names until you try it.

Also,

Spoiler:

Keeping the list of nicknames nicely organized is must easier with a Rolodex where you can insert into the correct position. This can be done with a linked list, and a few “divider” pointers, but may require a bit of effort to keep the divider pointers up to date, depending on whether you want them to bisect or only to mark first letters.

Regardless, if you have a quantum computer available, there’s a method to search an unsorted array in √N time. That way you can just list the nicknames in the order you create them, and never have to rearrange them nor deal with rolodex dividers.

[WarDaft]

Spoiler:

That's one reason I went with shortest name prefixes needed to uniquely describe the elf, with the choice to choose letters pseudorandomly from throughout of the name. If we repeat the assumption that two randomly chosen elves will have names roughly 99% similar, then as long as elves can remember specific parts of a name quickly, then the whole process can still be done quickly and efficiently [O(key) rather than O(name)]. 1000 characters on average is still likely sufficient for a population of thousands. 2000 characters is enough for tens of millions.

[mward]

Nobody has made use of this part of the description yet:

and even start building upwards when your population gets high enough.

Which suggests a possible solution that the setter may have been thinking of:

Spoiler:

Hash each elf's name to a location (an XY coordinate) build the elf's house at that location. If there is already a house there, build the new elf's house on top of the existing house. Direct the (occasional) visitor to the XY coordinate of the name of the elf they want to visit: if there is a stack of houses at that location, the visitor checks the ground floor first. Each elf can remember one or two names, so will know the names of one or two neighbours. So the visitor won't necessarily have to check every house in the stack.

With this method, there is no directory needed at all.

Spoiler:

If we repeat the assumption that two randomly chosen elves will have names roughly 99% similar...

Spoiler:

The assumption sounds reasonable, but cannot be relied upon. Elf names are probably something like: "Legolas, son of Thranduil, son of Oropher, son of..." going back for thousands of generations, with the same names appearing over and over again: i.e. there are just a few popular elf names which everyone uses. So siblings will have identical names, apart from the initial prefix. Also, certain sequences of names are considered "harmonious": so for example, any elf whose name starts "Thranduil, son of Oropher, son of..." is almost certain to call his first son "Legolas, son of Thranduil, son of Oropher, son of...". It just "sounds better that way". So many elves who are not closely related end up with the same (long) prefix in their names.

[jestingrabbit]

Nobody has made use of this part of the description yet:

and even start building upwards when your population gets high enough.

Which suggests a possible solution that the setter may have been thinking of:

Spoiler:

Hash each elf's name to a location (an XY coordinate) build the elf's house at that location. If there is already a house there, build the new elf's house on top of the existing house. Direct the (occasional) visitor to the XY coordinate of the name of the elf they want to visit: if there is a stack of houses at that location, the visitor checks the ground floor first. Each elf can remember one or two names, so will know the names of one or two neighbours. So the visitor won't necessarily have to check every house in the stack.

With this method, there is no directory needed at all.

That sounds pretty good actually. But, just fyi, please edit posts rather than making a new one if you're the last poster in a thread. -jr

[WarDaft]

Spoiler:

The assumption sounds reasonable, but cannot be relied upon. Elf names are probably something like: "Legolas, son of Thranduil, son of Oropher, son of..." going back for thousands of generations, with the same names appearing over and over again: i.e. there are just a few popular elf names which everyone uses. So siblings will have identical names, apart from the initial prefix. Also, certain sequences of names are considered "harmonious": so for example, any elf whose name starts "Thranduil, son of Oropher, son of..." is almost certain to call his first son "Legolas, son of Thranduil, son of Oropher, son of...". It just "sounds better that way". So many elves who are not closely related end up with the same (long) prefix in their names.

I went into more detail in my first post, offering ways to guard against things like that. Of course, for any strategy we can come up with a set of names that it is inefficient for, but I'm assuming that we're designing the system having knowledge of the kinds of the names it will have to work on, rather than designing names having knowledge of the system they have to mess up.

Also, it would take not thousands but hundreds of millions of generations to get names that long that way.

[hoopsgators]

you want to live here? your new name is Bob. you don't like it? well too bad. proceed to lot 1. and tell your friends so when they visit you they know what name to tell me. NEXT!

[MrHemroid]

The slow-search, but quick-add method:

Spoiler:

An array (or list, or vector, or 1 dimensional matrix, whatever you wish to call it).
Have the first elf be elf #1, The 2nd elf be #2, etc. Don't remember their names, just remember how I can contact them (like a phone number).
When someone new comes to live there, put him in the list as the nth elf.
When someone comes to find a friend, call each elf (starting at 1, up to n) and ask if he is the guy they are looking for. If he is, then ask him where he lives.

time to add: Order of 1, constant time.
time to search: Order of N, worst case scenario.

The quick-search, but slow-add method:

Spoiler:

A binary search tree.
I will be the initial elf, aka the root of the tree.
When a new elf comes to live, I determine if his name is less than or greater than my name (alphabetically, might take awhile).
Algorithm1:

Code: Select all

If his name is less than mine:
            if there is currently no one less than me: he becomes the guy I have to remember to the left of me.
            else: I tell him to go to the guy I remember to the left of me, and that guy does this same algorithm.
if his name is greater than mine: same thing as the case for less than, except replace "left" with "right."
else: Hey! We have the same name! Well, since I was here <nth> your name is now <name><n+1>. Go to the guy to my right.


When an elf comes to find a friend:
Algorithm2:

Code: Select all

if the friend's name is less than mine: tell him to go the the guy that I remember is to my left (and he does this algorithm too).
if the friend's name is greater than mine: just like less than, except replace "left" with "right."
else: He is looking for me! Hello old friend!


time to add: Order of Log(N), on average. order of N, worst case (the elves showed up in alphabetical order, and my name is "a").
time to search: same as adding.

[t1mm01994]

In the case of same names you're boned anyways, so you might as well leave that out.. I doubt the visitor would know which number his $elvenname elf is.

[tomtom2357]

you want to live here? your new name is Bob. you don't like it? well too bad. proceed to lot 1. and tell your friends so when they visit you they know what name to tell me. NEXT!

I like this one the best!

[hamsterofdeath]

i make one big house covering the complete area. every elf lives in this house. i sent every visitor in. problem solved. O(1).

[soraos21]

Visitor Solution:
"Immigrant or visitor?"
"Visitor."
"Do you know the name of the elf you're looking for?"
"Yes, I do."
"Step inside and shout the name out as loud as you can."

Immigrant solution:
"Immigrant or visitor?"
"Immigrant."
"Do you remember your elven name? I'm only asking for simplicity's sake, no need to say it for me."
"Yes, I do."
"Good. To make things far simpler in terms of registration, you will be given a random name which you are to remember. When you greet a fellow resident, state the name you have been given, as it will be easier to remember than a full elven name. Please make your way to the nearest open residence and your belongings will be brought to you shortly."