Week 9: programming assignments from week 8¶

Q8.1¶

Question:

Write an OCaml function that will substitute all occurrences of an element in a list by a different element. The argument will have small-to-moderate size and performance considerations are not critical.

# replace;;
- : 'a -> 'a -> 'a list -> 'a list = <fun>
# replace 2 0 [1;2;3;4;3;2;1];;
- : int list = [1; 0; 3; 4; 3; 0; 1]

We found this in the tutorial:

let rec replace a b l = match l with
| [] -> []
| x :: xs -> if x = a
then b :: (replace a b xs)
else x :: (replace a b xs)

Q8.2¶

Question:

Write an OCaml function that splits a list into list segments containing only identical elements. The function must work on small-to-moderate size lists. Performance of implementation is not critical.

# split;;
- : 'a list -> 'a list list = <fun>
# split [1;2;2;3;3;3;4;4;5;6];;
- : int list list = [[1]; [2; 2]; [3; 3; 3]; [4; 4]; [5]; [6]]
# split [];;
- : 'a list list = []
# split [1];;
- : int list list = [[1]]
# split [1;2;3;3;2;2;1;1];;
- : int list list = [[1]; [2]; [3; 3]; [2; 2]; [1; 1]]

We found this in the tutorial:

let rec split l = match l with
| [] -> []
| x :: xs -> let ys = split xs in
match ys with
| [] -> [[x]]
| z :: zs -> if x = List.hd z then (x :: z) :: zs
else [x] :: ys
;;

Q8.3a¶

Question:

You are given two lists that have as elements either integers or characters. The characters stand for variables of unknown values. You need to solve the following puzzle: Is there a way to give values to variables so that the two lists are equal?

For example [x, 1, x] and [3, y, 3] is solvable for x = 3 and y = 1 whereas [x, x, 0] and [1, 2, z] is not solvable.

Your task is to write an OCaml function that checks whether a puzzle is solvable or not.

type puzzle = K of int | U of char

# solvable;;
- : puzzle list -> puzzle list -> bool = <fun>

# solvable [U 'x'; K 1; U 'x'] [K 3; U 'y'; K 3] ;;
- : bool = true
# solvable [U 'x'; U 'x'; K 0] [K 1; K 2; U 'z'];;
- : bool = false

In the below solutions, I have fixed a bug since the tutorial.

We found this in the tutorial:

let rec solvable xs ys = match xs, ys with
| [], [] -> true
| [], (c :: cs) -> false
| (b :: bs), [] -> false
| (b :: bs), (c :: cs) ->
match b, c with
| K b', K c' -> (b' = c') && (solvable bs cs)
| U b', K c' -> solvable (replace (U b') (K c') bs) (replace (U b') (K c') cs)
| K b', U c' -> solvable (replace (U c') (K b') bs) (replace (U c') (K b') cs)
| U b', U c' -> solvable (replace (U b') (U c') bs) (replace (U b') (U c') cs);;

Alternatively, this:

let rec solvable xs ys = match xs, ys with
| [], [] -> true
| [], (c :: cs) -> false
| (b :: bs), [] -> false
| (b :: bs), (c :: cs) ->
match b, c with
| K b', K c' -> (b' = c') && (solvable bs cs)
| U b', K c' -> solvable (replace (U b') c bs) (replace (U b') c cs)
| K b', U c' -> solvable (replace (U c') b bs) (replace (U c') b cs)
| U b', U c' -> solvable (replace (U b') c bs) (replace (U b') c cs);;

Alternatively, this:

let rec solvable xs ys = match xs, ys with
| [], [] -> true
| [], (c :: cs) -> false
| (b :: bs), [] -> false
| (b :: bs), (c :: cs) ->
match b, c with
| K b', K c' -> (b' = c') && (solvable bs cs)
| U b', _ -> solvable (replace (U b') c bs) (replace (U b') c cs)
| _, U c' -> solvable (replace (U c') b bs) (replace (U c') b cs);;

In a sense, this is nicer because we have fewer cases. But it’s a matter of taste.

Alternatively, this:

let rec solvable xs ys = match xs, ys with
| [], [] -> true
| [], (c :: cs) -> false
| (b :: bs), [] -> false
| (b :: bs), (c :: cs) ->
match b with
| K b' -> (match c with
| U c' -> solvable (replace (U c') (K b') bs) (replace (U c') (K b') cs)
| K c' -> b' = c' && (solvable bs cs))
| U b' -> solvable (replace (U b') c bs) (replace (U b') c cs);;

(In the last program, I had to add parentheses around the inner match otherwise OCaml would think that | U b' belonged to the inner match.)