 # Sendell's solution

## to Rectangles in the OCaml Track

Published at Jun 01 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.mli

``val count_rectangles : string array -> int``

### rectangles.ml

``````open Base

let ( >> ) f g x = g (f x)

let to_coordinates =
Array.foldi ~init:[] ~f:(fun i ys line ->
let xs =
String.foldi line ~init:[] ~f:(fun j xs c ->
match c with '+' -> j :: xs | _ -> xs )
in
(i, xs) :: ys )
>> List.filter ~f:(snd >> List.is_empty >> not)
>> List.rev

let generates_candidates xs =
List.cartesian_product xs xs |> List.filter ~f:(fun (l, r) -> l < r)

let is_corner = Char.equal '+'

let is_vertical c = Char.equal '|' c || is_corner c

let is_horizontal c = Char.equal '-' c || is_corner c

let check_horizontal line x0 x1 =
(* A valid line contains either '+' or '-' in the middle *)
let inner =
let len = x1 - x0 + 1 in
if len > 2 then
String.sub line ~pos:x0 ~len
|> String.fold ~init:true ~f:(fun is_valid c ->
is_valid && is_horizontal c )
else true
in
(* And then a valid line starts and ends with '+' *)
inner && Char.equal line.[x0] '+' && Char.equal line.[x1] '+'

let check_vertical drawing x y0 y1 =
(* A valid line contains either '+' or '|' in the middle *)
let inner =
let len = y1 - y0 + 1 in
if len > 2 then
Array.sub drawing ~pos:y0 ~len
|> Array.fold ~init:true ~f:(fun is_valid l ->
let c = l.[x] in
is_valid && is_vertical c )
else true
in
(* And then a valid line starts and ends with '+' *)
inner && Char.equal drawing.(y0).[x] '+' && Char.equal drawing.(y1).[x] '+'

let is_valid_rectangle drawing x0 x1 y0 y1 =
check_horizontal drawing.(y0) x0 x1
&& check_horizontal drawing.(y1) x0 x1
&& check_vertical drawing x0 y0 y1
&& check_vertical drawing x1 y0 y1

let count_equal_pairs drawing ycs ypss =
let y0, cs = ycs in
List.fold cs ~init:0 ~f:(fun acc (c0, c1) ->
List.fold ypss ~init:0 ~f:(fun acc_inner yps ->
let y1, ps = yps in
List.count ps ~f:(fun (x0, x1) ->
c0 = x0 && c1 = x1 && is_valid_rectangle drawing x0 x1 y0 y1 )
+ acc_inner )
+ acc )

let count_rectangles drawing =
let rec aux total_count = function
| [] | [_] -> total_count
| ycs :: ypss ->
let sub_count = count_equal_pairs drawing ycs ypss in
aux (total_count + sub_count) ypss
in
to_coordinates drawing
|> List.map ~f:(fun (i, x) -> (i, generates_candidates x))
|> aux 0``````