This notebook is part of programming course prepared by Jerzy Wawro, Galicea
*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ć.
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}]
* guests = [{'name': 'Jan Kowalski', 'rank': 3}, {'name': 'Anna Kot', 'rank':2}]
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.
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}])
Uruchom poniższy program aby przetestować algorytm.
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()
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.
Sortowanie przez wybieranie - do dwóch list.
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)
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()