prob_098-Copy2.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import re\n",
    "import itertools\n",
    "from itertools import permutations\n",
    "from collections import Counter, defaultdict\n",
    "from time import time\n",
    "from math import sqrt\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "('A', 'YOUTH')"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "data = np.genfromtxt('p098_words.txt',delimiter='\",\"',dtype=\"str\").tolist()\n",
    "data[0] = re.sub('\"','',data[0])\n",
    "data[-1] = re.sub('\"','',data[-1])\n",
    "data[0],data[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "N= 10**7\n",
    "sqdict = defaultdict(list)\n",
    "for i in range(N):\n",
    "    sqdict[''.join(sorted(str(i*i)))].append((i, i*i))\n",
    "    \n",
    "usefulkey = [sq for sq in sqdict if len(sqdict[sq])>1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "anagramicsquares = [-1 for _ in range(N)]\n",
    "for i in range(N):\n",
    "    key = ''.join(sorted(str(i*i)))\n",
    "    if len(sqdict[key]) > 1:\n",
    "        anagramicsquares[i] = max(sqdict[key][1])\n",
    "\n",
    "usefulsquareindex = [i for i in range(len(anagramicsquares)) if anagramicsquares[i]>1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def isSquare(num):\n",
    "    sqrtnum = int(sqrt(num))\n",
    "    return(sqrtnum*sqrtnum ==num)\n",
    "\n",
    "# def maxsqcombination(num):\n",
    "#     numstr = str(num)\n",
    "#     ps = [int(''.join(p)) for p in permutations(numstr)]\n",
    "#     ps = [p for p in ps if isSquare(p)]\n",
    "#     if len(ps) < 1:\n",
    "#         return(num,len(ps),0)\n",
    "#     else:\n",
    "#         return(num,len(ps),max(ps))\n",
    "\n",
    "def maxsqcombination(num):\n",
    "    if num*num not in usefulsquareindex:\n",
    "        return(num, 0)\n",
    "    else:\n",
    "        return(num, num)\n",
    "\n",
    "def findsquarenumber(word):\n",
    "    result = list()\n",
    "    wordcounter = Counter(word)\n",
    "    wordcounterkey = [k for k in wordcounter.keys()]\n",
    "    ndiffchr = len(wordcounterkey)\n",
    "    for p in permutations('0123456789', ndiffchr):\n",
    "        chrdict = dict()\n",
    "        for i in range(ndiffchr):\n",
    "            chrdict[wordcounterkey[i]] = p[i]\n",
    "        num = int(''.join([chrdict[s] for s in word]))\n",
    "        if len(str(num)) == len(word) and isSquare(num):\n",
    "            possiblesq = maxsqcombination(num)\n",
    "            if possiblesq[1] > 1:\n",
    "                result.append(possiblesq)\n",
    "    return(result)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0 A 0.00014901161193847656\n",
      "A 4 4 0\n",
      "A 4 4 4\n",
      "ABLE 2401 2401 4\n",
      "ABLE 2401 2401 2401\n",
      "ABLE 2601 2601 2401\n",
      "ABLE 2601 2601 2601\n",
      "ABLE 2704 2704 2601\n",
      "ABLE 2704 2704 2704\n",
      "ABLE 3025 3025 2704\n",
      "ABLE 3025 3025 3025\n",
      "10 ACCIDENT 47.327412843704224\n"
     ]
    }
   ],
   "source": [
    "maxnumval = 0\n",
    "maxpossibleval = 0\n",
    "minnchr = 0\n",
    "t0 = time()\n",
    "for i, word in enumerate(data):\n",
    "    if i%10 ==0:\n",
    "        print(i,word, time()-t0)\n",
    "    if len(word) >= minnchr:\n",
    "        sqnumber = findsquarenumber(word)\n",
    "        if len(sqnumber) > 0:\n",
    "            for sq in sqnumber:\n",
    "                if sq[0] > maxnumval:\n",
    "                    maxnumval = sq[0]\n",
    "                    minnchr = len(word)\n",
    "                    print(word, sq[0], maxnumval,maxpossibleval)\n",
    "                if sq[1] > maxpossibleval:\n",
    "                    maxpossibleval = sq[1]\n",
    "                    minnchr = len(word)\n",
    "                    print(word, sq[0], maxnumval,maxpossibleval)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "\n",
    "words = np.genfromtxt('p098_words.txt',delimiter='\",\"',dtype=\"str\").tolist()\n",
    "words[0] = re.sub('\"','',words[0])\n",
    "words[-1] = re.sub('\"','',words[-1])\n",
    "words = [w for w in words if len(w)>6]\n",
    "\n",
    "# # file_url = \"https://projecteuler.net/project/resources/p098_words.txt\"\n",
    "# # words = [(w[1:-1], sorted(w[1:-1])) \n",
    "# #     for w in urllib2.urlopen(file_url).read().split(',') if len(w)>6]\n",
    "\n",
    "word_pairs = []\n",
    "while words:\n",
    "    w = words.pop()\n",
    "    word_pairs+= ((w[0], a[0]) for a in words if w[1] == a[1])\n",
    "\n",
    "max_sq = 0\n",
    "for w, a in word_pairs:\n",
    "    letter_set = {x:y for y, x in enumerate(set(w))}\n",
    "    print(letter_set)\n",
    "    for y in itertools.permutations('123456789', len(letter_set)):\n",
    "        def sq(n):\n",
    "            x = int(''.join(y[letter_set[i]] for i in n))\n",
    "            return x if int(x**0.5)**2 == x else False\n",
    "        if sq(w) and sq(a): max_sq = max(sq(w), sq(a), max_sq)\n",
    "\n",
    "# print \"Largest square formed by any member of an anagram pair:\", max_sq"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "anaconda-cloud": {},
  "kernelspec": {
   "display_name": "Python [conda root]",
   "language": "python",
   "name": "conda-root-py"
  },
  "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.5.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}