Pancake Problem: Baseline Submission

from __future__ import annotations

import pandas as pd
from pathlib import Path
from typing import Iterable

# Detect Kaggle environment ( /kaggle/input/... ), otherwise fall back to local repo layout.
DATA_ROOT = Path('/kaggle/input/pancake-sorting')
if not DATA_ROOT.exists():
    DATA_ROOT = Path('pancake-sorting')
assert DATA_ROOT.exists(), f'Dataset directory not found: {DATA_ROOT!s}'

TEST_PATH = DATA_ROOT / 'test.csv'
SUBMISSION_PATH = Path('submission.csv')  # Kaggle expects this in the working directory
TEST_PATH

def parse_permutation(raw: str) -> list[int]:
    """Parse a comma-separated permutation string into integer positions."""
    return [int(token) for token in raw.split(',') if token]

def pancake_sort_path(perm: Iterable[int]) -> list[str]:
    """Return a sequence of prefix reversals that sorts `perm` to the identity permutation."""
    arr = list(perm)
    n = len(arr)
    moves: list[str] = []

    for target in range(n, 1, -1):
        desired_value = target - 1
        idx = arr.index(desired_value)

        if idx == target - 1:
            continue  # already in place

        if idx != 0:
            moves.append(f'R{idx + 1}')
            arr[: idx + 1] = reversed(arr[: idx + 1])

        moves.append(f'R{target}')
        arr[:target] = reversed(arr[:target])

    return moves

test_df = pd.read_csv(TEST_PATH)
submission_rows: list[dict[str, str]] = []

for row in test_df.itertuples(index=False):
    perm = parse_permutation(row.permutation)
    moves = pancake_sort_path(perm)
    path_str = '.'.join(moves) if moves else 'UNSOLVED'
    submission_rows.append({'id': row.id, 'permutation': row.permutation, 'solution': path_str})

submission_df = pd.DataFrame(submission_rows).sort_values('id').reset_index(drop=True)
submission_df.head()

submission_df.to_csv(SUBMISSION_PATH, index=False)
SUBMISSION_PATH, len(submission_df)

submission_df.sample(5, random_state=0)