|
Size: 2889
Comment:
|
← Revision 6 as of 2011-02-03 15:43:56 ⇥
Size: 2789
Comment:
|
| Deletions are marked like this. | Additions are marked like this. |
| Line 7: | Line 7: |
| Tangram is an ancient Chinese game of Shapes. The goal is to form a particular shape from a set of seven pieces consisting of 5 triangles (of three different sizes), a square, and a parallelogram. The number of sides, the sizes and basic orientations of the seven blocks is defined below. The 1st argument is the block number, the 2nd is the number of sides, then there is the sequence of coordinates of successive vertexes: |
Tangram is an ancient Chinese game of Shapes. The goal is to form a particular shape from a set of seven pieces consisting of 5 triangles (of three different sizes), a square, and a parallelogram. These seven pieces are defined below, where the 1-st argument is the block number (an integer identifier), the 2-nd argument is the number {{{k}}} of sides of the block, and the last {{{2*k}}} arguments represents the vertices of the block. |
| Line 19: | Line 19: |
| Allowed angles are represented by the number 0..7 in parenthesis. You can assume MAXX=8 and MAXY=6. |
Note that these facts are not part of the input. |
| Line 22: | Line 21: |
| Your program needs to compute a predicate put/4 that associates to each block i in {1,...,7} one pair (X,Y) and one angle A. With that association the entire surface of the instance figure must be covered (and without overlapping, but this is a consequence for the chosen figures). | Allowed angles are 0 (0), 45 (1), 90 (2), 135 (3), 180 (4), 225 (5), 270 (6), and 315 (7) degrees, represented by means of the numbers 0..7 in parenthesis. |
| Line 32: | Line 32: |
| Any input instance is defined using two predicates: {{{sides(n)}}}. | A fact of the form {{{sides(n)}}}, fixing the number of sides of the figure. |
| Line 34: | Line 34: |
| that fixes the number of sides of the figure and | The target shape is specified by means of {{{n}}} facts of the form |
| Line 41: | Line 41: |
| that are the coordinates of the consecutive vertexes 1,2, ..., n of the figure. No need to say that the perimeter of the figure is the set of segments { (X1,Y1)-(X2,Y2), (X2,Y2)-(X3,Y3), ..., (Xn-1,Yn-1)-(Xn,Yn), (Xn-Yn)-(X1,Y1) }. | In particular, a fact of the form {{{coord(i,Xi,Yi)}}} specifies that the i-th vertex of the target shape is {{{(Xi,Yi)}}}. Thus, the perimeter of the figure is the set of segments {{{ { (X1,Y1)-(X2,Y2), (X2,Y2)-(X3,Y3), ..., (Xn-1,Yn-1)-(Xn,Yn), (Xn-Yn)-(X1,Y1) } }}}. |
| Line 43: | Line 45: |
| Although is clear that some of the sides of the 7 blocks have an irrational length, their orientation (above) as well as the orientations of the instances are chosen so as to work with integer numbers only. The allowed action is to "put" the vertex corresponding to (0,0) in the above "size_block" definition in a point (X,Y) with X in {0,1,...,MAXX} and Y in {0,1,...,MAXY} rotated wrt its basic orientation by 0 (0), 45 (1), 90 (2), 135 (3), 180 (4), 225 (5), 270 (6), 315 (7) degrees. |
In our setting, each coordinate X is an integer in {0,...,8}, and each coordinate Y is an integer in {0,...,6}. |
| Line 50: | Line 50: |
| A possible output should be of the form {{{ put(1,4,0,0). put(2,4,4,6). put(3,4,0,2). put(4,0,0,0). put(5,3,1,2). put(6,1,1,0). put(7,3,1,0). }}} that is also a correct solution of the instance {{{ sides(3). coord(1,0,0). coord(2,8,0). coord(3,4,4). }}} |
Your program needs to compute a predicate put/4 that associates to each block i in {1,...,7} one pair (X,Y) and one angle A. With that association the entire surface of the instance figure must be covered (and without overlapping, but this is a consequence for the chosen figures). More specifically, an atom of the form {{{put(i,x,y,r)}}} in the output specifies that the block with ID {{{i}}} is positioned in {{{(x,y)}}} and rotated according to {{{r}}}. |
| Line 63: | Line 57: |
Input: {{{sides(3). coord(1,0,0). coord(2,8,0). coord(3,4,4).}}} Output: {{{put(1,4,0,0). put(2,4,4,6). put(3,4,0,2). put(4,0,0,0). put(5,3,1,2). put(6,1,1,0). put(7,3,1,0).}}} |
Tangram
Problem Description
Tangram is an ancient Chinese game of Shapes. The goal is to form a particular shape from a set of seven pieces consisting of 5 triangles (of three different sizes), a square, and a parallelogram. These seven pieces are defined below, where the 1-st argument is the block number (an integer identifier), the 2-nd argument is the number k of sides of the block, and the last 2*k arguments represents the vertices of the block.
size_block(1,3, 0,0, 4,0, 2,2). %%% Large triangle size_block(2,3, 0,0, 4,0, 2,2). %%% Large triangle size_block(3,3, 0,0, 2,0, 0,2). %%% Medium triangle size_block(4,3, 0,0, 2,0, 1,1). %%% Small triangle size_block(5,3, 0,0, 2,0, 1,1). %%% Small triangle size_block(6,4, 0,0, 1,-1, 2,0, 1,1). %%% Square size_block(7,4, 0,0, 1,1, 1,3, 0,2). %%% Parallelogram
Note that these facts are not part of the input.
Allowed angles are 0 (0), 45 (1), 90 (2), 135 (3), 180 (4), 225 (5), 270 (6), and 315 (7) degrees, represented by means of the numbers 0..7 in parenthesis.
Predicates
Input: sides/1, coord/3
Output: put/4
Input format
A fact of the form sides(n), fixing the number of sides of the figure.
The target shape is specified by means of n facts of the form
coord(1,X1,Y1). coord(2,X2,Y2). ... coord(n,Xn,Yn).
In particular, a fact of the form coord(i,Xi,Yi) specifies that the i-th vertex of the target shape is (Xi,Yi). Thus, the perimeter of the figure is the set of segments { (X1,Y1)-(X2,Y2), (X2,Y2)-(X3,Y3), ..., (Xn-1,Yn-1)-(Xn,Yn), (Xn-Yn)-(X1,Y1) } .
In our setting, each coordinate X is an integer in {0,...,8}, and each coordinate Y is an integer in {0,...,6}.
Output format
Your program needs to compute a predicate put/4 that associates to each block i in {1,...,7} one pair (X,Y) and one angle A. With that association the entire surface of the instance figure must be covered (and without overlapping, but this is a consequence for the chosen figures). More specifically, an atom of the form put(i,x,y,r) in the output specifies that the block with ID i is positioned in (x,y) and rotated according to r.
Example(s)
Input: sides(3). coord(1,0,0). coord(2,8,0). coord(3,4,4).
Output: put(1,4,0,0). put(2,4,4,6). put(3,4,0,2). put(4,0,0,0). put(5,3,1,2). put(6,1,1,0). put(7,3,1,0).
Author(s)
- Author: Agostino Dovier
- Affiliation: University of Udine, Italy
- Author: Andrea Formisano
- Affiliation: University of Perugia, Italy
- Author: Enrico Pontelli
- Affiliation: New Mexico State University, USA