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. --- .../prog_8puzzle_3/common.py | 37 ++++++++++++++++++++++ .../denotational_semantics/prog_8puzzle_3/en.py | 19 +++++++++++ 2 files changed, 56 insertions(+) create mode 100644 prolog/problems/denotational_semantics/prog_8puzzle_3/common.py create mode 100644 prolog/problems/denotational_semantics/prog_8puzzle_3/en.py (limited to 'prolog/problems/denotational_semantics/prog_8puzzle_3') 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 = {} -- cgit v1.2.1