{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This notebook is part of programming course prepared by Jerzy Wawro, Galicea"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Wesele"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Problem: Jak rozmieścić gości przy stole.\n",
    "\n",
    "* [Algorytmizacja zadania](#Algorytmizacja-zadania)\n",
    "* [Szczegóły](#Szczegóły)\n",
    "* [Ograniczenia](#Ograniczenia)\n",
    "* [Kod - uproszczony](#Kod)\n",
    "* [Test - uproszczony](#Testowanie)\n",
    "* [Algorytm](#Algorytm)\n",
    "* [Test](#Test)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Algorytmizacja zadania\n",
    "\n",
    "***Zadanie***: zaplanować rozmieszczenie gości weselnych przy stole.\n",
    "Czy jest to zadanie algorytmiczne? Przy takim sformułowaniu oczywiście nie. Musimy dodać jakieś reguły rozmieszczania. Na przykład takie:\n",
    "Im bliżej młodych (jeden z końców stołu), tym miejsce bardziej honorowe. Wszyscy goście mają przypisane rangi (wagi), które pozwalają ich uporządkować. \n",
    "\n",
    "## Szczegóły\n",
    "\n",
    "Chcemy aby komputer pomógł nam w planowaniu. Musimy więc zadanie opisać na odpowiednim dla programowania poziomie szczegółowości (operując strukturami danych dostępnymi w językach programowania). Dla uproszczenia ponumerujmy gości.\n",
    "Mamy zatem listę gości (guests) o następującej strukturze:\n",
    "{'name': nazwisko, 'rank': ranga}\n",
    "\n",
    "**Przykład**:\n",
    "guests = [{'name': 'Jan Kowalski', 'rank': 3}, {'name': 'Anna Kot', 'rank':2}]\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Ograniczenia\n",
    "\n",
    "* Czy można założyć, że lista jest niepusta?\n",
    "    * Tak\n",
    "* Czy można założyć, że dane są poprawne (lista elementów z wypełnionymi polami name i rank)?\n",
    "    * Tak"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Dane testowe\n",
    "\n",
    "<pre>\n",
    "* guests = [{'name': 'Jan Kowalski', 'rank': 3}, {'name': 'Anna Kot', 'rank':2}]\n",
    "</pre>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Algorytm zerowy\n",
    "\n",
    "Możemy posortować listę gości według ich rangi. Po przeszukaniu internetu znajdujemy odpowiedni przykład sortowania, który adoptujemy dla naszych celów."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Kod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Solution0(object):\n",
    "    \n",
    "  def sort_key(self, guest): \n",
    "    return guest['rank']\n",
    "\n",
    "  def location(self,guests):\n",
    "    return sorted(guests, key=self.sort_key)\n",
    "\n",
    "# debug:\n",
    "#s=Solution0()\n",
    "#print s.location([{'name': 'Jan Kowalski', 'rank': 3}, {'name': 'Anna Kot', 'rank':2}])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Testowanie"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Uruchom poniższy program aby przetestować algorytm.**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "from nose.tools import assert_equal, assert_raises\n",
    "\n",
    "\n",
    "class TestWedding0(object):\n",
    "\n",
    "    def test_location(self, func):\n",
    "        print('Testuję...')\n",
    "        self.test0list=[{'name': 'Jan Kowalski', 'rank': 3}, {'name': 'Anna Kot', 'rank':2}]\n",
    "        self.test0expected = [{'name': 'Anna Kot', 'rank': 2}, {'name': 'Jan Kowalski', 'rank': 3}]\n",
    "        self.test1list=[\n",
    "            {\"name\": 'Jan Kowalski', \"rank\": 4}, \n",
    "            {\"name\": 'Anna Dobrowolska', \"rank\": 6},\n",
    "            {\"name\": 'Jan Nowak', \"rank\": 1},\n",
    "            {\"name\": 'Anna Kowalska', \"rank\":3},\n",
    "            {\"name\": 'Anna Tkacz', \"rank\": 2},\n",
    "            {\"name\": 'Jan Szostek', \"rank\": 5},\n",
    "            {\"name\": 'Maria Nowak', \"rank\": 0},\n",
    "            {\"name\": 'Jan Romanow', \"rank\": 3}]\n",
    "        self.test1expected = [{'name': 'Maria Nowak', 'rank': 0}, \n",
    "                              {'name': 'Jan Nowak', 'rank': 1}, \n",
    "                              {'name': 'Anna Tkacz', 'rank': 2}, \n",
    "                              {'name': 'Anna Kowalska', 'rank': 3}, \n",
    "                              {'name': 'Jan Romanow', 'rank': 3},\n",
    "                              {'name': 'Jan Kowalski', 'rank': 4}, \n",
    "                              {'name': 'Jan Szostek', 'rank': 5},\n",
    "                              {'name': 'Anna Dobrowolska', 'rank': 6}]\n",
    "        assert_raises(TypeError, func, None)\n",
    "        self.result=func(self.test0list)\n",
    "        assert_equal(self.result, self.test0expected)\n",
    "        self.result=func(self.test1list)\n",
    "        assert_equal(self.result, self.test1expected)\n",
    "        print('Sukces: poprawnie posortowane')\n",
    "\n",
    "\n",
    "def main():\n",
    "    test = TestWedding0()\n",
    "    solution = Solution0()\n",
    "    \n",
    "    try:\n",
    "        test.test_location(solution.location)\n",
    "    except AttributeError as e:\n",
    "        print e\n",
    "        pass\n",
    "\n",
    "\n",
    "if __name__ == '__main__':\n",
    "    main()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Dodatkowe warunki\n",
    "\n",
    "Goście siedzą po dwóch stronach stołu. Dodatkowo małżeństwa (pary) powinny siedzieć obok siebie, a kobiety z mężczyznami na przemian."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Algorytm\n",
    "\n",
    "Sortowanie przez wybieranie - do dwóch list."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Solution1(object):\n",
    "\n",
    "  def location(self,guests):\n",
    "    r_list=[]\n",
    "    l_list=[]\n",
    "    r_rank=0\n",
    "    l_rank=0\n",
    "    r_ids=[]\n",
    "    l_ids=[]\n",
    "    \n",
    "    for guest in guests:\n",
    "      if guest['partner'] in r_ids: # wstaw po prawej\n",
    "         i=0\n",
    "         while (i<len(r_ids)) and (r_ids[i] != guest['partner']):\n",
    "           i=i+1\n",
    "         if guest['sex']=='K':\n",
    "           r_list.insert(i,guest)\n",
    "           r_ids.insert(i,guest['id'])\n",
    "         else:\n",
    "           r_list.insert(i+1,guest)\n",
    "           r_ids.insert(i+1,guest['id'])\n",
    "      elif guest['partner'] in l_ids: # wstaw po lewej\n",
    "         i=0\n",
    "         while (i<len(l_ids)) and (l_ids[i] != guest['partner']):\n",
    "           i=i+1\n",
    "         if guest['sex']=='K':\n",
    "           l_list.insert(i+1,guest)\n",
    "           l_ids.insert(i+1,guest['id'])\n",
    "         else:\n",
    "           l_list.insert(i,guest)\n",
    "           l_ids.insert(i,guest['id'])\n",
    "      elif (len(r_ids)<=len(l_ids)):\n",
    "         i=0\n",
    "         while (i<len(r_list)) and (r_list[i]['rank'] < guest['rank']):\n",
    "           i=i+1\n",
    "         r_list.insert(i,guest)\n",
    "         r_ids.insert(i,guest['id'])\n",
    "      else:\n",
    "         i=0\n",
    "         while (i<len(l_list)) and (l_list[i]['rank'] < guest['rank']):\n",
    "           i=i+1\n",
    "         l_list.insert(i,guest)\n",
    "         l_ids.insert(i,guest['id'])\n",
    "    return (l_list, r_list)\n",
    "\n",
    "\n",
    "#algorythm = Solution1()\n",
    "#(l_list,r_list) =algorythm.location(guests)\n",
    "#print('lewa:')\n",
    "#for guest in l_list:\n",
    "#  print(guest)\n",
    "#print('prawa:')\n",
    "#for guest in r_list:\n",
    "#  print(guest)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Test"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "from nose.tools import assert_equal, assert_raises\n",
    "\n",
    "\n",
    "class TestWedding1(object):\n",
    "\n",
    "    def test_location(self, func):\n",
    "        print('Testuję...')\n",
    "        guests = [\n",
    "            {\"id\":1, \"name\": 'Jan Kowalski', \"sex\": 'M', \"rank\": 4, \"partner\":4 }, \n",
    "            {\"id\":2, \"name\": 'Anna Dobrowolska', \"sex\": 'K', \"rank\": 3, \"partner\":0},\n",
    "            {\"id\":3, \"name\": 'Jan Nowak', \"sex\": 'M', \"rank\": 1, \"partner\":7},\n",
    "            {\"id\":4, \"name\": 'Anna Kowalska', \"sex\": 'K', \"rank\": 3, \"partner\":1},\n",
    "            {\"id\":5, \"name\": 'Anna Tkacz', \"sex\": 'K', \"rank\": 2, \"partner\":0},\n",
    "            {\"id\":6, \"name\": 'Jan Szostek', \"sex\": 'M', \"rank\": 3, \"partner\":0},\n",
    "            {\"id\":7, \"name\": 'Maria Nowak', \"sex\": 'K', \"rank\": 0, \"partner\":3},\n",
    "            {\"id\":8, \"name\": 'Jan Romanow', \"sex\": 'M', \"rank\": 3, \"partner\":0}]\n",
    "        l_expected = [{'partner': 0, 'sex': 'K', 'id': 5, 'rank': 2, 'name': 'Anna Tkacz'},\n",
    "                      {'partner': 0, 'sex': 'M', 'id': 8, 'rank': 3, 'name': 'Jan Romanow'},\n",
    "                      {'partner': 0, 'sex': 'M', 'id': 6, 'rank': 3, 'name': 'Jan Szostek'},\n",
    "                      {'partner': 0, 'sex': 'K', 'id': 2, 'rank': 3, 'name': 'Anna Dobrowolska'} ]\n",
    "        r_expected = [{'partner': 3, 'sex': 'K', 'id': 7, 'rank': 0, 'name': 'Maria Nowak'},\n",
    "                      {'partner': 7, 'sex': 'M', 'id': 3, 'rank': 1, 'name': 'Jan Nowak'},\n",
    "                      {'partner': 1, 'sex': 'K', 'id': 4, 'rank': 3, 'name': 'Anna Kowalska'},\n",
    "                      {'partner': 4, 'sex': 'M', 'id': 1, 'rank': 4, 'name': 'Jan Kowalski'} ]\n",
    "        assert_raises(TypeError, func, None)\n",
    "        (l_result,r_result) = func(guests)\n",
    "        assert_equal(l_result, l_expected)\n",
    "        assert_equal(r_result, r_expected)\n",
    "        print('Sukces')\n",
    "\n",
    "\n",
    "def main():\n",
    "    test = TestWedding1()\n",
    "    solution = Solution1()\n",
    "    \n",
    "    try:\n",
    "        test.test_location(solution.location)\n",
    "    except AttributeError as e:\n",
    "        print e\n",
    "        pass\n",
    "\n",
    "\n",
    "if __name__ == '__main__':\n",
    "    main()"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 2",
   "language": "python",
   "name": "python2"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.13"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}