As computer science students, graphs are one of the most interesting problems we've encountered. The MRT is a well-connected graph, and as daily MRT commuters- we're always interested in the shortest path. But faced with nothing better to do, we asked ourselves, how about the longest possible path?

What it does

Finds the shortest and longest simple path (by number of stations) between any 2 Singapore MRT stations, providing some map 'visualisation'.

How we built it

We built the backend and scraped data from useless apis(??) ( with python using Flask and beautifulSoup4.

For the frontend, we used React and used Figma to handtrace the whole MRT map into an SVG that we can encode into the website.

Challenges we ran into

Request timeout issues faced with Heroku made it impossible for us to host the app in the short time given (this problem is NP hard).

Accomplishments that we're proud of

Solving an NP hard problem (-ish?).

What we learned

We found out what NP-hard REALLY meant by the end of the hackathon. Moreover, this meant that hosting our app was a whole other headache.

What's next for Stupid MRT

Spend ~20 days (1 pair takes about 3 minutes, with 170+++C2 combinations = sad) to run the algorithm on all possible combinations and see which route emerges on top and cache it for very social good.

Share this project: