### Code Snippet:

```
1 module Helpers =
2 let permutations ls =
3 let rec insertions x = function
4 | [] -> [[x]]
5 | (y :: ys) as l -> (x::l)::(List.map (fun x -> y::x) (insertions x ys))
6 let rec permutations' = function
7 | [] -> seq [ [] ]
8 | x :: xs -> Seq.concat (Seq.map (insertions x) (permutations' xs))
9 ls |> permutations'
10
11 module PrisonersHatsPuzzle =
12 type Hat = Red | Blue
13 type Prisoner = Hat
14 type Prisoners = Prisoner * Prisoner * Prisoner * Prisoner
15 type Guess = Prisoners -> Prisoner * Hat
16
17 // Bullet-proof logic for the prisoners to always go free:
18 //
19 // As the fourth prisoner is behind a screen, we don't care about him.
20 // If the last prisoner sees two equal colored hats, he knows he has the
21 // the opposite and hereby he can call out the color.
22 // In case the last prisoner doesn't call out his color, the second from
23 // behind will know that he doesn't have the same color hat as the prisoner
24 // in front of him, else the last one would have called it, hereby, he
25 // can safely call out the opposite color of the prisoners hat in
26 // front of him.
27 //
28 let guess : Guess =
29 fun prisoners ->
30 let a,b,c,d = prisoners
31 match a,b,c,d with
32 | (_,Red,Red,_) -> a,Blue
33 | (_,Blue,Blue,_) -> a,Red
34 | (_,_,Blue,_) -> b,Red
35 | (_,_,Red,_) -> b,Blue
36
37 open Helpers
38 open PrisonersHatsPuzzle
39
40 let hats = [Hat.Red; Hat.Blue; Hat.Red; Hat.Blue;]
41
42 let alwaysGoFree =
43 permutations hats
44 |> Seq.map(fun xs ->
45 match xs with
46 | a::b::c::d::[] -> a,b,c,d
47 | _ -> failwith "never")
48 |> Seq.map(fun x -> guess x)
49 |> Seq.toArray
```

### Code output:

```
module Helpers = begin
val permutations : ls:'a list -> seq<'a list>
end
module PrisonersHatsPuzzle = begin
type Hat =
| Red
| Blue
type Prisoner = Hat
type Prisoners = Prisoner * Prisoner * Prisoner * Prisoner
type Guess = Prisoners -> Prisoner * Hat
val guess : Prisoner * Prisoner * Prisoner * Prisoner -> Prisoner * Hat
end
val hats : Hat list = [Red; Blue; Red; Blue]
val alwaysGoFree : (Prisoner * Hat) [] =
[|(Blue, Blue); (Blue, Blue); (Blue, Blue); (Red, Red); (Red, Red);
(Red, Red); (Blue, Blue); (Red, Red); (Red, Red); (Red, Red); (Blue, Blue);
(Red, Red); (Red, Red); (Red, Red); (Blue, Blue); (Blue, Blue); (Red, Red);
(Red, Red); (Blue, Blue); (Blue, Blue); (Blue, Blue); (Blue, Blue);
(Blue, Blue); (Red, Red)|]
```

### References:

- Wikipedia: Prisoners and hats puzzle