getting-started-with-santa-2023.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "a33cbc13",
   "metadata": {
    "jupyter": {
     "outputs_hidden": false
    },
    "papermill": {
     "duration": 0.010984,
     "end_time": "2023-12-21T15:06:15.143595",
     "exception": false,
     "start_time": "2023-12-21T15:06:15.132611",
     "status": "completed"
    },
    "tags": []
   },
   "source": [
    "# Welcome to the Santa 2023 - The Polytope Permutation Puzzle! #\n",
    "\n",
    "Santa's tree is adorned with many-colored, puzzle-like decorations of all shapes and sizes. Unfortunately, the colors on these decorations have gotten all mixed up! In this competition, you're challenged to set the decorations right in the fewest number of moves.\n",
    "\n",
    "This notebook will give you a quick introduction to the competition."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4db31279",
   "metadata": {
    "jupyter": {
     "outputs_hidden": false
    },
    "papermill": {
     "duration": 0.009929,
     "end_time": "2023-12-21T15:06:15.163811",
     "exception": false,
     "start_time": "2023-12-21T15:06:15.153882",
     "status": "completed"
    },
    "tags": []
   },
   "source": [
    "# Setup #"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "09154e56",
   "metadata": {
    "collapsed": false,
    "execution": {
     "iopub.execute_input": "2023-12-21T15:06:15.186130Z",
     "iopub.status.busy": "2023-12-21T15:06:15.185163Z",
     "iopub.status.idle": "2023-12-21T15:06:20.751939Z",
     "shell.execute_reply": "2023-12-21T15:06:20.750837Z"
    },
    "jupyter": {
     "outputs_hidden": false
    },
    "papermill": {
     "duration": 5.581066,
     "end_time": "2023-12-21T15:06:20.754958",
     "exception": false,
     "start_time": "2023-12-21T15:06:15.173892",
     "status": "completed"
    },
    "tags": []
   },
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import pandas as pd\n",
    "from ast import literal_eval\n",
    "from pathlib import Path\n",
    "from pprint import pprint\n",
    "from sympy.combinatorics import Permutation\n",
    "\n",
    "# kaggle data_dir\n",
    "#data_dir = Path(\"/kaggle/input/santa-2023\")\n",
    "\n",
    "# local data_dir\n",
    "data_dir = Path(\"data\")\n",
    "\n",
    "puzzle_info = pd.read_csv(data_dir / 'puzzle_info.csv', index_col='puzzle_type')\n",
    "# Parse allowed_moves\n",
    "puzzle_info['allowed_moves'] = puzzle_info['allowed_moves'].apply(literal_eval)\n",
    "\n",
    "puzzles = pd.read_csv(data_dir / 'puzzles.csv', index_col='id')\n",
    "# Parse color states\n",
    "puzzles = puzzles.assign(\n",
    "    initial_state=lambda df: df['initial_state'].str.split(';'),\n",
    "    solution_state=lambda df: df['solution_state'].str.split(';')\n",
    ")\n",
    "\n",
    "sample_submission = pd.read_csv(data_dir / 'sample_submission.csv', index_col='id')"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "333dedc1",
   "metadata": {
    "jupyter": {
     "outputs_hidden": false
    },
    "papermill": {
     "duration": 0.010469,
     "end_time": "2023-12-21T15:06:20.776633",
     "exception": false,
     "start_time": "2023-12-21T15:06:20.766164",
     "status": "completed"
    },
    "tags": []
   },
   "source": [
    "# Permutation Puzzles #\n",
    "\n",
    "A **permutation puzzle** is an arrangement of **colors** together with a set of permutations of these arrangements called **moves**. The puzzle starts out with an **initial state** of colors and must be permuted through a sequence of moves to its **solution state**. The goal is to do this with as few moves as possible."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "7feec16a",
   "metadata": {
    "collapsed": false,
    "execution": {
     "iopub.execute_input": "2023-12-21T15:06:20.799142Z",
     "iopub.status.busy": "2023-12-21T15:06:20.798478Z",
     "iopub.status.idle": "2023-12-21T15:06:20.804469Z",
     "shell.execute_reply": "2023-12-21T15:06:20.803632Z"
    },
    "jupyter": {
     "outputs_hidden": false
    },
    "papermill": {
     "duration": 0.019957,
     "end_time": "2023-12-21T15:06:20.806723",
     "exception": false,
     "start_time": "2023-12-21T15:06:20.786766",
     "status": "completed"
    },
    "tags": []
   },
   "outputs": [],
   "source": [
    "# Here is a very simple puzzle\n",
    "solution_state = ['R', 'G', 'B']\n",
    "initial_state = ['B', 'G', 'R']\n",
    "moves = {\n",
    "    'r': [1, 2, 0],\n",
    "    's': [1, 0, 2],\n",
    "}\n",
    "r = moves['r']\n",
    "s = moves['s']"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5ad28ad7",
   "metadata": {
    "jupyter": {
     "outputs_hidden": false
    },
    "papermill": {
     "duration": 0.009769,
     "end_time": "2023-12-21T15:06:20.826620",
     "exception": false,
     "start_time": "2023-12-21T15:06:20.816851",
     "status": "completed"
    },
    "tags": []
   },
   "source": [
    "The moves are given in \"array form\", where a move `m` will send position `i` to `m[i]`. You can apply a move in array form using NumPy indexing."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "63678eb5",
   "metadata": {
    "collapsed": false,
    "execution": {
     "iopub.execute_input": "2023-12-21T15:06:20.849655Z",
     "iopub.status.busy": "2023-12-21T15:06:20.848887Z",
     "iopub.status.idle": "2023-12-21T15:06:20.856386Z",
     "shell.execute_reply": "2023-12-21T15:06:20.855382Z"
    },
    "jupyter": {
     "outputs_hidden": false
    },
    "papermill": {
     "duration": 0.021536,
     "end_time": "2023-12-21T15:06:20.858638",
     "exception": false,
     "start_time": "2023-12-21T15:06:20.837102",
     "status": "completed"
    },
    "tags": []
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array(['G', 'R', 'B'], dtype='<U1')"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# First convert the state to a NumPy array to use NumPy indexing\n",
    "initial_state_np = np.asarray(initial_state)\n",
    "\n",
    "initial_state_np[r]"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "132e1986",
   "metadata": {
    "jupyter": {
     "outputs_hidden": false
    },
    "papermill": {
     "duration": 0.009916,
     "end_time": "2023-12-21T15:06:20.878793",
     "exception": false,
     "start_time": "2023-12-21T15:06:20.868877",
     "status": "completed"
    },
    "tags": []
   },
   "source": [
    "You can also represent a move as a permutation in \"disjoint cycle\" form."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "2876615e",
   "metadata": {
    "collapsed": false,
    "execution": {
     "iopub.execute_input": "2023-12-21T15:06:20.901393Z",
     "iopub.status.busy": "2023-12-21T15:06:20.900585Z",
     "iopub.status.idle": "2023-12-21T15:06:20.908616Z",
     "shell.execute_reply": "2023-12-21T15:06:20.907443Z"
    },
    "jupyter": {
     "outputs_hidden": false
    },
    "papermill": {
     "duration": 0.022135,
     "end_time": "2023-12-21T15:06:20.911062",
     "exception": false,
     "start_time": "2023-12-21T15:06:20.888927",
     "status": "completed"
    },
    "tags": []
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "r: (0 1 2) \tSends 0 -> 1, 1 -> 2, and 2 -> 0.\n",
      "s: (2)(0 1) \tSends 0 -> 1, 1 -> 0, and 2 stays fixed.\n",
      "Effect of r: ['G', 'R', 'B']\n",
      "Effect of s: ['G', 'B', 'R']\n"
     ]
    }
   ],
   "source": [
    "rp = Permutation(r)\n",
    "sp = Permutation(s)\n",
    "print('r:', rp, \"\\tSends 0 -> 1, 1 -> 2, and 2 -> 0.\")\n",
    "print('s:', sp, \"\\tSends 0 -> 1, 1 -> 0, and 2 stays fixed.\" )\n",
    "\n",
    "# A Permutation is a function which you can apply to a state with a function call\n",
    "print(\"Effect of r:\", rp(initial_state))\n",
    "print(\"Effect of s:\", sp(initial_state))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "aa2a66de",
   "metadata": {
    "jupyter": {
     "outputs_hidden": false
    },
    "papermill": {
     "duration": 0.009921,
     "end_time": "2023-12-21T15:06:20.931232",
     "exception": false,
     "start_time": "2023-12-21T15:06:20.921311",
     "status": "completed"
    },
    "tags": []
   },
   "source": [
    "You are also allowed to use the *inverse* of any of a puzzle's moves. The inverse of a permutation just applies the change with \"the arrows reversed\"."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "id": "5302e697",
   "metadata": {
    "collapsed": false,
    "execution": {
     "iopub.execute_input": "2023-12-21T15:06:20.953727Z",
     "iopub.status.busy": "2023-12-21T15:06:20.953317Z",
     "iopub.status.idle": "2023-12-21T15:06:20.964831Z",
     "shell.execute_reply": "2023-12-21T15:06:20.963556Z"
    },
    "jupyter": {
     "outputs_hidden": false
    },
    "papermill": {
     "duration": 0.025761,
     "end_time": "2023-12-21T15:06:20.967231",
     "exception": false,
     "start_time": "2023-12-21T15:06:20.941470",
     "status": "completed"
    },
    "tags": []
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "r_inv=[2, 0, 1], s_inv=[1, 0, 2]\n",
      "\n",
      "r: (0 2 1) \tSends 1 -> 0, 2 -> 1, and 0 -> 2.\n",
      "s: (2)(0 1) \tSends 1 -> 0, 0 -> 1, and 2 stays fixed.\n"
     ]
    }
   ],
   "source": [
    "# Use np.argsort to get the inverse using array form\n",
    "r_inv = np.argsort(r).tolist()\n",
    "s_inv = np.argsort(s).tolist()\n",
    "print(f\"{r_inv=}, {s_inv=}\\n\")\n",
    "\n",
    "# Use a negative power to get the inverse of a Permutation\n",
    "rp_inv = rp ** -1\n",
    "sp_inv = sp ** -1\n",
    "\n",
    "# It's the same permutation either way\n",
    "assert Permutation(r_inv) == rp_inv\n",
    "assert Permutation(s_inv) == sp_inv\n",
    "\n",
    "# In this case, s is equal to its inverse\n",
    "assert (s == s_inv) and (sp == sp_inv)\n",
    "# But r is not\n",
    "assert (r != r_inv) and (rp != rp_inv)\n",
    "\n",
    "# Inversion reverses the arrows\n",
    "print('r:', rp_inv, \"\\tSends 1 -> 0, 2 -> 1, and 0 -> 2.\")\n",
    "print('s:', sp, \"\\tSends 1 -> 0, 0 -> 1, and 2 stays fixed.\" )"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4e1a6361",
   "metadata": {
    "jupyter": {
     "outputs_hidden": false
    },
    "papermill": {
     "duration": 0.010036,
     "end_time": "2023-12-21T15:06:20.988125",
     "exception": false,
     "start_time": "2023-12-21T15:06:20.978089",
     "status": "completed"
    },
    "tags": []
   },
   "source": [
    "Here's the solution to this simple puzzle:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "id": "f554e82e",
   "metadata": {
    "collapsed": false,
    "execution": {
     "iopub.execute_input": "2023-12-21T15:06:21.011291Z",
     "iopub.status.busy": "2023-12-21T15:06:21.010532Z",
     "iopub.status.idle": "2023-12-21T15:06:21.016231Z",
     "shell.execute_reply": "2023-12-21T15:06:21.015340Z"
    },
    "jupyter": {
     "outputs_hidden": false
    },
    "papermill": {
     "duration": 0.019755,
     "end_time": "2023-12-21T15:06:21.018515",
     "exception": false,
     "start_time": "2023-12-21T15:06:20.998760",
     "status": "completed"
    },
    "tags": []
   },
   "outputs": [],
   "source": [
    "# Using array form\n",
    "state = np.asarray(initial_state)\n",
    "state = state[s]\n",
    "state = state[r_inv]\n",
    "state = state.tolist()\n",
    "assert state == solution_state\n",
    "\n",
    "# Using Permutations\n",
    "state = sp(initial_state)\n",
    "state = rp_inv(state)\n",
    "assert state == solution_state"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8f9f0f64",
   "metadata": {
    "jupyter": {
     "outputs_hidden": false
    },
    "papermill": {
     "duration": 0.010051,
     "end_time": "2023-12-21T15:06:21.039010",
     "exception": false,
     "start_time": "2023-12-21T15:06:21.028959",
     "status": "completed"
    },
    "tags": []
   },
   "source": [
    "# Cube Puzzles #"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f06a7af1",
   "metadata": {
    "jupyter": {
     "outputs_hidden": false
    },
    "papermill": {
     "duration": 0.009882,
     "end_time": "2023-12-21T15:06:21.059076",
     "exception": false,
     "start_time": "2023-12-21T15:06:21.049194",
     "status": "completed"
    },
    "tags": []
   },
   "source": [
    "There are three puzzle types: `cube`, `wreath`, and `globe`. Each type of puzzle represents its arrangements on some geometric figure with the permutations being a twist or turn of some portion of the figure.\n",
    "Here, for example, is a `cube_2/2/2` puzzle: a cube with each face sliced into four \"facelets\". We can see the positions of the facelets as well as a coloring representing a \"solved\" puzzle.\n",
    "\n",
    "```\n",
    "         Positions                                Solution State\n",
    "\n",
    "         +--------+                               +--------+\n",
    "         | 0    1 |                               | A    A |\n",
    "         |   d1   |                               |   d1   |\n",
    "         | 2    3 |                               | A    A |\n",
    "+--------+--------+--------+--------+    +--------+--------+--------+--------+\n",
    "| 16  17 | 4    5 | 8   9  | 12  13 |    | E    E | B    B | C    C | D    D |\n",
    "|   r1   |   f0   |   r0   |   f1   |    |   r1   |   f0   |   r0   |   f1   |\n",
    "| 18  19 | 6    7 | 10  11 | 14  15 |    | E    E | B    B | C    C | D    D |\n",
    "+--------+--------+--------+--------+    +--------+--------+--------+--------+\n",
    "         | 20  21 |                               | F    F |\n",
    "         |   d0   |                               |   d0   |\n",
    "         | 22  23 |                               | F    F |\n",
    "         +--------+                               +--------+\n",
    "```\n",
    "\n",
    "The `2/2/2` means the cube has two layers along each of the three face axes: `d0, d1` (up and down), `f0, f1` (front and back), `r0, r1` (right and left). A `3/3/3` cube will have three layers along each exis, etc. In general, opposing faces will be the layers `a0, a{n-1}`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "id": "4f191a06",
   "metadata": {
    "collapsed": false,
    "execution": {
     "iopub.execute_input": "2023-12-21T15:06:21.081485Z",
     "iopub.status.busy": "2023-12-21T15:06:21.081054Z",
     "iopub.status.idle": "2023-12-21T15:06:21.101897Z",
     "shell.execute_reply": "2023-12-21T15:06:21.100628Z"
    },
    "jupyter": {
     "outputs_hidden": false
    },
    "papermill": {
     "duration": 0.035503,
     "end_time": "2023-12-21T15:06:21.104879",
     "exception": false,
     "start_time": "2023-12-21T15:06:21.069376",
     "status": "completed"
    },
    "tags": []
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "cube_2/2/2\n",
      "{'d0': [['F', 'F'], ['F', 'F']],\n",
      " 'd1': [['A', 'A'], ['A', 'A']],\n",
      " 'f0': [['B', 'B'], ['B', 'B']],\n",
      " 'f1': [['D', 'D'], ['D', 'D']],\n",
      " 'r0': [['C', 'C'], ['C', 'C']],\n",
      " 'r1': [['E', 'E'], ['E', 'E']]}\n",
      "\n",
      "cube_3/3/3\n",
      "{'d0': [['F', 'F', 'F'], ['F', 'F', 'F'], ['F', 'F', 'F']],\n",
      " 'd2': [['A', 'A', 'A'], ['A', 'A', 'A'], ['A', 'A', 'A']],\n",
      " 'f0': [['B', 'B', 'B'], ['B', 'B', 'B'], ['B', 'B', 'B']],\n",
      " 'f2': [['D', 'D', 'D'], ['D', 'D', 'D'], ['D', 'D', 'D']],\n",
      " 'r0': [['C', 'C', 'C'], ['C', 'C', 'C'], ['C', 'C', 'C']],\n",
      " 'r2': [['E', 'E', 'E'], ['E', 'E', 'E'], ['E', 'E', 'E']]}\n",
      "\n"
     ]
    }
   ],
   "source": [
    "def cube_state_to_faces(state):\n",
    "    \"\"\"Convert a state list to a dictionary of labeled faces.\"\"\"\n",
    "    n = int(np.sqrt(len(state) / 6))  # cube_n/n/n\n",
    "    n2 = n ** 2\n",
    "    labels = f\"d{n-1},f0,r0,f{n-1},r{n-1},d0\".split(',')\n",
    "    faces = {}\n",
    "    for i, l in enumerate(labels):\n",
    "        face = state[n2 * i : n2 * (i + 1)]\n",
    "        faces[l] = np.asarray(face).reshape(n, n).tolist()\n",
    "    return faces\n",
    "\n",
    "\n",
    "for ptype in ('cube_2/2/2', 'cube_3/3/3'):\n",
    "    sstate = puzzles.query(f\"puzzle_type == '{ptype}'\").iloc[0, 1]\n",
    "    print(ptype)\n",
    "    pprint(cube_state_to_faces(sstate))\n",
    "    print()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "625d3727",
   "metadata": {
    "jupyter": {
     "outputs_hidden": false
    },
    "papermill": {
     "duration": 0.01018,
     "end_time": "2023-12-21T15:06:21.126199",
     "exception": false,
     "start_time": "2023-12-21T15:06:21.116019",
     "status": "completed"
    },
    "tags": []
   },
   "source": [
    "There is a move for each layer, which corresponds to a quarter-twist for that layer."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "6f2ba382",
   "metadata": {
    "collapsed": false,
    "execution": {
     "iopub.execute_input": "2023-12-21T15:06:21.148916Z",
     "iopub.status.busy": "2023-12-21T15:06:21.148514Z",
     "iopub.status.idle": "2023-12-21T15:06:21.193855Z",
     "shell.execute_reply": "2023-12-21T15:06:21.192843Z"
    },
    "jupyter": {
     "outputs_hidden": false
    },
    "papermill": {
     "duration": 0.060382,
     "end_time": "2023-12-21T15:06:21.196935",
     "exception": false,
     "start_time": "2023-12-21T15:06:21.136553",
     "status": "completed"
    },
    "tags": []
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "cube_2/2/2\n",
      "f0: (23)(2 19 21 8)(3 17 20 10)(4 6 7 5)\n",
      "f1: (0 18 23 9)(1 16 22 11)(12 13 15 14)\n",
      "r0: (1 5 21 14)(3 7 23 12)(8 10 11 9)\n",
      "r1: (23)(0 4 20 15)(2 6 22 13)(16 17 19 18)\n",
      "d0: (6 18 14 10)(7 19 15 11)(20 22 23 21)\n",
      "d1: (23)(0 1 3 2)(4 16 12 8)(5 17 13 9)\n",
      "\n",
      "cube_3/3/3\n",
      "f0: (53)(6 44 47 18)(7 41 46 21)(8 38 45 24)(9 15 17 11)(10 12 16 14)\n",
      "f1: (53)(3 43 50 19)(4 40 49 22)(5 37 48 25)\n",
      "f2: (0 42 53 20)(1 39 52 23)(2 36 51 26)(27 29 35 33)(28 32 34 30)\n",
      "r0: (2 11 47 33)(5 14 50 30)(8 17 53 27)(18 24 26 20)(19 21 25 23)\n",
      "r1: (53)(1 10 46 34)(4 13 49 31)(7 16 52 28)\n",
      "r2: (53)(0 9 45 35)(3 12 48 32)(6 15 51 29)(36 38 44 42)(37 41 43 39)\n",
      "d0: (15 42 33 24)(16 43 34 25)(17 44 35 26)(45 51 53 47)(46 48 52 50)\n",
      "d1: (53)(12 39 30 21)(13 40 31 22)(14 41 32 23)\n",
      "d2: (53)(0 2 8 6)(1 5 7 3)(9 36 27 18)(10 37 28 19)(11 38 29 20)\n"
     ]
    }
   ],
   "source": [
    "print(\"cube_2/2/2\")\n",
    "for m, p in puzzle_info.loc['cube_2/2/2', 'allowed_moves'].items():\n",
    "    print(f\"{m}: {Permutation(p)}\")\n",
    "\n",
    "print()\n",
    "\n",
    "print(\"cube_3/3/3\")\n",
    "for m, p in puzzle_info.loc['cube_3/3/3', 'allowed_moves'].items():\n",
    "    print(f\"{m}: {Permutation(p)}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7528f75a",
   "metadata": {
    "jupyter": {
     "outputs_hidden": false
    },
    "papermill": {
     "duration": 0.010305,
     "end_time": "2023-12-21T15:06:21.218010",
     "exception": false,
     "start_time": "2023-12-21T15:06:21.207705",
     "status": "completed"
    },
    "tags": []
   },
   "source": [
    "As a hint to optimizing solutions, note that these moves satisfy certain relations like:\n",
    "- `m ** 3 == m ** -1` for any move `m`, and,\n",
    "- `f0 * f1 * r0 * (f1 ** -1) * (f0 ** -1) == d0`"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "eeb71b50",
   "metadata": {
    "jupyter": {
     "outputs_hidden": false
    },
    "papermill": {
     "duration": 0.011004,
     "end_time": "2023-12-21T15:06:21.239634",
     "exception": false,
     "start_time": "2023-12-21T15:06:21.228630",
     "status": "completed"
    },
    "tags": []
   },
   "source": [
    "# Wreath Puzzles #\n",
    "\n",
    "A `wreath` puzzle is two rings joined at two points, roughly like this:\n",
    "\n",
    "```\n",
    "   2   3      8   9\n",
    "1         4          10\n",
    "     l          r\n",
    "0         5          11\n",
    "   7   6     13  12\n",
    "```\n",
    "\n",
    "There will usually be points between the common points, however.\n",
    "\n",
    "A `wreath_X/Y` puzzle has `X` points in the left ring and `Y` points in the right ring."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "d5d2417a",
   "metadata": {
    "collapsed": false,
    "execution": {
     "iopub.execute_input": "2023-12-21T15:06:21.262866Z",
     "iopub.status.busy": "2023-12-21T15:06:21.262138Z",
     "iopub.status.idle": "2023-12-21T15:06:21.271047Z",
     "shell.execute_reply": "2023-12-21T15:06:21.269660Z"
    },
    "jupyter": {
     "outputs_hidden": false
    },
    "papermill": {
     "duration": 0.023043,
     "end_time": "2023-12-21T15:06:21.273142",
     "exception": false,
     "start_time": "2023-12-21T15:06:21.250099",
     "status": "completed"
    },
    "tags": []
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "wreath_6/6\n",
      "l: (9)(0 1 2 3 4 5)\n",
      "r: (0 6 7 2 8 9)\n"
     ]
    }
   ],
   "source": [
    "# A wreath with six in the left and six in the right\n",
    "# You can see the rings join at points 0 and 2.\n",
    "print(\"wreath_6/6\")\n",
    "for m, p in puzzle_info.loc['wreath_6/6', 'allowed_moves'].items():\n",
    "    print(f\"{m}: {Permutation(p)}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ae0343d4",
   "metadata": {
    "jupyter": {
     "outputs_hidden": false
    },
    "papermill": {
     "duration": 0.010468,
     "end_time": "2023-12-21T15:06:21.294441",
     "exception": false,
     "start_time": "2023-12-21T15:06:21.283973",
     "status": "completed"
    },
    "tags": []
   },
   "source": [
    "# Globe Puzzles #\n",
    "A `globe` puzzle is a sphere with cuts along lines of latitude and longitude. If you poke a hole at the North and South poles, cut along the meridian, and spread it out, it will look like a grid:\n",
    "\n",
    "```\n",
    "  | f0  f1  f2  f3  f4  f5  f6  f7\n",
    "--+-------------------------------\n",
    "r0| 0   1   2   3   4   5   6   7\n",
    "r1| 8   9   10  11  12  13  14  15\n",
    "r2| 16  17  18  19  20  21  22  23\n",
    "r3| 24  25  26  27  28  29  30  31\n",
    "```\n",
    "\n",
    "More precisely, a `globe_M/N` is a sphere with `M` lateral cuts (through latitude) and N radial cuts (through longitude). This gives a `(M + 1) x (2 N)` grid of positions. You could format a color state into a grid like this with something like `np.asarray(state).reshape(m+1, 2*n)`. The above is a `globe_3/4` puzzle."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "id": "0feb6c0e",
   "metadata": {
    "collapsed": false,
    "execution": {
     "iopub.execute_input": "2023-12-21T15:06:21.318402Z",
     "iopub.status.busy": "2023-12-21T15:06:21.317485Z",
     "iopub.status.idle": "2023-12-21T15:06:21.329444Z",
     "shell.execute_reply": "2023-12-21T15:06:21.328234Z"
    },
    "jupyter": {
     "outputs_hidden": false
    },
    "papermill": {
     "duration": 0.026985,
     "end_time": "2023-12-21T15:06:21.332144",
     "exception": false,
     "start_time": "2023-12-21T15:06:21.305159",
     "status": "completed"
    },
    "tags": []
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([['A', 'A', 'C', 'C', 'E', 'E', 'G', 'G'],\n",
       "       ['A', 'A', 'C', 'C', 'E', 'E', 'G', 'G'],\n",
       "       ['B', 'B', 'D', 'D', 'F', 'F', 'H', 'H'],\n",
       "       ['B', 'B', 'D', 'D', 'F', 'F', 'H', 'H']], dtype='<U1')"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Get a solution_state\n",
    "ss_globe34 = puzzles.query(\"puzzle_type == 'globe_3/4'\").iloc[0, 1]\n",
    "\n",
    "# Reshape into a grid\n",
    "np.asarray(ss_globe34).reshape(3+1, 2*4)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3b39a256",
   "metadata": {
    "jupyter": {
     "outputs_hidden": false
    },
    "papermill": {
     "duration": 0.010859,
     "end_time": "2023-12-21T15:06:21.354082",
     "exception": false,
     "start_time": "2023-12-21T15:06:21.343223",
     "status": "completed"
    },
    "tags": []
   },
   "source": [
    "There is a move for each lateral layer (the `r`s) and a move for each half (the `f`s). The `r` moves shift a layer by one position laterally, while the `f` moves shift one half of the globe by a half-twist."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "id": "24a690f1",
   "metadata": {
    "collapsed": false,
    "execution": {
     "iopub.execute_input": "2023-12-21T15:06:21.379238Z",
     "iopub.status.busy": "2023-12-21T15:06:21.378429Z",
     "iopub.status.idle": "2023-12-21T15:06:21.410073Z",
     "shell.execute_reply": "2023-12-21T15:06:21.408625Z"
    },
    "jupyter": {
     "outputs_hidden": false
    },
    "papermill": {
     "duration": 0.047371,
     "end_time": "2023-12-21T15:06:21.412914",
     "exception": false,
     "start_time": "2023-12-21T15:06:21.365543",
     "status": "completed"
    },
    "tags": []
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "globe_3/4\n",
      "r0: (31)(0 1 2 3 4 5 6 7)\n",
      "r1: (31)(8 9 10 11 12 13 14 15)\n",
      "r2: (31)(16 17 18 19 20 21 22 23)\n",
      "r3: (24 25 26 27 28 29 30 31)\n",
      "f0: (31)(0 27)(1 26)(2 25)(3 24)(8 19)(9 18)(10 17)(11 16)\n",
      "f1: (31)(1 28)(2 27)(3 26)(4 25)(9 20)(10 19)(11 18)(12 17)\n",
      "f2: (31)(2 29)(3 28)(4 27)(5 26)(10 21)(11 20)(12 19)(13 18)\n",
      "f3: (31)(3 30)(4 29)(5 28)(6 27)(11 22)(12 21)(13 20)(14 19)\n",
      "f4: (4 31)(5 30)(6 29)(7 28)(12 23)(13 22)(14 21)(15 20)\n",
      "f5: (0 29)(5 24)(6 31)(7 30)(8 21)(13 16)(14 23)(15 22)\n",
      "f6: (0 31)(1 30)(6 25)(7 24)(8 23)(9 22)(14 17)(15 16)\n",
      "f7: (0 25)(1 24)(2 31)(7 26)(8 17)(9 16)(10 23)(15 18)\n"
     ]
    }
   ],
   "source": [
    "print(\"globe_3/4\")\n",
    "for m, p in puzzle_info.loc['globe_3/4', 'allowed_moves'].items():\n",
    "    print(f\"{m}: {Permutation(p)}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "97ec6157",
   "metadata": {
    "jupyter": {
     "outputs_hidden": false
    },
    "papermill": {
     "duration": 0.010948,
     "end_time": "2023-12-21T15:06:21.435191",
     "exception": false,
     "start_time": "2023-12-21T15:06:21.424243",
     "status": "completed"
    },
    "tags": []
   },
   "source": [
    "# Submissions #\n",
    "\n",
    "The submission format requires moves in a sequence to be delimited by a period `.`. Indicate the inverse of a named move with a preceeding `-`. Moves are applied from left to right.\n",
    "\n",
    "The `sample_submission.csv` contains a baseline solution for each puzzle."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "id": "1dc50fb9",
   "metadata": {
    "collapsed": false,
    "execution": {
     "iopub.execute_input": "2023-12-21T15:06:21.460170Z",
     "iopub.status.busy": "2023-12-21T15:06:21.459777Z",
     "iopub.status.idle": "2023-12-21T15:06:21.478522Z",
     "shell.execute_reply": "2023-12-21T15:06:21.477747Z"
    },
    "jupyter": {
     "outputs_hidden": false
    },
    "papermill": {
     "duration": 0.033649,
     "end_time": "2023-12-21T15:06:21.480609",
     "exception": false,
     "start_time": "2023-12-21T15:06:21.446960",
     "status": "completed"
    },
    "tags": []
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: right;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>moves</th>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>id</th>\n",
       "      <th></th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>r1.-f1</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>f1.d0.-r0.-f1.-d0.-f1.d0.-r0.f0.-f1.-r0.f1.-d1...</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>f1.d0.-d1.r0.-d1.-f0.f1.-r0.-f0.-r1.-f0.r0.-d0...</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>-f0.-r0.-f0.-d0.-f0.f1.r0.-d1.-r0.-r1.-r0.-f1....</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4</th>\n",
       "      <td>d1.-f1.d1.r1.-f0.d1.-d0.-r1.d1.d1.-f1.d1.-d0.-...</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>...</th>\n",
       "      <td>...</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>393</th>\n",
       "      <td>f19.f21.-f39.f20.f2.-f5.f7.-r3.f55.-f12.f65.-f...</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>394</th>\n",
       "      <td>-f31.-f22.f16.-f17.-f13.-f24.-f14.f2.f21.f44.f...</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>395</th>\n",
       "      <td>-r0.-f42.-f8.f16.-f49.f14.-f1.f56.f26.f35.f62....</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>396</th>\n",
       "      <td>f25.-f29.f46.f49.-f8.f27.f26.-f20.f2.-f20.f6.f...</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>397</th>\n",
       "      <td>-r1.f23.-f24.-r2.f30.f30.f38.-f19.f24.f19.f18....</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "<p>398 rows × 1 columns</p>\n",
       "</div>"
      ],
      "text/plain": [
       "                                                 moves\n",
       "id                                                    \n",
       "0                                               r1.-f1\n",
       "1    f1.d0.-r0.-f1.-d0.-f1.d0.-r0.f0.-f1.-r0.f1.-d1...\n",
       "2    f1.d0.-d1.r0.-d1.-f0.f1.-r0.-f0.-r1.-f0.r0.-d0...\n",
       "3    -f0.-r0.-f0.-d0.-f0.f1.r0.-d1.-r0.-r1.-r0.-f1....\n",
       "4    d1.-f1.d1.r1.-f0.d1.-d0.-r1.d1.d1.-f1.d1.-d0.-...\n",
       "..                                                 ...\n",
       "393  f19.f21.-f39.f20.f2.-f5.f7.-r3.f55.-f12.f65.-f...\n",
       "394  -f31.-f22.f16.-f17.-f13.-f24.-f14.f2.f21.f44.f...\n",
       "395  -r0.-f42.-f8.f16.-f49.f14.-f1.f56.f26.f35.f62....\n",
       "396  f25.-f29.f46.f49.-f8.f27.f26.-f20.f2.-f20.f6.f...\n",
       "397  -r1.f23.-f24.-r2.f30.f30.f38.-f19.f24.f19.f18....\n",
       "\n",
       "[398 rows x 1 columns]"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sample_submission"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "fc2d8a05",
   "metadata": {
    "jupyter": {
     "outputs_hidden": false
    },
    "papermill": {
     "duration": 0.011169,
     "end_time": "2023-12-21T15:06:21.503307",
     "exception": false,
     "start_time": "2023-12-21T15:06:21.492138",
     "status": "completed"
    },
    "tags": []
   },
   "source": [
    "Let's check that the given sequence for the first puzzle is actually a solution."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "id": "45196e9e",
   "metadata": {
    "collapsed": false,
    "execution": {
     "iopub.execute_input": "2023-12-21T15:06:21.528139Z",
     "iopub.status.busy": "2023-12-21T15:06:21.527717Z",
     "iopub.status.idle": "2023-12-21T15:06:21.681722Z",
     "shell.execute_reply": "2023-12-21T15:06:21.680438Z"
    },
    "jupyter": {
     "outputs_hidden": false
    },
    "papermill": {
     "duration": 0.169691,
     "end_time": "2023-12-21T15:06:21.684441",
     "exception": false,
     "start_time": "2023-12-21T15:06:21.514750",
     "status": "completed"
    },
    "tags": []
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def apply_sequence(sequence, moves, state):\n",
    "    \"\"\"Apply a sequence of moves in array form to a color state.\"\"\"\n",
    "    state = np.asarray(state)\n",
    "    for m in sequence.split('.'):\n",
    "        state = state[moves[m]]\n",
    "    return state\n",
    "\n",
    "\n",
    "# Convert allowed_moves to dict and add inverse moves\n",
    "all_moves = puzzle_info.loc[:, 'allowed_moves'].to_dict()\n",
    "for ptype, moves in all_moves.copy().items():\n",
    "    for m, arr in moves.copy().items():\n",
    "        all_moves[ptype][f\"-{m}\"] = np.argsort(arr).tolist()\n",
    "\n",
    "\n",
    "# Get info for the first puzzle\n",
    "solution_state = puzzles.iloc[0, 1]\n",
    "initial_state = puzzles.iloc[0, 2]\n",
    "baseline_solution = sample_submission.loc[0, 'moves']\n",
    "\n",
    "state = apply_sequence(baseline_solution, all_moves['cube_2/2/2'], initial_state)\n",
    "np.array_equal(state, solution_state)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "da3c71b8",
   "metadata": {
    "jupyter": {
     "outputs_hidden": false
    },
    "papermill": {
     "duration": 0.011231,
     "end_time": "2023-12-21T15:06:21.707457",
     "exception": false,
     "start_time": "2023-12-21T15:06:21.696226",
     "status": "completed"
    },
    "tags": []
   },
   "source": [
    "In this case, the resulting state is exactly equal to the required solution state. For puzzles with wildcards, there can be an allowed number of differences. See the competitions [Evaluation](https://www.kaggle.com/competitions/santa-2023/overview/evaluation) page for more info."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4eaff517",
   "metadata": {
    "papermill": {
     "duration": 0.011314,
     "end_time": "2023-12-21T15:06:21.730437",
     "exception": false,
     "start_time": "2023-12-21T15:06:21.719123",
     "status": "completed"
    },
    "tags": []
   },
   "source": [
    "# Good luck! #\n",
    "\n",
    "We hope this introduction was informative! Here are some places to follow up for more information:\n",
    "- [The Complexity Dynamics of Magic Cubes and Twisty Puzzles](https://resplendence.org/dhushara.com/cubes/cubes.pdf)\n",
    "- [Twisty Puzzle Museum](https://twistypuzzles.com/app/museum/museum_search.php)\n",
    "- [Analyzing Rubik's Cube with GAP](https://www.gap-system.org/Doc/Examples/rubik.html) - You could try reproducing this with [SAGE](https://www.sagemath.org/), if you prefer."
   ]
  }
 ],
 "metadata": {
  "kaggle": {
   "accelerator": "none",
   "dataSources": [
    {
     "databundleVersionId": 7339171,
     "sourceId": 65704,
     "sourceType": "competition"
    }
   ],
   "dockerImageVersionId": 30626,
   "isGpuEnabled": false,
   "isInternetEnabled": true,
   "language": "python",
   "sourceType": "notebook"
  },
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.11.5"
  },
  "name": "getting_started.ipynb",
  "papermill": {
   "default_parameters": {},
   "duration": 10.734565,
   "end_time": "2023-12-21T15:06:22.363256",
   "environment_variables": {},
   "exception": null,
   "input_path": "__notebook__.ipynb",
   "output_path": "__notebook__.ipynb",
   "parameters": {},
   "start_time": "2023-12-21T15:06:11.628691",
   "version": "2.4.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}