{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Problem Set 1 - Part A"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This part of problem set 1 has **2 questions** and a total of **30 points**."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Question 1 (On the 4x4x4 Rubik's cube group action)\n",
    "\n",
    "This question is going to deal about the 4x4x4 Rubik's cube. Of course, we want to think of it as a group acting on 96 stickers. We'll use the following natural numbering.\n",
    "\n",
    "<pre>\n",
    "                    Up\n",
    "              +-------------+\n",
    "              |  1  2  3  4 |\n",
    "              |  5  6  7  8 |\n",
    "              |  9 10 11 12 |\n",
    "     Left     | 13 14 15 16 |    Right         Back\n",
    "+-------------+-------------+-------------+-------------+\n",
    "| 17 18 19 20 | 33 34 35 36 | 49 50 51 52 | 65 66 67 68 |\n",
    "| 21 22 23 24 | 37 38 39 40 | 53 54 55 56 | 69 70 71 72 |\n",
    "| 25 26 27 28 | 41 42 43 44 | 57 58 59 60 | 73 74 75 76 |\n",
    "| 29 30 31 32 | 45 46 47 48 | 61 62 63 64 | 77 78 79 80 |\n",
    "+-------------+-------------+-------------+-------------+\n",
    "              | 81 82 83 84 |\n",
    "              | 85 86 87 88 |\n",
    "              | 89 90 91 91 |\n",
    "              | 93 94 95 96 |\n",
    "              +-------------+\n",
    "                    Down\n",
    "</pre>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "1. **[0 points]** Without running any code, how many different orbits do these 96 stickers get partitioned into when considering all valid Rubik's cube moves? "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "2. **[2 points]** Use Sage to actually compute the orbits and see how many there are. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "S96 = SymmetricGroup(96)\n",
    "moves = {\n",
    "    \"1L\": S96([(1,33,81,80),(5,37,85,76),(9,41,89,72),(13,45,93,68),\n",
    "               (17,20,32,29),(18,24,31,25),(19,28,30,21),(22,23,27,26)]),    \n",
    "    \"2L\": S96([(2,34,82,79),(6,38,86,75),(10,42,90,71),(14,46,94,67)]),\n",
    "    \"1R\": S96([(4,77,84,36),(8,73,88,40),(12,69,92,44),(16,65,96,48),\n",
    "               (49,52,64,61),(50,56,63,57),(51,60,62,53),(54,55,59,58)]),\n",
    "    \"2R\": S96([(3,78,83,35),(7,74,87,39),(11,70,91,43),(15,66,95,47)]),\n",
    "    \"1F\": S96([(13,49,84,32),(14,53,83,28),(15,57,82,24),(16,61,81,20),\n",
    "               (33,36,48,45),(34,40,47,41),(35,44,46,37),(38,39,43,42)]),\n",
    "    \"2F\": S96([(9,50,88,31),(10,54,87,27),(11,58,86,23),(12,62,85,19)]),\n",
    "    \"1B\": S96([(1,29,96,52),(2,25,95,56),(3,21,94,60),(4,17,93,64),\n",
    "               (65,68,80,77),(66,72,79,73),(67,76,78,69),(70,71,75,74)]),\n",
    "    \"2B\": S96([(5,30,92,51),(6,26,91,55),(7,22,90,59),(8,18,89,63)]),\n",
    "    \"1D\": S96([(29,45,61,77),(30,46,62,78),(31,47,63,79),(32,48,64,80),\n",
    "               (81,84,96,93),(82,88,95,89),(83,92,94,85),(86,87,91,90)]),\n",
    "    \"2D\": S96([(25,41,57,73),(26,42,58,74),(27,43,59,75),(28,44,60,76)]),\n",
    "    \"1U\": S96([(1,4,16,13),(2,8,15,9),(3,12,14,5),(6,7,11,10),\n",
    "               (17,65,49,33),(18,66,50,34),(19,67,51,35),(20,68,52,36)]),\n",
    "    \"2U\": S96([(21,69,53,37),(22,70,54,38),(23,71,55,39),(24,72,56,40)])\n",
    "}\n",
    "R4 = PermutationGroup(list(moves.values()))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "3. **[2 points]** What was perhaps surprising about the previous answer? "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "4. **[6 points]** Use the site [alg.cubing.net](https://alg.cubing.net?puzzle=4x4x4) and construct a suitable sequence of moves that cycles through 3 edge pieces (pieces such as (14,34) or (15,35) etc.).\n",
    "   \n",
    "   **[+4 points]** if your sequence happens to cycle through three edge pieces on the same face. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "5. **[1 point]** Check if the move permutation $(14, 34)(15, 35)$ is present in the group `R4` or not. \n",
    "\n",
    "   **[1 point]** What about the permutation $(14, 35) (15, 34)$?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "6. **[4 points]** Use the site [alg.cubing.net](https://www.alg.cubing.net?puzzle=4x4x4) and try out the following sequence:\n",
    "\n",
    "   1R 2R 1U 1U 1R 2R 1F 1F 2R 1F 1F 2L 2L 2L 1U 1U 2L 1U 1U 2R 2R 2R 1U 1U 2R 1U 1U 1R 1R 1R 2R 2R 2R 1U 1U 1R 1R 1R 2R 2R 2R\n",
    "   \n",
    "   Explain the fallacy that you observe."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Question 2 (Action on vertices to action on edges)\n",
    "\n",
    "There are situations where you have a group $G$ acting on $[n]$ vertices. We had discussed a few situation where shuffling the vertices naturally ends up shuffling the edges. \n",
    "\n",
    "**[10 points]** Write a function that takes as input a permutation on $n$ elements and outputs its representation as an permutation on the $n^2$ pairs.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def lift_permutation_to_pairs(sigma, n = None):\n",
    "    '''\n",
    "    Write a function that takes as input a permutation sigma on [1,...,n]\n",
    "    and returns a permutation on [1,...,n^2] that is meant to be the \n",
    "    representation of sigma when interpretted as a shuffling of pairs.\n",
    "    '''\n",
    "\n",
    "    if n is None: n = 10\n",
    "    \n",
    "    vertices = [ i + 1 for i in range(n) ]\n",
    "    pairs = [ (i + 1, j + 1) for i in range(n) for j in range(n) ]\n",
    "    \n",
    "    Sn = SymmetricGroup(vertices)\n",
    "    \n",
    "    # Can't directly feed 'pairs' as the argument as SymmetricGroup() either\n",
    "    # expects an integer, or an array of distinct integers as input.\n",
    "    \n",
    "    Sn2 = SymmetricGroup([ i + 1 for i in range(n * n)]) \n",
    "\n",
    "    # Let say n = 10.\n",
    "    # We can use 1, ... , 100 to refer to these pairs in the order of the above list. \n",
    "    # \n",
    "    # For example, the pair (5,3) corresponds to pair number 'edges.index((5,3)) + 1'\n",
    "    # And you can access the pair corresponding to 17 via edges[17 - 1]\n",
    "    #\n",
    "    # (The annoying +1/-1 is to deal with the fact that indices go from 0 onwards in arrays)\n",
    "    \n",
    "\n",
    "    # do blah blah blah\n",
    "    # return pi\n",
    "    \n",
    "    pass"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Here is an example run (for n = 4):\n",
    "```\n",
    "Sn = SymmetricGroup(4)\n",
    "sigma = Sn([(1,2,3,4)])\n",
    "lift_permutation_to_pairs(sigma, 4)\n",
    "\n",
    "# output is (1,6,11,16)(2,7,12,13)(3,8,9,14)(4,5,10,15)\n",
    "#\n",
    "# The first cycles corresponds to (1,1) -> (2,2) -> (3,3) -> (4,4) -> (1,1)\n",
    "# and the second cycle corresponds to (1,2) -> (2,3) -> (3,4) -> (4,1) -> (1,2)\n",
    "# etc.\n",
    "```"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "SageMath 9.4",
   "language": "sage",
   "name": "sagemath-9.4"
  },
  "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.9.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}