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. --- 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 +++++++++++ 12 files changed, 185 insertions(+) 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 (limited to 'prolog/problems/sorting') 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 = {} -- cgit v1.2.1