Daily Challenge Day 22

Following on from yesterdays post, I created a travel path forming a continuous loop.

Yorke Peninsula Towns Connected by a Loop
Yorke Peninsula Towns Connected by a Loop

This isn’t the optimum path, the path was manually drawn in ProgeCAD starting with the east/west zigzag path from yesterday. The towns on the eastern side were connected in a line and likewise for the western towns, then the east/west lines were arbitrarily connected to either the eastern or western edge. In the main the inner towns are connected to the western coast, making the eastern edge, a near uninterrupted journey along the actual coastline. The only problem with drawing such path is that there is no quick and easy way to generate a list of the towns along the path.

I drew the path because things weren’t working out in my attempts to generate the path. I ended up testing my worksheet linked list class rather than generating any paths. Whilst my linked list implemented in a worksheet allows me to view the state of the list and store the list, at the moment it doesn’t have any routines for reading the list and using as is. Therefore I need to implement such before can progress further.

Previously in connecting towns if they were within a specified radial distance, I merely scanned the worksheet table of towns from top to bottom, comparing each town in turn to all the other towns. The problem with that approach is it is time consuming to process the data, and it also generated two lines connecting each town, which slows the Acad script down as well as producing a messy drawing. I solved that by using an extra pointer/counter to move the front of the compare list. So having selected a town it only compares against all the towns listed after the current town, as all towns listed before have already been compared.

For the current simple exercise (a stepping stone to the actual task) I want to select a town, and connect to the radially closest town. Once I have found a suitable town I want to drop that from the compare set and add it to the results set. For that purpose I thought a stack or a linked list would be suitable. Since I don’t know the required order of the towns on a stack, I decided a linked list was the appropriate option. Looking at how the linked list is implemented made me think I could reduce the storage requirements.

On the previous tasks I have been using two worksheets, one with the point cloud for the towns and a second sheet with the generated connectivity list. On the connectivity list worksheet I use worksheet formula to generate the Acad Script for copy pasting to the ProgeCad command line.

Before looking at the linked lists, I had added an extra field named “isVisited” to my table of towns. It is a boolean type field, with the purpose of identifying that the town had been visited already and therefore skip and move onto another town. The problem with that approach is the data has to be processed and then ignored, thus wasting time. The better option is to skip that chunk of data in the first place. A linked list has the potential to do that, assuming I implement it correctly in the worksheet and am not scanning all the rows of data to jump from one element to the next.

To implement the linked list in a worksheet I just need to add an extra column alongside the data containing a reference to the next node in the list. The default sorting of the points is the east/west zigzag pattern, therefore the default linked list would just be a chain of towns defining the zigzag pattern. Therefore the program doesn’t need to use a second worksheet to tabulate the results, all it needs to do is modify the values of the next node fields: so that the original worksheet contains a modified linked list presenting the required solution. Admittedly that has to be converted into Acad script to draw the connections, but that could be written directly to a script file (.scr) instead, or I could opt for using ProgeCAD’s COM automation capabilities and draw directly in CAD.

The other issue is that my current implementation of a linked list has a head and a tail, for the current task it may be better to make the list looped by connecting the head to the tail better representing the closed travel path I am aiming for. So the more immediate task is to make modifications to my linked list data structure.

As for the current looped path it measures 1064  km, where as my estimate yesterday was that the path should be less than 750 km based on one loop of the enclosing rectangle.

So for an alternate estimate, assume three vertical columns of towns, western coast, eastern coast and inland. There are 124 towns, therefore have approximately 42 towns per row. There would therefore be 41 vertical paths connecting the towns within each column, and 42 paths to connect the columns. That is 42 east to west paths, of 42 times the width of the enclosing rectangle. So a new crude estimate for the upper limit on the travel path is (2240) +(42135) =480+5670=6150 km. Which at 100 km/h results in a 62 hour trip, or 124 hours if travelling at 50 km/h. Assuming 8 h/day then would take 16 days. From previously need around 4 months to spend one day at each town, with the  travel time added this is approximately 5 months. therefore can only complete 2 full loops each year.

The estimate ignores actual roads, as well as the reality of east/west travel also including north/south travel. Given have one looped path measuring 1064 km, I don’t expect the actual path when take roads into consideration will climb higher than 2000 km.

The general expectation is that the loop will typically be entered at the north eastern corner, with most travellers coming from Adelaide via Port Wakefield. For which purpose I guess that including Port Wakefield on the map and in the loop may be useful. Though given the time and effort required to get a point from Google earth, into QGIS and out to Acad/ProgeCAD in Australian Map Grid (AMG) Coordinates, that can wait till the distant future.

So basically can enter the loop from Port Wakefield via Port Arthur. From there can travel to the south of the peninsula to Stenhouse bay, and then north up to Nelshaby, and then back to Port Arthur.

Or from Maitland, the apparent heart of the peninsula, where I am located, the option would be to travel along the west coast to Stenhouse bay, then north along the east coast through Port Arthur to Nelshaby, and then south along the west coast back to Maitland. Since such a trip passes near by home, the trip could  be broke into two loops, which are followed in the manner of a figure 8: that is loop up to the north along the west coast, then south via the east coast crossing back through Maitland, travelling south along the west coast and looping up along the east coast returning to Maitland. Such similar loops being created for any inland town used as a point of origin.

However at the moment the task is to get a sequential list of towns which form a loop. Once I have the list then I can go seek more background information on each town, following the sequence of the list.