Removing files from data analysis directory

[ou-summer-of-code-2017.git] / 02-lifts / lifts-solution.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Puzzle 2: Lifts\n",
    "\n",
    "## Part 1: using the lifts\n",
    "\n",
    "You've chosen your holiday, now it's time to catch your flight. You arrive at Heathwick airport and have to find the departures floor. However, getting around Terminal $\\pi$ is a real pain. The instructions for how to use the lifts are rather complex.\n",
    "\n",
    "You start in the car park (the basement level, floor 0) and follow this instructions one step at a time. The instructions are each one character:\n",
    "* `^` : go up one floor\n",
    "* `v` : go down one floor\n",
    "* `=` : open the doors, without moving floors.\n",
    "\n",
    "The input contains no other characters.\n",
    "\n",
    "If you follow the instructions and get out at the end, what floor do you end up on?\n",
    "\n",
    "Terminal $\\pi$ is large and there's no limit to the number of floors, both up and down.\n",
    "\n",
    "For instance, the sequence '^=' takes you to floor 1. \n",
    "\n",
    "The sequence `vv^=` takes you down two floors to the sub-sub-basement (floor -2), then up one floor, and you get out in the sub-basement on floor -1.\n",
    "\n",
    "The sequence `^^v=^=` would start on floor 0, go up two floors, then down one. The doors would then open on floor 1, but you'd stay in the lift. You'd then move up to floor 2, the doors open, and you get out on floor 2. \n",
    "\n",
    "The sequence `v^^^^^v=v=` would go down one floor (to floor -1), up five floors (to floor 4), down one floor (to floor 3), open the doors, go down another floor, and you'd finally get out at floor 2.\n",
    "\n",
    "Given the input in [02-lifts.txt](02-lifts.txt), where would you get out?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Worked example of solution: Part 1\n",
    "\n",
    "This is an example of a very common pattern: walking along a list, finding some total or final value. As such, there are a great many ways of doing it.\n",
    "\n",
    "The most obvious way is to have a variable that holds the current floor, and update it with every instruction that's read from the list of instructions. As the current floor is just a number, we can have a simple variable.\n",
    "\n",
    "The list of instructions will be read as a string, and we can iterate through a string easily, so we'll leave the instructions as a string. Happily, each instruction is one character, so no need to count characters and instructions separately.\n",
    "\n",
    "The only complication is that there's no obvious trick for converting the instruction characters. Given that, let's just do a simple `if`-`elisf`-`else` structure (or a `case` statement of your language of choice has it) to convert an instruction into a floor change. \n",
    "\n",
    "(I could also have used a `dict` like \n",
    "\n",
    "```\n",
    "value = {'^': 1, 'v': -1, '=': 0}\n",
    "```\n",
    "\n",
    "and it would behave in the same way.)\n",
    "\n",
    "(Another common solution was to count the number of `^` characters and the number of `v` characters, subtract one from the other, and give the result. That works for part 1 but doesn't work for part 2!)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def value(instr):\n",
    "    if instr == '^':\n",
    "        return 1\n",
    "    elif instr == 'v':\n",
    "        return -1\n",
    "    else:\n",
    "        return 0"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now we can find the floor-change of each instruction, we set the initial floor to 0 and run down the list, updating the current floor at each step."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def final(sequence):\n",
    "    current = 0\n",
    "    for c in sequence:\n",
    "        current += value(c)\n",
    "    return current"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Finally, open the file of instructions and find the final floor."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "209"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "with open('02-lifts.txt') as f:\n",
    "    instructions = f.read()\n",
    "    exit = final(instructions)\n",
    "exit"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "(For my testing purposes, find all the floors visited so I can give sensible hints for wrong answers.)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def running(sequence):\n",
    "    current = 0\n",
    "    floors = []\n",
    "    for i in sequence:\n",
    "        current += value(i)\n",
    "        floors += [current]\n",
    "    return floors"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(10002, 216, -6)"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "with open('02-lifts.txt') as f:\n",
    "    instructions = f.read()\n",
    "    floors = running(instructions)\n",
    "len(floors), max(floors), min(floors)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Smart-alec one line solution"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "209"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sum(value(i) for i in open('02-lifts.txt').read())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Part 2: getting out\n",
    "You can only leave the lift where the doors are open. What is the highest floor you could leave from?\n",
    "\n",
    "For instance, the sequence `^^v=^=` would allow you to exit on floors 1 and 2, so the highest floor you could leave from would be floor 2. \n",
    "\n",
    "The sequence `v^^^^^v=v=` would allow you to exit on floors 3 and 2, so the highest floor you could leave from would be floor 3 (even though the lift reaches floor 4)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Worked example of solution: part 2\n",
    "This is another common pattern: walking down a list, keeping some extreme value (the largest, the smallest, or something like that.)\n",
    "\n",
    "The basic idea is to keep a variable holding the highest exit seen so far, and update it if we see a higher exit. We start with some initial value, such as zero. \n",
    "\n",
    "The `highest_exit` function is very similar to the `final` function, but with the `if` statement in the loop. This just checks if we're at an exit and it's higher than what we've seen so far; if so, it updates the `highest_exit` variable.\n",
    "\n",
    "It was pointed out in the forums that by starting with the `highest_exit` at 0, we're assuming that the highest exit is above ground. That's true in this case, but its a valid concern. In this case, I should set the initial value to be smaller than the smallest valid value we can find, so that the first exit we find is correctly recorded. In this case, the smallest value for the exit is if all the instructions are down, or -1 × (number of instructions)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def highest_exit(sequence):\n",
    "    highest_exit = -1 - len(sequence) # or 0\n",
    "    current = 0\n",
    "    for i in sequence:\n",
    "        if value(i) == 0 and current > highest_exit:\n",
    "            highest_exit = current\n",
    "        else:\n",
    "            current += value(i)\n",
    "    return highest_exit"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "215"
      ]
     },
     "execution_count": 21,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "highest_exit(instructions)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A variation that returns a list of all the exits, so I can generate hints for obvious wrong answers (the last exit, the lowest exit, the first exit, the number of exits)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def exits(sequence):\n",
    "    current = 0\n",
    "    exits = []\n",
    "    for i in sequence:\n",
    "        if value(i) == 0:\n",
    "            exits.append(current)\n",
    "        else:\n",
    "            current += value(i)\n",
    "    return exits"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "215"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "max(exits(instructions))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "-5"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "min(exits(instructions))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "209"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "exits(instructions)[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "-2"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "exits(instructions)[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1259"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "len(exits(instructions))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Counter({-5: 1,\n",
       "         -4: 1,\n",
       "         -2: 2,\n",
       "         1: 1,\n",
       "         3: 1,\n",
       "         6: 1,\n",
       "         11: 1,\n",
       "         12: 1,\n",
       "         18: 1,\n",
       "         19: 2,\n",
       "         20: 3,\n",
       "         21: 3,\n",
       "         22: 4,\n",
       "         23: 4,\n",
       "         24: 6,\n",
       "         25: 4,\n",
       "         26: 4,\n",
       "         27: 6,\n",
       "         28: 4,\n",
       "         29: 4,\n",
       "         30: 2,\n",
       "         31: 1,\n",
       "         32: 7,\n",
       "         33: 3,\n",
       "         34: 5,\n",
       "         35: 2,\n",
       "         36: 2,\n",
       "         37: 2,\n",
       "         38: 3,\n",
       "         39: 5,\n",
       "         40: 9,\n",
       "         41: 4,\n",
       "         42: 7,\n",
       "         43: 11,\n",
       "         44: 15,\n",
       "         45: 19,\n",
       "         46: 22,\n",
       "         47: 12,\n",
       "         48: 23,\n",
       "         49: 24,\n",
       "         50: 27,\n",
       "         51: 25,\n",
       "         52: 27,\n",
       "         53: 25,\n",
       "         54: 16,\n",
       "         55: 21,\n",
       "         56: 21,\n",
       "         57: 15,\n",
       "         58: 13,\n",
       "         59: 18,\n",
       "         60: 19,\n",
       "         61: 13,\n",
       "         62: 21,\n",
       "         63: 15,\n",
       "         64: 19,\n",
       "         65: 18,\n",
       "         66: 17,\n",
       "         67: 17,\n",
       "         68: 8,\n",
       "         69: 8,\n",
       "         70: 12,\n",
       "         71: 6,\n",
       "         72: 5,\n",
       "         73: 3,\n",
       "         74: 6,\n",
       "         75: 5,\n",
       "         76: 3,\n",
       "         77: 2,\n",
       "         78: 1,\n",
       "         79: 4,\n",
       "         80: 2,\n",
       "         81: 1,\n",
       "         83: 1,\n",
       "         84: 4,\n",
       "         87: 3,\n",
       "         88: 4,\n",
       "         89: 2,\n",
       "         90: 2,\n",
       "         91: 3,\n",
       "         92: 1,\n",
       "         93: 5,\n",
       "         94: 2,\n",
       "         95: 6,\n",
       "         96: 5,\n",
       "         97: 11,\n",
       "         98: 10,\n",
       "         99: 15,\n",
       "         100: 10,\n",
       "         101: 17,\n",
       "         102: 15,\n",
       "         103: 6,\n",
       "         104: 9,\n",
       "         105: 6,\n",
       "         106: 8,\n",
       "         107: 13,\n",
       "         108: 12,\n",
       "         109: 9,\n",
       "         110: 10,\n",
       "         111: 7,\n",
       "         112: 4,\n",
       "         113: 8,\n",
       "         114: 13,\n",
       "         115: 6,\n",
       "         116: 6,\n",
       "         117: 6,\n",
       "         118: 6,\n",
       "         119: 7,\n",
       "         120: 4,\n",
       "         121: 3,\n",
       "         122: 5,\n",
       "         123: 8,\n",
       "         124: 6,\n",
       "         125: 7,\n",
       "         126: 6,\n",
       "         127: 4,\n",
       "         128: 3,\n",
       "         129: 5,\n",
       "         130: 6,\n",
       "         131: 6,\n",
       "         132: 8,\n",
       "         133: 5,\n",
       "         134: 13,\n",
       "         135: 13,\n",
       "         136: 14,\n",
       "         137: 9,\n",
       "         138: 16,\n",
       "         139: 12,\n",
       "         140: 12,\n",
       "         141: 11,\n",
       "         142: 15,\n",
       "         143: 16,\n",
       "         144: 3,\n",
       "         145: 5,\n",
       "         146: 10,\n",
       "         147: 3,\n",
       "         148: 3,\n",
       "         149: 2,\n",
       "         150: 3,\n",
       "         151: 6,\n",
       "         152: 7,\n",
       "         153: 5,\n",
       "         154: 7,\n",
       "         155: 5,\n",
       "         156: 5,\n",
       "         157: 1,\n",
       "         158: 5,\n",
       "         159: 5,\n",
       "         160: 6,\n",
       "         161: 2,\n",
       "         162: 2,\n",
       "         164: 7,\n",
       "         165: 2,\n",
       "         166: 2,\n",
       "         167: 3,\n",
       "         168: 1,\n",
       "         169: 4,\n",
       "         170: 3,\n",
       "         171: 1,\n",
       "         173: 1,\n",
       "         178: 1,\n",
       "         179: 1,\n",
       "         181: 1,\n",
       "         185: 1,\n",
       "         187: 1,\n",
       "         188: 1,\n",
       "         189: 1,\n",
       "         192: 2,\n",
       "         193: 1,\n",
       "         194: 3,\n",
       "         195: 1,\n",
       "         196: 2,\n",
       "         199: 1,\n",
       "         200: 2,\n",
       "         201: 1,\n",
       "         204: 1,\n",
       "         205: 1,\n",
       "         207: 2,\n",
       "         208: 3,\n",
       "         209: 11,\n",
       "         210: 2,\n",
       "         211: 1,\n",
       "         212: 1,\n",
       "         213: 2,\n",
       "         215: 2})"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "import collections\n",
    "collections.Counter(exits(instructions))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "-2"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "max(exits(instructions[:20]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(209, 215)"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "import functools\n",
    "ds = {'^': +1, 'v': -1, '=': 0}\n",
    "def s(p, c): return p[0] + ds[c], p[0] if c == '=' and p[0] > p[1] else p[1]\n",
    "functools.reduce(s, open('02-lifts.txt').read().strip(), (0, float('-inf')))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(209, 215)"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "import functools\n",
    "ds = {'^': +1, 'v': -1, '=': 0}\n",
    "functools.reduce(lambda p, c: (p[0] + ds[c], p[0] if c == '=' and p[0] > p[1] else p[1]), open('02-lifts.txt').read().strip(), (0, 0))"
   ]
  },
  {
   "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.5.2+"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}