tran-antoine / algo-companion Goto Github PK

Reminder for myself to fix this: when we go from a scene to the other, we must disable the key events associated to the previous scene, otherwise we get clashes

Now that we've written most of the necessary tools (DCAssembler, Serdes, SimulationListener, python templates), we need to think about how to coordinate those parts to make them work together. I suggest a Simulator class which does the following:

• Uses DCAssembler to create a script containing the divide, combine and base_case functions
• Move this script, as well as a copy of all necessary python code (simulator.py, dc_template.py, serde.py, matrix.py if necessary, etc) to the bin folder. The reason I think we should do this is because python imports with files from different folders are a huge mess to deal with, and we're talking about only a few files that aren't particularly long, so this doesn't really cause a performance issue.
• Run simulator.py and have a SimulationListener object ready to listen
• Transfer the result to the outside under the form of a Future[List[SimulationData]]

I started writing a simulator file (to then realize that I wasn't supposed to be doing it at the time) which looked like this:

import sys
import socket
from serde import *

def get_serde(type_id):
    if type_id == "ListType": return ListSerde
    if type_id == "MatrixType": return MatrixSerde
    if type_id == "BinaryTreeType": return BinaryTreeSerde
    if type_id == "HeapType": return HeapSerde

def main():

    input_serde = get_serde(sys.argv[0])


    sender = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
    port = int(sys.argv[1])

    sender.bind(("localhost", port))

    for (i, arg) in enumerate(sys.argv[2:]):
        run(arg, sender, DivideSerde, CombineSerde, input_serde, i)


if __name__ == '__main__':
    main()

so we can do something similar. Basically it's the script that the main program will execute, and that script will itself call the run function.

One side note: I think it would be wise to move dc_template out of the resources folder, because if we now consider that divide, combine and base_case are external functions from a different file and that they will be imported by dc_template, it is 100% valid python code. The other ones (base-template, etc) should remain resources I think.

After a quick discussion with some developers, we concluded that sending simulation results through the local network via sockets was the way to go. So we need some protocol for sending and receiving messages.

I figured it'd be useful to start off by listing the questions we need to address before getting started.

What are the possible "inputs" of the problem ? Is it general enough to only work with lists of numbers? Should we do something more abstract that gives more freedom?

I personally think that lists of numbers are good enough for now, we'll see later if we need more flexibility

How does the user provide the specs of their algorithm?

The idea I had was to have multiple input boxes:

• The recurrence relation for the total cost (so we can use the master theorem to instantly compute the complexity)
• A minimalist python script with global variables available (input and size basically) that specifies the division procedure. Maybe we can have "default" settings such as "evenly dividing in N pieces", where N could be infered from the recurrence relation
• A minimalist python script with global variables available (input1, input2, ..., size) that specifies the combining procedure. Default could be concatenation

What kind of animation would be useful?

I think it would be nice to show the base input, then divide it until we reach the base case, solve the best case then regroup the pieces. It's all a D&C algorithm always does as far as I know, I don't know if there are additional features that would be interesting to add. Should we go for a step-by-step animation where the user decides when to go to the next step? Should the user be able to interact in any way to maybe modify the input, correct a part of the animation on the fly, etc?
Maybe a cool feature would be to allow the user to "mark" steps in the combining procedure, so the animation could highlight those steps. For instance, if the user writes a merge-sort, they could do something like mark(chosen_number) (where chosen_number is the current smallest number out of the two lists) and that would highlight that number on the animation. So calling mark would both pause the animation and highlight a certain number

Does initial input need to be specified?

I think it would be nice to be able to choose between "random numbers" or a specific list. It can be useful for the user to test specific inputs so allowing them to enter them is important, but it's also practical to be able to run it with multiple random inputs to see if it works

Can we add a feature to instantly test if the algorithm ran perfectly?

We could maybe have an input box that defines a verifier, an algorithmic procedure that checks that the output is correct, that would enable fast forwarding the visualization in some cases, which could make the user save some time if their algorithm is correct

Now that we've added the messages for the script to communicate with the main program, we need to write the code that listens to them.

I think it is safe to assume that all messages will be sent practically instanteanously, so there should be no need to close and reopen the socket between every message. I don't think it is particularly useful to have a listening socket launched at the beginning of the program, because since the script launching procedure is done locally, we can open a socket at that moment.

So the way I'm going to do it is the following:

• Once the script is ready to be launched, a socket will be opened.
• The script will be executed either once (in case of a simulation) or multiple times (in case of a verification). We need this for verification too because once an input fails, the user will most likely want to simulate it, so we may as well already have the simulation data ready (and not just the information that the input failed)
• Once the socket receives as many Done messages as it received Register messages, it will close itself.

Whenever an input is received by the socket, the latter will deserialize it and store it somewhere in the program.

The verification procedure will be implemented later (it isn't really the priority for now), but at least we'll have an architecture that can support it easily in the future.