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)

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

More information

Link:	http://fssnip.net/ax
Posted:	1 years ago
Author:	Cesar Mendoza (website)
Tags:	Ninety-Nine F# Problems, tutorial, F#