3-1.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "\"\"\"\n",
    "3.6 version\n",
    "Lucky triple's are tuples (x,y,z) s.y. x|y & y|z\n",
    "You will be given a list and you need to count the number of lucky triples \n",
    "in the list. \n",
    "    The list consists of integers s.t. 2<=len(list)<=2000 and sup(list)<1000000\n",
    "    and 0<inf(list)\n",
    "    \n",
    "    The triples you must check must be of the form \\forall i,j,k i<j<k --> \n",
    "    allowed_triple(l[i],l[j],l[k])\n",
    "    \n",
    "    Your solution must fit within a signed 32-bit integer i.e. something like \n",
    "    2 billion elements. \n",
    "    \n",
    "\n",
    "Back of the envelope calc suggests there are ~ 8/6 billion many solutions at most, \n",
    "so I think the last condition is vacuous.\n",
    "\n",
    "\n",
    "Simplest possible implementation is something like\n",
    "\n",
    "\n",
    "is_lucky_triple = lambda x,y,z: 1 if x%y==0&y%z==0 else 0\n",
    "\n",
    "\n",
    "\n",
    "def solution(l):\n",
    "    accumulator = 0;\n",
    "    for k in range(len(l)):\n",
    "        for j in range(k):\n",
    "            for i in range(j):\n",
    "                accumulator += is_lucky_triple(l[i],l[j],l[k])\n",
    "    return accumulator;\n",
    "\n",
    "But this is quite slow. Maybe something faster would be to sort the indices, \n",
    "make an equality class of all the equivalent values and collapse the keys, but \n",
    "keeping a note of the keys, and then performing the operation over the keys which\n",
    "are elements of the list?\n",
    "\n",
    "Let's say you have a list\n",
    "[1,2,2,3,4]\n",
    "Make a dict and sort it by the key value to get\n",
    "{1:1, 2:2, 3:3, 4:3, 5:4}\n",
    "\n",
    "Create an equivalence class by values and log the number of keys to get\n",
    "    AH, YOU NEED TO KEEP THINGS IN ORDER so you can't treat make equivalence classes \n",
    "    that way. \n",
    "    \n",
    "    Like, if you had key:values 2:2 and 3:3 and 1:4 and 4:4 then you wouldn't be able \n",
    "    to do this stuff.\n",
    "    \n",
    "    BUT, maybe you could do something like \n",
    "    \n",
    "    {keys_1:value_1}, {keys_2:value_2}, {keys_3, value_3}\n",
    "    \n",
    "    Then check whether or not you have a lucky triple. \n",
    "    If so, then perform Sum_keys_1 Sum_keys_2 Sum_keys_3 1_{i<j<k}\n",
    "    Then add to to the accumulator.\n",
    "\n",
    "    This should be WAY more efficient when you a lot of elements in your list that\n",
    "    are the same.\n",
    "\n",
    "    \n",
    "Also you can speed thing up by checking if l[k]%l[j] !=0 first, then skipping if \n",
    "that's the case, which should be pretty often and will save on compute.\n",
    "\n",
    "\"\"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "is_lucky_triple = lambda x,y,z: 1 if y%x==0 and z%y==0 else 0\n",
    "\n",
    "\n",
    "def solution(l):\n",
    "    sorted_list =l\n",
    "    ls=[]\n",
    "    accumulator = 0;\n",
    "    for k in range(len(sorted_list)):\n",
    "        for j in range(k):\n",
    "            for i in range(j):\n",
    "                BOOL = is_lucky_triple(sorted_list[i],sorted_list[j],sorted_list[k]);\n",
    "                accumulator += is_lucky_triple(sorted_list[i],sorted_list[j],sorted_list[k])\n",
    "                if BOOL: \n",
    "                    ls.append([l[i],l[j],l[k]])\n",
    "                    print((i,j,k))\n",
    "    return (accumulator,ls)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def solution(l):\n",
    "    sorted_list = l\n",
    "    ls=[]\n",
    "    accumulator = 0;\n",
    "    for k in range(len(sorted_list)):\n",
    "        for j in range(k):\n",
    "            for i in range(j):\n",
    "                if l[k]%l[j]!=0:\n",
    "                    accumulator+=0\n",
    "                else:\n",
    "                    if l[j]%l[i]==0:\n",
    "                        accumulator+=1;\n",
    "                \n",
    "                #BOOL = is_lucky_triple(sorted_list[i],sorted_list[j],sorted_list[k]);\n",
    "                #accumulator += is_lucky_triple(sorted_list[i],sorted_list[j],sorted_list[k])\n",
    "                #if BOOL: ls.append([l[i],l[j],l[k]])\n",
    "    return accumulator"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "solution([1,2,10])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "\"\"\"\n",
    "\n",
    "\n",
    "Sum_k^n Sum_j^k Sum i^j 1_{j|k} 1_{i|j}\n",
    "\n",
    "Sum_k^N  Sum_j^k 1_{j|k} Sum_i^j 1_{i|j}\n",
    "\n",
    "\n",
    "Compute f[j] and store it.\n",
    "\n",
    "Sum_k^n Sum_j^k 1_{j,k} * f[j]\n",
    "\n",
    "\"\"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "\n",
    "def i_divides_j(ls):\n",
    "    table = [];\n",
    "    for j in range(len(ls)-1):\n",
    "        accumulator = 0;\n",
    "        for i in range(j):    \n",
    "            if ls[j]%ls[i]==0: accumulator+=1\n",
    "        table.append(accumulator)\n",
    "    return table\n",
    "                \n",
    "                \n",
    "def solution(ls):\n",
    "    accumulator =0;\n",
    "    table = i_divides_j(ls);\n",
    "    for k in range(len(ls)):\n",
    "        for j in range(k):\n",
    "            if ls[k]%ls[j] ==0:\n",
    "                accumulator+= table[j]\n",
    "    return accumulator"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3"
      ]
     },
     "execution_count": 35,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "solution([1,2,3,4,5,6])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "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
}