IqbalPuzzle.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Iqbal's puzzle"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Generate all unique factorisations by picking numbers in sorted order"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "# N: Number to be factorised\n",
    "# k: Number of terms in factorisation\n",
    "# s: Smallest element constraint\n",
    "def factorisations(N,k,s):\n",
    "    # Base case first\n",
    "    if k==1: return [[N]]\n",
    "    \n",
    "    # Current element has to be at least s\n",
    "    i = s\n",
    "    ret = []\n",
    "    \n",
    "    # Since numbers are in sorted order, current pick has to be at most N^(1/k)\n",
    "    while i**k <= N:\n",
    "        if N%i == 0:\n",
    "            # If i is a factor of N, recurse with lower limit as i\n",
    "            temp = factorisations(N//i,k-1,i)\n",
    "            temp\n",
    "            for factorisation in temp:\n",
    "                ret.append(list([i])+factorisation)\n",
    "        i +=1\n",
    "    return ret"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Generate factorisations of 36 into three"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[[1, 1, 36],\n",
       " [1, 2, 18],\n",
       " [1, 3, 12],\n",
       " [1, 4, 9],\n",
       " [1, 6, 6],\n",
       " [2, 2, 9],\n",
       " [2, 3, 6],\n",
       " [3, 3, 4]]"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "F = factorisations(36,3,1)\n",
    "F"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Group them by sum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "defaultdict(list,\n",
       "            {38: [[1, 1, 36]],\n",
       "             21: [[1, 2, 18]],\n",
       "             16: [[1, 3, 12]],\n",
       "             14: [[1, 4, 9]],\n",
       "             13: [[1, 6, 6], [2, 2, 9]],\n",
       "             11: [[2, 3, 6]],\n",
       "             10: [[3, 3, 4]]})"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "from collections import defaultdict\n",
    "S = defaultdict(list)\n",
    "for fac in F:\n",
    "    s = sum(fac)\n",
    "    S[s].append(fac)\n",
    "S"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "It can be seen that only the sum 13 gives two possibilities for the ages, and only [2,2,9] gives a single oldest child"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "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.7"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}