-
Notifications
You must be signed in to change notification settings - Fork 0
Design
This section differs from the original design as we will not be writing any data to a file.
Previously we were going to write the first world to a file.
Now, ALL interprocess communication is done through standard input/output.
The harness will be used to generate initial configurations. It will have functionality to generate our input data from the existing HTML configurations. It will accept the inputs:
- seed (coordinates of living cells)
Height and width are determined by text inputs. The initial configuration is done by clicking on TD elements contained within a TABLE element. The speed of generation is determined by a text input.
When the play button is pressed, the current configuration of the cells will be encoded using javascript into our defined input format. It will from there be sent using POST data. The harness then sends this information using standard input to the ACL2 component.
The ACL2 component will return the next generation in the form of HTML to be displayed within the TABLE element.
This process is repeated at the user-defined interval of time.
Features should be provided so users can:
- Start the "game"
- Stop the "game"
- Define frames per second (speed of generation advancement)
- Define the size of the grid.
Originally height and width were user-provided.
Now, we determine height and width from input data, assuming it is correctly described.
Using standard input we will provide the first generation of cells, as provided by the user in the web interface.
Living cells will be represented by an x. Dead cells will be represented by a space character.
Example input data:
x
x
xxx
ACL2 accepts input and builds an AVL tree based on the previous generation. Using this AVL tree for random access, we will apply the rules of Conway's Game of Life to the living cells and populate a new AVL tree representing the next generation. This new AVL tree will then be used to serve the STDOUT data.
-
(main state) - Reads input, invokes tree rebuilding, and writes output.
- state (ACL2 state) : state of the ACL2 world
-
(build-next-generation width height last-gen next-gen) - Builds the output.
- width (integer) : defines width of grid
- height (integer) : defines height of grid
- last-gen (avl tree) : avl tree representing the living cells in the last generation
- next-gen (list of character lists) : avl tree of the living cells for the next generation
-
(build-next-generation-row width height y last-gen next-gen) - Builds a single output row for row index y.
- width (integer) : defines width of grid
- height (integer) : defines height of grid
- y (integer) : current position in row
- last-gen (avl tree) : avl tree representing the living cells in the last generation
- next-gen (list of character lists) : avl tree of the living cells for the next generation
-
(build-next-generation-cell width height x y last-gen next-gen) - Determines whether a single output cell is live and adds it to the output tree if it is
- width (integer) : defines width of grid
- height (integer) : defines height of grid
- y (integer) : current position in row
- last-gen (avl tree) : avl tree representing the living cells in the last generation
- next-gen (list of character lists) : avl tree of the living cells for the next generation
-
(num-live-neighbors n width height x y last-gen) - Returns the number of live neighbors of the cell in the input.
- n (integer) [0-9] : which cell around the checked cell we are at
- width (integer) : defines width of grid
- height (integer) : defines height of grid
- y (integer) : current position in row
- last-gen (avl-tree) : an avl-tree with all living cells from the previous generation
-
(stdin->lines state) - reads input from standard input, like file->lines
- state (ACL2 state) : state of the ACL2 world
-
(string-list->stdout state) - writes output to standard output, like string-list->file
- state (ACL2 state) : state of the ACL2 world
-
(input-lines->avl-tree x y width input-lines last-gen) - creates an AVL tree from the input data
- x (integer) : x position to check
- y (integer) : y position to check
- width (integer) : width of world
- input-lines (list of character lists) : a long list of long character lists
- last-gen (avl-tree) : an avl tree passed recursively as it is populated with living cells
Added width variable, better described functionality
- (get-avl-key x y width) - returns the AVL key for position (x, y) by performing the simple calculation of (y * width) + x
- x (integer) : x-position
- y (integer) : y-position
- width (integer) : width of entire tree
All of the following line estimates are based on the PROBE data generated by our group tSumm report.
- Main : Large I/O based function. Estimate: 19
- build-next-generation: Huge non-I/O. Estimate: 13
- build-next-generation-row: Medium non-I/O Estimate: 6
- build-next-generation-cell: Large non-I/O Estimate: 9
- num-live-neighbors: Huge non-I/O. Estimate: 13
- stdin->lines: Medium I/O. Estimate: 16
- string-list->stdout: Large I/O. Estimate: 19
- By using standard input/output we are able to run multiple instances of the program without interfering with other players. This is more appropriate for an HTML-based game as it will most commonly be served over the world wide web.
-
Usage of the AVL-Tree allows us to randomly access the tree quicker than if we were to use a list. Using a list would surely require quadratic or greater time within our implementation.
-
Using a list would be so taxing that we never once approached the problem in this manner.
-
By using python bottle, we were able to reduce the time required to create handling for dynamic POST data entry. While it is not universally compilable as Java is, it is a script and python is available across all 3 major operating systems.
-
Furthermore, the requirements only requested it to be runnable within a Windows environment. By packaging all necessary python components (similarly to building an ACL2 executable) we were still able to provide a one-click solution to our implementation.