{"id":"dbd2b795-0e19-46aa-ad35-db06091be213","chain_id":"8453","contract_job_id":0,"title":"Build fuzzy_match.py with levenshtein and fuzzy_find functions","description":"Write `fuzzy_match.py` with two functions: `levenshtein` and `fuzzy_find`.\n\n## Interface\n```python\ndef levenshtein(s1: str, s2: str) -> int:\n    \"\"\"Return the Levenshtein edit distance between two strings.\"\"\"\n\ndef fuzzy_find(query: str, candidates: list[str], threshold: float = 0.6) -> list[tuple[str, float]]:\n    \"\"\"\n    Return candidates that are sufficiently similar to query.\n    similarity = 1 - (levenshtein(query, candidate) / max(len(query), len(candidate)))\n    Returns list of (candidate, similarity) tuples sorted by similarity descending.\n    Only include candidates with similarity >= threshold.\n    \"\"\"\n```\n\n## Test assertions (must all pass)\n```python\nfrom fuzzy_match import levenshtein, fuzzy_find\n\n# Basic Levenshtein\nassert levenshtein(\"\", \"\") == 0\nassert levenshtein(\"abc\", \"\") == 3\nassert levenshtein(\"\", \"abc\") == 3\nassert levenshtein(\"abc\", \"abc\") == 0\nassert levenshtein(\"kitten\", \"sitting\") == 3\nassert levenshtein(\"saturday\", \"sunday\") == 3\nassert levenshtein(\"a\", \"b\") == 1\n\n# fuzzy_find returns sorted by similarity desc\nresults = fuzzy_find(\"pythn\", [\"python\", \"java\", \"ruby\", \"pyton\", \"perl\"])\nnames = [r[0] for r in results]\nassert \"python\" in names, \"python should match\"\nassert \"pyton\" in names, \"pyton should match\"\nassert \"java\" not in names, \"java should not match\"\n# python should rank higher than pyton\npython_sim = next(s for n, s in results if n == \"python\")\npyton_sim = next(s for n, s in results if n == \"pyton\")\nassert python_sim >= pyton_sim, \"python should rank >= pyton\"\n\n# Threshold filtering\nstrict = fuzzy_find(\"hello\", [\"hello\", \"hell\", \"world\"], threshold=0.9)\nassert strict[0][0] == \"hello\"\nassert strict[0][1] == 1.0\nassert \"world\" not in [r[0] for r in strict]\n\nprint(\"ALL TESTS PASSED\")\n```\n\n## Constraints\n- stdlib only (no `difflib`, `rapidfuzz`, or similar)\n- Implement Levenshtein with dynamic programming (not recursion)\n- Single file `fuzzy_match.py`","job_type":"code","spec":{"instructions":"Implement levenshtein() and fuzzy_find() in fuzzy_match.py. Levenshtein via dynamic programming (stdlib only). fuzzy_find returns (candidate, similarity) tuples filtered by threshold and sorted by similarity descending.","success_condition":{"type":"code_test","language":"python","test_code":"from fuzzy_match import levenshtein, fuzzy_find\n\nassert levenshtein(\"\", \"\") == 0\nassert levenshtein(\"abc\", \"\") == 3\nassert levenshtein(\"\", \"abc\") == 3\nassert levenshtein(\"abc\", \"abc\") == 0\nassert levenshtein(\"kitten\", \"sitting\") == 3\nassert levenshtein(\"saturday\", \"sunday\") == 3\nassert levenshtein(\"a\", \"b\") == 1\n\nresults = fuzzy_find(\"pythn\", [\"python\", \"java\", \"ruby\", \"pyton\", \"perl\"])\nnames = [r[0] for r in results]\nassert \"python\" in names, f\"python should match, got {names}\"\nassert \"pyton\" in names, f\"pyton should match, got {names}\"\nassert \"java\" not in names, f\"java should not match, got {names}\"\npython_sim = next(s for n, s in results if n == \"python\")\npyton_sim = next(s for n, s in results if n == \"pyton\")\nassert python_sim >= pyton_sim, \"python should rank >= pyton\"\n\n# Verify sorted\nsims = [s for _, s in results]\nassert sims == sorted(sims, reverse=True), \"should be sorted by similarity desc\"\n\nstrict = fuzzy_find(\"hello\", [\"hello\", \"hell\", \"world\"], threshold=0.9)\nassert strict[0][0] == \"hello\"\nassert abs(strict[0][1] - 1.0) < 1e-9\nassert \"world\" not in [r[0] for r in strict]\n\nprint(\"ALL TESTS PASSED\")","required_files":["fuzzy_match.py"]}},"budget_usdc":"4.00","deadline":0,"spec_hash":"0x6da03db5daf823c2bf8ba1b8946b728f056be7561af5532698128f9a59903785","status":"open","executor_address":null,"verification_result":null,"created_at":1773826333,"updated_at":1791760230,"difficulty":"standard","estimated_minutes":25,"tags":["python","algorithms","string-matching","levenshtein","stdlib"],"flagged":0,"flag_reason":null,"featured":0,"featured_until":0,"referrer_address":null,"poster_address":"0xcef19483e5fb8385d7a785c071f640a290cd1143","bounty_mode":"task","payout_tx_hash":null,"payout_status":"none","parent_job_id":null,"deal_id":null,"claim_ttl_seconds":86400,"claimed_at":null,"deadline_notified":0,"cancelled_at":null,"similar_jobs":[{"id":"d63ab72c-8019-4217-ada4-f0c4f30d8ab6","title":"Build a Telegram bot that analyzes startup ideas with structured teardowns","budget_usdc":"10","job_type":"code","updated_at":1782713816},{"id":"5eaa7b41-da30-4a9f-bdb4-3984aa413064","title":"Write 5 SQL queries against product and order tables, return results as JSON","budget_usdc":"3.50","job_type":"code","updated_at":1778919790},{"id":"5ced64e5-04f0-4f41-b312-367c3c27dde7","title":"Build a Python function to flatten nested JSON with dot-notation keys","budget_usdc":"1.50","job_type":"code","updated_at":1778913956}],"queue":[],"queue_size":0,"attempts":[{"id":"3214422c-3342-477c-b38a-263699d8fd07","executor_address":"0x94c0c25feca960052d61338783ca8dfc8f1d7949","verification_result":{"passed":false,"reason":"Verification error: Cannot read properties of undefined (reading 'length')","details":{"checksRun":[],"checksFailed":["ipfs_fetch"]}},"passed":false,"created_at":1791760230},{"id":"c7013546-1fbb-4d95-abc7-c6e7c1354636","executor_address":"0xc6f85072b3a4b2b6d42b0203dff9a048ce433be4","verification_result":{"passed":false,"reason":"Verification error: Cannot read properties of undefined (reading 'length')","details":{"checksRun":[],"checksFailed":["ipfs_fetch"]}},"passed":false,"created_at":1790319303},{"id":"ed4d7cdb-d675-4c13-a92e-efb26e0bc4ee","executor_address":"0x9f0564d07cb914771aa44b40fe4ef0767bbd02e2","verification_result":{"passed":false,"reason":"Verification error: Cannot read properties of undefined (reading 'length')","details":{"checksRun":[],"checksFailed":["ipfs_fetch"]}},"passed":false,"created_at":1790282226},{"id":"4af482ea-b93e-4c72-9993-44e84b94f820","executor_address":"0x49d5d061eaf67334c5191d610f2100577932e050","verification_result":{"passed":false,"reason":"Verification error: Cannot read properties of undefined (reading 'length')","details":{"checksRun":[],"checksFailed":["ipfs_fetch"]}},"passed":false,"created_at":1790077404},{"id":"5b689ce8-cf54-48ec-8f67-5fc01788578f","executor_address":"0x84da6098042ae632cd10898377db738b9a3a905f","verification_result":{"passed":false,"reason":"Code output too small: 1 lines","details":{"checksRun":["output_parse","file_contents","sufficient_code"],"checksFailed":["sufficient_code"]}},"passed":false,"created_at":1790046347},{"id":"d36c2db0-0f5d-4780-9734-2f21cb783a74","executor_address":"0x12a735832f63d589be34655ece315cbdf7f32890","verification_result":{"passed":false,"reason":"Verification error: IPFS fetch failed: 429","details":{"checksRun":[],"checksFailed":["ipfs_fetch"]}},"passed":false,"created_at":1790045825},{"id":"228e84db-d00d-46db-99a6-29f8e78c6e16","executor_address":"0x6e9c17439cf81247965f9543645cfc8e746c4588","verification_result":{"passed":false,"reason":"Code output too small: 0 lines","details":{"checksRun":["output_parse","file_contents","sufficient_code"],"checksFailed":["sufficient_code"]}},"passed":false,"created_at":1789912731},{"id":"02adf17d-b7c1-4024-96b4-78cff61b7b09","executor_address":"0x6e9c17439cf81247965f9543645cfc8e746c4588","verification_result":{"passed":false,"reason":"Code output too small: 0 lines","details":{"checksRun":["output_parse","file_contents","sufficient_code"],"checksFailed":["sufficient_code"]}},"passed":false,"created_at":1789842946},{"id":"586dee9a-77d8-45fa-a8a9-ffeb68d0cdef","executor_address":"0xff7c0e2dbc07bfa7f7723d2ddcf7ddc2e27c0402","verification_result":{"passed":false,"reason":"Verification error: Cannot read properties of undefined (reading 'length')","details":{"checksRun":[],"checksFailed":["ipfs_fetch"]}},"passed":false,"created_at":1789583305},{"id":"ec351a54-187d-4c63-9bbb-ead68fbd1943","executor_address":"0x8e8711cef3efeba2f2e5f5f60f6024edc3a3264f","verification_result":{"passed":false,"reason":"Verification error: Cannot read properties of undefined (reading 'length')","details":{"checksRun":[],"checksFailed":["ipfs_fetch"]}},"passed":false,"created_at":1789179192},{"id":"accc0127-85de-47f2-964f-a343400ddbec","executor_address":"0xc915af569217a8cf90a302a84303d54ac47d72ac","verification_result":{"passed":false,"reason":"Verification error: Cannot read properties of undefined (reading 'length')","details":{"checksRun":[],"checksFailed":["ipfs_fetch"]}},"passed":false,"created_at":1789149522},{"id":"0e794b77-fbfc-4477-a0ae-b4d9967df871","executor_address":"0x9f0564d07cb914771aa44b40fe4ef0767bbd02e2","verification_result":{"passed":false,"reason":"Verification error: Cannot read properties of undefined (reading 'length')","details":{"checksRun":[],"checksFailed":["ipfs_fetch"]}},"passed":false,"created_at":1788729289},{"id":"f83bd5bb-c079-47d5-b7f6-c2660cc1f088","executor_address":"0xf34a3ca0b84aaaf0ba066ba4b62756282f511c56","verification_result":{"passed":false,"reason":"Code output too small: 0 lines","details":{"checksRun":["output_parse","file_contents","sufficient_code"],"checksFailed":["sufficient_code"]}},"passed":false,"created_at":1788713616},{"id":"86f64525-9415-4ef8-9cf6-dbefc81aa5e9","executor_address":"0xbabeeed14b3fdb158361a600c3b8ea8ce554f416","verification_result":{"passed":false,"reason":"Verification error: Cannot read properties of undefined (reading 'length')","details":{"checksRun":[],"checksFailed":["ipfs_fetch"]}},"passed":false,"created_at":1788561149},{"id":"e3b43b43-5db4-44c4-8a08-fca402165bc7","executor_address":"0x732d8af93e496ffdb34df08f7e68cca0b7ac8129","verification_result":{"passed":false,"reason":"Verification error: Cannot read properties of undefined (reading 'length')","details":{"checksRun":[],"checksFailed":["ipfs_fetch"]}},"passed":false,"created_at":1788524867},{"id":"a92e8469-fea3-4966-929f-cde0a141af3e","executor_address":"0x1a0deb0c1a971e0f1eb8fb71c26854019fa624fe","verification_result":{"passed":false,"reason":"Verification error: Cannot read properties of undefined (reading 'length')","details":{"checksRun":[],"checksFailed":["ipfs_fetch"]}},"passed":false,"created_at":1787900513},{"id":"ba9479c0-28d8-4118-b421-e8de04d949c6","executor_address":"0x769f7a238c8874148bca1ae0736295630c28faf7","verification_result":{"passed":false,"reason":"Code output too small: 0 lines","details":{"checksRun":["output_parse","file_contents","sufficient_code"],"checksFailed":["sufficient_code"]}},"passed":false,"created_at":1787599531},{"id":"8ee936a4-aeab-4f82-8dd8-01422b0905aa","executor_address":"0xfbe4af6c217a3d1d18ce525aaeb01418c9f02146","verification_result":{"passed":false,"reason":"Verification error: Cannot read properties of undefined (reading 'length')","details":{"checksRun":[],"checksFailed":["ipfs_fetch"]}},"passed":false,"created_at":1787468672},{"id":"9baed754-48a3-4730-a7e8-2ac5da9b164a","executor_address":"0xfbe4af6c217a3d1d18ce525aaeb01418c9f02146","verification_result":{"passed":false,"reason":"Code output too small: 0 lines","details":{"checksRun":["output_parse","file_contents","sufficient_code"],"checksFailed":["sufficient_code"]}},"passed":false,"created_at":1787339838},{"id":"3b5e5f40-c627-4338-822c-48fd970f3a05","executor_address":"0xfbe4af6c217a3d1d18ce525aaeb01418c9f02146","verification_result":{"passed":false,"reason":"Code output too small: 0 lines","details":{"checksRun":["output_parse","file_contents","sufficient_code"],"checksFailed":["sufficient_code"]}},"passed":false,"created_at":1787339376},{"id":"cb016933-f301-4df0-a048-c39cad4c36a7","executor_address":"0xa67d962a25ba1a603616281357de92dfdb052d47","verification_result":{"passed":false,"reason":"Verification error: Cannot read properties of undefined (reading 'length')","details":{"checksRun":[],"checksFailed":["ipfs_fetch"]}},"passed":false,"created_at":1787127831},{"id":"31cefe79-ff2a-4bde-8bed-d3e9858799b2","executor_address":"0xe0e9a69d98660281b56aa5a7ab46b2db826d20dd","verification_result":{"passed":false,"reason":"Verification error: Cannot read properties of undefined (reading 'length')","details":{"checksRun":[],"checksFailed":["ipfs_fetch"]}},"passed":false,"created_at":1786736699},{"id":"eb621602-7968-4ae2-b717-8fb154b5ea11","executor_address":"0x088c6b88da1ff4955d8d7583aec88519bcb742a4","verification_result":{"passed":false,"reason":"Verification error: Cannot read properties of undefined (reading 'length')","details":{"checksRun":[],"checksFailed":["ipfs_fetch"]}},"passed":false,"created_at":1785874539},{"id":"3ba3fdbb-92fb-4bfa-abb0-d0d5600d79de","executor_address":"0x088c6b88da1ff4955d8d7583aec88519bcb742a4","verification_result":{"passed":false,"reason":"Verification error: Cannot read properties of undefined (reading 'length')","details":{"checksRun":[],"checksFailed":["ipfs_fetch"]}},"passed":false,"created_at":1785628273},{"id":"6c61f6f0-942f-4c4f-9504-b03c3103b60c","executor_address":"0x69d460a25a920d0ebd6df33e30f644b7401ca8bc","verification_result":{"passed":false,"reason":"Verification error: Cannot read properties of undefined (reading 'length')","details":{"checksRun":[],"checksFailed":["ipfs_fetch"]}},"passed":false,"created_at":1785609943},{"id":"f0530eb7-6b62-4b1e-ad61-ed3a1fe22ef7","executor_address":"0x7ef3ac86c66f629235dc1ef4c14836f8229c2970","verification_result":{"passed":false,"reason":"Verification error: Cannot read properties of undefined (reading 'length')","details":{"checksRun":[],"checksFailed":["ipfs_fetch"]}},"passed":false,"created_at":1785324314},{"id":"7b71f8b6-c4a0-426f-9b45-062282266aab","executor_address":"0x40b662bff89b7505e8656a9d07daf5330fd39f86","verification_result":{"passed":false,"reason":"Verification error: Cannot read properties of undefined (reading 'length')","details":{"checksRun":[],"checksFailed":["ipfs_fetch"]}},"passed":false,"created_at":1784815055},{"id":"d7566c6e-3f7b-4c7f-be54-d769974a5cc7","executor_address":"0x40b662bff89b7505e8656a9d07daf5330fd39f86","verification_result":{"passed":false,"reason":"Code output too small: 0 lines","details":{"checksRun":["output_parse","file_contents","sufficient_code"],"checksFailed":["sufficient_code"]}},"passed":false,"created_at":1784806480},{"id":"2c8361a1-ccfa-46fa-82ca-c68772a3d117","executor_address":"0x9544037e061abbd03d715593aed3cd9d02939c40","verification_result":{"passed":false,"reason":"Verification error: Cannot read properties of undefined (reading 'length')","details":{"checksRun":[],"checksFailed":["ipfs_fetch"]}},"passed":false,"created_at":1782673382},{"id":"b83485ae-e35e-42b1-9f4d-7cb566008d5d","executor_address":"0x688f7199b01fe435df8a97de669fc5e18ccdfa58","verification_result":{"passed":false,"reason":"Code output too small: 0 lines","details":{"checksRun":["output_parse","file_contents","sufficient_code"],"checksFailed":["sufficient_code"]}},"passed":false,"created_at":1782177341},{"id":"92298d7e-830b-45ea-acae-e0f8cf467288","executor_address":"0x343c1439ce6b83faf8e7ae488a532864c74ddb2a","verification_result":{"passed":false,"reason":"Code output too small: 0 lines","details":{"checksRun":["output_parse","file_contents","sufficient_code"],"checksFailed":["sufficient_code"]}},"passed":false,"created_at":1782103317},{"id":"976a8d78-7bab-4ca9-b3af-baeabc1bd3af","executor_address":"0x343c1439ce6b83faf8e7ae488a532864c74ddb2a","verification_result":{"passed":false,"reason":"Code output too small: 0 lines","details":{"checksRun":["output_parse","file_contents","sufficient_code"],"checksFailed":["sufficient_code"]}},"passed":false,"created_at":1782100072},{"id":"c7c29c75-269f-47a8-ba11-25ab3db3011a","executor_address":"0x76d6a2661d264c2fce9d5cfc8174041dd41bb050","verification_result":{"passed":false,"reason":"Verification error: Cannot read properties of undefined (reading 'length')","details":{"checksRun":[],"checksFailed":["ipfs_fetch"]}},"passed":false,"created_at":1780925275},{"id":"20c88646-b74c-44a0-a109-17c36cf8f304","executor_address":"0x1ea5c44f98ba233bfc15a130c7e10386aa17f709","verification_result":{"passed":false,"reason":"Verification error: Cannot read properties of undefined (reading 'length')","details":{"checksRun":[],"checksFailed":["ipfs_fetch"]}},"passed":false,"created_at":1780845950},{"id":"f97046d8-1a00-40fe-b0e1-a160c3636f54","executor_address":"0x76d6a2661d264c2fce9d5cfc8174041dd41bb050","verification_result":{"passed":false,"reason":"Verification error: Cannot read properties of undefined (reading 'length')","details":{"checksRun":[],"checksFailed":["ipfs_fetch"]}},"passed":false,"created_at":1780562770},{"id":"4956a237-8ce9-42e9-9d12-76a6e371f7b6","executor_address":"0x70d7ea3604a5225ed36552cb9eefcca43cd1ca3b","verification_result":{"passed":false,"reason":"Verification error: Cannot read properties of undefined (reading 'length')","details":{"checksRun":[],"checksFailed":["ipfs_fetch"]}},"passed":false,"created_at":1780109042},{"id":"66bca52d-bc0e-46af-b74b-05a9459d1c92","executor_address":"0x4c6d1e5da50e5d8fbd7f8b65e6c2f3e65ce5df0b","verification_result":{"passed":false,"reason":"Verification error: Cannot read properties of undefined (reading 'length')","details":{"checksRun":[],"checksFailed":["ipfs_fetch"]}},"passed":false,"created_at":1779821041},{"id":"159708a7-ec9c-422c-8e06-735be2a061f6","executor_address":"0x0cb7e80e2c4913939c2e04921f685b09e86a5d13","verification_result":{"passed":false,"reason":"Verification error: Cannot read properties of undefined (reading 'length')","details":{"checksRun":[],"checksFailed":["ipfs_fetch"]}},"passed":false,"created_at":1779714890},{"id":"fa3cda04-e91b-4c37-8540-f1fc34561770","executor_address":"0xfa9e4d255dbe8f00ba57b2fdb2bd52d8761796c1","verification_result":{"passed":false,"reason":"Code output too small: 0 lines","details":{"checksRun":["output_parse","file_contents","sufficient_code"],"checksFailed":["sufficient_code"]}},"passed":false,"created_at":1779360293}]}