Merge pull request #282 from python-discord/jb3/features/condorcet-count

Add Condorcet count endpoint

4 files changed, 207 insertions, 2 deletions

diff --git a/backend/__init__.py b/backend/__init__.py
index 67015d7..c2e1335 100644
--- a/backend/__init__.py
+++ b/backend/__init__.py
@@ -1,9 +1,12 @@
 import sentry_sdk
 from sentry_sdk.integrations.asgi import SentryAsgiMiddleware
 from starlette.applications import Starlette
+from starlette.exceptions import HTTPException
 from starlette.middleware import Middleware
 from starlette.middleware.authentication import AuthenticationMiddleware
 from starlette.middleware.cors import CORSMiddleware
+from starlette.requests import Request
+from starlette.responses import JSONResponse
 
 from backend import constants
 from backend.authentication import JWTAuthenticationBackend
@@ -47,5 +50,14 @@ middleware = [
     Middleware(ProtectedDocsMiddleware),
 ]
 
-app = Starlette(routes=create_route_map(), middleware=middleware)
+
+async def http_exception(_request: Request, exc: HTTPException) -> JSONResponse:  # noqa: RUF029
+    return JSONResponse({"detail": exc.detail}, status_code=exc.status_code)
+
+
+exception_handlers = {HTTPException: http_exception}
+
+app = Starlette(
+    routes=create_route_map(), middleware=middleware, exception_handlers=exception_handlers
+)
 api.register(app)
diff --git a/backend/routes/forms/condorcet.py b/backend/routes/forms/condorcet.py
new file mode 100644
index 0000000..902770b
--- /dev/null
+++ b/backend/routes/forms/condorcet.py
@@ -0,0 +1,104 @@
+"""Calculate the condorcet winner for a given question on a poll."""
+
+from condorcet import CondorcetEvaluator
+from pydantic import BaseModel
+from spectree import Response
+from starlette import exceptions
+from starlette.authentication import requires
+from starlette.requests import Request
+from starlette.responses import JSONResponse
+
+from backend import discord
+from backend.models import Form, FormResponse, Question
+from backend.route import Route
+from backend.validation import api
+
+
+class CondorcetResponse(BaseModel):
+    question: Question
+    winners: list[str]
+    rest_of_table: dict
+
+
+class InvalidCondorcetRequest(exceptions.HTTPException):
+    """The request for a condorcet calculation was invalid."""
+
+
+def reprocess_vote_object(vote: dict[str, int | None], number_options: int) -> dict[str, int]:
+    """Reprocess votes so all no-preference votes are re-ranked as last (equivalent in Condorcet)."""
+    vote_object = {}
+
+    for option, score in vote.items():
+        vote_object[option] = score or number_options
+
+    return vote_object
+
+
+class Condorcet(Route):
+    """Run a condorcet calculation on the given question on a form."""
+
+    name = "form_condorcet"
+    path = "/{form_id:str}/condorcet/{question_id:str}"
+
+    @requires(["authenticated"])
+    @api.validate(
+        resp=Response(HTTP_200=CondorcetResponse),
+        tags=["forms", "responses", "condorcet"],
+    )
+    async def get(self, request: Request) -> JSONResponse:
+        """
+        Run and return the condorcet winner for a poll.
+
+        Optionally takes a `?winners=` parameter specifying the number of winners to calculate.
+        """
+        form_id = request.path_params["form_id"]
+        question_id = request.path_params["question_id"]
+        num_winners = request.query_params.get("winners", "1")
+
+        try:
+            num_winners = int(num_winners)
+        except ValueError:
+            raise InvalidCondorcetRequest(detail="Invalid number of winners", status_code=400)
+
+        await discord.verify_response_access(form_id, request)
+
+        # We can assume we have a form now because verify_response_access
+        # checks for form existence.
+        form_data = Form(**(await request.state.db.forms.find_one({"_id": form_id})))
+
+        questions = [question for question in form_data.questions if question.id == question_id]
+
+        if len(questions) != 1:
+            raise InvalidCondorcetRequest(detail="Question not found", status_code=400)
+
+        question = questions[0]
+
+        if num_winners > len(question.data["options"]):
+            raise InvalidCondorcetRequest(
+                detail="Requested more winners than there are candidates", status_code=400
+            )
+
+        if question.type != "vote":
+            raise InvalidCondorcetRequest(
+                detail="Requested question is not a condorcet vote component", status_code=400
+            )
+
+        cursor = request.state.db.responses.find(
+            {"form_id": form_id},
+        )
+        responses = [FormResponse(**response) for response in await cursor.to_list(None)]
+
+        votes = [
+            reprocess_vote_object(response.response[question_id], len(question.data["options"]))
+            for response in responses
+        ]
+
+        evaluator = CondorcetEvaluator(candidates=question.data["options"], votes=votes)
+
+        winners, rest_of_table = evaluator.get_n_winners(num_winners)
+
+        return JSONResponse({
+            "question": question.dict(),
+            "winners": winners,
+            "rest_of_table": rest_of_table,
+        })
diff --git a/poetry.lock b/poetry.lock
index 6a3e2e0..508e518 100644
--- a/poetry.lock
+++ b/poetry.lock
@@ -68,6 +68,20 @@ files = [
 ]
 
 [[package]]
+name = "condorcet"
+version = "0.1.1"
+description = "Condorcet is a utility for evaluating votes using the condorcet method"
+optional = false
+python-versions = ">=3.8,<4.0"
+files = [
+    {file = "condorcet-0.1.1-py3-none-any.whl", hash = "sha256:8c69ebb2292f9fae51f8b3f740a1695f97560fbcc8a5f1d6d8bce91157d7fffc"},
+    {file = "condorcet-0.1.1.tar.gz", hash = "sha256:ba53f89ea2be76ba6fcb24bc381293b68a49bc25d2b8ca0d4b922f1b71b9c436"},
+]
+
+[package.dependencies]
+pytest-mock = ">=3.6.1,<4.0.0"
+
+[[package]]
 name = "deepmerge"
 version = "1.1.1"
 description = "a toolset to deeply merge python dictionaries."
@@ -255,6 +269,17 @@ files = [
 ]
 
 [[package]]
+name = "iniconfig"
+version = "2.0.0"
+description = "brain-dead simple config-ini parsing"
+optional = false
+python-versions = ">=3.7"
+files = [
+    {file = "iniconfig-2.0.0-py3-none-any.whl", hash = "sha256:b6a85871a79d2e3b22d2d1b94ac2824226a63c6b741c88f7ae975f18b6778374"},
+    {file = "iniconfig-2.0.0.tar.gz", hash = "sha256:2d91e135bf72d31a410b17c16da610a82cb55f6b0477d1a902134b24a455b8b3"},
+]
+
+[[package]]
 name = "motor"
 version = "3.5.0"
 description = "Non-blocking MongoDB driver for Tornado or asyncio"
@@ -300,6 +325,17 @@ files = [
 ]
 
 [[package]]
+name = "packaging"
+version = "24.1"
+description = "Core utilities for Python packages"
+optional = false
+python-versions = ">=3.8"
+files = [
+    {file = "packaging-24.1-py3-none-any.whl", hash = "sha256:5b8f2217dbdbd2f7f384c41c628544e6d52f2d0f53c6d0c3ea61aa5d1d7ff124"},
+    {file = "packaging-24.1.tar.gz", hash = "sha256:026ed72c8ed3fcce5bf8950572258698927fd1dbda10a5e981cdf0ac37f4f002"},
+]
+
+[[package]]
 name = "platformdirs"
 version = "4.2.2"
 description = "A small Python package for determining appropriate platform-specific dirs, e.g. a `user data dir`."
@@ -316,6 +352,21 @@ test = ["appdirs (==1.4.4)", "covdefaults (>=2.3)", "pytest (>=7.4.3)", "pytest-
 type = ["mypy (>=1.8)"]
 
 [[package]]
+name = "pluggy"
+version = "1.5.0"
+description = "plugin and hook calling mechanisms for python"
+optional = false
+python-versions = ">=3.8"
+files = [
+    {file = "pluggy-1.5.0-py3-none-any.whl", hash = "sha256:44e1ad92c8ca002de6377e165f3e0f1be63266ab4d554740532335b9d75ea669"},
+    {file = "pluggy-1.5.0.tar.gz", hash = "sha256:2cffa88e94fdc978c4c574f15f9e59b7f4201d439195c3715ca9e2486f1d0cf1"},
+]
+
+[package.extras]
+dev = ["pre-commit", "tox"]
+testing = ["pytest", "pytest-benchmark"]
+
+[[package]]
 name = "pre-commit"
 version = "3.7.1"
 description = "A framework for managing and maintaining multi-language pre-commit hooks."
@@ -482,6 +533,43 @@ test = ["pytest (>=7)"]
 zstd = ["zstandard"]
 
 [[package]]
+name = "pytest"
+version = "8.2.2"
+description = "pytest: simple powerful testing with Python"
+optional = false
+python-versions = ">=3.8"
+files = [
+    {file = "pytest-8.2.2-py3-none-any.whl", hash = "sha256:c434598117762e2bd304e526244f67bf66bbd7b5d6cf22138be51ff661980343"},
+    {file = "pytest-8.2.2.tar.gz", hash = "sha256:de4bb8104e201939ccdc688b27a89a7be2079b22e2bd2b07f806b6ba71117977"},
+]
+
+[package.dependencies]
+colorama = {version = "*", markers = "sys_platform == \"win32\""}
+iniconfig = "*"
+packaging = "*"
+pluggy = ">=1.5,<2.0"
+
+[package.extras]
+dev = ["argcomplete", "attrs (>=19.2)", "hypothesis (>=3.56)", "mock", "pygments (>=2.7.2)", "requests", "setuptools", "xmlschema"]
+
+[[package]]
+name = "pytest-mock"
+version = "3.14.0"
+description = "Thin-wrapper around the mock package for easier use with pytest"
+optional = false
+python-versions = ">=3.8"
+files = [
+    {file = "pytest-mock-3.14.0.tar.gz", hash = "sha256:2719255a1efeceadbc056d6bf3df3d1c5015530fb40cf347c0f9afac88410bd0"},
+    {file = "pytest_mock-3.14.0-py3-none-any.whl", hash = "sha256:0b72c38033392a5f4621342fe11e9219ac11ec9d375f8e2a0c164539e0d70f6f"},
+]
+
+[package.dependencies]
+pytest = ">=6.2.5"
+
+[package.extras]
+dev = ["pre-commit", "pytest-asyncio", "tox"]
+
+[[package]]
 name = "python-dotenv"
 version = "1.0.1"
 description = "Read key-value pairs from a .env file and set them as environment variables"
@@ -970,4 +1058,4 @@ files = [
 [metadata]
 lock-version = "2.0"
 python-versions = "^3.12"
-content-hash = "86bcd95d5baef49cc4c7efa6f791359af74e93f96f8f0ce9d8275c1e14e768ed"
+content-hash = "968392db8dc6b1835b0ed3a09234b4e4245263c7cb1ee4310294411f664b721c"
diff --git a/pyproject.toml b/pyproject.toml
index edea8a7..af8c13d 100644
--- a/pyproject.toml
+++ b/pyproject.toml
@@ -18,6 +18,7 @@ pydantic = "^1.10.17"
 spectree = "^1.2.10"
 deepmerge = "^1.1.1"
 sentry-sdk = "^2.7.1"
+condorcet = "^0.1.1"
 
 [tool.poetry.group.dev.dependencies]
 ruff = "^0.5.1"