 # marionebl's solution

## to Rectangles in the OCaml Track

Published at May 28 2019 · 0 comments
Instructions
Test suite
Solution

#### Note:

This exercise has changed since this solution was written.

Count the rectangles in an ASCII diagram like the one below.

``````   +--+
++  |
+-++--+
|  |  |
+--+--+
``````

The above diagram contains 6 rectangles:

``````

+-----+
|     |
+-----+
``````
``````   +--+
|  |
|  |
|  |
+--+
``````
``````   +--+
|  |
+--+

``````
``````

+--+
|  |
+--+
``````
``````

+--+
|  |
+--+
``````
``````
++
++

``````

You may assume that the input is always a proper rectangle (i.e. the length of every line equals the length of the first line).

## Getting Started

For installation and learning resources, refer to the exercism help page.

## Installation

To work on the exercises, you will need `Opam` and `Base`. Consult opam website for instructions on how to install `opam` for your OS. Once `opam` is installed open a terminal window and run the following command to install base:

``````opam install base
``````

To run the tests you will need `OUnit`. Install it using `opam`:

``````opam install ounit
``````

## Running Tests

A Makefile is provided with a default target to compile your solution and run the tests. At the command line, type:

``````make
``````

## Interactive Shell

`utop` is a command line program which allows you to run Ocaml code interactively. The easiest way to install it is via opam:

``````opam install utop
``````

Consult utop for more detail.

## Feedback, Issues, Pull Requests

The exercism/ocaml repository on GitHub is the home for all of the Ocaml exercises.

If you have feedback about an exercise, or want to help implementing a new one, head over there and create an issue. We'll do our best to help you!

## Submitting Incomplete Solutions

It's possible to submit an incomplete solution so you can see how others have completed the exercise.

### test.ml

``````open OUnit2
open Rectangles

let ae exp got _test_ctxt = assert_equal exp got ~printer:string_of_int

let tests = [
"no rows" >::
ae 0 (count_rectangles [||]);
"no columns" >::
ae 0 (count_rectangles [|""|]);
"no rectangles" >::
ae 0 (count_rectangles [|" "|]);
"one rectangle" >::
ae 1 (count_rectangles [|"+-+";
"| |";
"+-+"|]);
"two rectangles without shared parts" >::
ae 2 (count_rectangles [|"  +-+";
"  | |";
"+-+-+";
"| |  ";
"+-+  "|]);
"five rectangles with shared parts" >::
ae 5 (count_rectangles [|"  +-+";
"  | |";
"+-+-+";
"| | |";
"+-+-+"|]);
"rectangle of height 1 is counted" >::
ae 1 (count_rectangles [|"+--+";
"+--+"|]);
"rectangle of width 1 is counted" >::
ae 1 (count_rectangles [|"++";
"||";
"++"|]);
"1x1 square is counted" >::
ae 1 (count_rectangles [|"++";
"++"|]);
"only complete rectangles are counted" >::
ae 1 (count_rectangles [|"  +-+";
"    |";
"+-+-+";
"| | -";
"+-+-+"|]);
"rectangles can be of different sizes" >::
ae 3 (count_rectangles [|"+------+----+";
"|      |    |";
"+---+--+    |";
"|   |       |";
"+---+-------+"|]);
"corner is required for a rectangle to be complete" >::
ae 2 (count_rectangles [|"+------+----+";
"|      |    |";
"+------+    |";
"|   |       |";
"+---+-------+"|]);
"large input with many rectangles" >::
ae 60 (count_rectangles [|"+---+--+----+";
"|   +--+----+";
"+---+--+    |";
"|   +--+----+";
"+---+--+--+-+";
"+---+--+--+-+";
"+------+  | |";
"          +-+"|]);
]

let () =
run_test_tt_main ("rectangles tests" >::: tests)``````

### rectangles.ml

``````open Base

type point = {
x: int;
y: int;
}

type direction =
| Horizontal
| Vertical

type line = {
start: point;
length: int;
direction: direction;
}

type rectangle = {
a: point;
b: point;
}

let y_points (y: int) (l: char array): point array =
let is_point = Char.equal '+' in
Array.filter_mapi l ~f:(fun x s -> if is_point s then Some { x=x; y=y } else None)

let points (board: string array): point array =
board
|> Array.map ~f:(String.to_array)
|> Array.concat_mapi ~f:(y_points)

let connected_x (board: string array) (start: point) (b: point): line option =
let length = b.x - start.x in
if length <= 0 || b.y <> start.y then
None
else
let connection = String.sub (Array.get board start.y) ~pos:(start.x) ~len:(b.x - start.x) in
let empty = Char.equal ' ' in
if not (String.for_all connection ~f:(Fn.non empty)) then
None
else
Some { start; length; direction=Horizontal }

let connected_y (board: string array) (a: point) (b: point): bool =
Int.equal a.x b.x &&
Array.filteri board ~f:(fun i _ -> i >= a.y && i <= b.y)
|> Array.for_all ~f:(fun line ->
Char.equal line.[a.x] '|' || Char.equal line.[a.x] '+')

let sides (board: string array) (points: point array): line array =
let connected_points p = Array.filter_map points ~f:(connected_x board p) in
points |> Array.concat_map ~f:(connected_points)

let opposing (a: line) (b: line): bool = a.start.y < b.start.y && Int.equal a.start.x b.start.x && Int.equal a.length b.length

let candidates (sides: line array) =
let opposing' b a = if opposing a b then  Some { a=a.start; b={ x=(b.start.x + b.length); y=b.start.y } } else None in
let candidates' b = Array.filter_map sides ~f:(opposing' b) in
Array.concat_map sides ~f:(candidates')

let closed (board: string array) (cs: rectangle array): rectangle array =
Array.filter cs ~f:(fun c -> connected_y board c.a { x=c.a.x; y=c.b.y } && connected_y board { x=c.b.x; y=c.a.y } c.b)

let count_rectangles (board: string array): int =
points board
|> sides board
|> candidates
|> closed board
|> Array.length``````

### rectangles.mli

``````type point = {
x: int;
y: int;
}

type direction =
| Horizontal
| Vertical

type line = {
start: point;
length: int;
direction: direction;
}

val count_rectangles : string array -> int
val sides : string array -> point array -> line array
val points : string array -> point array
val opposing : line -> line -> bool``````

### test.ml

``````open OUnit2
open Rectangles

let ae exp got _test_ctxt = assert_equal exp got ~printer:string_of_int

let print_point p = Printf.sprintf "point { x=%i; y=%i }" p.x p.y
let print_direction = function | Horizontal -> "Horizontal" | Vertical -> "Vertical"
let print_line l = Printf.sprintf "line { start=%s; length=%i; direction=%s }" (print_point l.start) l.length (print_direction l.direction)
let print_array a ~item = Printf.sprintf "[| %s |]" ((Array.map item a) |> Array.to_list |> String.concat "; ")

let tests = [
"points - no rows" >::
(fun _ -> assert_equal [||] (points [||]));
"points - single" >::
(fun _ -> assert_equal [|{ x=0; y=0 }|] (points [|"+"|]) ~printer:(print_array ~item:print_point));
"points - multiple" >::
(fun _ -> assert_equal [|{ x=0; y=0 }; { x=3; y=0 }; { x=3; y=1 }|] (points [|"+--+"; "   +"|]) ~printer:(print_array ~item:print_point));

"sides - single" >::
(fun _ -> assert_equal [|{ start={x=0; y=0}; length=3; direction=Horizontal }|] (sides [|"+--+"; "   +"|] [|{ x=0; y=0 }; { x=3; y=0 }; { x=3; y=1 }|]) ~printer:(print_array ~item:print_line));
"sides - multiple" >::
(fun _ -> assert_equal [|{ start={x=0; y=0}; length=3; direction=Horizontal }; { start={x=0; y=1}; length=5; direction=Horizontal }|] (sides [|"+--+  "; "+----+"|] [|{ x=0; y=0 }; { x=3; y=0 }; { x=0; y=1 }; { x=5; y=1 }|]) ~printer:(print_array ~item:print_line));
"sides - nested" >::
(fun _ -> assert_equal [|
{ start={x=0; y=0}; length=3; direction=Horizontal }; { start={x=0; y=0}; length=7; direction=Horizontal }; { start={x=0; y=0}; length=12; direction=Horizontal };
{ start={x=3; y=0}; length=4; direction=Horizontal }; { start={x=3; y=0}; length=9; direction=Horizontal };
{ start={x=7; y=0}; length=5; direction=Horizontal };
|] (sides [|"+--+---+----+"|] [|{ x=0; y=0 }; { x=3; y=0 }; { x=7; y=0 }; { x=12; y=0 }|]) ~printer:(print_array ~item:print_line));

"opposing - equivalent" >::
(fun _ -> assert_equal false (opposing { start={x=0; y=0}; length=3; direction=Horizontal } { start={x=0; y=0}; length=3; direction=Horizontal }));
"opposing - simple" >::
(fun _ -> assert_equal true (opposing { start={x=0; y=0}; length=3; direction=Horizontal } { start={x=0; y=1}; length=3; direction=Horizontal }));
"opposing - inverted" >::
(fun _ -> assert_equal false (opposing { start={x=0; y=1}; length=3; direction=Horizontal } { start={x=0; y=0}; length=3; direction=Horizontal }));

"no rows" >::
ae 0 (count_rectangles [||]);
"no columns" >::
ae 0 (count_rectangles [|""|]);
"no rectangles" >::
ae 0 (count_rectangles [|" "|]);
"one rectangle" >::
ae 1 (count_rectangles [|"+-+";
"| |";
"+-+"|]);
"two rectangles without shared parts" >::
ae 2 (count_rectangles [|"  +-+";
"  | |";
"+-+-+";
"| |  ";
"+-+  "|]);
"five rectangles with shared parts" >::
ae 5 (count_rectangles [|"  +-+";
"  | |";
"+-+-+";
"| | |";
"+-+-+"|]);
"rectangle of height 1 is counted" >::
ae 1 (count_rectangles [|"+--+";
"+--+"|]);
"rectangle of width 1 is counted" >::
ae 1 (count_rectangles [|"++";
"||";
"++"|]);
"1x1 square is counted" >::
ae 1 (count_rectangles [|"++";
"++"|]);
"only complete rectangles are counted" >::
ae 1 (count_rectangles [|"  +-+";
"    |";
"+-+-+";
"| | -";
"+-+-+"|]);
"rectangles can be of different sizes" >::
ae 3 (count_rectangles [|"+------+----+";
"|      |    |";
"+---+--+    |";
"|   |       |";
"+---+-------+"|]);
"corner is required for a rectangle to be complete" >::
ae 2 (count_rectangles [|"+------+----+";
"|      |    |";
"+------+    |";
"|   |       |";
"+---+-------+"|]);
"large input with many rectangles" >::
ae 60 (count_rectangles [|"+---+--+----+";
"|   +--+----+";
"+---+--+    |";
"|   +--+----+";
"+---+--+--+-+";
"+---+--+--+-+";
"+------+  | |";
"          +-+"|]);
]

let () =
run_test_tt_main ("rectangles tests" >::: tests)``````