search

python-discord / sir-lancebot

A Discord bot started as a community project for Hacktoberfest 2018, later evolved to an introductory project for aspiring new developers starting out with open source development.
MIT License
240 stars 240 forks source link

Add random graph trivia questions #1495

Open jonathan-d-zhang opened 5 months ago

jonathan-d-zhang commented 5 months ago

Description

Created from discussion in #1491. Me:

A question I thought would be fun is generating a random directed graph and asking people to find the shortest path between two randomly selected nodes. Variations could be solving TSP, and so on. Would need to send images though, which would require some modifications to a lot of code.

@wookie184 :

The graph idea also sounds cool, though I think it would require a bit more discussion first - I think it would be good to open a separate issue for it. It could be worth looking into if there's a Python package or API that could handle converting a graph to an image so we don't need to worry about installing graphviz.

Reasoning

These questions would be fun and cool.

Proposed Implementation

  1. Add a dynamic_id question in the CS section
  2. Add question list as constant. Questions asked could be:
    • Find the shortest path between two nodes.
    • Find the longest path between two nodes.
    • Find a minimal spanning tree.
    • Solve TSP given a start node.
    • Simpler ones like "is this connected", "how many edges", "find a path from source to destination" Each of these would have an associated function for validating a given answer.
  3. Create a function to generate a Erdos-Renyi random graph suitable for each question. E.g., don't pick a disconnected graph for solving TSP. https://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93R%C3%A9nyi_model.
  4. Create function for generating image representing the graph.

Functionality exists to send images already, but it would need to be slightly modified, since the current code only supports sending via URLs read from the config.

The "proper" way to generate the images would be via graphviz. We would use pygraphviz to interface with a graphviz installed in the container. Would require modifying the Dockerfile to install graphviz.  

Additional Details

Performance

Should be fine: graph sizes will be small, furthermore we don't need to precompute answers for computationally hard questions, we only need to validate. p != np or something.

Alternative impls

These two should work, the LaTeX api we use supports tikz.

Would you like to implement this yourself?

wookie184 commented 5 months ago

Thanks for writing up a detailed issue. I think adding graphviz for this is fine, and is the best option here. Marked as approved, feel free to work on this.