Moving Up in life.. and to the Right

c-delannoy.fs

open System

/// Returns a tuple of the first two elements of an array.
let head2 (a : 'a array) = a.[0], a.[1]

/// Reads a line from standard input, and verifies it is of the given length.
let readln length =
  let line = Console.ReadLine() in
  if line.Length = length then line else sprintf "Invalid line length: %s" line |> failwith

/// Calculates the (a, b)th Delannoy number.
let rec del = function
  | (0L, _) | (_, 0L) -> 1L
  | (a, b) -> del (a - 1L, b) + del (a - 1L, b - 1L) + del (a, b - 1L)

/// Calculates the number of path combinations in the given input lines.
/// Nasty int64 conversion malarkey because the numbers get large quickly.
let rec combs i j (c : int64) = function
  | [] -> c
  | (x :: xs) : string list as s -> match x.IndexOf('X') with
                      | -1           -> combs i (j + 1) c xs
                      | x when x < i -> 0L
                      | i_           -> let _i = x.LastIndexOf('X') in
                                        combs _i 0 (if c = 0L then 1L else c * del (i_ - i |> int64, j + 1 |> int64)) xs

[<EntryPoint>]
let main argv = 
    let (width, height) = Console.ReadLine().Split(',') |> Array.map int |> head2 in
    let count = List.init height (fun _ -> readln width) |> List.rev |> combs 0 0 0L in
    (if count = 0L then "No Xs on grid, or impossible solution." else string count) |> printfn "%s"
    Console.ReadKey(); 0