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

Wesele

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

* guests = [{'name': 'Jan Kowalski', 'rank': 3}, {'name': 'Anna Kot', 'rank':2}]

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()