## Ninety-Nine F# Problems - Problems 95 - 99 - Miscellaneous problems]

These are F# solutions of Ninety-Nine Haskell Problems which are themselves translations of Ninety-Nine Lisp Problems and Ninety-Nine Prolog Problems. The solutions are hidden so you can try to solve them yourself.

Tools:

### Ninety-Nine F# Problems - Problems 95 - 99 - Miscellaneous problems

``` 1: ///
2: /// These are F# solutions of Ninety-Nine F# Problems
4: /// which are themselves translations of Ninety-Nine Lisp Problems
5: /// (http://www.ic.unicamp.br/~meidanis/courses/mc336/2006s2/funcional/L-99_Ninety-Nine_Lisp_Problems.html)
6: /// and Ninety-Nine Prolog Problems
8: ///
9: /// If you would like to contribute a solution or fix any bugs, send
10: /// an email to paks at kitiara dot org with the subject "99 F# problems".
11: /// I'll try to update the problem as soon as possible.
12: ///
13: /// The problems have different levels of difficulty. Those marked with a single asterisk (*)
14: /// are easy. If you have successfully solved the preceeding problems you should be able to
15: /// solve them within a few (say 15) minutes. Problems marked with two asterisks (**) are of
16: /// intermediate difficulty. If you are a skilled F# programmer it shouldn't take you more than
17: /// 30-90 minutes to solve them. Problems marked with three asterisks (***) are more difficult.
18: /// You may need more time (i.e. a few hours or more) to find a good solution
19: ///
20: /// Though the problems number from 1 to 99, there are some gaps and some additions marked with
21: /// letters. There are actually only 88 problems.
22: ///```

### (**) Problem 95 : English number words

``` 1: /// On financial documents, like cheques, numbers must sometimes be written in full words.
2: /// Example: 175 must be written as one-seven-five. Write a predicate full-words/1 to print
3: /// (non-negative) integer numbers in full words.
4: ///
5: /// Example in F#:
6: ///
7: /// > fullWords 175;;
8: /// val it : string = "one-seven-five"
9:
10: (Solution)```

### (**) Problem 96 : Syntax checker

``` 1: /// In a certain programming language (Ada) identifiers are defined by the syntax diagram below.
2: ///
3: ///   ---->|letter|---+-------------------------------------+------>
4: ///                   |                                     |
5: ///                   +--------------+------>|letter|---+---+
6: ///                   |             / \                 |
7: ///                   +--->| - |---+   +---->|digit |---+
8: ///                   |                                 |
9: ///                   +---------------------------------+
10: ///
11: /// Transform the syntax diagram into a system of syntax diagrams which do not contain loops;
12: /// i.e. which are purely recursive. Using these modified diagrams, write a predicate
13: /// identifier/1 that can check whether or not a given string is a legal identifier.
14: ///
15: /// Example in Prolog:
16: /// % identifier(Str) :- Str is a legal identifier
17: ///
18: /// Example in F#:
19: ///
20: /// > identifier "this-is-a-long-identifier";;
21: /// val it : bool = true
22: /// > identifier "this-ends-in-";;
23: /// val it : bool = false
24: /// > identifier "two--hyphens";;
25: /// val it : bool = false
26:
27: (Solution 1)
28:
29: (Solution 2)```

### (***) Problem 97 : Sudoku

``` 1: /// Sudoku puzzles go like this:
2: ///
3: ///       Problem statement                 Solution
4: ///
5: ///        .  .  4 | 8  .  . | .  1  7          9  3  4 | 8  2  5 | 6  1  7
6: ///                |         |                          |         |
7: ///        6  7  . | 9  .  . | .  .  .          6  7  2 | 9  1  4 | 8  5  3
8: ///                |         |                          |         |
9: ///        5  .  8 | .  3  . | .  .  4          5  1  8 | 6  3  7 | 9  2  4
10: ///        --------+---------+--------          --------+---------+--------
11: ///        3  .  . | 7  4  . | 1  .  .          3  2  5 | 7  4  8 | 1  6  9
12: ///                |         |                          |         |
13: ///        .  6  9 | .  .  . | 7  8  .          4  6  9 | 1  5  3 | 7  8  2
14: ///                |         |                          |         |
15: ///        .  .  1 | .  6  9 | .  .  5          7  8  1 | 2  6  9 | 4  3  5
16: ///        --------+---------+--------          --------+---------+--------
17: ///        1  .  . | .  8  . | 3  .  6          1  9  7 | 5  8  2 | 3  4  6
18: ///                |         |                          |         |
19: ///        .  .  . | .  .  6 | .  9  1          8  5  3 | 4  7  6 | 2  9  1
20: ///                |         |                          |         |
21: ///        2  4  . | .  .  1 | 5  .  .          2  4  6 | 3  9  1 | 5  7  8
22: ///
23: /// Every spot in the puzzle belongs to a (horizontal) row and a (vertical) column, as well
24: /// as to one single 3x3 square (which we call "square" for short). At the beginning, some
25: /// of the spots carry a single-digit number between 1 and 9. The problem is to fill the
26: /// missing spots with digits in such a way that every number between 1 and 9 appears exactly
27: /// once in each row, in each column, and in each square.
28:
29: (Solution)```

### (***) Problem 98 : Nonograms

``` 1: /// Around 1994, a certain kind of puzzle was very popular in England. The "Sunday Telegraph"
2: /// newspaper wrote: "Nonograms are puzzles from Japan and are currently published each week
3: /// only in The Sunday Telegraph. Simply use your logic and skill to complete the grid and
4: /// reveal a picture or diagram." As a Prolog programmer, you are in a better situation: you
5: /// can have your computer do the work! Just write a little program ;-).
6: ///
7: /// The puzzle goes like this: Essentially, each row and column of a rectangular bitmap is
8: /// annotated with the respective lengths of its distinct strings of occupied cells. The
9: /// person who solves the puzzle must complete the bitmap given only these lengths.
10: ///
11: ///             Problem statement:          Solution:
12: ///             |_|_|_|_|_|_|_|_| 3         |_|X|X|X|_|_|_|_| 3
13: ///             |_|_|_|_|_|_|_|_| 2 1       |X|X|_|X|_|_|_|_| 2 1
14: ///             |_|_|_|_|_|_|_|_| 3 2       |_|X|X|X|_|_|X|X| 3 2
15: ///             |_|_|_|_|_|_|_|_| 2 2       |_|_|X|X|_|_|X|X| 2 2
16: ///             |_|_|_|_|_|_|_|_| 6         |_|_|X|X|X|X|X|X| 6
17: ///             |_|_|_|_|_|_|_|_| 1 5       |X|_|X|X|X|X|X|_| 1 5
18: ///             |_|_|_|_|_|_|_|_| 6         |X|X|X|X|X|X|_|_| 6
19: ///             |_|_|_|_|_|_|_|_| 1         |_|_|_|_|X|_|_|_| 1
20: ///             |_|_|_|_|_|_|_|_| 2         |_|_|_|X|X|_|_|_| 2
21: ///              1 3 1 7 5 3 4 3             1 3 1 7 5 3 4 3
22: ///              2 1 5 1                     2 1 5 1
23: ///
24: /// For the example above, the problem can be stated as the two lists [[3],[2,1],[3,2],[2,2]
25: /// ,[6],[1,5],[6],[1],[2]] and [[1,2],[3,1],[1,5],[7,1],[5],[3],[4],[3]] which give the
26: /// "solid" lengths of the rows and columns, top-to-bottom and left-to-right, respectively.
27: /// Published puzzles are larger than this example, e.g. 25 x 20, and apparently always have
28: /// unique solutions.
29: ///
30: /// Example in F#:
31: ///
32: /// > printfn "%s" <| nonogram [[3];[2;1];[3;2];[2;2];[6];[1;5];[6];[1];[2]]
33: ///                             [[1;2];[3;1];[1;5];[7;1];[5];[3];[4];[3]];;
34: /// |_|X|X|X|_|_|_|_| 3
35: /// |X|X|_|X|_|_|_|_| 2 1
36: /// |_|X|X|X|_|_|X|X| 3 2
37: /// |_|_|X|X|_|_|X|X| 2 2
38: /// |_|_|X|X|X|X|X|X| 6
39: /// |X|_|X|X|X|X|X|_| 1 5
40: /// |X|X|X|X|X|X|_|_| 6
41: /// |_|_|_|_|X|_|_|_| 1
42: /// |_|_|_|X|X|_|_|_| 2
43: ///  1 3 1 7 5 3 4 3
44: ///  2 1 5 1
45: ///
46:
47: (Solution needed)
48: ```

### (***) Problem 99 : Crossword puzzle

``` 1: /// Given an empty (or almost empty) framework of a crossword puzzle and a set of words. The
2: /// problem is to place the words into the framework.
3: ///
4: ///                P R O L O G     E
5: ///                E   N     N     M
6: ///                R   L i N U X   A
7: ///                L   i   F   M A C
8: ///                    N   S Q L   S
9: ///                    E
10: ///                  W E B
11: ///
12: /// The particular crossword puzzle is specified in a text file which first lists the words
13: /// (one word per line) in an arbitrary order. Then, after an empty line, the crossword
14: /// framework is defined. In this framework specification, an empty character location is
15: /// represented by a dot (.). In order to make the solution easier, character locations can
16: /// also contain predefined character values. The puzzle above is defined in the file
17: /// p99a.dat, other examples are p99b.dat and p99d.dat. There is also an example of a puzzle
18: /// (p99c.dat) which does not have a solution.
19: ///
20: /// Words are strings (character lists) of at least two characters. A horizontal or vertical
21: /// sequence of character places in the crossword puzzle framework is called a site. Our
22: /// problem is to find a compatible way of placing words onto sites.
23: ///
24: /// Hints: (1) The problem is not easy. You will need some time to thoroughly understand it.
25: /// So, don't give up too early! And remember that the objective is a clean solution, not
26: /// just a quick-and-dirty hack!
27: ///
28: /// (2) Reading the data file is a tricky problem for which a solution is provided in the
29: /// file p99-readfile.pl. See the predicate read_lines/2.
30: ///
31: /// (3) For efficiency reasons it is important, at least for larger puzzles, to sort the
32: /// words and the sites in a particular order. For this part of the problem, the solution
33: /// of P28 may be very helpful.
34: ///
35: /// Example in F#:
36: ///
37: /// ALPHA
38: /// ARES
39: /// POPPY
40: ///
41: ///   .
42: ///   .
43: /// .....
44: ///   . .
45: ///   . .
46: ///     .
47: /// > solve \$ readCrossword "ALPHA\nARES\nPOPPY\n\n  .  \n  .  \n.....\n  . .\n  . .\n    .\n"
48: ///
49: /// [[((3,1),'A');((3,2),'L');((3,3),'P');((3,4),'H');((3,5),'A');((1,3),'P');((2,3)
50: /// ,'O');((3,3),'P');((4,3),'P');((5,3),'Y');((3,5),'A');((4,5),'R');((5,5),'E');((
51: /// 6,5),'S')]]
52:
53: (Solution needed)
54: ```
let fullWords (n: int) =
let words = [| "zero"; "one"; "two"; "three"; "four"; "five"; "six"; "seven"; "eight"; "nine" |]
let digits = n.ToString() |> Seq.map (fun c -> int c - int '0') |> Seq.map (fun c -> words.[c])|> Array.ofSeq
System.String.Join("-", digits)
// identifier = letter((-)?(letter|digit))*
// Some people, when confronted with a problem, think "I know, I'll use regular expressions." Now they have two problems. - Jamie Zawinski
let identifier expr = System.Text.RegularExpressions.Regex.IsMatch(expr,@"^([a-z]|[A-Z])((\-)?([0-9]|[a-z]|[A-Z]))*\$")
// This is the overkill solution using a parser combinator.
// For a solution using fslex and fsyacc go here: https://github.com/paks/99-FSharp-Problems/tree/master/P96
// The combinator came from here: http://v2matveev.blogspot.com/2010/05/f-parsing-simple-language.html
type 'a ParserResult = Success of 'a * char list | Failed

type 'a Parser = Parser of (char list -> 'a ParserResult)

let apply (Parser p) s = p s

let run p l = apply p (Seq.toList l)

let one v = Parser(fun cs -> Success(v,cs))
let fail() = Parser(fun _ -> Failed)

let bind p f = Parser (fun cs ->
match apply p cs with
| Success(r, cs2) -> apply (f r) cs2
| Failed -> Failed)

let choose f p = Parser(fun cs ->
match cs with
| c::cs when f c -> Success(p c, cs)
| _ -> Failed)

let (<|>) p1 p2 = Parser(fun cs ->
match apply p1 cs with
| Failed -> apply p2 cs
| result -> result)

let (<&>) p1 p2 = Parser(fun cs ->
match apply p1 cs with
| Success(_, cs2) -> apply p2 cs2
| Failed -> Failed)

let letter = choose System.Char.IsLetter id

let letterOrDigit = choose System.Char.IsLetterOrDigit id

let hiphen = choose ((=) '-') id

type ParseBuilder() =
member parser.Return(v) = one v
member parser.Bind(p, f) = bind p f
member parser.ReturnFrom(p) = p
member parser.Zero() = fail()

let parser = new ParseBuilder()

let rec zeroOrMany p f v0 =
parser {
return! oneOrMany p f v0 <|> one v0
}

and oneOrMany p f v0 =
parser {
let! v1 = p
return! zeroOrMany p f (f v0 v1)
}

let hiphenLetterOrDigit = (hiphen <&> letterOrDigit) <|> letterOrDigit

let identifierP = parser {
let! l = letter
let sb = new System.Text.StringBuilder(l.ToString())
let! rest = sb |> zeroOrMany hiphenLetterOrDigit (fun acc v -> acc.Append(v))
return rest.ToString()
}

let identifier' str =
match run identifierP str with
| Success(_,[]) -> true //if the parser consumed all the input, then it's an identifier
| _ -> false
let solution97 = "https://github.com/paks/ProjectEuler/blob/master/Euler2/P96/sudoku.fs"
let solution98 = "your solution here!!"
let solution99 = "your solution here!!"