# Simple challenge: Is there a more "Julian" solution?

**URL:** <https://discourse.julialang.org/t/simple-challenge-is-there-a-more-julian-solution/32211>\
**Category:** Performance\
**Created:** [December 12, 2019, 10:49pm UTC](https://discourse.julialang.org/t/simple-challenge-is-there-a-more-julian-solution/32211 "2019-12-12T22:49:20Z")\
**Posts on this page:** 13\
**Page:** 1

<div class="post-metadata">

**Author:** ![wsphillips](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/wsphillips/32/6777_2.png) [@wsphillips](https://discourse.julialang.org/u/wsphillips)\
**Post date:** [December 12, 2019, 10:49pm UTC](https://discourse.julialang.org/t/simple-challenge-is-there-a-more-julian-solution/32211/1 "2019-12-12T22:49:20Z")

</div>

I am porting someone else’s MATLAB code and found an indexing pattern that was baked in rather than generated programmatically. After hacking at it for a bit I managed to generalize the pattern. My solution isn’t very pretty or clever, nor is it a function that _demands_ performance optimization. However, I am always curious to see demos of good idiomatic Julia.

So…for those that want to try solving it, here is an example of the pattern when `N = 13`:

```julia
index1=[
1,1,1,1,1,1,1,1,1,1,1,1,1,2,3,4,5,6,7,8,9,10,11,12,13,13,13,13,13,13,13,13,13,
13,13,13,13,12,11,10,9,8,7,6,5,4,3,2,2,2,2,2,2,2,2,2,2,2,2,3,4,5,6,7,8,9,10,11,
12,12,12,12,12,12,12,12,12,12,12,11,10,9,8,7,6,5,4,3,3,3,3,3,3,3,3,3,3,4,5,6,7,
8,9,10,11,11,11,11,11,11,11,11,11,10,9,8,7,6,5,4,4,4,4,4,4,4,4,5,6,7,8,9,10,10,
10,10,10,10,10,9,8,7,6,5,5,5,5,5,5,6,7,8,9,9,9,9,9,8,7,6,6,6,6,7,8,8,8,7,7]

```

I have a [gist here](https://gist.github.com/wsphillips/c70681b4d57bedd67f7ec1808a0a4c2c) with my own MWE of a working solution. You can either look at the gist and try to improve it, or, for bonus difficulty ignore the gist and just use the unrolled vector as a reference.

---

<div class="post-metadata">

**Author:** ![longemen3000](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/longemen3000/32/7298_2.png) [@longemen3000](https://discourse.julialang.org/u/longemen3000)\
**Post date:** [December 13, 2019, 2:45am UTC](https://discourse.julialang.org/t/simple-challenge-is-there-a-more-julian-solution/32211/2 "2019-12-13T02:45:53Z")

</div>

didn’t look at the gist. this is a lazy constructor

```julia
struct MyCustomIndex
    len::Int
end
Base.length(a::MyCustomIndex) = a.len*a.len

custom_state(i::Int,state::Int,current_n::Int,max_n::Int,counter::Int) = custom_state(i,Val(state),current_n,max_n,counter)

function custom_state(i::Int,state::Val{1},current_n::Int,max_n::Int,counter::Int) #constant increasing
    if current_n == max_n
        return (i+1,10,1,max_n,counter+1)
    else
        return (i,1,current_n+1,max_n,counter+1)
    end 
end
function custom_state(i::Int,state::Val{10},current_n::Int,max_n::Int,counter::Int) #increasing
    if current_n+1 == max_n
        return (i,-1,1,max_n-1,counter+1)
    else
        return (i+1,10,current_n+1,max_n,counter+1)
    end 
end
function custom_state(i::Int,state::Val{-1},current_n::Int,max_n::Int,counter::Int) #constant decreasing
    if current_n+1 == max_n
        return (i,-10,1,max_n,counter+1)
    else
        return (i,-1,current_n+1,max_n,counter+1)
    end 
end

function custom_state(i::Int,state::Val{-10},current_n::Int,max_n::Int,counter::Int) #decreasing
    if current_n == max_n
        return (i,1,1,max_n-1,counter+1)
    else
        return (i-1,-10,current_n+1,max_n,counter+1)
    end 
end

function Base.iterate(S::MyCustomIndex, state=(1,1,1,S.len,1))
    if state[end] > S.len^2
        return nothing
    else
        return (state[1],custom_state(state...))
    end
end

```

to test:

```julia
a = MyCustomIndex(13)
collect(a) == index1 #true

```

To explain my code, i take the challenge as builing a state machine capable of spitting those values. i observed 4 states:

- constant increasing (1): the value is kept constant, the next state will increase the value
- increasing (10): the value is increasing, the next state will maintain the value
- constant increasing (-1): the value is kept constant, the next state will decrease the value
- increasing (-10): the value is decreasing, the next state will maintain the value  
the states follow the order 1 → 10 → -1 → -10 → 1 …

Then, i build some functions that pass those states around. the termination criteria is in the iteration protocol instead of the state using the variable `counter`

I used the following julia capabilities:

- Multiple dispatch on values: `custom_state(x) = custom_state(Val(x))` allows me to dispatch on the value (in this case the state’s numbers. another option could be to build some structs to represent those states, but i didn’t feel like it 😅 . this allowed me to define he logic in different functions instead of a big if else branch
- iterator interface: i can define `Base.iterate` from my custom type, and that allows me to build Iterators that are lazy calculated. for example doing `MyCustomIndex(10_000)` doesn’t allocate a vector of length 100\_000\_000, and you just consume the values

---

<div class="post-metadata">

**Author:** ![longemen3000](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/longemen3000/32/7298_2.png) [@longemen3000](https://discourse.julialang.org/u/longemen3000)\
**Post date:** [December 13, 2019, 2:48am UTC](https://discourse.julialang.org/t/simple-challenge-is-there-a-more-julian-solution/32211/3 "2019-12-13T02:48:58Z")

</div>

Shorter Version:

```julia
struct MyCustomIndex
    len::Int
end

Base.length(a::MyCustomIndex) = a.len*a.len

custom_state(i,state,n,max_n,j) = custom_state(i,Val(state),n,max_n,j)

custom_state(i,state::Val{1},n,max_n,j) = n == max_n ? (i+1,10,1,max_n,j+1) : (i,1,n+1,max_n,j+1)

custom_state(i,state::Val{10},n,max_n,j) = n+1 == max_n ? (i,-1,1,max_n-1,j+1) : (i+1,10,n+1,max_n,j+1)

custom_state(i,state::Val{-1},n,max_n,j) = n+1 == max_n ? (i,-10,1,max_n,j+1) : (i,-1,n+1,max_n,j+1)

custom_state(i,state::Val{-10},n,max_n,j) = n == max_n ? (i,1,1,max_n-1,j+1) : (i-1,-10,n+1,max_n,j+1)

function Base.iterate(a::MyCustomIndex, state=(1,1,1,a.len,1))
    if state[end] > length(a)
        return nothing
    else
        return (state[1],custom_state(state...))
    end
end

```

---

<div class="post-metadata">

**Author:** ![Mason](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mason/32/2423_2.png) [@Mason](https://discourse.julialang.org/u/Mason)\
**Post date:** [December 13, 2019, 3:07am UTC](https://discourse.julialang.org/t/simple-challenge-is-there-a-more-julian-solution/32211/4 "2019-12-13T03:07:10Z")

</div>

Note that the dynamic dispatching you’re doing with `Val` makes your solution 1000x times slower than the one that the OP linked to.

---

<div class="post-metadata">

**Author:** ![longemen3000](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/longemen3000/32/7298_2.png) [@longemen3000](https://discourse.julialang.org/u/longemen3000)\
**Post date:** [December 13, 2019, 3:08am UTC](https://discourse.julialang.org/t/simple-challenge-is-there-a-more-julian-solution/32211/5 "2019-12-13T03:08:00Z")

</div>

is enum an option?

---

<div class="post-metadata">

**Author:** ![Mason](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mason/32/2423_2.png) [@Mason](https://discourse.julialang.org/u/Mason)\
**Post date:** [December 13, 2019, 3:12am UTC](https://discourse.julialang.org/t/simple-challenge-is-there-a-more-julian-solution/32211/6 "2019-12-13T03:12:47Z")

</div>

No, you can’t dispatch on enum values. Instead, you can do pattern matching:

```julia
using Rematch
struct MyCustomIndex
    len::Int
end

Base.length(a::MyCustomIndex) = a.len*a.len

custom_state(i, state, n, max_n, j) = @match state begin
    1 => n == max_n ? (i+1,10,1,max_n,j+1) : (i,1,n+1,max_n,j+1)
    10 => n+1 == max_n ? (i,-1,1,max_n-1,j+1) : (i+1,10,n+1,max_n,j+1)
    -1 => n+1 == max_n ? (i,-10,1,max_n,j+1) : (i,-1,n+1,max_n,j+1)
    -10 => n == max_n ? (i,1,1,max_n-1,j+1) : (i-1,-10,n+1,max_n,j+1)
end

function Base.iterate(a::MyCustomIndex, state=(1,1,1,a.len,1))
    if state[end] > length(a)
        return nothing
    else
        return (state[1],custom_state(state...))
    end
end

```

or just write `if-else` statements.

---

<div class="post-metadata">

**Author:** ![longemen3000](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/longemen3000/32/7298_2.png) [@longemen3000](https://discourse.julialang.org/u/longemen3000)\
**Post date:** [December 13, 2019, 3:25am UTC](https://discourse.julialang.org/t/simple-challenge-is-there-a-more-julian-solution/32211/7 "2019-12-13T03:25:34Z")

</div>

added some types to dispatch on real types hahaha

```julia

struct P1 end
struct P10 end
struct M10 end
struct M1 end

struct MyCustomIndex
    len::Int
end

Base.length(a::MyCustomIndex) = a.len*a.len

custom_state(i,state::P1,n,max_n,j) = n == max_n ? (i+1,P10(),1,max_n,j+1) : (i,state,n+1,max_n,j+1)

custom_state(i,state::P10,n,max_n,j) = n+1 == max_n ? (i,M1(),1,max_n-1,j+1) : (i+1,state,n+1,max_n,j+1)

custom_state(i,state::M1,n,max_n,j) = n+1 == max_n ? (i,M10(),1,max_n,j+1) : (i,state,n+1,max_n,j+1)

custom_state(i,state::M10,n,max_n,j) = n == max_n ? (i,P1(),1,max_n-1,j+1) : (i-1,state,n+1,max_n,j+1)

function Base.iterate(S::MyCustomIndex, state=(1,P1(),1,S.len,1))
    if state[end] > S.len^2
        return nothing
    else
        return (state[1],custom_state(state...))
    end
end

```

---

<div class="post-metadata">

**Author:** ![longemen3000](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/longemen3000/32/7298_2.png) [@longemen3000](https://discourse.julialang.org/u/longemen3000)\
**Post date:** [December 13, 2019, 3:56am UTC](https://discourse.julialang.org/t/simple-challenge-is-there-a-more-julian-solution/32211/8 "2019-12-13T03:56:58Z")

</div>

yeah, finally the fastest code is a simple if else (what Rematch is doing i suppose, nice package!). I recommend adding the method `eltype`, to specify the type of the array created when collecting the results if necessary

```julia
struct MyCustomIndex
    len::Int
end

Base.eltype(::Type{MyCustomIndex}) = Int #important when collecting
Base.length(a::MyCustomIndex) = a.len*a.len

function custom_state(i::Int,state,n,max_n,j)
    if state == 1
        n == max_n ? (i+1,10,2,max_n,j+1) : (i,state,n+1,max_n,j+1)
    elseif state == 10
        n == max_n ? (i,-1,2,max_n-1,j+1) : (i+1,state,n+1,max_n,j+1)
    elseif state == -1
        n == max_n ? (i,-10,1,max_n,j+1) : (i,state,n+1,max_n,j+1)
    else
        n == max_n ? (i,1,1,max_n-1,j+1) : (i-1,state,n+1,max_n,j+1)
    end
end

function Base.iterate(S::MyCustomIndex, state=(1,1,1,S.len,1))
    i,state,n,max_n,j = state
    if j > S.len^2
        return nothing
    else
        return (i,custom_state(i,state,n,max_n,j))
    end
end

```

Is this indexing algorithm related somewhat with this image?  
 ![image](https://global.discourse-cdn.com/julialang/original/3X/1/b/1b428930a47ef0c0af0b928faad7badf41a18a0f.png)

---

<div class="post-metadata">

**Author:** ![Mason](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mason/32/2423_2.png) [@Mason](https://discourse.julialang.org/u/Mason)\
**Post date:** [December 13, 2019, 5:50am UTC](https://discourse.julialang.org/t/simple-challenge-is-there-a-more-julian-solution/32211/9 "2019-12-13T05:50:21Z")

</div>

> [@longemen3000](#):
>
> added some types to dispatch on real types hahaha

Dynamically dispatching on ‘real` types doesn’t solve the problem. It’s just that whenever you can’t statically predict what types go into a function, you should expect significant slowdowns since type level stuff needs to happen at runtime. Your example way fare a better in practice due to small union optimization though.

---

<div class="post-metadata">

**Author:** ![RoyiAvital](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/royiavital/32/571_2.png) [@RoyiAvital](https://discourse.julialang.org/u/RoyiAvital)\
**Post date:** [December 13, 2019, 7:03am UTC](https://discourse.julialang.org/t/simple-challenge-is-there-a-more-julian-solution/32211/10 "2019-12-13T07:03:34Z")

</div>

> [@Mason](#):
>
> Note that the dynamic dispatching you’re doing with `Val` makes your solution 1000x times slower than the one that the OP linked to.

Could you explain? I thought the Dynamic Dispatching in Julia help choosing optimized code path, not create slow downs. Is it used incorrectly above?

---

<div class="post-metadata">

**Author:** ![kristoffer.carlsson](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/kristoffer.carlsson/32/22_2.png) [@kristoffer.carlsson](https://discourse.julialang.org/u/kristoffer.carlsson)\
**Post date:** [December 13, 2019, 7:27am UTC](https://discourse.julialang.org/t/simple-challenge-is-there-a-more-julian-solution/32211/11 "2019-12-13T07:27:36Z")

</div>

Dynamic dispatch has a cost (you need to lookup what method to call). Depending on how much work the function does that cost may be significant or not.

---

<div class="post-metadata">

**Author:** ![GunnarFarneback](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/gunnarfarneback/32/1827_2.png) [@GunnarFarneback](https://discourse.julialang.org/u/GunnarFarneback)\
**Post date:** [December 13, 2019, 8:34am UTC](https://discourse.julialang.org/t/simple-challenge-is-there-a-more-julian-solution/32211/12 "2019-12-13T08:34:28Z")

</div>

This might qualify as overly clever rather than anything else. Enjoy.

```julia
julia> function index(n, i)
           a = n^2 - i
           b = floor(Int, sqrt(a))
           c = a - b^2
           return (n + 1) ÷ 2 - min(c - b ÷ 2, (b + 1) ÷ 2) * (-1)^b
       end
index (generic function with 1 method)

julia> index1 == index.(13, 1:169)
true

```

---

<div class="post-metadata">

**Author:** ![wsphillips](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/wsphillips/32/6777_2.png) [@wsphillips](https://discourse.julialang.org/u/wsphillips)\
**Post date:** [December 13, 2019, 1:51pm UTC](https://discourse.julialang.org/t/simple-challenge-is-there-a-more-julian-solution/32211/13 "2019-12-13T13:51:55Z")

</div>

> [@longemen3000](#):
>
> Is this indexing algorithm related somewhat with this image?

There are two patterns, the second being just an offset of the first (it starts with the increment instead of repeating integers). They’re used as a pair of indexes to slice into an ndarray of images for some volumetric deconvolution.

> [@GunnarFarneback](#):
>
> This might qualify as overly clever rather than anything else. Enjoy.
> 
> ```julia
> julia> function index(n, i)
> a = n^2 - i
> b = floor(Int, sqrt(a))
> c = a - b^2
> return (n + 1) ÷ 2 - min(c - b ÷ 2, (b + 1) ÷ 2) * (-1)^b
> end
> index (generic function with 1 method)
> 
> julia> index1 == index.(13, 1:169)
> true
> 
> ```

This is nice, and more along the lines of what I expected 😃 Storing the pattern as a vector (as in my own solution) is not nearly as clever as transforming any given index. (Although, for my intended application I believe it’s worth it to compute and store the values just once.)

> [@kristoffer.carlsson](#):
>
> Dynamic dispatch has a cost (you need to lookup what method to call). Depending on how much work the function does that cost may be significant or not.

Indeed, later on the algorithm has to lookup the same values many thousands of times! 😅 However, that also depends on whether I rearrange the logic/computation after the straight port. When I stumbled upon the baked in pattern (and subsequently had to scratch my chin for a surprising amount of time) I thought it was a great challenge akin to MatLAB Cody that some might enjoy flexing on.