zahlenrätsel.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true,
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "from collections import Counter"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": true,
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "def reverse_dict(d):\n",
    "    revdict = {}\n",
    "    for k, v in d.items():\n",
    "        revdict.setdefault(v, set()).add(k) \n",
    "    return revdict"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": false,
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "500500\n"
     ]
    }
   ],
   "source": [
    "candidates = set(range(1,1000+1))\n",
    "keys = set((x,y) for x in candidates for y in candidates if x>=y)\n",
    "zsum = {(x,y):(x+y) for x in candidates for y in candidates if x>=y}\n",
    "zprod = {(x,y):(x*y) for x in candidates for y in candidates if x>=y}\n",
    "zdiff = {(x,y):(x-y) for x in candidates for y in candidates if x>=y}\n",
    "\n",
    "zprod_orig = zprod.copy()\n",
    "zsum_orig = zsum.copy()\n",
    "print(len(zsum))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": false,
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "355777\n"
     ]
    }
   ],
   "source": [
    "# \"peter: kenne zahlen nicht\" -> es gibt mehr als eine faktorzerlegung\n",
    "zprod_unique = reverse_dict(Counter(zprod.values()))[1] #pseudoprimes\n",
    "for x,y in keys:\n",
    "    if x*y in zprod_unique:\n",
    "        del zsum[(x,y)]\n",
    "        del zprod[(x,y)]\n",
    "        del zdiff[(x,y)]\n",
    "print(len(zsum))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": false,
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "zerlegungen = reverse_dict(zsum_orig)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": false,
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "27596\n"
     ]
    }
   ],
   "source": [
    "# \"simon: das wusste ich schon\" -> z1+z2 kann nicht als summe zweier primzahlen dargestellt werden!\n",
    "# entferne alle (x,y) bei denen (x+y) durch summe zweier primzahlen dargestellt werden kann\n",
    "\n",
    "excluded_sums = set()\n",
    "for sum, summands in zerlegungen.items():\n",
    "    for x,y in summands:\n",
    "        if x*y in zprod_unique:\n",
    "            excluded_sums.add(sum)\n",
    "            \n",
    "for x,y in keys:\n",
    "    if x+y in excluded_sums:\n",
    "        #pop instead of del b/c it might have been removed in step 1\n",
    "        zsum.pop((x,y), None)\n",
    "        zprod.pop((x,y), None)\n",
    "        zdiff.pop((x,y), None)\n",
    "print(len(zsum))\n",
    "\n",
    "zsum_prev = zsum.copy()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": false,
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "6984\n"
     ]
    }
   ],
   "source": [
    "# \"peter: dann kenne ich die zahlen jetzt\" -> davor gab es bei der faktorisierung mehrere möglichkeiten, jetzt gibt es nur noch eine\n",
    "zprod_candidate = reverse_dict(Counter(zprod.values()))[1] - reverse_dict(Counter(zprod_orig.values()))[1]\n",
    "\n",
    "rev_zprod = reverse_dict(zprod)\n",
    "zsum, zprod, zdiff = {}, {}, {}\n",
    "for prod in zprod_candidate:\n",
    "    for x,y in rev_zprod[prod]:\n",
    "        zsum[(x,y)] = x+y\n",
    "        zprod[(x,y)] = x*y\n",
    "        zdiff[(x,y)] = x-y\n",
    "\n",
    "print(len(zsum))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": false,
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "27\n"
     ]
    }
   ],
   "source": [
    "# \"simon: ich kenne sie jetzt auch\" -> davor gab es bei der summenbildung mehr als eine möglichkeit, jetzt gibt es noch genau eine\n",
    "zsum_candidate = reverse_dict(Counter(zsum.values()))[1] - reverse_dict(Counter(zsum_prev.values())).get(1, set())\n",
    "\n",
    "rev_zsum = reverse_dict(zsum)\n",
    "zsum, zprod, zdiff = {}, {}, {}\n",
    "for sum in zsum_candidate:\n",
    "    for x,y in rev_zsum[sum]:\n",
    "        zsum[(x,y)] = x+y\n",
    "        zprod[(x,y)] = x*y\n",
    "        zdiff[(x,y)] = x-y\n",
    "        \n",
    "print(len(zsum))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "collapsed": false,
    "scrolled": true
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{(4, 1): 5,\n",
       " (8, 1): 9,\n",
       " (9, 1): 10,\n",
       " (15, 1): 16,\n",
       " (16, 11): 27,\n",
       " (31, 8): 39,\n",
       " (32, 1): 33,\n",
       " (32, 13): 45,\n",
       " (32, 23): 55,\n",
       " (32, 29): 61,\n",
       " (37, 16): 53,\n",
       " (41, 32): 73,\n",
       " (43, 16): 59,\n",
       " (53, 32): 85,\n",
       " (61, 16): 77,\n",
       " (64, 37): 101,\n",
       " (64, 43): 107,\n",
       " (71, 32): 103,\n",
       " (71, 56): 127,\n",
       " (73, 16): 89,\n",
       " (73, 64): 137,\n",
       " (89, 8): 97,\n",
       " (97, 16): 113,\n",
       " (101, 8): 109,\n",
       " (101, 32): 133,\n",
       " (103, 16): 119,\n",
       " (109, 40): 149}"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "zsum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "collapsed": false,
    "scrolled": true
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{(4, 1): 4,\n",
       " (8, 1): 8,\n",
       " (9, 1): 9,\n",
       " (15, 1): 15,\n",
       " (16, 11): 176,\n",
       " (31, 8): 248,\n",
       " (32, 1): 32,\n",
       " (32, 13): 416,\n",
       " (32, 23): 736,\n",
       " (32, 29): 928,\n",
       " (37, 16): 592,\n",
       " (41, 32): 1312,\n",
       " (43, 16): 688,\n",
       " (53, 32): 1696,\n",
       " (61, 16): 976,\n",
       " (64, 37): 2368,\n",
       " (64, 43): 2752,\n",
       " (71, 32): 2272,\n",
       " (71, 56): 3976,\n",
       " (73, 16): 1168,\n",
       " (73, 64): 4672,\n",
       " (89, 8): 712,\n",
       " (97, 16): 1552,\n",
       " (101, 8): 808,\n",
       " (101, 32): 3232,\n",
       " (103, 16): 1648,\n",
       " (109, 40): 4360}"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "zprod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "collapsed": false,
    "scrolled": true
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{(4, 1): 3,\n",
       " (8, 1): 7,\n",
       " (9, 1): 8,\n",
       " (15, 1): 14,\n",
       " (16, 11): 5,\n",
       " (31, 8): 23,\n",
       " (32, 1): 31,\n",
       " (32, 13): 19,\n",
       " (32, 23): 9,\n",
       " (32, 29): 3,\n",
       " (37, 16): 21,\n",
       " (41, 32): 9,\n",
       " (43, 16): 27,\n",
       " (53, 32): 21,\n",
       " (61, 16): 45,\n",
       " (64, 37): 27,\n",
       " (64, 43): 21,\n",
       " (71, 32): 39,\n",
       " (71, 56): 15,\n",
       " (73, 16): 57,\n",
       " (73, 64): 9,\n",
       " (89, 8): 81,\n",
       " (97, 16): 81,\n",
       " (101, 8): 93,\n",
       " (101, 32): 69,\n",
       " (103, 16): 87,\n",
       " (109, 40): 69}"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "zdiff"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "collapsed": false,
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "# \"kenne die beiden zahlen noch nicht\" -> gibt noch mehr als eine mögliche zerlegung der differenz\n",
    "# lösche alle differenzen, die mittlerweile eindeutig wären\n",
    "unique_zdiff = reverse_dict(Counter(zdiff.values()))[1]\n",
    "rev_zdiff = reverse_dict(zdiff)\n",
    "\n",
    "for diff in unique_zdiff:\n",
    "    for x,y in rev_zdiff[diff]:\n",
    "        del zsum[(x,y)]\n",
    "        del zprod[(x,y)]\n",
    "        del zdiff[(x,y)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "collapsed": false,
    "scrolled": true
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{(4, 1): 5,\n",
       " (32, 23): 55,\n",
       " (32, 29): 61,\n",
       " (37, 16): 53,\n",
       " (41, 32): 73,\n",
       " (43, 16): 59,\n",
       " (53, 32): 85,\n",
       " (64, 37): 101,\n",
       " (64, 43): 107,\n",
       " (73, 64): 137,\n",
       " (89, 8): 97,\n",
       " (97, 16): 113,\n",
       " (101, 32): 133,\n",
       " (109, 40): 149}"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "zsum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "collapsed": false,
    "scrolled": true
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{(4, 1): 4,\n",
       " (32, 23): 736,\n",
       " (32, 29): 928,\n",
       " (37, 16): 592,\n",
       " (41, 32): 1312,\n",
       " (43, 16): 688,\n",
       " (53, 32): 1696,\n",
       " (64, 37): 2368,\n",
       " (64, 43): 2752,\n",
       " (73, 64): 4672,\n",
       " (89, 8): 712,\n",
       " (97, 16): 1552,\n",
       " (101, 32): 3232,\n",
       " (109, 40): 4360}"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "zprod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {
    "collapsed": false,
    "scrolled": true
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{(4, 1): 3,\n",
       " (32, 23): 9,\n",
       " (32, 29): 3,\n",
       " (37, 16): 21,\n",
       " (41, 32): 9,\n",
       " (43, 16): 27,\n",
       " (53, 32): 21,\n",
       " (64, 37): 27,\n",
       " (64, 43): 21,\n",
       " (73, 64): 9,\n",
       " (89, 8): 81,\n",
       " (97, 16): 81,\n",
       " (101, 32): 69,\n",
       " (109, 40): 69}"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "zdiff"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {
    "collapsed": false,
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{9} {9: 32}\n"
     ]
    }
   ],
   "source": [
    "# \"eine zahl ist wahrscheinlich\"\n",
    "from operator import itemgetter\n",
    "rev_zdiff = reverse_dict(zdiff)\n",
    "\n",
    "zdiff_candidate = set()\n",
    "likely_number = dict()\n",
    "for k in rev_zdiff.keys():\n",
    "    cnt = Counter()\n",
    "    for x, y in rev_zdiff[k]:\n",
    "        cnt[x]+=1; cnt[y]+=1\n",
    "        sort = sorted(cnt.items(), key=itemgetter(1), reverse=True)\n",
    "        more_likely = sort[0][1] > sort[1][1]\n",
    "        if more_likely:\n",
    "            zdiff_candidate.add(k)\n",
    "            likely_number[k] = sort[0][0]\n",
    "            \n",
    "print(zdiff_candidate, likely_number)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# \"die wahrscheinliche zahl ist aber falsch\"\n",
    "zdiff = {k:v for k, v in zdiff.items() if v in zdiff_candidate and all(x != likely_number[v] for x in k)}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{(73, 64): 9}"
      ]
     },
     "execution_count": 42,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "zdiff"
   ]
  }
 ],
 "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.5.3+"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}