Project Euler problem 104 in Julia.

Problem104.ipynb

{
 "metadata": {
  "language": "Julia",
  "name": ""
 },
 "nbformat": 3,
 "nbformat_minor": 0,
 "worksheets": [
  {
   "cells": [
    {
     "cell_type": "heading",
     "level": 1,
     "metadata": {},
     "source": [
      "Pandigit checking in Fibonacci Numbers"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "[Project Euler problem 104](http://projecteuler.net/problem=104) is to write an algorithm to determine the first Fibonacci number for which the first 9 digits are 1-9 pandigital and the last 9 digits are also pandigital, where pandigital means that these digits are a permutation of 1 to 9.\n",
      "\n",
      "Because the answer is going to be a very large number the `BigInt` class is the most convenient representation for storing and manipulating these numbers. Although the compute time and the amount of storage required will be dominated by the operations of adding, storing and converting these numbers to strings of digits, it is still worthwhile being careful how we create and store the Fibonacci numbers."
     ]
    },
    {
     "cell_type": "heading",
     "level": 2,
     "metadata": {},
     "source": [
      "Generating the Fibonacci numbers"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "An obvious approach to generating the numbers in the Fibonacci sequence is to store the numbers in a vector, generating the i'th value from the previous two values and pushing it onto the end of the vector. On a modern computer this approach will be fine for a few hundred or a few thousand values but it will slow down terribly when requiring hundreds of thousands of Fibonacci numbers, as this problem does.\n",
      "\n",
      "Consider instead storing the last two values in the sequence and updating them. The current state, stored as a vector of two `BigInt`s, is initialized to a pair of ones and thereafter each step involves replacing the second last number by the sum of these two.\n",
      "\n",
      "One way to do this is to shift the two values on every update, as in"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "function nextfib(st::Vector{BigInt})\n",
      "    n = st[1] + st[2]\n",
      "    st[1] = st[2]\n",
      "    st[2] = n\n",
      "    n\n",
      "end"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 1,
       "text": [
        "nextfib (generic function with 1 method)"
       ]
      }
     ],
     "prompt_number": 1
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "However, we may want to store the index into the sequence along with the value, in which case we could represent the state as a user-defined type."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "type FibState\n",
      "    i::Int\n",
      "    s::Vector{BigInt}\n",
      "    FibState() = new(2,ones(BigInt,2))    \n",
      "end"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 2
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "The function `FibState` defined within the `FibState` type is an _internal constructor_.  It is used to initialize the state to the second index with both the first and second values being 1, represented as a `BigInt`.\n",
      "\n",
      "When we increment a `FibState` object we can alternate between replacing the first and the second values in the vector `s`, according to the value of `i`.  We also provide extractors for the value and the index."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "function increment(st::FibState)\n",
      "    s = st.s\n",
      "    st.i += 1\n",
      "    s[isodd(st.i) ? 1 : 2] = s[1] + s[2]\n",
      "    st\n",
      "end\n",
      "index(st::FibState) = st.i\n",
      "value(st::FibState) = st.s[isodd(st.i) ? 1 : 2]"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 3,
       "text": [
        "value (generic function with 1 method)"
       ]
      }
     ],
     "prompt_number": 3
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Let's check that this works as intended."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "st = FibState()\n",
      "while index(increment(st)) <= 20\n",
      "    println(index(st),\": \",value(st))\n",
      "end"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "3: "
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "2\n",
        "4: 3\n",
        "5: 5\n",
        "6: 8\n",
        "7: 13\n",
        "8: 21\n",
        "9: 34\n",
        "10: 55\n",
        "11: 89\n",
        "12: 144\n",
        "13: 233\n",
        "14: 377\n",
        "15: 610\n",
        "16: 987\n",
        "17: 1597\n",
        "18: 2584\n",
        "19: 4181\n",
        "20: 6765\n"
       ]
      }
     ],
     "prompt_number": 4
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "We are very close to having an `iterator` which is a type that provides methods for `length`, `start`, `next` and `done` but we will leave that for another time"
     ]
    },
    {
     "cell_type": "heading",
     "level": 2,
     "metadata": {},
     "source": [
      "Checking for first or last 9 digits being pandigital"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Methods for the `string` function produce character strings from other types of objects. We can add a `string` method for the `FibState` type."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "import Base.string     # so we can add string methods\n",
      "string(st::FibState) = string(value(st))\n",
      "string(st)             # recall that index is now 21"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 5,
       "text": [
        "\"10946\""
       ]
      }
     ],
     "prompt_number": 5
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "The string itself consists of an vector of bytes (the type `Uint8`)."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "names(\"10946\")"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 6,
       "text": [
        "1-element Array{Any,1}:\n",
        " :data"
       ]
      }
     ],
     "prompt_number": 6
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "typeof(\"10946\".data)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 7,
       "text": [
        "Array{Uint8,1}"
       ]
      }
     ],
     "prompt_number": 7
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "We could use the `int` function to convert the digits in a string to integers but it is a bit cleaner to subtract the character representation of `0` from the elements."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "show(\"10946\".data - '0')"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "["
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "0x01,0x00,0x09,0x04,0x06]"
       ]
      }
     ],
     "prompt_number": 8
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Next we need to determine if a vector of 9 unsigned integers constitutes a permutation.  The `isperm` function could be used to do this but if we are going to do so hundreds of thousands of times we may wish to be more concise.\n",
      "\n",
      "We'll show the function then discuss it."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "function isdigitperm(A::Vector{Uint8})\n",
      "    (length(A) == 9) || return false\n",
      "    used = falses(9)\n",
      "    for a in A\n",
      "        d = a - '0'\n",
      "        (0 < d < 10) && (used[d] $= true) || return false\n",
      "    end\n",
      "    true\n",
      "end\n"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 9,
       "text": [
        "isdigitperm (generic function with 1 method)"
       ]
      }
     ],
     "prompt_number": 9
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "This special-purpose function checks a vector of bytes to determine if its length is exactly 9 and every byte is in the range '1' to '9' and no value in the range '1' to '9' occurs more than once. The expression\n",
      "```jl\n",
      "    used[d] $= true\n",
      "```\n",
      "replaces `used[d]` by the exclusive or of `used[d]` and `true`.  In other words, it negates the logical value and stores the result back into the location at the same time. The first time a digit is flagged as used, the expression returns `true`.  The second time a digit is used it returns `false`."
     ]
    },
    {
     "cell_type": "heading",
     "level": 2,
     "metadata": {},
     "source": [
      "Checking for the first or last 9 digits being pandigital or both"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "function first9pandigital()\n",
      "    st = FibState()\n",
      "    while length(string(increment(st))) < 9 end\n",
      "    while !isdigitperm(string(st).data[1:9])\n",
      "        increment(st)\n",
      "    end\n",
      "    st\n",
      "end"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 10,
       "text": [
        "first9pandigital (generic function with 1 method)"
       ]
      }
     ],
     "prompt_number": 10
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "first9pandigital()"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 11,
       "text": [
        "FibState(2749,[14372689553387917661829645671564334144347634506448917723663290089702222530009397342095721197748390703442578832440606734797476053095767644629443572915711792647722348302386453121454440843797863921561581124399573134833792671117667661197245544556688422949193607193895988306702702760603047336208386100938317422813175407356709232675779685357629997245797294804250463809150187026942349354902182628605422407739419382801150894021953277500195893045355811369520046888338772777218694864406890501694863448727599353830662539700881454734823358742184362414868465995609763288002569665002250249,8882810653744279514485694748125812375732849751297108255084959486990434372916634744577818914260701869600909783888810024985796146896310939747463302125919319171019482090197974901998607036334499473051061534789819562244913549076712416681135135769854879654325478116593469709577420996729583173003248763591736108420837371980297490974395916653387025703790294927230273060942921777620545005278746683898207840517062790672861160964463309578409134888733561142463260314071777151855683804048280701113956693827906336793011366003791501139124180416150996570324585861472852993251848309768327376])"
       ]
      }
     ],
     "prompt_number": 11
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "@time first9pandigital();"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "elapsed time: "
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "0.015653844 seconds (6323525 bytes allocated)\n"
       ]
      }
     ],
     "prompt_number": 11
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Notice that we time the second execution of the function.  The first execution can be much slower than subsequent executions because the function is compiled the first time it is called with an argument signature.  (In the the case of `first9pandigital` there is only one method definition and that is for an empty argument list.)\n",
      "\n",
      "Instead of showing these potentially very large numbers, we create a `show` method for the `FibState` type that prints an abbreviated version."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "import Base.show   # so we can add show methods\n",
      "function show(io::IO, st::FibState)\n",
      "    s = string(st)\n",
      "    println(io, \"Fib[\", st.i,\"] = \",s[1:10],\"...\",s[end-9:end],\n",
      "            \", \", length(s), \" decimal digits\")\n",
      "end\n",
      "show(first9pandigital())"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "Fib[2749] = 1437268955...5002250249, 575 decimal digits\n"
       ]
      }
     ],
     "prompt_number": 12
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "function last9pandigital()\n",
      "    st = FibState()\n",
      "    while length(string(increment(st))) < 9 end\n",
      "    while !isdigitperm(string(st).data[end-8:end])\n",
      "        increment(st)\n",
      "    end\n",
      "    st\n",
      "end\n",
      "show(last9pandigital())"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "Fib[541] = 5162123292...8839725641, 113 decimal digits\n"
       ]
      }
     ],
     "prompt_number": 13
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "@time last9pandigital();"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "elapsed time: 0.001514266 seconds (375743 bytes allocated)\n"
       ]
      }
     ],
     "prompt_number": 13
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Finally, create a function that allows for checking either the first 9 digits or the last 9 digits or both."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "function fibpandigit(first::Bool,last::Bool)\n",
      "    st = FibState(); while length(string(increment(st))) < 9 end\n",
      "    while !((!first || isdigitperm(string(st).data[1:9])) &&\n",
      "            (!last || isdigitperm(string(st).data[end-8:end])))\n",
      "         increment(st)\n",
      "    end\n",
      "    st\n",
      "end\n",
      "show(fibpandigit(true,false))  # should be same as first9pandigital"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "Fib["
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "2749] = 1437268955...5002250249, 575 decimal digits\n"
       ]
      }
     ],
     "prompt_number": 14
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "show(fibpandigit(false,true))"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "Fib[541] = 5162123292...8839725641, 113 decimal digits\n"
       ]
      }
     ],
     "prompt_number": 15
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "@time res = fibpandigit(true,true);"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "elapsed time: "
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "558.664758252 seconds (60210195439 bytes allocated)\n"
       ]
      }
     ],
     "prompt_number": 15
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "show(res)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "Fib[329468] = 2456817391...0352786941, 68855 decimal digits\n"
       ]
      }
     ],
     "prompt_number": 16
    }
   ],
   "metadata": {}
  }
 ]
}