|
Size: 2952
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 5: | Line 5: |
| == 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. |
|
| Line 7: | Line 26: |
| * '''Input''': sides/1, coord/3 | * '''Input''': {{{sides/1, coord/3}}} |
| Line 9: | Line 28: |
| * '''Output''': put/4 == 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. 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: size_block(1,3, 0,0, 4,0, 2,2). %%% Large triangle <<BR>> size_block(2,3, 0,0, 4,0, 2,2). %%% Large triangle <<BR>> size_block(3,3, 0,0, 2,0, 0,2). %%% Medium triangle <<BR>> size_block(4,3, 0,0, 2,0, 1,1). %%% Small triangle <<BR>> size_block(5,3, 0,0, 2,0, 1,1). %%% Small triangle <<BR>> size_block(6,4, 0,0, 1,-1, 2,0, 1,1). %%% Square <<BR>> size_block(7,4, 0,0, 1,1, 1,3, 0,2). %%% parallelogram <<BR>> Allowed angles are represented by the number 0..7 in parenthesis. You can assume MAXX=8 and MAXY=6. 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). |
* '''Output''': {{{put/4}}} |
| Line 32: | Line 32: |
| Any input instance is defined using two predicates: | A fact of the form {{{sides(n)}}}, fixing the number of sides of the figure. |
| Line 34: | Line 34: |
| sides(n). | 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) } }}}. |
| Line 36: | Line 45: |
| that fixes the number of sides of the figure and coord(1,X1,Y1). <<BR>> coord(2,X2,Y2). <<BR>> ... <<BR>> coord(n,Xn,Yn). <<BR>> 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) }. 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 52: | Line 50: |
| A possible output should be of the form | 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 54: | Line 56: |
| put(1,4,0,0). put(2,4,4,6). put(3,4,0,2). put(4,0,0,0). <<BR>> put(5,3,1,2). put(6,1,1,0). put(7,3,1,0). <<BR>> |
== Example(s) == |
| Line 57: | Line 58: |
| that is also a correct solution of the instance | Input: {{{sides(3). coord(1,0,0). coord(2,8,0). coord(3,4,4).}}} |
| Line 59: | Line 60: |
| sides(3). <<BR>> coord(1,0,0). <<BR>> coord(2,8,0). <<BR>> coord(3,4,4). <<BR>> == Example == |
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