--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/arrays.jl	Sat Nov 26 09:23:14 2022 +0100
@@ -0,0 +1,189 @@
+function _longest_increasing_subsequence(v::Vector{Int})::Vector{Int}
+    M = zeros(Int, length(v))
+    P = zeros(Int, length(v))
+    Longest = 0
+    for i = eachindex(v)
+        e = v[i]
+        # Find element in sequence so far that is smaller than current element e.
+        lo, hi = 1, Longest+1
+        while lo < hi
+            mid = round(Int, floor((lo+hi)/2))
+            if e < v[M[mid]]
+                hi = mid
+            else
+                lo = mid+1
+            end
+        end
+        @assert lo == hi
+        P[i] = lo > 1 ? M[lo-1] : -1
+        M[lo] = i
+
+        if lo > Longest
+            Longest = lo
+        end
+    end
+
+    @show P, M
+    # Reconstruct sequence
+    ixs = zeros(Int, 0)
+    i = M[Longest]
+    while i > 0
+        push!(ixs, v[i])
+        i = P[i]
+    end
+    reverse!(ixs)
+    ixs
+end
+
+function twosum1(a::Vector{Int}, n::Int)::Tuple{Int,Int}
+    # n² complexity (trivial):
+    for (i,e1) in enumerate(a)
+        for (j,e2) in enumerate(a)
+            if e1+e2 == n
+                return (i,j)
+            end
+        end
+    end
+    return (0,0)
+end
+
+function twosum2(a::Vector{Int}, n::Int)::Tuple{Int,Int}
+    # More clever?
+    #
+    # 1. sort array; cut off all elements > n. Start from largest leftover number
+    # and smallest one; look for a match:
+    a_ = sort(a)
+    maxix = 1
+    for (i, e) = enumerate(a_)
+        if e < n
+            maxix = i
+        else
+            break
+        end
+    end
+
+    a_ = a_[begin:maxix]
+    front, back = 1, length(a_)
+    while front < back
+        while a_[front]+a_[back] < n
+            front += 1
+        end
+        if a_[front]+a_[back] == n
+            return (front, back)
+        end
+        back -= 1
+    end
+    nothing
+end
+
+function watercontainer(a::Vector{Int})
+    maxvol = 0
+    best = (0,0)
+    for lo = 1:length(a)
+        for hi = length(a):-1:lo
+            vol = (hi-lo) * min(a[lo], a[hi])
+            if vol > maxvol
+                best = (lo, hi)
+                maxvol = vol
+            end
+        end
+    end
+    best, maxvol
+end
+
+function rainwater(a::Vector{Int})
+    lm, rm = 0, 0
+    leftmax, rightmax = zeros(Int, length(a)), zeros(Int, length(a))
+    for (i,e) in enumerate(a)
+        if e > lm
+            lm = e
+        end
+        leftmax[i] = lm
+    end
+    for (i,e) in enumerate(reverse(a))
+        if e > rm
+            rm = e
+        end
+        rightmax[length(rightmax)-(i-1)] = rm
+    end
+
+    water = 0
+    for (i, e) in enumerate(a)
+        water += min(leftmax[i], rightmax[i]) - e
+    end
+    wat
+end
+
+function longest_increasing_subsequence(v::Vector{Int})::Vector{Int}
+    M = zeros(Int, length(v)) # M[L] stores last index of sequence with length L.
+    P = zeros(Int, length(v)) # P[i] stores predecessor of element i in longest sequence.
+    Longest = 0
+    for i = eachindex(v)
+        # Binary search for position in longest-sequence-so-far
+        lo, hi = 1, Longest+1
+        while lo < hi
+            mid = round(Int, floor((lo+hi)/2))
+            if v[i] < v[M[mid]]
+                hi = mid
+            else
+                lo = mid+1
+            end
+        end
+        @assert lo == hi
+        # Update predecessor of current index.
+        P[i] = lo > 1 ? M[lo-1] : -1
+        M[lo] = i
+
+        if lo >= Longest
+            Longest = lo
+        end
+    end
+
+    # Reconstruct sequence.
+    seq = zeros(Int, Longest)
+    i = M[Longest]
+    for j = Longest:-1:1
+        seq[j] = v[i]
+        i = P[i]
+    end
+    seq
+end
+
+function longest_common_subsequence(x::Vector{T}, y::Vector{T})::Vector{T} where {T}
+    m, n = length(x), length(y)
+    C = zeros(Int, m+1, n+1)
+    # Not necessary:
+    for i = 1:m
+        C[i,1] = 0
+    end
+    for j = 1:n
+        C[1,j] = 0
+    end
+    for i = 1:m
+        for j = 1:n
+            if x[i] == y[j]
+                C[i+1,j+1] = C[i, j] + 1
+            else
+                C[i+1,j+1] = max(C[i, j+1], C[i+1, j])
+            end
+        end
+    end
+
+    # Reconstruct sequence
+    i, j = m, n
+    k = C[m+1, n+1]
+    seq = Vector{T}(undef, k)
+    while k > 0
+        if C[i,j] + 1 == C[i+1,j+1]
+            seq[k] = x[i]
+            k -= 1
+            i -= 1
+            j -= 1
+        elseif C[i,j+1] == C[i+1,j+1]
+            i -= 1
+        elseif C[i+1,j] == C[i+1,j+1]
+            j -= 1
+        end
+    end
+    seq
+end

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/cb.jl	Sat Nov 26 09:23:14 2022 +0100
@@ -0,0 +1,42 @@
+mutable struct CircularBuffer{T}
+    b::Vector{T}
+    first::Int
+    last::Int
+    count::Int
+
+    function CircularBuffer{T}(capacity::Integer) where {T}
+        new(Vector{T}(undef, capacity), 1, 0, 0)
+    end
+end
+
+function Base.push!(cb::CircularBuffer, item; overwrite::Bool=false)
+    if !overwrite || (overwrite && cb.count < length(cb.b))
+        if cb.count >= length(cb.b)
+            error("buffer is full")
+        end
+        cb.last = cb.last%length(cb.b) + 1
+        cb.b[cb.last] = item
+        cb.count += 1
+    else
+        cb.b[cb.first] = item
+        cb.first = cb.first%length(cb.b) + 1
+    end
+end
+
+function Base.popfirst!(cb::CircularBuffer)
+    if cb.count <= 0
+        error("buffer is empty")
+    end
+    e = cb.b[cb.first]
+    #cb.b[cb.first] = undef
+    cb.first = cb.first%length(cb.b) + 1
+    cb.count -= 1
+    e
+end
+
+function Base.empty!(cb::CircularBuffer)
+    cb.count = 0
+    cb.first = 1
+    cb.last = 0
+end
+

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/circus.jl	Sat Nov 26 09:23:14 2022 +0100
@@ -0,0 +1,23 @@
+function config1()::Vector{Tuple{Int,Int}}
+    [(65,100),
+    (70,180),
+    (56,94),
+    (75,190),
+    (60,95),
+    (68,110)]
+end
+
+function largest_tower(c::Vector{Tuple{Int,Int}})::Tuple{Int, Vector{Tuple{Int,Int}}}
+    sort!(c; lt=((h1,w1), (h2,w2)) -> !(h1 < h2 || (h1 == h2 && w1 < w2)))
+    n = 1
+    for i in 2:length(c)
+        h2, w2 = c[i]
+        h1, w1 = c[i-1]
+        if h1 > h2 && w1 > w2
+            n += 1
+        else
+            break
+        end
+    end
+    n, c
+end

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/coins.jl	Sat Nov 26 09:23:14 2022 +0100
@@ -0,0 +1,18 @@
+
+function best_selection(a::Vector{UInt})::Tuple{Int, Int, Int, Vector{UInt}}
+    N = length(a)
+    N_2 = div(N, 2)
+    left, right = 1, N_2
+    current_sum = sum(a[left:right])
+    min = current_sum
+    for i in 1:N_2
+        current_sum -= a[i]
+        current_sum += a[i+N_2]
+        if current_sum <= min
+            min = current_sum
+            left, right = i+1, i+N_2
+        end
+    end
+    (min, left, right, a[left:right])
+end
+

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/heap.jl	Sat Nov 26 09:23:14 2022 +0100
@@ -0,0 +1,51 @@
+
+function heap_parent(ix::Int)::Int
+    max(1, round(Int, floor(ix/2)))
+end
+
+function heap_children(ix::Int)::Tuple{Int,Int}
+    (2ix, 2ix+1)
+end
+
+function heap_bubble!(h::Vector{Int}, ix::Int)
+    if ix == 1
+        return
+    end
+    hp = heap_parent(ix)
+    if h[hp] > h[ix]
+        h[hp], h[ix] = h[ix], h[hp]
+    end
+    heap_bubble!(h, hp)
+end
+
+# Min-heap
+function heap_insert!(h::Vector{Int}, n::Int)
+    push!(h, n)
+    ix = length(h)
+    heap_bubble!(h, ix)
+end
+
+function heap_pull!(h::Vector{Int}, ix::Int)
+    l, r = heap_children(ix)
+    if l <= length(h) && r <= length(h)
+        if h[l] < h[r]
+            h[ix], h[l] = h[l], h[ix]
+            heap_pull!(h, l)
+        else
+            h[ix], h[r] = h[r], h[ix]
+            heap_pull!(h, r)
+        end
+    elseif l <= length(h)
+        @assert l == length(h)
+        h[ix], h[l] = h[l], h[ix]
+        popat!(h, length(h))
+    else
+        h[ix] = 10000
+    end
+end
+
+function heap_pop!(h::Vector{Int})::Int
+    e = h[1]
+    heap_pull!(h, 1)
+    e
+end

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/magicsquare.jl	Sat Nov 26 09:23:14 2022 +0100
@@ -0,0 +1,78 @@
+
+function testsquare1()::Matrix{Int}
+    [1 0 4 0;
+     0 2 0 3;
+     0 0 3 0;
+     0 0 0 4]
+end
+function testsquare2()::Matrix{Int}
+    [4 0 0 2;
+     0 3 0 0;
+     0 0 2 0;
+     3 0 0 1]
+end
+
+function neighbors_4x4(m::Matrix{Int}, i::Int, j::Int)::Vector{Int}
+    q, r = div(i-1, 2), div(j-1, 2)
+    s = union(Set(m[i,:]), Set(m[:,j]), Set([m[2q+1, 2r+1], m[2q+1, 2r+2], m[2q+2, 2r+1], m[2q+2, 2r+2]]))
+    pop!(s, 0)
+    collect(s)
+end
+
+function candidates_4x4(m::Matrix{Int}, i::Int, j::Int)::Vector{Int}
+    n = neighbors_4x4(m, i, j)
+    c = setdiff(1:4, n)
+    collect(c)
+end
+
+function solve_4x4(m::Matrix{Int})::Union{Some{Matrix{Int}}, Nothing}
+    @assert all(m .<= 4) && all(m .>= 0)
+
+    m = copy(m)
+    n = 1
+    d = Matrix{Union{Some{Vector{Int}}, Nothing}}(nothing, 4, 4)
+    # 1) Find candidates for all positions.
+    while n > 0
+        n = 0
+        for i = 1:4
+            for j = 1:4
+                if m[i,j] == 0
+                    d[i,j] = Some(candidates_4x4(m, i, j))
+                end
+            end
+        end
+        # 2) Fix those cells where only one candidate matches
+        for i = 1:4
+            for j = 1:4
+                if m[i,j] == 0 && length(something(d[i,j])) == 1
+                    n += 1
+                    m[i,j] = something(d[i,j])[1]
+                    d[i,j] = nothing
+                elseif m[i,j] == 0 && length(something(d[i,j])) == 0
+                    display(m)
+                    error("Unsolveable magic square! at $((i,j))")
+                end
+            end
+        end
+    end
+   
+    if all(m .> 0)
+        return Some(m)
+    end
+    # 3) Backtracking step: Select candidate, try to solve.
+    for i = 1:4
+        for j = 1:4
+            if !isnothing(d[i,j])
+                for cand in something(d[i,j])
+                    m[i,j] = cand
+                    m_ = solve_4x4(m)
+                    if !isnothing(m_)
+                        return m_
+                    end
+                end
+                return nothing
+            end
+        end
+    end
+end
+

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/matrixsearch.jl	Sat Nov 26 09:23:14 2022 +0100
@@ -0,0 +1,53 @@
+
+function generate_sorted_matrix(m, n)::Matrix{Int}
+    v = abs.(rand(Int, m*n)) .% 1000
+    sort!(v)
+    reshape(v, m, n)
+end
+
+const Option{T} = Union{Some{T}, Nothing}
+
+function find_in_sorted_array(V::AbstractVector{Int}, n::Int)::Option{Int}
+    lo, mid, hi = 1, round(Int, length(V)/2), length(V)
+    while lo < hi
+        if n < V[mid]
+            hi = mid-1
+            mid = round(Int, (lo+hi)/2)
+            continue
+        elseif n > V[mid]
+            lo = mid+1
+            mid = round(Int, (lo+hi)/2)
+            continue
+        elseif n == V[mid]
+            return Some(mid)
+        end
+        @assert false "if exhausted"
+    end
+    V[mid] == n ? Some(mid) : nothing
+end
+
+function find_in_sorted_matrix(M::Matrix, n::Int)::Option{Tuple{Int, Int}}
+    r, c = size(M)
+    # 1. Find column
+    lo, mid, hi = 1, round(Int, c/2), c
+    while lo < hi
+        if n < M[begin, mid]
+            hi = mid-1
+            mid = round(Int, (lo+hi)/2)
+            continue
+        elseif n > M[end, mid]
+            lo = mid+1
+            mid = round(Int, (lo+hi)/2)
+            continue
+        else
+            break
+        end
+    end
+    # 2. Find element
+    in_array = find_in_sorted_array((@view M[:,mid]), n)
+    if isnothing(in_array)
+        nothing
+    else
+        Some((mid, something(in_array)))
+    end
+end

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/quicksort.jl	Sat Nov 26 09:23:14 2022 +0100
@@ -0,0 +1,43 @@
+
+function partition(v::Vector{T}, from::Int, to::Int)::Int where {T}
+    if to-from < 1
+        return from
+    end
+    lo, hi = from-1, to+1
+    mid = round(Int, (lo+hi)/2)
+    piv = v[mid]
+    while lo < hi
+        lo += 1
+        while v[lo] < piv
+            lo += 1
+        end
+        hi -= 1
+        while v[hi] > piv
+            hi -= 1
+        end
+        if lo >= hi
+            return hi
+        end
+        v[lo], v[hi] = v[hi], v[lo]
+    end
+    lo
+end
+
+function quicksort!(v::Vector{T}, from=1, to=-1) where {T}
+    if to < 0
+        to = length(v)
+    end
+    if to-from == 1
+        return
+    else
+        mid = partition(v, from, to)
+        @show (from, to, mid)
+        if from < mid
+            quicksort!(v, from, mid)
+        end
+        if mid+1 < to
+            quicksort!(v, mid+1, to)
+        end
+    end
+end
+

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/recursion.jl	Sat Nov 26 09:23:14 2022 +0100
@@ -0,0 +1,9 @@
+
+function combinations(n::Int, k::Int)::Vector
+    if k == 1
+        return collect(1:n)
+    end
+    lower = combinations(n, k-1)
+    [(i, l...) for i in 1:n for l in lower]
+end
+

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/strings.jl	Sat Nov 26 09:23:14 2022 +0100
@@ -0,0 +1,39 @@
+
+# "(())()" -> good;
+# "(()" -> bad
+function goodparens(s::String)::Bool
+    nesting = 0
+    for c in s
+        if c == '('
+            nesting += 1
+        elseif c == ')'
+            nesting -= 1
+        end
+        if nesting < 0
+            return false
+        end
+    end
+    if nesting != 0
+        false
+    else
+        true
+    end
+end
+
+# "[()]{}" -> good; "[(])" -> bad
+function goodmultiparens(s::String)::Bool
+    stack::Vector{Char} = []
+    for c in s
+        if c in ['(', '[', '{']
+            push!(stack, c)
+        elseif c in [')', ']', '}']
+            o = pop!(stack);
+            if (c == ')' && o == '(') || (c==']' && o == '[') || (c=='}' && o == '{')
+                continue
+            else
+                return false
+            end
+        end
+    end
+    length(stack) == 0
+end