3 people like it.

Like the snippet!

## 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.

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

1: /// 2: /// These are F# solutions of Ninety-Nine F# Problems 3: /// (http://www.haskell.org/haskellwiki/H-99:_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 7: /// (https://sites.google.com/site/prologsite/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)

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]))*$")

// 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

// 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!!"

### More information

Link: |
http://fssnip.net/ax |

Posted: |
3 years ago |

Author: |
Cesar Mendoza (website) |

Tags: |
Ninety-Nine F# Problems, tutorial, F# |