#!/usr/bin/env python3 """Algorithm Starter Validation Script A practical helper for getting started with algorithms in operational settings. What this script does: - captures a precise problem definition - estimates time and space complexity from a chosen approach - validates sample outputs and common edge cases - compares a candidate result against a known-good reference - prints a production-readiness checklist This is intentionally vendor-neutral and safe to run locally. """ from __future__ import annotations import argparse import ast import json import sys from collections import Counter from dataclasses import dataclass from typing import Any, Callable, Dict, Iterable, List, Optional, Sequence, Tuple @dataclass class ProblemSpec: name: str input_description: str output_description: str success_criteria: str invalid_input: str expected_scale: str ordering: str = "unspecified" @dataclass class ComplexityEstimate: time: str space: str notes: str EDGE_CASES = { "empty_input": [], "single_item": [1], "all_identical": [7, 7, 7, 7], "already_sorted": [1, 2, 3, 4], "reverse_sorted": [4, 3, 2, 1], "duplicates": [4, 2, 4, 7, 2, 9], } def parse_list_literal(text: str) -> List[Any]: """Parse a Python list literal from the command line.""" try: value = ast.literal_eval(text) except (SyntaxError, ValueError) as exc: raise ValueError(f"Invalid Python literal: {exc}") from exc if not isinstance(value, list): raise ValueError("Input must be a Python list literal, for example: [1, 2, 3]") return value def estimate_complexity(approach: str) -> ComplexityEstimate: normalized = approach.lower().strip() if normalized in {"scan", "linear", "one-pass"}: return ComplexityEstimate("O(n)", "O(1)", "A single pass over the input with constant extra memory.") if normalized in {"hash", "hashing", "counter"}: return ComplexityEstimate("O(n)", "O(n)", "Uses a lookup structure to trade memory for faster repeated access.") if normalized in {"sort", "sorting"}: return ComplexityEstimate("O(n log n)", "O(1) to O(n)", "Depends on the language/runtime sort implementation.") if normalized in {"nested", "bruteforce", "brute force"}: return ComplexityEstimate("O(n^2)", "O(1)", "Two nested passes typically scale quadratically.") return ComplexityEstimate( "unknown", "unknown", "Approach not recognized. Use scan, hash, sort, or nested for a basic estimate.", ) def validate_duplicate_finder(items: Sequence[Any]) -> List[Any]: """Reference implementation for a common starter problem: find duplicates.""" counts = Counter(items) return sorted([value for value, count in counts.items() if count > 1]) def validate_sorted_output(result: Sequence[Any]) -> bool: return list(result) == sorted(result) def compare_to_reference(candidate: Sequence[Any], reference: Sequence[Any]) -> bool: return list(candidate) == list(reference) def build_problem_spec(args: argparse.Namespace) -> ProblemSpec: return ProblemSpec( name=args.problem_name, input_description=args.input_description, output_description=args.output_description, success_criteria=args.success_criteria, invalid_input=args.invalid_input, expected_scale=args.expected_scale, ordering=args.ordering, ) def print_problem_spec(spec: ProblemSpec) -> None: print("\nPROBLEM DEFINITION") print(f"- name: {spec.name}") print(f"- input: {spec.input_description}") print(f"- output: {spec.output_description}") print(f"- success: {spec.success_criteria}") print(f"- invalid input: {spec.invalid_input}") print(f"- expected scale: {spec.expected_scale}") print(f"- ordering: {spec.ordering}") def print_complexity(estimate: ComplexityEstimate) -> None: print("\nCOMPLEXITY ESTIMATE") print(f"- time: {estimate.time}") print(f"- space: {estimate.space}") print(f"- notes: {estimate.notes}") def run_edge_case_checks() -> Dict[str, Dict[str, Any]]: results: Dict[str, Dict[str, Any]] = {} for name, items in EDGE_CASES.items(): reference = validate_duplicate_finder(items) results[name] = { "input": items, "reference_output": reference, "is_sorted": validate_sorted_output(reference), } return results def print_edge_case_results(results: Dict[str, Dict[str, Any]]) -> None: print("\nEDGE CASE CHECKS") for name, data in results.items(): print(f"- {name}: input={data['input']} reference_output={data['reference_output']} sorted={data['is_sorted']}") def readiness_checklist() -> List[str]: return [ "Problem is defined with clear inputs, outputs, constraints, and invalid input behavior.", "Expected data size and latency or batch-window requirements are documented.", "Chosen approach matches the constraint profile and is the simplest viable option.", "Time and space complexity are estimated against realistic workload sizes.", "Small examples and boundary cases have been validated.", "A known-good reference or brute-force baseline has been used for comparison.", "Rollback, cleanup, and observability requirements are understood before release.", "Pathological inputs and resource exhaustion risks have been considered.", ] def print_checklist() -> None: print("\nPRODUCTION READINESS CHECKLIST") for item in readiness_checklist(): print(f"- [ ] {item}") def main(argv: Optional[Sequence[str]] = None) -> int: parser = argparse.ArgumentParser( description="Define an algorithm problem, estimate complexity, and validate correctness before production use.", ) parser.add_argument("--problem-name", default="duplicate finder", help="Short name for the algorithm problem.") parser.add_argument("--input-description", default="a list of user identifiers", help="Describe the input clearly.") parser.add_argument("--output-description", default="each identifier that appears more than once", help="Describe the output clearly.") parser.add_argument("--success-criteria", default="correct output under expected load and within the target runtime", help="Define what success means.") parser.add_argument("--invalid-input", default="null values are rejected", help="Define invalid input behavior.") parser.add_argument("--expected-scale", default="up to 10 million items", help="State the expected scale.") parser.add_argument("--ordering", default="sorted lexicographically", help="State any ordering requirements.") parser.add_argument("--approach", default="hash", help="Basic approach to estimate: scan, hash, sort, or nested.") parser.add_argument("--candidate", help="Optional Python list literal to compare against the reference implementation.") parser.add_argument("--json", action="store_true", help="Output results as JSON.") args = parser.parse_args(argv) spec = build_problem_spec(args) estimate = estimate_complexity(args.approach) edge_results = run_edge_case_checks() output: Dict[str, Any] = { "problem": spec.__dict__, "complexity": estimate.__dict__, "edge_cases": edge_results, "checklist": readiness_checklist(), } if args.candidate is not None: candidate = parse_list_literal(args.candidate) reference = validate_duplicate_finder(candidate) output["candidate_validation"] = { "candidate": candidate, "reference_output": reference, "matches_reference": compare_to_reference(sorted(candidate), candidate) if candidate else True, "reference_is_sorted": validate_sorted_output(reference), } if args.json: print(json.dumps(output, indent=2, sort_keys=True)) else: print_problem_spec(spec) print_complexity(estimate) print_edge_case_results(edge_results) print_checklist() if args.candidate is not None: print("\nCANDIDATE VALIDATION") print(f"- candidate: {output['candidate_validation']['candidate']}") print(f"- reference_output: {output['candidate_validation']['reference_output']}") print(f"- matches_reference: {output['candidate_validation']['matches_reference']}") print(f"- reference_is_sorted: {output['candidate_validation']['reference_is_sorted']}") return 0 if __name__ == "__main__": raise SystemExit(main())