blob: ad177db2b011aad0403bedd859e79c9a10dfa63c (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
|
namespace Common
module Util =
open System.Globalization
open FParsec
open FSharpPlus
open FSharpPlus.Math.Generic
let parse parser input =
match run parser input with
| Success (result, _, _) -> result
| _ -> failwith "Invalid input format!"
let countDistinct xs = xs |> Set |> Set.count
let countWhere pred = Seq.filter pred >> Seq.length
let charToInt = CharUnicodeInfo.GetDigitValue
let wrapInRangeInc lower upper x =
lower + remE (x - lower) (upper - lower + 1)
let cutInHalf xs =
let half = Seq.length xs / 2
[ Seq.take half xs; Seq.skip half xs ]
let splitStringToTuple sep string =
match Seq.toList <| String.split [ sep ] string with
| [ x; y ] -> x, y
| _ -> failwith "Invalid string format!"
let matrixToString matrix =
matrix
|> Seq.map (Seq.map string >> String.concat "")
|> String.concat "\n"
let mapEachToSeq mapping matrix =
seq {
for row in 0 .. Array2D.length1 matrix - 1 do
for col in 0 .. Array2D.length2 matrix - 1 -> mapping matrix (Vec2(col, row)) matrix[row, col]
}
let mAt matrix (Vec2 (col, row)) = Array2D.get matrix row col
let rec composition n f x =
if n = 0 then
x
else
composition (n - 1) f (f x)
let notIn set element = not <| Set.contains element set
let updateMax key newValue map =
map
|> Map.add key (max newValue (map |> Map.tryFind key |> Option.defaultValue 0))
let rec insertSorted x =
function
| h :: t -> min h x :: (insertSorted (max h x) t)
| [] -> [ x ]
let liftList xs =
match List.forall Option.isSome xs with
| true -> Some(List.map Option.get xs)
| false -> None
let cycle =
function
| h :: t -> h, t @ [ h ]
| [] -> failwith "Empty list!"
let tsort graph =
let dfs =
let rec explore path result node =
if List.contains node path then
failwith "Cycle found!"
elif List.contains node result then
result
else
node
:: List.fold (explore (node :: path)) result (Map.find node graph)
explore []
graph |> Map.keys |> Seq.fold dfs [] |> List.rev
let topN n xs =
Seq.fold
(fun acc x ->
if List.length acc < n then
insertSorted x acc
elif List.head acc < x then
insertSorted x <| List.tail acc
else
acc)
List.empty
xs
|
