text:
### A Pluto.jl notebook ###
# v0.15.1

using Markdown
using InteractiveUtils

# This Pluto notebook uses @bind for interactivity. When running this notebook outside of Pluto, the following 'mock version' of @bind gives bound variables a default value (instead of an error).
macro bind(def, element)
    quote
        local el = $(esc(element))
        global $(esc(def)) = Core.applicable(Base.get, el) ? Base.get(el) : missing
        el
    end
end

# ╔═╡ 8c64d70d-f46b-4ae4-9b43-53d7fd461efe
begin
	using PlutoUI
	using DataStructures
	using LightGraphs
	using Plots
	using GraphRecipes
end

# ╔═╡ 94e5f9f8-f157-11eb-2b69-6d7253ae9cf9
md"""
# Chapter 13
#### Nicetak
 $(import Dates; Dates.format(Dates.today(), Dates.DateFormat("U d, Y")))
"""

# ╔═╡ 5ee0cdc1-ac4b-4664-b350-daa3c3179806
md"""
## 13.1
無向グラフの連結成分の個数を数える問題を深さ優先探索または幅優先探索を用いて解いてください.
"""

# ╔═╡ f535e226-0c5c-47d5-ab6b-d3590ba14e4d
function f₁(G)
	n = length(G)
	dists = -ones(Int, n)
	que = Queue{Int}()

	ans = 0
	for v = 1:n
		if dists[v] == -1
			dists[v] = 0
			enqueue!(que, v)
			while !isempty(que)
				w = dequeue!(que)
				for x ∈ G[w]
					if dists[x] == -1
						dists[x] = dists[w] + 1
						enqueue!(que, x)
					end
				end
			end
			ans += 1
		end
	end

	return ans
end

# ╔═╡ f3577938-4381-45a5-88b2-ab06f0f16529
function edges_to_graph(edges, n; is_directed=false)
	m = size(edges)[1]
	G = [Vector{Int}() for _ in 1:n]

	for i in 1:m
		src, dst = edges[i, 1], edges[i, 2]
		push!(G[src], dst)
		!is_directed && push!(G[dst], src)
	end

	return G
end

# ╔═╡ d8d0fddf-2853-4fa0-bc3a-585773b58a3b
begin
	edges = [
			1 2
			2 3
			3 1
			4 5
			5 6
			7 8
		]
	G = edges_to_graph(edges, 8)
	graphplot(G,
		names=1:8,
		curves=false,
		nodeshape=:circle,
		fontsize=20,
		title="Number of Connected Blocks is $(f₁(G))")
end

# ╔═╡ f6899ade-339e-4365-8dd5-c229dc9db42f
md"""
## 13.2
コード13.4では, グラフ$G = (V, E)$上の2頂点$s, t \in V$に対してs-tパスが存在するかどうかを判定しています. これを幅優先探索によって実装してください.
"""

# ╔═╡ b60d06df-a58f-4a6f-9afc-b46478f4c142
function f₂(G; s, t)
	n = length(G)
	dists = -ones(Int, n)
	que = Queue{Int}()
	dists[s] = 0; enqueue!(que, s)
	while !isempty(que)
		v = dequeue!(que)
		for x ∈ G[v]
			if dists[x] == -1
				dists[x] = dists[v] + 1
				enqueue!(que, x)
			end
		end
	end

	if dists[t] != -1
		return "Yes"
	else
		return "No"
	end
end

# ╔═╡ 1daa8e24-e917-4a46-b6b9-853e89e330ef
with_terminal() do
	@show f₂(G, s = 1, t= 3)
	@show f₂(G, s = 1, t = 6)
end

# ╔═╡ 5bff4f06-5657-4fbd-9114-ac1fc5026c5d
md"""
## 13.3
コード13.5では, 無向グラフ$G=(V, E)$が二部グラフかどうかを判定しています. これを幅優先探索によって実装してください.
"""

# ╔═╡ 5f1297fe-1368-4695-99a0-a26582fe53da
function f₃(G)
	n = length(G)
	dists = -ones(Int, n)
	que = Queue{Int}()
	is_bipartite = true

	for v in 1:n
		if dists[v] == -1
			dists[v] = 0; enqueue!(que, v)
			while !isempty(que)
				w = dequeue!(que)
				for x ∈ G[w]
					if dists[x] == -1
						dists[x] = dists[w] + 1
						enqueue!(que, x)
					else
						if dists[w] == dists[x]
							is_bipartite = false
						end
					end
				end
			end
		end
	end

	if is_bipartite
		return "Yes"
	else
		return "No"
	end
end

# ╔═╡ 8e5274a8-b024-4a47-a630-5206de4a82cd
begin
	edges₃ = [
			1 2
			2 3
			1 4
			2 5
			4 5
			4 8
			6 7
			6 8
		]
	G₃ = edges_to_graph(edges₃, 8)
	graphplot(G₃,
		names=1:8,
		curves=false,
		nodeshape=:circle,
		markercolor = [:orange, :skyblue, :orange,
			:skyblue, :orange, :skyblue, :orange, :orange],
		fontsize=20,
		title="Is Bipartite? - $(f₃(G₃)).")
end

# ╔═╡ 60029bce-d61d-4feb-bfe2-ad0623c30fb4
md"""
## 13.4
1.2.2節で見たような迷路について, 迷路のサイズをH×Wとして, スタートからゴールまでたどり着く最短路を$O(HW)$で求めるアルゴリズムを設計してください.
"""

# ╔═╡ 96f1ac18-95c9-47a1-b4b8-f0ebfc24a762
mutable struct Puzzle
	height::Int
	width::Int
	xₛ::Int
	yₛ::Int
	xₑ::Int
	yₑ::Int
	M::Array{Bool, 2}
end

# ╔═╡ 2991eb47-6667-474d-9967-126d2fdf9f09
function str_to_puzzle(s)
	ls = split(s, "\n")
	height, width = parse.(Int, split(ls[1]))

	xₛ, yₛ, xₑ, yₑ = 0, 0, 0, 0
	M = trues(height, width)

	for i = 1:height, j = 1:width
		e =ls[i+1][j]
		if e == '#'
			M[i, j] = false
		elseif e == 'S'
			xₛ, yₛ = i, j
		elseif e == 'G'
			xₑ, yₑ = i, j
		end
	end

	return Puzzle(height, width, xₛ, yₛ, xₑ, yₑ, M)
end

# ╔═╡ b612f9b9-3128-446f-8940-1c4d86df64db
function f₄(pz::Puzzle)
	dx = [1, 0, -1, 0]
	dy = [0, 1, 0, -1]

	dists = -ones(Int, pz.height, pz.width)
	dists[pz.xₛ, pz.yₛ] = 0

	prevs_x = -ones(Int, pz.height, pz.width)
	prevs_y = similar(prevs_x)

	que = Queue{Tuple{Int, Int}}()
	enqueue!(que, (pz.xₛ, pz.yₛ))

	while !isempty(que)
		x, y = dequeue!(que)
		for d = 1:4
			x′ = x + dx[d]
			y′ = y + dy[d]
			if 1 ≤ x′ ≤ pz.width && 1 ≤ y′ ≤ pz.height &&
				pz.M[x′, y′] && dists[x′, y′] == -1

				enqueue!(que, (x′, y′))
				dists[x′, y′] = dists[x, y] + 1
				prevs_x[x′, y′] = x
				prevs_y[x′, y′] = y

			end
		end
	end

	n = dists[pz.xₑ, pz.yₑ]
	steps = [(0, 0) for _ = 1:n+1]
	steps[n+1] = (pz.xₑ, pz.yₑ)
	for i = n+1:-1:2
		x, y = steps[i]
		steps[i-1] = (prevs_x[x, y], prevs_y[x, y])
	end

	return steps, dists
end

# ╔═╡ 288312ad-71d5-40c8-adad-8fba1f987d98
md"""
Distance $( @bind show_dist CheckBox())
Path $( @bind show_path CheckBox())
"""

# ╔═╡ 0e523d1f-9b05-46ae-a5f2-d6b6930ba0eb
let
	s = "8 8
.#....#G
.#.#....
...#.##.
#.##...#
...###.#
.#.....#
...#.#..
S......."

	pz = str_to_puzzle(s)
	steps, dists = f₄(pz)

	# Map
	rectangle(w, h, x, y) = Shape(x .+ [0,w,w,0], y .+ [0,0,h,h])
	plot()
	for i = 1:pz.height, j = 1:pz.width
		if i == pz.xₛ && j == pz.yₛ
			plot!(rectangle(1,1,j, pz.height+1 - i), opacity=.2, color = :blue)
		elseif i == pz.xₑ && j == pz.yₑ
			plot!(rectangle(1,1,j, pz.height+1 - i), opacity=.2, color = :orange)
		elseif pz.M[i, j]
			plot!(rectangle(1,1,j, pz.height+1 - i), opacity=.2, color = :white)
		else
			plot!(rectangle(1,1,j, pz.height+1 - i), opacity=.5, color = :black)
		end
	end

	# Distance
	if show_dist
		for i = 1:pz.height, j = 1:pz.width
			pz.M[i, j] && annotate!(j+.5, pz.height + 1 - i+.5, dists[i, j])
		end
	else
		annotate!(pz.yₛ + .5, pz.height + 1 - pz.xₛ + .5, "S")
		annotate!(pz.yₑ + .5, pz.height + 1 - pz.xₑ + .5, "G")
	end

	# Path
	if show_path
		for i in 1:length(steps)-1
			plot!([steps[i+1][2]+.5, steps[i][2]+.5],
				pz.height+2 .- [steps[i+1][1]+.5, steps[i][1]+.5],
				opacity=.5,
				color = :red,
				linewidth = 4
			)
		end
	end

	# Plot
	plot!(legend=false,
		aspectratio=1,
		xlims=(1,pz.width+1),
		ylims=(1,pz.height+1),
		axis=nothing)
end

# ╔═╡ 137942e1-2815-4bc4-9ba2-8efa48113a32
md"""
## 13.5
コード13.6のトポロジカルソートを幅優先探索によって実装してください.
"""

# ╔═╡ f0fee254-67e7-4e54-9dff-529dca6d9dae
function f₅(G)
	n = length(G)

	# Create Reversed Graph G′
	G′ = [Vector{Int}() for _ in 1:n]
	for i = 1:n, e ∈ G[i]
		push!(G′[e], i)
	end

	num_ins = [length(g) for g ∈ G]

	que = Queue{Int}()
	for i = 1:n
		num_ins[i] == 0 && enqueue!(que, i)
	end

	ans = MutableLinkedList{Int}()
	while !isempty(que)
		now = dequeue!(que)
		pushfirst!(ans, now)
		for e ∈ G′[now]
			num_ins[e] -= 1
			num_ins[e] == 0 && enqueue!(que, e)
		end
	end

	return collect(ans)
end

# ╔═╡ 87d201d1-00c3-4d90-84b7-e7b989902bba
let
	edges = [
		1 6
		2 4
		2 7
		3 6
		3 8
		4 1
		4 8
		5 2
		5 3
		5 7
		7 8
		8 1
	]

	G = edges_to_graph(edges, 8, is_directed=true)
	graphplot(G,
		names=0:7,
		curves=false,
		nodeshape=:circle,
		fontsize=20,
		title="Topological Sort \n$(f₅(G) .- 1)")

end

# ╔═╡ a5a7bb2e-f278-418d-96dc-e10a01392550
md"""
## 13.6
有向グラフ$G=(V, E)$が有向サイクルを含むかどうかを判定し, 含むならば具体的に1つ求めるアルゴリズムを設計してください.
"""

# ╔═╡ ac9fa9a8-72dd-4ca5-964f-16aa231f4d96
begin
	function f₆(G)
		n = length(G)
		seens = falses(n)
		fins = falses(n)
		st_hist = Stack{Int}()
		has_cycle = false

		function dfs(G, v)
			seens[v] = true
			push!(st_hist, v)

			for v′ ∈ G[v]
				if fins[v′]
					#Skip
				elseif seens[v′] && !fins[v′]
					has_cycle = true
					return
				else
					dfs(G, v′)
					has_cycle && return
				end
			end

			pop!(st_hist)
			fins[v] = true

			return
		end

		for i = 1:n
			if !fins[i]
				dfs(G, i)
			end

			has_cycle && break
		end

		return collect(st_hist)
	end

end

# ╔═╡ 662bce03-e461-4e7c-9827-f327c7da6754
let
	edges = [
		1 6
		2 4
		2 7
		3 6
		3 8
		4 1
		4 8
		5 2
		5 3
		7 5
		7 8
		8 1
	]

	G = edges_to_graph(edges, 8, is_directed=true)
	graphplot(G,
		names=0:7,
		curves=false,
		nodeshape=:circle,
		fontsize=20,
		title="Cycle: $(f₆(G) .- 1)")

end

# ╔═╡ 00000000-0000-0000-0000-000000000001
PLUTO_PROJECT_TOML_CONTENTS = """
[deps]
DataStructures = "864edb3b-99cc-5e75-8d2d-829cb0a9cfe8"
GraphRecipes = "bd48cda9-67a9-57be-86fa-5b3c104eda73"
LightGraphs = "093fc24a-ae57-5d10-9952-331d41423f4d"
Plots = "91a5bcdd-55d7-5caf-9e0b-520d859cae80"
PlutoUI = "7f904dfe-b85e-4ff6-b463-dae2292396a8"

[compat]
DataStructures = "~0.18.9"
GraphRecipes = "~0.5.7"
LightGraphs = "~1.3.5"
Plots = "~1.19.4"
PlutoUI = "~0.7.9"
"""

# ╔═╡ 00000000-0000-0000-0000-000000000002
PLUTO_MANIFEST_TOML_CONTENTS = """
# This file is machine-generated - editing it directly is not advised

[[AbstractTrees]]
git-tree-sha1 = "03e0550477d86222521d254b741d470ba17ea0b5"
uuid = "1520ce14-60c1-5f80-bbc7-55ef81b5835c"
version = "0.3.4"

[[Adapt]]
deps = ["LinearAlgebra"]
git-tree-sha1 = "84918055d15b3114ede17ac6a7182f68870c16f7"
uuid = "79e6a3ab-5dfb-504d-930d-738a2a938a0e"
version = "3.3.1"

[[ArgTools]]
uuid = "0dad84c5-d112-42e6-8d28-ef12dabb789f"

[[ArnoldiMethod]]
deps = ["LinearAlgebra", "Random", "StaticArrays"]
git-tree-sha1 = "f87e559f87a45bece9c9ed97458d3afe98b1ebb9"
uuid = "ec485272-7323-5ecc-a04f-4719b315124d"
version = "0.1.0"

[[Artifacts]]
uuid = "56f22d72-fd6d-98f1-02f0-08ddc0907c33"

[[AxisAlgorithms]]
deps = ["LinearAlgebra", "Random", "SparseArrays", "WoodburyMatrices"]
git-tree-sha1 = "a4d07a1c313392a77042855df46c5f534076fab9"
uuid = "13072b0f-2c55-5437-9ae7-d433b7a33950"
version = "1.0.0"

[[Base64]]
uuid = "2a0f44e3-6c83-55bd-87e4-b1978d98bd5f"

[[Bzip2_jll]]
deps = ["Artifacts", "JLLWrappers", "Libdl", "Pkg"]
git-tree-sha1 = "c3598e525718abcc440f69cc6d5f60dda0a1b61e"
uuid = "6e34b625-4abd-537c-b88f-471c36dfa7a0"
version = "1.0.6+5"

[[Cairo_jll]]
deps = ["Artifacts", "Bzip2_jll", "Fontconfig_jll", "FreeType2_jll", "Glib_jll", "JLLWrappers", "LZO_jll", "Libdl", "Pixman_jll", "Pkg", "Xorg_libXext_jll", "Xorg_libXrender_jll", "Zlib_jll", "libpng_jll"]
git-tree-sha1 = "e2f47f6d8337369411569fd45ae5753ca10394c6"
uuid = "83423d85-b0ee-5818-9007-b63ccbeb887a"
version = "1.16.0+6"

[[ChainRulesCore]]
deps = ["Compat", "LinearAlgebra", "SparseArrays"]
git-tree-sha1 = "f53ca8d41e4753c41cdafa6ec5f7ce914b34be54"
uuid = "d360d2e6-b24c-11e9-a2a3-2a2ae2dbcce4"
version = "0.10.13"

[[ColorSchemes]]
deps = ["ColorTypes", "Colors", "FixedPointNumbers", "Random", "StaticArrays"]
git-tree-sha1 = "ed268efe58512df8c7e224d2e170afd76dd6a417"
uuid = "35d6a980-a343-548e-a6ea-1d62b119f2f4"
version = "3.13.0"

[[ColorTypes]]
deps = ["FixedPointNumbers", "Random"]
git-tree-sha1 = "32a2b8af383f11cbb65803883837a149d10dfe8a"
uuid = "3da002f7-5984-5a60-b8a6-cbb66c0b333f"
version = "0.10.12"

[[Colors]]
deps = ["ColorTypes", "FixedPointNumbers", "Reexport"]
git-tree-sha1 = "417b0ed7b8b838aa6ca0a87aadf1bb9eb111ce40"
uuid = "5ae59095-9a9b-59fe-a467-6f913c188581"
version = "0.12.8"

[[Compat]]
deps = ["Base64", "Dates", "DelimitedFiles", "Distributed", "InteractiveUtils", "LibGit2", "Libdl", "LinearAlgebra", "Markdown", "Mmap", "Pkg", "Printf", "REPL", "Random", "SHA", "Serialization", "SharedArrays", "Sockets", "SparseArrays", "Statistics", "Test", "UUIDs", "Unicode"]
git-tree-sha1 = "344f143fa0ec67e47917848795ab19c6a455f32c"
uuid = "34da2185-b29b-5c13-b0c7-acf172513d20"
version = "3.32.0"

[[CompilerSupportLibraries_jll]]
deps = ["Artifacts", "Libdl"]
uuid = "e66e0078-7015-5450-92f7-15fbd957f2ae"

[[Contour]]
deps = ["StaticArrays"]
git-tree-sha1 = "9f02045d934dc030edad45944ea80dbd1f0ebea7"
uuid = "d38c429a-6771-53c6-b99e-75d170b6e991"
version = "0.5.7"

[[DataAPI]]
git-tree-sha1 = "ee400abb2298bd13bfc3df1c412ed228061a2385"
uuid = "9a962f9c-6df0-11e9-0e5d-c546b8b5ee8a"
version = "1.7.0"

[[DataStructures]]
deps = ["Compat", "InteractiveUtils", "OrderedCollections"]
git-tree-sha1 = "4437b64df1e0adccc3e5d1adbc3ac741095e4677"
uuid = "864edb3b-99cc-5e75-8d2d-829cb0a9cfe8"
version = "0.18.9"

[[DataValueInterfaces]]
git-tree-sha1 = "bfc1187b79289637fa0ef6d4436ebdfe6905cbd6"
uuid = "e2d170a0-9d28-54be-80f0-106bbe20a464"
version = "1.0.0"

[[Dates]]
deps = ["Printf"]
uuid = "ade2ca70-3891-5945-98fb-dc099432e06a"

[[DelimitedFiles]]
deps = ["Mmap"]
uuid = "8bb1440f-4735-579b-a4ab-409b98df4dab"

[[Distributed]]
deps = ["Random", "Serialization", "Sockets"]
uuid = "8ba89e20-285c-5b6f-9357-94700520ee1b"

[[Downloads]]
deps = ["ArgTools", "LibCURL", "NetworkOptions"]
uuid = "f43a241f-c20a-4ad4-852c-f6b1247861c6"

[[EarCut_jll]]
deps = ["Artifacts", "JLLWrappers", "Libdl", "Pkg"]
git-tree-sha1 = "92d8f9f208637e8d2d28c664051a00569c01493d"
uuid = "5ae413db-bbd1-5e63-b57d-d24a61df00f5"
version = "2.1.5+1"

[[Expat_jll]]
deps = ["Artifacts", "JLLWrappers", "Libdl", "Pkg"]
git-tree-sha1 = "b3bfd02e98aedfa5cf885665493c5598c350cd2f"
uuid = "2e619515-83b5-522b-bb60-26c02a35a201"
version = "2.2.10+0"

[[FFMPEG]]
deps = ["FFMPEG_jll"]
git-tree-sha1 = "b57e3acbe22f8484b4b5ff66a7499717fe1a9cc8"
uuid = "c87230d0-a227-11e9-1b43-d7ebe4e7570a"
version = "0.4.1"

[[FFMPEG_jll]]
deps = ["Artifacts", "Bzip2_jll", "FreeType2_jll", "FriBidi_jll", "JLLWrappers", "LAME_jll", "LibVPX_jll", "Libdl", "Ogg_jll", "OpenSSL_jll", "Opus_jll", "Pkg", "Zlib_jll", "libass_jll", "libfdk_aac_jll", "libvorbis_jll", "x264_jll", "x265_jll"]
git-tree-sha1 = "3cc57ad0a213808473eafef4845a74766242e05f"
uuid = "b22a6f82-2f65-5046-a5b2-351ab43fb4e5"
version = "4.3.1+4"

[[FixedPointNumbers]]
deps = ["Statistics"]
git-tree-sha1 = "335bfdceacc84c5cdf16aadc768aa5ddfc5383cc"
uuid = "53c48c17-4a7d-5ca2-90c5-79b7896eea93"
version = "0.8.4"

[[Fontconfig_jll]]
deps = ["Artifacts", "Bzip2_jll", "Expat_jll", "FreeType2_jll", "JLLWrappers", "Libdl", "Libuuid_jll", "Pkg", "Zlib_jll"]
git-tree-sha1 = "35895cf184ceaab11fd778b4590144034a167a2f"
uuid = "a3f928ae-7b40-5064-980b-68af3947d34b"
version = "2.13.1+14"

[[Formatting]]
deps = ["Printf"]
git-tree-sha1 = "8339d61043228fdd3eb658d86c926cb282ae72a8"
uuid = "59287772-0a20-5a39-b81b-1366585eb4c0"
version = "0.4.2"

[[FreeType2_jll]]
deps = ["Artifacts", "Bzip2_jll", "JLLWrappers", "Libdl", "Pkg", "Zlib_jll"]
git-tree-sha1 = "cbd58c9deb1d304f5a245a0b7eb841a2560cfec6"
uuid = "d7e528f0-a631-5988-bf34-fe36492bcfd7"
version = "2.10.1+5"

[[FriBidi_jll]]
deps = ["Artifacts", "JLLWrappers", "Libdl", "Pkg"]
git-tree-sha1 = "aa31987c2ba8704e23c6c8ba8a4f769d5d7e4f91"
uuid = "559328eb-81f9-559d-9380-de523a88c83c"
version = "1.0.10+0"

[[GLFW_jll]]
deps = ["Artifacts", "JLLWrappers", "Libdl", "Libglvnd_jll", "Pkg", "Xorg_libXcursor_jll", "Xorg_libXi_jll", "Xorg_libXinerama_jll", "Xorg_libXrandr_jll"]
git-tree-sha1 = "dba1e8614e98949abfa60480b13653813d8f0157"
uuid = "0656b61e-2033-5cc2-a64a-77c0f6c09b89"
version = "3.3.5+0"

[[GR]]
deps = ["Base64", "DelimitedFiles", "GR_jll", "HTTP", "JSON", "Libdl", "LinearAlgebra", "Pkg", "Printf", "Random", "Serialization", "Sockets", "Test", "UUIDs"]
git-tree-sha1 = "9f473cdf6e2eb360c576f9822e7c765dd9d26dbc"
uuid = "28b8d3ca-fb5f-59d9-8090-bfdbd6d07a71"
version = "0.58.0"

[[GR_jll]]
deps = ["Artifacts", "Bzip2_jll", "Cairo_jll", "FFMPEG_jll", "Fontconfig_jll", "GLFW_jll", "JLLWrappers", "JpegTurbo_jll", "Libdl", "Libtiff_jll", "Pixman_jll", "Pkg", "Qt5Base_jll", "Zlib_jll", "libpng_jll"]
git-tree-sha1 = "eaf96e05a880f3db5ded5a5a8a7817ecba3c7392"
uuid = "d2c73de3-f751-5644-a686-071e5b155ba9"
version = "0.58.0+0"

[[GeometryBasics]]
deps = ["EarCut_jll", "IterTools", "LinearAlgebra", "StaticArrays", "StructArrays", "Tables"]
git-tree-sha1 = "15ff9a14b9e1218958d3530cc288cf31465d9ae2"
uuid = "5c1252a2-5f33-56bf-86c9-59e7332b4326"
version = "0.3.13"

[[GeometryTypes]]
deps = ["ColorTypes", "FixedPointNumbers", "LinearAlgebra", "StaticArrays"]
git-tree-sha1 = "07194161fe4e181c6bf51ef2e329ec4e7d050fc4"
uuid = "4d00f742-c7ba-57c2-abde-4428a4b178cb"
version = "0.8.4"

[[Gettext_jll]]
deps = ["Artifacts", "CompilerSupportLibraries_jll", "JLLWrappers", "Libdl", "Libiconv_jll", "Pkg", "XML2_jll"]
git-tree-sha1 = "9b02998aba7bf074d14de89f9d37ca24a1a0b046"
uuid = "78b55507-aeef-58d4-861c-77aaff3498b1"
version = "0.21.0+0"

[[Glib_jll]]
deps = ["Artifacts", "Gettext_jll", "JLLWrappers", "Libdl", "Libffi_jll", "Libiconv_jll", "Libmount_jll", "PCRE_jll", "Pkg", "Zlib_jll"]
git-tree-sha1 = "7bf67e9a481712b3dbe9cb3dac852dc4b1162e02"
uuid = "7746bdde-850d-59dc-9ae8-88ece973131d"
version = "2.68.3+0"

[[GraphRecipes]]
deps = ["AbstractTrees", "GeometryTypes", "InteractiveUtils", "Interpolations", "LightGraphs", "LinearAlgebra", "NaNMath", "NetworkLayout", "PlotUtils", "RecipesBase", "SparseArrays", "Statistics"]
git-tree-sha1 = "7269dc06b8cd8d16fc2b1756cf7f41901bbc3c52"
uuid = "bd48cda9-67a9-57be-86fa-5b3c104eda73"
version = "0.5.7"

[[Grisu]]
git-tree-sha1 = "53bb909d1151e57e2484c3d1b53e19552b887fb2"
uuid = "42e2da0e-8278-4e71-bc24-59509adca0fe"
version = "1.0.2"

[[HTTP]]
deps = ["Base64", "Dates", "IniFile", "Logging", "MbedTLS", "NetworkOptions", "Sockets", "URIs"]
git-tree-sha1 = "c6a1fff2fd4b1da29d3dccaffb1e1001244d844e"
uuid = "cd3eb016-35fb-5094-929b-558a96fad6f3"
version = "0.9.12"

[[Inflate]]
git-tree-sha1 = "f5fc07d4e706b84f72d54eedcc1c13d92fb0871c"
uuid = "d25df0c9-e2be-5dd7-82c8-3ad0b3e990b9"
version = "0.1.2"

[[IniFile]]
deps = ["Test"]
git-tree-sha1 = "098e4d2c533924c921f9f9847274f2ad89e018b8"
uuid = "83e8ac13-25f8-5344-8a64-a9f2b223428f"
version = "0.5.0"

[[InteractiveUtils]]
deps = ["Markdown"]
uuid = "b77e0a4c-d291-57a0-90e8-8db25a27a240"

[[Interpolations]]
deps = ["AxisAlgorithms", "ChainRulesCore", "LinearAlgebra", "OffsetArrays", "Random", "Ratios", "Requires", "SharedArrays", "SparseArrays", "StaticArrays", "WoodburyMatrices"]
git-tree-sha1 = "1470c80592cf1f0a35566ee5e93c5f8221ebc33a"
uuid = "a98d9a8b-a2ab-59e6-89dd-64a1c18fca59"
version = "0.13.3"

[[IterTools]]
git-tree-sha1 = "05110a2ab1fc5f932622ffea2a003221f4782c18"
uuid = "c8e1da08-722c-5040-9ed9-7db0dc04731e"
version = "1.3.0"

[[IteratorInterfaceExtensions]]
git-tree-sha1 = "a3f24677c21f5bbe9d2a714f95dcd58337fb2856"
uuid = "82899510-4779-5014-852e-03e436cf321d"
version = "1.0.0"

[[JLLWrappers]]
deps = ["Preferences"]
git-tree-sha1 = "642a199af8b68253517b80bd3bfd17eb4e84df6e"
uuid = "692b3bcd-3c85-4b1f-b108-f13ce0eb3210"
version = "1.3.0"

[[JSON]]
deps = ["Dates", "Mmap", "Parsers", "Unicode"]
git-tree-sha1 = "81690084b6198a2e1da36fcfda16eeca9f9f24e4"
uuid = "682c06a0-de6a-54ab-a142-c8b1cf79cde6"
version = "0.21.1"

[[JpegTurbo_jll]]
deps = ["Artifacts", "JLLWrappers", "Libdl", "Pkg"]
git-tree-sha1 = "d735490ac75c5cb9f1b00d8b5509c11984dc6943"
uuid = "aacddb02-875f-59d6-b918-886e6ef4fbf8"
version = "2.1.0+0"

[[LAME_jll]]
deps = ["Artifacts", "JLLWrappers", "Libdl", "Pkg"]
git-tree-sha1 = "f6250b16881adf048549549fba48b1161acdac8c"
uuid = "c1c5ebd0-6772-5130-a774-d5fcae4a789d"
version = "3.100.1+0"

[[LZO_jll]]
deps = ["Artifacts", "JLLWrappers", "Libdl", "Pkg"]
git-tree-sha1 = "e5b909bcf985c5e2605737d2ce278ed791b89be6"
uuid = "dd4b983a-f0e5-5f8d-a1b7-129d4a5fb1ac"
version = "2.10.1+0"

[[LaTeXStrings]]
git-tree-sha1 = "c7f1c695e06c01b95a67f0cd1d34994f3e7db104"
uuid = "b964fa9f-0449-5b57-a5c2-d3ea65f4040f"
version = "1.2.1"

[[Latexify]]
deps = ["Formatting", "InteractiveUtils", "LaTeXStrings", "MacroTools", "Markdown", "Printf", "Requires"]
git-tree-sha1 = "a4b12a1bd2ebade87891ab7e36fdbce582301a92"
uuid = "23fbe1c1-3f47-55db-b15f-69d7ec21a316"
version = "0.15.6"

[[LibCURL]]
deps = ["LibCURL_jll", "MozillaCACerts_jll"]
uuid = "b27032c2-a3e7-50c8-80cd-2d36dbcbfd21"

[[LibCURL_jll]]
deps = ["Artifacts", "LibSSH2_jll", "Libdl", "MbedTLS_jll", "Zlib_jll", "nghttp2_jll"]
uuid = "deac9b47-8bc7-5906-a0fe-35ac56dc84c0"

[[LibGit2]]
deps = ["Base64", "NetworkOptions", "Printf", "SHA"]
uuid = "76f85450-5226-5b5a-8eaa-529ad045b433"

[[LibSSH2_jll]]
deps = ["Artifacts", "Libdl", "MbedTLS_jll"]
uuid = "29816b5a-b9ab-546f-933c-edad1886dfa8"

[[LibVPX_jll]]
deps = ["Artifacts", "JLLWrappers", "Libdl", "Pkg"]
git-tree-sha1 = "12ee7e23fa4d18361e7c2cde8f8337d4c3101bc7"
uuid = "dd192d2f-8180-539f-9fb4-cc70b1dcf69a"
version = "1.10.0+0"

[[Libdl]]
uuid = "8f399da3-3557-5675-b5ff-fb832c97cbdb"

[[Libffi_jll]]
deps = ["Artifacts", "JLLWrappers", "Libdl", "Pkg"]
git-tree-sha1 = "761a393aeccd6aa92ec3515e428c26bf99575b3b"
uuid = "e9f186c6-92d2-5b65-8a66-fee21dc1b490"
version = "3.2.2+0"

[[Libgcrypt_jll]]
deps = ["Artifacts", "JLLWrappers", "Libdl", "Libgpg_error_jll", "Pkg"]
git-tree-sha1 = "64613c82a59c120435c067c2b809fc61cf5166ae"
uuid = "d4300ac3-e22c-5743-9152-c294e39db1e4"
version = "1.8.7+0"

[[Libglvnd_jll]]
deps = ["Artifacts", "JLLWrappers", "Libdl", "Pkg", "Xorg_libX11_jll", "Xorg_libXext_jll"]
git-tree-sha1 = "7739f837d6447403596a75d19ed01fd08d6f56bf"
uuid = "7e76a0d4-f3c7-5321-8279-8d96eeed0f29"
version = "1.3.0+3"

[[Libgpg_error_jll]]
deps = ["Artifacts", "JLLWrappers", "Libdl", "Pkg"]
git-tree-sha1 = "c333716e46366857753e273ce6a69ee0945a6db9"
uuid = "7add5ba3-2f88-524e-9cd5-f83b8a55f7b8"
version = "1.42.0+0"

[[Libiconv_jll]]
deps = ["Artifacts", "JLLWrappers", "Libdl", "Pkg"]
git-tree-sha1 = "42b62845d70a619f063a7da093d995ec8e15e778"
uuid = "94ce4f54-9a6c-5748-9c1c-f9c7231a4531"
version = "1.16.1+1"

[[Libmount_jll]]
deps = ["Artifacts", "JLLWrappers", "Libdl", "Pkg"]
git-tree-sha1 = "9c30530bf0effd46e15e0fdcf2b8636e78cbbd73"
uuid = "4b2f31a3-9ecc-558c-b454-b3730dcb73e9"
version = "2.35.0+0"

[[Libtiff_jll]]
deps = ["Artifacts", "JLLWrappers", "JpegTurbo_jll", "Libdl", "Pkg", "Zlib_jll", "Zstd_jll"]
git-tree-sha1 = "340e257aada13f95f98ee352d316c3bed37c8ab9"
uuid = "89763e89-9b03-5906-acba-b20f662cd828"
version = "4.3.0+0"

[[Libuuid_jll]]
deps = ["Artifacts", "JLLWrappers", "Libdl", "Pkg"]
git-tree-sha1 = "7f3efec06033682db852f8b3bc3c1d2b0a0ab066"
uuid = "38a345b3-de98-5d2b-a5d3-14cd9215e700"
version = "2.36.0+0"

[[LightGraphs]]
deps = ["ArnoldiMethod", "DataStructures", "Distributed", "Inflate", "LinearAlgebra", "Random", "SharedArrays", "SimpleTraits", "SparseArrays", "Statistics"]
git-tree-sha1 = "432428df5f360964040ed60418dd5601ecd240b6"
uuid = "093fc24a-ae57-5d10-9952-331d41423f4d"
version = "1.3.5"

[[LinearAlgebra]]
deps = ["Libdl"]
uuid = "37e2e46d-f89d-539d-b4ee-838fcccc9c8e"

[[Logging]]
uuid = "56ddb016-857b-54e1-b83d-db4d58db5568"

[[MacroTools]]
deps = ["Markdown", "Random"]
git-tree-sha1 = "6a8a2a625ab0dea913aba95c11370589e0239ff0"
uuid = "1914dd2f-81c6-5fcd-8719-6d5c9610ff09"
version = "0.5.6"

[[Markdown]]
deps = ["Base64"]
uuid = "d6f4376e-aef5-505a-96c1-9c027394607a"

[[MbedTLS]]
deps = ["Dates", "MbedTLS_jll", "Random", "Sockets"]
git-tree-sha1 = "1c38e51c3d08ef2278062ebceade0e46cefc96fe"
uuid = "739be429-bea8-5141-9913-cc70e7f3736d"
version = "1.0.3"

[[MbedTLS_jll]]
deps = ["Artifacts", "Libdl"]
uuid = "c8ffd9c3-330d-5841-b78e-0817d7145fa1"

[[Measures]]
git-tree-sha1 = "e498ddeee6f9fdb4551ce855a46f54dbd900245f"
uuid = "442fdcdd-2543-5da2-b0f3-8c86c306513e"
version = "0.3.1"

[[Missings]]
deps = ["DataAPI"]
git-tree-sha1 = "4ea90bd5d3985ae1f9a908bd4500ae88921c5ce7"
uuid = "e1d29d7a-bbdc-5cf2-9ac0-f12de2c33e28"
version = "1.0.0"

[[Mmap]]
uuid = "a63ad114-7e13-5084-954f-fe012c677804"

[[MozillaCACerts_jll]]
uuid = "14a3606d-f60d-562e-9121-12d972cd8159"

[[NaNMath]]
git-tree-sha1 = "bfe47e760d60b82b66b61d2d44128b62e3a369fb"
uuid = "77ba4419-2d1f-58cd-9bb1-8ffee604a2e3"
version = "0.3.5"

[[NetworkLayout]]
deps = ["GeometryBasics", "LinearAlgebra", "Random", "Requires", "SparseArrays"]
git-tree-sha1 = "76bbbe01d2e582213e656688e63707d94aaadd15"
uuid = "46757867-2c16-5918-afeb-47bfcb05e46a"
version = "0.4.0"

[[NetworkOptions]]
uuid = "ca575930-c2e3-43a9-ace4-1e988b2c1908"

[[OffsetArrays]]
deps = ["Adapt"]
git-tree-sha1 = "4f825c6da64aebaa22cc058ecfceed1ab9af1c7e"
uuid = "6fe1bfb0-de20-5000-8ca7-80f57d26f881"
version = "1.10.3"

[[Ogg_jll]]
deps = ["Artifacts", "JLLWrappers", "Libdl", "Pkg"]
git-tree-sha1 = "7937eda4681660b4d6aeeecc2f7e1c81c8ee4e2f"
uuid = "e7412a2a-1a6e-54c0-be00-318e2571c051"
version = "1.3.5+0"

[[OpenSSL_jll]]
deps = ["Artifacts", "JLLWrappers", "Libdl", "Pkg"]
git-tree-sha1 = "15003dcb7d8db3c6c857fda14891a539a8f2705a"
uuid = "458c3c95-2e84-50aa-8efc-19380b2a3a95"
version = "1.1.10+0"

[[Opus_jll]]
deps = ["Artifacts", "JLLWrappers", "Libdl", "Pkg"]
git-tree-sha1 = "51a08fb14ec28da2ec7a927c4337e4332c2a4720"
uuid = "91d4177d-7536-5919-b921-800302f37372"
version = "1.3.2+0"

[[OrderedCollections]]
git-tree-sha1 = "85f8e6578bf1f9ee0d11e7bb1b1456435479d47c"
uuid = "bac558e1-5e72-5ebc-8fee-abe8a469f55d"
version = "1.4.1"

[[PCRE_jll]]
deps = ["Artifacts", "JLLWrappers", "Libdl", "Pkg"]
git-tree-sha1 = "b2a7af664e098055a7529ad1a900ded962bca488"
uuid = "2f80f16e-611a-54ab-bc61-aa92de5b98fc"
version = "8.44.0+0"

[[Parsers]]
deps = ["Dates"]
git-tree-sha1 = "94bf17e83a0e4b20c8d77f6af8ffe8cc3b386c0a"
uuid = "69de0a69-1ddd-5017-9359-2bf0b02dc9f0"
version = "1.1.1"

[[Pixman_jll]]
deps = ["Artifacts", "JLLWrappers", "Libdl", "Pkg"]
git-tree-sha1 = "b4f5d02549a10e20780a24fce72bea96b6329e29"
uuid = "30392449-352a-5448-841d-b1acce4e97dc"
version = "0.40.1+0"

[[Pkg]]
deps = ["Artifacts", "Dates", "Downloads", "LibGit2", "Libdl", "Logging", "Markdown", "Printf", "REPL", "Random", "SHA", "Serialization", "TOML", "Tar", "UUIDs", "p7zip_jll"]
uuid = "44cfe95a-1eb2-52ea-b672-e2afdf69b78f"

[[PlotThemes]]
deps = ["PlotUtils", "Requires", "Statistics"]
git-tree-sha1 = "a3a964ce9dc7898193536002a6dd892b1b5a6f1d"
uuid = "ccf2f8ad-2431-5c83-bf29-c5338b663b6a"
version = "2.0.1"

[[PlotUtils]]
deps = ["ColorSchemes", "Colors", "Dates", "Printf", "Random", "Reexport", "Statistics"]
git-tree-sha1 = "501c20a63a34ac1d015d5304da0e645f42d91c9f"
uuid = "995b91a9-d308-5afd-9ec6-746e21dbc043"
version = "1.0.11"

[[Plots]]
deps = ["Base64", "Contour", "Dates", "FFMPEG", "FixedPointNumbers", "GR", "GeometryBasics", "JSON", "Latexify", "LinearAlgebra", "Measures", "NaNMath", "PlotThemes", "PlotUtils", "Printf", "REPL", "Random", "RecipesBase", "RecipesPipeline", "Reexport", "Requires", "Scratch", "Showoff", "SparseArrays", "Statistics", "StatsBase", "UUIDs"]
git-tree-sha1 = "1e72752052a3893d0f7103fbac728b60b934f5a5"
uuid = "91a5bcdd-55d7-5caf-9e0b-520d859cae80"
version = "1.19.4"

[[PlutoUI]]
deps = ["Base64", "Dates", "InteractiveUtils", "JSON", "Logging", "Markdown", "Random", "Reexport", "Suppressor"]
git-tree-sha1 = "44e225d5837e2a2345e69a1d1e01ac2443ff9fcb"
uuid = "7f904dfe-b85e-4ff6-b463-dae2292396a8"
version = "0.7.9"

[[Preferences]]
deps = ["TOML"]
git-tree-sha1 = "00cfd92944ca9c760982747e9a1d0d5d86ab1e5a"
uuid = "21216c6a-2e73-6563-6e65-726566657250"
version = "1.2.2"

[[Printf]]
deps = ["Unicode"]
uuid = "de0858da-6303-5e67-8744-51eddeeeb8d7"

[[Qt5Base_jll]]
deps = ["Artifacts", "CompilerSupportLibraries_jll", "Fontconfig_jll", "Glib_jll", "JLLWrappers", "Libdl", "Libglvnd_jll", "OpenSSL_jll", "Pkg", "Xorg_libXext_jll", "Xorg_libxcb_jll", "Xorg_xcb_util_image_jll", "Xorg_xcb_util_keysyms_jll", "Xorg_xcb_util_renderutil_jll", "Xorg_xcb_util_wm_jll", "Zlib_jll", "xkbcommon_jll"]
git-tree-sha1 = "ad368663a5e20dbb8d6dc2fddeefe4dae0781ae8"
uuid = "ea2cea3b-5b76-57ae-a6ef-0a8af62496e1"
version = "5.15.3+0"

[[REPL]]
deps = ["InteractiveUtils", "Markdown", "Sockets", "Unicode"]
uuid = "3fa0cd96-eef1-5676-8a61-b3b8758bbffb"

[[Random]]
deps = ["Serialization"]
uuid = "9a3f8284-a2c9-5f02-9a11-845980a1fd5c"

[[Ratios]]
git-tree-sha1 = "37d210f612d70f3f7d57d488cb3b6eff56ad4e41"
uuid = "c84ed2f1-dad5-54f0-aa8e-dbefe2724439"
version = "0.4.0"

[[RecipesBase]]
git-tree-sha1 = "b3fb709f3c97bfc6e948be68beeecb55a0b340ae"
uuid = "3cdcf5f2-1ef4-517c-9805-6587b60abb01"
version = "1.1.1"

[[RecipesPipeline]]
deps = ["Dates", "NaNMath", "PlotUtils", "RecipesBase"]
git-tree-sha1 = "2a7a2469ed5d94a98dea0e85c46fa653d76be0cd"
uuid = "01d81517-befc-4cb6-b9ec-a95719d0359c"
version = "0.3.4"

[[Reexport]]
git-tree-sha1 = "5f6c21241f0f655da3952fd60aa18477cf96c220"
uuid = "189a3867-3050-52da-a836-e630ba90ab69"
version = "1.1.0"

[[Requires]]
deps = ["UUIDs"]
git-tree-sha1 = "4036a3bd08ac7e968e27c203d45f5fff15020621"
uuid = "ae029012-a4dd-5104-9daa-d747884805df"
version = "1.1.3"

[[SHA]]
uuid = "ea8e919c-243c-51af-8825-aaa63cd721ce"

[[Scratch]]
deps = ["Dates"]
git-tree-sha1 = "0b4b7f1393cff97c33891da2a0bf69c6ed241fda"
uuid = "6c6a2e73-6563-6170-7368-637461726353"
version = "1.1.0"

[[Serialization]]
uuid = "9e88b42a-f829-5b0c-bbe9-9e923198166b"

[[SharedArrays]]
deps = ["Distributed", "Mmap", "Random", "Serialization"]
uuid = "1a1011a3-84de-559e-8e89-a11a2f7dc383"

[[Showoff]]
deps = ["Dates", "Grisu"]
git-tree-sha1 = "91eddf657aca81df9ae6ceb20b959ae5653ad1de"
uuid = "992d4aef-0814-514b-bc4d-f2e9a6c4116f"
version = "1.0.3"

[[SimpleTraits]]
deps = ["InteractiveUtils", "MacroTools"]
git-tree-sha1 = "5d7e3f4e11935503d3ecaf7186eac40602e7d231"
uuid = "699a6c99-e7fa-54fc-8d76-47d257e15c1d"
version = "0.9.4"

[[Sockets]]
uuid = "6462fe0b-24de-5631-8697-dd941f90decc"

[[SortingAlgorithms]]
deps = ["DataStructures"]
git-tree-sha1 = "b3363d7460f7d098ca0912c69b082f75625d7508"
uuid = "a2af1166-a08f-5f64-846c-94a0d3cef48c"
version = "1.0.1"

[[SparseArrays]]
deps = ["LinearAlgebra", "Random"]
uuid = "2f01184e-e22b-5df5-ae63-d93ebab69eaf"

[[StaticArrays]]
deps = ["LinearAlgebra", "Random", "Statistics"]
git-tree-sha1 = "885838778bb6f0136f8317757d7803e0d81201e4"
uuid = "90137ffa-7385-5640-81b9-e52037218182"
version = "1.2.9"

[[Statistics]]
deps = ["LinearAlgebra", "SparseArrays"]
uuid = "10745b16-79ce-11e8-11f9-7d13ad32a3b2"

[[StatsAPI]]
git-tree-sha1 = "1958272568dc176a1d881acb797beb909c785510"
uuid = "82ae8749-77ed-4fe6-ae5f-f523153014b0"
version = "1.0.0"

[[StatsBase]]
deps = ["DataAPI", "DataStructures", "LinearAlgebra", "Missings", "Printf", "Random", "SortingAlgorithms", "SparseArrays", "Statistics", "StatsAPI"]
git-tree-sha1 = "fed1ec1e65749c4d96fc20dd13bea72b55457e62"
uuid = "2913bbd2-ae8a-5f71-8c99-4fb6c76f3a91"
version = "0.33.9"

[[StructArrays]]
deps = ["Adapt", "DataAPI", "StaticArrays", "Tables"]
git-tree-sha1 = "000e168f5cc9aded17b6999a560b7c11dda69095"
uuid = "09ab397b-f2b6-538f-b94a-2f83cf4a842a"
version = "0.6.0"

[[Suppressor]]
git-tree-sha1 = "a819d77f31f83e5792a76081eee1ea6342ab8787"
uuid = "fd094767-a336-5f1f-9728-57cf17d0bbfb"
version = "0.2.0"

[[TOML]]
deps = ["Dates"]
uuid = "fa267f1f-6049-4f14-aa54-33bafae1ed76"

[[TableTraits]]
deps = ["IteratorInterfaceExtensions"]
git-tree-sha1 = "c06b2f539df1c6efa794486abfb6ed2022561a39"
uuid = "3783bdb8-4a98-5b6b-af9a-565f29a5fe9c"
version = "1.0.1"

[[Tables]]
deps = ["DataAPI", "DataValueInterfaces", "IteratorInterfaceExtensions", "LinearAlgebra", "TableTraits", "Test"]
git-tree-sha1 = "8ed4a3ea724dac32670b062be3ef1c1de6773ae8"
uuid = "bd369af6-aec1-5ad0-b16a-f7cc5008161c"
version = "1.4.4"

[[Tar]]
deps = ["ArgTools", "SHA"]
uuid = "a4e569a6-e804-4fa4-b0f3-eef7a1d5b13e"

[[Test]]
deps = ["InteractiveUtils", "Logging", "Random", "Serialization"]
uuid = "8dfed614-e22c-5e08-85e1-65c5234f0b40"

[[URIs]]
git-tree-sha1 = "97bbe755a53fe859669cd907f2d96aee8d2c1355"
uuid = "5c2747f8-b7ea-4ff2-ba2e-563bfd36b1d4"
version = "1.3.0"

[[UUIDs]]
deps = ["Random", "SHA"]
uuid = "cf7118a7-6976-5b1a-9a39-7adc72f591a4"

[[Unicode]]
uuid = "4ec0a83e-493e-50e2-b9ac-8f72acf5a8f5"

[[Wayland_jll]]
deps = ["Artifacts", "Expat_jll", "JLLWrappers", "Libdl", "Libffi_jll", "Pkg", "XML2_jll"]
git-tree-sha1 = "3e61f0b86f90dacb0bc0e73a0c5a83f6a8636e23"
uuid = "a2964d1f-97da-50d4-b82a-358c7fce9d89"
version = "1.19.0+0"

[[Wayland_protocols_jll]]
deps = ["Artifacts", "JLLWrappers", "Libdl", "Pkg", "Wayland_jll"]
git-tree-sha1 = "2839f1c1296940218e35df0bbb220f2a79686670"
uuid = "2381bf8a-dfd0-557d-9999-79630e7b1b91"
version = "1.18.0+4"

[[WoodburyMatrices]]
deps = ["LinearAlgebra", "SparseArrays"]
git-tree-sha1 = "59e2ad8fd1591ea019a5259bd012d7aee15f995c"
uuid = "efce3f68-66dc-5838-9240-27a6d6f5f9b6"
version = "0.5.3"

[[XML2_jll]]
deps = ["Artifacts", "JLLWrappers", "Libdl", "Libiconv_jll", "Pkg", "Zlib_jll"]
git-tree-sha1 = "1acf5bdf07aa0907e0a37d3718bb88d4b687b74a"
uuid = "02c8fc9c-b97f-50b9-bbe4-9be30ff0a78a"
version = "2.9.12+0"

[[XSLT_jll]]
deps = ["Artifacts", "JLLWrappers", "Libdl", "Libgcrypt_jll", "Libgpg_error_jll", "Libiconv_jll", "Pkg", "XML2_jll", "Zlib_jll"]
git-tree-sha1 = "91844873c4085240b95e795f692c4cec4d805f8a"
uuid = "aed1982a-8fda-507f-9586-7b0439959a61"
version = "1.1.34+0"

[[Xorg_libX11_jll]]
deps = ["Artifacts", "JLLWrappers", "Libdl", "Pkg", "Xorg_libxcb_jll", "Xorg_xtrans_jll"]
git-tree-sha1 = "5be649d550f3f4b95308bf0183b82e2582876527"
uuid = "4f6342f7-b3d2-589e-9d20-edeb45f2b2bc"
version = "1.6.9+4"

[[Xorg_libXau_jll]]
deps = ["Artifacts", "JLLWrappers", "Libdl", "Pkg"]
git-tree-sha1 = "4e490d5c960c314f33885790ed410ff3a94ce67e"
uuid = "0c0b7dd1-d40b-584c-a123-a41640f87eec"
version = "1.0.9+4"

[[Xorg_libXcursor_jll]]
deps = ["Artifacts", "JLLWrappers", "Libdl", "Pkg", "Xorg_libXfixes_jll", "Xorg_libXrender_jll"]
git-tree-sha1 = "12e0eb3bc634fa2080c1c37fccf56f7c22989afd"
uuid = "935fb764-8cf2-53bf-bb30-45bb1f8bf724"
version = "1.2.0+4"

[[Xorg_libXdmcp_jll]]
deps = ["Artifacts", "JLLWrappers", "Libdl", "Pkg"]
git-tree-sha1 = "4fe47bd2247248125c428978740e18a681372dd4"
uuid = "a3789734-cfe1-5b06-b2d0-1dd0d9d62d05"
version = "1.1.3+4"

[[Xorg_libXext_jll]]
deps = ["Artifacts", "JLLWrappers", "Libdl", "Pkg", "Xorg_libX11_jll"]
git-tree-sha1 = "b7c0aa8c376b31e4852b360222848637f481f8c3"
uuid = "1082639a-0dae-5f34-9b06-72781eeb8cb3"
version = "1.3.4+4"

[[Xorg_libXfixes_jll]]
deps = ["Artifacts", "JLLWrappers", "Libdl", "Pkg", "Xorg_libX11_jll"]
git-tree-sha1 = "0e0dc7431e7a0587559f9294aeec269471c991a4"
uuid = "d091e8ba-531a-589c-9de9-94069b037ed8"
version = "5.0.3+4"

[[Xorg_libXi_jll]]
deps = ["Artifacts", "JLLWrappers", "Libdl", "Pkg", "Xorg_libXext_jll", "Xorg_libXfixes_jll"]
git-tree-sha1 = "89b52bc2160aadc84d707093930ef0bffa641246"
uuid = "a51aa0fd-4e3c-5386-b890-e753decda492"
version = "1.7.10+4"

[[Xorg_libXinerama_jll]]
deps = ["Artifacts", "JLLWrappers", "Libdl", "Pkg", "Xorg_libXext_jll"]
git-tree-sha1 = "26be8b1c342929259317d8b9f7b53bf2bb73b123"
uuid = "d1454406-59df-5ea1-beac-c340f2130bc3"
version = "1.1.4+4"

[[Xorg_libXrandr_jll]]
deps = ["Artifacts", "JLLWrappers", "Libdl", "Pkg", "Xorg_libXext_jll", "Xorg_libXrender_jll"]
git-tree-sha1 = "34cea83cb726fb58f325887bf0612c6b3fb17631"
uuid = "ec84b674-ba8e-5d96-8ba1-2a689ba10484"
version = "1.5.2+4"

[[Xorg_libXrender_jll]]
deps = ["Artifacts", "JLLWrappers", "Libdl", "Pkg", "Xorg_libX11_jll"]
git-tree-sha1 = "19560f30fd49f4d4efbe7002a1037f8c43d43b96"
uuid = "ea2f1a96-1ddc-540d-b46f-429655e07cfa"
version = "0.9.10+4"

[[Xorg_libpthread_stubs_jll]]
deps = ["Artifacts", "JLLWrappers", "Libdl", "Pkg"]
git-tree-sha1 = "6783737e45d3c59a4a4c4091f5f88cdcf0908cbb"
uuid = "14d82f49-176c-5ed1-bb49-ad3f5cbd8c74"
version = "0.1.0+3"

[[Xorg_libxcb_jll]]
deps = ["Artifacts", "JLLWrappers", "Libdl", "Pkg", "XSLT_jll", "Xorg_libXau_jll", "Xorg_libXdmcp_jll", "Xorg_libpthread_stubs_jll"]
git-tree-sha1 = "daf17f441228e7a3833846cd048892861cff16d6"
uuid = "c7cfdc94-dc32-55de-ac96-5a1b8d977c5b"
version = "1.13.0+3"

[[Xorg_libxkbfile_jll]]
deps = ["Artifacts", "JLLWrappers", "Libdl", "Pkg", "Xorg_libX11_jll"]
git-tree-sha1 = "926af861744212db0eb001d9e40b5d16292080b2"
uuid = "cc61e674-0454-545c-8b26-ed2c68acab7a"
version = "1.1.0+4"

[[Xorg_xcb_util_image_jll]]
deps = ["Artifacts", "JLLWrappers", "Libdl", "Pkg", "Xorg_xcb_util_jll"]
git-tree-sha1 = "0fab0a40349ba1cba2c1da699243396ff8e94b97"
uuid = "12413925-8142-5f55-bb0e-6d7ca50bb09b"
version = "0.4.0+1"

[[Xorg_xcb_util_jll]]
deps = ["Artifacts", "JLLWrappers", "Libdl", "Pkg", "Xorg_libxcb_jll"]
git-tree-sha1 = "e7fd7b2881fa2eaa72717420894d3938177862d1"
uuid = "2def613f-5ad1-5310-b15b-b15d46f528f5"
version = "0.4.0+1"

[[Xorg_xcb_util_keysyms_jll]]
deps = ["Artifacts", "JLLWrappers", "Libdl", "Pkg", "Xorg_xcb_util_jll"]
git-tree-sha1 = "d1151e2c45a544f32441a567d1690e701ec89b00"
uuid = "975044d2-76e6-5fbe-bf08-97ce7c6574c7"
version = "0.4.0+1"

[[Xorg_xcb_util_renderutil_jll]]
deps = ["Artifacts", "JLLWrappers", "Libdl", "Pkg", "Xorg_xcb_util_jll"]
git-tree-sha1 = "dfd7a8f38d4613b6a575253b3174dd991ca6183e"
uuid = "0d47668e-0667-5a69-a72c-f761630bfb7e"
version = "0.3.9+1"

[[Xorg_xcb_util_wm_jll]]
deps = ["Artifacts", "JLLWrappers", "Libdl", "Pkg", "Xorg_xcb_util_jll"]
git-tree-sha1 = "e78d10aab01a4a154142c5006ed44fd9e8e31b67"
uuid = "c22f9ab0-d5fe-5066-847c-f4bb1cd4e361"
version = "0.4.1+1"

[[Xorg_xkbcomp_jll]]
deps = ["Artifacts", "JLLWrappers", "Libdl", "Pkg", "Xorg_libxkbfile_jll"]
git-tree-sha1 = "4bcbf660f6c2e714f87e960a171b119d06ee163b"
uuid = "35661453-b289-5fab-8a00-3d9160c6a3a4"
version = "1.4.2+4"

[[Xorg_xkeyboard_config_jll]]
deps = ["Artifacts", "JLLWrappers", "Libdl", "Pkg", "Xorg_xkbcomp_jll"]
git-tree-sha1 = "5c8424f8a67c3f2209646d4425f3d415fee5931d"
uuid = "33bec58e-1273-512f-9401-5d533626f822"
version = "2.27.0+4"

[[Xorg_xtrans_jll]]
deps = ["Artifacts", "JLLWrappers", "Libdl", "Pkg"]
git-tree-sha1 = "79c31e7844f6ecf779705fbc12146eb190b7d845"
uuid = "c5fb5394-a638-5e4d-96e5-b29de1b5cf10"
version = "1.4.0+3"

[[Zlib_jll]]
deps = ["Libdl"]
uuid = "83775a58-1f1d-513f-b197-d71354ab007a"

[[Zstd_jll]]
deps = ["Artifacts", "JLLWrappers", "Libdl", "Pkg"]
git-tree-sha1 = "cc4bf3fdde8b7e3e9fa0351bdeedba1cf3b7f6e6"
uuid = "3161d3a3-bdf6-5164-811a-617609db77b4"
version = "1.5.0+0"

[[libass_jll]]
deps = ["Artifacts", "Bzip2_jll", "FreeType2_jll", "FriBidi_jll", "JLLWrappers", "Libdl", "Pkg", "Zlib_jll"]
git-tree-sha1 = "acc685bcf777b2202a904cdcb49ad34c2fa1880c"
uuid = "0ac62f75-1d6f-5e53-bd7c-93b484bb37c0"
version = "0.14.0+4"

[[libfdk_aac_jll]]
deps = ["Artifacts", "JLLWrappers", "Libdl", "Pkg"]
git-tree-sha1 = "7a5780a0d9c6864184b3a2eeeb833a0c871f00ab"
uuid = "f638f0a6-7fb0-5443-88ba-1cc74229b280"
version = "0.1.6+4"

[[libpng_jll]]
deps = ["Artifacts", "JLLWrappers", "Libdl", "Pkg", "Zlib_jll"]
git-tree-sha1 = "94d180a6d2b5e55e447e2d27a29ed04fe79eb30c"
uuid = "b53b4c65-9356-5827-b1ea-8c7a1a84506f"
version = "1.6.38+0"

[[libvorbis_jll]]
deps = ["Artifacts", "JLLWrappers", "Libdl", "Ogg_jll", "Pkg"]
git-tree-sha1 = "c45f4e40e7aafe9d086379e5578947ec8b95a8fb"
uuid = "f27f6e37-5d2b-51aa-960f-b287f2bc3b7a"
version = "1.3.7+0"

[[nghttp2_jll]]
deps = ["Artifacts", "Libdl"]
uuid = "8e850ede-7688-5339-a07c-302acd2aaf8d"

[[p7zip_jll]]
deps = ["Artifacts", "Libdl"]
uuid = "3f19e933-33d8-53b3-aaab-bd5110c3b7a0"

[[x264_jll]]
deps = ["Artifacts", "JLLWrappers", "Libdl", "Pkg"]
git-tree-sha1 = "d713c1ce4deac133e3334ee12f4adff07f81778f"
uuid = "1270edf5-f2f9-52d2-97e9-ab00b5d0237a"
version = "2020.7.14+2"

[[x265_jll]]
deps = ["Artifacts", "JLLWrappers", "Libdl", "Pkg"]
git-tree-sha1 = "487da2f8f2f0c8ee0e83f39d13037d6bbf0a45ab"
uuid = "dfaa095f-4041-5dcd-9319-2fabd8486b76"
version = "3.0.0+3"

[[xkbcommon_jll]]
deps = ["Artifacts", "JLLWrappers", "Libdl", "Pkg", "Wayland_jll", "Wayland_protocols_jll", "Xorg_libxcb_jll", "Xorg_xkeyboard_config_jll"]
git-tree-sha1 = "ece2350174195bb31de1a63bea3a41ae1aa593b6"
uuid = "d8fb68d0-12a3-5cfd-a85a-d49703b185fd"
version = "0.9.1+5"
"""

# ╔═╡ Cell order:
# ╟─94e5f9f8-f157-11eb-2b69-6d7253ae9cf9
# ╠═8c64d70d-f46b-4ae4-9b43-53d7fd461efe
# ╟─5ee0cdc1-ac4b-4664-b350-daa3c3179806
# ╠═f535e226-0c5c-47d5-ab6b-d3590ba14e4d
# ╟─f3577938-4381-45a5-88b2-ab06f0f16529
# ╟─d8d0fddf-2853-4fa0-bc3a-585773b58a3b
# ╟─f6899ade-339e-4365-8dd5-c229dc9db42f
# ╠═b60d06df-a58f-4a6f-9afc-b46478f4c142
# ╟─1daa8e24-e917-4a46-b6b9-853e89e330ef
# ╟─5bff4f06-5657-4fbd-9114-ac1fc5026c5d
# ╠═5f1297fe-1368-4695-99a0-a26582fe53da
# ╟─8e5274a8-b024-4a47-a630-5206de4a82cd
# ╟─60029bce-d61d-4feb-bfe2-ad0623c30fb4
# ╠═96f1ac18-95c9-47a1-b4b8-f0ebfc24a762
# ╟─2991eb47-6667-474d-9967-126d2fdf9f09
# ╠═b612f9b9-3128-446f-8940-1c4d86df64db
# ╟─288312ad-71d5-40c8-adad-8fba1f987d98
# ╟─0e523d1f-9b05-46ae-a5f2-d6b6930ba0eb
# ╟─137942e1-2815-4bc4-9ba2-8efa48113a32
# ╠═f0fee254-67e7-4e54-9dff-529dca6d9dae
# ╟─87d201d1-00c3-4d90-84b7-e7b989902bba
# ╟─a5a7bb2e-f278-418d-96dc-e10a01392550
# ╠═ac9fa9a8-72dd-4ca5-964f-16aa231f4d96
# ╟─662bce03-e461-4e7c-9827-f327c7da6754
# ╟─00000000-0000-0000-0000-000000000001
# ╟─00000000-0000-0000-0000-000000000002


text:
include("utils.jl")

using Plots
using LaTeXStrings
using Statistics

n = 100
maxk = 50
repeats = 20

A = hilbert(n)
ks = 1:maxk
λ = 1e-4

errors = zeros(maxk, repeats, 3)

methods = [
    ridge_weights(A, λ),
    uniform_weights(A),
    squared_norms_weights(A)
]

for k in ks
    for rep = 1:repeats
        for (i, w) in enumerate(methods)
            C = samplemat(A, w, k)
            C = unique(C, dims=2)
            errors[k, rep, i] = approxerror(A, C)
        end
    end
end

best_approx_errors = zeros(maxk)

for k in ks
    C = best_approx(A, k)
    best_approx_errors[k] = approxerror(A, C)
end

means = mean(errors, dims=2)[:, 1, :]
stds = std(errors, dims=2)[:, 1, :]

plot(xlabel=L"k", ylabel=L"\textrm{error}")
plot!(ks, means[:, 2], yaxis=:log, label="uniform", w=2)
plot!(ks, means[:, 3], yaxis=:log, label="squared norm", w=2)
plot!(ks, means[:, 1], yaxis=:log, label="ridge", w=2)
p = plot!(ks, best_approx_errors, yaxis=:log, label="best", c=:gray, w=2, ls=:dashdot)
savefig(p, "./plot.pdf")
display(p)  # sometimes the display doesn't work

ext: jl


text:
module test_1
using AdventOfCode2018.Day1
using Test

@testset "day 1, part 1" begin
	@test parse_input("+1\n-2\n3\n+1") == [1, -2, 3, 1]

	@test part_1([1, 1, 1]) == 3
	@test part_1([1, 1, -2]) == 0
	@test part_1([-1, -2, -3]) == -6
end

@testset "day 1, part 2" begin
	@test part_2([1, -1]) == 0
	@test part_2([3, 3, 4, -2, -4]) == 10
	@test part_2([-6, 3, 8, 5, -6]) == 5
	@test part_2([7, 7, -2, -7, -4]) == 14
end
end


text:
using Test

@testset "MOI" begin
    include("MOI_wrapper.jl")
end


text:
### A Pluto.jl notebook ###
# v0.17.1

using Markdown
using InteractiveUtils

# ╔═╡ f0f80b1a-d090-11eb-2b0d-d11fd8196311
using Omega, Distributions, UnicodePlots

# ╔═╡ daa9fd86-5a36-4aa2-842e-477cdb19b8d5
md"# Probability Dilution
Probability dilution is refers to scenarios where one can increase one's confidence by increasing the noisyness of one's measurement device.

Here we'll use an example on microcrip certification to demonstrate."

# ╔═╡ 62257a75-2949-4afc-8543-fe3fa4073be5
md"## Example: Chip certification

Imagine you're a microchip certification engineer.  You probe microchips coming off the supply line to see if they are good or bad.  A microchip is bad if its power pin (which is the first pin) has a zero voltage.  If any of the other pins have zero voltage it's salvageable, and we'll say it's a good pin.  For simplicitly, we assume that only one (and exactly one) pin is faulty."

# ╔═╡ 53572568-9d02-465a-baba-1c624d79d4b5
md"We'll express our prior belief over which pin is faulty using a discrete uniform distribution over the 10 pins:"

# ╔═╡ 49b116d3-dc2f-4e1d-9bff-41131e8148c2
Normal

# ╔═╡ 4936c45a-a5bf-49cb-bfdc-c05883d5982b
faulty_pin = 1 ~ DiscreteUniform(1, 10)

# ╔═╡ 57c308fa-a2e7-49fb-b52d-41346ee7ea0d
md"The probe tells us which pin is faulty.  Unfortunately, the probe is a little error prone.  Under normal operation it gives back the true answer, but with some probability it just gives back a random answer between 1 and 10"

# ╔═╡ d3af8df6-5375-4a52-9432-41ef6227af0c
error_prob_rv(id, ω) = 0.01 # We're making this a random variable to be able to intervene it later

# ╔═╡ aa5ea98f-5db3-4de5-89e4-fe1ca27c0157
error_prob = 2 ~ error_prob_rv

# ╔═╡ b0769639-7b6a-4d95-bc8d-bdedd5d27c4f
error_occurred(ω) = (3 ~ Bernoulli(error_prob(ω)))(ω)

# ╔═╡ 8e2fb0c5-ca50-4bcb-85bf-d78c06ea5653
alternative_pin = 4 ~ DiscreteUniform(1, 10)

# ╔═╡ ad3ec928-dc20-4987-aaed-78e8c4141d3e
function measure(ω)
	if error_occurred(ω)
		alternative_pin(ω)
	else
		faulty_pin(ω)
	end
end

# ╔═╡ 87199546-b427-4908-9531-28d40995efa8
md"As described above, a chip is bad if the faulty_pin is pin 1"

# ╔═╡ 4b8285ca-0fa8-4c38-a2a9-870169a2c1d7
bad_chip = faulty_pin ==ₚ 1

# ╔═╡ 0ed2799b-0e1b-434a-85be-99a3869a89c7
prob(x; n = 1000) = mean(randsample(x, n))

# ╔═╡ 505f497c-2852-44f2-bf17-8bfb12886554
md"The probability that it's a bad chip is:"

# ╔═╡ fc03484c-206d-4c3d-90f9-773e3b9b0a90
prob(bad_chip)

# ╔═╡ 413d05ce-ed65-406e-be97-32a2bad22d92
md"Now suppose we use our probe and observe a measurement of 1"

# ╔═╡ ff0aced3-466f-44e8-8d84-9521fca7c7c4
evidence = measure ==ₚ 1;

# ╔═╡ 233e3ee2-e56c-4c4d-a53d-83c144c303d0
md"Given the evidence, we can look at our conditional belief over which pin is faulty:"

# ╔═╡ 5774b63a-d492-490e-862a-0c3645722885
histogram(randsample(cnd(faulty_pin, evidence), 1000))

# ╔═╡ c6d93cdd-a2bd-4e5b-b835-1509cc582978
md"And compute the conditional probability that it is indeed a bad chip (faulty pin == 1)"

# ╔═╡ 32b3da83-0fb4-4a99-9742-46f9ad13eb8b
conditional_bad_chip = cnd(bad_chip, evidence);

# ╔═╡ 5ddfb321-d696-4853-bb9a-f3b8593f074d
md"Given the evidence, the conditional probability the chip is bad is high, at:"

# ╔═╡ ff904fa3-898b-4c35-a1c4-8a08ca5f82df
prob_bad = prob(conditional_bad_chip)

# ╔═╡ ae28acc2-fb0f-4189-bdaa-574a3e090f75
md"The certification handbook says a chip can be ceritifed if there's less than a 20% chance that it is faulty"

# ╔═╡ dbe58fac-bc39-4ee1-8930-6bb4e8453317
can_certify(p) = p < 0.3

# ╔═╡ 03ac41b7-10fd-4466-976d-f2815fe655a2
md"Clearly, we cannot certify this chip:"

# ╔═╡ 6b9ac9fa-56c3-453f-aba7-69cd193d91c3
can_certify(prob_bad)

# ╔═╡ 9ef8cafd-49e5-439a-9723-479babd7e6d7
md" \"Not to worry!\" your colleague.  Sneaky Simon says.  \"Just use the bad probe.\""

# ╔═╡ 8c128635-e46d-418e-8c51-d74fc55973e4
md"We'll use `intervene` in Omega to construct a different model where the error rate is different"

# ╔═╡ aa15703f-6137-4d67-bb25-bec070d3d193
error_prob_noisy = 0.9

# ╔═╡ da0608ac-94bd-4ba1-81be-1cde40bd4cae
conditional_bad_chip_noisy_probe = intervene(conditional_bad_chip, error_prob => error_prob_noisy);

# ╔═╡ 828161b0-c32e-4ae8-9206-1f7ce95dfda4
prob_bad_noisy = prob(conditional_bad_chip_noisy_probe)

# ╔═╡ 1e1a3659-0a82-46c1-9b6e-0f8de142f9be
md"Job done?"

# ╔═╡ b6470b88-3ac0-4ccf-81df-c6f80e409a64
can_certify(prob_bad_noisy)

# ╔═╡ abe64bc4-cdef-4cb5-80cc-2e99e792ecab
md"Apparently, Sneaky Simon was right.  Using the bad probe has allowed us to certify the chip.  Is this right?  If not, what has gone wrong?"

# ╔═╡ 672b6bfa-54ce-4b12-80f0-ee930a777cbc
probwow = pw(prob, rid(conditional_bad_chip_noisy_probe, (faulty_pin, alternative_pin)))

# ╔═╡ 36a6cb8a-f81e-4e05-9dd0-a475e88ab62c
histogram(randsample(probwow, 100))

# ╔═╡ 00000000-0000-0000-0000-000000000001
PLUTO_PROJECT_TOML_CONTENTS = """
[deps]
Distributions = "31c24e10-a181-5473-b8eb-7969acd0382f"
Omega = "1af16e33-887a-59b3-8344-18f1671b3ade"
UnicodePlots = "b8865327-cd53-5732-bb35-84acbb429228"

[compat]
Distributions = "~0.23.12"
UnicodePlots = "~2.4.6"
"""

# ╔═╡ 00000000-0000-0000-0000-000000000002
PLUTO_MANIFEST_TOML_CONTENTS = """
# This file is machine-generated - editing it directly is not advised

[[ArgTools]]
uuid = "0dad84c5-d112-42e6-8d28-ef12dabb789f"

[[Artifacts]]
uuid = "56f22d72-fd6d-98f1-02f0-08ddc0907c33"

[[Base64]]
uuid = "2a0f44e3-6c83-55bd-87e4-b1978d98bd5f"

[[Cassette]]
git-tree-sha1 = "6ce3cd755d4130d43bab24ea5181e77b89b51839"
uuid = "7057c7e9-c182-5462-911a-8362d720325c"
version = "0.3.9"

[[ChainRulesCore]]
deps = ["Compat", "LinearAlgebra", "SparseArrays"]
git-tree-sha1 = "f885e7e7c124f8c92650d61b9477b9ac2ee607dd"
uuid = "d360d2e6-b24c-11e9-a2a3-2a2ae2dbcce4"
version = "1.11.1"

[[ChangesOfVariables]]
deps = ["LinearAlgebra", "Test"]
git-tree-sha1 = "9a1d594397670492219635b35a3d830b04730d62"
uuid = "9e997f8a-9a97-42d5-a9f1-ce6bfc15e2c0"
version = "0.1.1"

[[Compat]]
deps = ["Base64", "Dates", "DelimitedFiles", "Distributed", "InteractiveUtils", "LibGit2", "Libdl", "LinearAlgebra", "Markdown", "Mmap", "Pkg", "Printf", "REPL", "Random", "SHA", "Serialization", "SharedArrays", "Sockets", "SparseArrays", "Statistics", "Test", "UUIDs", "Unicode"]
git-tree-sha1 = "dce3e3fea680869eaa0b774b2e8343e9ff442313"
uuid = "34da2185-b29b-5c13-b0c7-acf172513d20"
version = "3.40.0"

[[CompilerSupportLibraries_jll]]
deps = ["Artifacts", "Libdl"]
uuid = "e66e0078-7015-5450-92f7-15fbd957f2ae"

[[Crayons]]
git-tree-sha1 = "3f71217b538d7aaee0b69ab47d9b7724ca8afa0d"
uuid = "a8cc5b0e-0ffa-5ad4-8c14-923d3ee1735f"
version = "4.0.4"

[[DataAPI]]
git-tree-sha1 = "cc70b17275652eb47bc9e5f81635981f13cea5c8"
uuid = "9a962f9c-6df0-11e9-0e5d-c546b8b5ee8a"
version = "1.9.0"

[[DataStructures]]
deps = ["Compat", "InteractiveUtils", "OrderedCollections"]
git-tree-sha1 = "7d9d316f04214f7efdbb6398d545446e246eff02"
uuid = "864edb3b-99cc-5e75-8d2d-829cb0a9cfe8"
version = "0.18.10"

[[Dates]]
deps = ["Printf"]
uuid = "ade2ca70-3891-5945-98fb-dc099432e06a"

[[DelimitedFiles]]
deps = ["Mmap"]
uuid = "8bb1440f-4735-579b-a4ab-409b98df4dab"

[[Distributed]]
deps = ["Random", "Serialization", "Sockets"]
uuid = "8ba89e20-285c-5b6f-9357-94700520ee1b"

[[Distributions]]
deps = ["FillArrays", "LinearAlgebra", "PDMats", "Printf", "QuadGK", "Random", "SparseArrays", "SpecialFunctions", "StaticArrays", "Statistics", "StatsBase", "StatsFuns"]
git-tree-sha1 = "501c11d708917ca09ce357bed163dbaf0f30229f"
uuid = "31c24e10-a181-5473-b8eb-7969acd0382f"
version = "0.23.12"

[[DocStringExtensions]]
deps = ["LibGit2"]
git-tree-sha1 = "b19534d1895d702889b219c382a6e18010797f0b"
uuid = "ffbed154-4ef7-542d-bbb7-c09d3a79fcae"
version = "0.8.6"

[[Downloads]]
deps = ["ArgTools", "LibCURL", "NetworkOptions"]
uuid = "f43a241f-c20a-4ad4-852c-f6b1247861c6"

[[FillArrays]]
deps = ["LinearAlgebra", "Random", "SparseArrays"]
git-tree-sha1 = "502b3de6039d5b78c76118423858d981349f3823"
uuid = "1a297f60-69ca-5386-bcde-b61e274b549b"
version = "0.9.7"

[[Future]]
deps = ["Random"]
uuid = "9fa8497b-333b-5362-9e8d-4d0656e87820"

[[InferenceBase]]
deps = ["OmegaCore"]
path = "../../../home/zenna/repos/Omega.jl/InferenceBase"
uuid = "5213bc24-6d0f-4e1b-8b55-aef4cfc4ccc3"
version = "0.1.0"

[[InteractiveUtils]]
deps = ["Markdown"]
uuid = "b77e0a4c-d291-57a0-90e8-8db25a27a240"

[[InverseFunctions]]
deps = ["Test"]
git-tree-sha1 = "a7254c0acd8e62f1ac75ad24d5db43f5f19f3c65"
uuid = "3587e190-3f89-42d0-90ee-14403ec27112"
version = "0.1.2"

[[IrrationalConstants]]
git-tree-sha1 = "7fd44fd4ff43fc60815f8e764c0f352b83c49151"
uuid = "92d709cd-6900-40b7-9082-c6be49f344b6"
version = "0.1.1"

[[JLLWrappers]]
deps = ["Preferences"]
git-tree-sha1 = "642a199af8b68253517b80bd3bfd17eb4e84df6e"
uuid = "692b3bcd-3c85-4b1f-b108-f13ce0eb3210"
version = "1.3.0"

[[LibCURL]]
deps = ["LibCURL_jll", "MozillaCACerts_jll"]
uuid = "b27032c2-a3e7-50c8-80cd-2d36dbcbfd21"

[[LibCURL_jll]]
deps = ["Artifacts", "LibSSH2_jll", "Libdl", "MbedTLS_jll", "Zlib_jll", "nghttp2_jll"]
uuid = "deac9b47-8bc7-5906-a0fe-35ac56dc84c0"

[[LibGit2]]
deps = ["Base64", "NetworkOptions", "Printf", "SHA"]
uuid = "76f85450-5226-5b5a-8eaa-529ad045b433"

[[LibSSH2_jll]]
deps = ["Artifacts", "Libdl", "MbedTLS_jll"]
uuid = "29816b5a-b9ab-546f-933c-edad1886dfa8"

[[Libdl]]
uuid = "8f399da3-3557-5675-b5ff-fb832c97cbdb"

[[LinearAlgebra]]
deps = ["Libdl"]
uuid = "37e2e46d-f89d-539d-b4ee-838fcccc9c8e"

[[LogExpFunctions]]
deps = ["ChainRulesCore", "ChangesOfVariables", "DocStringExtensions", "InverseFunctions", "IrrationalConstants", "LinearAlgebra"]
git-tree-sha1 = "be9eef9f9d78cecb6f262f3c10da151a6c5ab827"
uuid = "2ab3a3ac-af41-5b50-aa03-7779005ae688"
version = "0.3.5"

[[Logging]]
uuid = "56ddb016-857b-54e1-b83d-db4d58db5568"

[[Markdown]]
deps = ["Base64"]
uuid = "d6f4376e-aef5-505a-96c1-9c027394607a"

[[MbedTLS_jll]]
deps = ["Artifacts", "Libdl"]
uuid = "c8ffd9c3-330d-5841-b78e-0817d7145fa1"

[[Missings]]
deps = ["DataAPI"]
git-tree-sha1 = "bf210ce90b6c9eed32d25dbcae1ebc565df2687f"
uuid = "e1d29d7a-bbdc-5cf2-9ac0-f12de2c33e28"
version = "1.0.2"

[[Mmap]]
uuid = "a63ad114-7e13-5084-954f-fe012c677804"

[[MozillaCACerts_jll]]
uuid = "14a3606d-f60d-562e-9121-12d972cd8159"

[[NetworkOptions]]
uuid = "ca575930-c2e3-43a9-ace4-1e988b2c1908"

[[Omega]]
deps = ["Distributions", "InferenceBase", "OmegaCore", "OmegaDistributions", "OmegaMH", "OmegaSoftPredicates", "Reexport", "ReplicaExchange", "SoftPredicates"]
path = "../../../home/zenna/repos/Omega.jl"
uuid = "1af16e33-887a-59b3-8344-18f1671b3ade"
version = "0.2.0"

[[OmegaCore]]
deps = ["Future", "Random", "Reexport", "Spec"]
path = "../../../home/zenna/repos/Omega.jl/OmegaCore"
uuid = "84d23798-d00f-4e9b-a82e-be69778c030a"
version = "0.1.0"

[[OmegaDistributions]]
deps = ["Distributions", "OmegaCore"]
path = "../../../home/zenna/repos/Omega.jl/connectors/OmegaDistributions"
uuid = "4ee16af8-c862-4b7a-9514-3b66b113c005"
version = "0.1.0"

[[OmegaMH]]
deps = ["InferenceBase", "OmegaCore", "SoftPredicates"]
path = "../../../home/zenna/repos/Omega.jl/OmegaMH"
uuid = "89eb2d39-e1f3-436d-870a-9a4679d6d79e"
version = "0.1.0"

[[OmegaSoftPredicates]]
deps = ["InferenceBase", "OmegaCore", "SoftPredicates"]
path = "../../../home/zenna/repos/Omega.jl/connectors/OmegaSoftPredicates"
uuid = "ffc32627-273f-428b-9998-33a39d288549"
version = "0.1.0"

[[OpenSpecFun_jll]]
deps = ["Artifacts", "CompilerSupportLibraries_jll", "JLLWrappers", "Libdl", "Pkg"]
git-tree-sha1 = "13652491f6856acfd2db29360e1bbcd4565d04f1"
uuid = "efe28fd5-8261-553b-a9e1-b2916fc3738e"
version = "0.5.5+0"

[[OrderedCollections]]
git-tree-sha1 = "85f8e6578bf1f9ee0d11e7bb1b1456435479d47c"
uuid = "bac558e1-5e72-5ebc-8fee-abe8a469f55d"
version = "1.4.1"

[[PDMats]]
deps = ["LinearAlgebra", "SparseArrays", "SuiteSparse", "Test"]
git-tree-sha1 = "95a4038d1011dfdbde7cecd2ad0ac411e53ab1bc"
uuid = "90014a1f-27ba-587c-ab20-58faa44d9150"
version = "0.10.1"

[[Pkg]]
deps = ["Artifacts", "Dates", "Downloads", "LibGit2", "Libdl", "Logging", "Markdown", "Printf", "REPL", "Random", "SHA", "Serialization", "TOML", "Tar", "UUIDs", "p7zip_jll"]
uuid = "44cfe95a-1eb2-52ea-b672-e2afdf69b78f"

[[Preferences]]
deps = ["TOML"]
git-tree-sha1 = "00cfd92944ca9c760982747e9a1d0d5d86ab1e5a"
uuid = "21216c6a-2e73-6563-6e65-726566657250"
version = "1.2.2"

[[Printf]]
deps = ["Unicode"]
uuid = "de0858da-6303-5e67-8744-51eddeeeb8d7"

[[QuadGK]]
deps = ["DataStructures", "LinearAlgebra"]
git-tree-sha1 = "78aadffb3efd2155af139781b8a8df1ef279ea39"
uuid = "1fd47b50-473d-5c70-9696-f719f8f3bcdc"
version = "2.4.2"

[[REPL]]
deps = ["InteractiveUtils", "Markdown", "Sockets", "Unicode"]
uuid = "3fa0cd96-eef1-5676-8a61-b3b8758bbffb"

[[Random]]
deps = ["Serialization"]
uuid = "9a3f8284-a2c9-5f02-9a11-845980a1fd5c"

[[Reexport]]
git-tree-sha1 = "45e428421666073eab6f2da5c9d310d99bb12f9b"
uuid = "189a3867-3050-52da-a836-e630ba90ab69"
version = "1.2.2"

[[ReplicaExchange]]
deps = ["InferenceBase", "OmegaCore", "Spec"]
path = "../../../home/zenna/repos/Omega.jl/ReplicaExchange"
uuid = "5ad4e244-73e6-47c5-b007-45e12ac3dae1"
version = "0.1.0"

[[Rmath]]
deps = ["Random", "Rmath_jll"]
git-tree-sha1 = "bf3188feca147ce108c76ad82c2792c57abe7b1f"
uuid = "79098fc4-a85e-5d69-aa6a-4863f24498fa"
version = "0.7.0"

[[Rmath_jll]]
deps = ["Artifacts", "JLLWrappers", "Libdl", "Pkg"]
git-tree-sha1 = "68db32dff12bb6127bac73c209881191bf0efbb7"
uuid = "f50d1b31-88e8-58de-be2c-1cc44531875f"
version = "0.3.0+0"

[[SHA]]
uuid = "ea8e919c-243c-51af-8825-aaa63cd721ce"

[[Serialization]]
uuid = "9e88b42a-f829-5b0c-bbe9-9e923198166b"

[[SharedArrays]]
deps = ["Distributed", "Mmap", "Random", "Serialization"]
uuid = "1a1011a3-84de-559e-8e89-a11a2f7dc383"

[[Sockets]]
uuid = "6462fe0b-24de-5631-8697-dd941f90decc"

[[SoftPredicates]]
deps = ["Cassette", "DocStringExtensions", "InferenceBase", "LinearAlgebra", "Spec"]
path = "../../../home/zenna/repos/Omega.jl/SoftPredicates"
uuid = "5345b20a-9614-40c4-b281-8f4998fc0f3b"
version = "0.1.0"

[[SortingAlgorithms]]
deps = ["DataStructures"]
git-tree-sha1 = "b3363d7460f7d098ca0912c69b082f75625d7508"
uuid = "a2af1166-a08f-5f64-846c-94a0d3cef48c"
version = "1.0.1"

[[SparseArrays]]
deps = ["LinearAlgebra", "Random"]
uuid = "2f01184e-e22b-5df5-ae63-d93ebab69eaf"

[[Spec]]
deps = ["Cassette", "Pkg", "Random", "Test"]
git-tree-sha1 = "01317d4b40fe250c4cd07323584070c3d2d82811"
uuid = "b8ccf107-3a88-5e0f-823b-b838c6a0f327"
version = "0.2.0"

[[SpecialFunctions]]
deps = ["OpenSpecFun_jll"]
git-tree-sha1 = "d8d8b8a9f4119829410ecd706da4cc8594a1e020"
uuid = "276daf66-3868-5448-9aa4-cd146d93841b"
version = "0.10.3"

[[StaticArrays]]
deps = ["LinearAlgebra", "Random", "Statistics"]
git-tree-sha1 = "da4cf579416c81994afd6322365d00916c79b8ae"
uuid = "90137ffa-7385-5640-81b9-e52037218182"
version = "0.12.5"

[[Statistics]]
deps = ["LinearAlgebra", "SparseArrays"]
uuid = "10745b16-79ce-11e8-11f9-7d13ad32a3b2"

[[StatsAPI]]
git-tree-sha1 = "1958272568dc176a1d881acb797beb909c785510"
uuid = "82ae8749-77ed-4fe6-ae5f-f523153014b0"
version = "1.0.0"

[[StatsBase]]
deps = ["DataAPI", "DataStructures", "LinearAlgebra", "LogExpFunctions", "Missings", "Printf", "Random", "SortingAlgorithms", "SparseArrays", "Statistics", "StatsAPI"]
git-tree-sha1 = "eb35dcc66558b2dda84079b9a1be17557d32091a"
uuid = "2913bbd2-ae8a-5f71-8c99-4fb6c76f3a91"
version = "0.33.12"

[[StatsFuns]]
deps = ["ChainRulesCore", "InverseFunctions", "IrrationalConstants", "LogExpFunctions", "Reexport", "Rmath", "SpecialFunctions"]
git-tree-sha1 = "385ab64e64e79f0cd7cfcf897169b91ebbb2d6c8"
uuid = "4c63d2b9-4356-54db-8cca-17b64c39e42c"
version = "0.9.13"

[[SuiteSparse]]
deps = ["Libdl", "LinearAlgebra", "Serialization", "SparseArrays"]
uuid = "4607b0f0-06f3-5cda-b6b1-a6196a1729e9"

[[TOML]]
deps = ["Dates"]
uuid = "fa267f1f-6049-4f14-aa54-33bafae1ed76"

[[Tar]]
deps = ["ArgTools", "SHA"]
uuid = "a4e569a6-e804-4fa4-b0f3-eef7a1d5b13e"

[[Test]]
deps = ["InteractiveUtils", "Logging", "Random", "Serialization"]
uuid = "8dfed614-e22c-5e08-85e1-65c5234f0b40"

[[UUIDs]]
deps = ["Random", "SHA"]
uuid = "cf7118a7-6976-5b1a-9a39-7adc72f591a4"

[[Unicode]]
uuid = "4ec0a83e-493e-50e2-b9ac-8f72acf5a8f5"

[[UnicodePlots]]
deps = ["Crayons", "Dates", "SparseArrays", "StatsBase"]
git-tree-sha1 = "f1d09f14722f5f3cef029bcb031be91a92613ae9"
uuid = "b8865327-cd53-5732-bb35-84acbb429228"
version = "2.4.6"

[[Zlib_jll]]
deps = ["Libdl"]
uuid = "83775a58-1f1d-513f-b197-d71354ab007a"

[[nghttp2_jll]]
deps = ["Artifacts", "Libdl"]
uuid = "8e850ede-7688-5339-a07c-302acd2aaf8d"

[[p7zip_jll]]
deps = ["Artifacts", "Libdl"]
uuid = "3f19e933-33d8-53b3-aaab-bd5110c3b7a0"
"""

# ╔═╡ Cell order:
# ╟─daa9fd86-5a36-4aa2-842e-477cdb19b8d5
# ╠═62257a75-2949-4afc-8543-fe3fa4073be5
# ╟─53572568-9d02-465a-baba-1c624d79d4b5
# ╠═f0f80b1a-d090-11eb-2b0d-d11fd8196311
# ╠═49b116d3-dc2f-4e1d-9bff-41131e8148c2
# ╠═4936c45a-a5bf-49cb-bfdc-c05883d5982b
# ╟─57c308fa-a2e7-49fb-b52d-41346ee7ea0d
# ╠═d3af8df6-5375-4a52-9432-41ef6227af0c
# ╠═aa5ea98f-5db3-4de5-89e4-fe1ca27c0157
# ╠═b0769639-7b6a-4d95-bc8d-bdedd5d27c4f
# ╠═8e2fb0c5-ca50-4bcb-85bf-d78c06ea5653
# ╠═ad3ec928-dc20-4987-aaed-78e8c4141d3e
# ╟─87199546-b427-4908-9531-28d40995efa8
# ╠═4b8285ca-0fa8-4c38-a2a9-870169a2c1d7
# ╠═0ed2799b-0e1b-434a-85be-99a3869a89c7
# ╟─505f497c-2852-44f2-bf17-8bfb12886554
# ╠═fc03484c-206d-4c3d-90f9-773e3b9b0a90
# ╟─413d05ce-ed65-406e-be97-32a2bad22d92
# ╠═ff0aced3-466f-44e8-8d84-9521fca7c7c4
# ╟─233e3ee2-e56c-4c4d-a53d-83c144c303d0
# ╠═5774b63a-d492-490e-862a-0c3645722885
# ╟─c6d93cdd-a2bd-4e5b-b835-1509cc582978
# ╠═32b3da83-0fb4-4a99-9742-46f9ad13eb8b
# ╟─5ddfb321-d696-4853-bb9a-f3b8593f074d
# ╠═ff904fa3-898b-4c35-a1c4-8a08ca5f82df
# ╟─ae28acc2-fb0f-4189-bdaa-574a3e090f75
# ╠═dbe58fac-bc39-4ee1-8930-6bb4e8453317
# ╟─03ac41b7-10fd-4466-976d-f2815fe655a2
# ╠═6b9ac9fa-56c3-453f-aba7-69cd193d91c3
# ╟─9ef8cafd-49e5-439a-9723-479babd7e6d7
# ╟─8c128635-e46d-418e-8c51-d74fc55973e4
# ╠═aa15703f-6137-4d67-bb25-bec070d3d193
# ╠═da0608ac-94bd-4ba1-81be-1cde40bd4cae
# ╠═828161b0-c32e-4ae8-9206-1f7ce95dfda4
# ╟─1e1a3659-0a82-46c1-9b6e-0f8de142f9be
# ╠═b6470b88-3ac0-4ccf-81df-c6f80e409a64
# ╟─abe64bc4-cdef-4cb5-80cc-2e99e792ecab
# ╠═672b6bfa-54ce-4b12-80f0-ee930a777cbc
# ╠═36a6cb8a-f81e-4e05-9dd0-a475e88ab62c
# ╟─00000000-0000-0000-0000-000000000001
# ╟─00000000-0000-0000-0000-000000000002

max_stars_repo_name: zenna/expect

max_issues_repo_name: zenna/expect

max_forks_repo_name: zenna/expect


text:
"""
A flavor of TOML for more general data-serialization,
    including support for 'null' values, infinities, and NaN's.
Also supports JSON3-esque serialization of data structures, using `StructTypes`.
"""
module WOML

using Dates
using TOML, StructTypes

include("toml-type.jl")
include("unions.jl")
include("converter.jl")

"
Parses a TOML string into the given type.
The type defaults to `Dict{String, Any}`, same as the original TOML package.
"
@inline read(toml::AbstractString, T...) = read(IOBuffer(toml, write=false), T...)

function read(io::IO, T = Dict{String, Any})
    struct_type = StructTypes.StructType(T)

end

export CM_Read, CM_Write

end # module


text:
const LABELLED_SQUARES = [*(args...) for args in Base.product("hgfedcba","12345678")]
const LABEL_TO_SQUARE = Dict(reshape(LABELLED_SQUARES, 64) .=> 1:64)

const START_FEN = "rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1"

"""
    importfen(fen::String)

Create a `Board` object from an input FEN, given as a `String`.
"""
function importfen(fen::String)
    board = Board()

    # break down components of the string
    parts = split(fen, r"\s+")

    # start from square 64 and go backwards
    sqr = 64
    for char in parts[1]
        piece = chartopiece(char)
        if piece !== BLANK
            add!(board, piece, sqr)
            sqr -= 1
        elseif '1' <= char <= '8'
            sqr -= parse(Int, char)
        elseif char == '/'
            nothing
        else
            error("Could not process input")
        end
    end

    # update who's turn it is
    turn = get(parts, 2, "w")
    if isequal(turn, "w")
        board.turn = WHITE
    else
        board.turn = BLACK
        board.hash ⊻= zobturnkey()
    end

    # fix castling rights
    castling = get(parts, 3, "-")
    for char in castling
        i = findfirst(isequal(char), "KkQq")
        if i !== nothing
            board.castling |= UInt8(1) << (i - 1)
            board.hash ⊻= zobookey(UInt8(1) << (i - 1))
        end
    end

    # annotate the enpassant square
    enpass = get(parts, 4, "-")
    if !isequal(enpass, "-")
        sqr = LABEL_TO_SQUARE[enpass]
        board.enpass = sqr
        board.hash ⊻= zobepkey(sqr)
    end

    board.halfmovecount = parse(Int, get(parts, 5, "0"))
    board.movecount = parse(Int, get(parts, 6, "1")) * 2
    if board.turn == WHITE
        board.movecount -= 1
    end

    board.pinned = findpins(board)
    board.checkers = kingAttackers(board)

    board.history = ZobristHash.(zeros(UInt64, 512))
    board.history[board.movecount] = board.hash

    board
end

"""
    exportfen(board::Board)

Create a FEN 'String' object from a given 'Board'.
"""
function exportfen(board::Board)
    fen = Vector{SubString{String}}()

    # core string
    skip = '0'
    core = ""
    for sqr in 64:-1:1

        # handle line break
        if iszero(sqr%8) && (sqr < 64)
            if skip !== '0'
                core *= skip
                skip = '0'
            end
            core *= '/'
        end

        # extract char
        char = piecetochar(board.squares[sqr])

        # blank square
        if char == '1'
            skip += 1

        # new line or piece char
        else
            if skip !== '0'
                core *= skip
                skip = '0'
            end
            core *= char
        end
    end
    push!(fen, core)

    # add color
    if board.turn == WHITE
        push!(fen, "w")
    else
        push!(fen, "b")
    end

    # add castling
    castle = ""
    cancastlekingside(board, WHITE) && (castle *= 'K')
    cancastlequeenside(board, WHITE) && (castle *= 'Q')
    cancastlekingside(board, BLACK) && (castle *= 'k')
    cancastlequeenside(board, BLACK) && (castle *= 'q')
    (castle == "") && (castle *= '-')
    push!(fen, castle)

    # add enpassant
    enpass = ""
    iszero(board.enpass) ? (enpass *= '-') : (enpass *= LABELLED_SQUARES[board.enpass])
    push!(fen, enpass)

    # add halfmovecount
    push!(fen, "$(board.halfmovecount)")

    # add fullmovecount
    push!(fen, "$(board.movecount)")

    return join(fen, " ")
end

"""
    chartopiece(c::Char)

Converts a `Char` from the FEN to its respective `Piece` type.
"""
function chartopiece(c::Char)
    if c == 'r'
        return BLACKROOK
    elseif c == 'n'
        return BLACKKNIGHT
    elseif c == 'b'
        return BLACKBISHOP
    elseif c == 'q'
        return BLACKQUEEN
    elseif c == 'k'
        return BLACKKING
    elseif c == 'p'
        return BLACKPAWN
    elseif c == 'R'
        return WHITEROOK
    elseif c == 'N'
        return WHITEKNIGHT
    elseif c == 'B'
        return WHITEBISHOP
    elseif c == 'Q'
        return WHITEQUEEN
    elseif c == 'K'
        return WHITEKING
    elseif c == 'P'
        return WHITEPAWN
    else
        return BLANK
    end
end

"""
    piecetochar(p::Piece)

Converts a `Piece` to its respective FEN `Char`.
"""
function piecetochar(p::Piece)
    if p == BLACKROOK
        return 'r'
    elseif p == BLACKKNIGHT
        return 'n'
    elseif p == BLACKBISHOP
        return 'b'
    elseif p == BLACKQUEEN
        return 'q'
    elseif p == BLACKKING
        return 'k'
    elseif p == BLACKPAWN
        return 'p'
    elseif p == WHITEROOK
        return 'R'
    elseif p == WHITEKNIGHT
        return 'N'
    elseif p == WHITEBISHOP
        return 'B'
    elseif p == WHITEQUEEN
        return 'Q'
    elseif p == WHITEKING
        return 'K'
    elseif p == WHITEPAWN
        return 'P'
    else
        # will be a blank, which needs special consideration
        return '1'
    end
end

max_stars_repo_name: J-Revell/Astellarn

max_issues_repo_name: J-Revell/Astellarn

max_forks_repo_name: J-Revell/Astellarn


text:
import Gaugefields:staggered_U

struct StaggeredFermion_4D_nowing{NC} <: AbstractFermionfields_4D{NC}
    NC::Int64
    NX::Int64
    NY::Int64
    NZ::Int64
    NT::Int64
    NDW::Int64
    NG::Int64 #size of the Gamma matrix. In Staggered fermion, this is one.
    NV::Int64
    f::Array{ComplexF64,6}
    Dirac_operator::String
    fshifted::Array{ComplexF64,6}

    function StaggeredFermion_4D_nowing(NC,NX,NY,NZ,NT)
        NG = 1
        NDW = 0
        NV = NC*NX*NY*NZ*NT*NG
        #@assert NDW == 1 "only NDW = 1 is supported. Now NDW = $NDW"
        f = zeros(ComplexF64,NC,NX+2NDW,NY+2NDW,NZ+2NDW,NT+2NDW,NG)
        fshifted = zero(f)
        Dirac_operator = "Staggered"
        return new{NC}(NC,NX,NY,NZ,NT,NDW,NG,NV,f,Dirac_operator,fshifted)
    end
end

function Base.size(x::StaggeredFermion_4D_nowing{NC}) where NC
    return (x.NC,x.NX,x.NY,x.NZ,x.NT,x.NG)
    #return (x.NV,)
end

function Base.length(x::StaggeredFermion_4D_nowing{NC}) where {NC}
    return NC*x.NX*x.NY*x.NZ*x.NT*x.NG
end

function Base.similar(x::T) where T <: StaggeredFermion_4D_nowing
    return StaggeredFermion_4D_nowing(x.NC,x.NX,x.NY,x.NZ,x.NT)
end

function Dx!(xout::T,U::Array{G,1},
    x::T,temps::Array{T,1},boundarycondition) where  {T <: StaggeredFermion_4D_nowing,G <:AbstractGaugefields}
    #temp = temps[4]
    temp1 = temps[1]
    temp2 = temps[2]

    #clear!(temp)
    set_wing_fermion!(x,boundarycondition)
    clear_fermion!(xout)
    for ν=1:4
        xplus = shift_fermion(x,ν)
        Us = staggered_U(U[ν],ν)
        mul!(temp1,Us,xplus)

        xminus = shift_fermion(x,-ν)
        Uminus = shift_U(U[ν],-ν)
        Uminus_s = staggered_U(Uminus,ν)
        mul!(temp2,Uminus_s',xminus)

        add_fermion!(xout,0.5,temp1,-0.5,temp2)

        #fermion_shift!(temp1,U,ν,x)
        #fermion_shift!(temp2,U,-ν,x)
        #add!(xout,0.5,temp1,-0.5,temp2)

    end

    set_wing_fermion!(xout,boundarycondition)

    return
end

function clear_fermion!(x::StaggeredFermion_4D_nowing{NC},evensite) where NC
    ibush = ifelse(evensite,0,1)
    for it=1:x.NT
        for iz=1:x.NZ
            for iy=1:x.NY
                xran =1+(1+ibush+iy+iz+it)%2:2:x.NX
                for ix in xran
                    @simd for ic=1:NC
                        x[ic,ix,iy,iz,it,1] = 0
                    end
                end
            end
        end
    end
    return
end

function shift_fermion(F::StaggeredFermion_4D_nowing{NC},ν::T) where {T <: Integer,NC}
    if ν == 1
        shift = (1,0,0,0)
    elseif ν == 2
        shift = (0,1,0,0)
    elseif ν == 3
        shift = (0,0,1,0)
    elseif ν == 4
        shift = (0,0,0,1)
    elseif ν == -1
            shift = (-1,0,0,0)
    elseif ν == -2
            shift = (0,-1,0,0)
    elseif ν == -3
            shift = (0,0,-1,0)
    elseif ν == -4
            shift = (0,0,0,-1)
    end

    return Shifted_fermionfields_4D_nowing(F,shift)
end

function shift_fermion(F::TF,shift::NTuple{Dim,T}) where {Dim,T <: Integer,TF <: StaggeredFermion_4D_nowing}
    return Shifted_fermionfields_4D_nowing(F,shift)
end

function shifted_fermion!(x::StaggeredFermion_4D_nowing{NC},boundarycondition,shift) where NC
    NX = x.NX
    NY = x.NY
    NZ = x.NZ
    NT = x.NT
    factor_t = 1
    factor_z = 1
    factor_y = 1
    factor_x = 1
    bc = boundarycondition

    #n6 = size(x.f)[6]
    #f = zeros(ComplexF64,4)
    #e = zeros(ComplexF64,4)

    #for ic=1:NC
    for ig = 1:1
        for it=1:NT
            it_shifted = it + shift[4]
            inside_up = it_shifted > NT
            inside_down = it_shifted < 1
            factor_t = ifelse(inside_up || inside_down,bc[4],1)
            it_shifted += ifelse(inside_up,-NT,0)
            it_shifted += ifelse(inside_down,+NT,0)
            for iz=1:NZ
                iz_shifted = iz + shift[3]
                inside_up = iz_shifted > NZ
                inside_down = iz_shifted < 1
                factor_z = ifelse(inside_up || inside_down,bc[3],1)
                iz_shifted += ifelse(inside_up,-NZ,0)
                iz_shifted += ifelse(inside_down,+NZ,0)
                for iy=1:NY
                    iy_shifted = iy + shift[2]
                    inside_up = iy_shifted > NY
                    inside_down = iy_shifted < 1
                    factor_y = ifelse(inside_up || inside_down,bc[2],1)
                    iy_shifted += ifelse(inside_up,-NY,0)
                    iy_shifted += ifelse(inside_down,+NY,0)
                    for ix=1:NX
                        ix_shifted = ix + shift[1]
                        inside_up = ix_shifted > NX
                        inside_down = ix_shifted < 1
                        factor_x = ifelse(inside_up || inside_down,bc[1],1)
                        ix_shifted += ifelse(inside_up,-NX,0)
                        ix_shifted += ifelse(inside_down,+NX,0)
                        @inbounds @simd for ic=1:NC
                            #@code_warntype x.f[ic,ix_shifted,iy_shifted,iz_shifted,it_shifted,ig]
                            x.fshifted[ic,ix,iy,iz,it,ig] =
                                factor_x*factor_y*factor_z*factor_t*x[ic,ix_shifted,iy_shifted,iz_shifted,it_shifted,ig]
                        end
                    end
                end
            end
        end
    end
    #end

end

function set_wing_fermion!(a::StaggeredFermion_4D_nowing{NC},boundarycondition) where NC
   return
end


text:
export getColoringFirst
export getColoringSecond
export getColoringSecondS

# Make a maximal independent set of coarse nodes from the grid.
#
# The slowest part of the naive algorithm is taking max(lambda) over and over again
# A simple solution is updating the maximum as we increase values in lambda
# When no index of lambda has increased over the maximum, we need to check if the maximum is now lower

function getColoringFirst(S::SparseMatrixCSC, n::Int64)

	# lambda - count of strongly connected nodes to current
	# coloring -  will hold the C/F value for each node. C == 1, F == 0
	lambda = [0 for i=1:n]
	coloring = fill(0, n)
	rows = rowvals(S)

	# for each neighbour count, holds the nodes that has that number of neighbours.
	indeces = [Set{Int}() for i=1:n+1]

	# store by neigbour count, store max
	nmax = 0
	for i = 1:n
		lambda[i] = S.colptr[i+1] - S.colptr[i]
	end
	for i=1:n
		# Has only diagonal, make it free
		if(lambda[i] == 1)
			lambda[i] == 0
			coloring[i] == 0
		end
		push!(indeces[lambda[i] + 1],i)
		if (lambda[i] > nmax)
			nmax = lambda[i]
		end
	end

	while (nmax > 0)
		old_max = nmax

		# take a node that has a maximal neigbour count
		curr = pop!(indeces[nmax + 1])

		# set the node as coarse, and reset it's neigbour count
		coloring[curr] = 1
		lambda[curr] = 0

		# look at every neigbour it has
		for j in nzrange(S,curr)
			row = rows[j]
			if lambda[row] != 0
				# mark as free node
				pop!(indeces[lambda[row] + 1], row)
				lambda[row] = 0
				push!(indeces[lambda[row] + 1], row)
				coloring[row] = 0
			end
		end

		for j in nzrange(S,curr)
			row = rows[j]
			for k in nzrange(S, row)
				rowk = rows[k]
				# node was already set, ignore it.
				if (lambda[rowk] == 0)
					continue
				end

				# update node count
				pop!(indeces[lambda[rowk] + 1], rowk)
				lambda[rowk] += 1
				push!(indeces[lambda[rowk] + 1], rowk)

				# we have a new max
				if(lambda[rowk] > nmax)
					nmax = lambda[rowk]
				end
			end

		end

		# No new max, check if max should be lower
		if (old_max == nmax)
			for j=nmax:-1:0
				nmax = j
				if (~isempty(indeces[j + 1]))
					break
				end
			end
		end
	end
	coloring
end

# Change coloring according to heuristic:
# for every strongly connected F-F couple,
# both nodes has to have at least one common strongly connected C node.
function getColoringSecond(S::SparseMatrixCSC, coloring::Array, n::Int64)
	for i=1:n
		# This is a coarse node
		if coloring[i] == 1
			continue
		end
		# Split nodes strongly connected to i, into F and C sets
		fconn, cconn = strongSplitting(S, coloring, i)
		# Go through every F-F connection
		for j in fconn
			# if we don't have a common C node, make current node a C node
			if !hasCommonC(S, coloring, cconn, i, j)
				coloring[i] = 1
				break
			end
		end
	end
	return coloring
end

# Check if nodes i,j has a common strongly connected C node
function hasCommonC(S::SparseMatrixCSC, coloring::Array, cconn::Set{Int}, i::Int64, j::Int64)
	# Check for common C nodes
	for k in nzrange(S, j)
		if S.rowval[k] == i
			continue
		end
		if coloring[S.rowval[k]] == 1 && S.rowval[k] in cconn
			# println("Found F-F with common C : $i , $j, C is $(S.rowval[k])")
			return true
		end
	end
	return false
end

# Split the nodes strongly connected to i into coarse a set (cconn) and a free set (fconn)
function strongSplitting(S::SparseMatrixCSC, coloring::Array, i::Int64)
	fconn = Set{Int}()
	cconn = Set{Int}()

	for j in nzrange(S,i)
		# skip if this is a node already checked, or is the current node (that means i)
		if S.rowval[j] == i
			continue
		end
		if coloring[S.rowval[j]] == 0
			push!(fconn, S.rowval[j])
		else
			push!(cconn, S.rowval[j])
		end
	end
	fconn, cconn
end

## Alternative algorithm. Tries to minimize the coarse grid.

# idea
# get all F-F links for a free node, which do not have a common C neighbour and store in set.
# Do so for each free node - will be saved in an Array.
# now take the node with the maximal number of such neighbours,
# remove it from all it's neighbours' sets, remove it's set and turn it into a coarse node.
# repeat until all sets are empty
function getColoringSecondS(S::SparseMatrixCSC, coloring::Array, n::Int64)
	(fconn, cconn) = getConnections(S, coloring, n)

	maxi = 0
	max_node = 1

	# fconn holds all F-F connections that doesn't have a common C node
	# Make the free node with the maximal amount of such neighbours, a C node. Until no more exist
	while(true)
		(fconn, maxi, max_node) = clearConnections(S, fconn, cconn, n, 0, 1)
		if maxi == 0
			break
		end

		coloring[max_node] = 1
		for i in fconn[max_node]
			pop!(fconn[i],max_node)
			push!(cconn[i],max_node)
		end
		empty!(fconn[max_node])
	end

	return coloring
end

# Get all strong connections for every node, split into a coarse set and a free set.
# fconn[i] holds all free nodes strongly connected to i
# cconn[i] holds all coarse nodes strongly connected to i
function getConnections(S::SparseMatrixCSC, coloring::Array, n::Int64)
	fconn = [Set{Int}() for i=1:n]
	cconn = [Set{Int}() for i=1:n]
	# Populate fconn with all F-F connections, and cconn with all C-F connections
	for i=1:n

		# Skip over coarse nodes
		if coloring[i] == 1
			continue
		end

		for j in nzrange(S, i)
			if i == S.rowval[j]
				continue
			end

			# coarse neighbour
			if coloring[S.rowval[j]] == 1
				push!(cconn[i],S.rowval[j])
				continue

			# free neighbour
			else
				push!(fconn[i],S.rowval[j])
			end

		end
	end
	fconn, cconn
end

# Remove all free nodes strongly connected, such that they have a common coarse node.
# fconn will be left with all F-F connections without a common node in cconn
function clearConnections(S::SparseMatrixCSC, fconn::Array{Set{Int64},1}, cconn::Array{Set{Int64},1}, n::Int64, maxi::Int64, max_node::Int64)
	for i=1:n
		for j in fconn[i]
			if i == j
				continue
			end
			for k in cconn[j]
				# Has a common c node, remove F-F connection
				if k in cconn[i]
					pop!(fconn[i],j)
					pop!(fconn[j],i)
					break
				end
			end
		end
		if length(fconn[i]) > maxi
			max_node = i
			maxi = length(fconn[i])
		end
	end
	return fconn, maxi, max_node
end


text:
@testset "134.gas-station.jl" begin
    @test can_complete_circuit([2, 3, 4], [3, 4, 3]) == -1
    @test can_complete_circuit([1, 2, 3, 4, 5], [3, 4, 5, 1, 2]) == 3
end


text:
using GeometricAlgebra

@basis "++𝟎"

a = 1.0v1 + 1.0v2 + 1.0v3
b = 0.0v1 + 0.0v2 + 1.0v3
c = 0.5v1 + 0.5v2 + 1.0v3

l1 = a ∧ b
l2 = a ∧ c

magnitude2(a)


text:
export platform_key, platform_dlext, valid_dl_path, arch, wordsize, triplet,
       Platform, UnknownPlatform, Linux, MacOS, Windows, FreeBSD
import Base: show

abstract type Platform end

struct UnknownPlatform <: Platform
end

struct Linux <: Platform
    arch::Symbol
    libc::Symbol
    abi::Symbol

    function Linux(arch::Symbol, libc::Symbol=:glibc,
                                 abi::Symbol=:default_abi)
        if !in(arch, [:i686, :x86_64, :aarch64, :powerpc64le, :armv7l])
            throw(ArgumentError("Unsupported architecture '$arch' for Linux"))
        end

        # The default libc on Linux is glibc
        if libc === :blank_libc
            libc = :glibc
        end

        if !in(libc, [:glibc, :musl])
            throw(ArgumentError("Unsupported libc '$libc' for Linux"))
        end

        # The default abi on Linux is blank, so map over to that by default,
        # except on armv7l, where we map it over to :eabihf
        if abi === :default_abi
            if arch != :armv7l
                abi = :blank_abi
            else
                abi = :eabihf
            end
        end

        if !in(abi, [:eabihf, :blank_abi])
            throw(ArgumentError("Unsupported abi '$abi' for Linux"))
        end

        # If we're constructing for armv7l, we MUST have the eabihf abi
        if arch == :armv7l && abi != :eabihf
            throw(ArgumentError("armv7l Linux must use eabihf, not '$abi'"))
        end
        # ...and vice-versa
        if arch != :armv7l && abi == :eabihf
            throw(ArgumentError("eabihf Linux is only on armv7l, not '$arch'!"))
        end

        return new(arch, libc, abi)
    end
end

struct MacOS <: Platform
    arch::Symbol
    libc::Symbol
    abi::Symbol

    # Provide defaults for everything because there's really only one MacOS
    # target right now.  Maybe someday iOS.  :fingers_crossed:
    function MacOS(arch::Symbol=:x86_64, libc::Symbol=:blank_libc,
                                         abi=:blank_abi)
        if arch !== :x86_64
            throw(ArgumentError("Unsupported architecture '$arch' for macOS"))
        end
        if libc !== :blank_libc
            throw(ArgumentError("Unsupported libc '$libc' for macOS"))
        end
        if abi !== :blank_abi
            throw(ArgumentError("Unsupported abi '$abi' for macOS"))
        end
        return new(arch, libc, abi)
    end
end

struct Windows <: Platform
    arch::Symbol
    libc::Symbol
    abi::Symbol

    function Windows(arch::Symbol, libc::Symbol=:blank_libc,
                                   abi::Symbol=:blank_abi)
        if !in(arch, [:i686, :x86_64])
            throw(ArgumentError("Unsupported architecture '$arch' for Windows"))
        end
        # We only support the one libc/abi on Windows, so no need to play
        # around with "default" values.
        if libc !== :blank_libc
            throw(ArgumentError("Unsupported libc '$libc' for Windows"))
        end
        if abi !== :blank_abi
            throw(ArgumentError("Unsupported abi '$abi' for Windows"))
        end
        return new(arch, libc, abi)
    end
end

struct FreeBSD <: Platform
    arch::Symbol
    libc::Symbol
    abi::Symbol

    function FreeBSD(arch::Symbol, libc::Symbol=:blank_libc,
                                   abi::Symbol=:default_abi)
        # `uname` on FreeBSD reports its architecture as amd64 and i386 instead of x86_64
        # and i686, respectively. In the off chance that Julia hasn't done the mapping for
        # us, we'll do it here just in case.
        if arch === :amd64
            arch = :x86_64
        elseif arch === :i386
            arch = :i686
        elseif !in(arch, [:i686, :x86_64, :aarch64, :powerpc64le, :armv7l])
            throw(ArgumentError("Unsupported architecture '$arch' for FreeBSD"))
        end

        # The only libc we support on FreeBSD is the blank libc, which corresponds to
        # FreeBSD's default libc
        if libc !== :blank_libc
            throw(ArgumentError("Unsupported libc '$libc' for FreeBSD"))
        end

        # The default abi on FreeBSD is blank, execpt on armv7l
        if abi === :default_abi
            if arch != :armv7l
                abi = :blank_abi
            else
                abi = :eabihf
            end
        end

        if !in(abi, [:eabihf, :blank_abi])
            throw(ArgumentError("Unsupported abi '$abi' for FreeBSD"))
        end

        # If we're constructing for armv7l, we MUST have the eabihf abi
        if arch == :armv7l && abi != :eabihf
            throw(ArgumentError("armv7l FreeBSD must use eabihf, no '$abi'"))
        end
        # ...and vice-versa
        if arch != :armv7l && abi == :eabihf
            throw(ArgumentError("eabihf FreeBSD is only on armv7l, not '$arch'!"))
        end

        return new(arch, libc, abi)
    end
end

"""
    platform_name(p::Platform)

Get the "platform name" of the given platform.  E.g. returns "Linux" for a
`Linux` object, or "Windows" for a `Windows` object.
"""
platform_name(p::Linux) = "Linux"
platform_name(p::MacOS) = "MacOS"
platform_name(p::Windows) = "Windows"
platform_name(p::FreeBSD) = "FreeBSD"
platforn_name(p::UnknownPlatform) = "UnknownPlatform"

"""
    arch(p::Platform)

Get the architecture for the given `Platform` object as a `Symbol`.

# Examples
```jldoctest
julia> arch(Linux(:aarch64))
:aarch64

julia> arch(MacOS())
:x86_64
```
"""
arch(p::Platform) = p.arch
arch(u::UnknownPlatform) = :unknown

"""
    libc(p::Platform)

Get the libc for the given `Platform` object as a `Symbol`.

# Examples
```jldoctest
julia> libc(Linux(:aarch64))
:glibc

julia> libc(FreeBSD(:x86_64))
:default_libc
```
"""
libc(p::Platform) = p.libc
libc(u::UnknownPlatform) = :unknown

"""
    abi(p::Platform)

Get the ABI for the given `Platform` object as a `Symbol`.

# Examples
```jldoctest
julia> abi(Linux(:x86_64))
:blank_abi

julia> abi(FreeBSD(:armv7l))
:eabihf
```
"""
abi(p::Platform) = p.abi
abi(u::UnknownPlatform) = :unknown

"""
    wordsize(platform)

Get the word size for the given `Platform` object.

# Examples
```jldoctest
julia> wordsize(Linux(:arm7vl))
32

julia> wordsize(MacOS())
64
```
"""
wordsize(p::Platform) = (arch(p) === :i686 || arch(p) === :armv7l) ? 32 : 64
wordsize(u::UnknownPlatform) = 0

"""
    triplet(platform)

Get the target triplet for the given `Platform` object as a `String`.

# Examples
```jldoctest
julia> triplet(MacOS())
"x86_64-apple-darwin14"

julia> triplet(Windows(:i686))
"i686-w64-mingw32"

julia> triplet(Linux(:armv7l))
"arm-linux-gnueabihf"
```
"""
triplet(w::Windows) = string(arch_str(w), "-w64-mingw32")
triplet(m::MacOS) = string(arch_str(m), "-apple-darwin14")
triplet(l::Linux) = string(arch_str(l), "-linux", libc_str(l), abi_str(l))
triplet(f::FreeBSD) = string(arch_str(f), "-unknown-freebsd11.1", libc_str(f), abi_str(f))
triplet(u::UnknownPlatform) = "unknown-unknown-unknown"

# Helper functions for Linux and FreeBSD libc/abi mishmashes
arch_str(p::Platform) = (arch(p) == :armv7l) ? "arm" : "$(arch(p))"
function libc_str(p::Platform)
    if libc(p) == :blank_libc
        return ""
    elseif libc(p) == :glibc
        return "-gnu"
    else
        return "-$(libc(p))"
    end
end
abi_str(p::Platform) = (abi(p) == :blank_abi) ? "" : "$(abi(p))"

# Override Compat definitions as well
Compat.Sys.isapple(p::Platform) = p isa MacOS
Compat.Sys.islinux(p::Platform) = p isa Linux
Compat.Sys.iswindows(p::Platform) = p isa Windows
Compat.Sys.isbsd(p::Platform) = (p isa FreeBSD) || (p isa MacOS)

"""
    platform_key(machine::AbstractString = Sys.MACHINE)

Returns the platform key for the current platform, or any other though the
the use of the `machine` parameter.
"""
function platform_key(machine::AbstractString = Sys.MACHINE)
    # We're going to build a mondo regex here to parse everything:
    arch_mapping = Dict(
        :x86_64 => "(x86_|amd)64",
        :i686 => "i\\d86",
        :aarch64 => "aarch64",
        :armv7l => "arm(v7l)?",
        :powerpc64le => "p(ower)?pc64le",
    )
    platform_mapping = Dict(
        :darwin => "-apple-darwin\\d*",
        :freebsd => "-(.*-)?freebsd[\\d\\.]*",
        :mingw32 => "-w64-mingw32",
        :linux => "-(.*-)?linux",
    )
    libc_mapping = Dict(
        :blank_libc => "",
        :glibc => "-gnu",
        :musl => "-musl",
    )
    abi_mapping = Dict(
        :blank_abi => "",
        :eabihf => "eabihf",
    )

    # Helper function to collapse dictionary of mappings down into a regex of
    # named capture groups joined by "|" operators
    c(mapping) = string("(",join(["(?<$k>$v)" for (k, v) in mapping], "|"), ")")

    triplet_regex = Regex(string(
        c(arch_mapping),
        c(platform_mapping),
        c(libc_mapping),
        c(abi_mapping),
    ))

    m = match(triplet_regex, machine)
    if m != nothing
        # Helper function to find the single named field within the giant regex
        # that is not `nothing` for each mapping we give it.
        get_field(m, mapping) = begin
            for k in keys(mapping)
                if m[k] != nothing
                   return k
                end
            end
        end

        # Extract the information we're interested in:
        arch = get_field(m, arch_mapping)
        platform = get_field(m, platform_mapping)
        libc = get_field(m, libc_mapping)
        abi = get_field(m, abi_mapping)

        # First, figure out what platform we're dealing with, then sub that off
        # to the appropriate constructor.  All constructors take in (arch, libc,
        # abi)  but they will throw errors on trouble, so we catch those and
        # return the value UnknownPlatform() here to be nicer to client code.
        try
            if platform == :darwin
                return MacOS(arch, libc, abi)
            elseif platform == :mingw32
                return Windows(arch, libc, abi)
            elseif platform == :freebsd
                return FreeBSD(arch, libc, abi)
            elseif platform == :linux
                return Linux(arch, libc, abi)
            end
        catch
        end
    end

    Compat.@warn("Platform `$(machine)` is not an officially supported platform")
    return UnknownPlatform()
end

"""
    platform_dlext(platform::Platform = platform_key())

Return the dynamic library extension for the given platform, defaulting to the
currently running platform.  E.g. returns "so" for a Linux-based platform,
"dll" for a Windows-based platform, etc...
"""
platform_dlext(l::Linux) = "so"
platform_dlext(f::FreeBSD) = "so"
platform_dlext(m::MacOS) = "dylib"
platform_dlext(w::Windows) = "dll"
platform_dlext(u::UnknownPlatform) = "unknown"
platform_dlext() = platform_dlext(platform_key())

"""
    valid_dl_path(path::AbstractString, platform::Platform)

Return `true` if the given `path` ends in a valid dynamic library filename.
E.g. returns `true` for a path like `"usr/lib/libfoo.so.3.5"`, but returns
`false` for a path like `"libbar.so.f.a"`.
"""
function valid_dl_path(path::AbstractString, platform::Platform)
    dlext_regexes = Dict(
        # On Linux, libraries look like `libnettle.so.6.3.0`
        "so" => r"^(.*).so(\.[\d]+){0,3}$",
        # On OSX, libraries look like `libnettle.6.3.dylib`
        "dylib" => r"^(.*).dylib$",
        # On Windows, libraries look like `libnettle-6.dylib`
        "dll" => r"^(.*).dll$"
    )

    # Given a platform, find the dlext regex that matches it
    dlregex = dlext_regexes[platform_dlext(platform)]

    # Return whether or not that regex matches the basename of the given path
    return occursin(dlregex, basename(path))
end

# Define show() for these objects for two reasons:
#  - I don't like the `BinaryProvider.` at the beginning of the types;
#    it's unnecessary as these are exported
#  - I don't like the :blank_* arguments, they're unnecessary
function show(io::IO, p::Platform)
    write(io, "$(platform_name(p))($(repr(arch(p)))")
    omit_libc = libc(p) == :blank_libc
    omit_abi = abi(p) == :blank_abi

    if !omit_libc || !omit_abi
        write(io, ", $(repr(libc(p)))")
    end
    if !omit_abi
        write(io, ", $(repr(abi(p)))")
    end
    write(io, ")")
end


text:
using Test
using MakieRipserer
using AbstractPlotting
using Ripserer
using Suppressor

@testset "ripserer" begin
    @suppress begin
        data = [Point3f0(rand(), rand(), rand()) for _ in 1:50]
        plt = ReductionPlot(data, Rips(data); debug=true)

        res_coh = ripserer(plt; dim_max=2)
        res_hom = ripserer(plt; dim_max=1, alg=:homology)
        res_inv = ripserer(plt; dim_max=2, alg=:involuted)
        res_nor = ripserer(data; dim_max=2)
        @test res_coh == res_nor
        @test res_hom == res_nor[1:2]
        @test res_inv == res_nor
    end
end


text:
using RiskAdjustedLinearizations, Test, JLD2
include(joinpath(dirname(@__FILE__), "..", "..", "examples", "wachter_disaster_risk", "wachter.jl"))

# Get stochastic steady state
sssout = JLD2.jldopen(joinpath(dirname(@__FILE__), "..", "reference", "iterative_sss_output.jld2"), "r")
z = vec(sssout["z"])
y = vec(sssout["y"])
Ψ = sssout["Psi"]

# Create model and update it
m = WachterDisasterRisk()
ral = inplace_wachter_disaster_risk(m)
update!(ral, z, y, Ψ)
@info "The following messages about Blanchard-Kahn conditions are expected."
@test RiskAdjustedLinearizations.blanchard_kahn(ral)
@test RiskAdjustedLinearizations.blanchard_kahn(ral; verbose = :low)
@test RiskAdjustedLinearizations.blanchard_kahn(ral; verbose = :none)

# Get deterministic steady state
detout = JLD2.jldopen(joinpath(dirname(@__FILE__), "..", "reference", "det_ss_output.jld2"), "r")
z = vec(detout["z"])
y = vec(detout["y"])

update!(ral, z, y, zeros(length(y), length(z)))
RiskAdjustedLinearizations.compute_Ψ(ral; zero_entropy_jacobian = true)
@test RiskAdjustedLinearizations.blanchard_kahn(ral; deterministic = true, verbose = :low)
@test RiskAdjustedLinearizations.blanchard_kahn(ral; deterministic = true, verbose = :high)

nothing


text:
import FourierFlows.KuramotoSivashinsky

function growingwavetest()
  nx, Lx = 256, 4π
  dt, nt = 1e-6, 100
  prob = KuramotoSivashinsky.Problem(nx=nx, Lx=Lx, dt=dt, stepper="FilteredETDRK4")
  x = prob.grid.x

  # Initial condition
  a = 1e-4
  u0 = @. a*cos(x/2)
  ua(x, t) = a*exp(3t/16)*cos(x/2) + a^2*2/3*(exp(3t/8)-1)*sin(x)
  KuramotoSivashinsky.set_u!(prob, u0)

  stepforward!(prob, nt)
  KuramotoSivashinsky.updatevars!(prob)
  u, t = prob.vars.u, prob.t

  arbitraryerror = 1e-14 # what is an appropriate error?
  L1(u) = prob.grid.dx*sum(abs.(u))/Lx

  L1(u-ua.(x, t))/L1(ua.(x, 0)) < arbitraryerror # tests relative error
end

@test growingwavetest()