359 [Hard] Primes in Grids.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This puzzle was first proposed (1989) by [Gordon Lee](http://www.primepuzzles.net/puzzles/puzz_001.htm): given a grid of numbers, how many distinct primes can you find embedded in the matrix, regarding that you can read the lines or part of them, in form vertical, horizontal or diagonal orientation, in both directions.\n",
    "\n",
    "Note that you can't change direction once you start moving (e.g. this isn't Boggle).\n",
    "\n",
    "Input Description\n",
    "You'll be given a single number on a line which tells you how many rows and columns to read (all grids will be square). Example:\n",
    "\n",
    "    3 \n",
    "    113\n",
    "    754\n",
    "    937"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1 loop, best of 1: 10.8 ms per loop\n"
     ]
    }
   ],
   "source": [
    "L = \"\"\"3 \n",
    "113\n",
    "754\n",
    "937,5 \n",
    "11933\n",
    "99563\n",
    "89417\n",
    "33731\n",
    "32939,6\n",
    "317333\n",
    "995639\n",
    "118142\n",
    "136373\n",
    "349199\n",
    "379379,40\n",
    "0251677085866837460317708637021446063144\n",
    "8812262220360202463050064531874436437682\n",
    "5251855367278508848642345043775871434078\n",
    "0042675865438283025822603307175060748288\n",
    "5672321632434878440388701468545837465571\n",
    "3448326728143606881852187616524878044060\n",
    "8876415778774852362710315274652021065556\n",
    "1406474838287088561242126854006826771778\n",
    "7827443331184330371521043472218803550383\n",
    "6318874838447276075161123302780187880165\n",
    "0884752758538865306583258450386821283658\n",
    "1260362124615176735303563717773657467333\n",
    "2580363145201308707655341168610513145546\n",
    "4142635386876777348215436708254351251288\n",
    "5301330463217260626047132625527161775404\n",
    "8620446353006857360714856156584322276288\n",
    "0813375760405334773480860674772272733638\n",
    "6715558007108501053612008324501255710425\n",
    "8840634327383685827335506853781648727036\n",
    "8827728873376824454871536655067801443735\n",
    "0664640563836487481174816586572628815173\n",
    "7186752536147276768154002317573417465332\n",
    "4438770023402783205544064640821537621225\n",
    "4162442401558771474140203865162080237721\n",
    "5008757506737224070577338578644664641338\n",
    "2155803687408638660278862273674652462840\n",
    "2118148017744113203720114756276821067158\n",
    "4838003412436782114402742024145245437315\n",
    "5161343527676283186170466281455700086618\n",
    "7723886261287175705152273086317588317188\n",
    "6653360024271146551000054710768617586846\n",
    "0050014847531086708661266564560614115164\n",
    "3351156208161708784441387827072734346251\n",
    "0457546342466313073230326436563643506534\n",
    "3837451141488371231210888733717540046582\n",
    "3334248265835234158638343058444640886465\n",
    "0173240266426385002380821305357684721128\n",
    "0437020214873361352055818843664073456138\n",
    "3858604586068245520287541000014334760058\n",
    "5840781588142205318614583635575571714673\"\"\".split(',')\n",
    "\n",
    "\n",
    "inx = \"\"\"6\n",
    "317333\n",
    "995639\n",
    "118142\n",
    "136373\n",
    "349199\n",
    "379379\"\"\"\n",
    "\n",
    "import numpy as np\n",
    "from sympy import isprime\n",
    "\n",
    "def prep_data(inx):\n",
    "    r = inx.split('\\n')\n",
    "    A = np.array([[x for x in y.strip()] for y in r[1:]])\n",
    "    s = int(r[0])\n",
    "    S = set()\n",
    "    \n",
    "    dia = [A[::-1,:].diagonal(i) for i in range(-s+1,s)]\n",
    "    dia += [A.diagonal(i) for i in range(s-1,-s,-1)]\n",
    "    dia += [A[i] for i in range(s)]\n",
    "    dia += [A.T[i] for i in range(s)]\n",
    "    \n",
    "    def substrings(L):\n",
    "        L_rev = L[::-1]\n",
    "        l = len(L)\n",
    "        for x in range(l):\n",
    "            n = l-x\n",
    "            for y in range(n):\n",
    "                S.add(int(L[x:x+y+1]))\n",
    "                S.add(int(L_rev[x:x+y+1]))\n",
    "    for x in dia:\n",
    "        substrings(''.join(x.tolist()))\n",
    "    return S\n",
    "\n",
    "%timeit -n1 -r1 sum(isprime(x) for x in prep_data(inx) if x > 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "30 (0.031 secs)\n",
      "116 (0.139 secs)\n",
      "187 (0.215 secs)\n",
      "5487 (18.048 secs)\n"
     ]
    }
   ],
   "source": [
    "import numpy as np\n",
    "import time\n",
    "from random import randint\n",
    "\n",
    "def grid_primes(s):\n",
    "    start = time.time()\n",
    "\n",
    "    size = int(s[:s.find('\\n')])\n",
    "    grid = np.array(list(s[2:].replace('\\n', ''))).reshape([size, -1])\n",
    "    lines, seq = set(), set()\n",
    "\n",
    "    for i in range(size):\n",
    "        lines.add(''.join(grid[:, i])) # columns\n",
    "        lines.add(''.join(grid[i])) # rows\n",
    "\n",
    "    for _ in range(4):\n",
    "        for i in range(size):\n",
    "            lines.add(''.join(grid.diagonal(i))) # diagonals\n",
    "        grid = np.rot90(grid) \n",
    "\n",
    "    for line in lines:\n",
    "        for i in range(len(line)):\n",
    "            for j in range(i + 1, size + 1):\n",
    "                if line[i:j][0] != '0':\n",
    "                    seq.add(line[i:j])\n",
    "                if line[i:j][::-1][0] != '0':\n",
    "                    seq.add(line[i:j][::-1])\n",
    "\n",
    "    def miller_rabin_test(n):\n",
    "        k, t, d = 100, 0, n - 1\n",
    "\n",
    "        if n == 1:\n",
    "            return False\n",
    "        if n == 2:\n",
    "            return True\n",
    "        if n % 2 == 0:\n",
    "            return False\n",
    "\n",
    "        while d % 2 == 0:\n",
    "            t += 1\n",
    "            d //= 2\n",
    "        for _ in range(k):\n",
    "            a = randint(2, n - 1)\n",
    "            res = pow(a, d, n)\n",
    "            if res == 1:\n",
    "                continue\n",
    "            for _ in range(t - 1):\n",
    "                if res == n - 1:\n",
    "                    break\n",
    "                res = pow(res, 2, n)\n",
    "            if res != n - 1:\n",
    "                return False\n",
    "        return True\n",
    "\n",
    "    seq = [int(i) for i in seq]   \n",
    "    primes = len([n for n in seq if miller_rabin_test(n)])\n",
    "\n",
    "    print('{} ({} secs)'.format(primes, round(time.time() - start, 3)))\n",
    "\n",
    "for x in L:\n",
    "    grid_primes(x)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "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.6.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}