SEND + MORE = MONEY

Genetic Algorithm.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Send More Money – Genetic Algorithm"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "type Digit = Int\n",
    "type Individual = Vector[Digit]\n",
    "type Population = List[Individual]\n",
    "\n",
    "/** side-effect */\n",
    "val r = util.Random\n",
    "val generationSize = 512\n",
    "val generationRetainment = 32 // top 6%\n",
    "\n",
    "// 16 of the 28 possible mutations\n",
    "val individualProlificness: Int = generationSize / generationRetainment\n",
    "\n",
    "val species = Vector(0, 1, 2, 5, 6, 7, 8, 9) // no (3, 4)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\u001b[36mnumberOfSpecies\u001b[0m: \u001b[32mInt\u001b[0m = \u001b[32m45\u001b[0m"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "val numberOfSpecies: Int =\n",
    "  List(0, 1, 2, 3, 4, 5, 6, 7, 8, 9)\n",
    "    .combinations(2)\n",
    "    .toSet\n",
    "    .size"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def generateIndividual(): Individual = r.shuffle(species)\n",
    "\n",
    "def generatePopulation(n: Int): Population = List.fill(n)(generateIndividual()).sortBy(fitness)\n",
    "\n",
    "def fitness(individual: Individual): Int = {\n",
    "  val cs = \"sendmoremoney\".distinct\n",
    "  val m = cs.zip(individual).toMap\n",
    "  val send = \"send\" map m reduce (_ * 10 + _)\n",
    "  val more = \"more\" map m reduce (_ * 10 + _)\n",
    "  val money = \"money\" map m reduce (_ * 10 + _)\n",
    "  math.abs(send + more - money)\n",
    "}\n",
    "\n",
    "def everyMutation(individual: Individual): Iterator[Individual] = {\n",
    "  val mutationIndices = List(0, 1, 2, 3, 4, 5, 6, 7).combinations(2)\n",
    "  r.shuffle(mutationIndices)\n",
    "    .map { case Seq(i, j) =>\n",
    "      individual\n",
    "        .updated(i, individual(j))\n",
    "        .updated(j, individual(i))\n",
    "    }\n",
    "}\n",
    "\n",
    "// +-+-+-+-+-+-+-+-+\n",
    "// |S|E|N|D|M|O|R|Y|\n",
    "// +-+-+-+-+-+-+-+-+\n",
    "// |0|1|2|3|4|5|6|7|\n",
    "// +-+-+-+-+-+-+-+-+\n",
    "//      ^     ^\n",
    "//      |     |\n",
    "//      +-----+\n",
    "//     [i]   [j]\n",
    "\n",
    "def createNextGeneration(currentGeneration: Population): Population =\n",
    "  if (fitness(currentGeneration.head) == 0) {\n",
    "    currentGeneration.take(1)\n",
    "  } else {\n",
    "    currentGeneration.take(generationRetainment)\n",
    "      .flatMap(everyMutation(_).take(individualProlificness))\n",
    "      .sortBy(fitness)\n",
    "  }"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      ".\n",
      ".\n",
      ".\n",
      ".\n",
      "solution=Vector(9, 5, 6, 7, 1, 0, 8, 2) - fitness(solution)=0\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "\u001b[36msolution\u001b[0m: \u001b[32mIndividual\u001b[0m = \u001b[33mVector\u001b[0m(\u001b[32m9\u001b[0m, \u001b[32m5\u001b[0m, \u001b[32m6\u001b[0m, \u001b[32m7\u001b[0m, \u001b[32m1\u001b[0m, \u001b[32m0\u001b[0m, \u001b[32m8\u001b[0m, \u001b[32m2\u001b[0m)"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "val solution = Iterator\n",
    "  .iterate(generatePopulation(generationSize))(createNextGeneration)\n",
    "  .map { p => println(\".\"); p }\n",
    "  .dropWhile(_.size > 1)\n",
    "  .map(_.head).next()\n",
    "\n",
    "println(s\"solution=$solution - fitness(solution)=${fitness(solution)}\")"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Scala 2.11",
   "language": "scala211",
   "name": "scala211"
  },
  "language_info": {
   "codemirror_mode": "text/x-scala",
   "file_extension": ".scala",
   "mimetype": "text/x-scala",
   "name": "scala211",
   "pygments_lexer": "scala",
   "version": "2.11.8"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}

Nested for.ipynb

Scala API.ipynb

StateT List.ipynb