%EXAMPLES

let myMaze = {
    rooms = [1; 2; 3; 4; 5; 6; 7; 8; 9; 10; 11; 12; 13];
    entrances = [1;4;11];
    exits = [6;12];
    passages = [(1,2);(1,4);(1,5);(2,5);(3,6);(4,5);(4,7);
                (5,6);(5,8);(6,9);(7,8);(8,9);(10,11);(11,12)]
};;

let myMaze2 = {
    rooms = [1;4;12;13;14];
    entrances = [1;12];
    exits = [4;14];
    passages = [(1,14)]
};;

let myMaze3 = {
    rooms = [1;2;3;4];
    entrances = [1];
    exits = [];
    passages = [(1,2);(2,3);(3,4)]
};;

let comb1 = {
    rooms = [14];
    entrances = [14];
    exits = [];
    passages = [(1,14)]
}

let valid1 = {
    rooms = [1];
    entrances = [1];
    exits = [];
    passages = []
};;

let comb2 = {
    rooms = [1; 2; 3; 4; 5; 6; 7; 8; 9; 10; 11; 12; 13];
    entrances = [1];
    exits = [2; 3; 4; 5; 6; 7; 8; 9; 10; 11; 12; 13];
    passages = [(1,2);(1,4);(1,5)]
}

let invalid1 = {
    rooms = [1];
    entrances = [];
    exits = [];
    passages = []
};;

let invalid2 = {
    rooms = [1; 2; 3; 4; 5];
    entrances = [1];
    exits = [5];
    passages = [(1,2);(2,3);(3,4);(4,5);(5,6)]
};;

let invalid3 = {
    rooms = [1; 2; 3; 4; 5];
    entrances = [1];
    exits = [1];
    passages = [(1,2);(2,3);(3,4);(4,5)]
};;

let invalid4 = {
    rooms = [1; 2; 3; 3; 4; 5];
    entrances = [1];
    exits = [5];
    passages = [(1,2);(2,3);(3,4);(4,5)]
};;

let invalid5 = {
    rooms = [1; 2; 3; 5; 4; 5];
    entrances = [1];
    exits = [5];
    passages = [(1,2);(2,3);(3,4);(4,5)]
};;

let loopMaze = {
    rooms = [1;2;3;4];
    entrances = [1];
    exits = [4];
    passages = [(1,2);(2,3);(3,4);(4,1)]
};;

let loopMaze2 = {
    rooms = [1;2;3;4];
    entrances = [1];
    exits = [4];
    passages = [(1,2);(2,1);(2,3);(3,4);(4,1)]
};;


let _sortIslands ll =
    List.sort_uniq compare (List.map (List.sort_uniq compare) ll);;

%END



%A01
%INPUT
isValid myMaze;;
isValid myMaze2;;
isValid myMaze3;;
isValid invalid1;;
%OUTPUT
- : bool = true
- : bool = true
- : bool = true
- : bool = false

%end

%A02
%INPUT
isValid myMaze;;
isValid loopMaze;;
isValid loopMaze2;;
isValid loopMaze3;;
isValid invalid1;;
%OUTPUT
- : bool = true
- : bool = true
- : bool = true
- : bool = true
- : bool = false

%end

%A03
%INPUT
isValid myMaze;;
isValid valid1;;
isValid invalid1;;
isValid invalid2;;
isValid invalid3;;
%OUTPUT
- : bool = true
- : bool = true
- : bool = false
- : bool = false
- : bool = false

%end

%A04
%INPUT
isValid myMaze;;
isValid valid1;;
isValid invalid4;;
isValid invalid5;;
%OUTPUT
- : bool = true
- : bool = true
- : bool = false
- : bool = false

%end

%B01
%INPUT
makeLineMaze 1 2;;
%OUTPUT
- : Maze.maze =
{rooms = [1; 2]; entrances = [1]; exits = [2]; passages = [(1, 2)]}

%end

%B02
%INPUT
makeLineMaze 1 9;;
%OUTPUT
- : Maze.maze =
{rooms = [1; 2; 3; 4; 5; 6; 7; 8; 9]; entrances = [1]; exits = [9];
 passages = [(1, 2); (2, 3); (3, 4); (4, 5); (5, 6); (6, 7); (7, 8); (8, 9)]}

%end

%B03
%INPUT
makeLineMaze 9 19;;
%OUTPUT
- : Maze.maze =
{rooms = [9; 10; 11; 12; 13; 14; 15; 16; 17; 18; 19]; entrances = [9];
 exits = [19];
 passages =
  [(9, 10); (10, 11); (11, 12); (12, 13); (13, 14); (14, 15); (15, 16);
   (16, 17); (17, 18); (18, 19)]}

%end

%B04
%INPUT
let m = makeLineMaze 1 100000 in
    (List.length m.passages, m);;
%OUTPUT
- : int * Maze.maze =
(99999,
 {rooms =
   [1; 2; 3; 4; 5; 6; 7; 8; 9; 10; 11; 12; 13; 14; 15; 16; 17; 18; 19; 20;
    21; 22; 23; 24; 25; 26; 27; 28; 29; 30; 31; 32; 33; 34; 35; 36; 37; 38;
    39; 40; 41; 42; 43; 44; 45; 46; 47; 48; 49; 50; 51; 52; 53; 54; 55; 56;
    57; 58; 59; 60; 61; 62; 63; 64; 65; 66; 67; 68; 69; 70; 71; 72; 73; 74;
    75; 76; 77; 78; 79; 80; 81; 82; 83; 84; 85; 86; 87; 88; 89; 90; 91; 92;
    93; 94; 95; 96; 97; 98; 99; 100; 101; 102; 103; 104; 105; 106; 107; 108;
    109; 110; 111; 112; 113; 114; 115; 116; 117; 118; 119; 120; 121; 122;
    123; 124; 125; 126; 127; 128; 129; 130; 131; 132; 133; 134; 135; 136;
    137; 138; 139; 140; 141; 142; 143; 144; 145; 146; 147; 148; 149; 150;
    151; 152; 153; 154; 155; 156; 157; 158; 159; 160; 161; 162; 163; 164;
    165; 166; 167; 168; 169; 170; 171; 172; 173; 174; 175; 176; 177; 178;
    179; 180; 181; 182; 183; 184; 185; 186; 187; 188; 189; 190; 191; 192;
    193; 194; 195; 196; 197; 198; 199; 200; 201; 202; 203; 204; 205; 206;
    207; 208; 209; 210; 211; 212; 213; 214; 215; 216; 217; 218; 219; 220;
    221; 222; 223; 224; 225; 226; 227; 228; 229; 230; 231; 232; 233; 234;
    235; 236; 237; 238; 239; 240; 241; 242; 243; 244; 245; 246; 247; 248;
    249; 250; 251; 252; 253; 254; 255; 256; 257; 258; 259; 260; 261; 262;
    263; 264; 265; 266; 267; 268; 269; 270; 271; 272; 273; 274; 275; 276;
    277; 278; 279; 280; 281; 282; 283; 284; 285; 286; 287; 288; 289; 290;
    291; 292; 293; 294; 295; ...];
  entrances = ...; exits = ...; passages = ...})

%end

%C01
%INPUT
combine myMaze myMaze;;
%OUTPUT
- : Maze.maze =
{rooms = [1; 2; 3; 4; 5; 6; 7; 8; 9; 10; 11; 12; 13]; entrances = [1; 4; 11];
 exits = [6; 12];
 passages =
  [(1, 2); (1, 4); (1, 5); (2, 5); (3, 6); (4, 5); (4, 7); (5, 6); (5, 8);
   (6, 9); (7, 8); (8, 9); (10, 11); (11, 12)]}

%end

%C02
%INPUT
combine myMaze comb1;;
%OUTPUT
- : Maze.maze =
{rooms = [1; 2; 3; 4; 5; 6; 7; 8; 9; 10; 11; 12; 13; 14];
 entrances = [1; 4; 11; 14]; exits = [6; 12];
 passages =
  [(1, 2); (1, 4); (1, 5); (1, 14); (2, 5); (3, 6); (4, 5); (4, 7); (5, 6);
   (5, 8); (6, 9); (7, 8); (8, 9); (10, 11); (11, 12)]}

%end

%C03
%INPUT
combine myMaze comb2;;
%OUTPUT
- : Maze.maze =
{rooms = [1; 2; 3; 4; 5; 6; 7; 8; 9; 10; 11; 12; 13]; entrances = [1; 4; 11];
 exits = [2; 3; 5; 6; 7; 8; 9; 10; 12; 13];
 passages =
  [(1, 2); (1, 4); (1, 5); (2, 5); (3, 6); (4, 5); (4, 7); (5, 6); (5, 8);
   (6, 9); (7, 8); (8, 9); (10, 11); (11, 12)]}

%end

%D01
%INPUT
next myMaze 5;;
%OUTPUT
- : Maze.rooms = [6; 8]

%end

%D02
%INPUT
next myMaze 13;;
%OUTPUT
- : Maze.rooms = []

%end

%E01
%INPUT
next2 myMaze [5];;
%OUTPUT
- : Maze.rooms = [6; 8]

%end

%E02
%INPUT
next2 myMaze [1;5;13];;
%OUTPUT
- : Maze.rooms = [2; 4; 5; 6; 8]

%end

%F01
%INPUT
prev myMaze 5;;
%OUTPUT
- : Maze.rooms = [1; 2; 4]

%end

%F02
%INPUT
prev myMaze 1;;
%OUTPUT
- : Maze.rooms = []

%end

%G01
%INPUT
adjacent myMaze 5;;
%OUTPUT
- : Maze.rooms = [1; 2; 4; 6; 8]

%end

%G02
%INPUT
adjacent myMaze 1;;
adjacent myMaze 12;;
adjacent myMaze 13;;
adjacent loopMaze3 1;;
%OUTPUT
- : Maze.rooms = [2; 4; 5]
- : Maze.rooms = [11]
- : Maze.rooms = []
- : Maze.rooms = [2; 100]

%end

%H01
%INPUT
reachable myMaze;;
%OUTPUT
- : Maze.rooms = [1; 2; 4; 5; 6; 7; 8; 9; 11; 12]

%end

%H02
%INPUT
reachable myMaze2;;
%OUTPUT
- : Maze.rooms = [1; 12; 14]

%end

%H03
%INPUT
reachable myMaze3;;
reachable valid1;;
%OUTPUT
- : Maze.rooms = [1; 2; 3; 4]
- : Maze.rooms = [1]

%end

%I01
%INPUT
solitary myMaze;;
%OUTPUT
- : Maze.rooms = [13]

%end

%I02
%INPUT
solitary myMaze2;;
%OUTPUT
- : Maze.rooms = [4; 12; 13]

%end

%I03
%INPUT
solitary myMaze3;;
%OUTPUT
- : Maze.rooms = []

%end

%J01
%INPUT
_sortIslands (islands myMaze);;
%OUTPUT
- : Maze.room list list = [[1; 2; 3; 4; 5; 6; 7; 8; 9]; [10; 11; 12]; [13]]

%end

%J02
%INPUT
_sortIslands (islands myMaze2);;
%OUTPUT
- : Maze.room list list = [[1; 14]; [4]; [12]; [13]]

%end

%J03
%INPUT
_sortIslands (islands myMaze3);;
_sortIslands (islands valid1);;
%OUTPUT
- : Maze.room list list = [[1; 2; 3; 4]]
- : Maze.room list list = [[1]]

%end

%K01
%INPUT
shortest myMaze;;
%OUTPUT
- : Maze.path = [11; 12]

%end

%K02
%INPUT
shortest myMaze2;;
%OUTPUT
- : Maze.path = [1; 14]

%end

%K03
%INPUT
shortest myMaze3;;
%OUTPUT
- : Maze.path = []

%end

%L01
%INPUT
List.sort_uniq compare (paths myMaze);;
%OUTPUT
- : Maze.path list =
[[1; 2; 5; 6]; [1; 2; 5; 6; 9]; [1; 2; 5; 8; 9]; [1; 4; 5; 6];
 [1; 4; 5; 6; 9]; [1; 4; 5; 8; 9]; [1; 4; 7; 8; 9]; [1; 5; 6]; [1; 5; 6; 9];
 [1; 5; 8; 9]; [4; 5; 6]; [4; 5; 6; 9]; [4; 5; 8; 9]; [4; 7; 8; 9]; [11; 12]]

%end

%L02
%INPUT
List.sort_uniq compare (paths myMaze2);;
%OUTPUT
- : Maze.path list = [[1; 14]; [12]]

%end

%L03
%INPUT
List.sort_uniq compare (paths myMaze3);;
%OUTPUT
- : Maze.path list = [[1; 2; 3; 4]]

%end

%M01
%INPUT
hasLoop myMaze;;
hasLoop loopMaze2;;
%OUTPUT
- : bool = false
- : bool = true

%end

%M02
%INPUT
hasLoop myMaze;;
hasLoop loopMaze3;;
hasLoop loopMaze4;;
%OUTPUT
- : bool = false
- : bool = true
- : bool = true

%end

%M3
%INPUT
hasLoop myMaze;;
hasLoop loopMaze5;;
%OUTPUT
- : bool = false
- : bool = true

%end

%N01
%INPUT
shortest2 myMaze;;
%OUTPUT
- : Maze.path = [11; 12]

%end

%N02
%INPUT
shortest2 loopMaze;;
shortest2 loopMaze2;;
%OUTPUT
- : Maze.path = [1; 2; 3; 4]
- : Maze.path = [1; 2; 3; 4]

%end

%N03
%INPUT
shortest2 loopMaze3;;
shortest2 loopMaze4;;
%OUTPUT
- : Maze.path =
[1; 2; 3; 4; 5; 6; 7; 8; 9; 10; 11; 12; 13; 14; 15; 16; 17; 18; 19; 20; 21;
 22; 23; 24; 25; 26; 27; 28; 29; 30; 31; 32; 33; 34; 35; 36; 37; 38; 39; 40;
 41; 42; 43; 44; 45; 46; 47; 48; 49; 50; 51; 52; 53; 54; 55; 56; 57; 58; 59;
 60; 61; 62; 63; 64; 65; 66; 67; 68; 69; 70; 71; 72; 73; 74; 75; 76; 77; 78;
 79; 80; 81; 82; 83; 84; 85; 86; 87; 88; 89; 90; 91; 92; 93; 94; 95; 96; 97;
 98; 99; 100]
- : Maze.path = [1; 2; 3; 4; 5; 6; 7; 8; 9; 10; 11; 12; 13; 14; 15; 16]

%end