euler_hack_011.ipynb

euler_hack_011.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "%reload_ext Cython\n",
    "# %%cython\n",
    "\n",
    "import io\n",
    "import re\n",
    "import csv\n",
    "import json\n",
    "import math\n",
    "import random\n",
    "import numbers\n",
    "import decimal\n",
    "import fractions\n",
    "import statistics\n",
    "import collections\n",
    "import operator as op\n",
    "import itertools as it\n",
    "import functools as ft"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Euler Hack #11 (2017-08-14)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "## Problem 7 - 10001st prime\n",
    "\n",
    "By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6th prime is 13.\n",
    "\n",
    "What is the 10 001st prime number?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "104743"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def is_prime(candidate, primes):\n",
    "    candidate_sqrt = candidate ** 0.5\n",
    "    for prime in primes:\n",
    "        if prime > candidate_sqrt:\n",
    "            return True\n",
    "        if candidate % prime == 0:\n",
    "            return False\n",
    "    return True\n",
    "\n",
    "def primes(num_primes):\n",
    "    primes = [2, 3, 5]\n",
    "    candidate = 7\n",
    "    while len(primes) < num_primes:\n",
    "        if is_prime(candidate, primes):\n",
    "            primes.append(candidate)\n",
    "        candidate += 2\n",
    "    return primes\n",
    "\n",
    "primes(10001)[-1]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Problem 102 - Triangle containment\n",
    "\n",
    "Three distinct points are plotted at random on a Cartesian plane, for which -1000 ≤ x, y ≤ 1000, such that a triangle is formed.\n",
    "\n",
    "Consider the following two triangles:\n",
    "\n",
    "    A(-340,495), B(-153,-910), C(835,-947)\n",
    "    X(-175,41), Y(-421,-714), Z(574,-645)\n",
    "\n",
    "It can be verified that triangle ABC contains the origin, whereas triangle XYZ does not.\n",
    "\n",
    "Using triangles.txt (right click and 'Save Link/Target As...'), a 27K text file containing the co-ordinates of one thousand \"random\" triangles, find the number of triangles for which the interior contains the origin.\n",
    "\n",
    "NOTE: The first two examples in the file represent the triangles in the example given above."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [],
   "source": [
    "point = collections.namedtuple('point', ['x', 'y'])\n",
    "\n",
    "with open(\"share/p102_triangles.txt\") as fh:\n",
    "    triangles = [\n",
    "        (\n",
    "            point(*(int(n) for n in l.strip().split(\",\")[:2])),\n",
    "            point(*(int(n) for n in l.strip().split(\",\")[2:4])),\n",
    "            point(*(int(n) for n in l.strip().split(\",\")[4:])),\n",
    "        )\n",
    "        for l in fh\n",
    "    ]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "                 Y  A\n",
    "                    |\n",
    "                    |\n",
    "               a    |\n",
    "                    |   d    \n",
    "                  e |    \n",
    "    ----------------o-----------------> X\n",
    "                    |    f        \n",
    "                    |       \n",
    "                   b|        c\n",
    "               h    |\n",
    "                    |"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 84,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[(0, 1), (1, 0)]\n",
      "[(0, 0), (0, 0)]\n",
      "[(0, -1), (-1, 0)]\n",
      "[(1, 0)]\n",
      "[(0, -1)]\n"
     ]
    }
   ],
   "source": [
    "def axis_intersects(A, B):\n",
    "    dx = (A.x - B.x)\n",
    "    dy = (A.y - B.y)\n",
    "\n",
    "    yi_ok = A.x * B.x <= 0\n",
    "    xi_ok = A.y * B.y <= 0\n",
    "        \n",
    "    if dy == 0:\n",
    "        if yi_ok:\n",
    "            yield point(A.x, 0)\n",
    "        return\n",
    "    \n",
    "    if dx == 0:\n",
    "        if xi_ok:\n",
    "            yield point(0, A.y)\n",
    "        return\n",
    "    \n",
    "    slope2 = dx / dy\n",
    "    b2 = -slope2 * A.y + A.x\n",
    "    yi = b2\n",
    "\n",
    "    slope1 = dy / dx\n",
    "    b1 = -slope1 * A.x + A.y\n",
    "    xi = b1\n",
    "    \n",
    "    if yi_ok:\n",
    "        yield point(0, xi)\n",
    "    if xi_ok:\n",
    "        yield point(yi, 0)\n",
    "\n",
    "\n",
    "def norm_coords(intersections):\n",
    "    isects = list(intersections)\n",
    "    return [\n",
    "        (\n",
    "            int(isect.x / abs(isect.x) if isect.x != 0 else 0),\n",
    "            int(isect.y / abs(isect.y) if isect.y != 0 else 0),\n",
    "        )\n",
    "        for isect in isects\n",
    "    ]\n",
    "\n",
    "print(norm_coords(axis_intersects(point(1, 0), point(0, 1))))\n",
    "print(norm_coords(axis_intersects(point(1, 1), point(-1, -1))))\n",
    "print(norm_coords(axis_intersects(point(-1, 0), point(0, -1))))\n",
    "print(norm_coords(axis_intersects(point(1, 1), point(-1, 1))))\n",
    "print(norm_coords(axis_intersects(point(1, -1), point(1, 1))))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 86,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "228\n"
     ]
    }
   ],
   "source": [
    "result = 0\n",
    "\n",
    "for a, b, c in triangles:\n",
    "    intersects = set((\n",
    "        norm_coords(axis_intersects(a, b)) + \n",
    "        norm_coords(axis_intersects(b, c)) +\n",
    "        norm_coords(axis_intersects(a, c))\n",
    "    ))\n",
    "    if len(intersects) == 4:\n",
    "        result += 1\n",
    "            \n",
    "print(result)"
   ]
  },
  {
   "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.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}