wizard-switches.ipynb

{
 "metadata": {
  "name": "Wizard switch problem"
 },
 "nbformat": 3,
 "nbformat_minor": 0,
 "worksheets": [
  {
   "cells": [
    {
     "cell_type": "heading",
     "level": 1,
     "source": [
      "Wizard switch problem"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "class Wizard:\n",
      "    def __init__(self):\n",
      "        self.health = 49 # wizardly health, with potions\n",
      "        self.attack = 25 # angry bearded stare\n",
      "        self.magic = 90  # powerful staff of the elders\n",
      "        self.dance = 12  # the robe interferes with disco moves\n",
      "        # Our state:\n",
      "        self.state = [True, True]\n",
      "\n",
      "    def visit_room(self, switches):\n",
      "        # The first switch decides between our state variables. The\n",
      "        # second switch is the state of *that specific* semaphore / mutex.\n",
      "        [mux, ready] = switches\n",
      "        if ready and self.state[mux]:\n",
      "            # We haven't used this semaphore before and it's unlocked,\n",
      "            # so lock it\n",
      "            switches[1] = False\n",
      "            # But remember it, so we never lock it again.\n",
      "            self.state[mux] = False\n",
      "\n",
      "class LeadWizard:\n",
      "    def __init__(self, num_wizards):\n",
      "        # The lead wizard behaves differently the first time he enters the room\n",
      "        self.first_time = True\n",
      "        self.n_wizards_left = num_wizards\n",
      "    def visit_room(self, switches):\n",
      "        if self.first_time:\n",
      "            self.first_time = False\n",
      "            # Toggle the mux, so everyone now considers their other\n",
      "            # state variable. This gets everyone on a clean state\n",
      "            # because I'm the only wizard that toggles the mux.\n",
      "            switches[0] = not switches[0]\n",
      "            # Unlock this lock\n",
      "            switches[1] = True\n",
      "            # I entered the room\n",
      "            self.n_wizards_left -= 1\n",
      "        else:\n",
      "            # If the lock is locked, someone else was here, so I will\n",
      "            # unlock it.\n",
      "            if switches[1] == False:\n",
      "                self.n_wizards_left -= 1\n",
      "                switches[1] = True\n",
      "        # All done? Time to tempt fate\n",
      "        if self.n_wizards_left == 0:\n",
      "            return \"All wizards have entered the room\""
     ],
     "language": "python",
     "outputs": [],
     "prompt_number": 44
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "# The prison warden leaves everything to chance\n",
      "import random\n",
      "\n",
      "def imprison_several_wizards(num_wizards):\n",
      "    wizards = [ Wizard() for n in xrange(num_wizards) ]\n",
      "    # Elect a leader\n",
      "    wizards[0] = LeadWizard(num_wizards)\n",
      "    finished_wizards = set()\n",
      "    # Prison warden sets switches to a random state\n",
      "    switches = [ random.choice([True,False]), random.choice([True, False]) ]\n",
      "\n",
      "    while True:\n",
      "        print switches,\"  Lead wiz thinks there are\",wizards[0].n_wizards_left,\" left\"\n",
      "        which_wizard = random.choice(wizards)\n",
      "        finished_wizards.add(which_wizard)\n",
      "        if which_wizard.visit_room(switches):\n",
      "            break\n",
      "\n",
      "    if len(finished_wizards) == num_wizards:\n",
      "        print \"Wizards win\"\n",
      "    else:\n",
      "        raise ValueError(\"All wizards die\")\n",
      "\n",
      "imprison_several_wizards(5)\n"
     ],
     "language": "python",
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "[True, True]   Lead wiz thinks there are 5  left\n",
        "[True, False]   Lead wiz thinks there are 5  left\n",
        "[True, False]   Lead wiz thinks there are 5  left\n",
        "[False, True]   Lead wiz thinks there are 4  left\n",
        "[False, False]   Lead wiz thinks there are 4  left\n",
        "[False, False]   Lead wiz thinks there are 4  left\n",
        "[False, False]   Lead wiz thinks there are 4  left\n",
        "[False, False]   Lead wiz thinks there are 4  left\n",
        "[False, False]   Lead wiz thinks there are 4  left\n",
        "[False, False]   Lead wiz thinks there are 4  left\n",
        "[False, False]   Lead wiz thinks there are 4  left\n",
        "[False, True]   Lead wiz thinks there are 3  left\n",
        "[False, False]   Lead wiz thinks there are 3  left\n",
        "[False, False]   Lead wiz thinks there are 3  left\n",
        "[False, True]   Lead wiz thinks there are 2  left\n",
        "[False, True]   Lead wiz thinks there are 2  left\n",
        "[False, True]   Lead wiz thinks there are 2  left\n",
        "[False, True]   Lead wiz thinks there are 2  left\n",
        "[False, False]   Lead wiz thinks there are 2  left\n",
        "[False, False]   Lead wiz thinks there are 2  left\n",
        "[False, False]   Lead wiz thinks there are 2  left\n",
        "[False, False]   Lead wiz thinks there are 2  left\n",
        "[False, False]   Lead wiz thinks there are 2  left\n",
        "[False, False]   Lead wiz thinks there are 2  left\n",
        "[False, False]   Lead wiz thinks there are 2  left\n",
        "[False, True]   Lead wiz thinks there are 1  left\n",
        "[False, True]   Lead wiz thinks there are 1  left\n",
        "[False, True]   Lead wiz thinks there are 1  left\n",
        "[False, True]   Lead wiz thinks there are 1  left\n",
        "[False, True]   Lead wiz thinks there are 1  left\n",
        "[False, True]   Lead wiz thinks there are 1  left\n",
        "[False, True]   Lead wiz thinks there are 1  left\n",
        "[False, False]   Lead wiz thinks there are 1  left\n",
        "Wizards win\n"
       ]
      }
     ],
     "prompt_number": 70
    }
   ]
  }
 ]
}