JohnyDL
commented
6 years ago I did go away and think about this a little, I think I've made something that solves part 1 and 2 of this challenge, if you'd like to play with it a little it's on KhanAcademy
https://www.khanacademy.org/computer-programming/random-connected-planar-network/4636353372389376
Random Graph Coding Challenge (Chinese Postperson Problem)
I recently rewatched the TSP videos (and a whole bunch of other coding challenges) and I thought there was some optimisation and real world aspects that could be drawn together. So I was thinking this challenge would be to create limited (rather than complete) graphs/maps that could be interacted with more generally and you could explore another interesting specific mapping problem, the Chinese Postperson Problem which you haven't done yet.
I don't think you've ever done anything with limited graphs like this in coding challenges and the things it covers might be applicable to a bunch of different things from visualising game level/maze design in alternate ways to displaying neural network data to my favourite example below real world mapping problems, there's obviously 3d expansion that could be done for say traversing the galactic map and as a way of thinking and playing with a whole host of common CS problems it'd be a nice toy. So much expansion on this topic is possible I've even added a bunch more direct extensions at the bottom and I've barely scratched the surface, see the off shoot problems and challenges for viewers
Challenge stages 1 Create a complete graph (or map) with nodes at random points on the plane and define all the edges that connect them (make the edges objects that hold their distance rather than constantly requiring recalculation for a change 😉) 2 Create an algorithm to detect when edges that cross other edges and remove the longer of the two, as a way of reducing the map to it's most important/useful connections. I can think of a three ways to achieve this A start with all edges included and test each included edge against each other edge (semi randomly/the order they were created/added to the network) and when a crossing is found, test which is longest and disable it, B start with all edges enabled sort the edges longest to shortest start with the (next) longest and test against all shorter enabled edges removing the edge being tested when a crossing found, C start with edges disabled sort shortest to longest test the (next) shortest against all enabled edges and if doesn't cross any then enable it, (thinking about it these 3 solutions all might create different graphs from the same data and exploring which graph is "better" would be interesting in of itself but all 3 should be connected graphs) 3 (optional) Create an algorithm that spreads out the nodes visually (maybe virtually inflating the nodes like soap bubbles or making them magnetically repulsive to move them apart and a springy force from the existence of edges then applying a little physics to create reasonable visuals of the network) if they're too close together to make the graph easier to look at but keep their original position data for weights on the edges 4 Chinese postperson problem on this graph, find the shortest path and shortest cycle that travels every (enabled) edge at least once, as an extension of Eulerian Path algorithm.
Off shoot problems
1 Apply A* (and other search algorithms) on this graph to get from one node to another 2 Traveling salesperson problem on this graph as a subset of the complete graph traversed in lexicographical order TSP coding challenge this algorithm this is 'harder' to code since not every edge is available to be traveled but should run faster since far fewer things to check, as it scales up many more invalid routes are added than valid ones (and it's more real-worldy since nodes could be considered road junctions or cities and edges the known fastest routes between them) also the Hamiltonian Path and Cycle are subtly different so show how to implement both, one finds the shortest path and doesn't care where you start or end the other is the shortest path that starts and ends at the same point. The difference being if I live at node A my shortest path including going home would start and end there but if I'm visiting another continent for my sales trip it doesn't really matter where I start and end cause I'm flying in and out anyway 3 Extend the edges nodes/code to allow edges to be one way does this effect the search algorithms, TSP or CPP solutions? 4 With the graph having one way routes show whether it's strongly connected then highlight disconnected/black hole regions that once entered cannot be returned from 5 If you keep the data for the "removed connections" by making booleans for traversible/enabled edges when a map is no longer strongly connected find the shortest route(s) that would make the graph strongly connected again (even if it crosses other routes) and re-enable it/them
Extensions for viewers 1 Possibly the off shoot problems 2 Graphically enhance the output, animate, colour nodes or edges based on weight, find the shortest route between all possible pairs and colour edges and nodes based on how much they're used etc 3 Apply other route finding algorithms, take the A as a base and figure out breadth first or depth first or flood fill etc 4 Scale up to more nodes, challenge: most nodes TSPed in 1 hour 5 Find the shortest route that includes only certain nodes, I'm going out I need to visit 5 places out of these 50 nodes what's the shortest route to do that, what's the shortest route never using an edge or node twice, etc 6 Find the shortest route avoiding certain edges, I don't like motorways or there's a traffic jam or roadworks what's the fastest alternate route 7 Interface with something like Google maps to get real world data for nodes and edges or importing/saving the data from/to file rather than random generation 8 Grade edges by other things than just distances (maybe prefer higher speeds, wider roads, better cared for etc) or make a hierarchy to nodes (clusters of nodes being treated as a unit one level up each super node having a distance to cross and the edges between super nodes being simplified rather than showing every interconnection) so traveling longer distances across the graph can be partially precalculated, for example if there's 10000+ nodes it might be useful to have partial solutions for traveling very long distances, nodes being individual junction level, precalculated routes could then being suburb to suburb, town to town and county to county would make sense, then the search functions could go find the local directions to a suburb route, then suburb directions to a town route, town directions to county, County to county as far as necessary and then step down again town, suburb, local for the end of the route rather than searching for the perfect route through all nodes A huge steps of the algorithm are predetermined this is likely how Google maps does some optimisation