This is a Telegram bot that parses commands allowing the user to manipulate, store and load skylines.
To start using the bot, you will need to install the required Python libraries:
> pip3 install -r requirements.txtYou will also need a valid Telegram bot token, which has to be stored in a plain text file called token.txt in the same directory as the bot.py file.
To run the bot, simply execute:
> python3 bot.pyand you can start chatting!
Note: You need at least Python 3.6 because the program uses f-strings.
The bot understands seven commands, identified by a slash (/) at the start.
/startinitiates the conversation with the bot and greets the user./helpshows a list with all the available commands and a brief description of each one./authorshows the name and email of the author./lstshows a list of all the valid skyline identifiers in memory, with their area and height./cleanerases all skyline identifiers in memory./save idsaves the skyline with identifieridto disk./load idloads the skyline with identifieridfrom disk to memory.
The bot can also parse messages that allow the user to manipulate the skylines. These messages do not start with a slash (/). The following section will explain the grammar that these messages follow.
- The user can construct a skyline with a single building, by specifying the start x-coordinate, the height, and the end x-coordinate. An example would be
(1, 2, 3), where the building has height 2 and goes from the x-coordinates 1 to 3. - The user can construct a skyline with multiple buildings by entering a list with multiple single buildings. An example would be
[(1, 2, 3), (4, 5, 6)]. - The user can construct a skyline with many randomly generated buildings by specifying some parameters
{n, h, w, xmin, xmax}. An example would be{100, 20, 4, 1, 1000}. The meaning of the parameters is:n: the amount of buildingsh: the maximum height of each buildingw: the maximum width of each buildingxmin: the minimum x-coordinate of each buildingxmaxthe maximum x-coordinate of each building
- The union of two skylines is represented by
skyline1 + skyline2. - The intersection of two skylines is represented by
skyline1 * skyline2. - The reflection of a skyline is represented by the unary negation operator:
-skyline. - The right shift by
nunits of a skyline is represented byskyline + n. - The left shift by
nunits of a skyline is represented byskyline - n. - The replication
ntimes of a skyline is represented byskyline * n.
Any of the previous operations can be stored into a variable with an identifier as follows: a1 := (1, 2, 3). The identifiers can then be used in expressions. A valid identifier is a letter followed by zero or more digits or letters.
Note: Whitespace is always ignored in the parsing of the expressions.
Skylines are represented by a series of points (x, y) where the skyline changes its height. Note that the last point is always of the form (x, 0) because the heigth from that point on is zero. This allows for easy plotting, area calculation and height calculation. The implementation of the operations is also simplified by this structure.
There can be empty skylines, generated by the intersection of any two disjoint skylines. These are represented by an empty list.
The reflection operation can be achieved by simply traversing the list of points backward and setting to each point the y-coordinate of the next one, adding a zero to the end and adjusting the x-coordinates with a simple calculation.
The union and intersection of two skylines are calculated in linear time, and their implementations are simple, but prone to index errors and edge cases.
Shifts are very easy to implement, by adding or subtracting the given offset to the x-coordinate of each point, and replications are also easy, taking into account that the zero point at the end of the original list only has to be replicated once.
The most interesting operation is the construction of a skyline given a list of buildings, randomly generated or not. It is easy to come up with an O(n^2) algorithm by keeping a result skyline and repeatedly joining it with each building. To comply with the requirements, we have to do better, and O(n logn) is possible, using a variant of merge sort. We start with a list of skylines which have one building each, and repeatedly divide the list into halves until the parts have one element. Then, we can just join the halves using the O(n) join function we previously had. By a similar argument to the one used for merge sort, this produces a tree of height log n, and thus the whole operation is O(n logn).
The parsing of expressions is implemented with the antlr4 library for Python.
The basis of the grammar is base_expr, which can either be an expr or an identifier, the symbol := and an expr.
An expr is defined to match a constructor, an identifier or any of the operations that the user can do.
Persistent storage is achieved with the pickle module in the Python standard library, which allows the saving and loading of arbitrary objects into binary files.
The code for this program has been formatted with the black module. The settings used were the default ones except for line length, which was set to unlimited.
The grammar doesn't accept expressions of the type IDENTIFIER MINUS NUMBER, without spaces. That is, "a-2" doesn't behave correctly, but "a - 2" and "a+2" do.