Skip to article frontmatterSkip to article content

Pancake sorting baseline

!pip install git+https://github.com/cayleypy/cayleypy -q
  Installing build dependencies ... done
  Getting requirements to build wheel ... done
  Preparing metadata (pyproject.toml) ... done
   ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━ 363.4/363.4 MB 4.2 MB/s eta 0:00:00:00:0100:01
   ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━ 13.8/13.8 MB 82.3 MB/s eta 0:00:00:00:010:01
   ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━ 24.6/24.6 MB 63.7 MB/s eta 0:00:00:00:0100:01
   ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━ 883.7/883.7 kB 33.9 MB/s eta 0:00:00
   ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━ 664.8/664.8 MB 2.2 MB/s eta 0:00:00:00:0100:01
   ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━ 211.5/211.5 MB 5.4 MB/s eta 0:00:00:00:0100:01
   ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━ 56.3/56.3 MB 27.6 MB/s eta 0:00:00:00:0100:01
   ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━ 127.9/127.9 MB 8.9 MB/s eta 0:00:00:00:0100:01
   ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━ 207.5/207.5 MB 2.6 MB/s eta 0:00:00:00:0100:01
   ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━ 21.1/21.1 MB 72.2 MB/s eta 0:00:00:00:0100:01
  Building wheel for cayleypy (pyproject.toml) ... done
ERROR: pip's dependency resolver does not currently take into account all the packages that are installed. This behaviour is the source of the following dependency conflicts.
libcugraph-cu12 25.6.0 requires libraft-cu12==25.6.*, but you have libraft-cu12 25.2.0 which is incompatible.
pylibcugraph-cu12 25.6.0 requires pylibraft-cu12==25.6.*, but you have pylibraft-cu12 25.2.0 which is incompatible.
pylibcugraph-cu12 25.6.0 requires rmm-cu12==25.6.*, but you have rmm-cu12 25.2.0 which is incompatible.

import random
import numpy as np
import pandas as pd

import torch
from torch import nn

from cayleypy import CayleyGraph, PermutationGroups, Predictor
from cayleypy.algo import RandomWalksGenerator
from torch.utils.data import TensorDataset, DataLoader
from tqdm import tqdm
test = pd.read_csv("/kaggle/input/CayleyPy-pancake/test.csv")
test["n"].unique()
array([ 5, 12, 15, 16, 20, 25, 30, 35, 40, 45, 50, 75, 100])
def pancake_sort_path(perm: list[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
class StateScorer(nn.Module):
    def __init__(self, n_pancakes: int, hidden_dim: int):
        super().__init__()
        self.n_pancakes = n_pancakes
        self.net = nn.Sequential(nn.Linear(n_pancakes, hidden_dim), nn.LeakyReLU(), nn.Linear(hidden_dim, 1))

    def forward(self, x):
        return self.net(2*x.float() / (self.n_pancakes - 1) - 1).squeeze(-1)
def seed_everything(seed):
    np.random.seed(seed)
    random.seed(seed)
    torch.manual_seed(seed)
    torch.use_deterministic_algorithms(True)
def train_predictor(n, graph=None, width=1000, length=5, n_dim=100, batch_size=16, epochs=8, random_seed=42):
    seed_everything(random_seed)
    if graph is None:
        graph = CayleyGraph(PermutationGroups.pancake(n))
    rwg = RandomWalksGenerator(graph)
    states, distances = rwg.generate(width=width, length=length, mode="classic")
    train_dataset = TensorDataset(states.float(), distances.float())
    train_dataloader = DataLoader(train_dataset, batch_size=batch_size, shuffle=True)
        
    predictor = StateScorer(n, n_dim)
    predictor.train()

    optimizator = torch.optim.AdamW(predictor.parameters(), lr=3e-4)
    loss_fn = nn.MSELoss()

    for _ in range(epochs):
        for states, dist in tqdm(train_dataloader):
            optimizator.zero_grad()
            pred_dist = predictor(states)
            loss = loss_fn(pred_dist, dist)
            loss.backward()
            optimizator.step()

    predictor.eval()
    return predictor

Prediction

graphs = {}
models = {}
for n_s in test["n"].unique():
    graphs[n_s] = CayleyGraph(PermutationGroups.pancake(n_s))
    models[n_s] = Predictor(graphs[n_s], train_predictor(n_s, graph=graphs[n_s], width=n_s*100, length=int(n_s*1.6), batch_size=32, epochs=4))
100%|██████████| 125/125 [00:00<00:00, 658.20it/s]
100%|██████████| 125/125 [00:00<00:00, 676.80it/s]
100%|██████████| 125/125 [00:00<00:00, 670.13it/s]
100%|██████████| 125/125 [00:00<00:00, 662.92it/s]
100%|██████████| 713/713 [00:01<00:00, 671.87it/s]
100%|██████████| 713/713 [00:01<00:00, 672.34it/s]
100%|██████████| 713/713 [00:01<00:00, 647.28it/s]
100%|██████████| 713/713 [00:01<00:00, 675.47it/s]
100%|██████████| 1125/1125 [00:01<00:00, 676.58it/s]
100%|██████████| 1125/1125 [00:01<00:00, 679.75it/s]
100%|██████████| 1125/1125 [00:01<00:00, 667.46it/s]
100%|██████████| 1125/1125 [00:01<00:00, 654.57it/s]
100%|██████████| 1250/1250 [00:01<00:00, 657.41it/s]
100%|██████████| 1250/1250 [00:01<00:00, 670.92it/s]
100%|██████████| 1250/1250 [00:01<00:00, 673.74it/s]
100%|██████████| 1250/1250 [00:01<00:00, 666.15it/s]
100%|██████████| 2000/2000 [00:02<00:00, 667.30it/s]
100%|██████████| 2000/2000 [00:03<00:00, 658.49it/s]
100%|██████████| 2000/2000 [00:02<00:00, 677.35it/s]
100%|██████████| 2000/2000 [00:02<00:00, 675.26it/s]
100%|██████████| 3125/3125 [00:04<00:00, 650.51it/s]
100%|██████████| 3125/3125 [00:04<00:00, 652.55it/s]
100%|██████████| 3125/3125 [00:04<00:00, 648.47it/s]
100%|██████████| 3125/3125 [00:04<00:00, 655.66it/s]
100%|██████████| 4500/4500 [00:06<00:00, 644.09it/s]
100%|██████████| 4500/4500 [00:06<00:00, 649.14it/s]
100%|██████████| 4500/4500 [00:07<00:00, 642.01it/s]
100%|██████████| 4500/4500 [00:06<00:00, 650.18it/s]
100%|██████████| 6125/6125 [00:09<00:00, 645.17it/s]
100%|██████████| 6125/6125 [00:09<00:00, 645.45it/s]
100%|██████████| 6125/6125 [00:09<00:00, 645.53it/s]
100%|██████████| 6125/6125 [00:09<00:00, 637.39it/s]
100%|██████████| 8000/8000 [00:12<00:00, 638.14it/s]
100%|██████████| 8000/8000 [00:12<00:00, 640.79it/s]
100%|██████████| 8000/8000 [00:12<00:00, 640.21it/s]
100%|██████████| 8000/8000 [00:12<00:00, 634.07it/s]
100%|██████████| 10125/10125 [00:15<00:00, 638.97it/s]
100%|██████████| 10125/10125 [00:15<00:00, 635.79it/s]
100%|██████████| 10125/10125 [00:15<00:00, 636.39it/s]
100%|██████████| 10125/10125 [00:15<00:00, 633.64it/s]
100%|██████████| 12500/12500 [00:19<00:00, 631.37it/s]
100%|██████████| 12500/12500 [00:19<00:00, 637.08it/s]
100%|██████████| 12500/12500 [00:19<00:00, 627.20it/s]
100%|██████████| 12500/12500 [00:19<00:00, 629.20it/s]
100%|██████████| 28125/28125 [00:44<00:00, 629.61it/s]
100%|██████████| 28125/28125 [00:44<00:00, 625.74it/s]
100%|██████████| 28125/28125 [00:45<00:00, 624.11it/s]
100%|██████████| 28125/28125 [00:45<00:00, 623.41it/s]
100%|██████████| 50000/50000 [01:21<00:00, 613.12it/s]
100%|██████████| 50000/50000 [01:21<00:00, 613.09it/s]
100%|██████████| 50000/50000 [01:21<00:00, 616.61it/s]
100%|██████████| 50000/50000 [01:21<00:00, 612.08it/s]

def pancake_sort_path(perm: list[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
heurestic_paths = []
for _, row in tqdm(test.iterrows(), total=len(test)):
    perms = np.array(row["permutation"].split(",")).astype(int)
    moves = pancake_sort_path(perms)
    heurestic_paths.append(".".join(moves))
100%|██████████| 2405/2405 [00:00<00:00, 5771.70it/s] 

pred_paths = []

for i, row in tqdm(test.iterrows(), total=len(test)):
    n = row["n"]
    if n >= 20:
        pred_paths.append(heurestic_paths[i])
        continue
    heurestic_length = heurestic_paths[i].count(".") + 1
    perms = np.array(row["permutation"].split(",")).astype(int)
    graphs[n].free_memory()
    result = graphs[n].beam_search(start_state=perms, beam_width=1000, max_steps=heurestic_length, predictor=models[n], return_path=True)
    if result.path_found and len(result.path) < heurestic_length:
        pred_paths.append(".".join([f"R{gen_index+2}" for gen_index in result.path]))
    else:
        pred_paths.append(heurestic_paths[i])
100%|██████████| 2405/2405 [06:16<00:00,  6.39it/s]

submissions = pd.read_csv("/kaggle/input/CayleyPy-pancake/sample_submission.csv")
submissions["solution"] = pred_paths
submissions.to_csv("nn_submission.csv")
Experiments
Base solution
Research Log
Base solution by Egor K.