# Sunday Small challenge

**URL:** <https://discourse.julialang.org/t/sunday-small-challenge/85041>\
**Category:** General Usage\
**Tags:** performance\
**Created:** [July 30, 2022, 11:01pm UTC](https://discourse.julialang.org/t/sunday-small-challenge/85041 "2022-07-30T23:01:23Z")\
**Posts on this page:** 11\
**Page:** 1

<div class="post-metadata">

**Author:** ![miguelraz](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/miguelraz/32/631_2.png) [@miguelraz](https://discourse.julialang.org/u/miguelraz)\
**Post date:** [July 30, 2022, 11:01pm UTC](https://discourse.julialang.org/t/sunday-small-challenge/85041/1 "2022-07-30T23:01:23Z")

</div>

Hello Julians!  
Welcome to the first Sunday Small challenge.  
I will post 3 lil’ problems - whoever can solve them in Julia (in serial, all architectures allowed) on the input(s) repeated 1000x wins all the internet points. Each problem is it’s own category.  
Challenge ends next Sunday.

1. Remove HTML Tags

```julia
# Input - assume the string is ASCII
str = Vector{UInt8}("<div>Hello <b>JuliaCon2022!</b></div>")
# Output satisfies 
unhtml(str) == Vector{UInt8}("Hello JuliaCon2022!")

```

1. Hamming distance - count the number of corresponding unequal elements in 2 ordered collections of equal size.

```julia
# input - assume ASCII
s1 = "AAABBB"; s2 = "AAACCC";
# output
hamming(s1, s2) == 3

```

1. Max Parenthesis depth - count the deepest level of nesting for parenthesis.

```julia
# Input, assume ASCII
str = "(()()(((((())))()()()(((()))()()())))))()()"
# Output
depth(str) == 7

```

---

<div class="post-metadata">

**Author:** ![camilogarciabotero](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/camilogarciabotero/32/35000_2.png) [@camilogarciabotero](https://discourse.julialang.org/u/camilogarciabotero)\
**Post date:** [July 30, 2022, 11:23pm UTC](https://discourse.julialang.org/t/sunday-small-challenge/85041/2 "2022-07-30T23:23:53Z")

</div>

Hey @miguelraz

I got a solution for number 2:

```julia
function hamming(x,y)
    @assert length(x) == length(y)
    hd = 0
    for i in 1:length(x)
        if x[i] != y[i]
            hd += 1
        end
    end
    return hd
end

```

---

<div class="post-metadata">

**Author:** ![Elrod](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/elrod/32/22461_2.png) [@Elrod](https://discourse.julialang.org/u/Elrod)\
**Post date:** [July 31, 2022, 12:06am UTC](https://discourse.julialang.org/t/sunday-small-challenge/85041/3 "2022-07-31T00:06:10Z")

</div>

Here is a SIMD implementation taking advantage of AVX512.  
Note! That means it requires AVX512 to be fast. It’ll probably be pretty slow otherwise.

It’s also probably suboptimal, but good enough for now

```julia
julia> cppstr = "<div>Hello <b>CppNorth!</b></div>";

julia> cppstrlong = cppstr^10;

julia> v = UInt8[];

julia> vunhtml!(v, cppstr);

julia> Base.unsafe_string(pointer(v), length(v))
"Hello CppNorth!"

julia> vunhtml!(v, cppstrlong);

julia> Base.unsafe_string(pointer(v), length(v))
"Hello CppNorth!Hello CppNorth!Hello CppNorth!Hello CppNorth!Hello CppNorth!Hello CppNorth!Hello CppNorth!Hello CppNorth!Hello CppNorth!Hello CppNorth!"

julia> @benchmark vunhtml!($v, $cppstr)
BenchmarkTools.Trial: 10000 samples with 996 evaluations.
 Range (min … max): 25.315 ns … 1.095 μs ┊ GC (min … max): 0.00% … 0.00%
 Time (median): 26.340 ns ┊ GC (median): 0.00%
 Time (mean ± σ): 27.295 ns ± 11.404 ns ┊ GC (mean ± σ): 0.00% ± 0.00%

  ▅██▇▅▂▁▁ ▂
  ██████████▇▇▇▇▅▅▆▆▄▄▅▅▅▅▅▅▄▅▅▄▅▅▅▄▅▄▅▄▂▃▃▄▄▄▄▄▅▅▅▆▆▆▇▇▇▆▆▆▇ █
  25.3 ns Histogram: log(frequency) by time 48.2 ns <

 Memory estimate: 0 bytes, allocs estimate: 0.

julia> @benchmark vunhtml!($v, $cppstrlong)
BenchmarkTools.Trial: 10000 samples with 955 evaluations.
 Range (min … max): 88.157 ns … 175.039 ns ┊ GC (min … max): 0.00% … 0.00%
 Time (median): 91.343 ns ┊ GC (median): 0.00%
 Time (mean ± σ): 93.188 ns ± 6.414 ns ┊ GC (mean ± σ): 0.00% ± 0.00%

  ▅ ▆█ ▂▂ ▁▂▁▁ ▁
  █▆▅█▆████████████▇█▇▇▇▇▇▆▆▅▆▆▆▆▅▅▆▆▆▅▅▅▅▄▆▆▅▅▅▆▅▇▇▇▇▆▆▇▇▇▇▇▆ █
  88.2 ns Histogram: log(frequency) by time 119 ns <

 Memory estimate: 0 bytes, allocs estimate: 0.

```

Implementation:

```julia
using VectorizationBase

function vunhtml!(output::Vector{UInt8}, input::AbstractVector{UInt8})
  N = length(input)
  resize!(output, N)
  n = 0
  W = VectorizationBase.pick_vector_width(UInt8)
  GC.@preserve output input begin
    pinput = VectorizationBase.zstridedpointer(input)
    pout = pointer(output)
    i = 0
    while i < N
      m = VectorizationBase.mask(W, i, N)
      md = VectorizationBase.data(m)
      # @show i md
      v = vload(pinput, (MM{Int(W)}(i),), m)
      ml = v == UInt8('<')
      mu = v == UInt8('>')
      muu = VectorizationBase.data(mu)
      mlu = VectorizationBase.data(ml)
      i += 64
      m2 = VectorizationBase.Mask(m)
      if mlu > muu
        lz = leading_zeros(mlu)
        truncflag = (one(UInt) << (8sizeof(UInt) - 1 - lz))
        mlu -= truncflag
        m2 &= VectorizationBase.Mask{Int(W)}((truncflag-one(truncflag)))
        i -= 1 + lz
      end
      cmu = ~((muu - mlu) + muu)
      cm = VectorizationBase.Mask{Int(W)}(cmu) & m2
      cmd = VectorizationBase.data(cm)
      # @show muu mlu cmu 
      VectorizationBase.compressstore!(pout + n, v, cm)
      n += count_ones(cm)
    end
  end
  resize!(output, n)
  output
end
vunhtml!(output, input::String) = vunhtml!(output, codeunits(input))

```

---

<div class="post-metadata">

**Author:** ![Jollywatt](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jollywatt/32/202198_2.png) [@Jollywatt](https://discourse.julialang.org/u/Jollywatt)\
**Post date:** [July 31, 2022, 12:14am UTC](https://discourse.julialang.org/t/sunday-small-challenge/85041/4 "2022-07-31T00:14:23Z")

</div>

For lovers of succinctness:

```julia
unhtml(str) = replace(String(str), r"</?\w+>" => "")

depth(str) = cumsum(get(Dict('(' => +1, ')' => -1), c, 0)
                    for c in str) |> maximum

hamming(s1, s2) = sum(collect(s1) .!= collect(s2))

```

---

<div class="post-metadata">

**Author:** ![Syx\_Pek](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/syx_pek/32/6364_2.png) [@Syx\_Pek](https://discourse.julialang.org/u/Syx_Pek)\
**Post date:** [August 1, 2022, 7:47am UTC](https://discourse.julialang.org/t/sunday-small-challenge/85041/5 "2022-08-01T07:47:16Z")

</div>

Here’s a similar one for depth.

`depth(str) = cumsum(2('(' - c) + 1 for c in str) |> maximum`

---

<div class="post-metadata">

**Author:** ![Eben60](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/eben60/32/13475_2.png) [@Eben60](https://discourse.julialang.org/u/Eben60)\
**Post date:** [August 1, 2022, 10:56am UTC](https://discourse.julialang.org/t/sunday-small-challenge/85041/6 "2022-08-01T10:56:22Z")

</div>

> [@Jollywatt](#):
>
> `unhtml(str) = replace(String(str), r"</?\w+>" => "")`

In case source string is a known **const** , you don’t need any regexes, the answer is already known. If it not exactly that and can be some other valid HTML:

```julia

unhtml(str) = replace(String(str), r"</?\w+>" => "")

s1 = "<div>Hello <b>JuliaCon2022!</b></div>"
s2 = """
<div id="header" class="container_10">Hello <b>JuliaCon2022!</b></div>
"""

s1v = Vector{UInt8}(s1)
s2v = Vector{UInt8}(s2)

julia> unhtml(s1v)
"Hello JuliaCon2022!"

julia> unhtml(s2v)
"<div id=\"header\" class=\"container_10\">Hello JuliaCon2022!\n"

```

BTW the last tag in the original post should probably be a closing one: `</div>`

---

<div class="post-metadata">

**Author:** ![DNF](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/dnf/32/10191_2.png) [@DNF](https://discourse.julialang.org/u/DNF)\
**Post date:** [August 1, 2022, 1:25pm UTC](https://discourse.julialang.org/t/sunday-small-challenge/85041/7 "2022-08-01T13:25:02Z")

</div>

> [@Syx\_Pek](#):
>
> ```julia
> depth(str) = cumsum(2('(' - c) + 1 for c in str) |> maximum
> 
> ```

Here’s one for parens depth that doesn’t allocate, for a 10x speedup, and handles strings that aren’t just ‘(’ and ‘)’:

```julia
function pdepth(str)
    current = 0
    maxdepth = -1
    for c in str
        current += (c == '(') - (c == ')')
        maxdepth = max(maxdepth, current)
    end
    return maxdepth
end

```

---

<div class="post-metadata">

**Author:** ![DNF](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/dnf/32/10191_2.png) [@DNF](https://discourse.julialang.org/u/DNF)\
**Post date:** [August 1, 2022, 1:31pm UTC](https://discourse.julialang.org/t/sunday-small-challenge/85041/8 "2022-08-01T13:31:40Z")

</div>

> [@miguelraz](#):
>
> Max Parenthesis depth - count the deepest level of nesting for parenthesis.

How should the code handle leading `)`s? What is the correct value for

```julia
str = ")))(())()()("

```

or

```julia
str = "(((()"

```

?

---

<div class="post-metadata">

**Author:** ![jules](https://avatars.discourse-cdn.com/v4/letter/j/41988e/32.png) [@jules](https://discourse.julialang.org/u/jules)\
**Post date:** [August 1, 2022, 1:48pm UTC](https://discourse.julialang.org/t/sunday-small-challenge/85041/9 "2022-08-01T13:48:14Z")

</div>

### 2

```julia
hamming(x, y) = sum(Base.splat(!=), zip(x, y))

```

---

<div class="post-metadata">

**Author:** ![miguelraz](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/miguelraz/32/631_2.png) [@miguelraz](https://discourse.julialang.org/u/miguelraz)\
**Post date:** [August 1, 2022, 1:49pm UTC](https://discourse.julialang.org/t/sunday-small-challenge/85041/10 "2022-08-01T13:49:05Z")

</div>

Thanks, I’ve fixed the closing tag, yes.

---

<div class="post-metadata">

**Author:** ![Syx\_Pek](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/syx_pek/32/6364_2.png) [@Syx\_Pek](https://discourse.julialang.org/u/Syx_Pek)\
**Post date:** [August 1, 2022, 4:57pm UTC](https://discourse.julialang.org/t/sunday-small-challenge/85041/11 "2022-08-01T16:57:20Z")

</div>

We can also obfuscate it 😛

```julia
depth(str) = foldl(((c, m), n) -> (c+n, max(m, c+n)), 
    (2('(' - c) + 1 for c in str); init = (0, 0))[2]

```