{"metadata":{"kernelspec":{"language":"python","display_name":"Python 3","name":"python3"},"language_info":{"name":"python","version":"3.10.12","mimetype":"text/x-python","codemirror_mode":{"name":"ipython","version":3},"pygments_lexer":"ipython3","nbconvert_exporter":"python","file_extension":".py"},"kaggle":{"accelerator":"none","dataSources":[{"sourceId":84795,"databundleVersionId":11281725,"sourceType":"competition"},{"sourceId":225126329,"sourceType":"kernelVersion"},{"sourceId":236919,"sourceType":"modelInstanceVersion","isSourceIdPinned":true,"modelInstanceId":202340,"modelId":224071},{"sourceId":236932,"sourceType":"modelInstanceVersion","modelInstanceId":202348,"modelId":224071},{"sourceId":237029,"sourceType":"modelInstanceVersion","modelInstanceId":202436,"modelId":224071},{"sourceId":276458,"sourceType":"modelInstanceVersion","isSourceIdPinned":true,"modelInstanceId":236741,"modelId":224053}],"isInternetEnabled":false,"language":"python","sourceType":"notebook","isGpuEnabled":false}},"nbformat_minor":4,"nbformat":4,"cells":[{"cell_type":"markdown","source":"# Setup","metadata":{}},{"cell_type":"code","source":"import os\nimport sys\nos.environ[\"TRITON_PTXAS_PATH\"] = \"/usr/local/cuda/bin/ptxas\"","metadata":{"trusted":true,"execution":{"iopub.status.busy":"2025-03-11T14:16:28.054016Z","iopub.execute_input":"2025-03-11T14:16:28.054216Z","iopub.status.idle":"2025-03-11T14:16:28.057073Z","shell.execute_reply.started":"2025-03-11T14:16:28.054197Z","shell.execute_reply":"2025-03-11T14:16:28.056534Z"}},"outputs":[],"execution_count":null},{"cell_type":"code","source":"import io\nimport time\nimport shutil\n\nimport pandas as pd\nimport polars as pl\n\nimport kaggle_evaluation.konwinski_prize_inference_server\nfrom typing import List, Tuple, Dict, Optional\n\nimport tree_sitter_python as tspython\nfrom tree_sitter import Language, Parser\n\nPY_LANGUAGE = Language(tspython.language())\nparser = Parser(PY_LANGUAGE)\n\nstart_time = time.time()\nallowed_time = [start_time + 90 * 60]","metadata":{"trusted":true,"execution":{"iopub.status.busy":"2025-03-11T14:16:28.057682Z","iopub.execute_input":"2025-03-11T14:16:28.057873Z","iopub.status.idle":"2025-03-11T14:16:39.404976Z","shell.execute_reply.started":"2025-03-11T14:16:28.057855Z","shell.execute_reply":"2025-03-11T14:16:39.404305Z"}},"outputs":[],"execution_count":null},{"cell_type":"code","source":"instance_count: Optional[int] = None\n\n\ndef get_number_of_instances(num_instances: int) -> None:\n    \"\"\"The very first message from the gateway will be the total number of instances to be served.\n    You don't need to edit this function.\n    \"\"\"\n    global instance_count\n    instance_count = num_instances\n    print(instance_count)\n\n    if instance_count == 71:    \n        allowed_time[-1] = start_time + 9 * 3600\n    else:\n        allowed_time[-1] = start_time + 24 * 3600","metadata":{"trusted":true,"execution":{"iopub.status.busy":"2025-03-11T14:16:39.405581Z","iopub.execute_input":"2025-03-11T14:16:39.405941Z","iopub.status.idle":"2025-03-11T14:16:39.409812Z","shell.execute_reply.started":"2025-03-11T14:16:39.40592Z","shell.execute_reply":"2025-03-11T14:16:39.409101Z"}},"outputs":[],"execution_count":null},{"cell_type":"code","source":"import torch\nfrom transformers import AutoTokenizer, AutoModelForCausalLM, BitsAndBytesConfig\nfrom huggingface_hub import hf_hub_download\nimport numpy as np\nimport random\nfrom vllm import LLM, SamplingParams","metadata":{"_uuid":"38b86f00-408f-4577-b91e-890da62fd434","_cell_guid":"eec2b282-90f3-4965-a943-54cffbeb7a5b","trusted":true,"collapsed":false,"jupyter":{"outputs_hidden":false},"execution":{"iopub.status.busy":"2025-03-11T14:16:39.410441Z","iopub.execute_input":"2025-03-11T14:16:39.410658Z","iopub.status.idle":"2025-03-11T14:17:35.166079Z","shell.execute_reply.started":"2025-03-11T14:16:39.410639Z","shell.execute_reply":"2025-03-11T14:17:35.165365Z"}},"outputs":[],"execution_count":null},{"cell_type":"code","source":"os.environ[\"CUDA_VISIBLE_DEVICES\"] = \"0,1,2,3\"\nos.environ[\"TOKENIZERS_PARALLELISM\"] = \"false\"\n\n# llm_model_pth = \"/kaggle/input/m/huikang/deepseek-r1/transformers/qwen-qwq-32b-awq/1\"\n# llm_model_pth = \"/kaggle/input/deepseek-r1/transformers/deepseek-r1-distill-llama-70b-awq/1\"\n# llm_model_pth = \"/kaggle/input/deepseek-r1/transformers/deepseek-r1-distill-qwen-32b-awq/1\"\nllm_model_pth = \"/kaggle/input/deepseek-r1/transformers/deepseek-r1-distill-qwen-14b-awq/1\"\n\nBATCH_SIZE: int = 6\nVALIDATION_COPY_COUNT: int = 5\n# Model needs tokens to think, but it might not exceed ~4000 on average, but if it does it does not fit time limits in worst case \nMAX_TOKENS: int = 4096 \n\n# ToT\nBRANCHING_FACTOR = 12\nPRUNING_FACTOR = 3/12\n\nMAX_NUM_SEQS: int = max([BATCH_SIZE, VALIDATION_COPY_COUNT, BRANCHING_FACTOR])\nMAX_MODEL_LEN: int = 32_768","metadata":{"trusted":true,"execution":{"iopub.status.busy":"2025-03-11T14:17:35.1667Z","iopub.execute_input":"2025-03-11T14:17:35.166913Z","iopub.status.idle":"2025-03-11T14:17:35.170947Z","shell.execute_reply.started":"2025-03-11T14:17:35.166894Z","shell.execute_reply":"2025-03-11T14:17:35.170354Z"}},"outputs":[],"execution_count":null},{"cell_type":"code","source":"llm: LLM = LLM(\n    llm_model_pth,\n    max_num_seqs=MAX_NUM_SEQS,  # Maximum number of sequences per iteration. Default is 256\n    max_model_len=MAX_MODEL_LEN,  # Model context length\n    trust_remote_code=True,  # Trust remote code (e.g., from HuggingFace) when downloading the model and tokenizer\n    tensor_parallel_size=4,  # The number of GPUs to use for distributed execution with tensor parallelism\n    enable_prefix_caching=True,\n    gpu_memory_utilization=0.8,  # The ratio (between 0 and 1) of GPU memory to reserve for the model\n    seed=42069\n)","metadata":{"_uuid":"eca28397-2a40-4265-b36e-dfa9d80eb2b1","_cell_guid":"c863b090-e04a-441e-9add-bddae0863ef9","trusted":true,"collapsed":false,"_kg_hide-output":true,"jupyter":{"outputs_hidden":false},"execution":{"iopub.status.busy":"2025-03-11T14:17:35.17267Z","iopub.execute_input":"2025-03-11T14:17:35.172879Z","iopub.status.idle":"2025-03-11T14:21:32.666147Z","shell.execute_reply.started":"2025-03-11T14:17:35.172861Z","shell.execute_reply":"2025-03-11T14:21:32.665378Z"}},"outputs":[],"execution_count":null},{"cell_type":"code","source":"tokenizer = llm.get_tokenizer()\n\ndef count_tokens(text: str) -> int:\n    return len(tokenizer.encode(text))","metadata":{"_uuid":"5a982fe4-e4e2-466d-b5bf-4839ec8804c8","_cell_guid":"99e40ae3-6474-4b05-a969-0b48de303ba6","trusted":true,"collapsed":false,"jupyter":{"outputs_hidden":false},"execution":{"iopub.status.busy":"2025-03-11T14:21:32.667629Z","iopub.execute_input":"2025-03-11T14:21:32.667875Z","iopub.status.idle":"2025-03-11T14:21:32.671224Z","shell.execute_reply.started":"2025-03-11T14:21:32.667848Z","shell.execute_reply":"2025-03-11T14:21:32.670603Z"}},"outputs":[],"execution_count":null},{"cell_type":"markdown","source":"# Scaffold\n\nThis notebook is a fork of [Select-Patch-Verify](https://www.kaggle.com/code/huikang/starter-notebook-select-patch-verify):\n1. Select - given the problem statement and repository structure return list of queries on snippet extraction.\n2. Patch - given the problem statement and related files return a diff patch that will fix the issue.\n3. Verify - pass the proposed solution through validation (diff correctness and dry run), as there is no actual test for the issue make model \"vote\" for the solution.\n\nThis competition favours sceptic models as wrong answers are punished while skips \"effectively\" are not. Thus verification step here is very rigorous, featuring somewhat similar to [SC-CoT](https://arxiv.org/pdf/2203.11171).\n\nIt is resembling of top-performing scaffolding approach of [Agentless](https://arxiv.org/abs/2407.01489) that also does not rely on emergent agentic capabilities of LLM as they have not yet reached the stage when they can build complex constructions like [ToT](https://arxiv.org/abs/2305.10601), though by using RL techniques they can \"naturally\" produce CoT. Based on such evidence Agentless provides deterministic sequence of actions to complete tasks like issue patching.\n\nAgentless is a bit more complex:\n1. Select step is multi-stage, it makes an initial guess that is more optimal as well as it provides an internal file-сarcass representation to give the model bigger attention span.\n2. Verification step does not use judges, but runs a query that produces reproduction test which is the final challenge for the produced patch.\n3. Patch and verification form a feedback loop.\n\nAs well as using domain-specific answer processing this solution tries to take the best of both worlds:\n1. Multi-stage select, with tree-sitter based search for high quality snippets.\n2. ToT-based patch-verify loop that does not start from many batches that are pruned eventually, but uses branching-verification-pruning.","metadata":{"_uuid":"30f587b9-7b4f-4812-82f7-d87787c58d1c","_cell_guid":"3a54e069-fe31-4873-9d25-a02c38576c59","trusted":true,"collapsed":false,"jupyter":{"outputs_hidden":false}}},{"cell_type":"code","source":"def stringify_directory(directory: str) -> str:\n    full_paths: List[str] = []\n\n    for root, dirs, files in os.walk(directory):\n        for file in files:\n            if not file.endswith('.py'):\n                continue\n                \n            full_path: str = os.path.join(root, file)            \n            full_paths.append(full_path)\n            \n    return \"\\n\".join(full_paths)","metadata":{"_uuid":"43546fee-8473-4f0d-80ec-46a86369426b","_cell_guid":"44d40acd-8428-4813-ba5d-62f625309dd4","trusted":true,"execution":{"iopub.status.busy":"2025-03-11T14:21:32.671935Z","iopub.execute_input":"2025-03-11T14:21:32.672141Z","iopub.status.idle":"2025-03-11T14:21:32.68274Z","shell.execute_reply.started":"2025-03-11T14:21:32.672123Z","shell.execute_reply":"2025-03-11T14:21:32.682138Z"}},"outputs":[],"execution_count":null},{"cell_type":"code","source":"import re\n\ndef extract_file_query(xml_content: str) -> Dict[str, List[str]]:\n    import xml.etree.ElementTree as ET\n\n    # Prepare a data structure to collect results\n    parsed_data: Dict[str, List[str]] = {}\n    pattern: str = r\"<root>(.*?)</root>\"\n    matches: List[str] = re.findall(pattern, xml_content, re.DOTALL)\n\n    for match in matches:\n        try:\n            # Parse the XML\n            root = ET.fromstring(\"<root>\" + match + \"</root>\")\n\n            # Find all <entry> elements\n            for entry in root.findall(\"entry\"):\n                # Extract the <filepath> text\n                filepath = entry.find(\"filepath\")\n                filepath_text: Optional[str] = (\n                    filepath.text.strip()\n                    if filepath is not None and filepath.text is not None\n                    else None\n                )\n\n                summary = entry.find(\"summary\")\n                summary_text: Optional[str] = (\n                    summary.text.strip()\n                    if summary is not None and summary.text is not None\n                    else None\n                )\n\n                # Locate <strings_to_search> container\n                strings_container = entry.find(\"strings_to_search\")\n\n                # Gather each <string_to_search> text\n                search_strings: List[str] = []\n                if strings_container is not None:\n                    for s in strings_container.findall(\"string_to_search\"):\n                        if s.text is not None:\n                            search_strings.append(s.text.strip())\n\n                # Store in a dictionary: { filepath: [search_strings...] }\n                parsed_data[filepath_text] = (search_strings, summary_text)  # type: ignore\n        except:\n            # Wrong matches do not short circuit to allow successful ones to pass\n            pass\n\n    return parsed_data","metadata":{"_uuid":"47b13790-f9e8-47cd-8b78-c93567e04b56","_cell_guid":"50b46124-4395-4783-b523-f11f4b6228bf","trusted":true,"execution":{"iopub.status.busy":"2025-03-11T14:21:32.683404Z","iopub.execute_input":"2025-03-11T14:21:32.68362Z","iopub.status.idle":"2025-03-11T14:21:32.693506Z","shell.execute_reply.started":"2025-03-11T14:21:32.683602Z","shell.execute_reply":"2025-03-11T14:21:32.692904Z"}},"outputs":[],"execution_count":null},{"cell_type":"markdown","source":"It is not guaranteed, but most of the issues use pytest, so test files can be identified. It can be used to run them on verification step. However, usability of such step requires the following assumptions to be correct:\n* There are already tests that are useful for us\n* This subset of tests is small enough (main concern is how long it is to run them)\n* It is easy for the model to identify the right ones\n\nI am not convinced that all of the above is correct (Now that we know more about the top solutions - it is quite correct). Instead test files are simply filtered out, so the model has no way to change them (doing so results in error).","metadata":{}},{"cell_type":"code","source":"def get_test_paths(repo_path, timeout=30):\n    pattern: str = r\"[^:]+::\"\n    cmd = f\"pytest --co -q {repo_path}\"\n    try:\n        result = subprocess.run(cmd, shell=True, capture_output=True, text=True, timeout=timeout)\n        lines = result.stdout.split(\"\\n\")\n        \n        filenames = []\n        for line in lines:\n            matches = re.findall(pattern, line)\n            if len(matches) > 0:\n                filenames.append(\"repo/\" + matches[0][:-2])\n        \n        return filenames\n    except Exception as e:\n        return []","metadata":{"trusted":true,"execution":{"iopub.status.busy":"2025-03-11T14:21:32.694166Z","iopub.execute_input":"2025-03-11T14:21:32.694367Z","iopub.status.idle":"2025-03-11T14:21:32.706057Z","shell.execute_reply.started":"2025-03-11T14:21:32.69435Z","shell.execute_reply":"2025-03-11T14:21:32.705497Z"}},"outputs":[],"execution_count":null},{"cell_type":"markdown","source":"To keep the searches consistent multiple suggested search queries are merged from the entries that repeat often enough. Too high thresholds result in an unsuccessful retrieval.","metadata":{}},{"cell_type":"code","source":"def get_consistent_query(file_queries):\n    threshold = 2 # BATCH_SIZE // 2\n\n    query_scores = {}\n    summaries = {}\n    for file_query in file_queries:\n        for file, (strings, summary) in file_query.items():\n            for string in strings:\n                address = (file, string)\n                \n                if address not in query_scores:\n                    query_scores[address] = 1\n                    summaries[address] = summary\n                else: \n                    query_scores[address] += 1\n\n    consistent_queries = []\n    for query, score in query_scores.items():\n        if score >= threshold:\n            consistent_queries.append(query)\n\n    consistent_file_query = {}\n    for query in consistent_queries:\n        file, string = query\n        if file not in consistent_file_query:\n            consistent_file_query[file] = ([], summaries[query])\n\n        consistent_file_query[file][0].append(string)\n\n    return [consistent_file_query]","metadata":{"trusted":true,"execution":{"iopub.status.busy":"2025-03-11T14:21:32.706713Z","iopub.execute_input":"2025-03-11T14:21:32.706925Z","iopub.status.idle":"2025-03-11T14:21:32.71808Z","shell.execute_reply.started":"2025-03-11T14:21:32.706908Z","shell.execute_reply":"2025-03-11T14:21:32.717512Z"}},"outputs":[],"execution_count":null},{"cell_type":"markdown","source":"Interesting observation for me was that the model when given the prompt that describes its future actions still executes them and hallucinates the answers. When telling it ```You'll be implementing a diff patch, so select files for yourself``` rather then ```You're assisting a programmer and you need to suggest the files to investigate to fix an issue``` it may also start planning the solution and sometimes it will even imagine the patch.\n\nIt sounds cool, but on practice the model fixes the codes that may not even exist as well as it practically wastes tokens. Thus each prompt is executed as an independent task even if it is a part of some loop. This fix does not completely eliminate this behaviour, but I believe it does not affect the agent as much now.","metadata":{}},{"cell_type":"code","source":"reading_prompt: str = (\n    \"\"\"\nYou are assisting a programmer who will be implementing a patch to solve an issue with the code repository.\nYou need to select files in the file directory that can be helpful, use your coding knowledge to provide the best results. \nThis process will be executed multiple times and you will need to refine your previous selections, only the last selection is used.\n\nProblem Statement: \n\n{problem_statement}\n\nFile Directory:\n\n<directory>\n{directory_string}\n</directory>\n\nCurrently Selected Snippets (if any):  \n<snippets>\n{snippets}\n</snippets>\n\nWhich files should be inspected so that we can identify and solve the problem?\nWhat is the root of the problem and what are its dependencies?\nWhen we inspect each file, what strings should be searched?\n\nReturn the strings to search in this format\n\n(explanation)\n\n<root>\n    <entry>\n        <filepath>filepath</filepath>\n        <summary>summary for the file purpose in patching</summary>\n        <strings_to_search>\n            <string_to_search>string_to_search</string_to_search>\n            ...\n            <string_to_search>string_to_search</string_to_search>\n        </strings_to_search>\n    </entry>\n    <entry>\n        <filepath>filepath</filepath>\n        <summary>summary for the file purpose in patching</summary>\n        <strings_to_search>\n            <string_to_search>string_to_search</string_to_search>\n            ...\n            <string_to_search>string_to_search</string_to_search>\n        </strings_to_search>\n    </entry>\n    ...\n</root>\n...\n\nImportant Guidelines:\n\n- Encoding: Ensure each entry is enclosed within the `<root>` and `</root>` tags.\n- Filepaths: Return the full filepaths exactly as specified in the `<directory>` block.\n- Search Strings:  \n  - When targeting function calls or keywords, include contextual characters to reduce false positives, but resort from guessing details.\n      For example, when you search for function definition omit the signature: prefer def function_name( over def function_name(self, arg).\n  - Prefer more specific strings that are unlikely to occur by chance elsewhere in the codebase.  \n- Error Context:\n  - Reconstruct the sequence of actions leading to the error and identify the related files.\n  - Include any relevant files and trace the call stack where necessary.\n- Moderation:\n  - If no snippets have been selected yet, be cautious with file selection until further context is available.\n  - Your previous selections are discarded. If they're useful include them into query again.\n\"\"\".strip()\n)\n\n\ndef get_selection_query(\n    directory_string: str, problem_statement: str, file_content_strings: List[str] = [\"\"] * BATCH_SIZE\n) -> Tuple[List[str], List[Dict[str, List[str]]]]:\n    sampling_params: SamplingParams = SamplingParams(\n        temperature=0.5,  # randomness of the sampling\n        min_p=0.01,\n        top_p=0.95,\n        skip_special_tokens=True,  # Whether to skip special tokens in the output\n        max_tokens=MAX_TOKENS,\n    )\n\n    list_of_messages: List[List[Dict[str, str]]] = [\n        [\n            {\n                \"role\": \"user\",\n                \"content\": reading_prompt.format(\n                    problem_statement=problem_statement[:20_000],\n                    directory_string=directory_string[:30_000],\n                    snippets=file_content_strings[input_idx][:30_000]\n                ),\n            },\n        ]\n        for input_idx in range(BATCH_SIZE)\n    ]\n\n    prompt_texts: List[str] = [\n        (\n            tokenizer.apply_chat_template(\n                conversation=messages, tokenize=False, add_generation_prompt=True\n            )  # type: ignore\n        )\n        + \"<think>\\n\"\n        for messages in list_of_messages\n    ]\n    \n    print(\"get_selection_query\", [count_tokens(text) for text in prompt_texts])\n    request_outputs: list[RequestOutput] = llm.generate(\n        prompt_texts, sampling_params=sampling_params\n    )\n    if not request_outputs:\n        return [], []\n\n    if (\n        os.getenv(\"KAGGLE_KERNEL_RUN_TYPE\") == \"Interactive\"\n        and not os.getenv(\"KAGGLE_IS_COMPETITION_RERUN\")\n    ):\n        print(prompt_texts[0])\n        print(request_outputs[0].outputs[0].text)\n    \n    response_texts: List[str] = [\n        request_output.outputs[0].text for request_output in request_outputs\n    ]\n    print(\"get_selection_query\", [count_tokens(text) for text in response_texts])\n\n\n    file_queries: List[Dict[str, List[str]]] = [\n        extract_file_query(response_text) for response_text in response_texts\n    ]\n    return file_queries","metadata":{"_uuid":"b6264935-32cf-49b5-b1da-aece43dbf184","_cell_guid":"a636bf5a-ec3a-4113-8504-bc95550036ef","trusted":true,"execution":{"iopub.status.busy":"2025-03-11T14:21:32.718689Z","iopub.execute_input":"2025-03-11T14:21:32.718896Z","iopub.status.idle":"2025-03-11T14:21:32.728343Z","shell.execute_reply.started":"2025-03-11T14:21:32.718879Z","shell.execute_reply":"2025-03-11T14:21:32.727767Z"}},"outputs":[],"execution_count":null},{"cell_type":"code","source":"REPO_PATH: str = \"repo\"\n\n# ---------------------------------------------------------\n# 3. MERGE OVERLAPPING/ADJACENT SNIPPETS\n# ---------------------------------------------------------\n\ndef merge_file_snippets(\n    file_snippets: List[List[Tuple[int, str]]], gap: int = 0\n) -> List[List[Tuple[int, str]]]:\n    \"\"\"\n    Merge overlapping or nearly adjacent snippets in a single file’s snippet list.\n    \"\"\"\n    intervals: List[Tuple[int, int, List[Tuple[int, str]]]] = []\n    for snippet in file_snippets:\n        if snippet:\n            start_line: int = snippet[0][0]\n            end_line: int = snippet[-1][0]\n            intervals.append((start_line, end_line, snippet))\n\n    intervals.sort(key=lambda x: x[0])  # sort by start line\n\n    merged: List[Tuple[int, int, List[Tuple[int, str]]]] = []\n    for start, end, snippet in intervals:\n        if not merged:\n            merged.append((start, end, snippet))\n            continue\n\n        prev_start, prev_end, prev_snippet = merged[-1]\n        if start <= prev_end + gap:\n            new_end: int = max(end, prev_end)\n            combined_dict: Dict[int, str] = {}\n            for ln, txt in prev_snippet:\n                combined_dict[ln] = txt\n            for ln, txt in snippet:\n                combined_dict[ln] = txt\n            merged_snippet: List[Tuple[int, str]] = [\n                (ln, combined_dict[ln]) for ln in sorted(combined_dict)\n            ]\n            merged[-1] = (prev_start, new_end, merged_snippet)\n        else:\n            merged.append((start, end, snippet))\n\n    # Extract just the merged snippet portion\n    return [x[2] for x in merged]\n\ndef merge_all_snippets(\n    all_files_snips: List[List[List[Tuple[int, str]]]], gap: int = 0\n) -> List[List[List[Tuple[int, str]]]]:\n    \"\"\"\n    Merge snippet blocks within each file.\n    all_files_snips is a list-of-lists:\n      [\n        [ snippetA, snippetB, ... ],  # file 1\n        [ snippetC, snippetD, ... ],  # file 2\n      ]\n    \"\"\"\n    merged: List[List[List[Tuple[int, str]]]] = []\n    for snips in all_files_snips:\n        merged.append(merge_file_snippets(snips, gap=gap))\n    return merged\n\ndef fetch_file_contents(\n    files_to_search: Dict[str, List[str]], context_lines: int = 12, max_gap: int = 0, max_matches_per_file=15\n) -> str:\n    from io import StringIO\n    from typing import Tuple\n\n    def find_lines_in_files_with_context(\n        search_map: Dict[str, Tuple[List[str], str]], context_lines: int = context_lines\n    ) -> List[List[List[Tuple[int, str]]]]:\n        \"\"\"\n        Given a dictionary mapping file paths to a list of search terms,\n        open each file and gather *snippets* of lines that contain any\n        of those search terms, including 'context_lines' before and after.\n\n        Returns a list of lists:\n        [\n          [  # For file1\n             [ (line_number, text), (line_number, text), ... ],\n             [ ... ],\n          ],\n          [  # For file2\n             ...\n          ],\n          ...\n        ]\n        \"\"\"\n        all_matches_per_file: List[List[List[Tuple[int, str]]]] = []\n\n        for path, (terms, _) in search_map.items():\n            if not os.path.isfile(path):\n                # If the file is not found, record an empty list\n                all_matches_per_file.append([])\n                continue\n\n            with open(path, \"r\", encoding=\"utf-8\", errors=\"replace\") as f:\n                lines = f.readlines()\n\n            file_snippets: List[List[Tuple[int, str]]] = []\n            num_lines: int = len(lines)\n\n            for i, line in enumerate(lines, start=1):\n                if any(t in line for t in terms):\n                    start_idx: int = max(1, i - context_lines)\n                    end_idx: int = min(num_lines, i + context_lines)\n                    snippet: List[Tuple[int, str]] = []\n                    for snippet_no in range(start_idx, end_idx + 1):\n                        text_content: str = lines[snippet_no - 1].rstrip(\"\\n\")\n                        snippet.append((snippet_no, text_content))\n                    file_snippets.append(snippet)\n\n            all_matches_per_file.append(file_snippets)\n\n        return all_matches_per_file\n\n    # ---------------------------------------------------------\n    # 4. RUN LOGIC: generate files, search, merge, and BUILD A STRING\n    # ---------------------------------------------------------\n\n    has_any_matches: bool = False\n\n    # 1) Gather snippets around each match\n    context_snippets: List[List[List[Tuple[int, str]]]] = (\n        find_lines_in_files_with_context(files_to_search, context_lines=context_lines)\n    )\n\n    # 2) Merge overlapping snippets\n    merged_snips: List[List[List[Tuple[int, str]]]] = merge_all_snippets(\n        context_snippets, gap=max_gap\n    )\n\n    # 3) Build a string (instead of printing)\n    output = StringIO()\n    snippets_dict = {}\n\n    # For each file\n    for (filepath, (terms, summary)), snippet_list in zip(files_to_search.items(), merged_snips):\n        output.write(f\"[file name]: {filepath[len(REPO_PATH) + 1:]}\\n\")\n        terms_searched_as_str = \"\\n\".join(terms)\n        output.write(f\"[summary]:\\n{summary}\\n\")\n        output.write(f\"[terms searched]:\\n{terms_searched_as_str}\\n\")\n        output.write(\"[file content begin]\\n\")\n        \n        snippets_dict[filepath] = snippet_list\n        \n        if not snippet_list:\n            output.write(\"  No matches found.\\n\")\n        else:\n            has_any_matches = True\n            for snippet_idx, snippet in enumerate(snippet_list[:max_matches_per_file], start=1):\n                snippet_start: int = snippet[0][0]\n                snippet_end: int = snippet[-1][0]\n                output.write(\n                    f\"\\nMatch #{snippet_idx}, lines {snippet_start} to {snippet_end}:\\n\"\n                )\n                for line_no, text in snippet:\n                    output.write(f\"  {line_no:3d} | {text}\\n\")\n                output.write(\"\\n\")\n        output.write(\"[file content end]\\n\\n\")\n\n    file_content_string: str = output.getvalue()\n\n    return file_content_string, snippets_dict","metadata":{"_uuid":"f8ae44f3-2595-4c78-b58a-6551c0fec3a8","_cell_guid":"2e6aebd6-10e8-4769-98dc-4e89aaf35b41","trusted":true,"execution":{"iopub.status.busy":"2025-03-11T14:21:32.729007Z","iopub.execute_input":"2025-03-11T14:21:32.729205Z","iopub.status.idle":"2025-03-11T14:21:32.744556Z","shell.execute_reply.started":"2025-03-11T14:21:32.729188Z","shell.execute_reply":"2025-03-11T14:21:32.743978Z"}},"outputs":[],"execution_count":null},{"cell_type":"code","source":"def node_length(node):\n    return node.end_point.row - node.start_point.row + 1\n\ndef node_source(node, source):\n    return source[node.start_byte:node.end_byte].decode(\"utf8\")\n\nallowed_nodes = ['class_definition', 'function_definition', 'decorated_definition']\n\ndef fetch_code_contents(\n    files_to_search: Dict[str, List[str]], max_lines=40, max_matches_per_file=15, context_lines=12\n) -> str:\n    from io import StringIO\n    from typing import Tuple\n\n    def search_tree(filepath, terms):\n        \"\"\"\n        Build tree sitter tree\n        Traverse the tree by picking the highest nodes that are max_lines or less and leaves\n        If node contains any of terms:\n        - If it is small it is appended in full\n        - If it is big it is processed via default script\n        \"\"\"\n        \n        if not os.path.isfile(filepath):\n            # If the file is not found, record an empty list\n            return []\n\n        with open(filepath, \"r\", encoding=\"utf-8\", errors=\"replace\") as f:\n            lines = f.readlines()\n        \n        file_snippets: List[List[Tuple[int, str]]] = []\n        num_lines: int = len(lines)\n\n        file_bytes = bytes(\"\".join(lines), \"utf8\")\n        tree = parser.parse(file_bytes, encoding=\"utf8\")\n\n        snippet_candidates = []\n        queue = [tree.root_node]\n\n        while len(queue) > 0:\n            head, *tail = queue\n\n            text = node_source(head, file_bytes)\n            if all(term not in text for term in terms):\n                queue = tail\n                continue\n            \n            if head.grammar_name in allowed_nodes and (node_length(head) <= max_lines or len(head.children) == 0):\n                snippet_candidates.append(head)\n            else:\n                tail += list(head.children)\n                \n            queue = tail\n\n        for candidate in snippet_candidates:\n            node_len = node_length(candidate)\n            node_lines = node_source(candidate, file_bytes).split(\"\\n\")\n            \n            if node_len <= max_lines:\n                snippet_lines = [(candidate.start_point.row + i + 1, node_lines[i]) for i in range(node_len)]\n                file_snippets.append(snippet_lines)\n            else:\n                snippets_to_merge = []\n                \n                # process as regular snippet\n                for i, line in enumerate(node_lines, start=1):\n                    if any(t in line for t in terms):\n                        start_idx: int = max(1, candidate.start_point.row + i + 1 - context_lines)\n                        end_idx: int = min(num_lines, candidate.start_point.row + i + 1 + context_lines)\n                        snippet: List[Tuple[int, str]] = []\n                        for snippet_no in range(start_idx, end_idx + 1):\n                            text_content: str = lines[snippet_no - 1].rstrip(\"\\n\")\n                            snippet.append((snippet_no, text_content))\n                        snippets_to_merge.append(snippet)\n\n                file_snippets += merge_file_snippets(snippets_to_merge)\n        return merge_file_snippets(file_snippets)\n    \n    has_any_matches = False\n    output = StringIO()\n    snippets_dict = {}\n    \n    for filepath, (terms, summary) in files_to_search.items():\n        output.write(f\"[file name]: {filepath[len(REPO_PATH) + 1:]}\\n\")\n        terms_searched_as_str = \"\\n\".join(terms)\n        output.write(f\"[summary]:\\n{summary}\\n\")\n        output.write(f\"[terms searched]:\\n{terms_searched_as_str}\\n\")\n        output.write(\"[file content begin]\\n\")\n\n        snippet_list = search_tree(filepath, terms)\n        snippets_dict[filepath] = snippet_list\n        \n        if not snippet_list:\n            output.write(\"  No matches found.\\n\")\n        else:\n            has_any_matches = True\n            for snippet_idx, snippet in enumerate(snippet_list[:max_matches_per_file], start=1):\n                snippet_start: int = snippet[0][0]\n                snippet_end: int = snippet[-1][0]\n                output.write(\n                    f\"\\nMatch #{snippet_idx}, lines {snippet_start} to {snippet_end}:\\n\"\n                )\n                for line_no, text in snippet:\n                    output.write(f\"  {line_no:3d} | {text}\\n\")\n                output.write(\"\\n\")\n        output.write(\"[file content end]\\n\\n\")\n\n    file_content_string: str = output.getvalue()\n\n    return file_content_string, snippets_dict","metadata":{"trusted":true,"execution":{"iopub.status.busy":"2025-03-11T14:21:32.745162Z","iopub.execute_input":"2025-03-11T14:21:32.745358Z","iopub.status.idle":"2025-03-11T14:21:32.759317Z","shell.execute_reply.started":"2025-03-11T14:21:32.745341Z","shell.execute_reply":"2025-03-11T14:21:32.758704Z"}},"outputs":[],"execution_count":null},{"cell_type":"markdown","source":"I am not sure how exactly suggested patch is applied: patch utility has a `-fuzz` parameter that allows to apply patches with slight issues in their context, like shifted line count. This allows to pass dry-run validation, but does not really guarantee a good patch. Here dry-run is exexuted with no fuzz, but patches are automatically \"healed\" by recounting and shifting them.\n\nUsing those healing routines is crucial as the LLMs do not really excel in precise answers.","metadata":{}},{"cell_type":"code","source":"def try_fuzz_in(patch_string, fuzz=5):\n    # Parse the patch:\n    # * Split it into different files and into different snippets\n    hunks = []\n\n    current_filename = \"\"\n    current_hunk_init = []\n    current_hunk_new = []\n    current_hunk = []\n\n    in_hunk = False\n\n    diff_lines = patch_string.split('\\n')\n    for line in diff_lines:\n        if line.startswith('@@ '):\n            # New hunk starts; process the previous one if it exists.\n            if current_hunk:\n                hunks.append((current_filename, current_hunk, current_hunk_new, current_hunk_init))\n                current_hunk_init = []\n                current_hunk_new = []\n                current_hunk = []\n            current_hunk.append(line)\n            in_hunk = True\n        elif in_hunk and (line.startswith(' ') or line.startswith('-') or line.startswith('+')):\n            if in_hunk and (line.startswith(' ') or line.startswith('-')):\n                current_hunk_init.append(line[1:])\n            if in_hunk and (line.startswith(' ') or line.startswith('+')):\n                current_hunk_new.append(line[1:])\n            current_hunk.append(line)\n        else:\n            # Lines outside hunks (like file header lines) are output as-is.\n            if current_hunk:\n                hunks.append((current_filename, current_hunk, current_hunk_new, current_hunk_init))\n                current_hunk_init = []\n                current_hunk_new = []\n                current_hunk = []\n                in_hunk = False\n            if line.startswith('---'):\n                current_filename = line[5:]\n    if current_hunk:\n        hunks.append((current_filename, current_hunk, current_hunk_new, current_hunk_init))\n\n    hunks_dictionary = {}\n\n    # For each available hunk\n    for (filepath, hunk_lines, new_hunk_lines, init_hunk_lines) in hunks:\n        if filepath not in hunks_dictionary:\n            hunks_dictionary[filepath] = \"\"\n        \n        actual_filepath = REPO_PATH + filepath\n        # Try reading source file\n        try:\n            with open(actual_filepath, \"r\", encoding=\"utf-8\", errors=\"replace\") as f:\n                lines = f.readlines()\n\n            header_line = hunk_lines[0]\n            # Match header of the form: @@ -<old_start>[,<old_count>] +<new_start>[,<new_count>] @@[ optional text]\n            m = re.match(r'^@@ -(\\d+)(?:,(\\d+))? \\+(\\d+)(?:,(\\d+))? @@(.*)$', header_line)\n            if not m:\n                # If header doesn't match expected format, return as-is\n                raise Exception(\"Invalid hunk\")\n\n            old_start = int(m.group(1))\n            # If count isn’t given, it defaults to 1\n            old_count_orig = int(m.group(2)) if m.group(2) else 1\n            new_start = int(m.group(3))\n            new_count_orig = int(m.group(4)) if m.group(4) else 1\n            extra = m.group(5)\n\n            correct_offset = None\n            for offset in range(-fuzz, fuzz+1):\n                start = max(0, old_start + offset - 1)\n                end = min(len(lines) - 1, old_start + old_count_orig + offset - 1)\n                \n                if any([not source.strip() == line.strip() for (source, line) in zip(lines[start:end], init_hunk_lines)]):\n                    continue\n\n                correct_offset = offset\n                break\n\n            if correct_offset is None:\n                raise Exception(\"Failed fuzzing\")\n            \n            new_header = f\"@@ -{old_start + correct_offset},{old_count_orig} +{new_start + correct_offset},{new_count_orig} @@ {extra}\"\n            \n            # Try matching init lines with the source in a sliding window [-fuzz:fuzz]\n            # If successful - return hunk with corrected start string\n            hunks_dictionary[filepath] += \"\\n\".join([new_header] + hunk_lines[1:])\n        # Otherwise save it as is\n        except Exception as e:\n            hunks_dictionary[filepath] += \"\\n\".join(hunk_lines)\n    \n    fuzzed_patch_string = \"\"\n    for k, v in hunks_dictionary.items():\n        fuzzed_patch_string += f\"--- a{k}\\n+++ b{k}\\n{v}\\n\"\n    \n    return fuzzed_patch_string","metadata":{"_uuid":"5dcae870-2699-4110-956b-121c8687bfa9","_cell_guid":"a2564919-7162-4711-a5c6-92077938254f","trusted":true,"execution":{"iopub.status.busy":"2025-03-11T14:21:32.759907Z","iopub.execute_input":"2025-03-11T14:21:32.760101Z","iopub.status.idle":"2025-03-11T14:21:32.770352Z","shell.execute_reply.started":"2025-03-11T14:21:32.760084Z","shell.execute_reply":"2025-03-11T14:21:32.769763Z"}},"outputs":[],"execution_count":null},{"cell_type":"code","source":"def has_no_changes(patch_string):\n    # Check if patch contains at least one + or -\n\n    in_hunk = False\n\n    diff_lines = patch_string.split('\\n')\n    for line in diff_lines:\n        if line.startswith('@@ '):\n            # New hunk starts; process the previous one if it exists.\n            in_hunk = True\n        elif in_hunk and (line.startswith('-') or line.startswith('+')):\n            return True\n        else:\n            # Lines outside hunks (like file header lines) are output as-is.\n            if in_hunk:\n                in_hunk = False\n\n    return False","metadata":{"trusted":true,"execution":{"iopub.status.busy":"2025-03-11T14:21:32.771017Z","iopub.execute_input":"2025-03-11T14:21:32.771215Z","iopub.status.idle":"2025-03-11T14:21:32.784377Z","shell.execute_reply.started":"2025-03-11T14:21:32.771199Z","shell.execute_reply":"2025-03-11T14:21:32.783793Z"}},"outputs":[],"execution_count":null},{"cell_type":"code","source":"def extract_patch_string(text: str) -> Optional[str]:\n    pattern: str = r\"\\n```diff\\n(.*?)\\n```\"\n    matches: List[str] = re.findall(pattern, text, re.DOTALL)\n    if matches is None or len(matches) == 0:\n        return None\n    initial_string = matches[-1] + \"\\n\"\n\n    if has_no_changes(initial_string):\n        return None\n    \n    patch_string = recalc_diff(initial_string.split(\"\\n\"))\n    patch_string = try_fuzz_in(patch_string)\n    \n    return patch_string","metadata":{"_uuid":"5dcae870-2699-4110-956b-121c8687bfa9","_cell_guid":"a2564919-7162-4711-a5c6-92077938254f","trusted":true,"execution":{"iopub.status.busy":"2025-03-11T14:21:32.785034Z","iopub.execute_input":"2025-03-11T14:21:32.785229Z","iopub.status.idle":"2025-03-11T14:21:32.79412Z","shell.execute_reply.started":"2025-03-11T14:21:32.785212Z","shell.execute_reply":"2025-03-11T14:21:32.79354Z"}},"outputs":[],"execution_count":null},{"cell_type":"markdown","source":"To make sure ToT is effective branched prompts are always different choosing different strategies each time to ensure the state space is explored properly.","metadata":{}},{"cell_type":"code","source":"patching_strategies = [\n    \"\"\"\n1. Analyze the initial problem and restore the calls that lead to it with proposed relevant files.\n2. Come up with a solution that will fix the problem without any side effects.\n3. Write it as a minimalistic diff patch.\n    \"\"\",\n    \"\"\"\n1. Break the problem into sub-issues (e.g., \"Isolate the bug to module X\").\n2. Solve each sub-issue independently.\n3. Combine fixes into a cohesive patch.\n4. Verify no integration conflicts arise.\n    \"\"\",\n    \"\"\"\n1. Propose ~3 hypotheses for the root cause (e.g., \"Race condition?\").\n2. Design tests to validate/invalidate each hypothesis.\n3. Eliminate invalid hypotheses.\n4. Fix the surviving hypothesis.\n    \"\"\",\n    \"\"\"\n1. Propose 2-3 alternative code changes (e.g., \"Fix via regex vs. string parsing\").\n2. Simulate the outcomes of each.\n3. Rank solutions by efficiency, readability, and side effects.\n4. Select the optimal implementation.\n    \"\"\",\n    \"\"\"\n1. Trace the error to its origin (e.g., \"Why does this function return `None`?\").\n2. Fix the root cause, not symptoms.\n3. Validate upstream/downstream dependencies.\n    \"\"\",\n    \"\"\"\n1. Generate a minimal \"quick fix\" (e.g., add a null check).\n2. Generate a \"refactor\" (e.g., redesign error handling).\n3. Compare risks/rewards of each.\n4. Choose based on project priorities (stability vs. scalability).\n    \"\"\",\n]","metadata":{"trusted":true,"execution":{"iopub.status.busy":"2025-03-11T14:21:32.794933Z","iopub.execute_input":"2025-03-11T14:21:32.795148Z","iopub.status.idle":"2025-03-11T14:21:32.804195Z","shell.execute_reply.started":"2025-03-11T14:21:32.79513Z","shell.execute_reply":"2025-03-11T14:21:32.803532Z"}},"outputs":[],"execution_count":null},{"cell_type":"code","source":"patching_prompt: str = (\n    \"\"\"\nYou will be implementing a git diff patch to solve an issue with the code repository.\nThis is the problem statement.\n\n{problem_statement}\n\nThese are the files that are thought to be relevant\n\n{file_content_string}\n\n{strategy}\n\nExample:\n\n```diff\n--- a/first.txt\n+++ b/first.txt\n@@ -1,3 +1,3 @@\n start\n-first change\n+new first change\n middle\n@@ -7,4 +7,4 @@\n some content\n-second change\n+new second change\n more content\n--- a/second.txt\n+++ b/second.txt\n@@ -1,3 +1,3 @@\n beginning\n-old line\n+new line\n end\n```\n\nReminder\n- Put your diff within ```diff and ``` and make sure the diff represents your changes accurately.\n- Do not edit the test files.\n- Only the last diff printed will be considered. Use it to your advantage to think of multiple solutions.\n\"\"\".strip()\n)\n\nimport re\n\n\ndef get_patch_string(\n    problem_statement: str, file_content_strings: List[str]\n) -> Tuple[List[str], List[Optional[str]]]:\n    sampling_params: SamplingParams = SamplingParams(\n        temperature=0.6,  # randomness of the sampling\n        min_p=0.01,\n        top_p=0.95,\n        skip_special_tokens=True,  # Whether to skip special tokens in the output\n        max_tokens=MAX_TOKENS,\n    )\n\n    inference_idx_to_input_idx: list[int] = [\n        input_idx\n        for input_idx, file_content_string in enumerate(file_content_strings)\n        # if file_content_string != \"\"\n    ]\n\n    list_of_messages: List[List[Dict[str, str]]] = [\n        [\n            {\n                \"role\": \"user\",\n                \"content\": patching_prompt.format(\n                    problem_statement=problem_statement[:20_000],\n                    file_content_string=file_content_strings[input_idx][:30_000],\n                    strategy=random.choice(patching_strategies)\n                ),\n            },\n        ]\n        for input_idx in inference_idx_to_input_idx\n    ]\n\n    prompt_texts: List[str] = [\n        (\n            tokenizer.apply_chat_template(\n                conversation=messages, tokenize=False, add_generation_prompt=True\n            )  # type: ignore\n        )\n        + \"<think>\\n\"\n        for messages in list_of_messages\n    ]\n\n    print(\"get_patch_string\", [count_tokens(text) for text in prompt_texts])\n    request_outputs: list[RequestOutput] = llm.generate(\n        prompt_texts, sampling_params=sampling_params\n    )\n\n    if (\n        os.getenv(\"KAGGLE_KERNEL_RUN_TYPE\") == \"Interactive\"\n        and not os.getenv(\"KAGGLE_IS_COMPETITION_RERUN\")\n    ):\n        print(prompt_texts[0])\n        print(request_outputs[0].outputs[0].text)\n    \n    response_texts_from_inference: List[str] = [\n        request_output.outputs[0].text for request_output in request_outputs\n    ]\n    print(\n        \"get_patch_string\",\n        [count_tokens(text) for text in response_texts_from_inference],\n    )\n\n    patch_strings_from_inference: List[Optional[str]] = [\n        extract_patch_string(response_text)\n        for response_text in response_texts_from_inference\n    ]\n\n    patch_strings: List[Optional[str]] = [None for _ in file_content_strings]\n    for inference_idx, patch_string in enumerate(patch_strings_from_inference):\n        input_idx = inference_idx_to_input_idx[inference_idx]\n        patch_strings[input_idx] = patch_string\n\n    return patch_strings","metadata":{"_uuid":"3229d17a-0142-4003-8b3c-ba42ae72d4d9","_cell_guid":"2000b5e2-13f3-4b86-8743-4aff8a950f2c","trusted":true,"execution":{"iopub.status.busy":"2025-03-11T14:21:32.804792Z","iopub.execute_input":"2025-03-11T14:21:32.805Z","iopub.status.idle":"2025-03-11T14:21:32.8145Z","shell.execute_reply.started":"2025-03-11T14:21:32.804982Z","shell.execute_reply":"2025-03-11T14:21:32.813866Z"}},"outputs":[],"execution_count":null},{"cell_type":"code","source":"import re\nimport sys\n\ndef recalc_hunk(hunk_lines):\n    \"\"\"\n    Given a hunk (list of lines with a unified diff hunk header as first line),\n    recalculate the counts for removed (old) and added (new) lines.\n    \"\"\"\n    header_line = hunk_lines[0]\n    # Match header of the form: @@ -<old_start>[,<old_count>] +<new_start>[,<new_count>] @@[ optional text]\n    m = re.match(r'^@@ -(\\d+)(?:,(\\d+))? \\+(\\d+)(?:,(\\d+))? @@(.*)$', header_line)\n    if not m:\n        # If header doesn't match expected format, return as-is\n        return hunk_lines\n\n    old_start = int(m.group(1))\n    # If count isn’t given, it defaults to 1\n    old_count_orig = int(m.group(2)) if m.group(2) else 1\n    new_start = int(m.group(3))\n    new_count_orig = int(m.group(4)) if m.group(4) else 1\n    extra = m.group(5)\n\n    # Recalculate counts based on the hunk's content.\n    recalculated_old = 0\n    recalculated_new = 0\n    for line in hunk_lines[1:]:\n        if line.startswith(' '):\n            recalculated_old += 1\n            recalculated_new += 1\n        elif line.startswith('-'):\n            recalculated_old += 1\n        elif line.startswith('+'):\n            recalculated_new += 1\n        # Other lines (if any) are ignored\n\n    # Build a new header with the recalculated counts.\n    new_header = f\"@@ -{old_start},{recalculated_old} +{new_start},{recalculated_new} @@{extra}\"\n    return [new_header] + hunk_lines[1:]\n\ndef recalc_diff(diff_lines):\n    \"\"\"\n    Process the entire diff (as a list of lines), recalc each hunk header,\n    and return a new list of diff lines.\n    \"\"\"\n    new_diff = []\n    current_hunk = []\n    in_hunk = False\n\n    for line in diff_lines:\n        if line.startswith('@@ '):\n            # New hunk starts; process the previous one if it exists.\n            if current_hunk:\n                new_diff.extend(recalc_hunk(current_hunk))\n                current_hunk = []\n            current_hunk.append(line)\n            in_hunk = True\n        elif in_hunk and (line.startswith(' ') or line.startswith('+') or line.startswith('-')):\n            current_hunk.append(line)\n        else:\n            # Lines outside hunks (like file header lines) are output as-is.\n            if current_hunk:\n                new_diff.extend(recalc_hunk(current_hunk))\n                current_hunk = []\n                in_hunk = False\n            new_diff.append(line)\n    # Process any hunk still in progress.\n    if current_hunk:\n        new_diff.extend(recalc_hunk(current_hunk))\n    return '\\n'.join(new_diff)","metadata":{"trusted":true,"execution":{"iopub.status.busy":"2025-03-11T14:21:32.817235Z","iopub.execute_input":"2025-03-11T14:21:32.817447Z","iopub.status.idle":"2025-03-11T14:21:32.826496Z","shell.execute_reply.started":"2025-03-11T14:21:32.817429Z","shell.execute_reply":"2025-03-11T14:21:32.825892Z"}},"outputs":[],"execution_count":null},{"cell_type":"markdown","source":"It is important to eliminate hallucinations early. Healed version of the patch is checked for whether it could've been made from accessed snippets if it's not it is considered hallucinated and removed early.","metadata":{}},{"cell_type":"code","source":"from pathlib import Path\n\ndef is_hallucinated(patch_string, snippets_dict):\n    # Parse the patch:\n    # Split it into different files and into different snippets\n    hunks = []\n\n    current_filename = \"\"\n    current_hunk = []\n\n    in_hunk = False\n\n    diff_lines = patch_string.split('\\n')\n    for line in diff_lines:\n        if line.startswith('@@ '):\n            # New hunk starts; process the previous one if it exists.\n            if current_hunk:\n                hunks.append((current_filename, current_hunk))\n                current_hunk = []\n            current_hunk.append(line)\n            in_hunk = True\n        elif in_hunk and (line.startswith(' ') or line.startswith('-')): # We omit `or line.startswith('+')`\n            current_hunk.append(line)\n        else:\n            # Lines outside hunks (like file header lines) are output as-is.\n            if current_hunk:\n                hunks.append((current_filename, current_hunk))\n                current_hunk = []\n                in_hunk = False\n            if line.startswith('---'):\n                current_filename = REPO_PATH + line[5:]\n    if current_hunk:\n        hunks.append((current_filename, current_hunk))\n    \n    errors = []\n    # If any of the checks fail do not short circuit - accumulate the errors for the feedback\n    for i, (filepath, hunk_lines) in enumerate(hunks):\n        # Restore initial data (according to the diff):\n        header_line = hunk_lines[0]\n        metadata = re.match(r'^@@ -(\\d+)(?:,(\\d+))? \\+(\\d+)(?:,(\\d+))? @@(.*)$', header_line)\n        if not metadata:\n            errors.append(f\"Hunk #{i + 1} has malformed header\")\n            continue\n\n        start = int(metadata.group(1))\n        count_orig = int(metadata.group(2)) if metadata.group(2) else 1\n        end = start + count_orig - 1\n\n        if not filepath in snippets_dict:\n            errors.append(f\"Hunk #{i + 1} is from file that was not read\")\n            continue\n\n        snippets = snippets_dict[filepath]\n\n        # 1. Check if there is a snippet that covers all those lines\n        source_snippet = None\n        for snippet in snippets:\n            if snippet[0][0] <= start and snippet[-1][0] >= end:\n                source_snippet = snippet\n                break\n\n        # 2. Check if restored contents actually match the snippet content\n        if source_snippet is None:\n            errors.append(f\"Hunk #{i + 1} contains lines that were not read\")\n            continue\n\n        _, source_lines = zip(*snippet[start - source_snippet[0][0]:end - source_snippet[0][0]])\n        if any([not source.strip() == line.strip() for (source, line) in zip(source_lines, hunk_lines[1:])]):\n            errors.append(f\"Hunk #{i + 1} contents do not match the source code\")\n            continue\n    \n    # And return it in the end \n\n    if len(errors) == 0: \n        return False, \"\"\n    else:\n        return True, \"\\n\".join(errors)\n\ndef is_valid_patch_format(patch_string: str) -> bool:\n    \"\"\"\n    A quick check to confirm if a patch could be valid.\n    \"\"\"\n    if not(isinstance(patch_string, str)):\n        return False, \"Object is not a string\"\n    try:\n        patch_set = unidiff.PatchSet(patch_string)\n        if len(patch_set) == 0:\n            return False, \"Zero length string\"\n    except Exception as e:\n        return False, \"Exception processing a patch: \" + str(e)\n    return True, None\n\n\ndef patch_dry_run_succeeds(patch_string: str, repo_path: str = REPO_PATH, fuzz=0, timeout: int = 30) -> bool:\n    \"\"\"\n    A robust check if the patch will proceed without any errors.\n    Should be run after `is_valid_patch_format()`: the patch\n    command can hang if the inputs are sufficiently invalid.\n\n    Args:\n        patch_path: Path to a file containing the patch.\n        repo_path: Path to the directory to be patched.\n        timeout: Number of seconds before the dry run will be cancelled.\n    \"\"\"\n    with open(\"patch.txt\", \"w\") as f:\n        f.write(patch_string)\n    patch_path = \"/kaggle/working/patch.txt\"\n\n    cmd = f\"patch --verbose --dry-run --fuzz={fuzz} -p1 -i {patch_path} -d {repo_path}\"\n    try:\n        result = subprocess.run(cmd, shell=True, text=True, timeout=timeout, capture_output=True)\n        \n        if not \"FAILED\" in result.stdout:\n            return True, \"\"\n        else:\n            errors = result.stdout.strip() + \"\\n\" + result.stderr.strip()\n            return False, errors\n    except Exception as e:\n        return False, str(e)","metadata":{"_uuid":"5f229582-95fc-48d2-ac8e-27e71fd5e4c9","_cell_guid":"b7e7aec9-62b4-4dc2-af35-b8f01bdcff73","trusted":true,"execution":{"iopub.status.busy":"2025-03-11T14:21:32.827528Z","iopub.execute_input":"2025-03-11T14:21:32.827735Z","iopub.status.idle":"2025-03-11T14:21:32.839406Z","shell.execute_reply.started":"2025-03-11T14:21:32.827718Z","shell.execute_reply":"2025-03-11T14:21:32.83881Z"}},"outputs":[],"execution_count":null},{"cell_type":"markdown","source":"To enrich feedback loop verification step is performed not as simple voting, but rather as peer-review where each answer is augmented by the comment on a decision.\n\nTo make verification prompts lighter in worst case they'll be running with reduced max tokens. They can be ran with a lighter/faster model as well.\n\nTo avoid bias towards either of the answers and increase granularity model is asked to provide a score rather than 'Yes' or 'No'. Answer can be crisped afterwards.","metadata":{}},{"cell_type":"code","source":"verification_strategies = [\n    \"\"\"\nEvaluate whether the patch fully solves the problem:\n- The patch fully fixes the problem described in the issue.\n- The patch does not modify any test files or binaries.\n- The patch does not introduce any side effects or cause other tests to fail.\n    \"\"\",\n    \"\"\"\nAssess the patch's effectiveness:\n- Selected relevant files are on point.\n- The patch completely resolves the reported issue and very concisely.\n- It does not cause any unintended side effects or additional test failures.\n    \"\"\",\n    \"\"\"\nReview the patch to ensure proper functionality:\n- The patch correctly identifies the root of the problem.\n- It alters only the relevant files.\n- It resolves the problem, not its symptoms.\n    \"\"\",\n    \"\"\"\nVerify the patch integrity:\n- The patch is not a partial fix (in context of this problem).\n- It preserves the state of test files.\n- It does not lead to new issues or test failures.\n    \"\"\",\n    \"\"\"\nAnalyze the resulting patch:\n- The patch resolves the issue and is understandable.\n- It does not modify files that are not affected.\n- Produced code is maintainable and clear, no ninja-coding.\n    \"\"\",\n]","metadata":{"trusted":true,"execution":{"iopub.status.busy":"2025-03-11T14:21:32.840067Z","iopub.execute_input":"2025-03-11T14:21:32.840272Z","iopub.status.idle":"2025-03-11T14:21:32.851622Z","shell.execute_reply.started":"2025-03-11T14:21:32.840255Z","shell.execute_reply":"2025-03-11T14:21:32.850945Z"}},"outputs":[],"execution_count":null},{"cell_type":"code","source":"verifying_prompt: str = (\n    \"\"\"\nThis is the problem statement.\n\n{problem_statement}\n\nThese are the files that are thought to be relevant.\n\n{file_content_string}\n\nThis is the proposed patch to fix the problem.\n\n{patch_string}\n\n{strategy}\n\nConsider counter examples and possible undiscovered related issues. Analyze relevant files for completeness.\nRepresent all the pros and cons in a score. \nEnd your response with a short review of the patch. \nBe consistent about it, if you don't give a perfect score you must mention an issue and give a hint on what needs to be done to score max,\nif you give the lowest score you can't praise the answer.\nDo NOT lower the score for potential issues if you can't provide any example into your review, eapecially if it's out of the scope of the issue.\n\nReview template:\n\n<root>\n    <comment>Your point on why that patch will work</comment>\n    <score>Your score from 1 to 10 of this patch</score>\n</root>\n\"\"\".strip()\n)","metadata":{"trusted":true,"execution":{"iopub.status.busy":"2025-03-11T14:21:32.852265Z","iopub.execute_input":"2025-03-11T14:21:32.852466Z","iopub.status.idle":"2025-03-11T14:21:32.860791Z","shell.execute_reply.started":"2025-03-11T14:21:32.852448Z","shell.execute_reply":"2025-03-11T14:21:32.860208Z"}},"outputs":[],"execution_count":null},{"cell_type":"markdown","source":"To provide deterministic scepticism following changes are made to the scoring system:\n* Skip is scored as 0 as it is the most favorable of wrong outputs and the default one too\n* Even positive-scoring answers do not become new best-answer by default as they need to pass the \"votes threshold\"","metadata":{}},{"cell_type":"code","source":"import unidiff\nimport subprocess\n\n\ndef choose_patch_string(\n    patch_strings: list[Optional[str]], repo_path: str, problem_statement, file_content_strings, snippets_dictionary,\n    best_score = 0, best_patch_string = None\n) -> tuple[list[int], list[str], Optional[str]]:\n    threshold = VALIDATION_COPY_COUNT - 1\n    \n    scores = []\n    reviews = []\n\n    def get_peer_review(judge_response: str):\n        import xml.etree.ElementTree as ET\n        pattern: str = r\"<root>(.*?)</root>\"\n        matches: List[str] = re.findall(pattern, judge_response, re.DOTALL)\n    \n        try:\n            match = matches[-1]\n            # Parse the XML\n            root = ET.fromstring(\"<root>\" + match + \"</root>\")\n\n            score = root.find(\"score\")\n            if score is not None and score.text is not None and score.text.isdigit():\n                label = True if int(score.text) > 9 else False \n            else:\n                return None, \"\"\n            \n            review = root.find(\"comment\")\n            if review is not None and review.text is not None:\n                review = review.text\n        \n        except:\n            return None, \"\"\n    \n        return label, review\n    \n    def score_judges(patch_string: str, file_content_string: str) -> tuple[str, str]:\n        sampling_params: SamplingParams = SamplingParams(\n            temperature=0.6,  # randomness of the sampling\n            min_p=0.01,\n            top_p=0.95,\n            skip_special_tokens=True,  # Whether to skip special tokens in the output\n            max_tokens=MAX_TOKENS // 2,\n        )\n\n        list_of_messages: List[List[Dict[str, str]]] = [\n            [\n                {\n                    \"role\": \"user\",\n                    \"content\": verifying_prompt.format(\n                        problem_statement=problem_statement[:20_000],\n                        file_content_string=file_content_string[:30_000],\n                        patch_string=patch_string,\n                        strategy=random.choice(verification_strategies)\n                    ),\n                },\n            ]\n            for input_idx in range(VALIDATION_COPY_COUNT)\n        ]\n    \n        prompt_texts: List[str] = [\n            (\n                tokenizer.apply_chat_template(\n                    conversation=messages, tokenize=False, add_generation_prompt=True\n                )  # type: ignore\n            )\n            + \"<think>\\n\"\n            for messages in list_of_messages\n        ]\n    \n        print(\"get_verification\", [count_tokens(text) for text in prompt_texts])\n        request_outputs: list[RequestOutput] = llm.generate(\n            prompt_texts, sampling_params=sampling_params\n        )\n\n        if (\n            os.getenv(\"KAGGLE_KERNEL_RUN_TYPE\") == \"Interactive\"\n            and not os.getenv(\"KAGGLE_IS_COMPETITION_RERUN\")\n        ):\n            print(prompt_texts[0])\n            print(request_outputs[0].outputs[0].text)\n            \n        response_texts: List[str] = [\n            request_output.outputs[0].text for request_output in request_outputs\n        ]\n        print(\"get_verification\", [count_tokens(text) for text in response_texts])\n\n        score = 0\n        total_review = \"\"\n\n        for i, response in enumerate(response_texts):\n            passes, review = get_peer_review(response)\n\n            if passes is None:\n                total_review += f\"Reviewer {i}: No response\"\n                continue\n            \n            if passes:\n                score += 1\n\n            total_review += f\"Reviewer {i}, {'Passed' if passes else 'Not passed'}: {review}\\n\"\n\n        total_review = f\"({score}/{VALIDATION_COPY_COUNT})\" + total_review\n        \n        return score, total_review\n        \n    \n    for (patch_string, file_content_string) in zip(patch_strings, file_content_strings):\n        \n        if best_score == VALIDATION_COPY_COUNT or patch_string is None or patch_string == \"\":\n            score = 0\n            scores.append(score)\n            reviews.append(f\"({score}) No patch proposed. Skip.\")\n            continue\n\n        hallucinated, e = is_hallucinated(patch_string, snippets_dictionary)\n        if hallucinated:\n            score = -3\n            scores.append(score)\n            reviews.append(f\"(score) Diff contains hallucinations: {e}\")\n            continue\n        \n        valid, e = is_valid_patch_format(patch_string)\n        if not valid:\n            score = -2\n            scores.append(score)\n            reviews.append(f\"(score) Invalid diff format: {e}\")\n            continue\n\n        dry_run, e = patch_dry_run_succeeds(patch_string, repo_path)\n        if not dry_run:\n            score = -1\n            scores.append(score)\n            reviews.append(f\"(score) Dry run fails: {e}\")\n            continue\n        \n        score, review = score_judges(patch_string, file_content_string)\n        scores.append(score)\n        reviews.append(review)\n        \n        if score > best_score and score > threshold:\n            best_score = score\n            best_patch_string = patch_string\n\n    return scores, reviews, best_score, best_patch_string","metadata":{"_uuid":"ac627a45-b48c-4bc3-b3e8-ff0ee18b3fc6","_cell_guid":"9814b304-d64c-4d61-b1d7-a4ab7b85496f","trusted":true,"execution":{"iopub.status.busy":"2025-03-11T14:21:32.861462Z","iopub.execute_input":"2025-03-11T14:21:32.861677Z","iopub.status.idle":"2025-03-11T14:21:32.874213Z","shell.execute_reply.started":"2025-03-11T14:21:32.861659Z","shell.execute_reply":"2025-03-11T14:21:32.873625Z"}},"outputs":[],"execution_count":null},{"cell_type":"code","source":"refinement_prompt: str = (\n    \"\"\"\nYou will be implementing a git diff patch to solve an issue with the code repository.\nThis is the problem statement.\n\n{problem_statement}\n\nThese are the files that are thought to be relevant\n\n{file_content_string}\n\nPreviously you have proposed the following patch\n\n{previous_iteration}\n\nWhich was evaluated with the following review \n\n{review}\n\nHere negative score means that patch is confirmed incorrect and positive score means that there is a chance that it will succeed. If it has done \nto review phase you will also have a list of peer reviews. You need to try to pass all of them.\n\nAnalyze your previous answer, check it for possible errors, pros and cons.\n{strategy}\n\nExample:\n\n```diff\n--- a/first.txt\n+++ b/first.txt\n@@ -1,3 +1,3 @@\n start\n-first change\n+new first change\n middle\n@@ -7,4 +7,4 @@\n some content\n-second change\n+new second change\n more content\n--- a/second.txt\n+++ b/second.txt\n@@ -1,3 +1,3 @@\n beginning\n-old line\n+new line\n end\n```\n\nReminder\n- Put your diff within ```diff and ``` and make sure the diff represents your changes accurately.\n- Do not edit the test files.\n- Only the last diff printed will be considered. Use it to your advantage to think of multiple solutions.\n\"\"\".strip()\n)\n\nimport re\n\n\ndef refine_patch_string(\n    problem_statement: str, file_content_strings: List[str], patch_strings: List[str], reviews: List[str]\n) -> Tuple[List[str], List[Optional[str]]]:\n    sampling_params: SamplingParams = SamplingParams(\n        temperature=0.6,  # randomness of the sampling\n        min_p=0.01,\n        top_p=0.95,\n        skip_special_tokens=True,  # Whether to skip special tokens in the output\n        max_tokens=MAX_TOKENS,\n    )\n\n    inference_idx_to_input_idx: list[int] = [\n        input_idx\n        for input_idx, file_content_string in enumerate(file_content_strings)\n        # if file_content_string != \"\"\n    ]\n\n    list_of_messages: List[List[Dict[str, str]]] = [\n        [\n            {\n                \"role\": \"user\",\n                \"content\": refinement_prompt.format(\n                    problem_statement=problem_statement[:20_000],\n                    file_content_string=file_content_strings[input_idx][:30_000],\n                    previous_iteration=patch_strings[input_idx],\n                    review=reviews[input_idx],\n                    strategy=random.choice(patching_strategies)\n                ),\n            },\n        ]\n        for input_idx in inference_idx_to_input_idx\n    ]\n\n    prompt_texts: List[str] = [\n        (\n            tokenizer.apply_chat_template(\n                conversation=messages, tokenize=False, add_generation_prompt=True\n            )  # type: ignore\n        )\n        + \"<think>\\n\"\n        for messages in list_of_messages\n    ]\n\n    print(\"refine_patch_string\", [count_tokens(text) for text in prompt_texts])\n    request_outputs: list[RequestOutput] = llm.generate(\n        prompt_texts, sampling_params=sampling_params\n    )\n\n    if (\n        os.getenv(\"KAGGLE_KERNEL_RUN_TYPE\") == \"Interactive\"\n        and not os.getenv(\"KAGGLE_IS_COMPETITION_RERUN\")\n    ):\n        print(prompt_texts[0])\n        print(request_outputs[0].outputs[0].text)\n    \n    response_texts_from_inference: List[str] = [\n        request_output.outputs[0].text for request_output in request_outputs\n    ]\n    print(\n        \"refine_patch_string\",\n        [count_tokens(text) for text in response_texts_from_inference],\n    )\n    patch_strings_from_inference: List[Optional[str]] = [\n        extract_patch_string(response_text)\n        for response_text in response_texts_from_inference\n    ]\n\n    patch_strings: List[Optional[str]] = [None for _ in file_content_strings]\n    for inference_idx, patch_string in enumerate(patch_strings_from_inference):\n        input_idx = inference_idx_to_input_idx[inference_idx]\n        patch_strings[input_idx] = patch_string\n\n    return patch_strings","metadata":{"_uuid":"ac627a45-b48c-4bc3-b3e8-ff0ee18b3fc6","_cell_guid":"9814b304-d64c-4d61-b1d7-a4ab7b85496f","trusted":true,"execution":{"iopub.status.busy":"2025-03-11T14:21:32.874892Z","iopub.execute_input":"2025-03-11T14:21:32.875092Z","iopub.status.idle":"2025-03-11T14:21:32.886841Z","shell.execute_reply.started":"2025-03-11T14:21:32.875075Z","shell.execute_reply":"2025-03-11T14:21:32.886239Z"}},"outputs":[],"execution_count":null},{"cell_type":"markdown","source":"# Predict function","metadata":{"_uuid":"332ef3ee-d385-4103-8c68-d547dda443bf","_cell_guid":"d0812f8b-c4aa-47f0-a3be-36d135908ffc","trusted":true,"collapsed":false,"jupyter":{"outputs_hidden":false}}},{"cell_type":"markdown","source":"Branch-prune works as follows:\n* Branch current answers by querying the same queries multiple times (different seed, different strategy)\n* Optionally remove negative-scoring answers right after the scoring\n* Rank received outputs by the score and select the fraction based on the pruning factor\n* Repeat the used answer until the branching factor is restored\n\nWith the fact that validation can be interpreted as scoring posteriors of the model thoughts it can be considered a variant of [PoT](https://arxiv.org/pdf/2404.19055). ","metadata":{}},{"cell_type":"code","source":"import math\n\ndef backtracking_tot(scores, file_content_strings, patch_strings, reviews, history):\n    # update history with new entries\n    for (score, content, patch, review) in zip(scores, file_content_strings, patch_strings, reviews):\n        history.append((score, content, patch, review))\n\n    random.shuffle(history)\n    \n    n = int(BRANCHING_FACTOR * PRUNING_FACTOR)\n    # Select all time best N solutions\n    index = [i[0] for i in sorted(filter(lambda x: x[1][0] > 0, enumerate(history)), key=lambda x:-x[1][0])]\n    pruned_index = index[:n] if len(index) > 0 else [0]\n\n    scale = int(math.ceil(BRANCHING_FACTOR / len(pruned_index)))\n    pruned_index = (pruned_index * scale)[:BRANCHING_FACTOR]\n    print([history[i][0] for i in pruned_index])\n\n    return [history[i][1] for i in pruned_index], [history[i][2] for i in pruned_index], [history[i][3] for i in pruned_index], history","metadata":{"trusted":true,"execution":{"iopub.status.busy":"2025-03-11T14:21:32.887445Z","iopub.execute_input":"2025-03-11T14:21:32.887654Z","iopub.status.idle":"2025-03-11T14:21:32.898619Z","shell.execute_reply.started":"2025-03-11T14:21:32.887637Z","shell.execute_reply":"2025-03-11T14:21:32.898007Z"}},"outputs":[],"execution_count":null},{"cell_type":"code","source":"ACTUAL_TIMEOUT_ERROR_LIMIT = 60*30 - 60  # 30 minutes - 1 minute to guarantee proper timeout\nTEST_TIMEOUT_LIMIT = 60*18  # 18 minute timeout","metadata":{"trusted":true,"execution":{"iopub.status.busy":"2025-03-11T14:21:32.899185Z","iopub.execute_input":"2025-03-11T14:21:32.899378Z","iopub.status.idle":"2025-03-11T14:21:32.910824Z","shell.execute_reply.started":"2025-03-11T14:21:32.899362Z","shell.execute_reply":"2025-03-11T14:21:32.910254Z"}},"outputs":[],"execution_count":null},{"cell_type":"code","source":"def predict_inner(problem_statement: str, directory: str) -> Optional[str]:\n    t1 = time.time()\n    \n    directory_string = stringify_directory(directory)\n    test_files = get_test_paths(directory)\n    directory_string = \"\\n\".join([path for path in directory_string.split(\"\\n\") if path not in test_files])\n    \n    file_queries = get_selection_query(\n        directory_string, problem_statement\n    )\n    file_queries = get_consistent_query(file_queries)\n\n    file_content_strings, _ =  zip(*[\n        fetch_code_contents(code_query) for code_query in file_queries\n    ])\n\n    # Scaling the selections\n    for _ in range(2):\n        file_queries = get_selection_query(\n            directory_string, problem_statement, file_content_strings * BATCH_SIZE\n        )\n        file_queries = get_consistent_query(file_queries)\n    \n        file_content_strings, snippets_dictionaries = zip(*[\n            fetch_code_contents(code_query) for code_query in file_queries\n        ])\n        snippets_dictionary = snippets_dictionaries[0]\n    # ---------------------------\n    \n    if file_content_strings[0].strip().count(\"No matches found.\") == file_content_strings[0].strip().count(\"[file name]:\"):\n        print(\"Failed file extraction\")\n        return None\n    \n    file_content_strings = file_content_strings * BRANCHING_FACTOR\n    patch_strings = get_patch_string(\n        problem_statement, file_content_strings\n    )\n\n    scores, reviews, best_score, patch_string = choose_patch_string(patch_strings, directory, problem_statement, \n                                                                    file_content_strings, snippets_dictionary)\n    print(scores)\n\n    history = []\n    file_content_strings, patch_strings, reviews, history = backtracking_tot(scores, file_content_strings, patch_strings, reviews, history)\n    \n    # Scaling the patches\n    for _ in range(3):\n        delta = (time.time() - t1)\n        print(f\"({delta})s/({TEST_TIMEOUT_LIMIT})s\")\n        \n        if delta > TEST_TIMEOUT_LIMIT:\n            print(f\"Timed out\")\n            break\n\n        if (all([s <= 0 for s in scores])):\n            break\n        \n        if (VALIDATION_COPY_COUNT in scores):\n            break\n        \n        patch_strings = refine_patch_string(\n            problem_statement, file_content_strings, patch_strings, reviews\n        )\n    \n        scores, reviews, best_score, patch_string = choose_patch_string(\n            patch_strings, directory, problem_statement, file_content_strings, snippets_dictionary, best_score, patch_string\n        )\n        print(scores)\n\n        file_content_strings, patch_strings, reviews, history = backtracking_tot(scores, file_content_strings, patch_strings, reviews, history)\n    # ---------------------------\n    \n    return patch_string","metadata":{"_uuid":"d5aa7692-14fa-46cb-81aa-4a05d2990df4","_cell_guid":"41d164a7-440a-4b3d-b82b-9473575c89a4","trusted":true,"execution":{"iopub.status.busy":"2025-03-11T14:21:32.911467Z","iopub.execute_input":"2025-03-11T14:21:32.911678Z","iopub.status.idle":"2025-03-11T14:21:32.920798Z","shell.execute_reply.started":"2025-03-11T14:21:32.91166Z","shell.execute_reply":"2025-03-11T14:21:32.920214Z"}},"outputs":[],"execution_count":null},{"cell_type":"code","source":"import io\nfrom typing import Optional, List\n\nskip_prediction: bool = False\n\n\ndef predict(\n    problem_statement: str,\n    repo_archive: io.BytesIO,\n    pip_packages_archive: io.BytesIO,\n    env_setup_cmds_templates: List[str],\n) -> Optional[str]:\n    \"\"\"Replace this function with your inference code.\n    Args:\n        problem_statement: The text of the git issue.\n        repo_archive: A BytesIO buffer path with a .tar containing the codebase that must be patched. The gateway will make this directory available immediately before this function runs.\n    \"\"\"\n    if (allowed_time[-1] - time.time()) < 1800:\n        return None\n    \n    global skip_prediction\n    if skip_prediction:\n        return None\n\n    try:\n        with open(\"repo_archive.tar\", \"wb\") as f:\n            f.write(repo_archive.read())\n        repo_path: str = REPO_PATH\n        if os.path.exists(repo_path):\n            shutil.rmtree(repo_path)\n        shutil.unpack_archive(\"repo_archive.tar\", extract_dir=repo_path)\n        os.remove(\"repo_archive.tar\")\n        \n        patch_string: Optional[str] = None\n        patch_string = predict_inner(problem_statement=problem_statement, directory=repo_path)\n        shutil.rmtree(repo_path)\n    except Exception as e:\n        print(e)\n        patch_string: Optional[str] = None\n        \n    if not os.getenv(\"KAGGLE_IS_COMPETITION_RERUN\"):\n        skip_prediction = True\n\n    print(\"submitted patch_string\")\n    print(patch_string)\n\n    if patch_string is None:\n        return None\n\n    return patch_string\n    ","metadata":{"_uuid":"1fe33c0a-f4bb-4d58-a31a-8a35efed47f4","_cell_guid":"f6603ce1-36ca-4c32-b6b7-55d970a38851","trusted":true,"execution":{"iopub.status.busy":"2025-03-11T14:21:32.921401Z","iopub.execute_input":"2025-03-11T14:21:32.921609Z","iopub.status.idle":"2025-03-11T14:21:32.933579Z","shell.execute_reply.started":"2025-03-11T14:21:32.921592Z","shell.execute_reply":"2025-03-11T14:21:32.932999Z"}},"outputs":[],"execution_count":null},{"cell_type":"markdown","source":"# Get predict data without server","metadata":{}},{"cell_type":"code","source":"import zipfile\n\n# !mkdir -p /kaggle/tmp/konwinski-prize-alt\nos.makedirs(\"/kaggle/tmp/konwinski-prize-alt\", exist_ok=True)\n\n# !unzip -q -o /kaggle/input/konwinski-prize/data.a_zip -d /kaggle/tmp/konwinski-prize-alt/ 2>/dev/null || true\ntry:\n    with zipfile.ZipFile(\"/kaggle/input/konwinski-prize/data.a_zip\", \"r\") as zip_ref:\n        zip_ref.extractall(\"/kaggle/tmp/konwinski-prize-alt/\")\nexcept Exception as e:\n    print(e)\n    pass","metadata":{"trusted":true,"execution":{"iopub.status.busy":"2025-03-11T14:21:32.934233Z","iopub.execute_input":"2025-03-11T14:21:32.934431Z","iopub.status.idle":"2025-03-11T14:21:37.781937Z","shell.execute_reply.started":"2025-03-11T14:21:32.934414Z","shell.execute_reply":"2025-03-11T14:21:37.781195Z"}},"outputs":[],"execution_count":null},{"cell_type":"code","source":"def get_problem(problem_index: int) -> Tuple[str, str, io.BytesIO]:\n    df = pd.read_parquet(\"/kaggle/tmp/konwinski-prize-alt/data/data.parquet\")\n\n    problem_statement: str = df[\"problem_statement\"][problem_index]\n    repo_path: str = (\n        f\"/kaggle/tmp/konwinski-prize-alt/data/repos/repo__{df['instance_id'][problem_index]}\"\n    )\n\n    import shutil\n    import tempfile\n\n    with tempfile.TemporaryDirectory() as tmpdir:\n        shutil.make_archive(os.path.join(tmpdir, \"a_repo\"), \"tar\", repo_path)\n        with open(os.path.join(tmpdir, \"a_repo.tar\"), \"rb\") as f:\n            repo_archive = io.BytesIO(f.read())\n\n    return problem_statement, repo_path, repo_archive","metadata":{"trusted":true,"execution":{"iopub.status.busy":"2025-03-11T14:21:37.782619Z","iopub.execute_input":"2025-03-11T14:21:37.782837Z","iopub.status.idle":"2025-03-11T14:21:37.787106Z","shell.execute_reply.started":"2025-03-11T14:21:37.782819Z","shell.execute_reply":"2025-03-11T14:21:37.786534Z"}},"outputs":[],"execution_count":null},{"cell_type":"code","source":"demo_problem_index: int = 3\n\nif os.getenv(\"KAGGLE_KERNEL_RUN_TYPE\") == \"Interactive\" and not os.getenv(\n    \"KAGGLE_IS_COMPETITION_RERUN\"\n):\n    problem_statement, repo_path, repo_archive = get_problem(\n        problem_index=demo_problem_index\n    )\n\n    print(repo_path)\n    print(problem_statement)\n    print(len(list(repo_archive)))\n    print(len(list(repo_archive)))","metadata":{"trusted":true,"execution":{"iopub.status.busy":"2025-03-11T14:21:37.787766Z","iopub.execute_input":"2025-03-11T14:21:37.787966Z","iopub.status.idle":"2025-03-11T14:21:38.709281Z","shell.execute_reply.started":"2025-03-11T14:21:37.787948Z","shell.execute_reply":"2025-03-11T14:21:38.708564Z"}},"outputs":[],"execution_count":null},{"cell_type":"code","source":"if os.getenv(\"KAGGLE_KERNEL_RUN_TYPE\") == \"Interactive\" and not os.getenv(\n    \"KAGGLE_IS_COMPETITION_RERUN\"\n):\n    skip_prediction = False\n    problem_statement, repo_path, repo_archive = get_problem(\n        problem_index=demo_problem_index\n    )\n    patch_string = predict(problem_statement, repo_archive, io.BytesIO(), [])","metadata":{"trusted":true,"execution":{"iopub.status.busy":"2025-03-11T14:21:38.71003Z","iopub.execute_input":"2025-03-11T14:21:38.710262Z","iopub.status.idle":"2025-03-11T14:38:22.575613Z","shell.execute_reply.started":"2025-03-11T14:21:38.710244Z","shell.execute_reply":"2025-03-11T14:38:22.574845Z"}},"outputs":[],"execution_count":null},{"cell_type":"code","source":"if (\n    os.getenv(\"KAGGLE_KERNEL_RUN_TYPE\") == \"Interactive\"\n    and not os.getenv(\"KAGGLE_IS_COMPETITION_RERUN\")\n    and patch_string is not None\n):\n    import polars as pl\n\n    df = pl.read_parquet(\"/kaggle/tmp/konwinski-prize-alt/data/data.parquet\")\n\n    import kaggle_evaluation.konwinski_prize_gateway\n\n    k_prize_gateway = kaggle_evaluation.konwinski_prize_gateway.KPrizeGateway()\n    k_prize_gateway.unpack_data_paths()\n\n    results = k_prize_gateway._evaluate_instance(\n        instance=df.row(demo_problem_index, named=True),\n        patch=patch_string,\n    )\n\n    from collections import Counter\n    print(\n        demo_problem_index, Counter(result.unit_test_outcome for result in results[1:])\n    )","metadata":{"trusted":true,"execution":{"iopub.status.busy":"2025-03-11T14:38:22.576294Z","iopub.execute_input":"2025-03-11T14:38:22.57653Z","iopub.status.idle":"2025-03-11T14:38:22.580808Z","shell.execute_reply.started":"2025-03-11T14:38:22.57651Z","shell.execute_reply":"2025-03-11T14:38:22.580145Z"}},"outputs":[],"execution_count":null},{"cell_type":"code","source":"if (\n    os.getenv(\"KAGGLE_KERNEL_RUN_TYPE\") == \"Interactive\"\n    and not os.getenv(\"KAGGLE_IS_COMPETITION_RERUN\")\n    and patch_string is not None\n):\n    from kaggle_evaluation.konwinski_prize_gateway import UnitTestOutcome\n\n    for result in results[1:]:\n        if result.unit_test_outcome != UnitTestOutcome.PASSED:\n            print(result.test_name)\n            print(result.fail_description)","metadata":{"trusted":true,"execution":{"iopub.status.busy":"2025-03-11T14:38:22.581528Z","iopub.execute_input":"2025-03-11T14:38:22.581746Z","iopub.status.idle":"2025-03-11T14:38:22.597168Z","shell.execute_reply.started":"2025-03-11T14:38:22.581728Z","shell.execute_reply":"2025-03-11T14:38:22.596533Z"}},"outputs":[],"execution_count":null},{"cell_type":"markdown","source":"# Evaluation with inference server","metadata":{}},{"cell_type":"code","source":"skip_prediction = False","metadata":{"trusted":true,"execution":{"iopub.status.busy":"2025-03-08T06:43:32.460773Z","iopub.execute_input":"2025-03-08T06:43:32.461104Z","iopub.status.idle":"2025-03-08T06:43:32.464218Z","shell.execute_reply.started":"2025-03-08T06:43:32.461079Z","shell.execute_reply":"2025-03-08T06:43:32.463532Z"}},"outputs":[],"execution_count":null},{"cell_type":"code","source":"inference_server = (\n    kaggle_evaluation.konwinski_prize_inference_server.KPrizeInferenceServer(\n        get_number_of_instances, predict\n    )\n)\n\nif os.getenv(\"KAGGLE_IS_COMPETITION_RERUN\"):\n    inference_server.serve()\nelse:\n    inference_server.run_local_gateway(\n        data_paths=(\n            \"/kaggle/input/konwinski-prize/\",  # Path to the entire competition dataset\n            \"/kaggle/tmp/konwinski-prize/\",  # Path to a scratch directory for unpacking data.a_zip.\n        )  # type: ignore\n    )","metadata":{"trusted":true,"execution":{"iopub.status.busy":"2025-03-08T06:43:37.046746Z","iopub.execute_input":"2025-03-08T06:43:37.047079Z","iopub.status.idle":"2025-03-08T06:46:09.131061Z","shell.execute_reply.started":"2025-03-08T06:43:37.047052Z","shell.execute_reply":"2025-03-08T06:46:09.130246Z"}},"outputs":[],"execution_count":null},{"cell_type":"markdown","source":"Hope this notebook is insightful. I would've liked to run it in a different configurations for performance or to assign different task to different models cause some read better, some code better and some are coding too well so the \"judges\" fall for it. Running custom tests or selecting the available ones is also an interesting option, though I omitted it for stability. \n\nHere pretty rich selection of validating and shortcircuiting methods was used. Based on the results I don't think I've found just the right balance as the resulting models do not score high even when they do not skip so aggressively.\n\nP.S.\n\nThe given problem is really tricky: to work properly all the actions of the system require qreat precision: great file retrieval, great coding capabilities (in this pipeline formatting capabilites too) as well as an ability to identify/produce a verification for such solution. \n\nDoing this in one pass is something only an oracle will get completely right and I don't think an oracle is realistic. Definitely it requires smarter models to do the refinement even better, but it can't be denied that current models are already quite powerful, but what they or we lack is a good understanding of how a backtracking can be performed with LLM in efficient way. If not for that I might have preferred sticking to an agentic approach.\n\nHow I see current inefficiency? Let's compare the model answering to a backtracking search on a state space. States are connected by tokens, similar states may be considered as one. Following one branch may result in zeroing some tokens, effectively cutting (like in Prolog) out the state, so that the model never arrives here. Model is left with narrower options, that, when not different enough becomes highly skewed bias. Not completely negative effect, it allows model to converge at the solution, but uncontrollable it can simply lock the model in its branch. Like the model can be budget-scaled by adding wait, perhaps some \"reset query\" can be a breakthrough.\n\nEffectively differentiating branches is also a good topic. For example image generating models when not given details (let's say we've asked for an image of a cute cat) will often return pretty similar cats. Despite Google's Gemini failing that one time it overdid it with diversity it was cool to see something that diversified past bias even if it was also past the bounds.\n\nThere are other aspects of the agents that is the context size and optimal way to show the \"story\" available to agent, but these fields seem to flourish. Still, modern agents under restrictions like here may really do better when being guided.","metadata":{}}]}