Maximum Nesting Depth + Julia

[mcabbott]

I came across this page https://github.com/codereport/array-language-comparisons/blob/main/comparisons/leetcode/P1614_Max_Paren_Depth.md

For Julia, I'm not too sure what "no row-wise minus reduction" means, but it sounds like you are looking for maximum(cumsum(..., something like this:

julia> str = "(1)+((2))+(((3)))";

julia> maximum(cumsum([(c=='(')-(c==')') for c in str]))
3

julia> maximum(Iterators.accumulate(+, (c=='(')-(c==')') for c in str))  # lazy version
3

julia> foldl(str; init=(0,0)) do (i,maxi), c
         c=='(' && return i+1, max(i+1,maxi)
         c==')' && return i-1, maxi
         i, maxi
       end[2]
3

[codereport]

@mcabbott Similar to the other solutions, I am trying to do an outer_product in Julia via broadcasting, something like:

matrix = reshape(collect("()"), (1, :)) .== collect("(1+(2*3)+((8)/4))+1")
19×2 BitMatrix:
 1  0
 0  0
 0  0
 1  0
 0  0
 0  0
 0  0
 0  1
 0  0
 1  0
 1  0
 0  0
 0  1
 0  0
 0  0
 0  1
 0  1
 0  0
 0  0

and then a row-wise minus reduce or minus leftFold. However, that doesn't work in Julia:

julia> reduce(-, matrix, dims=1)
ERROR: MethodError: no method matching reducedim_init(::typeof(identity), ::typeof(-), ::BitMatrix, ::Int64)
Closest candidates are:
  reducedim_init(::Any, ::typeof(min), ::AbstractArray, ::Any) at reducedim.jl:128
  reducedim_init(::Any, ::typeof(max), ::AbstractArray, ::Any) at reducedim.jl:128
  reducedim_init(::Any, ::typeof(&), ::Union{Base.AbstractBroadcasted, AbstractArray}, ::Any) at reducedim.jl:206
  ...
Stacktrace:
 [1] _mapreduce_dim(f::Function, op::Function, #unused#::Base._InitialValue, A::BitMatrix, dims::Int64)
   @ Base ./reducedim.jl:371
 [2] #mapreduce#765
   @ ./reducedim.jl:357 [inlined]
 [3] #reduce#767
   @ ./reducedim.jl:406 [inlined]
 [4] top-level scope
   @ REPL[72]:1

[mcabbott]

I believe the error is trying to say that it doesn't know the neutral element for reducing over -, which it would infer for +. You could provide this but (1) the reduction order isn't guaranteed and (2) I think this is the wrong thing:

julia> reduce(-, matrix, dims=1, init=0)
1×2 Matrix{Int64}:
 -4  -4

This is closer:

julia> reduce(-, matrix, dims=2, init=0)
19×1 Matrix{Int64}:
 -1
  0
  0
 -1
  0
  0
  0
 -1
  0
 -1
 -1
  0
 -1
  0
  0
 -1
 -1
  0
  0

but that always uses init, whereas you want to subtract the second column from the first. It's a little strange now that I think about it that the dims method forbids this.

julia> reduce(-, [1, 0])
1

julia> reduce(-, [1, 0], init=0)
-1

The first is probably ill-defined due to relying on the order. It should be foldl but that doesn't take dims. You can do mapslices(row -> foldl(-, row), matrix, dims=2), or else foldl.(-, eachrow(matrix)).

You could also literally subtract the whole columns, -(eachcol(matrix)...) |> cumsum |> maximum.

[codereport]

Yea, I found foldl when trying to solve this problem which is what I wanted but that doesn't take a dims argument. Is there some reason for that?

[mcabbott]

I think foldl sort-of belongs to the iteration protocol? While accumulate was only for arrays until fairly recently. It is a bit weird, now that you point it out.

Easy to define versions (of sub-optimal efficiency):

fold1(f, x::AbstractArray; dims, kw...) = mapslices(y -> foldl(f, y; kw...), x; dims);
fold2(f, x::AbstractArray; dims, kw...) = accumulate(f, x; dims, kw...)[_last(x, dims)...];

_last(x, dims) = ntuple(d -> d in dims ? (lastindex(x,d):lastindex(x,d)) : (:), ndims(x))

fold1(-, ones(Int, 2,2), dims=1)
fold2(-, ones(Int, 2,2), dims=1)  # both [0 0]

fold1(-, ones(Int, 2,2), dims=1, init=0)  # instead [-2 -2]