summaryrefslogtreecommitdiff
path: root/prolog/problems/sorting
diff options
context:
space:
mode:
authorAleš Smodiš <aless@guru.si>2015-08-18 16:06:19 +0200
committerAleš Smodiš <aless@guru.si>2015-08-18 16:06:19 +0200
commit95e2fe57f6e4639f6ae9f1fef368829d5090dbf6 (patch)
tree462ba05eb0c4732ca1c97739548801258bf47b40 /prolog/problems/sorting
Exported all problems from the SQLite database into the new directory structure.
Diffstat (limited to 'prolog/problems/sorting')
-rw-r--r--prolog/problems/sorting/is_sorted_1/common.py13
-rw-r--r--prolog/problems/sorting/is_sorted_1/en.py14
-rw-r--r--prolog/problems/sorting/isort_2/common.py18
-rw-r--r--prolog/problems/sorting/isort_2/en.py12
-rw-r--r--prolog/problems/sorting/pivoting_4/common.py15
-rw-r--r--prolog/problems/sorting/pivoting_4/en.py12
-rw-r--r--prolog/problems/sorting/quick_sort_2/common.py24
-rw-r--r--prolog/problems/sorting/quick_sort_2/en.py12
-rw-r--r--prolog/problems/sorting/sins_3/common.py14
-rw-r--r--prolog/problems/sorting/sins_3/en.py14
-rw-r--r--prolog/problems/sorting/slowest_sort_ever_2/common.py25
-rw-r--r--prolog/problems/sorting/slowest_sort_ever_2/en.py12
12 files changed, 185 insertions, 0 deletions
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 = '''\
+<p><code>is_sorted(L)</code>: the elements of list <code>L</code> are sorted in non-decreasing order.</p>
+<pre>
+ ?- is_sorted([2,3,6,8,12]).
+ true.
+ ?- is_sorted([2,3,1,6,5]).
+ false.
+</pre>'''
+
+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 = '''\
+<p><code>isort(L, SL)</code>: the list <code>SL</code> contains the elements of <code>L</code> sorted in non-decreasing order. Use the predicate <code>sins/3</code> to implement insertion sort.</p>
+<pre>
+ ?- isort([2,3,1,5,4], L).
+ L = [1,2,3,4,5].
+</pre>'''
+
+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 = '''\
+<p><code>pivoting(P, L, S, G)</code>: the list <code>S</code> contains the elements of <code>L</code> <em>smaller or equal to</em> <code>P</code>, and the list <code>G</code> contains the elements of <code>L</code> <em>greater than</em> <code>P</code>. The order of elements in <code>S</code> and <code>G</code> should be the same as in <code>L</code>.</p>
+<pre>
+ ?- pivoting(4, [1,4,5,8,6,4,2], S, G).
+ S = [1,4,4,2], G = [5,8,6].
+</pre>'''
+
+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 = '''\
+<p><code>quick_sort(L, SL)</code>: the list <code>SL</code> contains the elements of <code>L</code> sorted in non-decreasing order. Use the predicate <code>pivoting/4</code> to implement quicksort.</p>
+<pre>
+ ?- quick_sort([2,3,1,5,4], L).
+ L = [1,2,3,4,5].
+</pre>'''
+
+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 = '''\
+<p><code>sins(X, SortedList, NewList)</code>: the list <code>NewList</code> is obtained by inserting <code>X</code> into <code>SortedList</code> at the correct position to preserve the non-decreasing order of elements.</p>
+<pre>
+ ?- 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].
+</pre>'''
+
+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 = '''\
+<p><code>slowest_sort_ever(L, SL)</code>: the list <code>SL</code> contains the elements of <code>L</code> sorted in non-decreasing order. Average and worst case running time is O(n * n!).</p>
+<pre>
+ ?- slowest_sort_ever([2,3,1,5,4], L).
+ L = [1,2,3,4,5].
+</pre>'''
+
+hint = {}