DS_Exercise_Day1.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# DS-Exercise Day1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "- 早上請大家 fork 的方式，請先拋在腦後，忘記他。\n",
    "- 交作業方式改為:\n",
    "- 於 GitHub 中，新增一個 Repo，命名為: X-Village-DS-Exercise\n",
    "- 並依照範例檔命名及完成作業，在上傳至 GitHub。\n",
    "\n",
    "\n",
    "- 用 [slido](https://app2.sli.do/event/bgcdkics/questions) 可以匿名問問題喔！"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Stack"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "### Quickstart"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "from lib.stack import Stack\n",
    "\n",
    "s = Stack()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "scrolled": false,
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Is empyty? True\n",
      "Stack size: 0\n",
      "Is empyty? False\n",
      "Stack size: 2\n"
     ]
    }
   ],
   "source": [
    "print('Is empyty?', s.isEmpty())\n",
    "print('Stack size:', s.size())\n",
    "\n",
    "s.push(4)\n",
    "s.push('dog')\n",
    "\n",
    "print('Is empyty?', s.isEmpty())\n",
    "print('Stack size:', s.size())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Pop an item: 8.4\n",
      "Pop an item: dog\n",
      "Stack size: 1\n"
     ]
    }
   ],
   "source": [
    "s.push(8.4)\n",
    "print('Pop an item:', s.pop())\n",
    "print('Pop an item:', s.pop())\n",
    "print('Stack size:', s.size())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "| Lines | Queue Operation | Queue Contents     | Return Value |\n",
    "|-------|-----------------|--------------------|--------------|\n",
    "| 1     | s.isEmpty()     | []                 | True         |\n",
    "| 2     | s.push(4)       | [4]                |              |\n",
    "| 3     | s.push('dog')   | [4,'dog']          |              |\n",
    "| 4     | s.push(True)    | [4,'dog',True]     |              |\n",
    "| 5     | s.size()        | [4,'dog',True]     | 3            |\n",
    "| 6     | s.isEmpty()     | [4,'dog',True]     | False        |\n",
    "| 7     | s.push(8.4)     | [4,'dog',True,8.4] |              |\n",
    "| 8     | s.pop()         | [4,'dog',True]     | 8.4          |\n",
    "| 9     | s.pop()         | [4,'dog']          | True         |\n",
    "| 10    | s.size()        | [4,'dog']          | 2            |"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "### The stack operations\n",
    "- `Stack()` creates a new stack that is empty. It needs no parameters and returns an empty stack.\n",
    "- `push(item)` adds a new item to the top of the stack. It needs the item and returns nothing.\n",
    "- `pop()` removes the top item from the stack. It needs no parameters and returns the item. The stack is modified."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "- `peek()` returns the top item from the stack but does not remove it. It needs no parameters. The stack is not modified.\n",
    "- `isEmpty()` tests to see whether the stack is empty. It needs no parameters and returns a boolean value.\n",
    "- `size()` returns the number of items on the stack. It needs no parameters and returns an integer."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "And then, Let's trace source code!"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "### Exercise1 十進位轉二進位 (ex1.py)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "![binary](https://upload.wikimedia.org/wikipedia/commons/a/a7/Binary_Back.jpg)\n",
    "(From Wikimedia Commons, the free media repository)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "34567<sub>(10)</sub> = 3\\*10000 + 4\\*1000 + 5\\*100 + 6\\*10 + 7\\*1\n",
    "\n",
    "34567<sub>(10)</sub> = 3\\*(10^4) + 4\\*(10^3) + 5\\*(10^2) + 6\\*(10^1) + 7\\*(10^0)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "101001<sub>(2)</sub> = 1\\*(2^5) + 0\\*(2^4) + 1\\*(2^3) + 0\\*(2^2) + 0\\*(2^1) + 1\\*(2^0)\n",
    "\n",
    "101001<sub>(2)</sub> = 1\\*32 + 0\\*16 + 1\\*8 + 0\\*4 + 0\\*2 + 1\\*1\n",
    "\n",
    "101001<sub>(2)</sub> = 41<sub>(10)</sub>\n",
    "\n",
    "101111 = 41 + 2 + 4"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "![base_convert](http://interactivepython.org/runestone/static/pythonds/_images/dectobin.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "- 利用 Stack，定義一個 function，傳入十進位數字，回傳二進位數字\n",
    "(hint: 11/2 = 5.5, 11//2 = 5, 11%2 = 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "def dec_to_bin(dec):\n",
    "    ...\n",
    "    ...\n",
    "    return binary\n",
    "\n",
    "dec_to_bin(42)   # 回傳 101010\n",
    "dec_to_bin(100)  # 回傳 1100100"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Queue"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "### Quickstart"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "from lib.queue import Queue\n",
    "\n",
    "q = Queue()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Is empyty? True\n",
      "Queue size: 0\n",
      "Is empyty? False\n",
      "Queue size: 2\n"
     ]
    }
   ],
   "source": [
    "print('Is empyty?', q.isEmpty())\n",
    "print('Queue size:', q.size())\n",
    "\n",
    "q.enqueue(4)\n",
    "q.enqueue('dog')\n",
    "\n",
    "print('Is empyty?', q.isEmpty())\n",
    "print('Queue size:', q.size())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Removes the front item: 4\n",
      "Queue size: 1\n",
      "Removes the front item: dog\n",
      "Queue size: 0\n"
     ]
    }
   ],
   "source": [
    "print('Removes the front item:', q.dequeue())\n",
    "print('Queue size:', q.size())\n",
    "print('Removes the front item:', q.dequeue())\n",
    "print('Queue size:', q.size())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "| Lines | Queue Operation  | Queue Contents     | Return Value |\n",
    "|-------|------------------|--------------------|--------------|\n",
    "| 1     | q.isEmpty()      | []                 | True         |\n",
    "| 2     | q.enqueue(4)     | [4]                |              |\n",
    "| 3     | q.enqueue('dog') | ['dog',4]          |              |\n",
    "| 4     | q.enqueue(True)  | [True,'dog',4]     |              |\n",
    "| 5     | q.size()         | [True,'dog',4]     | 3            |\n",
    "| 6     | q.isEmpty()      | [True,'dog',4]     | False        |\n",
    "| 7     | q.enqueue(8.4)   | [8.4,True,'dog',4] |              |\n",
    "| 8     | q.dequeue()      | [8.4,True,'dog']   | 4            |\n",
    "| 9     | q.dequeue()      | [8.4,True]         | 'dog'        |\n",
    "| 10    | q.size()         | [8.4,True]         | 2            |"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "### The queue operations\n",
    "- `Queue()` creates a new queue that is empty. It needs no parameters and returns an empty queue.\n",
    "- `enqueue(item)` adds a new item to the rear of the queue. It needs the item and returns nothing.\n",
    "- `dequeue()` removes the front item from the queue. It needs no parameters and returns the item. The queue is modified.\n",
    "- `isEmpty()` tests to see whether the queue is empty. It needs no parameters and returns a boolean value.\n",
    "- `size()` returns the number of items in the queue. It needs no parameters and returns an integer.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Exercise2 傳燙馬鈴薯 (ex2.py)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "1. 拿著馬鈴薯的人，會在 front\n",
    "2. 傳遞馬鈴薯的過程，就是先 `dequeue` 後在 `enqueue`，將本來在 front 的人放到尾端\n",
    "3. 傳遞 `num` 次後，拿著馬鈴薯的人（位置在 front）會被淘汰\n",
    "4. 回到第一步，下一回合開始，直到剩最後一個人，為贏家"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "![potato](https://imgur.com/SkLz6mo.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "- 利用 Queue, 定義一個function, 傳入名字列表和次數，回傳最後一人的名字"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "def hot_potato(name_list, num):\n",
    "    ...\n",
    "    ...\n",
    "    return remaining_person\n",
    "\n",
    "hot_potato([\"Susan\",\"Brad\",\"Kent\",\"David\"], 6)               # 回傳 \"Brad\"\n",
    "hot_potato([\"Bill\",\"David\",\"Susan\",\"Jane\",\"Kent\",\"Brad\"], 7) # 回傳 \"Susan\""
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Bonus1 十進位轉任何進位 (bonus1.py)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "- 定義一個 function，傳入十進位數字和 `base`，回傳 `base`進位數字 (2 <= base <= 16)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "def base_converter(dec_number, base):\n",
    "    digits = \"0123456789ABCDEF\"\n",
    "    ...\n",
    "    ...\n",
    "    return string\n",
    "\n",
    "base_converter(1000, 16)  # 回傳 3E8\n",
    "base_converter(700, 12)   # 回傳 4A4"
   ]
  }
 ],
 "metadata": {
  "celltoolbar": "Slideshow",
  "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.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}