Mercurial > lbo > hg > juliaplay
changeset 3:c1db337c15be
Reorganize files
| author | Lewin Bormann <lbo@spheniscida.de> |
|---|---|
| date | Tue, 14 Feb 2023 21:12:06 +0100 |
| parents | b7160d5e22cc |
| children | 00f57653128a |
| files | arrays.jl cb.jl circus.jl coins.jl heap.jl julia/arrays.jl julia/cb.jl julia/circus.jl julia/coins.jl julia/heap.jl julia/longest_common_subsequence.jl julia/longest_increasing_subsequence.jl julia/magicsquare.jl julia/matrixsearch.jl julia/mergesort.jl julia/quicksort.jl julia/recursion.jl julia/strings.jl longest_common_subsequence.jl longest_increasing_subsequence.jl magicsquare.jl matrixsearch.jl mergesort.jl python/sorting.py quicksort.jl recursion.jl strings.jl |
| diffstat | 27 files changed, 773 insertions(+), 671 deletions(-) [+] |
line wrap: on
line diff
--- a/arrays.jl Sun Feb 12 21:06:13 2023 +0100 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,189 +0,0 @@ -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
--- a/cb.jl Sun Feb 12 21:06:13 2023 +0100 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,42 +0,0 @@ -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 -
--- a/circus.jl Sun Feb 12 21:06:13 2023 +0100 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,23 +0,0 @@ -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
--- a/coins.jl Sun Feb 12 21:06:13 2023 +0100 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,18 +0,0 @@ - -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 -
--- a/heap.jl Sun Feb 12 21:06:13 2023 +0100 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,51 +0,0 @@ - -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/julia/arrays.jl Tue Feb 14 21:12:06 2023 +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/julia/cb.jl Tue Feb 14 21:12:06 2023 +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/julia/circus.jl Tue Feb 14 21:12:06 2023 +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/julia/coins.jl Tue Feb 14 21:12:06 2023 +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/julia/heap.jl Tue Feb 14 21:12:06 2023 +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/julia/longest_common_subsequence.jl Tue Feb 14 21:12:06 2023 +0100 @@ -0,0 +1,38 @@ +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/julia/longest_increasing_subsequence.jl Tue Feb 14 21:12:06 2023 +0100 @@ -0,0 +1,34 @@ +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
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/julia/magicsquare.jl Tue Feb 14 21:12:06 2023 +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/julia/matrixsearch.jl Tue Feb 14 21:12:06 2023 +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/julia/mergesort.jl Tue Feb 14 21:12:06 2023 +0100 @@ -0,0 +1,46 @@ + +function merge!(a::AbstractArray, mid::Int, aux::Union{AbstractArray, Nothing}=nothing) + if length(a) <= 1 + return + end + # Left half: begin:mid + # Right half: mid+1:end + left, right, i = 1, mid+1, 1 + ac = isnothing(aux) ? copy(a) : aux + while i <= length(a) + if left > mid + ac[i] = a[right] + right += 1 + elseif right > length(a) + ac[i] = a[left] + left += 1 + else + if a[left] < a[right] + ac[i] = a[left] + left += 1 + else + ac[i] = a[right] + right += 1 + end + end + i += 1 + end + for i = eachindex(a) + a[i] = ac[i] + end +end + +function mergesort!(a::AbstractArray) + aux = copy(a) + if length(a) <= 1 + return + elseif length(a) == 2 + a[1], a[2] = (a[1] < a[2] ? (a[1],a[2]) : (a[2],a[1])) + return + else + mid = div(1+length(a), 2) + mergesort!(@view a[begin:mid]) + mergesort!(@view a[mid+1:end]) + merge!(a, mid, aux) + end +end
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/julia/quicksort.jl Tue Feb 14 21:12:06 2023 +0100 @@ -0,0 +1,49 @@ +function partition(v::Vector{T}, from::Int, to::Int)::Int where {T} + piv = v[to] + i = from-1 + for j = from:to-1 + if v[j] <= piv + i += 1 + v[i], v[j] = v[j], v[i] + end + end + i += 1 + v[i], v[to] = v[to], v[i] + i +end + +function hoare!(v::AbstractArray, from::Int, to::Int)::Int + if from >= to + return from + end + lo, hi = from-1, to+1 + piv = v[div(from+to,2)] + while true + 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 +end + +function quicksort!(v::Vector{T}, from=1, to=-1) where {T} + if to < 0 + to = length(v) + end + if to <= from + return + else + mid = hoare!(v, from, to) + quicksort!(v, from, mid) + quicksort!(v, mid+1, to) + end +end +
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/julia/recursion.jl Tue Feb 14 21:12:06 2023 +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/julia/strings.jl Tue Feb 14 21:12:06 2023 +0100 @@ -0,0 +1,41 @@ + +# "(())()" -> 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 + +
--- a/longest_common_subsequence.jl Sun Feb 12 21:06:13 2023 +0100 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,38 +0,0 @@ -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
--- a/longest_increasing_subsequence.jl Sun Feb 12 21:06:13 2023 +0100 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,34 +0,0 @@ -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
--- a/magicsquare.jl Sun Feb 12 21:06:13 2023 +0100 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,78 +0,0 @@ - -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 -
--- a/matrixsearch.jl Sun Feb 12 21:06:13 2023 +0100 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,53 +0,0 @@ - -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
--- a/mergesort.jl Sun Feb 12 21:06:13 2023 +0100 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,46 +0,0 @@ - -function merge!(a::AbstractArray, mid::Int, aux::Union{AbstractArray, Nothing}=nothing) - if length(a) <= 1 - return - end - # Left half: begin:mid - # Right half: mid+1:end - left, right, i = 1, mid+1, 1 - ac = isnothing(aux) ? copy(a) : aux - while i <= length(a) - if left > mid - ac[i] = a[right] - right += 1 - elseif right > length(a) - ac[i] = a[left] - left += 1 - else - if a[left] < a[right] - ac[i] = a[left] - left += 1 - else - ac[i] = a[right] - right += 1 - end - end - i += 1 - end - for i = eachindex(a) - a[i] = ac[i] - end -end - -function mergesort!(a::AbstractArray) - aux = copy(a) - if length(a) <= 1 - return - elseif length(a) == 2 - a[1], a[2] = (a[1] < a[2] ? (a[1],a[2]) : (a[2],a[1])) - return - else - mid = div(1+length(a), 2) - mergesort!(@view a[begin:mid]) - mergesort!(@view a[mid+1:end]) - merge!(a, mid, aux) - end -end
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/python/sorting.py Tue Feb 14 21:12:06 2023 +0100 @@ -0,0 +1,102 @@ +import copy + +def partition(a, fro, to): + if fro >= to: + return fro + # Hoare partitioning scheme + mid = (fro+to) // 2 + piv = a[mid] + lo, hi = fro-1, to+1 + while True: + lo += 1 + while a[lo] < piv: + lo += 1 + hi -= 1 + while a[hi] > piv: + hi -= 1 + if lo >= hi: + return hi + a[lo], a[hi] = a[hi], a[lo] + +def quicksort(a, fro=0, to=-1): + if to < 0: + to = len(a) - 1 + if to-fro <= 0: + return + mid = partition(a, fro, to) + quicksort(a, fro, mid) + quicksort(a, mid+1, to) + +def mergehalves(a, lo, mid, hi, aux): + i, l, r = 0, lo, mid + while i <= hi-lo: + if l >= mid: + aux[i] = a[r] + r += 1 + elif r > hi: + aux[i] = a[l] + l += 1 + else: + if a[l] < a[r]: + aux[i] = a[l] + l += 1 + else: + aux[i] = a[r] + r += 1 + i += 1 + print(a[lo:hi+1], aux[0:i]) + a[lo:hi+1] = aux[0:i] + +def mergesort(a, lo=0, hi=-1, aux=None): + aux = aux or copy.copy(a) + hi = hi if hi > 0 else len(a)-1 + if hi == lo: + return + elif hi-lo == 1: + if a[lo] > a[hi]: + a[lo], a[hi] = a[hi], a[lo] + return + else: + mid = (lo+hi)//2 + mergesort(a, lo, mid, aux) + mergesort(a, mid, hi, aux) + mergehalves(a, lo, mid, hi, aux) + +def children(i): + return (2*i, 2*i+1) + +def swap(a, i, j): + a[i], a[j] = a[j], a[i] + + +def sink(a, i, N=-1): + N = N if N >= 0 else len(a) + while 2*i < N: + c1, c2 = children(i) + if c2 >= N: + if a[i] < a[c1]: + swap(a, i, c1) + i = c1 + else: + sm, la = (c1, c2) if a[c1] < a[c2] else (c2, c1) + if a[i] < a[la]: + swap(a, i, la) + i = la + +def buildheap(a): + i = len(a) // 2 + while i > 0: + sink(a, i) + i -= 1 + +def heapsort(a): + a = [0] + a + buildheap(a) + i = len(a)-1 + while i > 0: + swap(a, 1, i) + i -= 1 + sink(a, 1, i) + + return a +
--- a/quicksort.jl Sun Feb 12 21:06:13 2023 +0100 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,49 +0,0 @@ -function partition(v::Vector{T}, from::Int, to::Int)::Int where {T} - piv = v[to] - i = from-1 - for j = from:to-1 - if v[j] <= piv - i += 1 - v[i], v[j] = v[j], v[i] - end - end - i += 1 - v[i], v[to] = v[to], v[i] - i -end - -function hoare!(v::AbstractArray, from::Int, to::Int)::Int - if from >= to - return from - end - lo, hi = from-1, to+1 - piv = v[div(from+to,2)] - while true - 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 -end - -function quicksort!(v::Vector{T}, from=1, to=-1) where {T} - if to < 0 - to = length(v) - end - if to <= from - return - else - mid = hoare!(v, from, to) - quicksort!(v, from, mid) - quicksort!(v, mid+1, to) - end -end -
--- a/recursion.jl Sun Feb 12 21:06:13 2023 +0100 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,9 +0,0 @@ - -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 -
--- a/strings.jl Sun Feb 12 21:06:13 2023 +0100 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,41 +0,0 @@ - -# "(())()" -> 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 - -