A Telegram bot that simplifies finding train timetables in Montenegro.
Original timetable - https://zpcg.me/search
The site does not have a mobile version, is hard to navigate and can't show intersecting routes. This bot is an attempt to solve those issues.
/start
is the first message the bot receives after the user starts the bot. It returns a quick,
laconic instructions of how to use the bot.
Returns the message in different languages depending on the users telegram settings. If the user's language is not supported, it uses English for communication.
Any message without a /
is parsed as a timetable request.
Let's introduce two definitions
{delimiter symbol}
- one of !@#$%^&*()_+-=[]{}|;':",./<>? chars
{departure/arrival station name}
- any number of Latin chars. It may contain any other chars other than delimiter
symbols, but they will be ignored
The request is expected to be in following formats:
{departure station name} {delimiter symbol} {arrival station name}
or
{departure station name} {delimiter symbol} {any number of any chars} {delimiter symbol} {arrival station name}
Messages in the expected format are replied with a timetable. For any other format, there will be an error.
The default error is defined in /internal/service/render/{language_code}.go
files.
If the input message is in the right format but contains a station name from the black list defined in
/internal/service/blacklist
- it is responded with a custom warning usually telling the user
that the station does not exist.
Response with a route without an intersection is in the following format:
Podgorica > Danilovgrad
[7100](https://zpcg.me/details?timetable=201#tab3) 08:00 > 08:29
[7102](https://zpcg.me/details?timetable=202#tab3) 12:50 > 13:19
[7104](https://zpcg.me/details?timetable=160#tab3) 15:35 > 16:04
[7106](https://zpcg.me/details?timetable=204#tab3) 18:30 > 18:59
[7108](https://zpcg.me/details?timetable=203#tab3) 21:45 > 22:14
{inline button with a link to the route on zpcg.me}
Response with a route with an intersection is in the following format:
Virpazar > Podgorica > Nikšić
[6100](https://zpcg.me/details?timetable=102#tab3) 05:43 > 06:19
[6150](https://zpcg.me/details?timetable=217#tab3) 06:55 > 07:26
[7100](https://zpcg.me/details?timetable=201#tab3) 08:00 > 09:03
[6152](https://zpcg.me/details?timetable=221#tab3) 09:51 > 10:22
[6154](https://zpcg.me/details?timetable=222#tab3) 12:08 > 12:39
[7102](https://zpcg.me/details?timetable=202#tab3) 12:50 > 13:53
[6156](https://zpcg.me/details?timetable=223#tab3) 14:41 > 15:12
[7104](https://zpcg.me/details?timetable=160#tab3) 15:35 > 16:38
[6102](https://zpcg.me/details?timetable=103#tab3) 16:03 > 17:06
[6158](https://zpcg.me/details?timetable=224#tab3) 17:35 > 18:06
[7106](https://zpcg.me/details?timetable=204#tab3) 18:30 > 19:33
[6104](https://zpcg.me/details?timetable=205#tab3) 18:25 > 19:15
[7108](https://zpcg.me/details?timetable=203#tab3) 21:45 > 22:48
[6160](https://zpcg.me/details?timetable=225#tab3) 21:29 > 22:00
{inline button with a link to the first route on zpcg.me} {inline button with a link to the second route on zpcg.me}
The format is the same as for the route without intersections but:
The error message repeats to the user the format of the timetable request. Example:
Try again - two stations, separated by a comma. Just like that:
Podgorica, Niksic
The bot uses its own path finding algorithm. It does not use Dijkstra or any other ways to solve the problem.
It is built with some assumptions listed below.
Railway system of Montenegro consist of:
So the assumptions are:
This means, that it is completely enough to return only one of two types of routes for every possible input:
Conditions that may disrupt the assumptions include:
Possible improvements to the system might involve:
Extending the Podgorica - Belgrade branch to the Subotica station and beyond to Hungary, in light of Subotica being mentioned in the official timetable and the Subotica - Szeged rail line is now reopened. It may add new stations to the branch but not going to create a cycle. Some kind of fork might be added which mean there might be another preferred intersection change for trains going from Hungary to Serbia, but it is obviously outside the context of the Montenegro timetable bot.
The same applies to the possible renovation of the Podgorica - Tuzi - Durrës/Tirane branch and an extension of the Podgorica - Niksic line to the Sarajevo.
It means we can easily rely on the assumptions listed above in order to optimize the path finding algorithm.
Preparation: needed data structures
StationIdToTrainIdSetMap: map: station -> set of train ids
This field is a map where each key is a StationId and each value is a set of TrainId. This map allows the PathFinder to know which trains depart from any given station. This information is essential for identifying possible routes when calculating the paths between two stations.
Train ids are unique and for every station exist a set of trains that passes the station. Consequently, it is possible to fill this structure correctly.
TrainIdToStationsMap: map: train id -> (set of stations -> {station name, arrival time, departure time})
This field is also a map. Each key is a TrainId and each value is a StationIdToStationMap that contains every station that the train stops at. This map is important to derive the sequence of stations that each train traverses along its route.
According to the assumptions, every train passes each station of its route only once. That makes possible to build a set of route stations with details about the arrival/departure time.
TransferStation: station id for the interchange station
This field represents a predefined station which serves as the only transfer point in case there are no direct paths available between two requested stations.
Check for Direct Path
Find a direct path/route from station A (aStation) to station B (bStation). "Direct" here means there are trains which go from station A to station B without the need for a transfer.
It is done by first checking which trains serve both the station A and station B using the predefined StationIdToTrainIdSetMap:
trainIdSetA = p.stationIdToTrainIdSetMap[aStation]
trainIdSetB = p.stationIdToTrainIdSetMap[bStation]
// get intersection of maps of the trains
possibleRoutes := utils.Intersection(trainIdSetA, trainIdSetB)
If the set intersection is not empty - the directs paths are found.
The final result is defined by validating if the train/s found have a schedule such that it/they depart/s from station A and arrive at station B consecutively. This information might be found using prepared TrainIdToStationsMap. If the condition is met, then this direct path is valid and is added to the returning paths.
We assume that the direct paths are the preferred ones, so there is no need to look for another paths.
The problem is solved.
Check for Indirect Path
If no direct path is found, paths with a transfer needed to be found. This is the step where the predefined Transfer Station is being used.
In this step the algorithm essentially performs a two-part journey - first it finds the paths from station A to the Transfer Station, then it finds the paths from the Transfer Station to station B the same way as it was done in the previous step. These possible routes are merged together in a specific manner, in case of overlapping schedules, the route which arrives at the transfer station before the departure to station B is preferred.
We assume that the path through the Transfer station always exist and is the most suitable.
Returning Paths
Finally return the paths found and a bool flag indicating whether the found routes are direct or not.
In the first step, the algorithm iterates over each train in a set which contains the intersection of trains at station A and station B. The intersection operation would have a time complexity of O(n), where n is the number of elements in the larger train set. Then, for every train, it checks the conditions and possibly appends it to the paths. Adding all of this up, the time complexity of this operation can be considered to be O(n).
In the second one, the algorithm repeats step one twice, so that would be 2*O(n) ~ O(n). Then it iterates through the lists of direct paths from station A to the transfer station and from the transfer station to station B, merging these paths as it goes. This merger can, in the worst case, have a time complexity of O(n + m), where n and m are the lengths of the two lists. Adding these together, the overall time complexity could be considered to be O(n + m) where n is the number of elements in the larger set and m is the total number of paths.
The space complexity of the algorithm comes primarily from the storage of the 'paths'. In the worst case, it could potentially store each direct path from the source station to the destination, as well as each path via the transfer station. This gives a worst-case space complexity of O(n + m), where n and m are the numbers of direct and transfer paths, respectively.
Please note: In these analyses, m and n are not necessarily numbers of stations or trains but rather the number of paths and matches the algorithm needs to keep track of. Thus, the actual time or space this algorithm takes might be different based on the specific graph structure of the train network.
Also, the memory requirement of the StationIdToTrainIdSetMap and TrainIdToStationsMap structures scale linearly with the overall increase in the number of stations and trains. The exact growth can be viewed as O(n) and O(m) respectively, where 'n' is the number of train services and 'm' is the number of stations.
Therefore, basically, the algorithm has a linear time and space complexity.
Exporter prepares the needed data structures for finding routes. It parses the official site
and saves structures as a file in .gob format using "encoding/gob"
golang lib.
The file is embedded right into the executable using "embed"
lib and is loaded to the memory at a startup.
The bot waits for HTTP requests from Telegram, handles and sends messages to users. It runs on the Google Cloud Run platform, invokes on every request (i.e. is not running all time long) which makes it cost-effective.
It is running on the smallest cpu and memory available: 1 vCPU and 128Mb RAM. And uses usually no more than 15% of this memory.
The life cycle is simple:
The request handling time (~200ms) is the only billable time in this lifecycle. The overall cost of the bot right now is about 0 ~ 0.13 euros per month. (TODO: add metrics and count num of requests/month)
The bot is almost free to maintain and as cost-effective as possible.
This project might be improved in several ways in order to meet the requirements listed above.
"I prefer clicking buttons over a raw keyboard input" - this is a common feedback I get from users. Implementing keyboard is a great way to improve UX. But how can the implementation still be stateless and fast enough then?
Force reply feature is going to be helpful for that.
For each timetable message there has to be a way to update it without sending additional input. It be implemented using inline keyboards.
Additional info like price, route stations, ticket offices working hours, etc. must be provided. But it is impossible to print in one small message. It might be done using WebApps feature and GitHub Pages as a host.
Telegram bots API is powerful, but the Telegram itself is mostly used by a russian speaking community. In Montenegro Viber is widely used and WhatsApp is the best option for any other tourists or foreigners. It is a good idea to port this solution to other platforms in order to reach the audience.
ZPCG has a Viber chat to get info about the timetable. But it is replies to messages only on working days from 07:00 to 15:00, probably because there is a person behind the scenes that is answering all the questions. I think it is a good idea to provide the same service but working fast and 24/7.
Telegram allows developers to use keyboards. However, it is cached in the users device telegram instance. Even though if it may no longer be supported, the users might still attempt to use an old cached version of the keyboard. As a remedy, the keyboard is deleted with the first message received from the new version. For an efficient cleanup, consider clearing the cached keyboard with a broadcast update message.
It might be a good idea to clear the cached keyboard with a broadcast update message. It might be also a good idea to do so after the new keyboard will be done in order to send only one message instead of two.
Some users are not familiar with the transportation in Montenegro: do not know where the railways stations are, which cities have stations, etc. It leads users to blindly search for the stations that do not exist. There are some examples of the inputs:
I think there should be some kind of /help
command to return some general information
about the bot, Montenegro and the transport.
Previous version of the bot was completely static, made in an hour using a free telegram bot constructor with hardcoded timetable. It was truly obvious that the timetable was not updated and might be (and actually was) outdated. So users have those trust issues now and the bot has to overcome this.
There has to be:
There has to be a warning about possible delays especially for routes with intersections, in summer and for the fast trains - they are usually late for several hours, unfortunately.