From 95e2fe57f6e4639f6ae9f1fef368829d5090dbf6 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Ale=C5=A1=20Smodi=C5=A1?= Date: Tue, 18 Aug 2015 16:06:19 +0200 Subject: Exported all problems from the SQLite database into the new directory structure. --- .../denotational_semantics_aux__predicates.py | 32 ++++++++ prolog/facts/family_relations.py | 76 ++++++++++++++++++ prolog/problems/clp_fd/gcd_3/common.py | 16 ++++ prolog/problems/clp_fd/gcd_3/en.py | 13 +++ prolog/problems/clp_fd/magic_1/common.py | 17 ++++ prolog/problems/clp_fd/magic_1/en.py | 13 +++ prolog/problems/clp_fd/puzzle_abc_3/common.py | 14 ++++ prolog/problems/clp_fd/puzzle_abc_3/en.py | 9 +++ prolog/problems/clp_fd/puzzle_beth_1/common.py | 9 +++ prolog/problems/clp_fd/puzzle_beth_1/en.py | 10 +++ prolog/problems/clp_fd/puzzle_momson_2/common.py | 14 ++++ prolog/problems/clp_fd/puzzle_momson_2/en.py | 9 +++ prolog/problems/clp_fd/puzzle_ratio_2/common.py | 17 ++++ prolog/problems/clp_fd/puzzle_ratio_2/en.py | 9 +++ prolog/problems/clp_fd/tobase_3/common.py | 15 ++++ prolog/problems/clp_fd/tobase_3/en.py | 16 ++++ prolog/problems/clp_r/bounding_box_3/common.py | 14 ++++ prolog/problems/clp_r/bounding_box_3/en.py | 12 +++ prolog/problems/clp_r/center_3/common.py | 20 +++++ prolog/problems/clp_r/center_3/en.py | 13 +++ prolog/problems/clp_r/linear_opt_3/common.py | 12 +++ prolog/problems/clp_r/linear_opt_3/en.py | 16 ++++ prolog/problems/clp_r/max_sum_2/common.py | 12 +++ prolog/problems/clp_r/max_sum_2/en.py | 14 ++++ prolog/problems/clp_r/megabytes_2/common.py | 9 +++ prolog/problems/clp_r/megabytes_2/en.py | 14 ++++ prolog/problems/clp_r/turkey_3/common.py | 15 ++++ prolog/problems/clp_r/turkey_3/en.py | 10 +++ prolog/problems/dcg/ab_2/common.py | 11 +++ prolog/problems/dcg/ab_2/en.py | 10 +++ prolog/problems/dcg/digit_2/common.py | 9 +++ prolog/problems/dcg/digit_2/en.py | 8 ++ prolog/problems/dcg/expr_2/common.py | 23 ++++++ prolog/problems/dcg/expr_2/en.py | 10 +++ prolog/problems/dcg/expr_3/common.py | 24 ++++++ prolog/problems/dcg/expr_3/en.py | 14 ++++ prolog/problems/dcg/flower_2/common.py | 13 +++ prolog/problems/dcg/flower_2/en.py | 10 +++ prolog/problems/dcg/number_2/common.py | 12 +++ prolog/problems/dcg/number_2/en.py | 9 +++ prolog/problems/dcg/number_3/common.py | 30 +++++++ prolog/problems/dcg/number_3/en.py | 13 +++ prolog/problems/dcg/number_proper_2/common.py | 16 ++++ prolog/problems/dcg/number_proper_2/en.py | 9 +++ prolog/problems/dcg/paren_2/common.py | 10 +++ prolog/problems/dcg/paren_2/en.py | 10 +++ prolog/problems/dcg/paren_3/common.py | 10 +++ prolog/problems/dcg/paren_3/en.py | 13 +++ .../denotational_semantics/algol_3/common.py | 79 ++++++++++++++++++ .../problems/denotational_semantics/algol_3/en.py | 33 ++++++++ .../denotational_semantics/algol_for_3/common.py | 93 ++++++++++++++++++++++ .../denotational_semantics/algol_for_3/en.py | 19 +++++ .../denotational_semantics/algol_if_3/common.py | 86 ++++++++++++++++++++ .../denotational_semantics/algol_if_3/en.py | 20 +++++ .../prog_8puzzle_2/common.py | 17 ++++ .../denotational_semantics/prog_8puzzle_2/en.py | 10 +++ .../prog_8puzzle_3/common.py | 37 +++++++++ .../denotational_semantics/prog_8puzzle_3/en.py | 19 +++++ .../prog_listswap_2/common.py | 16 ++++ .../denotational_semantics/prog_listswap_2/en.py | 11 +++ .../prog_listswap_3/common.py | 24 ++++++ .../denotational_semantics/prog_listswap_3/en.py | 18 +++++ .../problems/family_relations/ancestor_2/common.py | 13 +++ prolog/problems/family_relations/ancestor_2/en.py | 14 ++++ prolog/problems/family_relations/aunt_2/common.py | 17 ++++ prolog/problems/family_relations/aunt_2/en.py | 13 +++ .../problems/family_relations/brother_2/common.py | 13 +++ prolog/problems/family_relations/brother_2/en.py | 13 +++ .../family_relations/connected_3/common.py | 16 ++++ prolog/problems/family_relations/connected_3/en.py | 14 ++++ .../problems/family_relations/cousin_2/common.py | 26 ++++++ prolog/problems/family_relations/cousin_2/en.py | 13 +++ .../family_relations/descendant_2/common.py | 13 +++ .../problems/family_relations/descendant_2/en.py | 14 ++++ .../family_relations/grandparent_2/common.py | 11 +++ .../problems/family_relations/grandparent_2/en.py | 15 ++++ .../problems/family_relations/mother_2/common.py | 11 +++ prolog/problems/family_relations/mother_2/en.py | 15 ++++ .../problems/family_relations/sister_2/common.py | 13 +++ prolog/problems/family_relations/sister_2/en.py | 12 +++ .../license_plates/checklicenseplate_3/common.py | 52 ++++++++++++ .../license_plates/checklicenseplate_3/en.py | 17 ++++ .../problems/license_plates/firstminus_2/common.py | 11 +++ prolog/problems/license_plates/firstminus_2/en.py | 13 +++ prolog/problems/license_plates/genexp_2/common.py | 23 ++++++ prolog/problems/license_plates/genexp_2/en.py | 18 +++++ .../problems/license_plates/getdigits_2/common.py | 14 ++++ prolog/problems/license_plates/getdigits_2/en.py | 12 +++ .../problems/license_plates/joindigits_2/common.py | 14 ++++ prolog/problems/license_plates/joindigits_2/en.py | 15 ++++ prolog/problems/lists/conc_3/common.py | 11 +++ prolog/problems/lists/conc_3/en.py | 14 ++++ prolog/problems/lists/count_3/common.py | 15 ++++ prolog/problems/lists/count_3/en.py | 12 +++ prolog/problems/lists/del_3/common.py | 11 +++ prolog/problems/lists/del_3/en.py | 19 +++++ prolog/problems/lists/divide_3/common.py | 12 +++ prolog/problems/lists/divide_3/en.py | 14 ++++ prolog/problems/lists/dup_2/common.py | 11 +++ prolog/problems/lists/dup_2/en.py | 14 ++++ .../problems/lists/evenlen_1_+_oddlen_1/common.py | 15 ++++ prolog/problems/lists/evenlen_1_+_oddlen_1/en.py | 17 ++++ prolog/problems/lists/insert_3/common.py | 13 +++ prolog/problems/lists/insert_3/en.py | 14 ++++ prolog/problems/lists/len_2/common.py | 12 +++ prolog/problems/lists/len_2/en.py | 12 +++ prolog/problems/lists/max_2/common.py | 14 ++++ prolog/problems/lists/max_2/en.py | 14 ++++ prolog/problems/lists/memb_2/common.py | 11 +++ prolog/problems/lists/memb_2/en.py | 16 ++++ prolog/problems/lists/min_2/common.py | 14 ++++ prolog/problems/lists/min_2/en.py | 14 ++++ prolog/problems/lists/palindrome_1/common.py | 17 ++++ prolog/problems/lists/palindrome_1/en.py | 14 ++++ prolog/problems/lists/permute_2/common.py | 15 ++++ prolog/problems/lists/permute_2/en.py | 17 ++++ prolog/problems/lists/rev_2/common.py | 15 ++++ prolog/problems/lists/rev_2/en.py | 14 ++++ prolog/problems/lists/shiftleft_2/common.py | 13 +++ prolog/problems/lists/shiftleft_2/en.py | 12 +++ prolog/problems/lists/shiftright_2/common.py | 13 +++ prolog/problems/lists/shiftright_2/en.py | 12 +++ prolog/problems/lists/sublist_2/common.py | 14 ++++ prolog/problems/lists/sublist_2/en.py | 18 +++++ prolog/problems/lists/sum_2/common.py | 12 +++ prolog/problems/lists/sum_2/en.py | 12 +++ prolog/problems/old_exams/pascal_3/common.py | 16 ++++ prolog/problems/old_exams/pascal_3/en.py | 26 ++++++ prolog/problems/other/genlist_4/common.py | 14 ++++ prolog/problems/other/genlist_4/en.py | 12 +++ prolog/problems/sets/diff_3/common.py | 19 +++++ prolog/problems/sets/diff_3/en.py | 12 +++ prolog/problems/sets/intersect_3/common.py | 18 +++++ prolog/problems/sets/intersect_3/en.py | 12 +++ prolog/problems/sets/is_subset_2/common.py | 16 ++++ prolog/problems/sets/is_subset_2/en.py | 14 ++++ prolog/problems/sets/is_superset_2/common.py | 16 ++++ prolog/problems/sets/is_superset_2/en.py | 14 ++++ prolog/problems/sets/powerset_2/common.py | 16 ++++ prolog/problems/sets/powerset_2/en.py | 12 +++ prolog/problems/sets/subset_2/common.py | 13 +++ prolog/problems/sets/subset_2/en.py | 19 +++++ prolog/problems/sets/union_3/common.py | 19 +++++ prolog/problems/sets/union_3/en.py | 12 +++ prolog/problems/sorting/is_sorted_1/common.py | 13 +++ prolog/problems/sorting/is_sorted_1/en.py | 14 ++++ prolog/problems/sorting/isort_2/common.py | 18 +++++ prolog/problems/sorting/isort_2/en.py | 12 +++ prolog/problems/sorting/pivoting_4/common.py | 15 ++++ prolog/problems/sorting/pivoting_4/en.py | 12 +++ prolog/problems/sorting/quick_sort_2/common.py | 24 ++++++ prolog/problems/sorting/quick_sort_2/en.py | 12 +++ prolog/problems/sorting/sins_3/common.py | 14 ++++ prolog/problems/sorting/sins_3/en.py | 14 ++++ .../problems/sorting/slowest_sort_ever_2/common.py | 25 ++++++ prolog/problems/sorting/slowest_sort_ever_2/en.py | 12 +++ prolog/problems/trees/deletebt_3/common.py | 17 ++++ prolog/problems/trees/deletebt_3/en.py | 14 ++++ prolog/problems/trees/depthbt_2/common.py | 17 ++++ prolog/problems/trees/depthbt_2/en.py | 12 +++ prolog/problems/trees/insertbt_3/common.py | 20 +++++ prolog/problems/trees/insertbt_3/en.py | 15 ++++ prolog/problems/trees/maxt_2/common.py | 25 ++++++ prolog/problems/trees/maxt_2/en.py | 12 +++ prolog/problems/trees/memberbt_2/common.py | 13 +++ prolog/problems/trees/memberbt_2/en.py | 14 ++++ prolog/problems/trees/membert_2/common.py | 18 +++++ prolog/problems/trees/membert_2/en.py | 14 ++++ prolog/problems/trees/mirrorbt_2/common.py | 12 +++ prolog/problems/trees/mirrorbt_2/en.py | 12 +++ prolog/problems/trees/numberbt_2/common.py | 13 +++ prolog/problems/trees/numberbt_2/en.py | 12 +++ prolog/problems/trees/tolistbt_2/common.py | 17 ++++ prolog/problems/trees/tolistbt_2/en.py | 12 +++ 174 files changed, 2872 insertions(+) create mode 100644 prolog/facts/denotational_semantics_aux__predicates.py create mode 100644 prolog/facts/family_relations.py create mode 100644 prolog/problems/clp_fd/gcd_3/common.py create mode 100644 prolog/problems/clp_fd/gcd_3/en.py create mode 100644 prolog/problems/clp_fd/magic_1/common.py create mode 100644 prolog/problems/clp_fd/magic_1/en.py create mode 100644 prolog/problems/clp_fd/puzzle_abc_3/common.py create mode 100644 prolog/problems/clp_fd/puzzle_abc_3/en.py create mode 100644 prolog/problems/clp_fd/puzzle_beth_1/common.py create mode 100644 prolog/problems/clp_fd/puzzle_beth_1/en.py create mode 100644 prolog/problems/clp_fd/puzzle_momson_2/common.py create mode 100644 prolog/problems/clp_fd/puzzle_momson_2/en.py create mode 100644 prolog/problems/clp_fd/puzzle_ratio_2/common.py create mode 100644 prolog/problems/clp_fd/puzzle_ratio_2/en.py create mode 100644 prolog/problems/clp_fd/tobase_3/common.py create mode 100644 prolog/problems/clp_fd/tobase_3/en.py create mode 100644 prolog/problems/clp_r/bounding_box_3/common.py create mode 100644 prolog/problems/clp_r/bounding_box_3/en.py create mode 100644 prolog/problems/clp_r/center_3/common.py create mode 100644 prolog/problems/clp_r/center_3/en.py create mode 100644 prolog/problems/clp_r/linear_opt_3/common.py create mode 100644 prolog/problems/clp_r/linear_opt_3/en.py create mode 100644 prolog/problems/clp_r/max_sum_2/common.py create mode 100644 prolog/problems/clp_r/max_sum_2/en.py create mode 100644 prolog/problems/clp_r/megabytes_2/common.py create mode 100644 prolog/problems/clp_r/megabytes_2/en.py create mode 100644 prolog/problems/clp_r/turkey_3/common.py create mode 100644 prolog/problems/clp_r/turkey_3/en.py create mode 100644 prolog/problems/dcg/ab_2/common.py create mode 100644 prolog/problems/dcg/ab_2/en.py create mode 100644 prolog/problems/dcg/digit_2/common.py create mode 100644 prolog/problems/dcg/digit_2/en.py create mode 100644 prolog/problems/dcg/expr_2/common.py create mode 100644 prolog/problems/dcg/expr_2/en.py create mode 100644 prolog/problems/dcg/expr_3/common.py create mode 100644 prolog/problems/dcg/expr_3/en.py create mode 100644 prolog/problems/dcg/flower_2/common.py create mode 100644 prolog/problems/dcg/flower_2/en.py create mode 100644 prolog/problems/dcg/number_2/common.py create mode 100644 prolog/problems/dcg/number_2/en.py create mode 100644 prolog/problems/dcg/number_3/common.py create mode 100644 prolog/problems/dcg/number_3/en.py create mode 100644 prolog/problems/dcg/number_proper_2/common.py create mode 100644 prolog/problems/dcg/number_proper_2/en.py create mode 100644 prolog/problems/dcg/paren_2/common.py create mode 100644 prolog/problems/dcg/paren_2/en.py create mode 100644 prolog/problems/dcg/paren_3/common.py create mode 100644 prolog/problems/dcg/paren_3/en.py create mode 100644 prolog/problems/denotational_semantics/algol_3/common.py create mode 100644 prolog/problems/denotational_semantics/algol_3/en.py create mode 100644 prolog/problems/denotational_semantics/algol_for_3/common.py create mode 100644 prolog/problems/denotational_semantics/algol_for_3/en.py create mode 100644 prolog/problems/denotational_semantics/algol_if_3/common.py create mode 100644 prolog/problems/denotational_semantics/algol_if_3/en.py create mode 100644 prolog/problems/denotational_semantics/prog_8puzzle_2/common.py create mode 100644 prolog/problems/denotational_semantics/prog_8puzzle_2/en.py create mode 100644 prolog/problems/denotational_semantics/prog_8puzzle_3/common.py create mode 100644 prolog/problems/denotational_semantics/prog_8puzzle_3/en.py create mode 100644 prolog/problems/denotational_semantics/prog_listswap_2/common.py create mode 100644 prolog/problems/denotational_semantics/prog_listswap_2/en.py create mode 100644 prolog/problems/denotational_semantics/prog_listswap_3/common.py create mode 100644 prolog/problems/denotational_semantics/prog_listswap_3/en.py create mode 100644 prolog/problems/family_relations/ancestor_2/common.py create mode 100644 prolog/problems/family_relations/ancestor_2/en.py create mode 100644 prolog/problems/family_relations/aunt_2/common.py create mode 100644 prolog/problems/family_relations/aunt_2/en.py create mode 100644 prolog/problems/family_relations/brother_2/common.py create mode 100644 prolog/problems/family_relations/brother_2/en.py create mode 100644 prolog/problems/family_relations/connected_3/common.py create mode 100644 prolog/problems/family_relations/connected_3/en.py create mode 100644 prolog/problems/family_relations/cousin_2/common.py create mode 100644 prolog/problems/family_relations/cousin_2/en.py create mode 100644 prolog/problems/family_relations/descendant_2/common.py create mode 100644 prolog/problems/family_relations/descendant_2/en.py create mode 100644 prolog/problems/family_relations/grandparent_2/common.py create mode 100644 prolog/problems/family_relations/grandparent_2/en.py create mode 100644 prolog/problems/family_relations/mother_2/common.py create mode 100644 prolog/problems/family_relations/mother_2/en.py create mode 100644 prolog/problems/family_relations/sister_2/common.py create mode 100644 prolog/problems/family_relations/sister_2/en.py create mode 100644 prolog/problems/license_plates/checklicenseplate_3/common.py create mode 100644 prolog/problems/license_plates/checklicenseplate_3/en.py create mode 100644 prolog/problems/license_plates/firstminus_2/common.py create mode 100644 prolog/problems/license_plates/firstminus_2/en.py create mode 100644 prolog/problems/license_plates/genexp_2/common.py create mode 100644 prolog/problems/license_plates/genexp_2/en.py create mode 100644 prolog/problems/license_plates/getdigits_2/common.py create mode 100644 prolog/problems/license_plates/getdigits_2/en.py create mode 100644 prolog/problems/license_plates/joindigits_2/common.py create mode 100644 prolog/problems/license_plates/joindigits_2/en.py create mode 100644 prolog/problems/lists/conc_3/common.py create mode 100644 prolog/problems/lists/conc_3/en.py create mode 100644 prolog/problems/lists/count_3/common.py create mode 100644 prolog/problems/lists/count_3/en.py create mode 100644 prolog/problems/lists/del_3/common.py create mode 100644 prolog/problems/lists/del_3/en.py create mode 100644 prolog/problems/lists/divide_3/common.py create mode 100644 prolog/problems/lists/divide_3/en.py create mode 100644 prolog/problems/lists/dup_2/common.py create mode 100644 prolog/problems/lists/dup_2/en.py create mode 100644 prolog/problems/lists/evenlen_1_+_oddlen_1/common.py create mode 100644 prolog/problems/lists/evenlen_1_+_oddlen_1/en.py create mode 100644 prolog/problems/lists/insert_3/common.py create mode 100644 prolog/problems/lists/insert_3/en.py create mode 100644 prolog/problems/lists/len_2/common.py create mode 100644 prolog/problems/lists/len_2/en.py create mode 100644 prolog/problems/lists/max_2/common.py create mode 100644 prolog/problems/lists/max_2/en.py create mode 100644 prolog/problems/lists/memb_2/common.py create mode 100644 prolog/problems/lists/memb_2/en.py create mode 100644 prolog/problems/lists/min_2/common.py create mode 100644 prolog/problems/lists/min_2/en.py create mode 100644 prolog/problems/lists/palindrome_1/common.py create mode 100644 prolog/problems/lists/palindrome_1/en.py create mode 100644 prolog/problems/lists/permute_2/common.py create mode 100644 prolog/problems/lists/permute_2/en.py create mode 100644 prolog/problems/lists/rev_2/common.py create mode 100644 prolog/problems/lists/rev_2/en.py create mode 100644 prolog/problems/lists/shiftleft_2/common.py create mode 100644 prolog/problems/lists/shiftleft_2/en.py create mode 100644 prolog/problems/lists/shiftright_2/common.py create mode 100644 prolog/problems/lists/shiftright_2/en.py create mode 100644 prolog/problems/lists/sublist_2/common.py create mode 100644 prolog/problems/lists/sublist_2/en.py create mode 100644 prolog/problems/lists/sum_2/common.py create mode 100644 prolog/problems/lists/sum_2/en.py create mode 100644 prolog/problems/old_exams/pascal_3/common.py create mode 100644 prolog/problems/old_exams/pascal_3/en.py create mode 100644 prolog/problems/other/genlist_4/common.py create mode 100644 prolog/problems/other/genlist_4/en.py create mode 100644 prolog/problems/sets/diff_3/common.py create mode 100644 prolog/problems/sets/diff_3/en.py create mode 100644 prolog/problems/sets/intersect_3/common.py create mode 100644 prolog/problems/sets/intersect_3/en.py create mode 100644 prolog/problems/sets/is_subset_2/common.py create mode 100644 prolog/problems/sets/is_subset_2/en.py create mode 100644 prolog/problems/sets/is_superset_2/common.py create mode 100644 prolog/problems/sets/is_superset_2/en.py create mode 100644 prolog/problems/sets/powerset_2/common.py create mode 100644 prolog/problems/sets/powerset_2/en.py create mode 100644 prolog/problems/sets/subset_2/common.py create mode 100644 prolog/problems/sets/subset_2/en.py create mode 100644 prolog/problems/sets/union_3/common.py create mode 100644 prolog/problems/sets/union_3/en.py create mode 100644 prolog/problems/sorting/is_sorted_1/common.py create mode 100644 prolog/problems/sorting/is_sorted_1/en.py create mode 100644 prolog/problems/sorting/isort_2/common.py create mode 100644 prolog/problems/sorting/isort_2/en.py create mode 100644 prolog/problems/sorting/pivoting_4/common.py create mode 100644 prolog/problems/sorting/pivoting_4/en.py create mode 100644 prolog/problems/sorting/quick_sort_2/common.py create mode 100644 prolog/problems/sorting/quick_sort_2/en.py create mode 100644 prolog/problems/sorting/sins_3/common.py create mode 100644 prolog/problems/sorting/sins_3/en.py create mode 100644 prolog/problems/sorting/slowest_sort_ever_2/common.py create mode 100644 prolog/problems/sorting/slowest_sort_ever_2/en.py create mode 100644 prolog/problems/trees/deletebt_3/common.py create mode 100644 prolog/problems/trees/deletebt_3/en.py create mode 100644 prolog/problems/trees/depthbt_2/common.py create mode 100644 prolog/problems/trees/depthbt_2/en.py create mode 100644 prolog/problems/trees/insertbt_3/common.py create mode 100644 prolog/problems/trees/insertbt_3/en.py create mode 100644 prolog/problems/trees/maxt_2/common.py create mode 100644 prolog/problems/trees/maxt_2/en.py create mode 100644 prolog/problems/trees/memberbt_2/common.py create mode 100644 prolog/problems/trees/memberbt_2/en.py create mode 100644 prolog/problems/trees/membert_2/common.py create mode 100644 prolog/problems/trees/membert_2/en.py create mode 100644 prolog/problems/trees/mirrorbt_2/common.py create mode 100644 prolog/problems/trees/mirrorbt_2/en.py create mode 100644 prolog/problems/trees/numberbt_2/common.py create mode 100644 prolog/problems/trees/numberbt_2/en.py create mode 100644 prolog/problems/trees/tolistbt_2/common.py create mode 100644 prolog/problems/trees/tolistbt_2/en.py diff --git a/prolog/facts/denotational_semantics_aux__predicates.py b/prolog/facts/denotational_semantics_aux__predicates.py new file mode 100644 index 0000000..4bf315b --- /dev/null +++ b/prolog/facts/denotational_semantics_aux__predicates.py @@ -0,0 +1,32 @@ +id = 2 + +name = 'denotational semantics aux. predicates' + +facts = '''\ +findblank(R, Bx) :- + findblank(R, 1, Bx). +findblank([0|_], Bx, Bx) :- !. +findblank([_|T], Cx, Bx) :- + Cx1 is Cx + 1, + findblank(T, Cx1, Bx). + +swap([H1,H2|T],2,[H2,H1|T]). +swap([H|T],C0,[H|NewT]):- + C0 > 2, + C is C0 - 1, + swap(T,C,NewT). + +swap(R, I1, I2, NewR) :- + (I1 < I2, !, + Ix1 = I1, Ix2 = I2 + ; + Ix1 = I2, Ix2 = I1), + Cut1 is Ix1 - 1, + Cut2 is Ix2 - Ix1 - 1, + length(LBef, Cut1), + length(LMid, Cut2), + lists:append(LBef, [E1|RRest], R), + lists:append(LMid, [E2|LAft], RRest), + lists:append(LBef, [E2|RIntermediate], NewR), + lists:append(LMid, [E1|LAft], RIntermediate). +''' diff --git a/prolog/facts/family_relations.py b/prolog/facts/family_relations.py new file mode 100644 index 0000000..6be71fa --- /dev/null +++ b/prolog/facts/family_relations.py @@ -0,0 +1,76 @@ +id = 1 + +name = 'family relations' + +facts = '''\ +parent(tina, william). +parent(thomas, william). +parent(thomas, sally). +parent(thomas, jeffrey). +parent(sally, andrew). +parent(sally, melanie). +parent(andrew, joanne). +parent(jill, joanne). +parent(joanne, steve). +parent(william, vanessa). +parent(william, patricia). +parent(vanessa, susan). +parent(patrick, susan). +parent(patricia, john). +parent(john, michael). +parent(john, michelle). + +parent(frank, george). +parent(estelle, george). +parent(morty, jerry). +parent(helen, jerry). +parent(jerry, anna). +parent(elaine, anna). +parent(elaine, kramer). +parent(george, kramer). + +parent(margaret, nevia). +parent(margaret, alessandro). +parent(ana, aleksander). +parent(aleksandr, aleksander). +parent(nevia, luana). +parent(aleksander, luana). +parent(nevia, daniela). +parent(aleksander, daniela). + +male(william). +male(thomas). +male(jeffrey). +male(andrew). +male(steve). +male(patrick). +male(john). +male(michael). +male(frank). +male(george). +male(morty). +male(jerry). +male(kramer). +male(aleksandr). +male(alessandro). +male(aleksander). + +female(tina). +female(sally). +female(melanie). +female(joanne). +female(jill). +female(vanessa). +female(patricia). +female(susan). +female(michelle). +female(estelle). +female(helen). +female(elaine). +female(anna). +female(margaret). +female(ana). +female(nevia). +female(luana). +female(daniela). +''' diff --git a/prolog/problems/clp_fd/gcd_3/common.py b/prolog/problems/clp_fd/gcd_3/common.py new file mode 100644 index 0000000..8ab99ef --- /dev/null +++ b/prolog/problems/clp_fd/gcd_3/common.py @@ -0,0 +1,16 @@ +id = 149 +group = 'clp_fd' +number = 61 +visible = True +facts = None + +solution = '''\ +cd(X, Y, CD):- + X #= _ * CD, + Y #= _ * CD, + indomain(CD). + +gcd(X, Y, GCD):- + cd(X, Y, GCD), + \+ ( cd(X, Y, CD), CD > GCD ). +''' diff --git a/prolog/problems/clp_fd/gcd_3/en.py b/prolog/problems/clp_fd/gcd_3/en.py new file mode 100644 index 0000000..6d64602 --- /dev/null +++ b/prolog/problems/clp_fd/gcd_3/en.py @@ -0,0 +1,13 @@ +id = 149 +name = 'gcd/3' +slug = 'greatest common divisor' + +description = '''\ +

gcd(X, Y, GCD): GCD is the greatest common divisor of X and Y. Implement this predicate using constraints.

+

Hint: try writing a predicate to find all common divisors of two numbers first.

+
+  ?- gcd(36, 84, GCD).
+    GCD = 12.
+
''' + +hint = {} diff --git a/prolog/problems/clp_fd/magic_1/common.py b/prolog/problems/clp_fd/magic_1/common.py new file mode 100644 index 0000000..0308e1d --- /dev/null +++ b/prolog/problems/clp_fd/magic_1/common.py @@ -0,0 +1,17 @@ +id = 151 +group = 'clp_fd' +number = 60 +visible = True +facts = None + +solution = '''\ +magic(L):- + L = [A1,A2,A3,B1,B2,B3,C1,C2,C3], + L ins 1..9, + all_different(L), + A1+A2+A3 #= B1+B2+B3, + A1+A2+A3 #= C1+C2+C3, + A1+B1+C1 #= A2+B2+C2, + A1+B1+C1 #= A3+B3+C3, + A1+B2+C3 #= A3+B2+C1, + labeling([], L).''' diff --git a/prolog/problems/clp_fd/magic_1/en.py b/prolog/problems/clp_fd/magic_1/en.py new file mode 100644 index 0000000..6fcf252 --- /dev/null +++ b/prolog/problems/clp_fd/magic_1/en.py @@ -0,0 +1,13 @@ +id = 151 +name = 'magic/1' +slug = 'generate a 3x3 magic square' + +description = '''\ +

magic(S): the list S represents a 3×3 magic square (S is a permutation of numbers 1 to 9 - three numbers for each row). The sums of numbers in each row, column and diagonal of a magic squre are equal. Implement this predicate using constraints. Your code should return all possible solutions.

+
+  ?- magic(S).
+    S = [2, 7, 6, 9, 5, 1, 4, 3, 8] ;
+    …
+
''' + +hint = {} diff --git a/prolog/problems/clp_fd/puzzle_abc_3/common.py b/prolog/problems/clp_fd/puzzle_abc_3/common.py new file mode 100644 index 0000000..ee5da6f --- /dev/null +++ b/prolog/problems/clp_fd/puzzle_abc_3/common.py @@ -0,0 +1,14 @@ +id = 153 +group = 'clp_fd' +number = 57 +visible = True +facts = None + +solution = '''\ +puzzle_abc(A, B, C) :- + A #= B + 2, + B #= 2 * C, + A+B+C #= 27, + [A,B,C] ins 0..inf, + labeling([], [A,B,C]). +''' diff --git a/prolog/problems/clp_fd/puzzle_abc_3/en.py b/prolog/problems/clp_fd/puzzle_abc_3/en.py new file mode 100644 index 0000000..5385fe2 --- /dev/null +++ b/prolog/problems/clp_fd/puzzle_abc_3/en.py @@ -0,0 +1,9 @@ +id = 153 +name = 'puzzle_abc/3' +slug = 'age puzzle: abc' + +description = '''\ +

Person A is two years older than B who is twice as old as C. The total of the ages of A, B and C is 27.

+

Write the predicate puzzle_abc(A, B, C) that finds the ages of the three people.

''' + +hint = {} diff --git a/prolog/problems/clp_fd/puzzle_beth_1/common.py b/prolog/problems/clp_fd/puzzle_beth_1/common.py new file mode 100644 index 0000000..a7bcfeb --- /dev/null +++ b/prolog/problems/clp_fd/puzzle_beth_1/common.py @@ -0,0 +1,9 @@ +id = 155 +group = 'clp_fd' +number = 56 +visible = True +facts = None + +solution = '''\ +puzzle_beth(X) :- + X + 2 #= 2*(X-5).''' diff --git a/prolog/problems/clp_fd/puzzle_beth_1/en.py b/prolog/problems/clp_fd/puzzle_beth_1/en.py new file mode 100644 index 0000000..7f4ebc2 --- /dev/null +++ b/prolog/problems/clp_fd/puzzle_beth_1/en.py @@ -0,0 +1,10 @@ +id = 155 +name = 'puzzle_beth/1' +slug = 'age puzzle: beth' + +description = '''\ +

When asked how old she was, Beth replied "In two years I will be twice as old as I was five years ago".

+

Write the predicate puzzle_beth(X) that finds her current age as X.

+''' + +hint = {} diff --git a/prolog/problems/clp_fd/puzzle_momson_2/common.py b/prolog/problems/clp_fd/puzzle_momson_2/common.py new file mode 100644 index 0000000..f96f403 --- /dev/null +++ b/prolog/problems/clp_fd/puzzle_momson_2/common.py @@ -0,0 +1,14 @@ +id = 152 +group = 'clp_fd' +number = 58 +visible = True +facts = None + +solution = '''\ +puzzle_momson(M, S) :- + M #= 10*A + B, + S #= 10*B + A, + [A,B] ins 1..9, + M + S #= 66, + M #> S, + labeling([], [M, S]).''' diff --git a/prolog/problems/clp_fd/puzzle_momson_2/en.py b/prolog/problems/clp_fd/puzzle_momson_2/en.py new file mode 100644 index 0000000..8fa8a1f --- /dev/null +++ b/prolog/problems/clp_fd/puzzle_momson_2/en.py @@ -0,0 +1,9 @@ +id = 152 +name = 'puzzle_momson/2' +slug = 'age puzzle: mom & son' + +description = '''\ +

The sum of ages of mother and her son is 66. The mother's age is the son's age reversed. How old are they?

+

Write the predicate puzzle_momson(M, S) that finds the ages of mother M and son S.

''' + +hint = {} diff --git a/prolog/problems/clp_fd/puzzle_ratio_2/common.py b/prolog/problems/clp_fd/puzzle_ratio_2/common.py new file mode 100644 index 0000000..ba7585b --- /dev/null +++ b/prolog/problems/clp_fd/puzzle_ratio_2/common.py @@ -0,0 +1,17 @@ +id = 154 +group = 'clp_fd' +number = 59 +visible = True +facts = None + +solution = '''\ +puzzle_ratio(A, B) :- + A #= 5*X, + B #= 4*X, + X #> 0, + A+3 #= 11*Y, + B+3 #= 9*Y, + Y #> 0, + A #< 200, + B #< 200, + labeling([], [A, B]).''' diff --git a/prolog/problems/clp_fd/puzzle_ratio_2/en.py b/prolog/problems/clp_fd/puzzle_ratio_2/en.py new file mode 100644 index 0000000..aa5b647 --- /dev/null +++ b/prolog/problems/clp_fd/puzzle_ratio_2/en.py @@ -0,0 +1,9 @@ +id = 154 +name = 'puzzle_ratio/2' +slug = 'age puzzle: ratio' + +description = '''\ +

Present ages of A and B are in the ratio of 5:4. In three years the ratio of their ages will become 11:9.

+

Write the predicate puzzle_ratio(A, B) that finds the ages of A and B.

''' + +hint = {} diff --git a/prolog/problems/clp_fd/tobase_3/common.py b/prolog/problems/clp_fd/tobase_3/common.py new file mode 100644 index 0000000..fb88be0 --- /dev/null +++ b/prolog/problems/clp_fd/tobase_3/common.py @@ -0,0 +1,15 @@ +id = 150 +group = 'clp_fd' +number = 62 +visible = True +facts = None + +solution = '''\ +tobase(0, _, 0) :- !. +tobase(N, B, Nb) :- + B in 2..10, + indomain(B), + N #= N1 * B + Rem, + Rem #>= 0, Rem #< B, + Nb #= Nb1 * 10 + Rem, + tobase(N1, B, Nb1).''' diff --git a/prolog/problems/clp_fd/tobase_3/en.py b/prolog/problems/clp_fd/tobase_3/en.py new file mode 100644 index 0000000..bac8723 --- /dev/null +++ b/prolog/problems/clp_fd/tobase_3/en.py @@ -0,0 +1,16 @@ +id = 150 +name = 'tobase/3' +slug = 'convert numbers from/to the decimal system' + +description = '''\ +

tobase(Number, B, X): given a Number in the decimal system (base 10), X represents the same number in the system with base B. Implement this predicate using constraints. Limit the value of B to the interval [2..10].

+
+  ?- tobase(42, 2, X).
+    X = 101010.
+  ?- tobase(N, 2, 101010).
+    N = 42.
+  ?- tobase(42, B, 101010).
+    B = 2.
+
''' + +hint = {} diff --git a/prolog/problems/clp_r/bounding_box_3/common.py b/prolog/problems/clp_r/bounding_box_3/common.py new file mode 100644 index 0000000..631f017 --- /dev/null +++ b/prolog/problems/clp_r/bounding_box_3/common.py @@ -0,0 +1,14 @@ +id = 157 +group = 'clp_r' +number = 67 +visible = True +facts = None + +solution = '''\ +bounding_box([], Xa/Ya, Xb/Yb) :- + minimize(Xb - Xa), + minimize(Yb - Ya). +bounding_box([X/Y|L], Xa/Ya, Xb/Yb) :- + { Xa =< X, X =< Xb, + Ya =< Y, Y =< Yb }, + bounding_box(L, Xa/Ya, Xb/Yb).''' diff --git a/prolog/problems/clp_r/bounding_box_3/en.py b/prolog/problems/clp_r/bounding_box_3/en.py new file mode 100644 index 0000000..bc800b9 --- /dev/null +++ b/prolog/problems/clp_r/bounding_box_3/en.py @@ -0,0 +1,12 @@ +id = 157 +name = 'bounding_box/3' +slug = 'find the smallest bounding box' + +description = '''\ +

bounding_box(Points, X1/Y1, X2/Y2): X1/Y1 and X2/Y2 are the bottom-left and top-right points defining the smallest bounding box containing all points in the list Points. +

+  ?- bounding_box([4.5/2.3, 3.6/1.2, 6.7/0.1], X1/Y1, X2/Y2).
+    X1 = 3.6, Y1 = 0.1, X2 = 6.7, Y2 = 2.3.
+
''' + +hint = {} diff --git a/prolog/problems/clp_r/center_3/common.py b/prolog/problems/clp_r/center_3/common.py new file mode 100644 index 0000000..1474ef1 --- /dev/null +++ b/prolog/problems/clp_r/center_3/common.py @@ -0,0 +1,20 @@ +id = 158 +group = 'clp_r' +number = 68 +visible = True +facts = None + +solution = '''\ +memb158(X, [X|_]). +memb158(X, [_|T]) :- + memb158(X, T). + +check158([], _, _). +check158([X/Y | T], R, Xc/Yc) :- + { (X-Xc)*(X-Xc) + (Y-Yc)*(Y-Yc) =< R*R }, + check158(T, R, Xc/Yc). + +center(L, R, Xc/Yc) :- + memb158(Xc/Yc, L), + check158(L, R, Xc/Yc). +''' diff --git a/prolog/problems/clp_r/center_3/en.py b/prolog/problems/clp_r/center_3/en.py new file mode 100644 index 0000000..b2b4c8d --- /dev/null +++ b/prolog/problems/clp_r/center_3/en.py @@ -0,0 +1,13 @@ +id = 158 +name = 'center/3' +slug = 'find central points' + +description = '''\ +

center(Points, R, X/Y): X/Y is a point in the list Points that is at most R away from all other points.

+
+  ?- center([1.0/1.1, 2.0/2.1, 3.0/3.1, 4.0/4.1], 4.0, X/Y).
+    X = 2.0, Y = 2.1 ;
+    X = 3.0, Y = 3.1.
+
''' + +hint = {} diff --git a/prolog/problems/clp_r/linear_opt_3/common.py b/prolog/problems/clp_r/linear_opt_3/common.py new file mode 100644 index 0000000..95d7ea2 --- /dev/null +++ b/prolog/problems/clp_r/linear_opt_3/common.py @@ -0,0 +1,12 @@ +id = 159 +group = 'clp_r' +number = 63 +visible = True +facts = None + +solution = '''\ +linear_opt(X, Y, MaxE) :- + { X >= 0, Y >= 0, X =< 5, + X+Y =< 7, X+2*Y >= 4, Y =< X+5, + MaxE = -0.4*X+3.2*Y }, + maximize(MaxE).''' diff --git a/prolog/problems/clp_r/linear_opt_3/en.py b/prolog/problems/clp_r/linear_opt_3/en.py new file mode 100644 index 0000000..645a6c8 --- /dev/null +++ b/prolog/problems/clp_r/linear_opt_3/en.py @@ -0,0 +1,16 @@ +id = 159 +name = 'linear_opt/3' +slug = 'linear optimization' + +description = '''\ +

A set of points in the plane is defined by the inequalities

+ +

The predicate linear_opt(X, Y, MaxE) should return the point (X, Y) where the expression E = -0.4*X + 3.2*Y has the largest value.

''' + +hint = {} diff --git a/prolog/problems/clp_r/max_sum_2/common.py b/prolog/problems/clp_r/max_sum_2/common.py new file mode 100644 index 0000000..ef4ea79 --- /dev/null +++ b/prolog/problems/clp_r/max_sum_2/common.py @@ -0,0 +1,12 @@ +id = 156 +group = 'clp_r' +number = 66 +visible = True +facts = None + +solution = '''\ +max_sum([_], S) :- + minimize(S). +max_sum([A,B|T], S) :- + { S >= A + B }, + max_sum([B|T], S).''' diff --git a/prolog/problems/clp_r/max_sum_2/en.py b/prolog/problems/clp_r/max_sum_2/en.py new file mode 100644 index 0000000..3e8f136 --- /dev/null +++ b/prolog/problems/clp_r/max_sum_2/en.py @@ -0,0 +1,14 @@ +id = 156 +name = 'max_sum/2' +slug = 'find maximal adjacent elements' + +description = '''\ +

max_sum(List, Max): Max is the maximal sum of two adjacent elements in List.

+
+  ?- max_sum([4.5, 3.6, 1.2, 6.7], Max).
+    Max = 8.1.
+  ?- max_sum([1.1, 1.2, -12.3, 8.8], Max).
+    Max = 2.3.
+
''' + +hint = {} diff --git a/prolog/problems/clp_r/megabytes_2/common.py b/prolog/problems/clp_r/megabytes_2/common.py new file mode 100644 index 0000000..e528c3c --- /dev/null +++ b/prolog/problems/clp_r/megabytes_2/common.py @@ -0,0 +1,9 @@ +id = 160 +group = 'clp_r' +number = 65 +visible = True +facts = None + +solution = '''\ +megabytes(SI, IEC) :- + { SI * 2^20 = IEC * 10^6 }.''' diff --git a/prolog/problems/clp_r/megabytes_2/en.py b/prolog/problems/clp_r/megabytes_2/en.py new file mode 100644 index 0000000..6db93c8 --- /dev/null +++ b/prolog/problems/clp_r/megabytes_2/en.py @@ -0,0 +1,14 @@ +id = 160 +name = 'megabytes/2' +slug = 'convert mebibytes to megabytes' + +description = '''\ +

A megabyte is the SI unit meaning 106 bytes, while a mebibyte is the IEC unit meaning 220 bytes. Write the predicate megabytes(SI, IEC) that converts between the two using constraints.

+
+  ?- megabytes(2, IEC).
+    IEC = 1.9073486328125.
+  ?- megabytes(SI, 2).
+    SI = 2.097152.
+
''' + +hint = {} diff --git a/prolog/problems/clp_r/turkey_3/common.py b/prolog/problems/clp_r/turkey_3/common.py new file mode 100644 index 0000000..6a99fc4 --- /dev/null +++ b/prolog/problems/clp_r/turkey_3/common.py @@ -0,0 +1,15 @@ +id = 161 +group = 'clp_r' +number = 64 +visible = True +facts = None + +solution = '''\ +turkey(Brand1, Brand2, Cost) :- + {Cost = Brand1*0.20 + Brand2*0.30, + A = Brand1*5 + Brand2*10, + B = Brand1*4 + Brand2*3, + C = Brand1*0.5, + A >= 90, B >= 48, C >= 1.5}, + minimize(Cost). +''' diff --git a/prolog/problems/clp_r/turkey_3/en.py b/prolog/problems/clp_r/turkey_3/en.py new file mode 100644 index 0000000..3117e35 --- /dev/null +++ b/prolog/problems/clp_r/turkey_3/en.py @@ -0,0 +1,10 @@ +id = 161 +name = 'turkey/3' +slug = 'turkey feed' + +description = '''\ +

The Holiday Meal Turkey Ranch is considering buying two different brands of turkey feed and blending them to provide a good, low-cost diet for its turkeys. Each brand of feed contains, in varying proportions, some or all of the three nutritional ingredients essential for fattening turkeys. Each kilogram of brand 1 contains 5 grams of ingredient A, 4 grams of ingredient B and 0.5 grams of ingredient C. Each kilogram of brand 2 contains 10 grams of ingredient A, 3 grams of ingredient B, but nothing of ingredient C. The brand 1 feed costs 0.20 € a kilogram, while the brand 2 feed costs 0.30 € a kilogram.

+

The minimum monthly requirement per turkey is: 90 grams of ingredient A; 48 grams of ingredient B and 1.5 grams of ingredient C.

+

Formulate an LP model to help the rancher decide how to mix the two brands of turkey feed so that the minimum monthly intake requirement for each nutritional ingredient is met at minimum cost. Write the predicate turkey(Brand1, Brand2, Cost) that returns the amount (in kg) of brands 1 and 2 per turkey per month, and the total cost (in €).

''' + +hint = {} diff --git a/prolog/problems/dcg/ab_2/common.py b/prolog/problems/dcg/ab_2/common.py new file mode 100644 index 0000000..8cce3df --- /dev/null +++ b/prolog/problems/dcg/ab_2/common.py @@ -0,0 +1,11 @@ +id = 162 +group = 'dcg' +number = 69 +visible = True +facts = None + +solution = '''\ +ab --> [a], ab. +ab --> t162. +t162 --> [b], t162. +t162 --> [].''' diff --git a/prolog/problems/dcg/ab_2/en.py b/prolog/problems/dcg/ab_2/en.py new file mode 100644 index 0000000..8025081 --- /dev/null +++ b/prolog/problems/dcg/ab_2/en.py @@ -0,0 +1,10 @@ +id = 162 +name = 'ab/2' +slug = 'a*b*' + +description = '''\ +

Write a DCG with the starting symbol ab for the language ambn, where m, n ≥ 0.

+

Example words: [], a, aab, abbb, bbb.

+

Hint: to generate words of increasing length, use the query conc(Word,_,_), ab(Word,[]).

''' + +hint = {} diff --git a/prolog/problems/dcg/digit_2/common.py b/prolog/problems/dcg/digit_2/common.py new file mode 100644 index 0000000..9b82f15 --- /dev/null +++ b/prolog/problems/dcg/digit_2/common.py @@ -0,0 +1,9 @@ +id = 164 +group = 'dcg' +number = 71 +visible = True +facts = None + +solution = '''\ +digit --> ([0] ; [1] ; [2] ; [3] ; [4] ; [5] ; [6] ; [7] ; [8] ; [9]). +''' diff --git a/prolog/problems/dcg/digit_2/en.py b/prolog/problems/dcg/digit_2/en.py new file mode 100644 index 0000000..200689d --- /dev/null +++ b/prolog/problems/dcg/digit_2/en.py @@ -0,0 +1,8 @@ +id = 164 +name = 'digit/2' +slug = 'a decimal digit' + +description = '''\ +

Write a DCG with the starting symbol digit for the language defined by the set of words {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}.

''' + +hint = {} diff --git a/prolog/problems/dcg/expr_2/common.py b/prolog/problems/dcg/expr_2/common.py new file mode 100644 index 0000000..49059f2 --- /dev/null +++ b/prolog/problems/dcg/expr_2/common.py @@ -0,0 +1,23 @@ +id = 170 +group = 'dcg' +number = 77 +visible = False +facts = None + +solution = '''\ +expr --> term170, addterm170. +addterm170 --> []. +addterm170 --> [+], expr. +term170 --> factor170, multfactor170. +multfactor170 --> []. +multfactor170 --> [*], term170. +factor170 --> num170. +factor170 --> ['('], expr, [')']. + +num170 --> digit170. +num170 --> nzdigit170, num_next170. +num_next170 --> digit170. +num_next170 --> digit170, num_next170. +digit170 --> ([0] ; [1] ; [2] ; [3] ; [4] ; [5] ; [6] ; [7] ; [8] ; [9]). +nzdigit170 --> ([1] ; [2] ; [3] ; [4] ; [5] ; [6] ; [7] ; [8] ; [9]). +''' diff --git a/prolog/problems/dcg/expr_2/en.py b/prolog/problems/dcg/expr_2/en.py new file mode 100644 index 0000000..9b30551 --- /dev/null +++ b/prolog/problems/dcg/expr_2/en.py @@ -0,0 +1,10 @@ +id = 170 +name = 'expr/2' +slug = 'arithmetic expressions' + +description = '''\ +

Write a DCG with the starting symbol expr for the language of arithmetic expressions consisting of numbers (without leading zeros), addition and multiplication. Subexpressions can be grouped using parentheses.

+

Example words: (1+2)*3, 42*8*3, (2+1)*(3+4).

+''' + +hint = {} diff --git a/prolog/problems/dcg/expr_3/common.py b/prolog/problems/dcg/expr_3/common.py new file mode 100644 index 0000000..daa5b31 --- /dev/null +++ b/prolog/problems/dcg/expr_3/common.py @@ -0,0 +1,24 @@ +id = 171 +group = 'dcg' +number = 78 +visible = False +facts = None + +solution = '''\ +expr(N) --> term171(N). +expr(N) --> term171(N1), [+], expr(N2), {N is N1 + N2}. + +term171(N) --> factor171(N). +term171(N) --> factor171(N1), [*], term171(N2), {N is N1 * N2}. + +factor171(N) --> number171(N). +factor171(N) --> ['('], expr(N), [')']. + +memb171(X, [X|_]). +memb171(X, [_|T]) :- + memb171(X, T). + +digit171(N) --> [N], { memb171(N, [0,1,2,3,4,5,6,7,8,9]) }. +number171(N) --> digit171(N). +number171(N) --> number171(N1), digit171(D), { N is 10*N1 + D }. +''' diff --git a/prolog/problems/dcg/expr_3/en.py b/prolog/problems/dcg/expr_3/en.py new file mode 100644 index 0000000..3f91977 --- /dev/null +++ b/prolog/problems/dcg/expr_3/en.py @@ -0,0 +1,14 @@ +id = 171 +name = 'expr/3' +slug = 'arithmetic expressions with meaning' + +description = '''\ +

Write a DCG with the starting symbol expr for the language of arithmetic expressions consisting of numbers (without leading zeros), addition and multiplication. Subexpressions can be grouped using parentheses. The meaning of a word in this language is the numeric value of the represented arithmetic expression.

+

Example words: (1+2)*3, 42*8*3, (2+1)*(3+4).

+
+  ?- expr(N, ['(',2,'+',1,')','*','(',3,'+',4,')'], []).  % (2+1)*(3+4) = 21
+    N = 21.
+
+''' + +hint = {} diff --git a/prolog/problems/dcg/flower_2/common.py b/prolog/problems/dcg/flower_2/common.py new file mode 100644 index 0000000..d380722 --- /dev/null +++ b/prolog/problems/dcg/flower_2/common.py @@ -0,0 +1,13 @@ +id = 163 +group = 'dcg' +number = 70 +visible = True +facts = None + +solution = '''\ +flower --> iflower163. +flower --> [+], flower, [+]. + +iflower163 --> [-]. +iflower163 --> [-], iflower163. +''' diff --git a/prolog/problems/dcg/flower_2/en.py b/prolog/problems/dcg/flower_2/en.py new file mode 100644 index 0000000..85d1e73 --- /dev/null +++ b/prolog/problems/dcg/flower_2/en.py @@ -0,0 +1,10 @@ +id = 163 +name = 'flower/2' +slug = 'words like +++--+++' + +description = '''\ +

Write a DCG with the starting symbol flower for the language +n-m+n, where m > 0 and n ≥ 0.

+

Example words: -, ++-++, +---+.

+''' + +hint = {} diff --git a/prolog/problems/dcg/number_2/common.py b/prolog/problems/dcg/number_2/common.py new file mode 100644 index 0000000..e248891 --- /dev/null +++ b/prolog/problems/dcg/number_2/common.py @@ -0,0 +1,12 @@ +id = 165 +group = 'dcg' +number = 72 +visible = True +facts = None + +solution = '''\ +digit165 --> ([0] ; [1] ; [2] ; [3] ; [4] ; [5] ; [6] ; [7] ; [8] ; [9]). + +number --> digit165. +number --> digit165, number. +''' diff --git a/prolog/problems/dcg/number_2/en.py b/prolog/problems/dcg/number_2/en.py new file mode 100644 index 0000000..6a3d33e --- /dev/null +++ b/prolog/problems/dcg/number_2/en.py @@ -0,0 +1,9 @@ +id = 165 +name = 'number/2' +slug = 'numbers with potential leading zeros' + +description = '''\ +

Write a DCG with the starting symbol number for the language of non-negative integers. The numbers may include leading zeros.

+

Example words: 123, 54, 0122, 0001221, 0.

''' + +hint = {} diff --git a/prolog/problems/dcg/number_3/common.py b/prolog/problems/dcg/number_3/common.py new file mode 100644 index 0000000..cc4bde7 --- /dev/null +++ b/prolog/problems/dcg/number_3/common.py @@ -0,0 +1,30 @@ +id = 167 +group = 'dcg' +number = 74 +visible = True +facts = None + +solution = '''\ +number(Num) --> dig167(N), { l2n167(N,Num) }. +number(Num) --> nonzero167([N]), numb_next167(N1), { l2n167([N|N1],Num) }. + +zero167([0]) --> [0]. +nonzero167([N]) --> [N], {memb167(N, [1,2,3,4,5,6,7,8,9])}. + +dig167(N) --> zero167(N). +dig167(N) --> nonzero167(N). +numb_next167(N) --> dig167(N). +numb_next167([N|N1]) --> dig167([N]), numb_next167(N1). + +memb167(X, [X|_]). +memb167(X, [_|T]) :- + memb167(X, T). + +l2n167(L, N) :- + l2n167(L, 0, N). +l2n167([N], S, R) :- + R is S*10+N. +l2n167([H|T], S, N) :- + S1 is S*10+H, + l2n167(T, S1, N). +''' diff --git a/prolog/problems/dcg/number_3/en.py b/prolog/problems/dcg/number_3/en.py new file mode 100644 index 0000000..a7a22fa --- /dev/null +++ b/prolog/problems/dcg/number_3/en.py @@ -0,0 +1,13 @@ +id = 167 +name = 'number/3' +slug = 'numbers with meaning' + +description = '''\ +

Write a DCG with the starting symbol number for the language of non-negative integers. The numbers may contain leading zeros. The meaning of a word in this language is the numeric value of the represented number.

+
+  ?- number(N, [1,2,3,4], []).
+    N = 1234.
+
+''' + +hint = {} diff --git a/prolog/problems/dcg/number_proper_2/common.py b/prolog/problems/dcg/number_proper_2/common.py new file mode 100644 index 0000000..fdcc494 --- /dev/null +++ b/prolog/problems/dcg/number_proper_2/common.py @@ -0,0 +1,16 @@ +id = 166 +group = 'dcg' +number = 73 +visible = True +facts = None + +solution = '''\ +number_proper --> digit166. +number_proper --> nzdigit166, num_next166. + +num_next166 --> digit166. +num_next166 --> digit166, num_next166. + +digit166 --> ([0] ; [1] ; [2] ; [3] ; [4] ; [5] ; [6] ; [7] ; [8] ; [9]). +nzdigit166 --> ([1] ; [2] ; [3] ; [4] ; [5] ; [6] ; [7] ; [8] ; [9]). +''' diff --git a/prolog/problems/dcg/number_proper_2/en.py b/prolog/problems/dcg/number_proper_2/en.py new file mode 100644 index 0000000..37ad864 --- /dev/null +++ b/prolog/problems/dcg/number_proper_2/en.py @@ -0,0 +1,9 @@ +id = 166 +name = 'number_proper/2' +slug = 'numbers without leading zeros' + +description = '''\ +

Write a DCG with the starting symbol number_proper for the language of non-negative integers. The numbers should not contain leading zeros.

+

Example words: 123, 54, 122, 1221, 0.

''' + +hint = {} diff --git a/prolog/problems/dcg/paren_2/common.py b/prolog/problems/dcg/paren_2/common.py new file mode 100644 index 0000000..ce5ec87 --- /dev/null +++ b/prolog/problems/dcg/paren_2/common.py @@ -0,0 +1,10 @@ +id = 168 +group = 'dcg' +number = 75 +visible = True +facts = None + +solution = '''\ +paren --> []. +paren --> ['('], paren, [')'], paren. +''' diff --git a/prolog/problems/dcg/paren_2/en.py b/prolog/problems/dcg/paren_2/en.py new file mode 100644 index 0000000..a4ab666 --- /dev/null +++ b/prolog/problems/dcg/paren_2/en.py @@ -0,0 +1,10 @@ +id = 168 +name = 'paren/2' +slug = 'properly nested parens' + +description = '''\ +

Write a DCG with the starting symbol paren for the language of properly nested sequences of parentheses. The terminal symbols in the grammar should be written like this: ['('] and [')'].

+

Example words: (), (()), ()(()), (()())().

+

Example non-words: )(, (((), )).

''' + +hint = {} diff --git a/prolog/problems/dcg/paren_3/common.py b/prolog/problems/dcg/paren_3/common.py new file mode 100644 index 0000000..cf7c439 --- /dev/null +++ b/prolog/problems/dcg/paren_3/common.py @@ -0,0 +1,10 @@ +id = 169 +group = 'dcg' +number = 76 +visible = True +facts = None + +solution = '''\ +paren(0) --> []. +paren(D) --> ['('], paren(D1), [')'], paren(D2), { D1 >= D2, D is D1 + 1 ; D1 < D2 , D is D2 }. +''' diff --git a/prolog/problems/dcg/paren_3/en.py b/prolog/problems/dcg/paren_3/en.py new file mode 100644 index 0000000..f4d4c3b --- /dev/null +++ b/prolog/problems/dcg/paren_3/en.py @@ -0,0 +1,13 @@ +id = 169 +name = 'paren/3' +slug = 'properly nested parens with meaning' + +description = '''\ +

Write a DCG with the starting symbol paren for the language of properly nested sequences of parentheses. The meaning of a word in this language is the maximum depth of the nested parentheses.

+
+  ?- paren(D, ['(','(',')',')','(',')'], []).  % (())()
+    D = 2.
+
+''' + +hint = {} diff --git a/prolog/problems/denotational_semantics/algol_3/common.py b/prolog/problems/denotational_semantics/algol_3/common.py new file mode 100644 index 0000000..fe6618d --- /dev/null +++ b/prolog/problems/denotational_semantics/algol_3/common.py @@ -0,0 +1,79 @@ +id = 176 +group = 'denotational_semantics' +number = 83 +visible = True +facts = None + +solution = '''\ +algol(fun(S0,S,apply176([printout=[]|S0],S,Minstructs))) --> + [begin], instructs176(Minstructs), [end]. + +instructs176(Minstr) --> instr176(Minstr). +instructs176(fun(S0,S, + (apply176(S0,S1,Minstr), + apply176(S1,S,Minstructs)))) + --> + instr176(Minstr), instructs176(Minstructs). + +instr176(Massign) --> assign176(Massign). +instr176(fun(S0,[printout = L1|S1], + (memb(X = V,S0), + del(printout = L0,S0,S1), + conc(L0,[V],L1)))) + --> + [print(X)]. +instr176(fun(S0,S, + loop176(S0,Mcond,Minstructs,S))) + --> + [while], cond176(Mcond), [do,begin], instructs176(Minstructs), [end]. + +assign176(fun(S0,[X = Value|S1], + (apply176(S0,Value,Mexpr), + del(X = _,S0,S1)))) + --> + var176(X), [:=], expr176(Mexpr). + +cond176( fun( S, TruthVal, + (apply176(S,Val1,ME1), + apply176(S,Val2,ME2), + (Val1 < Val2,!,TruthVal = true ; TruthVal = false)))) + --> + expr176(ME1), [<], expr176(ME2). + +var176(X) --> [X], {atom(X)}. + +expr176(fun(S,Value,eval(Expr,S,Value))) --> + [Expr]. + +apply176(In, Out, fun(In, Out, Goals)) :- + call(Goals). + +loop176( State0, Mcond, _, State0) :- + apply176( State0, false, Mcond), !. +loop176( S0, Mcond, MBody, S) :- + copy_term( MBody, MBodyCopy), + apply176( S0, S1, MBody), + loop176( S1, Mcond, MBodyCopy, S). + +eval176( N, _, N) :- + number176( N), !. +eval176( X, State, Val) :- % A program variable + atom( X), !, + memb( X = Val, State). +eval176( E1 + E2, State, Val) :- !, + eval176( E1, State, V1), + eval176( E2, State, V2), + Val is V1 + V2. +eval176( E1 - E2, State, Val) :- !, + eval176( E1, State, V1), + eval176( E2, State, V2), + Val is V1 - V2. +eval176( E1 * E2, State, Val) :- !, + eval176( E1, State, V1), + eval176( E2, State, V2), + Val is V1 * V2. +eval176( E1 / E2, State, Val) :- !, + eval176( E1, State, V1), + eval176( E2, State, V2), + Val is V1 / V2. +''' diff --git a/prolog/problems/denotational_semantics/algol_3/en.py b/prolog/problems/denotational_semantics/algol_3/en.py new file mode 100644 index 0000000..4b46b11 --- /dev/null +++ b/prolog/problems/denotational_semantics/algol_3/en.py @@ -0,0 +1,33 @@ +id = 176 +name = 'algol/3' +slug = 'interpreter for mini-algol' + +description = '''\ +

A DCG for mini-algol.

+
+  % apply a function to a starting state
+  ?- apply([a=2], Out, fun(_In, Out, eval(a+3, _In, Out))).
+    Out = 5.
+
+  % a := a+b
+  % b := a-b
+  % a := a-b
+  ?- _Program = [begin,a,:=,a+b,b,:=,a-b,a,:=,a-b,end],
+      algol(_F, _Program, []),
+      apply([a=3,b=5], Output, _F).
+    Output = [a=5,b=3,printout=[]].
+
+  % a := 0
+  % while a < 10 do
+  % begin
+  %   print(a)
+  %   a := a+1
+  % end
+  ?- _Program = [begin,a,:=,0,while,a,<,10,do,begin,print(a),a,:=,a+1,end,end],
+      algol(_F, _Program, []),
+      apply([a=3], Output, _F).
+    Output = [a=10,printout=[0,1,2,3,4,5,6,7,8,9]].
+
+''' + +hint = {} diff --git a/prolog/problems/denotational_semantics/algol_for_3/common.py b/prolog/problems/denotational_semantics/algol_for_3/common.py new file mode 100644 index 0000000..3917aa6 --- /dev/null +++ b/prolog/problems/denotational_semantics/algol_for_3/common.py @@ -0,0 +1,93 @@ +id = 178 +group = 'denotational_semantics' +number = 85 +visible = True +facts = None + +solution = '''\ +algol_for(fun(S0,S,apply178([printout=[]|S0],S,Minstructs))) --> + [begin], instructs178(Minstructs), [end]. + +instructs178(Minstr) --> instr178(Minstr). +instructs178(fun(S0,S, + (apply178(S0,S1,Minstr), + apply178(S1,S,Minstructs)))) + --> + instr178(Minstr), instructs178(Minstructs). + +instr178(Massign) --> assign178(Massign). +instr178(fun(S0,[printout = L1|S1], + (memb(X = V,S0), + del(printout = L0,S0,S1), + conc(L0,[V],L1)))) + --> + [print(X)]. +instr178(fun(S0,S, + loop178(S0,Mcond,Minstructs,S))) + --> + [while], cond178(Mcond), [do,begin], instructs178(Minstructs), [end]. +instr178(fun(S0, S, + (apply178(S0, S1, Minit), + for178(S1, Mcond, Mstep, Mbody, S)))) + --> + [for], assign178(Minit), [&], cond178(Mcond), [&], assign178(Mstep), [do, begin], instructs178(Mbody), [end]. + +assign178(fun(S0,[X = Value|S1], + (apply178(S0,Value,Mexpr), + del(X = _,S0,S1)))) + --> + var178(X), [:=], expr178(Mexpr). + +cond178( fun( S, TruthVal, + (apply178(S,Val1,ME1), + apply178(S,Val2,ME2), + (Val1 < Val2,!,TruthVal = true ; TruthVal = false)))) + --> + expr178(ME1), [<], expr178(ME2). + +var178(X) --> [X], {atom(X)}. + +expr178(fun(S,Value,eval(Expr,S,Value))) --> + [Expr]. + +apply178(In, Out, fun(In, Out, Goals)) :- + call(Goals). + +loop178( State0, Mcond, _, State0) :- + apply178( State0, false, Mcond), !. +loop178( S0, Mcond, MBody, S) :- + copy_term( MBody, MBodyCopy), + apply178( S0, S1, MBody), + loop178( S1, Mcond, MBodyCopy, S). + +for178(S0, Mcond, _, _, S0) :- + apply178(S0, false, Mcond), !. +for178(S0, Mcond, Mstep, Mbody, S) :- + copy_term(Mbody, Mbody2), + copy_term(Mstep, Mstep2), + apply178(S0, S1, Mbody), + apply178(S1, S2, Mstep), + for178(S2, Mcond, Mstep2, Mbody2, S). + +eval178( N, _, N) :- + number178( N), !. +eval178( X, State, Val) :- % A program variable + atom( X), !, + memb( X = Val, State). +eval178( E1 + E2, State, Val) :- !, + eval178( E1, State, V1), + eval178( E2, State, V2), + Val is V1 + V2. +eval178( E1 - E2, State, Val) :- !, + eval178( E1, State, V1), + eval178( E2, State, V2), + Val is V1 - V2. +eval178( E1 * E2, State, Val) :- !, + eval178( E1, State, V1), + eval178( E2, State, V2), + Val is V1 * V2. +eval178( E1 / E2, State, Val) :- !, + eval178( E1, State, V1), + eval178( E2, State, V2), + Val is V1 / V2. +''' diff --git a/prolog/problems/denotational_semantics/algol_for_3/en.py b/prolog/problems/denotational_semantics/algol_for_3/en.py new file mode 100644 index 0000000..3578b71 --- /dev/null +++ b/prolog/problems/denotational_semantics/algol_for_3/en.py @@ -0,0 +1,19 @@ +id = 178 +name = 'algol_for/3' +slug = 'interpreter for mini-algol with for-statement' + +description = '''\ +

Extend the given DCG for mini-algol to support the for-statement. Example:

+
+  % for a := 0 & a < 5 & a := a + 1 do
+  % begin
+  %   print(a)
+  % end
+  ?- _Program = [begin,for,a,:=,0,&,a,<,5,&,a,:=,a+1,do,begin,print(a),end,end],
+      algol_for(_F, _Program, []),
+      apply([a=2], Output, _F).
+    Output = [a=5,printout=[0,1,2,3,4]].
+
+''' + +hint = {} diff --git a/prolog/problems/denotational_semantics/algol_if_3/common.py b/prolog/problems/denotational_semantics/algol_if_3/common.py new file mode 100644 index 0000000..8ca92bc --- /dev/null +++ b/prolog/problems/denotational_semantics/algol_if_3/common.py @@ -0,0 +1,86 @@ +id = 177 +group = 'denotational_semantics' +number = 84 +visible = True +facts = None + +solution = '''\ +algol_if(fun(S0,S,apply177([printout=[]|S0],S,Minstructs))) --> + [begin], instructs177(Minstructs), [end]. + +instructs177(Minstr) --> instr177(Minstr). +instructs177(fun(S0,S, + (apply177(S0,S1,Minstr), + apply177(S1,S,Minstructs)))) + --> + instr177(Minstr), instructs177(Minstructs). + +instr177(Massign) --> assign177(Massign). +instr177(fun(S0,[printout = L1|S1], + (memb(X = V,S0), + del(printout = L0,S0,S1), + conc(L0,[V],L1)))) + --> + [print(X)]. +instr177(fun(S0,S, + loop177(S0,Mcond,Minstructs,S))) + --> + [while], cond177(Mcond), [do,begin], instructs177(Minstructs), [end]. +instr177(fun(S0, S, + (apply177(S0, true, Mcond), !, + apply177(S0, S, MinstructsA) + ; + apply177(S0, S, MinstructsB)))) + --> + [if], cond177(Mcond), [then], instructs177(MinstructsA), [else], instructs177(MinstructsB), [end]. + +assign177(fun(S0,[X = Value|S1], + (apply177(S0,Value,Mexpr), + del(X = _,S0,S1)))) + --> + var177(X), [:=], expr177(Mexpr). + +cond177( fun( S, TruthVal, + (apply177(S,Val1,ME1), + apply177(S,Val2,ME2), + (Val1 < Val2,!,TruthVal = true ; TruthVal = false)))) + --> + expr177(ME1), [<], expr177(ME2). + +var177(X) --> [X], {atom(X)}. + +expr177(fun(S,Value,eval(Expr,S,Value))) --> + [Expr]. + +apply177(In, Out, fun(In, Out, Goals)) :- + call(Goals). + +loop177( State0, Mcond, _, State0) :- + apply177( State0, false, Mcond), !. +loop177( S0, Mcond, MBody, S) :- + copy_term( MBody, MBodyCopy), + apply177( S0, S1, MBody), + loop177( S1, Mcond, MBodyCopy, S). + +eval177( N, _, N) :- + number177( N), !. +eval177( X, State, Val) :- % A program variable + atom( X), !, + memb( X = Val, State). +eval177( E1 + E2, State, Val) :- !, + eval177( E1, State, V1), + eval177( E2, State, V2), + Val is V1 + V2. +eval177( E1 - E2, State, Val) :- !, + eval177( E1, State, V1), + eval177( E2, State, V2), + Val is V1 - V2. +eval177( E1 * E2, State, Val) :- !, + eval177( E1, State, V1), + eval177( E2, State, V2), + Val is V1 * V2. +eval177( E1 / E2, State, Val) :- !, + eval177( E1, State, V1), + eval177( E2, State, V2), + Val is V1 / V2. +''' diff --git a/prolog/problems/denotational_semantics/algol_if_3/en.py b/prolog/problems/denotational_semantics/algol_if_3/en.py new file mode 100644 index 0000000..6bc0cb8 --- /dev/null +++ b/prolog/problems/denotational_semantics/algol_if_3/en.py @@ -0,0 +1,20 @@ +id = 177 +name = 'algol_if/3' +slug = 'interpreter for mini-algol with if-statement' + +description = '''\ +

Extend the given DCG for mini-algol to support the if-statement. You can assume that both branches are present in every if-statement. Example:

+
+  % if a < b then
+  %   print(a)
+  % else
+  %   print(b)
+  % end
+  ?- _Program = [begin,if,a,<,b,then,print(a),else,print(b),end,end],
+      algol_if(_F, _Program, []),
+      apply([a=3,b=5], Output, _F).
+    Output = [a=3,b=5,printout=[3]].
+
+''' + +hint = {} diff --git a/prolog/problems/denotational_semantics/prog_8puzzle_2/common.py b/prolog/problems/denotational_semantics/prog_8puzzle_2/common.py new file mode 100644 index 0000000..4cc9c9e --- /dev/null +++ b/prolog/problems/denotational_semantics/prog_8puzzle_2/common.py @@ -0,0 +1,17 @@ +id = 172 +group = 'denotational_semantics' +number = 81 +visible = True +facts = None + +solution = '''\ +prog_8puzzle --> [begin], instructs172, [end]. + +instructs172 --> instr172. +instructs172 --> instr172, instructs172. + +instr172 --> [left]. +instr172 --> [right]. +instr172 --> [up]. +instr172 --> [down]. +''' diff --git a/prolog/problems/denotational_semantics/prog_8puzzle_2/en.py b/prolog/problems/denotational_semantics/prog_8puzzle_2/en.py new file mode 100644 index 0000000..eebf07b --- /dev/null +++ b/prolog/problems/denotational_semantics/prog_8puzzle_2/en.py @@ -0,0 +1,10 @@ +id = 172 +name = 'prog_8puzzle/2' +slug = '8-puzzle-solving language' + +description = '''\ +

Write a DCG for solving 8-puzzles. The first symbol in every word is [begin], followed by any sequence of "instruction" symbols from the set {left, right, up, down}, and finally [end]. The starting symbol should be named prog_8puzzle.

+ +

Example words: [begin,left,down,right,end], [begin,down,end].

''' + +hint = {} diff --git a/prolog/problems/denotational_semantics/prog_8puzzle_3/common.py b/prolog/problems/denotational_semantics/prog_8puzzle_3/common.py new file mode 100644 index 0000000..415dc17 --- /dev/null +++ b/prolog/problems/denotational_semantics/prog_8puzzle_3/common.py @@ -0,0 +1,37 @@ +id = 173 +group = 'denotational_semantics' +number = 82 +visible = True +facts = 'denotational_semantics_aux__predicates' + +solution = '''\ +prog_8puzzle(R0 --> R) --> + [begin], + { findblank(R0,C0) }, + instructs173(((R0,C0) --> (R,_C))), + [end]. + +instructs173((R0,C0) --> (R,C)) --> + instr173((R0,C0) --> (R,C)). +instructs173((R0,C0) --> (R,C)) --> + instr173((R0,C0) --> (R1,C1)), instructs173((R1,C1) --> (R,C)). + +instr173((R0,C0) --> (R,C)) --> + [left], {Pos is (C0-1) mod 3, + (Pos>0, C is C0-1, swap(R0,C0,C,R) + ; + Pos=0, C=C0, R=R0)}. +instr173((R0,C0) --> (R,C)) --> + [right], {Pos is (C0-1) mod 3, + (Pos<2, C is C0+1, swap(R0,C0,C,R) + ; + Pos=2, C=C0, R=R0)}. +instr173((R0,C0) --> (R,C)) --> + [up], { (C0>3, C is C0-3, swap(R0,C0,C,R) + ; + C0=<3, C=C0, R=R0)}. +instr173((R0,C0) --> (R,C)) --> + [down], { (C0=<6, C is C0+3, swap(R0,C0,C,R) + ; + C0>6, C=C0, R=R0)}. +''' diff --git a/prolog/problems/denotational_semantics/prog_8puzzle_3/en.py b/prolog/problems/denotational_semantics/prog_8puzzle_3/en.py new file mode 100644 index 0000000..c91b9e3 --- /dev/null +++ b/prolog/problems/denotational_semantics/prog_8puzzle_3/en.py @@ -0,0 +1,19 @@ +id = 173 +name = 'prog_8puzzle/3' +slug = '8-puzzle-solving language with semantics' + +description = '''\ +

Write a DCG for solving 8-puzzles. The syntax for this language should be the same as in the previous exercise: the first symbol in every word is [begin], followed by any sequence of "instruction" symbols from the set {left, right, up, down}, and finally [end]. The starting symbol should be named prog_8puzzle.

+ +

The meaning of a word (program) in this language has the form In-->Out, mapping from input to output states. Each state is a (permuted) list of numbers from 0 to 8, where 0 stands for the empty square and other numbers for the corresponding tiles. The first three numbers in the list correspond to the top row of the 8-puzzle, the next three numbers to the middle row, and the last three numbers to the last row. The meaning of instructions left, right, up and down is to move the blank tile in the given direction.

+ +
+  ?- prog_8puzzle([0,1,2,3,4,5,6,7,8]-->Out, [begin,down,right,end], []).
+    Out = [3,1,2,4,0,5,6,7,8].
+
+ +

Helper predicates (already defined):
+  findblank(List,I) returns the 1-based index I of the element 0 in List
+  swap(List,I,J,NewList) creates NewList by swapping elements I and J in List

''' + +hint = {} diff --git a/prolog/problems/denotational_semantics/prog_listswap_2/common.py b/prolog/problems/denotational_semantics/prog_listswap_2/common.py new file mode 100644 index 0000000..ae1c220 --- /dev/null +++ b/prolog/problems/denotational_semantics/prog_listswap_2/common.py @@ -0,0 +1,16 @@ +id = 175 +group = 'denotational_semantics' +number = 79 +visible = True +facts = None + +solution = '''\ +program --> [begin], instructs175, [end]. + +instructs175 --> instr175. +instructs175 --> instr175, instructs175. + +instr175 --> [left]. +instr175 --> [right]. +instr175 --> [swap]. +''' diff --git a/prolog/problems/denotational_semantics/prog_listswap_2/en.py b/prolog/problems/denotational_semantics/prog_listswap_2/en.py new file mode 100644 index 0000000..4dd0ed5 --- /dev/null +++ b/prolog/problems/denotational_semantics/prog_listswap_2/en.py @@ -0,0 +1,11 @@ +id = 175 +name = 'prog_listswap/2' +slug = 'list-manipulation language' + +description = '''\ +

Write a DCG for manipulating list elements. The first symbol in every word is [begin], followed by any sequence of "instruction" symbols from the set {left, right, swap}, and finally [end]. The starting symbol should be named prog_listswap.

+ +

Example words: [begin,right,swap,end], [begin,right,left,end].

+''' + +hint = {} diff --git a/prolog/problems/denotational_semantics/prog_listswap_3/common.py b/prolog/problems/denotational_semantics/prog_listswap_3/common.py new file mode 100644 index 0000000..110890d --- /dev/null +++ b/prolog/problems/denotational_semantics/prog_listswap_3/common.py @@ -0,0 +1,24 @@ +id = 174 +group = 'denotational_semantics' +number = 80 +visible = True +facts = 'denotational_semantics_aux__predicates' + +solution = '''\ +prog_listswap(In-->Out) --> + [begin], instructs174((In,1)-->(Out,_)), [end]. + +instructs174((R0,C0)-->(R,C)) --> + instr174((R0,C0)-->(R,C)). +instructs174((R0,C0)-->(R,C)) --> + instr174((R0,C0)-->(R1,C1)), + instructs174((R1,C1)-->(R,C)). + +instr174((R0,C0)-->(R0,C)) --> + [left], { C0 > 1, C is C0 - 1 ; C0 =< 1, C is C0 }. +instr174((R0,C0)-->(R0,C)) --> + [right], { length(R0, LenR0), + ( C0 < LenR0, C is C0 + 1 ; C0 >= LenR0, C is C0 ) }. + +instr174((R0,C0)-->(R,C0)) --> + [swap], {swap(R0,C0,R)}.''' diff --git a/prolog/problems/denotational_semantics/prog_listswap_3/en.py b/prolog/problems/denotational_semantics/prog_listswap_3/en.py new file mode 100644 index 0000000..1a7cb79 --- /dev/null +++ b/prolog/problems/denotational_semantics/prog_listswap_3/en.py @@ -0,0 +1,18 @@ +id = 174 +name = 'prog_listswap/3' +slug = 'list-manipulation language with semantics' + +description = '''\ +

Write a DCG for manipulating list elements. The first symbol in every word is [begin], followed by any sequence of "instruction" symbols from the set {left, right, swap}, and finally [end]. The starting symbol should be named prog_listswap.

+ +

The meaning of a word (program) in this language has the form In-->Out, mapping from input to output lists. Besides the list contents, internal states also hold the current cursor position. The left and right instructions move the cursor one step in the given direction, while the swap instruction swaps the element under the cursor with its left neighbor (and fails if cursor is currently pointing to the first element of the list).

+ +
+  ?- prog_listswap([1,2,3,4]-->Out, [begin,right,swap,end], []).
+    Out = [2,1,3,4].
+
+ +

Helper predicate (already defined):
+  swap(List,I,NewList) creates NewList by swapping the Ith element with its left neighbor in List

''' + +hint = {} diff --git a/prolog/problems/family_relations/ancestor_2/common.py b/prolog/problems/family_relations/ancestor_2/common.py new file mode 100644 index 0000000..61472b6 --- /dev/null +++ b/prolog/problems/family_relations/ancestor_2/common.py @@ -0,0 +1,13 @@ +id = 100 +group = 'family_relations' +number = 7 +visible = True +facts = 'family_relations' + +solution = '''\ +ancestor(X, Y) :- + parent(X, Y). +ancestor(X, Y) :- + parent(X, Z), + ancestor(Z, Y). +''' diff --git a/prolog/problems/family_relations/ancestor_2/en.py b/prolog/problems/family_relations/ancestor_2/en.py new file mode 100644 index 0000000..4853e15 --- /dev/null +++ b/prolog/problems/family_relations/ancestor_2/en.py @@ -0,0 +1,14 @@ +id = 100 +name = 'ancestor/2' +slug = 'the ancestor relation' + +description = '''\ +

ancestor(X, Y): X is an ancestor (parent, grandparent,...) of Y.

+
+  ?- ancestor(patricia, X).
+    X = john ;
+    X = michael ;
+    X = michelle.
+
''' + +hint = {} diff --git a/prolog/problems/family_relations/aunt_2/common.py b/prolog/problems/family_relations/aunt_2/common.py new file mode 100644 index 0000000..78e98c5 --- /dev/null +++ b/prolog/problems/family_relations/aunt_2/common.py @@ -0,0 +1,17 @@ +id = 98 +group = 'family_relations' +number = 5 +visible = True +facts = 'family_relations' + +solution = '''\ +sister98(X, Y) :- + parent(P, X), + parent(P, Y), + female(X), + X \== Y. + +aunt(X, Y) :- + sister98(X, Z), + parent(Z, Y). +''' diff --git a/prolog/problems/family_relations/aunt_2/en.py b/prolog/problems/family_relations/aunt_2/en.py new file mode 100644 index 0000000..95780a1 --- /dev/null +++ b/prolog/problems/family_relations/aunt_2/en.py @@ -0,0 +1,13 @@ +id = 98 +name = 'aunt/2' +slug = 'the aunt relation' + +description = '''\ +

aunt(X, Y): X is an aunt of Y.

+
+  ?- aunt(sally, X).
+    X = vanessa ;
+    X = patricia.
+
''' + +hint = {} diff --git a/prolog/problems/family_relations/brother_2/common.py b/prolog/problems/family_relations/brother_2/common.py new file mode 100644 index 0000000..c339644 --- /dev/null +++ b/prolog/problems/family_relations/brother_2/common.py @@ -0,0 +1,13 @@ +id = 97 +group = 'family_relations' +number = 4 +visible = True +facts = 'family_relations' + +solution = '''\ +brother(X, Y) :- + parent(P, X), + parent(P, Y), + male(X), + X \== Y. +''' diff --git a/prolog/problems/family_relations/brother_2/en.py b/prolog/problems/family_relations/brother_2/en.py new file mode 100644 index 0000000..8cae8b8 --- /dev/null +++ b/prolog/problems/family_relations/brother_2/en.py @@ -0,0 +1,13 @@ +id = 97 +name = 'brother/2' +slug = 'the brother relation' + +description = '''\ +

brother(X, Y): X is a brother of Y.

+
+  ?- brother(jeffrey, X).
+    X = william ;
+    X = sally.
+
''' + +hint = {} diff --git a/prolog/problems/family_relations/connected_3/common.py b/prolog/problems/family_relations/connected_3/common.py new file mode 100644 index 0000000..9a68d36 --- /dev/null +++ b/prolog/problems/family_relations/connected_3/common.py @@ -0,0 +1,16 @@ +id = 102 +group = 'family_relations' +number = 9 +visible = True +facts = 'family_relations' + +solution = '''\ +connected(X, X, _). +connected(X, Y, N) :- + N > 0, + N1 is N - 1, + ( parent(X, Z) + ; + parent(Z, X) ), + connected(Z, Y, N1). +''' diff --git a/prolog/problems/family_relations/connected_3/en.py b/prolog/problems/family_relations/connected_3/en.py new file mode 100644 index 0000000..8fe1eed --- /dev/null +++ b/prolog/problems/family_relations/connected_3/en.py @@ -0,0 +1,14 @@ +id = 102 +name = 'connected/3' +slug = 'check if two people are connected in the family tree' + +description = '''\ +

connected(X, Y, N): X and Y are connected with a series of (no more than N) parent/child relations.

+
+  ?- connected(ana, morty, 10).
+    false.
+  ?- connected(ana, margaret, 10).
+    true.
+
''' + +hint = {} diff --git a/prolog/problems/family_relations/cousin_2/common.py b/prolog/problems/family_relations/cousin_2/common.py new file mode 100644 index 0000000..9285a80 --- /dev/null +++ b/prolog/problems/family_relations/cousin_2/common.py @@ -0,0 +1,26 @@ +id = 99 +group = 'family_relations' +number = 6 +visible = True +facts = 'family_relations' + +solution = '''\ +sister99(X, Y) :- + parent(P, X), + parent(P, Y), + female(X), + X \== Y. + +brother99(X, Y) :- + parent(P, X), + parent(P, Y), + male(X), + X \== Y. + +cousin(X, Y) :- + parent(PX, X), + parent(PY, Y), + ( brother99(PX, PY) + ; + sister99(PX, PY) ). +''' diff --git a/prolog/problems/family_relations/cousin_2/en.py b/prolog/problems/family_relations/cousin_2/en.py new file mode 100644 index 0000000..72faa60 --- /dev/null +++ b/prolog/problems/family_relations/cousin_2/en.py @@ -0,0 +1,13 @@ +id = 99 +name = 'cousin/2' +slug = 'the cousin relation' + +description = '''\ +

cousin(X, Y): X is a cousin (male or female) of Y.

+
+  ?- cousin(andrew, X).
+    X = vanessa ;
+    X = patricia.
+
''' + +hint = {} diff --git a/prolog/problems/family_relations/descendant_2/common.py b/prolog/problems/family_relations/descendant_2/common.py new file mode 100644 index 0000000..408b3c7 --- /dev/null +++ b/prolog/problems/family_relations/descendant_2/common.py @@ -0,0 +1,13 @@ +id = 101 +group = 'family_relations' +number = 8 +visible = True +facts = 'family_relations' + +solution = '''\ +descendant(X, Y) :- + parent(Y, X). +descendant(X, Y) :- + parent(Y, Z), + descendant(X, Z). +''' diff --git a/prolog/problems/family_relations/descendant_2/en.py b/prolog/problems/family_relations/descendant_2/en.py new file mode 100644 index 0000000..d4ac794 --- /dev/null +++ b/prolog/problems/family_relations/descendant_2/en.py @@ -0,0 +1,14 @@ +id = 101 +name = 'descendant/2' +slug = 'the descendant relation' + +description = '''\ +

descendant(X, Y): X is a descendant (child, grandchild,...) of Y.

+
+  ?- descendant(patricia, X).
+    X = william ;
+    X = tina ;
+    X = thomas.
+
''' + +hint = {} diff --git a/prolog/problems/family_relations/grandparent_2/common.py b/prolog/problems/family_relations/grandparent_2/common.py new file mode 100644 index 0000000..12b7c0d --- /dev/null +++ b/prolog/problems/family_relations/grandparent_2/common.py @@ -0,0 +1,11 @@ +id = 95 +group = 'family_relations' +number = 2 +visible = True +facts = 'family_relations' + +solution = '''\ +grandparent(X, Y) :- + parent(X, Z), + parent(Z, Y). +''' diff --git a/prolog/problems/family_relations/grandparent_2/en.py b/prolog/problems/family_relations/grandparent_2/en.py new file mode 100644 index 0000000..cdc9cec --- /dev/null +++ b/prolog/problems/family_relations/grandparent_2/en.py @@ -0,0 +1,15 @@ +id = 95 +name = 'grandparent/2' +slug = 'the grandparent relation' + +description = '''\ +

grandparent(P, C): P is a grandparent of C.

+
+  ?- grandparent(tina, X).
+    X = vanessa ;
+    X = patricia.
+  ?- grandparent(tina, vanessa).
+    true.
+
''' + +hint = {} diff --git a/prolog/problems/family_relations/mother_2/common.py b/prolog/problems/family_relations/mother_2/common.py new file mode 100644 index 0000000..6c75823 --- /dev/null +++ b/prolog/problems/family_relations/mother_2/common.py @@ -0,0 +1,11 @@ +id = 94 +group = 'family_relations' +number = 1 +visible = True +facts = 'family_relations' + +solution = '''\ +mother(X, Y) :- + parent(X, Y), + female(X). +''' diff --git a/prolog/problems/family_relations/mother_2/en.py b/prolog/problems/family_relations/mother_2/en.py new file mode 100644 index 0000000..9f1c098 --- /dev/null +++ b/prolog/problems/family_relations/mother_2/en.py @@ -0,0 +1,15 @@ +id = 94 +name = 'mother/2' +slug = 'the mother-child relation' + +description = '''\ +

mother(M, C): M is the mother of C.

+
+  ?- mother(tina, william).
+    true.
+  ?- mother(nevia, X).
+    X = luana ;
+    X = daniela.
+
''' + +hint = {} diff --git a/prolog/problems/family_relations/sister_2/common.py b/prolog/problems/family_relations/sister_2/common.py new file mode 100644 index 0000000..75a2b62 --- /dev/null +++ b/prolog/problems/family_relations/sister_2/common.py @@ -0,0 +1,13 @@ +id = 96 +group = 'family_relations' +number = 3 +visible = True +facts = 'family_relations' + +solution = '''\ +sister(X, Y) :- + parent(P, X), + parent(P, Y), + female(X), + X \== Y. +''' diff --git a/prolog/problems/family_relations/sister_2/en.py b/prolog/problems/family_relations/sister_2/en.py new file mode 100644 index 0000000..140b76f --- /dev/null +++ b/prolog/problems/family_relations/sister_2/en.py @@ -0,0 +1,12 @@ +id = 96 +name = 'sister/2' +slug = 'the sister relation' + +description = '''\ +

sister(X, Y): X is a sister of Y.

+
+  ?- sister(vanessa, X).
+    X = patricia.
+
''' + +hint = {} diff --git a/prolog/problems/license_plates/checklicenseplate_3/common.py b/prolog/problems/license_plates/checklicenseplate_3/common.py new file mode 100644 index 0000000..f926481 --- /dev/null +++ b/prolog/problems/license_plates/checklicenseplate_3/common.py @@ -0,0 +1,52 @@ +id = 148 +group = 'license_plates' +number = 55 +visible = True +facts = None + +solution = '''\ +conc148([], L, L). +conc148([H|T], L2, [H|L]) :- + conc148(T, L2, L). + +memb148(X, [X|_]). +memb148(X, [_|T]) :- + memb148(X, T). + +getdigits148([], []). +getdigits148([X|T], [X|NT]) :- + number(X), !, + getdigits148(T, NT). +getdigits148([_|T], NT) :- + getdigits148(T, NT). + +joindigits148([X], [X]). +joindigits148([X,Y|T], NT) :- + XY is 10*X + Y, + joindigits148([XY|T], NT). +joindigits148([X,Y|T], [X|NT]) :- + joindigits148([Y|T], NT). + +genexp148([Exp], Exp). +genexp148(L, Exp) :- + conc148(Before, [N1,N2|After], L), + memb148(Op, ['+','-','*','/']), + NExp =.. [Op, N1, N2], + conc148(Before, [NExp|After], L1), + genexp148(L1, Exp). + +firstMinus148(L, L). +firstMinus148([X|T], [Y|T]) :- + Y is -X. + +checkLicensePlate(LP, E1, E2) :- + getdigits148(LP, Digs), + conc148(L1, L2, Digs), + joindigits148(L1, N1), + joindigits148(L2, N2), + firstMinus148(N1, MN1), + firstMinus148(N2, MN2), + genexp148(MN1, E1), + genexp148(MN2, E2), + E1 =:= E2. +''' diff --git a/prolog/problems/license_plates/checklicenseplate_3/en.py b/prolog/problems/license_plates/checklicenseplate_3/en.py new file mode 100644 index 0000000..1f3ea94 --- /dev/null +++ b/prolog/problems/license_plates/checklicenseplate_3/en.py @@ -0,0 +1,17 @@ +id = 148 +name = 'checkLicensePlate/3' +slug = 'check if the numbers in a license plate form an equation' + +description = '''\ +

checkLicensePlate(LP, E1, E2): the digits in the list LP can be combined into a valid equation E1 = E2. E1 and E2 are arithmetic expressions, obtained from sublists of Plate by inserting arithmetic operators (+, -, * and /) between elements. An additional unary minus can be inserted before the leftmost number of E1 and E2.

+
+  ?- checkLicensePlate([l,j,l,3,-,2,1,7], E1, E2).
+    E1 = 3,       E2 = 21/7 ;
+    E1 = -3,      E2 = -21/7 ;
+    E1 = 3*2,     E2 = -1+7 ;
+    E1 = -3*2,    E2 = 1-7 ;
+    E1 = 3*2+1,   E2 = 7 ;
+    E1 = -3*2-1,  E2 = -7.
+
''' + +hint = {} diff --git a/prolog/problems/license_plates/firstminus_2/common.py b/prolog/problems/license_plates/firstminus_2/common.py new file mode 100644 index 0000000..9e971f6 --- /dev/null +++ b/prolog/problems/license_plates/firstminus_2/common.py @@ -0,0 +1,11 @@ +id = 147 +group = 'license_plates' +number = 54 +visible = True +facts = None + +solution = '''\ +firstMinus(L, L). +firstMinus([X|T], [Y|T]) :- + Y is -X. +''' diff --git a/prolog/problems/license_plates/firstminus_2/en.py b/prolog/problems/license_plates/firstminus_2/en.py new file mode 100644 index 0000000..9fb8c69 --- /dev/null +++ b/prolog/problems/license_plates/firstminus_2/en.py @@ -0,0 +1,13 @@ +id = 147 +name = 'firstMinus/2' +slug = 'negate the first element in a list of numbers' + +description = '''\ +

firstMinus(L1, L2): the list L2 is the same as L1, except for the first element that may be negated. Your code should return both solutions.

+
+  ?- firstMinus([1,2,3], L).
+    L = [1,2,3] ;
+    L = [-1,2,3].
+
''' + +hint = {} diff --git a/prolog/problems/license_plates/genexp_2/common.py b/prolog/problems/license_plates/genexp_2/common.py new file mode 100644 index 0000000..a91c392 --- /dev/null +++ b/prolog/problems/license_plates/genexp_2/common.py @@ -0,0 +1,23 @@ +id = 146 +group = 'license_plates' +number = 53 +visible = True +facts = None + +solution = '''\ +memb146(X, [X|_]). +memb146(X, [_|T]) :- + memb146(X, T). + +conc146([], L, L). +conc146([H|T], L2, [H|L]) :- + conc146(T, L2, L). + +genexp([Exp], Exp). +genexp(L, Exp) :- + conc146(Before, [N1,N2|After], L), + memb146(Op, ['+','-','*','/']), + NExp =.. [Op, N1, N2], + conc146(Before, [NExp|After], L1), + genexp(L1, Exp). +''' diff --git a/prolog/problems/license_plates/genexp_2/en.py b/prolog/problems/license_plates/genexp_2/en.py new file mode 100644 index 0000000..c5c61fb --- /dev/null +++ b/prolog/problems/license_plates/genexp_2/en.py @@ -0,0 +1,18 @@ +id = 146 +name = 'genexp/2' +slug = 'generate an arithmetic expression from a list' + +description = '''\ +

genexp(L, E): the expression E is obtained from the list L by inserting arithmetic operators between list elements. Your code should generate all valid solutions.

+
+  ?- genexp([1,2,3], L).
+    L = 1+2+3 ;
+    L = 1+2-3 ;
+    L = (1+2)*3 ;
+    L = (1+2)/3 ;
+    L = 1-2+3 ;
+    L = 1-2-3 ;
+    ...
+
''' + +hint = {} diff --git a/prolog/problems/license_plates/getdigits_2/common.py b/prolog/problems/license_plates/getdigits_2/common.py new file mode 100644 index 0000000..8d6e890 --- /dev/null +++ b/prolog/problems/license_plates/getdigits_2/common.py @@ -0,0 +1,14 @@ +id = 144 +group = 'license_plates' +number = 51 +visible = True +facts = None + +solution = '''\ +getdigits([], []). +getdigits([X|T], [X|NT]) :- + number(X), !, + getdigits(T, NT). +getdigits([_|T], NT) :- + getdigits(T, NT). +''' diff --git a/prolog/problems/license_plates/getdigits_2/en.py b/prolog/problems/license_plates/getdigits_2/en.py new file mode 100644 index 0000000..06bfa22 --- /dev/null +++ b/prolog/problems/license_plates/getdigits_2/en.py @@ -0,0 +1,12 @@ +id = 144 +name = 'getdigits/2' +slug = 'remove non-numeric elements from a list' + +description = '''\ +

getdigits(L, DL): the list DL contains the numeric elements of L, in the same order as in the original list.

+
+  ?- getdigits([2,3,e,-,4,b], DL).
+    DL = [2,3,4].
+
''' + +hint = {} diff --git a/prolog/problems/license_plates/joindigits_2/common.py b/prolog/problems/license_plates/joindigits_2/common.py new file mode 100644 index 0000000..dc3e4a5 --- /dev/null +++ b/prolog/problems/license_plates/joindigits_2/common.py @@ -0,0 +1,14 @@ +id = 145 +group = 'license_plates' +number = 52 +visible = True +facts = None + +solution = '''\ +joindigits([X], [X]). +joindigits([X,Y|T], NT) :- + XY is 10*X + Y, + joindigits([XY|T], NT). +joindigits([X,Y|T], [X|NT]) :- + joindigits([Y|T], NT). +''' diff --git a/prolog/problems/license_plates/joindigits_2/en.py b/prolog/problems/license_plates/joindigits_2/en.py new file mode 100644 index 0000000..19623d7 --- /dev/null +++ b/prolog/problems/license_plates/joindigits_2/en.py @@ -0,0 +1,15 @@ +id = 145 +name = 'joindigits/2' +slug = 'join adjacent numbers in a list' + +description = '''\ +

joindigits(L, NL): the list NL is obtained from L by arbitrarily joining neighboring digits. Your code should generate all valid solutions.

+
+  ?- joindigits([3,2,4], NL).
+    NL = [324] ;
+    NL = [32,4] ;
+    NL = [3,24] ;
+    NL = [3,2,4].
+
''' + +hint = {} diff --git a/prolog/problems/lists/conc_3/common.py b/prolog/problems/lists/conc_3/common.py new file mode 100644 index 0000000..29a3919 --- /dev/null +++ b/prolog/problems/lists/conc_3/common.py @@ -0,0 +1,11 @@ +id = 104 +group = 'lists' +number = 12 +visible = True +facts = None + +solution = '''\ +conc([], L, L). +conc([H|T], L2, [H|L]) :- + conc(T, L2, L). +''' diff --git a/prolog/problems/lists/conc_3/en.py b/prolog/problems/lists/conc_3/en.py new file mode 100644 index 0000000..3e127c0 --- /dev/null +++ b/prolog/problems/lists/conc_3/en.py @@ -0,0 +1,14 @@ +id = 104 +name = 'conc/3' +slug = 'concatenate two lists' + +description = '''\ +

conc(L1, L2, L): the list L is obtained by appending the elements of L2 to L1.

+
+  ?- conc([1,2], [3,4], X).
+    X = [1,2,3,4].
+  ?- conc(X, [], [1,2,3]).
+    X = [1,2,3].
+
''' + +hint = {} diff --git a/prolog/problems/lists/count_3/common.py b/prolog/problems/lists/count_3/common.py new file mode 100644 index 0000000..583ad6b --- /dev/null +++ b/prolog/problems/lists/count_3/common.py @@ -0,0 +1,15 @@ +id = 120 +group = 'lists' +number = 27 +visible = True +facts = None + +solution = '''\ +count(_, [], 0). +count(X, [X|T], N) :- + count(X, T, NT), + N is NT + 1. +count(X, [Y|T], NT) :- + X \== Y, + count(X, T, NT). +''' diff --git a/prolog/problems/lists/count_3/en.py b/prolog/problems/lists/count_3/en.py new file mode 100644 index 0000000..799594e --- /dev/null +++ b/prolog/problems/lists/count_3/en.py @@ -0,0 +1,12 @@ +id = 120 +name = 'count/3' +slug = 'find the number of occurrences of an element in list' + +description = '''\ +

count(X, L, N): N is the number of times the element X appears in the list L.

+
+  ?- count(1, [1,2,1,3,1], N).
+    N = 3.
+
''' + +hint = {} diff --git a/prolog/problems/lists/del_3/common.py b/prolog/problems/lists/del_3/common.py new file mode 100644 index 0000000..1e99959 --- /dev/null +++ b/prolog/problems/lists/del_3/common.py @@ -0,0 +1,11 @@ +id = 105 +group = 'lists' +number = 11 +visible = True +facts = None + +solution = '''\ +del(X, [X|T], T). +del(X, [Y|T], [Y|L]) :- + del(X, T, L). +''' diff --git a/prolog/problems/lists/del_3/en.py b/prolog/problems/lists/del_3/en.py new file mode 100644 index 0000000..a0f0cd3 --- /dev/null +++ b/prolog/problems/lists/del_3/en.py @@ -0,0 +1,19 @@ +id = 105 +name = 'del/3' +slug = 'delete an element from list' + +description = '''\ +

del(X, L1, L2): the list L2 is obtained from L1 by deleting element X.

+
+  ?- del(1, [1,2,3], L).
+    L = [2,3].
+  ?- del(2, [1,2,3,2,5], L).
+    L = [1,3,2,5] ;
+    L = [1,2,3,5].
+  ?- del(X, [1,2,3], L).
+    X = 1, L = [2,3] ;
+    X = 2, L = [1,3] ;
+    X = 3, L = [1,2].
+
''' + +hint = {} diff --git a/prolog/problems/lists/divide_3/common.py b/prolog/problems/lists/divide_3/common.py new file mode 100644 index 0000000..901d2f4 --- /dev/null +++ b/prolog/problems/lists/divide_3/common.py @@ -0,0 +1,12 @@ +id = 115 +group = 'lists' +number = 22 +visible = True +facts = None + +solution = '''\ +divide([], [], []). +divide([X], [X], []). +divide([H1,H2|T], [H1|L1], [H2|L2]) :- + divide(T, L1, L2). +''' diff --git a/prolog/problems/lists/divide_3/en.py b/prolog/problems/lists/divide_3/en.py new file mode 100644 index 0000000..1a8d94e --- /dev/null +++ b/prolog/problems/lists/divide_3/en.py @@ -0,0 +1,14 @@ +id = 115 +name = 'divide/3' +slug = 'split a list into parts of roughly equal length' + +description = '''\ +

divide(L, L1, L2): the list L1 contains elements at odd positions in L, and the list L2 contains the elements at even positions in L.

+
+  ?- divide([a,b,c,d,e,f,g], X, Y).
+    X = [a,c,e,g], Y = [b,d,f].
+  ?- divide([a,b,c,d,e,f], X, Y).
+    X = [a,c,e], Y = [b,d,f].
+
''' + +hint = {} diff --git a/prolog/problems/lists/dup_2/common.py b/prolog/problems/lists/dup_2/common.py new file mode 100644 index 0000000..37a0842 --- /dev/null +++ b/prolog/problems/lists/dup_2/common.py @@ -0,0 +1,11 @@ +id = 110 +group = 'lists' +number = 17 +visible = True +facts = None + +solution = '''\ +dup([], []). +dup([H|T], [H,H|TT]) :- + dup(T, TT). +''' diff --git a/prolog/problems/lists/dup_2/en.py b/prolog/problems/lists/dup_2/en.py new file mode 100644 index 0000000..d6aef71 --- /dev/null +++ b/prolog/problems/lists/dup_2/en.py @@ -0,0 +1,14 @@ +id = 110 +name = 'dup/2' +slug = 'duplicate the elements of a list' + +description = '''\ +

dup(L1, L2): the list L2 is obtained from L1 by duplicating every element.

+
+  ?- dup([1,2], X).
+    X = [1,1,2,2].
+  ?- dup([1,2,3], X).
+    X = [1,1,2,2,3,3].
+
''' + +hint = {} diff --git a/prolog/problems/lists/evenlen_1_+_oddlen_1/common.py b/prolog/problems/lists/evenlen_1_+_oddlen_1/common.py new file mode 100644 index 0000000..2735965 --- /dev/null +++ b/prolog/problems/lists/evenlen_1_+_oddlen_1/common.py @@ -0,0 +1,15 @@ +id = 116 +group = 'lists' +number = 23 +visible = True +facts = None + +solution = '''\ +evenlen([]). +evenlen([_,_|T]) :- + evenlen(T). + +oddlen([_]). +oddlen([_,_|T]) :- + oddlen(T). +''' diff --git a/prolog/problems/lists/evenlen_1_+_oddlen_1/en.py b/prolog/problems/lists/evenlen_1_+_oddlen_1/en.py new file mode 100644 index 0000000..d1957d1 --- /dev/null +++ b/prolog/problems/lists/evenlen_1_+_oddlen_1/en.py @@ -0,0 +1,17 @@ +id = 116 +name = 'evenlen/1 + oddlen/1' +slug = 'check if the length of a list is even or odd' + +description = '''\ +

evenlen(L): the list L has an even number of elements.
+oddlen(L): the list L has an odd number of elements.

+
+  ?- oddlen([1,2,3,4,5]).
+    true.
+  ?- oddlen([1,2,3,4]).
+    false.
+  ?- evenlen([1,2,3,4]).
+    true.
+
''' + +hint = {} diff --git a/prolog/problems/lists/insert_3/common.py b/prolog/problems/lists/insert_3/common.py new file mode 100644 index 0000000..fa3a937 --- /dev/null +++ b/prolog/problems/lists/insert_3/common.py @@ -0,0 +1,13 @@ +id = 106 +group = 'lists' +number = 13 +visible = True +facts = None + +solution = '''\ +del106(X, [X|T], T). +del106(X, [Y|T], [Y|L]) :- + del106(X, T, L). +insert(X, List, BigList) :- + del106(X, BigList, List). +''' diff --git a/prolog/problems/lists/insert_3/en.py b/prolog/problems/lists/insert_3/en.py new file mode 100644 index 0000000..a4a1128 --- /dev/null +++ b/prolog/problems/lists/insert_3/en.py @@ -0,0 +1,14 @@ +id = 106 +name = 'insert/3' +slug = 'insert an element into list' + +description = '''\ +

insert(X, L1, L2): the list L2 is obtained from L1 by inserting the element X at arbitrary position.

+
+  ?- insert(1, [2,3], L).
+    L = [1,2,3] ;
+    L = [2,1,3] ;
+    L = [2,3,1].
+
''' + +hint = {} diff --git a/prolog/problems/lists/len_2/common.py b/prolog/problems/lists/len_2/common.py new file mode 100644 index 0000000..62be9cc --- /dev/null +++ b/prolog/problems/lists/len_2/common.py @@ -0,0 +1,12 @@ +id = 119 +group = 'lists' +number = 26 +visible = True +facts = None + +solution = '''\ +len([], 0). +len([_|T], Len) :- + len(T, LenT), + Len is LenT + 1. +''' diff --git a/prolog/problems/lists/len_2/en.py b/prolog/problems/lists/len_2/en.py new file mode 100644 index 0000000..b3e277c --- /dev/null +++ b/prolog/problems/lists/len_2/en.py @@ -0,0 +1,12 @@ +id = 119 +name = 'len/2' +slug = 'find the length of a list' + +description = '''\ +

len(L, Len): Len is the length of the list L.

+
+  ?- len([1,2,3], Len).
+    Len = 3.
+
''' + +hint = {} diff --git a/prolog/problems/lists/max_2/common.py b/prolog/problems/lists/max_2/common.py new file mode 100644 index 0000000..65e5a70 --- /dev/null +++ b/prolog/problems/lists/max_2/common.py @@ -0,0 +1,14 @@ +id = 109 +group = 'lists' +number = 16 +visible = True +facts = None + +solution = '''\ +max([X], X). +max([H|T], Max):- + max(T, Max1), + ( H > Max1, Max is H + ; + H =< Max1, Max is Max1 ). +''' diff --git a/prolog/problems/lists/max_2/en.py b/prolog/problems/lists/max_2/en.py new file mode 100644 index 0000000..dfb4d60 --- /dev/null +++ b/prolog/problems/lists/max_2/en.py @@ -0,0 +1,14 @@ +id = 109 +name = 'max/2' +slug = 'find the largest element in list' + +description = '''\ +

max(L, Max): Max is the largest value in the list L.

+
+  ?- max([5,4,1,6], M).
+    M = 6.
+  ?- max([3,2,2], M).
+    M = 3.
+
''' + +hint = {} diff --git a/prolog/problems/lists/memb_2/common.py b/prolog/problems/lists/memb_2/common.py new file mode 100644 index 0000000..32d9125 --- /dev/null +++ b/prolog/problems/lists/memb_2/common.py @@ -0,0 +1,11 @@ +id = 103 +group = 'lists' +number = 10 +visible = True +facts = None + +solution = '''\ +memb(X, [X|_]). +memb(X, [_|T]) :- + memb(X, T). +''' diff --git a/prolog/problems/lists/memb_2/en.py b/prolog/problems/lists/memb_2/en.py new file mode 100644 index 0000000..fca82b7 --- /dev/null +++ b/prolog/problems/lists/memb_2/en.py @@ -0,0 +1,16 @@ +id = 103 +name = 'memb/2' +slug = 'find elements in list' + +description = '''\ +

memb(M, L): M is an element of list L.

+
+  ?- memb(X, [1,2,3]).
+    X = 1 ;
+    X = 2 ;
+    X = 3.
+  ?- memb(1, [3,2,X]).
+    X = 1.
+
''' + +hint = {} diff --git a/prolog/problems/lists/min_2/common.py b/prolog/problems/lists/min_2/common.py new file mode 100644 index 0000000..7e9a0bc --- /dev/null +++ b/prolog/problems/lists/min_2/common.py @@ -0,0 +1,14 @@ +id = 108 +group = 'lists' +number = 15 +visible = True +facts = None + +solution = '''\ +min([X], X). +min([H|T], Min):- + min(T, Min1), + ( H < Min1, Min is H + ; + H >= Min1, Min is Min1 ). +''' diff --git a/prolog/problems/lists/min_2/en.py b/prolog/problems/lists/min_2/en.py new file mode 100644 index 0000000..a0a8e74 --- /dev/null +++ b/prolog/problems/lists/min_2/en.py @@ -0,0 +1,14 @@ +id = 108 +name = 'min/2' +slug = 'find the smallest element' + +description = '''\ +

min(L, Min): Min is the smallest value in the list L.

+
+  ?- min([5,4,1,6], M).
+    M = 1.
+  ?- min([3,2,2], M).
+    M = 2.
+
''' + +hint = {} diff --git a/prolog/problems/lists/palindrome_1/common.py b/prolog/problems/lists/palindrome_1/common.py new file mode 100644 index 0000000..8929fd9 --- /dev/null +++ b/prolog/problems/lists/palindrome_1/common.py @@ -0,0 +1,17 @@ +id = 112 +group = 'lists' +number = 19 +visible = True +facts = None + +solution = '''\ +conc112([], L, L). +conc112([H|T], L2, [H|L]) :- + conc112(T, L2, L). +rev112([], []). +rev112([H|T], R):- + rev112(T, R1), + conc112(R1, [H], R). +palindrome(L) :- + rev112(L, L). +''' diff --git a/prolog/problems/lists/palindrome_1/en.py b/prolog/problems/lists/palindrome_1/en.py new file mode 100644 index 0000000..c1b8971 --- /dev/null +++ b/prolog/problems/lists/palindrome_1/en.py @@ -0,0 +1,14 @@ +id = 112 +name = 'palindrome/1' +slug = 'check if list is a palindrome' + +description = '''\ +

palindrome(L): the elements of list L are the same when read from the front or back of the list.

+
+  ?- palindrome([1,2,3,2,1]).
+    true.
+  ?- palindrome([1,2,3]).
+    false.
+
''' + +hint = {} diff --git a/prolog/problems/lists/permute_2/common.py b/prolog/problems/lists/permute_2/common.py new file mode 100644 index 0000000..8e0386c --- /dev/null +++ b/prolog/problems/lists/permute_2/common.py @@ -0,0 +1,15 @@ +id = 107 +group = 'lists' +number = 14 +visible = True +facts = None + +solution = '''\ +del107(X, [X|T], T). +del107(X, [Y|T], [Y|L]) :- + del107(X, T, L). +permute([], []). +permute(L, [X|P]) :- + del107(X, L, L1), + permute(L1, P). +''' diff --git a/prolog/problems/lists/permute_2/en.py b/prolog/problems/lists/permute_2/en.py new file mode 100644 index 0000000..8898c83 --- /dev/null +++ b/prolog/problems/lists/permute_2/en.py @@ -0,0 +1,17 @@ +id = 107 +name = 'permute/2' +slug = 'generate permutations of a list' + +description = '''\ +

permute(L1, L2): the list L2 is a permutation of the elements of the list L1.

+
+  ?- permute([1,2,3], L).
+    L = [1,2,3] ;
+    L = [1,3,2] ;
+    L = [2,1,3] ;
+    L = [2,3,1] ;
+    L = [3,1,2] ;
+    L = [3,2,1].
+
''' + +hint = {} diff --git a/prolog/problems/lists/rev_2/common.py b/prolog/problems/lists/rev_2/common.py new file mode 100644 index 0000000..79c5fca --- /dev/null +++ b/prolog/problems/lists/rev_2/common.py @@ -0,0 +1,15 @@ +id = 111 +group = 'lists' +number = 18 +visible = True +facts = None + +solution = '''\ +conc111([], L, L). +conc111([H|T], L2, [H|L]) :- + conc111(T, L2, L). +rev([], []). +rev([H|T], R):- + rev(T, R1), + conc111(R1, [H], R). +''' diff --git a/prolog/problems/lists/rev_2/en.py b/prolog/problems/lists/rev_2/en.py new file mode 100644 index 0000000..9cacc95 --- /dev/null +++ b/prolog/problems/lists/rev_2/en.py @@ -0,0 +1,14 @@ +id = 111 +name = 'rev/2' +slug = 'reverse a list' + +description = '''\ +

rev(L1, L2): the list L2 is obtained from L1 by reversing the order of the elements.

+
+  ?- rev([], X).
+    X = [].
+  ?- rev([1,2,3], X).
+    X = [3,2,1].
+
''' + +hint = {} diff --git a/prolog/problems/lists/shiftleft_2/common.py b/prolog/problems/lists/shiftleft_2/common.py new file mode 100644 index 0000000..a8d56a7 --- /dev/null +++ b/prolog/problems/lists/shiftleft_2/common.py @@ -0,0 +1,13 @@ +id = 113 +group = 'lists' +number = 20 +visible = True +facts = None + +solution = '''\ +conc113([], L, L). +conc113([H|T], L2, [H|L]) :- + conc113(T, L2, L). +shiftleft([H|T], L2) :- + conc113(T, [H], L2). +''' diff --git a/prolog/problems/lists/shiftleft_2/en.py b/prolog/problems/lists/shiftleft_2/en.py new file mode 100644 index 0000000..0f4b807 --- /dev/null +++ b/prolog/problems/lists/shiftleft_2/en.py @@ -0,0 +1,12 @@ +id = 113 +name = 'shiftleft/2' +slug = 'shift a list left' + +description = '''\ +

shiftleft(L1, L2): the list L2 is obtained from L1 by shifting elements to the left by one (circular shift).

+
+  ?- shiftleft([1,2,3,4,5], X).
+    X = [2,3,4,5,1].
+
''' + +hint = {} diff --git a/prolog/problems/lists/shiftright_2/common.py b/prolog/problems/lists/shiftright_2/common.py new file mode 100644 index 0000000..3d5c3a5 --- /dev/null +++ b/prolog/problems/lists/shiftright_2/common.py @@ -0,0 +1,13 @@ +id = 114 +group = 'lists' +number = 21 +visible = True +facts = None + +solution = '''\ +conc114([], L, L). +conc114([H|T], L2, [H|L]) :- + conc114(T, L2, L). +shiftright(L1, [H|T]) :- + conc114(T, [H], L1). +''' diff --git a/prolog/problems/lists/shiftright_2/en.py b/prolog/problems/lists/shiftright_2/en.py new file mode 100644 index 0000000..8e2a57c --- /dev/null +++ b/prolog/problems/lists/shiftright_2/en.py @@ -0,0 +1,12 @@ +id = 114 +name = 'shiftright/2' +slug = 'shift a list right' + +description = '''\ +

shiftright(L1, L2): the list L2 is obtained from L1 by shifting elements to the right by one (circular shift).

+
+  ?- shiftright([1,2,3,4,5], X).
+    X = [5,1,2,3,4].
+
''' + +hint = {} diff --git a/prolog/problems/lists/sublist_2/common.py b/prolog/problems/lists/sublist_2/common.py new file mode 100644 index 0000000..84c0bc8 --- /dev/null +++ b/prolog/problems/lists/sublist_2/common.py @@ -0,0 +1,14 @@ +id = 117 +group = 'lists' +number = 24 +visible = True +facts = None + +solution = '''\ +conc117([], L, L). +conc117([H|T], L2, [H|L]) :- + conc117(T, L2, L). +sublist(L, S) :- + conc117(_, T, L), + conc117(S, _, T). +''' diff --git a/prolog/problems/lists/sublist_2/en.py b/prolog/problems/lists/sublist_2/en.py new file mode 100644 index 0000000..5b6808b --- /dev/null +++ b/prolog/problems/lists/sublist_2/en.py @@ -0,0 +1,18 @@ +id = 117 +name = 'sublist/2' +slug = 'generate sublists of a list' + +description = '''\ +

sublist(L, SL): SL is a continuous sublist of the list L.

+
+  ?- sublist([1,2,3], X).
+    X = [] ;
+    X = [1] ;
+    X = [1,2] ;
+    X = [1,2,3] ;
+    X = [2] ;
+    X = [2,3] ;
+    X = [3].
+
''' + +hint = {} diff --git a/prolog/problems/lists/sum_2/common.py b/prolog/problems/lists/sum_2/common.py new file mode 100644 index 0000000..14b0614 --- /dev/null +++ b/prolog/problems/lists/sum_2/common.py @@ -0,0 +1,12 @@ +id = 118 +group = 'lists' +number = 25 +visible = True +facts = None + +solution = '''\ +sum([], 0). +sum([H|T], Sum) :- + sum(T, SumT), + Sum is SumT + H. +''' diff --git a/prolog/problems/lists/sum_2/en.py b/prolog/problems/lists/sum_2/en.py new file mode 100644 index 0000000..8db0e67 --- /dev/null +++ b/prolog/problems/lists/sum_2/en.py @@ -0,0 +1,12 @@ +id = 118 +name = 'sum/2' +slug = 'find the sum of all elements in list' + +description = '''\ +

sum(L, Sum): Sum is the sum of all elements in the list L.

+
+  ?- sum([1,2,3], Sum).
+    Sum = 6.
+
''' + +hint = {} diff --git a/prolog/problems/old_exams/pascal_3/common.py b/prolog/problems/old_exams/pascal_3/common.py new file mode 100644 index 0000000..7fcb55e --- /dev/null +++ b/prolog/problems/old_exams/pascal_3/common.py @@ -0,0 +1,16 @@ +id = 179 +group = 'old_exams' +number = 86 +visible = False +facts = None + +solution = '''\ +pascal(_, 0, 1) :- !. +pascal(I, I, 1) :- !. +pascal(I, J, N) :- + I1 is I - 1, + J1 is J - 1, + pascal(I1, J, N1), + pascal(I1, J1, N2), + N is N1 + N2. +''' diff --git a/prolog/problems/old_exams/pascal_3/en.py b/prolog/problems/old_exams/pascal_3/en.py new file mode 100644 index 0000000..31a0d47 --- /dev/null +++ b/prolog/problems/old_exams/pascal_3/en.py @@ -0,0 +1,26 @@ +id = 179 +name = 'pascal/3' +slug = 'pascal's triangle' + +description = '''\ +

The first five rows of the Pascal's triangle look like this:

+
+        1
+       1 1
+      1 2 1
+     1 3 3 1
+    1 4 6 4 1
+
+

+Each row begins and ends with 1. Every other element can be obtained as a sum of the two values above it. Write the predicate pascal(I,J,N) that returns the J-th value in the I-th column of the Pascal's triangle. Your solution should return exactly one answer for any input (the I and J arguments start counting with 0; you can assume that 0 ≤ J ≤ I). + +

+  ?- pascal(0, 0, N).
+    N = 1.
+  ?- pascal(2, 1, N).
+    N = 2.
+  ?- pascal(4, 3, N).
+    N = 4.
+
''' + +hint = {} diff --git a/prolog/problems/other/genlist_4/common.py b/prolog/problems/other/genlist_4/common.py new file mode 100644 index 0000000..388c041 --- /dev/null +++ b/prolog/problems/other/genlist_4/common.py @@ -0,0 +1,14 @@ +id = 127 +group = 'other' +number = 34 +visible = False +facts = None + +solution = '''\ +genlist([], 0, _, _). +genlist([H|T], N, Min, Max):- + N > 0, + N1 is N - 1, + genlist(T, N1, Min, Max), + random(Min, Max, H). +''' diff --git a/prolog/problems/other/genlist_4/en.py b/prolog/problems/other/genlist_4/en.py new file mode 100644 index 0000000..488ccf2 --- /dev/null +++ b/prolog/problems/other/genlist_4/en.py @@ -0,0 +1,12 @@ +id = 127 +name = 'genlist/4' +slug = 'generate a list of random numbers' + +description = '''\ +

genlist(L, N, Min, Max): the list L contains N random numbers from the interval [Min,Max).

+
+  ?- genlist(L, 5, 10, 100).
+    L = [12,99,81,24].
+
''' + +hint = {} diff --git a/prolog/problems/sets/diff_3/common.py b/prolog/problems/sets/diff_3/common.py new file mode 100644 index 0000000..76b88ed --- /dev/null +++ b/prolog/problems/sets/diff_3/common.py @@ -0,0 +1,19 @@ +id = 130 +group = 'sets' +number = 37 +visible = True +facts = None + +solution = '''\ +memb130(X, [X|_]). +memb130(X, [_|T]) :- + memb130(X, T). + +diff([], _, []). +diff([H|T], S2, [H|D]) :- + \+ memb130(H, S2), + diff(T, S2, D). +diff([H|T], S2, D) :- + memb130(H, S2), + diff(T, S2, D). +''' diff --git a/prolog/problems/sets/diff_3/en.py b/prolog/problems/sets/diff_3/en.py new file mode 100644 index 0000000..a2fc55d --- /dev/null +++ b/prolog/problems/sets/diff_3/en.py @@ -0,0 +1,12 @@ +id = 130 +name = 'diff/3' +slug = 'find the difference of two sets' + +description = '''\ +

diff(S1, S2, D): the list D contains all elements of S1 that don't appear in S2, with no duplicates.

+
+  ?- diff([2,3,5,1,7,9], [3,7,4,5,6], D).
+    D = [2,1,9].
+
''' + +hint = {} diff --git a/prolog/problems/sets/intersect_3/common.py b/prolog/problems/sets/intersect_3/common.py new file mode 100644 index 0000000..ffa4f89 --- /dev/null +++ b/prolog/problems/sets/intersect_3/common.py @@ -0,0 +1,18 @@ +id = 129 +group = 'sets' +number = 36 +visible = True +facts = None + +solution = '''\ +memb129(X, [X|_]). +memb129(X, [_|T]) :- + memb129(X, T). + +intersect([], _, []). +intersect([H|T], S2, [H|I]) :- + memb129(H, S2), !, + intersect(T, S2, I). +intersect([_|T], S2, I):- + intersect(T, S2, I). +''' diff --git a/prolog/problems/sets/intersect_3/en.py b/prolog/problems/sets/intersect_3/en.py new file mode 100644 index 0000000..b4296e4 --- /dev/null +++ b/prolog/problems/sets/intersect_3/en.py @@ -0,0 +1,12 @@ +id = 129 +name = 'intersect/3' +slug = 'find the intersection of two sets' + +description = '''\ +

intersect(S1, S2, I): the list I contains every element that appears in both S1 and S2, with no duplicates.

+
+  ?- intersect([1,5,6,3,4,2], [8,1,5,9,4,3], I).
+    I = [1,5,3,4].
+
''' + +hint = {} diff --git a/prolog/problems/sets/is_subset_2/common.py b/prolog/problems/sets/is_subset_2/common.py new file mode 100644 index 0000000..5b365ee --- /dev/null +++ b/prolog/problems/sets/is_subset_2/common.py @@ -0,0 +1,16 @@ +id = 132 +group = 'sets' +number = 39 +visible = True +facts = None + +solution = '''\ +memb132(X, [X|_]). +memb132(X, [_|T]) :- + memb132(X, T). + +is_subset([], _). +is_subset([H|T], S2) :- + memb132(H, S2), + is_subset(T, S2). +''' diff --git a/prolog/problems/sets/is_subset_2/en.py b/prolog/problems/sets/is_subset_2/en.py new file mode 100644 index 0000000..ae2c113 --- /dev/null +++ b/prolog/problems/sets/is_subset_2/en.py @@ -0,0 +1,14 @@ +id = 132 +name = 'is_subset/2' +slug = 'check if one set is a subset of another' + +description = '''\ +

is_subset(S1, S2): the set S1 is a subset of S2.

+
+  ?- is_subset([2,1,3,5,0], [3,2,1,4,5,9]).
+    false.
+  ?- is_subset([2,1,3,5], [3,2,1,4,5,9]).
+    true.
+
''' + +hint = {} diff --git a/prolog/problems/sets/is_superset_2/common.py b/prolog/problems/sets/is_superset_2/common.py new file mode 100644 index 0000000..364c513 --- /dev/null +++ b/prolog/problems/sets/is_superset_2/common.py @@ -0,0 +1,16 @@ +id = 131 +group = 'sets' +number = 38 +visible = True +facts = None + +solution = '''\ +memb131(X, [X|_]). +memb131(X, [_|T]) :- + memb131(X, T). + +is_superset(_, []). +is_superset(S1, [H|T]) :- + memb131(H, S1), + is_superset(S1, T). +''' diff --git a/prolog/problems/sets/is_superset_2/en.py b/prolog/problems/sets/is_superset_2/en.py new file mode 100644 index 0000000..218c0c8 --- /dev/null +++ b/prolog/problems/sets/is_superset_2/en.py @@ -0,0 +1,14 @@ +id = 131 +name = 'is_superset/2' +slug = 'check if one set is a superset of the other' + +description = '''\ +

is_superset(S1, S2): the set S1 is a superset (contains all elements) of S2.

+
+  ?- is_superset([3,2,1,4,5,9], [2,1,3,5]).
+    true.
+  ?- is_superset([3,2,1,4,5,9], [2,1,3,5,0]).
+    false.
+
''' + +hint = {} diff --git a/prolog/problems/sets/powerset_2/common.py b/prolog/problems/sets/powerset_2/common.py new file mode 100644 index 0000000..8f3b70e --- /dev/null +++ b/prolog/problems/sets/powerset_2/common.py @@ -0,0 +1,16 @@ +id = 134 +group = 'sets' +number = 41 +visible = True +facts = None + +solution = '''\ +subset134([], []). +subset134([H|T], [H|T1]) :- + subset134(T, T1). +subset134([_|T], T1) :- + subset134(T, T1). + +powerset(Set, PowerSet) :- + findall(S, subset134(Set, S), PowerSet). +''' diff --git a/prolog/problems/sets/powerset_2/en.py b/prolog/problems/sets/powerset_2/en.py new file mode 100644 index 0000000..6471469 --- /dev/null +++ b/prolog/problems/sets/powerset_2/en.py @@ -0,0 +1,12 @@ +id = 134 +name = 'powerset/2' +slug = 'find all subsets of a set' + +description = '''\ +

powerset(Set, Powerset): the list Powerset contains all subsets of Set.

+
+  ?- powerset([1,2,3], L).
+    L = [[1,2,3],[1,2],[1,3],[1],[2,3],[2],[3],[]].
+
''' + +hint = {} diff --git a/prolog/problems/sets/subset_2/common.py b/prolog/problems/sets/subset_2/common.py new file mode 100644 index 0000000..7fbbf49 --- /dev/null +++ b/prolog/problems/sets/subset_2/common.py @@ -0,0 +1,13 @@ +id = 133 +group = 'sets' +number = 40 +visible = True +facts = None + +solution = '''\ +subset([], []). +subset([H|T], [H|T1]) :- + subset(T, T1). +subset([_|T], T1) :- + subset(T, T1). +''' diff --git a/prolog/problems/sets/subset_2/en.py b/prolog/problems/sets/subset_2/en.py new file mode 100644 index 0000000..9d9132b --- /dev/null +++ b/prolog/problems/sets/subset_2/en.py @@ -0,0 +1,19 @@ +id = 133 +name = 'subset/2' +slug = 'generate all subsets of a set' + +description = '''\ +

subset(Set, Subset): the set Subset is a subset of Set. This predicate should generate all valid solutions, one by one.

+
+  ?- subset([1,2,3], SS).
+    SS = [1,2,3] ;
+    SS = [1,2] ;
+    SS = [1,3] ;
+    SS = [1] ;
+    SS = [2,3] ;
+    SS = [2] ;
+    SS = [3] ;
+    SS = [].
+
''' + +hint = {} diff --git a/prolog/problems/sets/union_3/common.py b/prolog/problems/sets/union_3/common.py new file mode 100644 index 0000000..a219673 --- /dev/null +++ b/prolog/problems/sets/union_3/common.py @@ -0,0 +1,19 @@ +id = 128 +group = 'sets' +number = 35 +visible = True +facts = None + +solution = '''\ +memb128(X, [X|_]). +memb128(X, [_|T]) :- + memb128(X, T). + +union([], S2, S2). +union([H|T], S2, [H|U]) :- + \+ memb128(H, S2), + union(T, S2, U). +union([H|T], S2, U) :- + memb128(H, S2), + union(T, S2, U). +''' diff --git a/prolog/problems/sets/union_3/en.py b/prolog/problems/sets/union_3/en.py new file mode 100644 index 0000000..8257415 --- /dev/null +++ b/prolog/problems/sets/union_3/en.py @@ -0,0 +1,12 @@ +id = 128 +name = 'union/3' +slug = 'find the union of two sets' + +description = '''\ +

union(S1, S2, U): the list U contains all elements of S1 and S2, with no duplicates.

+
+  ?- union([1,5,2,3], [3,4,8,2], U).
+    U = [1,5,3,4,8,2].
+
''' + +hint = {} diff --git a/prolog/problems/sorting/is_sorted_1/common.py b/prolog/problems/sorting/is_sorted_1/common.py new file mode 100644 index 0000000..2feb134 --- /dev/null +++ b/prolog/problems/sorting/is_sorted_1/common.py @@ -0,0 +1,13 @@ +id = 121 +group = 'sorting' +number = 28 +visible = True +facts = None + +solution = '''\ +is_sorted([]). +is_sorted([_]). +is_sorted([H1,H2|T]) :- + H1 =< H2, + is_sorted([H2|T]). +''' diff --git a/prolog/problems/sorting/is_sorted_1/en.py b/prolog/problems/sorting/is_sorted_1/en.py new file mode 100644 index 0000000..c4bd025 --- /dev/null +++ b/prolog/problems/sorting/is_sorted_1/en.py @@ -0,0 +1,14 @@ +id = 121 +name = 'is_sorted/1' +slug = 'check if list is sorted' + +description = '''\ +

is_sorted(L): the elements of list L are sorted in non-decreasing order.

+
+  ?- is_sorted([2,3,6,8,12]).
+    true.
+  ?- is_sorted([2,3,1,6,5]).
+    false.
+
''' + +hint = {} diff --git a/prolog/problems/sorting/isort_2/common.py b/prolog/problems/sorting/isort_2/common.py new file mode 100644 index 0000000..0b1aa47 --- /dev/null +++ b/prolog/problems/sorting/isort_2/common.py @@ -0,0 +1,18 @@ +id = 123 +group = 'sorting' +number = 30 +visible = True +facts = None + +solution = '''\ +sins123(X, [], [X]). +sins123(X, [Y|T], [X,Y|T]) :- + X =< Y. +sins123(X, [Y|T], [Y|L]) :- + X > Y, + sins123(X, T, L). +isort([], []). +isort([H|T], SL) :- + isort(T, ST), + sins123(H, ST, SL). +''' diff --git a/prolog/problems/sorting/isort_2/en.py b/prolog/problems/sorting/isort_2/en.py new file mode 100644 index 0000000..3a3dea0 --- /dev/null +++ b/prolog/problems/sorting/isort_2/en.py @@ -0,0 +1,12 @@ +id = 123 +name = 'isort/2' +slug = 'sort a list using insertion sort' + +description = '''\ +

isort(L, SL): the list SL contains the elements of L sorted in non-decreasing order. Use the predicate sins/3 to implement insertion sort.

+
+  ?- isort([2,3,1,5,4], L).
+    L = [1,2,3,4,5].
+
''' + +hint = {} diff --git a/prolog/problems/sorting/pivoting_4/common.py b/prolog/problems/sorting/pivoting_4/common.py new file mode 100644 index 0000000..278f694 --- /dev/null +++ b/prolog/problems/sorting/pivoting_4/common.py @@ -0,0 +1,15 @@ +id = 124 +group = 'sorting' +number = 31 +visible = True +facts = None + +solution = '''\ +pivoting(_, [], [], []). +pivoting(P, [H|T], [H|S], G) :- + H =< P, + pivoting(P, T, S, G). +pivoting(P, [H|T], S, [H|G]) :- + H > P, + pivoting(P, T, S, G). +''' diff --git a/prolog/problems/sorting/pivoting_4/en.py b/prolog/problems/sorting/pivoting_4/en.py new file mode 100644 index 0000000..4a1ab8c --- /dev/null +++ b/prolog/problems/sorting/pivoting_4/en.py @@ -0,0 +1,12 @@ +id = 124 +name = 'pivoting/4' +slug = 'split a list according to the pivot' + +description = '''\ +

pivoting(P, L, S, G): the list S contains the elements of L smaller or equal to P, and the list G contains the elements of L greater than P. The order of elements in S and G should be the same as in L.

+
+  ?- pivoting(4, [1,4,5,8,6,4,2], S, G).
+    S = [1,4,4,2], G = [5,8,6].
+
''' + +hint = {} diff --git a/prolog/problems/sorting/quick_sort_2/common.py b/prolog/problems/sorting/quick_sort_2/common.py new file mode 100644 index 0000000..5eff940 --- /dev/null +++ b/prolog/problems/sorting/quick_sort_2/common.py @@ -0,0 +1,24 @@ +id = 125 +group = 'sorting' +number = 32 +visible = True +facts = None + +solution = '''\ +conc125([], L, L). +conc125([H|T], L2, [H|L]) :- + conc125(T, L2, L). +pivoting125(_, [], [], []). +pivoting125(P, [H|T], [H|S], G) :- + H =< P, + pivoting125(P, T, S, G). +pivoting125(P, [H|T], S, [H|G]) :- + H > P, + pivoting125(P, T, S, G). +quick_sort([], []). +quick_sort([Pivot|T], Sorted) :- + pivoting125(Pivot, T, Smaller, Greater), + quick_sort(Smaller, SortedSmaller), + quick_sort(Greater, SortedGreater), + conc125(SortedSmaller, [Pivot|SortedGreater], Sorted). +''' diff --git a/prolog/problems/sorting/quick_sort_2/en.py b/prolog/problems/sorting/quick_sort_2/en.py new file mode 100644 index 0000000..b0d4ce1 --- /dev/null +++ b/prolog/problems/sorting/quick_sort_2/en.py @@ -0,0 +1,12 @@ +id = 125 +name = 'quick_sort/2' +slug = 'sort a list using quicksort' + +description = '''\ +

quick_sort(L, SL): the list SL contains the elements of L sorted in non-decreasing order. Use the predicate pivoting/4 to implement quicksort.

+
+  ?- quick_sort([2,3,1,5,4], L).
+    L = [1,2,3,4,5].
+
''' + +hint = {} diff --git a/prolog/problems/sorting/sins_3/common.py b/prolog/problems/sorting/sins_3/common.py new file mode 100644 index 0000000..8ebfee4 --- /dev/null +++ b/prolog/problems/sorting/sins_3/common.py @@ -0,0 +1,14 @@ +id = 122 +group = 'sorting' +number = 29 +visible = True +facts = None + +solution = '''\ +sins(X, [], [X]). +sins(X, [Y|T], [X,Y|T]) :- + X =< Y. +sins(X, [Y|T], [Y|L]) :- + X > Y, + sins(X, T, L). +''' diff --git a/prolog/problems/sorting/sins_3/en.py b/prolog/problems/sorting/sins_3/en.py new file mode 100644 index 0000000..684a619 --- /dev/null +++ b/prolog/problems/sorting/sins_3/en.py @@ -0,0 +1,14 @@ +id = 122 +name = 'sins/3' +slug = 'insert an element at correct position into a sorted list' + +description = '''\ +

sins(X, SortedList, NewList): the list NewList is obtained by inserting X into SortedList at the correct position to preserve the non-decreasing order of elements.

+
+  ?- sins(4, [1,2,3,5], L).
+    L = [1,2,3,4,5].
+  ?- sins(3, [1,2,3,4], L).
+    L = [1,2,3,3,4].
+
''' + +hint = {} diff --git a/prolog/problems/sorting/slowest_sort_ever_2/common.py b/prolog/problems/sorting/slowest_sort_ever_2/common.py new file mode 100644 index 0000000..5f4c283 --- /dev/null +++ b/prolog/problems/sorting/slowest_sort_ever_2/common.py @@ -0,0 +1,25 @@ +id = 126 +group = 'sorting' +number = 33 +visible = True +facts = None + +solution = '''\ +del126(X, [X|T], T). +del126(X, [Y|T], [Y|L]) :- + del126(X, T, L). + +permute126([], []). +permute126(L, [X|P]) :- + del126(X, L, L1), + permute126(L1, P). + +is_sorted126([_]). +is_sorted126([H1,H2|T]) :- + H1 =< H2, + is_sorted126([H2|T]). + +slowest_sort_ever(L, S) :- + permute126(L, S), + is_sorted126(S). +''' diff --git a/prolog/problems/sorting/slowest_sort_ever_2/en.py b/prolog/problems/sorting/slowest_sort_ever_2/en.py new file mode 100644 index 0000000..3018ec6 --- /dev/null +++ b/prolog/problems/sorting/slowest_sort_ever_2/en.py @@ -0,0 +1,12 @@ +id = 126 +name = 'slowest_sort_ever/2' +slug = 'sort a list by randomly permuting elements' + +description = '''\ +

slowest_sort_ever(L, SL): the list SL contains the elements of L sorted in non-decreasing order. Average and worst case running time is O(n * n!).

+
+  ?- slowest_sort_ever([2,3,1,5,4], L).
+    L = [1,2,3,4,5].
+
''' + +hint = {} diff --git a/prolog/problems/trees/deletebt_3/common.py b/prolog/problems/trees/deletebt_3/common.py new file mode 100644 index 0000000..76550f6 --- /dev/null +++ b/prolog/problems/trees/deletebt_3/common.py @@ -0,0 +1,17 @@ +id = 137 +group = 'trees' +number = 47 +visible = True +facts = None + +solution = '''\ +deleteBT(X, b(nil, X, nil), nil). +deleteBT(X, b(b(Ls, E, Rs), X, R), b(L, E, R)) :- + deleteBT(E, b(Ls, E, Rs), L). +deleteBT(X, b(L, X, b(Ls, E, Rs)), b(L, E, R)) :- + deleteBT(E, b(Ls, E, Rs), R). +deleteBT(X, b(L, E, R), b(L1, E, R)) :- + deleteBT(X, L, L1). +deleteBT(X, b(L, E, R), b(L, E, R1)) :- + deleteBT(X, R, R1). +''' diff --git a/prolog/problems/trees/deletebt_3/en.py b/prolog/problems/trees/deletebt_3/en.py new file mode 100644 index 0000000..557efaa --- /dev/null +++ b/prolog/problems/trees/deletebt_3/en.py @@ -0,0 +1,14 @@ +id = 137 +name = 'deleteBT/3' +slug = 'delete an element from a binary tree' + +description = '''\ +

deleteBT(X, T, NewT): the binary tree NewT is obtained from T by deleting one occurence of the element X. If X is not a leaf node, the root of one of its subtrees is moved up. Your code should generate all valid solutions.

+
+  ?- deleteBT(1, b(b(b(nil,4,nil),2,b(nil,6,nil)),1,b(nil,3,b(nil,5,nil))), T).
+    T = b(b(nil,4,b(nil,6,nil)),2,b(nil,3,b(nil,5,nil))) ;
+    T = b(b(b(nil,4,nil),6,nil),2,b(nil,3,b(nil,5,nil))) ;
+    T = b(b(b(nil,4,nil),2,b(nil,6,nil)),3,b(nil,5,nil)).
+
''' + +hint = {} diff --git a/prolog/problems/trees/depthbt_2/common.py b/prolog/problems/trees/depthbt_2/common.py new file mode 100644 index 0000000..9e26f21 --- /dev/null +++ b/prolog/problems/trees/depthbt_2/common.py @@ -0,0 +1,17 @@ +id = 140 +group = 'trees' +number = 45 +visible = True +facts = None + +solution = '''\ +depthBT(nil, 0). +depthBT(b(L, _, R), D) :- + depthBT(L, DL), + depthBT(R, DR), + (DL >= DR, + D is DL + 1 + ; + DL < DR, + D is DR + 1). +''' diff --git a/prolog/problems/trees/depthbt_2/en.py b/prolog/problems/trees/depthbt_2/en.py new file mode 100644 index 0000000..37cb3cd --- /dev/null +++ b/prolog/problems/trees/depthbt_2/en.py @@ -0,0 +1,12 @@ +id = 140 +name = 'depthBT/2' +slug = 'find the depth of a binary tree' + +description = '''\ +

depthBT(T, D): D is the depth of the binary tree T.

+
+  ?- depthBT(b(b(b(nil,4,nil),2,b(nil,6,nil)),1,nil), D).
+    D = 3.
+
''' + +hint = {} diff --git a/prolog/problems/trees/insertbt_3/common.py b/prolog/problems/trees/insertbt_3/common.py new file mode 100644 index 0000000..efbfb7d --- /dev/null +++ b/prolog/problems/trees/insertbt_3/common.py @@ -0,0 +1,20 @@ +id = 138 +group = 'trees' +number = 48 +visible = True +facts = None + +solution = '''\ +deleteBT138(X, b(nil, X, nil), nil). +deleteBT138(X, b(b(Ls, E, Rs), X, R), b(L, E, R)) :- + deleteBT138(E, b(Ls, E, Rs), L). +deleteBT138(X, b(L, X, b(Ls, E, Rs)), b(L, E, R)) :- + deleteBT138(E, b(Ls, E, Rs), R). +deleteBT138(X, b(L, E, R), b(L1, E, R)) :- + deleteBT138(X, L, L1). +deleteBT138(X, b(L, E, R), b(L, E, R1)) :- + deleteBT138(X, R, R1). + +insertBT(X, T, NewT) :- + deleteBT138(X, NewT, T). +''' diff --git a/prolog/problems/trees/insertbt_3/en.py b/prolog/problems/trees/insertbt_3/en.py new file mode 100644 index 0000000..202df0a --- /dev/null +++ b/prolog/problems/trees/insertbt_3/en.py @@ -0,0 +1,15 @@ +id = 138 +name = 'insertBT/3' +slug = 'insert an element into a binary tree' + +description = '''\ +

insertBT(X, T, NewT): the binary tree NewT is obtained from T by inserting the element X at a certain position. This is the opposite of the predicate deleteBT/3. Your code should generate all valid solutions.

+
+  ?- insertBT(2, b(nil,1,nil), T).
+    T = b(b(nil,1,nil),2,nil) ;
+    T = b(nil,2,b(nil,1,nil)) ;
+    T = b(b(nil,2,nil),1,nil) ;
+    T = b(nil,1,b(nil,2,nil)).
+
''' + +hint = {} diff --git a/prolog/problems/trees/maxt_2/common.py b/prolog/problems/trees/maxt_2/common.py new file mode 100644 index 0000000..be51d46 --- /dev/null +++ b/prolog/problems/trees/maxt_2/common.py @@ -0,0 +1,25 @@ +id = 143 +group = 'trees' +number = 50 +visible = True +facts = None + +solution = '''\ +max143([X], X). +max143([H|T], Max):- + max143(T, Max1), + ( H > Max1, Max is H + ; + H =< Max1, Max is Max1 ). + +maxT(t(E), E) :- !. +maxT(Tree, Max) :- + Tree =.. [t, E|SubTrees], + getMaxElems(SubTrees, MaxElems), + max143([E|MaxElems], Max). + +getMaxElems([], []). +getMaxElems([SubTree|SubTrees], [MaxElem|MaxElems]) :- + maxT(SubTree, MaxElem), + getMaxElems(SubTrees, MaxElems). +''' diff --git a/prolog/problems/trees/maxt_2/en.py b/prolog/problems/trees/maxt_2/en.py new file mode 100644 index 0000000..3e15b34 --- /dev/null +++ b/prolog/problems/trees/maxt_2/en.py @@ -0,0 +1,12 @@ +id = 143 +name = 'maxT/2' +slug = 'find the greatest element in a tree' + +description = '''\ +

maxT(Tree, Max): Max is the greatest element in the tree Tree.

+
+  ?- maxT(t(1, t(2), t(3)), Max).
+    Max = 3.
+
''' + +hint = {} diff --git a/prolog/problems/trees/memberbt_2/common.py b/prolog/problems/trees/memberbt_2/common.py new file mode 100644 index 0000000..f0ae0bd --- /dev/null +++ b/prolog/problems/trees/memberbt_2/common.py @@ -0,0 +1,13 @@ +id = 135 +group = 'trees' +number = 42 +visible = True +facts = None + +solution = '''\ +memberBT(X, b(_, X, _)). +memberBT(X, b(L, _, _)) :- + memberBT(X, L). +memberBT(X, b(_, _, R)) :- + memberBT(X, R). +''' diff --git a/prolog/problems/trees/memberbt_2/en.py b/prolog/problems/trees/memberbt_2/en.py new file mode 100644 index 0000000..fcca1d9 --- /dev/null +++ b/prolog/problems/trees/memberbt_2/en.py @@ -0,0 +1,14 @@ +id = 135 +name = 'memberBT/2' +slug = 'find elements in a binary tree' + +description = '''\ +

memberBT(X, T): X is an element of the binary tree T. A binary tree node is represented with the structure b(L, E, R), where L and R are left and right subtrees, respectively, and E is the node's value. An empty tree is denoted by nil.

+
+  ?- memberBT(X, b(b(nil,2,nil),1,b(nil,3,nil))).
+    X = 1 ;
+    X = 2 ;
+    X = 3.
+
''' + +hint = {} diff --git a/prolog/problems/trees/membert_2/common.py b/prolog/problems/trees/membert_2/common.py new file mode 100644 index 0000000..177309f --- /dev/null +++ b/prolog/problems/trees/membert_2/common.py @@ -0,0 +1,18 @@ +id = 142 +group = 'trees' +number = 49 +visible = True +facts = None + +solution = '''\ +memb142(X, [X|_]). +memb142(X, [_|T]) :- + memb142(X, T). + +memberT(X, Tree) :- + Tree =.. [t, X|_]. +memberT(X, Tree) :- + Tree =.. [t, _|SubTrees], + memb142(SubTree, SubTrees), + memberT(X, SubTree). +''' diff --git a/prolog/problems/trees/membert_2/en.py b/prolog/problems/trees/membert_2/en.py new file mode 100644 index 0000000..a6fdffb --- /dev/null +++ b/prolog/problems/trees/membert_2/en.py @@ -0,0 +1,14 @@ +id = 142 +name = 'memberT/2' +slug = 'find elements in a tree' + +description = '''\ +

memberT(X, T): X is an element of the tree T. A tree node is represented with the structure t(E, T1, T2...), where E is the node's value, followed by any number of subtrees. An empty tree is denoted by nil.

+
+  ?- memberT(X, t(3, t(1), t(2))).
+    X = 3 ;
+    X = 1 ;
+    X = 2.
+
''' + +hint = {} diff --git a/prolog/problems/trees/mirrorbt_2/common.py b/prolog/problems/trees/mirrorbt_2/common.py new file mode 100644 index 0000000..dc8d337 --- /dev/null +++ b/prolog/problems/trees/mirrorbt_2/common.py @@ -0,0 +1,12 @@ +id = 136 +group = 'trees' +number = 43 +visible = True +facts = None + +solution = '''\ +mirrorBT(nil, nil). +mirrorBT(b(L, X, R), b(NewR, X, NewL)) :- + mirrorBT(L, NewL), + mirrorBT(R, NewR). +''' diff --git a/prolog/problems/trees/mirrorbt_2/en.py b/prolog/problems/trees/mirrorbt_2/en.py new file mode 100644 index 0000000..d44f463 --- /dev/null +++ b/prolog/problems/trees/mirrorbt_2/en.py @@ -0,0 +1,12 @@ +id = 136 +name = 'mirrorBT/2' +slug = 'flip a binary tree horizontally' + +description = '''\ +

mirrorBT(T, NewT): the binary tree NewT is obtained from T by flipping it over the vertical axis through the root node.

+
+  ?- mirrorBT(b(b(b(nil,4,nil),2,b(nil,5,nil)),1,b(nil,3,nil)), X).
+    X = b(b(nil,3,nil), 1, b(b(nil,5,nil), 2, b(nil,4,nil))).
+
''' + +hint = {} diff --git a/prolog/problems/trees/numberbt_2/common.py b/prolog/problems/trees/numberbt_2/common.py new file mode 100644 index 0000000..65baa14 --- /dev/null +++ b/prolog/problems/trees/numberbt_2/common.py @@ -0,0 +1,13 @@ +id = 139 +group = 'trees' +number = 44 +visible = True +facts = None + +solution = '''\ +numberBT(nil, 0). +numberBT(b(L, _, R), N) :- + numberBT(L, LN), + numberBT(R, RN), + N is LN + RN + 1. +''' diff --git a/prolog/problems/trees/numberbt_2/en.py b/prolog/problems/trees/numberbt_2/en.py new file mode 100644 index 0000000..6f735ed --- /dev/null +++ b/prolog/problems/trees/numberbt_2/en.py @@ -0,0 +1,12 @@ +id = 139 +name = 'numberBT/2' +slug = 'find the number of nodes in a binary tree' + +description = '''\ +

numberBT(T, N): N is the number of nodes in the binary tree T.

+
+  ?- numberBT(b(b(nil,2,nil),1,b(nil,3,nil)), N).
+    N = 3.
+
''' + +hint = {} diff --git a/prolog/problems/trees/tolistbt_2/common.py b/prolog/problems/trees/tolistbt_2/common.py new file mode 100644 index 0000000..6df7cdd --- /dev/null +++ b/prolog/problems/trees/tolistbt_2/common.py @@ -0,0 +1,17 @@ +id = 141 +group = 'trees' +number = 46 +visible = True +facts = None + +solution = '''\ +conc141([], L, L). +conc141([H|T], L2, [H|L]) :- + conc141(T, L2, L). + +tolistBT(nil, []). +tolistBT(b(L, E, R), List) :- + tolistBT(L, LL), + tolistBT(R, RL), + conc141(LL, [E|RL], List). +''' diff --git a/prolog/problems/trees/tolistbt_2/en.py b/prolog/problems/trees/tolistbt_2/en.py new file mode 100644 index 0000000..c4bf5ba --- /dev/null +++ b/prolog/problems/trees/tolistbt_2/en.py @@ -0,0 +1,12 @@ +id = 141 +name = 'tolistBT/2' +slug = 'construct a list with all elements of a binary tree' + +description = '''\ +

tolistBT(T, L): the list L contains all the elements in the binary tree T, in infix order.

+
+  ?- tolistBT(b(b(nil,2,nil),1,b(nil,3,nil)), L).
+    L = [2,1,3].
+
''' + +hint = {} -- cgit v1.2.1