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``
About this solution
We automatically group similar solutions and generate statistics about how popular they are.
1
Submission
4y ago
First submitted
Max track rep
0 comments
No one has commented on this solution.
Be the first to add your comment!