#!/usr/bin/env python
# coding: utf-8

# This notebook is part of programming course prepared by Jerzy Wawro, Galicea

# # Wesele

# ## Problem: Jak rozmieścić gości przy stole.
# 
# * [Algorytmizacja zadania](#Algorytmizacja-zadania)
# * [Szczegóły](#Szczegóły)
# * [Ograniczenia](#Ograniczenia)
# * [Kod - uproszczony](#Kod)
# * [Test - uproszczony](#Testowanie)
# * [Algorytm](#Algorytm)
# * [Test](#Test)

# ## Algorytmizacja zadania
# 
# ***Zadanie***: zaplanować rozmieszczenie gości weselnych przy stole.
# Czy jest to zadanie algorytmiczne? Przy takim sformułowaniu oczywiście nie. Musimy dodać jakieś reguły rozmieszczania. Na przykład takie:
# 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ć. 
# 
# ## Szczegóły
# 
# 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.
# Mamy zatem listę gości (guests) o następującej strukturze:
# {'name': nazwisko, 'rank': ranga}
# 
# **Przykład**:
# guests = [{'name': 'Jan Kowalski', 'rank': 3}, {'name': 'Anna Kot', 'rank':2}]
# 
# 

# ## Ograniczenia
# 
# * Czy można założyć, że lista jest niepusta?
#     * Tak
# * Czy można założyć, że dane są poprawne (lista elementów z wypełnionymi polami name i rank)?
#     * Tak

# ## Dane testowe
# 
# <pre>
# * guests = [{'name': 'Jan Kowalski', 'rank': 3}, {'name': 'Anna Kot', 'rank':2}]
# </pre>

# ## Algorytm zerowy
# 
# 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.

# ## Kod

# In[ ]:


class Solution0(object):
    
  def sort_key(self, guest): 
    return guest['rank']

  def location(self,guests):
    return sorted(guests, key=self.sort_key)

# debug:
#s=Solution0()
#print s.location([{'name': 'Jan Kowalski', 'rank': 3}, {'name': 'Anna Kot', 'rank':2}])


# ## Testowanie

# **Uruchom poniższy program aby przetestować algorytm.**

# In[ ]:


from nose.tools import assert_equal, assert_raises


class TestWedding0(object):

    def test_location(self, func):
        print('Testuję...')
        self.test0list=[{'name': 'Jan Kowalski', 'rank': 3}, {'name': 'Anna Kot', 'rank':2}]
        self.test0expected = [{'name': 'Anna Kot', 'rank': 2}, {'name': 'Jan Kowalski', 'rank': 3}]
        self.test1list=[
            {"name": 'Jan Kowalski', "rank": 4}, 
            {"name": 'Anna Dobrowolska', "rank": 6},
            {"name": 'Jan Nowak', "rank": 1},
            {"name": 'Anna Kowalska', "rank":3},
            {"name": 'Anna Tkacz', "rank": 2},
            {"name": 'Jan Szostek', "rank": 5},
            {"name": 'Maria Nowak', "rank": 0},
            {"name": 'Jan Romanow', "rank": 3}]
        self.test1expected = [{'name': 'Maria Nowak', 'rank': 0}, 
                              {'name': 'Jan Nowak', 'rank': 1}, 
                              {'name': 'Anna Tkacz', 'rank': 2}, 
                              {'name': 'Anna Kowalska', 'rank': 3}, 
                              {'name': 'Jan Romanow', 'rank': 3},
                              {'name': 'Jan Kowalski', 'rank': 4}, 
                              {'name': 'Jan Szostek', 'rank': 5},
                              {'name': 'Anna Dobrowolska', 'rank': 6}]
        assert_raises(TypeError, func, None)
        self.result=func(self.test0list)
        assert_equal(self.result, self.test0expected)
        self.result=func(self.test1list)
        assert_equal(self.result, self.test1expected)
        print('Sukces: poprawnie posortowane')


def main():
    test = TestWedding0()
    solution = Solution0()
    
    try:
        test.test_location(solution.location)
    except AttributeError as e:
        print e
        pass


if __name__ == '__main__':
    main()


# ### Dodatkowe warunki
# 
# 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.

# ## Algorytm
# 
# Sortowanie przez wybieranie - do dwóch list.

# In[ ]:


class Solution1(object):

  def location(self,guests):
    r_list=[]
    l_list=[]
    r_rank=0
    l_rank=0
    r_ids=[]
    l_ids=[]
    
    for guest in guests:
      if guest['partner'] in r_ids: # wstaw po prawej
         i=0
         while (i<len(r_ids)) and (r_ids[i] != guest['partner']):
           i=i+1
         if guest['sex']=='K':
           r_list.insert(i,guest)
           r_ids.insert(i,guest['id'])
         else:
           r_list.insert(i+1,guest)
           r_ids.insert(i+1,guest['id'])
      elif guest['partner'] in l_ids: # wstaw po lewej
         i=0
         while (i<len(l_ids)) and (l_ids[i] != guest['partner']):
           i=i+1
         if guest['sex']=='K':
           l_list.insert(i+1,guest)
           l_ids.insert(i+1,guest['id'])
         else:
           l_list.insert(i,guest)
           l_ids.insert(i,guest['id'])
      elif (len(r_ids)<=len(l_ids)):
         i=0
         while (i<len(r_list)) and (r_list[i]['rank'] < guest['rank']):
           i=i+1
         r_list.insert(i,guest)
         r_ids.insert(i,guest['id'])
      else:
         i=0
         while (i<len(l_list)) and (l_list[i]['rank'] < guest['rank']):
           i=i+1
         l_list.insert(i,guest)
         l_ids.insert(i,guest['id'])
    return (l_list, r_list)


#algorythm = Solution1()
#(l_list,r_list) =algorythm.location(guests)
#print('lewa:')
#for guest in l_list:
#  print(guest)
#print('prawa:')
#for guest in r_list:
#  print(guest)


# ## Test

# In[ ]:


from nose.tools import assert_equal, assert_raises


class TestWedding1(object):

    def test_location(self, func):
        print('Testuję...')
        guests = [
            {"id":1, "name": 'Jan Kowalski', "sex": 'M', "rank": 4, "partner":4 }, 
            {"id":2, "name": 'Anna Dobrowolska', "sex": 'K', "rank": 3, "partner":0},
            {"id":3, "name": 'Jan Nowak', "sex": 'M', "rank": 1, "partner":7},
            {"id":4, "name": 'Anna Kowalska', "sex": 'K', "rank": 3, "partner":1},
            {"id":5, "name": 'Anna Tkacz', "sex": 'K', "rank": 2, "partner":0},
            {"id":6, "name": 'Jan Szostek', "sex": 'M', "rank": 3, "partner":0},
            {"id":7, "name": 'Maria Nowak', "sex": 'K', "rank": 0, "partner":3},
            {"id":8, "name": 'Jan Romanow', "sex": 'M', "rank": 3, "partner":0}]
        l_expected = [{'partner': 0, 'sex': 'K', 'id': 5, 'rank': 2, 'name': 'Anna Tkacz'},
                      {'partner': 0, 'sex': 'M', 'id': 8, 'rank': 3, 'name': 'Jan Romanow'},
                      {'partner': 0, 'sex': 'M', 'id': 6, 'rank': 3, 'name': 'Jan Szostek'},
                      {'partner': 0, 'sex': 'K', 'id': 2, 'rank': 3, 'name': 'Anna Dobrowolska'} ]
        r_expected = [{'partner': 3, 'sex': 'K', 'id': 7, 'rank': 0, 'name': 'Maria Nowak'},
                      {'partner': 7, 'sex': 'M', 'id': 3, 'rank': 1, 'name': 'Jan Nowak'},
                      {'partner': 1, 'sex': 'K', 'id': 4, 'rank': 3, 'name': 'Anna Kowalska'},
                      {'partner': 4, 'sex': 'M', 'id': 1, 'rank': 4, 'name': 'Jan Kowalski'} ]
        assert_raises(TypeError, func, None)
        (l_result,r_result) = func(guests)
        assert_equal(l_result, l_expected)
        assert_equal(r_result, r_expected)
        print('Sukces')


def main():
    test = TestWedding1()
    solution = Solution1()
    
    try:
        test.test_location(solution.location)
    except AttributeError as e:
        print e
        pass


if __name__ == '__main__':
    main()