🎉 Exercism Research is now launched. Help Exercism, help science and have some fun at research.exercism.io 🎉 # mbraak's solution

## to Rectangles in the OCaml Track

Published at Oct 03 2018 · 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 `Core`. 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 core:

``````opam install core
``````

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

``````(* Test/exercise version: "1.0.0" *)

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

type coords = int * int
type diagram = string array

let iter_diagram (diagram: diagram) : (coords * char) list =
diagram
|> Array.to_list
|> List.concat_mapi ~f: (fun y row ->
String.to_list row
|> List.mapi ~f: (fun x c ->
((x, y), c)
)
)

let positions_with_char (diagram: diagram) (c: char) : coords list =
iter_diagram diagram
|> List.filter_map ~f: (fun (coord, v) ->
if Char.equal c v then
Some coord
else
None
)

let unique_ints (l: int list) : int list =
List.dedup_and_sort l ~compare: Int.compare

let get_xs (positions: coords list) : int list =
List.map positions ~f: (fun (x, _) -> x)
|> unique_ints

let get_ys (positions: coords list) : int list =
List.map positions ~f: (fun (_, y) -> y)
|> unique_ints

let check_positions (positions: coords list) : bool =
List.length positions = 4 &&
List.length (get_xs positions) = 2 &&
List.length (get_ys positions) = 2

let take_two (l: int list) : (int * int) option =
match l with
| n1 :: n2 :: _ -> Some (n1, n2)
| _ -> None

let normalize_positions (positions: coords list) : (coords * coords) option =
match (take_two (get_xs positions), take_two (get_ys positions)) with
| (Some (x1, x2), Some (y1, y2)) -> Some ((x1, y1), (x2, y2))
| _ -> None

let at (diagram: diagram) (x: int) (y: int) : char =
let row = Array.get diagram y in
String.get row x

let contains (l: char list) (c: char) : bool =
List.exists l ~f: (fun v -> Char.equal c v)

let check_lines_for_coordinates (diagram: diagram) ((top_left): coords) (bottom_right: coords) : bool =
let (x1, y1) = top_left in
let (x2, y2) = bottom_right in
let xs = List.range x1 x2 ~stop: `inclusive in
let ys = List.range y1 y2 ~stop: `inclusive in
List.for_all xs ~f: (fun x -> contains ['+';'-'] (at diagram x y1)) &&
List.for_all xs ~f: (fun x -> contains ['+';'-'] (at diagram x y2)) &&
List.for_all ys ~f: (fun y -> contains ['+';'|'] (at diagram x1 y)) &&
List.for_all ys ~f: (fun y -> contains ['+';'|'] (at diagram x2 y))

let check_lines (diagram: diagram) (positions: coords list) : bool =
match normalize_positions positions with
| Some (top_left, bottom_right) -> check_lines_for_coordinates diagram top_left bottom_right
| _ -> false

let is_rectangle (diagram: diagram) (positions: coords list) : bool =
(check_positions positions) && (check_lines diagram positions)

let rec combinations (n: int) (l: coords list): (coords list) list =
if n <= 0 then [ [] ]
else match l with
| [] -> []
| h :: tl ->
let with_h = List.map ~f: (fun l -> h :: l) (combinations (n - 1) tl) in
let without_h = combinations n tl in
with_h @ without_h

let count_rectangles (diagram: diagram) : int =
combinations 4 (positions_with_char diagram '+')
|> List.count ~f: (fun (positions: coords list) ->
is_rectangle diagram positions
)``````