$29
Assignment 1 Solution
• Assignment Policies
Collaboration Policy. Homework will be done individually: each student must hand in their own answers. It is acceptable for students to collaborate in understanding the material but not in solving the problems or programming. Use of the Internet is allowed, but should not include searching for existing solutions.
Under absolutely no circumstances code can be exchanged between students.
Excerpts of code presented in class can be used.
Assignments from previous o erings of the course must not be re-used. Viola-tions will be penalized appropriately.
• Assignment
This assignment is about coding with lists and tuples. The setting is that of a simple game called Connect the Dots. A coded picture is a list of coordinates such that adjacent coordinates are aligned. Coordinates must be positive integers. Two coordinates are said to be aligned if they are either on the same x-axis, the same y-axis, or the di erence between their x and y coordinates is the same (i.e. \diagonal").
A coded picture induces a picture, namely the one obtained by connecting the coordinates in the list, in the order they are presented. For example, given the coded picture
[(0,0);(0,4);(2,2);(0,0)]
it induces a triangle.
• Exercises
We will use the following user de ned datatypes for representing coordinates and coded pictures.
• type coord = int * int
2 type c o d e d _ p i c t u r e = coord list
1
Below are two examples of coded pictures, the rst one determines a box (once the coordinates are connected) and the second a triangle.
1
let
cp1
=
[(0 ,0) ;(2 ,0) ;(2 ,2) ;(0
,2) ;(0 ,0) ]
2
let
cp2
=
[(0 ,0) ;(4 ,0) ;(4 ,4) ;(0
,0) ]
3.1 Your Task
Implement the following functions. You should work on the le cp_stub.ml. First rename it to cp.ml and then start completing the exercises given below.
1. stretch : coded_picture -> int -> coded-picture
The expression stretch cp factor enlarges the coded picture by a factor of factor in both axis. For example,
• utop # stretch cp1 2;;
2 - : c od e d_ pi c = [(0 , 0) ; (4 , 0) ; (4 , 4) ; (0 , 4) ; (0 , 0) ]
• utop # stretch cp2 7;;
• - : c od e d_ pi c = [(0 , 0) ; (28 , 0) ; (28 , 28) ; (0 , 0) ]
Provide two versions:
(a) stretch using explicit recursion; and
(b) stretch_m using map.
2. segment : coord -> coord -> coord list
Given aligned coordinates c1 and c2, it returns all the intermediate coordinates in the line segment from c1 to c2, excluding c1 but including c2. For example,
1
# segment (1 ,1)
(4 ,4) ;;
2
- : ( int
* int ) list =
[(2, 2); (3, 3); (4, 4)]
3
utop
# segment
(2 ,2)
(5 ,2) ;;
4
- :
( int
* int )
list
=
[(3, 2); (4, 2); (5, 2)]
Hint: The prede ned function compare: ’a -> ’a -> int allows you to compare values as a pre x operation. In particular, compare x 0 behaves like sign.
3. coverage: coded_pic -> coord list
1
# coverage cp1 ;;
2
- : coord list =
3
[(0, 0); (1, 0)
;
(2 ,
0) ;
(2 ,
1) ;
(2 ,
2) ;
(1 ,
2) ;
(0 ,
2) ;
(0 ,
1) ;
(0 ,
0) ]
4
# coverage cp2 ;;
5
- : coord list =
6
[(0, 0); (1, 0); (2,
0) ;
(3 ,
0) ;
(4 ,
0) ;
(4 ,
1) ;
(4 ,
2) ;
(4 ,
3) ;
(4 ,
4) ;
7
(3, 3); (2, 2);
(1 ,
1) ;
(0 ,
0) ]
Provide two versions:
(a) coverage using explicit recursion; and
2
(b) coverage_f using fold.
4. equivalent_pics : coded_pic -> coded_pic -> bool
Determines whether two coded pictures are equivalent. Two coded pictures are said to be equivalent if the coordinates they cover are identical, up to possible duplicates. For example,
1
utop
#
e q u i v a l e n t _ p i c s cp1
[(0 ,0) ;(1 ,0) ;(2 ,0) ;(2 ,2) ;(0 ,2) ;(0 ,0) ];;
2
-
: bool
=
true
3
utop
#
e q u i v a l e n t _ p i c s cp1
[(2 ,2) ;(0 ,2) ;(0 ,0) ;(2 ,0) ;(2 ,2) ];;
4
-
:
bool
=
true
5. height : coded_pic -> int and width : coded_pic -> int
Determines the height (maximum di erence between y coordinates) and width of a picture (maximum di erence between x-coordinates). For example,
• # height cp1 ;;
2 - : int = 2
• utop # height cp2 ;;
4 - : int = 4
• utop # width cp2 ;;
6 - : int = 4
• utop # width cp1 ;;
8 - : int = 2
6. tile : coded_pic -> int*int -> coded_pic list list
Given a coded picture and a pair of two numbers n and m, it returns a list of list of pictures. The result is obtained by constructing a rst row of n copies, side by side of the original pictures, and then m rows below that. For example,
1
utop
# tile (2 ,3)
cp2 ;;
2
- : c od e d_ pi c list list =
3
[[[(0, 0); (4, 0);
(4 ,
4)
;
(0 ,
0) ];
[(4 ,
0); (8, 0); (8,
4) ;
(4 ,
0) ]];
4
[[(0, 4); (4, 4);
(4 ,
8)
;
(0 ,
4) ];
[(4 ,
4); (8, 4); (8,
8) ;
(4 ,
4) ]];
5
[[(0, 8); (4, 8);
(4 ,
12); (0,
8) ];
[(4 ,
8) ;
(8 ,
8) ;
(8 ,
12) ; (4, 8) ]]]
6
utop
# tile (2 ,1)
cp2 ;;
7
- : c od e d_ pi c list list =
8
[[[(0, 0); (4, 0);
(4 ,
4)
;
(0 ,
0) ];
[(4 ,
0) ;
(8 ,
0) ;
(8 ,
4) ;
(4 ,
0) ]]]
9
utop
# tile (2 ,0)
cp2 ;;
10
- :
c od e d_ pi c list
list
=
[]
7. tri_aligned: coord -> coord -> coord -> bool
Determines whether three coordinates are aligned, horizontally, vertically or in diago-nal. For example,
1 utop # t r i _ a l i g n e d (0 ,0) (4 ,4) (9 ,9) ;;
• - : bool = true
3 utop # t r i _ a l i g n e d (0 ,0) (0 ,4) (9 ,9) ;;
• - : bool = false
5 utop # t r i _ a l i g n e d (0 ,0) (0 ,7) (0 ,9) ;;
• - : bool = true
7
utop
# t r i _ a l i g n e d (7 ,7) (2 ,2) (0 ,0) ;;
8
- :
bool = true
3
8. compress: coded_pic -> coded_pic
Compresses a coded picture by eliminating coordinates c2 such that c2 occurs between two other coordinates c1 and c3 and c1, c2, c3 are aligned. For example,
1
#
compress [(0 ,0) ;(1
,0)
;(2 ,0) ;(2
,2)
;(0 ,2) ;(0
,0)
];;
2
-
: c od e d_ pi c = [(0 ,
0)
; (2, 0);
(2
, 2); (0,
2)
; (0, 0)]
• Submission instructions
Submit a single le named cp.ml through Canvas. No report is required. Your grade will be determined as follows:
You will get 0 points if your code does not compile.
Partial credit may be given for style, comments and readability.
4
