 # jef's solution

## to Rectangles in the OCaml Track

Published at Jan 22 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)``````
``````open Base

let id a = a

(* list of column indeces where a segment exists from (row, start_col) to (row, X) *)
let find_endpoints_to_right grid row start_col =
let col_range = List.range (start_col + 1) (String.length grid.(0)) in
List.fold_until
col_range
~init:[]
~f:(fun endpoints col ->
match grid.(row).[col] with
| '-' -> Continue endpoints
| '+' -> Continue (col :: endpoints)
| _ -> Stop endpoints )
~finish:id
;;

(* list of row indeces where a segment exists from (start_row, col) to (X, col) *)
let find_endpoints_down grid start_row col =
let row_range = List.range (start_row + 1) (Array.length grid) in
List.fold_until
row_range
~init:[]
~f:(fun endpoints row ->
match grid.(row).[col] with
| '|' -> Continue endpoints
| '+' -> Continue (row :: endpoints)
| _ -> Stop endpoints )
~finish:id
;;

let is_horizontal_segment grid row left_col right_col =
Char.equal '+' grid.(row).[left_col]
&& Char.equal '+' grid.(row).[right_col]
&&
let col_range = List.range (left_col + 1) right_col in
List.fold_until
col_range
~init:true
~f:(fun _accum col ->
match grid.(row).[col] with '-' | '+' -> Continue true | _ -> Stop false )
~finish:id
;;

let is_vertical_segment grid col top_row bottom_row =
Char.equal '+' grid.(top_row).[col]
&& Char.equal '+' grid.(bottom_row).[col]
&&
let row_range = List.range (top_row + 1) bottom_row in
List.fold_until
row_range
~init:true
~f:(fun _accum row ->
match grid.(row).[col] with '|' | '+' -> Continue true | _ -> Stop false )
~finish:id
;;

let count_with_top_left_at grid top_row left_col =
let top_right_options = find_endpoints_to_right grid top_row left_col in
List.fold top_right_options ~init:0 ~f:(fun count right_col ->
let bottom_right_options = find_endpoints_down grid top_row right_col in
List.fold bottom_right_options ~init:count ~f:(fun count bottom_row ->
if is_horizontal_segment grid bottom_row left_col right_col
&& is_vertical_segment grid left_col top_row bottom_row
then count + 1
else count ) )
;;

let count_rectangles grid =
Array.foldi grid ~init:0 ~f:(fun row_index count row_string ->
String.foldi row_string ~init:count ~f:(fun col_index count char ->
match char with
| '+' -> count + count_with_top_left_at grid row_index col_index
| _ -> count ) )
;;``````