Submitted via CLI

Iteration 1

Latest
Published
Submitted via CLI,
  • 1
    module Dominoes
  • 2
  • 3
    type Domino = int * int
  • 4
  • 5
    // same as "exists euler cycle in graph with
  • 6
    // dominos-edges and numbers-vertices"
  • 7
    // rus: https://neerc.ifmo.ru/wiki/index.php?title=Эйлеровость_графов
  • 8
    let rec canChain (input: Domino list) =
  • 9
    let ``all vertices have even degree`` =
  • 10
    input
  • 11
    |> List.collect (fun (x, y) -> [x; y])
  • 12
    |> List.groupBy id
  • 13
    |> List.forall (fun (x, xs) -> (xs |> List.length) % 2 = 0)
  • 14
  • 15
    let ``graph is connected`` =
  • 16
    match input with
  • 17
    | [] -> true
  • 18
    | _ ->
  • 19
    let vertices =
  • 20
    input
  • 21
    |> List.collect (fun (x, y) -> [x; y])
  • 22
    |> List.distinct
  • 23
  • 24
    let vertice x = vertices |> List.findIndex ((=) x)
  • 25
  • 26
    let graph =
  • 27
    let graph = Array2D.zeroCreate<bool> vertices.Length vertices.Length
  • 28
    input
  • 29
    |> List.iter (fun (x, y) ->
  • 30
    graph.[vertice x, vertice y] <- true
  • 31
    graph.[vertice y, vertice x] <- true)
  • 32
    [
  • 33
    for rowI in graph.GetLowerBound 0 .. graph.GetUpperBound 0 do
  • 34
    yield
  • 35
    graph.[rowI, *]
  • 36
    |> List.ofArray
  • 37
    |> List.mapi (fun i x -> i, x)
  • 38
    |> List.filter (fun (i, x) -> x)
  • 39
    |> List.map fst
  • 40
    ]
  • 41
  • 42
    let rec dfs (visited:bool []) u =
  • 43
    visited.[u] <- true
  • 44
  • 45
    let sum =
  • 46
    graph.[u]
  • 47
    |> Seq.filter (fun v -> not visited.[v])
  • 48
    |> Seq.sumBy (dfs visited)
  • 49
  • 50
    1 + sum
  • 51
  • 52
    let visited = Array.zeroCreate<bool> vertices.Length
  • 53
  • 54
    dfs visited 0 = vertices.Length
  • 55
  • 56
    ``all vertices have even degree`` && ``graph is connected``
Loading data

0 comments

No one has commented on this solution.

Be the first to add your comment!

Loading data