From 969812724912512740dbf037940a9e6770df19ed Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Martin=20Mo=C5=BEina?= Date: Thu, 6 Oct 2016 12:55:26 +0200 Subject: Added recursion exercises. --- python/problems/recursion/common.py | 2 + python/problems/recursion/depth_to/common.py | 107 ++++++++++++++++++++ python/problems/recursion/depth_to/en.py | 13 +++ python/problems/recursion/depth_to/sl.py | 31 ++++++ python/problems/recursion/en.py | 3 + .../problems/recursion/family_tree_name/common.py | 103 ++++++++++++++++++++ python/problems/recursion/family_tree_name/en.py | 13 +++ python/problems/recursion/family_tree_name/sl.py | 42 ++++++++ .../recursion/family_tree_name_list/common.py | 104 ++++++++++++++++++++ .../problems/recursion/family_tree_name_list/en.py | 13 +++ .../problems/recursion/family_tree_name_list/sl.py | 28 ++++++ .../recursion/family_tree_youngest/common.py | 104 ++++++++++++++++++++ .../problems/recursion/family_tree_youngest/en.py | 13 +++ .../problems/recursion/family_tree_youngest/sl.py | 29 ++++++ python/problems/recursion/novak.png | Bin 0 -> 100267 bytes python/problems/recursion/path_to/common.py | 108 +++++++++++++++++++++ python/problems/recursion/path_to/en.py | 13 +++ python/problems/recursion/path_to/sl.py | 30 ++++++ python/problems/recursion/sl.py | 3 + python/problems/recursion/slovar.html | 44 +++++++++ 20 files changed, 803 insertions(+) create mode 100644 python/problems/recursion/common.py create mode 100644 python/problems/recursion/depth_to/common.py create mode 100644 python/problems/recursion/depth_to/en.py create mode 100644 python/problems/recursion/depth_to/sl.py create mode 100644 python/problems/recursion/en.py create mode 100644 python/problems/recursion/family_tree_name/common.py create mode 100644 python/problems/recursion/family_tree_name/en.py create mode 100644 python/problems/recursion/family_tree_name/sl.py create mode 100644 python/problems/recursion/family_tree_name_list/common.py create mode 100644 python/problems/recursion/family_tree_name_list/en.py create mode 100644 python/problems/recursion/family_tree_name_list/sl.py create mode 100644 python/problems/recursion/family_tree_youngest/common.py create mode 100644 python/problems/recursion/family_tree_youngest/en.py create mode 100644 python/problems/recursion/family_tree_youngest/sl.py create mode 100644 python/problems/recursion/novak.png create mode 100644 python/problems/recursion/path_to/common.py create mode 100644 python/problems/recursion/path_to/en.py create mode 100644 python/problems/recursion/path_to/sl.py create mode 100644 python/problems/recursion/sl.py create mode 100644 python/problems/recursion/slovar.html (limited to 'python/problems/recursion') diff --git a/python/problems/recursion/common.py b/python/problems/recursion/common.py new file mode 100644 index 0000000..f04b38b --- /dev/null +++ b/python/problems/recursion/common.py @@ -0,0 +1,2 @@ +id = 2008 +number = 8 \ No newline at end of file diff --git a/python/problems/recursion/depth_to/common.py b/python/problems/recursion/depth_to/common.py new file mode 100644 index 0000000..3aad348 --- /dev/null +++ b/python/problems/recursion/depth_to/common.py @@ -0,0 +1,107 @@ +import re +from python.util import has_token_sequence, string_almost_equal, \ + string_contains_number, get_tokens, get_numbers, get_exception_desc, \ + all_tokens, has_comprehension, has_loop, almost_equal, get_ast +from server.hints import Hint + +id = 20804 +number = 4 +visible = True + +solution = '''\ +def depthto(fr, to): + if fr == to: + return 0 + for c in children[fr]: + d = depthto(c, to) + if d is not None: + return d + 1 +''' + +precode = """ +children = { + "Adam": ["Matjaž", "Cilka", "Daniel", "Erik"], + "Aleksander": [], + "Alenka": [], + "Barbara": [], + "Cilka": [], + "Daniel": ["Elizabeta", "Hans"], + "Erik": [], + "Elizabeta": ["Ludvik", "Jurij", "Barbara", "Herman", "Mihael"], + "Franc": [], + "Herman": ["Margareta"], + "Hans": [], + "Jožef": ["Alenka", "Aleksander", "Petra"], + "Jurij": ["Franc", "Jožef"], + "Ludvik": [], + "Margareta": [], + "Matjaž": ["Viljem"], + "Mihael": [], + "Petra": [], + "Tadeja": [], + "Viljem": ["Tadeja"], +} + +age = { + "Adam": 111, "Matjaž": 90, "Cilka": 88, "Daniel": 85, "Erik": 83, + "Viljem": 58, "Tadeja": 20, "Elizabeta": 67, "Hans": 64, "Ludvik": 50, + "Jurij": 49, "Barbara": 45, "Herman": 39, "Mihael": 32, "Franc": 30, + "Jožef": 29, "Margareta": 10, "Alenka": 5, "Aleksander": 7, "Petra": 9 +}""" + +hint_type = { + 'final_hint': Hint('final_hint') +} + +def test(python, code): + code = precode + "\n" + code + func_name = 'depthto' + tokens = get_tokens(code) + if not has_token_sequence(tokens, ['def', func_name]): + return False, [{'id' : 'no_func_name', 'args' : {'func_name' : func_name}}] + + in_out = [ + (('Hans', 'Hans'), 0), + (('Daniel', 'Hans'), 1), + (('Adam', 'Hans'), 2), + (('Adam', 'Franc'), 4), + (('Adam', 'Petra'), 5), + (('Elizabeta', 'Aleksander'), 3), + (('Adam', 'Tadeja'), 3), + (('Daniel', 'Ludvik'), 2) + ] + + test_in = [('{0}{1}'.format(func_name, str(l[0])), None) + for l in in_out] + test_out = [l[1] for l in in_out] + + answers = python(code=code, inputs=test_in, timeout=1.0) + n_correct = 0 + tin, tout = None, None + for i, (ans, to) in enumerate(zip(answers, test_out)): + res = ans[0] + corr = res == to + n_correct += corr + if not corr: + tin = test_in[i][0] + tout = to + + passed = n_correct == len(test_in) + hints = [{'id': 'test_results', 'args': {'passed': n_correct, 'total': len(test_in)}}] + if tin: + hints.append({'id': 'problematic_test_case', 'args': {'testin': str(tin), 'testout': str(tout)}}) + if passed: + hints.append({'id': 'final_hint'}) + + return passed, hints + + +def hint(python, code): + tokens = get_tokens(code) + + # run one test first to see if there are any exceptions + answer = python(code=code, inputs=[(None, None)], timeout=1.0) + exc = get_exception_desc(answer[0][3]) + if exc: return exc + + return None diff --git a/python/problems/recursion/depth_to/en.py b/python/problems/recursion/depth_to/en.py new file mode 100644 index 0000000..9cb993d --- /dev/null +++ b/python/problems/recursion/depth_to/en.py @@ -0,0 +1,13 @@ +id = 20804 +name = 'Family tree: depth to' + +description = '''\ +

(translation missing)

''' + +hint = { + 'plan': '''\ +

(translation missing)

''', + + 'no_input_call': '''\ +

(translation missing)

''', +} diff --git a/python/problems/recursion/depth_to/sl.py b/python/problems/recursion/depth_to/sl.py new file mode 100644 index 0000000..e4315c0 --- /dev/null +++ b/python/problems/recursion/depth_to/sl.py @@ -0,0 +1,31 @@ +import server +mod = server.problems.load_language('python', 'sl') + +id = 20804 +name = 'Družinsko drevo: globina do' + +description = '''\ +

+Napišite funkcijo depthto(fr, to), ki pove kako globoko v rodbini +osebe fr je oseba z imenom to. +Uporabite družinsko +drevo (slika in +slovar).

+
+>>> depthto('Daniel', 'Hans')
+1
+>>> depthto('Adam', 'Hans')
+2
+>>> depthto('Adam', 'Franc')
+4
+
+''' + +plan = [] + +hint = { + 'final_hint': ['''\ +

Program je pravilen!
+

+'''], +} diff --git a/python/problems/recursion/en.py b/python/problems/recursion/en.py new file mode 100644 index 0000000..a1e8f91 --- /dev/null +++ b/python/problems/recursion/en.py @@ -0,0 +1,3 @@ +name = 'Recursion' +description = '' + diff --git a/python/problems/recursion/family_tree_name/common.py b/python/problems/recursion/family_tree_name/common.py new file mode 100644 index 0000000..d924665 --- /dev/null +++ b/python/problems/recursion/family_tree_name/common.py @@ -0,0 +1,103 @@ +import re +from python.util import has_token_sequence, string_almost_equal, \ + string_contains_number, get_tokens, get_numbers, get_exception_desc, \ + all_tokens, has_comprehension, has_loop, almost_equal, get_ast +from server.hints import Hint + +id = 20801 +number = 1 +visible = True + +solution = '''\ +def printnames(name): + print(name) + for c in children[name]: + printnames(c) +''' + +hint_type = { + 'final_hint': Hint('final_hint') +} + +precode = """ +children = { + "Adam": ["Matjaž", "Cilka", "Daniel", "Erik"], + "Aleksander": [], + "Alenka": [], + "Barbara": [], + "Cilka": [], + "Daniel": ["Elizabeta", "Hans"], + "Erik": [], + "Elizabeta": ["Ludvik", "Jurij", "Barbara", "Herman", "Mihael"], + "Franc": [], + "Herman": ["Margareta"], + "Hans": [], + "Jožef": ["Alenka", "Aleksander", "Petra"], + "Jurij": ["Franc", "Jožef"], + "Ludvik": [], + "Margareta": [], + "Matjaž": ["Viljem"], + "Mihael": [], + "Petra": [], + "Tadeja": [], + "Viljem": ["Tadeja"], +} + +age = { + "Adam": 111, "Matjaž": 90, "Cilka": 88, "Daniel": 85, "Erik": 83, + "Viljem": 58, "Tadeja": 20, "Elizabeta": 67, "Hans": 64, "Ludvik": 50, + "Jurij": 49, "Barbara": 45, "Herman": 39, "Mihael": 32, "Franc": 30, + "Jožef": 29, "Margareta": 10, "Alenka": 5, "Aleksander": 7, "Petra": 9 +}""" + +def test(python, code): + code = precode + "\n" + code + + func_name = 'printnames' + tokens = get_tokens(code) + if not has_token_sequence(tokens, ['def', func_name]): + return False, [{'id' : 'no_func_name', 'args' : {'func_name' : func_name}}] + + in_out = [ + ('Hans', ['Hans']), + ('Herman', ['Herman', 'Margareta']), + ('Jurij', ['Jurij', 'Franc', 'Jožef', 'Alenka', 'Aleksander', 'Petra']), + ('Viljem', ['Viljem', 'Tadeja']), + ('Daniel', ['Daniel', 'Elizabeta', 'Ludvik', 'Jurij', 'Franc', 'Jožef', 'Alenka', 'Aleksander', 'Petra', 'Barbara', 'Herman', 'Margareta', 'Mihael', 'Hans']), + ('Adam', ['Adam', 'Matjaž', 'Viljem', 'Tadeja', 'Cilka', 'Daniel', 'Elizabeta', 'Ludvik', 'Jurij', 'Franc', 'Jožef', 'Alenka', 'Aleksander', 'Petra', 'Barbara', 'Herman', 'Margareta', 'Mihael', 'Hans', 'Erik']) + ] + + test_in = [('{0}("{1}")'.format(func_name, str(l[0])), None) + for l in in_out] + test_out = [l[1] for l in in_out] + + answers = python(code=code, inputs=test_in, timeout=1.0) + n_correct = 0 + tin, tout = None, None + for i, (ans, to) in enumerate(zip(answers, test_out)): + res = ans[1].splitlines() + corr = len(res) == len(to) and set(res) == set(to) + n_correct += corr + if not corr: + tin = test_in[i][0] + tout = to + + passed = n_correct == len(test_in) + hints = [{'id': 'test_results', 'args': {'passed': n_correct, 'total': len(test_in)}}] + if tin: + hints.append({'id': 'problematic_test_case', 'args': {'testin': str(tin), 'testout': str(tout)}}) + if passed: + hints.append({'id': 'final_hint'}) + + return passed, hints + + +def hint(python, code): + tokens = get_tokens(code) + + # run one test first to see if there are any exceptions + answer = python(code=code, inputs=[(None, None)], timeout=1.0) + exc = get_exception_desc(answer[0][3]) + if exc: return exc + + return None diff --git a/python/problems/recursion/family_tree_name/en.py b/python/problems/recursion/family_tree_name/en.py new file mode 100644 index 0000000..b5621df --- /dev/null +++ b/python/problems/recursion/family_tree_name/en.py @@ -0,0 +1,13 @@ +id = 20801 +name = 'Family tree: printing names' + +description = '''\ +

(translation missing)

''' + +hint = { + 'plan': '''\ +

(translation missing)

''', + + 'no_input_call': '''\ +

(translation missing)

''', +} diff --git a/python/problems/recursion/family_tree_name/sl.py b/python/problems/recursion/family_tree_name/sl.py new file mode 100644 index 0000000..ff42c50 --- /dev/null +++ b/python/problems/recursion/family_tree_name/sl.py @@ -0,0 +1,42 @@ +import server +mod = server.problems.load_language('python', 'sl') + +id = 20801 +name = 'Družinsko drevo: izpis imen' + +description = '''\ +

+Napišite funkcijo printnames(name), ki izpiše vsa imena v določeni rodbini. +Uporabite družinsko +drevo (slika in +slovar), +ki ste ga spoznali na predavanjih.

+
+>>> printnames('Hans')
+Hans
+>>> printnames('Daniel')
+Daniel
+Elizabeta
+Ludvik
+Jurij
+Franc
+Jožef
+Alenka
+Aleksander
+Petra
+Barbara
+Herman
+Margareta
+Mihael
+Hans
+
+''' + +plan = [] + +hint = { + 'final_hint': ['''\ +

Program je pravilen!
+

+'''], +} diff --git a/python/problems/recursion/family_tree_name_list/common.py b/python/problems/recursion/family_tree_name_list/common.py new file mode 100644 index 0000000..880d8b1 --- /dev/null +++ b/python/problems/recursion/family_tree_name_list/common.py @@ -0,0 +1,104 @@ +import re +from python.util import has_token_sequence, string_almost_equal, \ + string_contains_number, get_tokens, get_numbers, get_exception_desc, \ + all_tokens, has_comprehension, has_loop, almost_equal, get_ast +from server.hints import Hint + +id = 20802 +number = 2 +visible = True + +solution = '''\ +def names(name): + xs = [name] + for c in children[ime]: + xs.extend(names(c)) + return xs +''' + +hint_type = { + 'final_hint': Hint('final_hint') +} + +precode = """ +children = { + "Adam": ["Matjaž", "Cilka", "Daniel", "Erik"], + "Aleksander": [], + "Alenka": [], + "Barbara": [], + "Cilka": [], + "Daniel": ["Elizabeta", "Hans"], + "Erik": [], + "Elizabeta": ["Ludvik", "Jurij", "Barbara", "Herman", "Mihael"], + "Franc": [], + "Herman": ["Margareta"], + "Hans": [], + "Jožef": ["Alenka", "Aleksander", "Petra"], + "Jurij": ["Franc", "Jožef"], + "Ludvik": [], + "Margareta": [], + "Matjaž": ["Viljem"], + "Mihael": [], + "Petra": [], + "Tadeja": [], + "Viljem": ["Tadeja"], +} + +age = { + "Adam": 111, "Matjaž": 90, "Cilka": 88, "Daniel": 85, "Erik": 83, + "Viljem": 58, "Tadeja": 20, "Elizabeta": 67, "Hans": 64, "Ludvik": 50, + "Jurij": 49, "Barbara": 45, "Herman": 39, "Mihael": 32, "Franc": 30, + "Jožef": 29, "Margareta": 10, "Alenka": 5, "Aleksander": 7, "Petra": 9 +}""" + +def test(python, code): + code = precode + "\n" + code + + func_name = 'names' + tokens = get_tokens(code) + if not has_token_sequence(tokens, ['def', func_name]): + return False, [{'id' : 'no_func_name', 'args' : {'func_name' : func_name}}] + + in_out = [ + ('Hans', ['Hans']), + ('Herman', ['Herman', 'Margareta']), + ('Jurij', ['Jurij', 'Franc', 'Jožef', 'Alenka', 'Aleksander', 'Petra']), + ('Viljem', ['Viljem', 'Tadeja']), + ('Daniel', ['Daniel', 'Elizabeta', 'Ludvik', 'Jurij', 'Franc', 'Jožef', 'Alenka', 'Aleksander', 'Petra', 'Barbara', 'Herman', 'Margareta', 'Mihael', 'Hans']), + ('Adam', ['Adam', 'Matjaž', 'Viljem', 'Tadeja', 'Cilka', 'Daniel', 'Elizabeta', 'Ludvik', 'Jurij', 'Franc', 'Jožef', 'Alenka', 'Aleksander', 'Petra', 'Barbara', 'Herman', 'Margareta', 'Mihael', 'Hans', 'Erik']) + ] + + test_in = [('{0}("{1}")'.format(func_name, str(l[0])), None) + for l in in_out] + test_out = [l[1] for l in in_out] + + answers = python(code=code, inputs=test_in, timeout=1.0) + n_correct = 0 + tin, tout = None, None + for i, (ans, to) in enumerate(zip(answers, test_out)): + res = ans[0] + corr = len(res) == len(to) and set(res) == set(to) + n_correct += corr + if not corr: + tin = test_in[i][0] + tout = to + + passed = n_correct == len(test_in) + hints = [{'id': 'test_results', 'args': {'passed': n_correct, 'total': len(test_in)}}] + if tin: + hints.append({'id': 'problematic_test_case', 'args': {'testin': str(tin), 'testout': str(tout)}}) + if passed: + hints.append({'id': 'final_hint'}) + + return passed, hints + + +def hint(python, code): + tokens = get_tokens(code) + + # run one test first to see if there are any exceptions + answer = python(code=code, inputs=[(None, None)], timeout=1.0) + exc = get_exception_desc(answer[0][3]) + if exc: return exc + + return None diff --git a/python/problems/recursion/family_tree_name_list/en.py b/python/problems/recursion/family_tree_name_list/en.py new file mode 100644 index 0000000..9d1820a --- /dev/null +++ b/python/problems/recursion/family_tree_name_list/en.py @@ -0,0 +1,13 @@ +id = 20802 +name = 'Family tree: list of names' + +description = '''\ +

(translation missing)

''' + +hint = { + 'plan': '''\ +

(translation missing)

''', + + 'no_input_call': '''\ +

(translation missing)

''', +} diff --git a/python/problems/recursion/family_tree_name_list/sl.py b/python/problems/recursion/family_tree_name_list/sl.py new file mode 100644 index 0000000..261e401 --- /dev/null +++ b/python/problems/recursion/family_tree_name_list/sl.py @@ -0,0 +1,28 @@ +import server +mod = server.problems.load_language('python', 'sl') + +id = 20802 +name = 'Družinsko drevo: seznam imen' + +description = '''\ +

+Podobno kot pri prejšnji nalogi napišite funkcijo names(name), ki +tokrat vrne vse imena v seznamu. Uporabite družinsko +drevo (slika in +slovar).

+
+>>> names('Hans')
+['Hans']
+>>> names('Daniel')
+['Daniel', 'Elizabeta', 'Ludvik', 'Jurij', 'Franc', 'Jožef', 'Alenka', 'Aleksander', 'Petra', 'Barbara', 'Herman', 'Margareta', 'Mihael', 'Hans']
+
+''' + +plan = [] + +hint = { + 'final_hint': ['''\ +

Program je pravilen!
+

+'''], +} diff --git a/python/problems/recursion/family_tree_youngest/common.py b/python/problems/recursion/family_tree_youngest/common.py new file mode 100644 index 0000000..099c1d3 --- /dev/null +++ b/python/problems/recursion/family_tree_youngest/common.py @@ -0,0 +1,104 @@ +import re +from python.util import has_token_sequence, string_almost_equal, \ + string_contains_number, get_tokens, get_numbers, get_exception_desc, \ + all_tokens, has_comprehension, has_loop, almost_equal, get_ast +from server.hints import Hint + +id = 20803 +number = 3 +visible = True + +solution = '''\ +def youngest(name): + xs = [(age[name], name)] + for c in children[name]: + xs.append(youngest(c)) + return min(xs) +''' + +hint_type = { + 'final_hint': Hint('final_hint') +} + +precode = """ +children = { + "Adam": ["Matjaž", "Cilka", "Daniel", "Erik"], + "Aleksander": [], + "Alenka": [], + "Barbara": [], + "Cilka": [], + "Daniel": ["Elizabeta", "Hans"], + "Erik": [], + "Elizabeta": ["Ludvik", "Jurij", "Barbara", "Herman", "Mihael"], + "Franc": [], + "Herman": ["Margareta"], + "Hans": [], + "Jožef": ["Alenka", "Aleksander", "Petra"], + "Jurij": ["Franc", "Jožef"], + "Ludvik": [], + "Margareta": [], + "Matjaž": ["Viljem"], + "Mihael": [], + "Petra": [], + "Tadeja": [], + "Viljem": ["Tadeja"], +} + +age = { + "Adam": 111, "Matjaž": 90, "Cilka": 88, "Daniel": 85, "Erik": 83, + "Viljem": 58, "Tadeja": 20, "Elizabeta": 67, "Hans": 64, "Ludvik": 50, + "Jurij": 49, "Barbara": 45, "Herman": 39, "Mihael": 32, "Franc": 30, + "Jožef": 29, "Margareta": 10, "Alenka": 5, "Aleksander": 7, "Petra": 9 +}""" + +def test(python, code): + code = precode + "\n" + code + + func_name = 'youngest' + tokens = get_tokens(code) + if not has_token_sequence(tokens, ['def', func_name]): + return False, [{'id' : 'no_func_name', 'args' : {'func_name' : func_name}}] + + in_out = [ + ('Hans', (64, 'Hans')), + ('Daniel', (5, 'Alenka')), + ('Herman', (10, 'Margareta')), + ('Viljem', (20, 'Tadeja')), + ('Aleksander', (7, 'Aleksander')), + ('Adam', (5, 'Alenka')) + ] + + test_in = [('{0}("{1}")'.format(func_name, str(l[0])), None) + for l in in_out] + test_out = [l[1] for l in in_out] + + answers = python(code=code, inputs=test_in, timeout=1.0) + n_correct = 0 + tin, tout = None, None + for i, (ans, to) in enumerate(zip(answers, test_out)): + res = ans[0] + corr = res == to + n_correct += corr + if not corr: + tin = test_in[i][0] + tout = to + + passed = n_correct == len(test_in) + hints = [{'id': 'test_results', 'args': {'passed': n_correct, 'total': len(test_in)}}] + if tin: + hints.append({'id': 'problematic_test_case', 'args': {'testin': str(tin), 'testout': str(tout)}}) + if passed: + hints.append({'id': 'final_hint'}) + + return passed, hints + + +def hint(python, code): + tokens = get_tokens(code) + + # run one test first to see if there are any exceptions + answer = python(code=code, inputs=[(None, None)], timeout=1.0) + exc = get_exception_desc(answer[0][3]) + if exc: return exc + + return None diff --git a/python/problems/recursion/family_tree_youngest/en.py b/python/problems/recursion/family_tree_youngest/en.py new file mode 100644 index 0000000..ba3f813 --- /dev/null +++ b/python/problems/recursion/family_tree_youngest/en.py @@ -0,0 +1,13 @@ +id = 20803 +name = 'Family tree: the youngest' + +description = '''\ +

(translation missing)

''' + +hint = { + 'plan': '''\ +

(translation missing)

''', + + 'no_input_call': '''\ +

(translation missing)

''', +} diff --git a/python/problems/recursion/family_tree_youngest/sl.py b/python/problems/recursion/family_tree_youngest/sl.py new file mode 100644 index 0000000..04c2700 --- /dev/null +++ b/python/problems/recursion/family_tree_youngest/sl.py @@ -0,0 +1,29 @@ +import server +mod = server.problems.load_language('python', 'sl') + +id = 20803 +name = 'Družinsko drevo: najmlajši' + +description = '''\ +

+Funkcija youngest(name) naj vrne starost in ime +najmlajšega člana določene rodbine. +Uporabite družinsko +drevo (slika in +slovar).

+
+>>> youngest('Hans')
+(64, 'Hans')
+>>> youngest('Daniel')
+(5, 'Alenka')
+
+''' + +plan = [] + +hint = { + 'final_hint': ['''\ +

Program je pravilen!
+

+'''], +} diff --git a/python/problems/recursion/novak.png b/python/problems/recursion/novak.png new file mode 100644 index 0000000..6bfc520 Binary files /dev/null and b/python/problems/recursion/novak.png differ diff --git a/python/problems/recursion/path_to/common.py b/python/problems/recursion/path_to/common.py new file mode 100644 index 0000000..cf63b6c --- /dev/null +++ b/python/problems/recursion/path_to/common.py @@ -0,0 +1,108 @@ +import re +from python.util import has_token_sequence, string_almost_equal, \ + string_contains_number, get_tokens, get_numbers, get_exception_desc, \ + all_tokens, has_comprehension, has_loop, almost_equal, get_ast +from server.hints import Hint + +id = 20805 +number = 5 +visible = True + +solution = '''\ +def pathto(fr, to): + if fr == to: + return [fr] + for c in children[fr]: + d = pathto(c, to) + if d is not None: + return [fr] + d +''' + +hint_type = { + 'final_hint': Hint('final_hint') +} + +precode = """ +children = { + "Adam": ["Matjaž", "Cilka", "Daniel", "Erik"], + "Aleksander": [], + "Alenka": [], + "Barbara": [], + "Cilka": [], + "Daniel": ["Elizabeta", "Hans"], + "Erik": [], + "Elizabeta": ["Ludvik", "Jurij", "Barbara", "Herman", "Mihael"], + "Franc": [], + "Herman": ["Margareta"], + "Hans": [], + "Jožef": ["Alenka", "Aleksander", "Petra"], + "Jurij": ["Franc", "Jožef"], + "Ludvik": [], + "Margareta": [], + "Matjaž": ["Viljem"], + "Mihael": [], + "Petra": [], + "Tadeja": [], + "Viljem": ["Tadeja"], +} + +age = { + "Adam": 111, "Matjaž": 90, "Cilka": 88, "Daniel": 85, "Erik": 83, + "Viljem": 58, "Tadeja": 20, "Elizabeta": 67, "Hans": 64, "Ludvik": 50, + "Jurij": 49, "Barbara": 45, "Herman": 39, "Mihael": 32, "Franc": 30, + "Jožef": 29, "Margareta": 10, "Alenka": 5, "Aleksander": 7, "Petra": 9 +}""" + +def test(python, code): + code = precode + "\n" + code + + func_name = 'pathto' + tokens = get_tokens(code) + if not has_token_sequence(tokens, ['def', func_name]): + return False, [{'id' : 'no_func_name', 'args' : {'func_name' : func_name}}] + + in_out = [ + (('Hans', 'Hans'), ['Hans']), + (('Daniel', 'Hans'), ['Daniel', 'Hans']), + (('Adam', 'Hans'), ['Adam', 'Daniel', 'Hans']), + (('Adam', 'Franc'), ['Adam', 'Daniel', 'Elizabeta', 'Jurij', 'Franc']), + (('Adam', 'Petra'), ['Adam', 'Daniel', 'Elizabeta', 'Jurij', 'Jožef', 'Petra']), + (('Elizabeta', 'Aleksander'), ['Elizabeta', 'Jurij', 'Jožef', 'Aleksander']), + (('Adam', 'Tadeja'), ['Adam', 'Matjaž', 'Viljem', 'Tadeja']), + (('Daniel', 'Ludvik'), ['Daniel', 'Elizabeta', 'Ludvik']) + ] + + test_in = [('{0}{1}'.format(func_name, str(l[0])), None) + for l in in_out] + test_out = [l[1] for l in in_out] + + answers = python(code=code, inputs=test_in, timeout=1.0) + n_correct = 0 + tin, tout = None, None + for i, (ans, to) in enumerate(zip(answers, test_out)): + res = ans[0] + corr = res == to + n_correct += corr + if not corr: + tin = test_in[i][0] + tout = to + + passed = n_correct == len(test_in) + hints = [{'id': 'test_results', 'args': {'passed': n_correct, 'total': len(test_in)}}] + if tin: + hints.append({'id': 'problematic_test_case', 'args': {'testin': str(tin), 'testout': str(tout)}}) + if passed: + hints.append({'id': 'final_hint'}) + + return passed, hints + + +def hint(python, code): + tokens = get_tokens(code) + + # run one test first to see if there are any exceptions + answer = python(code=code, inputs=[(None, None)], timeout=1.0) + exc = get_exception_desc(answer[0][3]) + if exc: return exc + + return None diff --git a/python/problems/recursion/path_to/en.py b/python/problems/recursion/path_to/en.py new file mode 100644 index 0000000..703d818 --- /dev/null +++ b/python/problems/recursion/path_to/en.py @@ -0,0 +1,13 @@ +id = 20805 +name = 'Family tree: path to' + +description = '''\ +

(translation missing)

''' + +hint = { + 'plan': '''\ +

(translation missing)

''', + + 'no_input_call': '''\ +

(translation missing)

''', +} diff --git a/python/problems/recursion/path_to/sl.py b/python/problems/recursion/path_to/sl.py new file mode 100644 index 0000000..b53bd26 --- /dev/null +++ b/python/problems/recursion/path_to/sl.py @@ -0,0 +1,30 @@ +import server +mod = server.problems.load_language('python', 'sl') + +id = 20805 +name = 'Družinsko drevo: pot do' + +description = '''\ +

+Reši podobno nalogo kot je prejšnja, le da naj funkcija ne vrne razdalje do +določene osebe, temveč pot do nje. Uporabite družinsko +drevo (slika in +slovar).

+
+>>> pathto('Daniel', 'Hans')
+['Daniel', 'Hans']
+>>> pathto('Adam', 'Hans')
+['Adam', 'Daniel', 'Hans']
+>>> pathto('Adam', 'Franc')
+['Adam', 'Daniel', 'Elizabeta', 'Jurij', 'Franc']
+
+''' + +plan = [] + +hint = { + 'final_hint': ['''\ +

Program je pravilen!
+

+'''], +} diff --git a/python/problems/recursion/sl.py b/python/problems/recursion/sl.py new file mode 100644 index 0000000..be7d05a --- /dev/null +++ b/python/problems/recursion/sl.py @@ -0,0 +1,3 @@ +name = 'Rekurzija' +description = 'Vaje iz rekurzije' + diff --git a/python/problems/recursion/slovar.html b/python/problems/recursion/slovar.html new file mode 100644 index 0000000..ed80a01 --- /dev/null +++ b/python/problems/recursion/slovar.html @@ -0,0 +1,44 @@ + + + + + + + + + + +
+children = {
+    "Adam": ["Matjaž", "Cilka", "Daniel", "Erik"],
+    "Aleksander": [],
+    "Alenka": [],
+    "Barbara": [],
+    "Cilka": [],
+    "Daniel": ["Elizabeta", "Hans"],
+    "Erik": [],
+    "Elizabeta": ["Ludvik", "Jurij", "Barbara", "Herman", "Mihael"],
+    "Franc": [],
+    "Herman": ["Margareta"],
+    "Hans": [],
+    "Jožef": ["Alenka", "Aleksander", "Petra"],
+    "Jurij": ["Franc", "Jožef"],
+    "Ludvik": [],
+    "Margareta": [],
+    "Matjaž": ["Viljem"],
+    "Mihael": [],
+    "Petra": [],
+    "Tadeja": [],
+    "Viljem": ["Tadeja"],
+}
+
+age = {
+    "Adam": 111, "Matjaž": 90, "Cilka": 88, "Daniel": 85, "Erik": 83,
+    "Viljem": 58, "Tadeja": 20, "Elizabeta": 67, "Hans": 64, "Ludvik": 50,
+    "Jurij": 49, "Barbara": 45, "Herman": 39, "Mihael": 32, "Franc": 30,
+    "Jožef": 29, "Margareta": 10, "Alenka": 5, "Aleksander": 7, "Petra": 9
+}
+
+ + + -- cgit v1.2.1