vindennt / Skytrainer

Productivity habit forming app using React Native and mobile gacha game design principles.
1 stars 0 forks source link

findViableTrips fails infinite loop #5

Closed vindennt closed 1 year ago

vindennt commented 1 year ago

findViableTrips(graph, Sapperton, 64) is the first to fail because traversal goes from Sapperton and then Commercial Broadway. From there, it is supposed to traverse onto the Millenium line, then onto Expo line to go past Production Way University to create infinite loop on the Expo line (lineid: "00"). Instead, it and other traversals do not retraverse the line they came from and fail to find solutions.

vindennt commented 1 year ago

If the starting station is within the infinite loop, the infinite loop fails. Stations outside of the infinite loop will be fine.

(stationid, lineid)

// (1, 2) -5- (2, 2) -6- (3, 2) -3- (4, 2) -7- (13, 3) // (2, 2) -3- (11, 3) -5- (12, 3) -10- (13, 3)

starting from 3 wlil traverse to 13 to transfer to line 3, traverse to 2, transfers back onto line 2, but gets stuck in deadend at 1. Solution should have traversed back to station 3

vindennt commented 1 year ago

Fixed by deleting all of visited (except station you just visited) if you were at a transfer station. This allowed traversal to revisit every station in a directional manner