2020-08-21_clockwise-spiral-matrix.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This problem was asked by Amazon.\n",
    "\n",
    "Given a N by M matrix of numbers, print out the matrix in a clockwise spiral.\n",
    "\n",
    "For example, given the following matrix:\n",
    "```\n",
    "[[1,  2,  3,  4,  5],\n",
    " [6,  7,  8,  9,  10],\n",
    " [11, 12, 13, 14, 15],\n",
    " [16, 17, 18, 19, 20]]\n",
    "```\n",
    "You should print out the following:\n",
    "```\n",
    "1\n",
    "2\n",
    "3\n",
    "4\n",
    "5\n",
    "10\n",
    "15\n",
    "20\n",
    "19\n",
    "18\n",
    "17\n",
    "16\n",
    "11\n",
    "6\n",
    "7\n",
    "8\n",
    "9\n",
    "14\n",
    "13\n",
    "12\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [],
   "source": [
    "def print_clockwise_spiral(mat):\n",
    "    \"\"\"Print matrix values in a clockwise spiral, starting from top-left.\n",
    "    \n",
    "    For a matrix with N rows and M columns, starting outside the matrix at (0, -1), any particular\n",
    "    movement is repeated N-k times for vertical displacements (M-k times for horizontal displacements),\n",
    "    where k is incremented by one after every even number of rotations:\n",
    "    M right --> N-1 down --> M-1 left --> N-2 up --> M-2 right --> N-3 down --> etc.\n",
    "    \"\"\"\n",
    "    N, M = dim(mat)\n",
    "    reps = [N, M]\n",
    "    irep = 1\n",
    "    moves = [(0, 1), (1, 0), (0, -1), (-1, 0)]\n",
    "    imove = 0\n",
    "    i = 0\n",
    "    j = -1\n",
    "    while min(reps) > 0:\n",
    "        # repeated displacement in one direction\n",
    "        for _ in range(reps[irep]):\n",
    "            i += moves[imove][0]\n",
    "            j += moves[imove][1]\n",
    "            print(mat[i][j])\n",
    "        # update direction and repeats\n",
    "        imove, irep = rotate(moves, reps, imove, irep)\n",
    "\n",
    "def dim(mat):\n",
    "    N = len(mat)\n",
    "    M = len(mat[0])\n",
    "    return N, M\n",
    "\n",
    "def rotate(moves, reps, imove, irep):\n",
    "    if imove % 2 == 0:\n",
    "        reps[0] -= 1\n",
    "        reps[1] -= 1\n",
    "    imove = (imove + 1) % 4\n",
    "    irep = (irep + 1) % 2\n",
    "    return imove, irep"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n",
      "2\n",
      "3\n",
      "4\n",
      "5\n",
      "10\n",
      "15\n",
      "20\n",
      "19\n",
      "18\n",
      "17\n",
      "16\n",
      "11\n",
      "6\n",
      "7\n",
      "8\n",
      "9\n",
      "14\n",
      "13\n",
      "12\n"
     ]
    }
   ],
   "source": [
    "mat = [\n",
    "    [1,  2,  3,  4,  5],\n",
    "    [6,  7,  8,  9,  10],\n",
    "    [11, 12, 13, 14, 15],\n",
    "    [16, 17, 18, 19, 20]\n",
    "]\n",
    "print_clockwise_spiral(mat)"
   ]
  }
 ],
 "metadata": {
  "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.7.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}