I'm doing a Travelling-Salesman-type problem where I have to visit every room in a world at least once by programmatically returning a list of traversal directions (e.g. 'n', 's'). The program to return the list can run for any amount of time but the list should be shorter than 2000 elements.
e.g.
traversal_path = ['n', 'n', 's', 's', 'e', 'e', 'w', 'w', 'w', 'e', 's','n']
It does work. In a few seconds my program returns a list of around 4.3k steps. Others have gotten it under 2k and even in the 900s. I don't think I can get that low with my algorithm but I want to see if I can get lower and maybe get under 2k but if not at least learn something.
I came up with my own probably naive approach through sweat and tears, but I want to stick with it a bit longer and see if I can't squeeze any more juice out of it by implementing my strategy below. My algorithm is at the bottom for those interested, but it's not critical to know for my question, which is:
I was wondering if I could filter my list to remove redundancies.
Suppose we have a list of directions
list = [n, n, n, w, w, e, e, s, s, s, n, n, n, w, w, w, e, e, e, s, s, s]
You'll notice that you can split the list into two lists sublists split near the center, L1=[n, n, n, w, w, e, e, s, s, s] and L2=[n, n, n, w, w, w, e, e, e, s, s, s]. L2 covers every room covered by L1 plus one more. That basically means for my purpose, L1 is useless and just taking up space. How would one go about identifying and filtering that out? (I'm also interested in this for it's own sake)
Specifically can we chunk the big list into multiple sublists or a list of lists where each sublist is defined as a sequence where it is known to begin at the 'origin' (the presumed location of L[0]) and ends back at the origin, and such that the first half of the sublist is a mirror image of the 2nd half ('e' being a mirror of 'w' for example) such that [e,e,s] = mirror([n,w,w]). After I build such a list of lists, I can see whether any sublists are supersets of others (order mattering) and then I can remove the non-super sets and thereby reduce my direction count by throwing out redundant blocks of steps.
If I can determine the index each time the player following the list would be at the origin, then I can make those 'cut points'. The origin would be therefore at index=0 and any time a full mirror is realized, when the subpath has fully 'folded back on itself'
I was wondering if there's a library for doing this or useful built in functions, or a name for what I am wanting to do, or otherwise any elegant techniques you wouldsuggest.
THE ALGORITHM I USED FOR CREATING A PATH TO VISIT EACH ROOM: I basically did a breadth first traversal to create a pair of maps (based on the classes provided) that I could use to get the direction to any room from the origin. I also populated a list of terminal rooms (rooms with only one way in and out) and I extended the traversal_list with a 'there and back again' set of directions to each terminal.
This didn't cover loop cases(which might be the only place where there are redundancies I can eliminate with my attempt above) so I made a list of unvisited rooms and chose at random from them to be a 'pseudo-terminal'. I would have the function visit that pseudo terminal and then repeat the process until each room in the entire world had been visited.
I don't suppose there's a way to remove even more redundancy with this data (in other words, delaying returning to the origin to cover other terminals)