DEV Community: Warisul Imam

Spiral Matrices with Julia

Warisul Imam — Mon, 15 Feb 2021 14:57:42 +0000

Julia gives you [almost] C-like speed with Python-like learning curve and easy syntax. In an attempt to solidify my Julia-lang skills I was working through the exercises on Exercism¹ which, by the way, is an amazing resource to practice programming languages. That's where I came across the Spiral Matrix problem.

As you can see, the problem requires you to write a function that takes in an integer n, and outputs a spiral matrix of dimensions n x n (which implies that it's also a square matrix) with n^2 elements sorted from smallest to largest in a [clockwise] spiral order².

I couldn't think of a way to accomplish this task right off the top of my head. But I refused to look up solutions and decided to figure it out entirely on my own. Three days of working on paper, in code, and hunting down repeating patterns which could be expressed in code through mathematical formulae - finally let me obtain the ever-desired spiral matrix. My hard-work paid off.

The purpose of this article is to walk the reader through my entire thought process from the moment I began brainstorming about ways of solving this problem all the way to the moment when I finally acquired the desired result. We'll come across some pattern-hunting, a bit of math, a few code snippets in Julia trying to achieve the individual parts that are finally put together to acquire the solution to the exercise. A basic understanding of linear algebra (vectors and matrices) will be helpful albeit not necessary.

If anything in the Julia syntax looks confusing or odd, make sure to check out the things you should know about Julia at the bottom of this article.

How I did it

The basic approach I took was to take an array containing the integers from 1 through n^2 and map them to a two-dimensional array (a n x n matrix) in a spiral manner. Every n in the one-dimensional array can be paired with some tuple (i,j) describing the location it is mapped to in the two dimensional array.³

Thus we obtain a new array of tuples.

Once we've obtained that array of tuples containing the coordinates of another two-dimensional array where each consecutive n in the range of 1 to n^2 is to be mapped to in order to obtain a spiral matrix, the remaining task is pretty straight forward. Here's how it looks (the linear_map variable is set for n=4)

# initiate a spiral matrix of n x n dimensions filled with zeros
spiral_mat = zeros(n, n)
display(spiral_mat)
#=
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
=#

# the array containing the coordinates
linear_map = [(1,1), (1,2), (1,3), (1,4), (2,4), (3,4), (4,4), (4,3), (4,2), (4,1), (3,1), (2,1), (2,2), (2,3), (3,3), (3,2)]

for n in 1:length(linear_map)
  # set n as the value of spiral_mat[i,j]
  spiral_mat[linear_map[n][1], linear_map[n][2]] = n
end

display(spiral_mat)
#=
 1  2  3 4
12 13 14 5
11 16 15 6
10  9  8 7
=#

Note: We're using `display()` instead of `print()` or `println()` because the latter two print the output as inline and thus don't have the pretty matrix-like formatting like `display()` does.

Okay, that was easy enough, just a couple of lines of code. But how do we obtain the linear_map? That's the fun part.. and also the relatively harder one 🙄.

Let's go find some patterns! 🙌

Hunting for Patterns

The first thing that came to my mind was to write down the is and js side by side and see if there's a specific incremental and/or decremental pattern that they followed.

Here are the hand-written linear_maps for n=2, n=3, and n=4 (2x2, 3x3, and 4x4 matrices).

2x2    3x3    4x4
1 1    1 1    1 1
1 2    1 2    1 2
2 2    1 3    1 3
2 1    2 3    1 4
       3 3    2 4
       3 2    3 4
       3 1    4 4
       2 1    4 3
       2 2    4 2
              4 1
              3 1
              2 1
              2 2
              2 3
              3 3
              3 2

Observe that in all three cases,

the right column increments while the left column remains at the same value
the left column increments while the right column remains at the same value
the right column decrements while the left column remains at the same value
the left column decrements while the right column remains at the same value

These four events take place in the order I've listed them and keep repeating till the center of the spiral matrix is reached.⁴ I'm going to call this list the actions and each of the elements, an action, through out the rest of the article for the ease of addressing.

We'll discuss shortly about how the algorithm (albeit a pretty abstract one so far) identifies the center.

To make it easier for you to remember, here's the same list in a more compact form. Keeping this in memory is going to prove helpful in a bit.

right increments, left stays same
left increments, right stays same
right decrements, left stays same
left decrements, right stays same

Alright. Now, how does the algorithm know when it's reached the center? The short answer is that it doesn't. I've left out a constraint from the algorithm which I'm going to add in now. Before each of the events take place, a check must be made whether the same configuration of i and j has been went over before. Namely, you can imagine adding (i,j) pairs to an array as you go through the steps mentioned above; but before adding the tuple to the array you check whether it's already in the array or not - you carry out the step if it isn't in the array, pass on to the next step if it is already in the array, and stop the algorithm if you find yourself in the situation where you skip to the next step because you found a certain pair, say, (a,b) in the array, but the pair generated from the next step, say, (c,d), is also in the array. That is to say that if you find two consecutively generated pairs to be in the array, that's when you stop.

Now we make another observation - exactly how many times does each of the columns increment or decrement before moving to the next step in the actions? Here's a Julia repl you can play with and generate the i and j columns for any given n to verify the claim I'm about to make.

Here's the claim, or the observation, rather. If you observe enough of those columns, you would notice a general pattern. Here's what it looks like. It might be a little long, so bear with me. We take i=1 and j=1.

i   j
i   j+1
i   j+2
.   .
.   .
.   .
i   n
i+1 n
i+2 n
i+3 n
.   .
.   .
.   .
n   n
n   n-1
n   n-2
n   n-3
.   .
.   .
.   .
n   j
n-1 j
n-2 j
n-3 j
.   .
.   .
.   .
i+1 j
i+1 j+1
i+1 j+2
i+1 j+3
.   .
.   .
.   .
i+1 n-1
i+2 n-1
i+3 n-1
i+4 n-1
.   .
.   .
.   .
n-1 n-1
n-1 n-2
n-1 n-3
n-1 n-4
.   .
.   .
.   .
n-1 j+1
n-2 j+1
n-3 j+1
n-4 j+1
.   .
.   .
.   .
i+2 j+1
i+2 j+2
i+2 j+3
.   .
.   .
.   .
i+2 n-2
i+3 n-2
i+4 n-2
.   .
.   .
.   .
n-2 n-2
n-2 n-3
n-2 n-4
.   .
.   .
.   .
n-2 j+2
n-3 j+2
n-4 j+2
.   .
.   .
.   .
i+3 j+2
i+3 j+3
i+3 j+4
.   .
.   .
.   .
i+3 n-3
i+4 n-3
i+5 n-3
.   .
.   .
.   .
n-3 n-3

Oookay, I suppose that was sufficient to show the pretty vague pattern that I spotted by observing a number of (i,j) pair columns for hours.

We can encode this pattern in a piece of pseudo-code. For a given n,

while j != n, j++;
while i != n, i++;
while j != 1, j--;
while i != 2, i--;
while j != n-1, j++;
while i != n-1, i++;
while j != 2, j--;
while i != 3, i--;
while j != n-2, j++;
while i != n-2, i++;
while j != 3, j--;
while i != 4, i--;
while j != n-3, j++;
while i != n-3, i++;

Note: This piece of pseudo-code, although still not dynamic, does the same thing as the general pattern showed earlier.

At this point, we've got ourselves a new array to work with -

[n, n, 1, 2, n-1, n-1, 2, 3, n-2, n-2, 3, 4, n-3, n-3, ...]

Let's recall what this array actually contains. The right column (the j column) increments till it reaches n, then the i increments till it reaches n, then the j decrements till it reaches 1, then the i decrements till it reaches 2, and so on. In other words, our new array contains the upper-bounds and the lower-bounds up to and down to which i and j increment and decrement based on the action. Naturally enough, I'm going to address this array as the bounds for the rest of the article.

Now let's implement the algorithm in the pseudo-code in julia syntax and find the linear_map for a value of n, say, n=2.

# initialize the linear map array
linear_map = []

# initialize i and j and set them equal to 1
i=j=1

# set a value for n
n = 2

while j != n
    push!(linear_map, (i, j))
    j += 1
end

while i != n
    push!(linear_map, (i, j))
    i += 1
end

while j != 1
    push!(linear_map, (i, j))
    j -= 1
end

push!(linear_map, (i,j))
#= we're pushing (i,j) first and then incrementing/decrementing;
that is why we need to push in the final values
of i and j after the loop is over
=#


display(linear_map)
#=
[(1,1), (1,2), (2,2), (2,1)]
=#

The capability of stopping the algorithm when the center is reached can not be deduced from this array. However, we'll find out soon that we won't need to stop when the center is reached, we can make use of another observation to select a part of this array, the bounds, to work with and neglect the rest.⁵

The next task is to establish a one-to-one correspondence between the set of natural numbers (1, 2, 3, ...) and the bounds. Although it looks like a tricky job at the face of it, we're going to figure out a clever work around to simplify the problem in hand.

Order within the Chaos

Let's begin with establishing a one-to-one correspondence between the set of natural numbers and the bounds.

Apologies: Please pardon my messy and lousy illustrations, working with graphics isn't quite my thing.

Now as you can see, there's no easy function that can be used to map each of the elements of the set of natural numbers to the bounds. Hence we're not going to work with the set of natural numbers directly. Instead, we're going to break it up into two subsets - one containing the natural numbers that are mapped to the elements in the bounds that have an n in them, and the other containing the natural numbers being mapped to the constants in the bounds. Then again, we'll make two more subsets from the two subsets of bounds - one containing the odd numbers of its parent set and the other containing the even numbers of the same. Like so...

We have thus acquired four simple arrays/sets - A, B, C, and D - whose general formulae can now be easily deduced unlike earlier. The general formulae are as follows

A(k) = 4k - 3
B(k) = 4k - 2
C(k) = 4k - 1
D(k) = 4k

Now, by noticing the mapping from the set of natural numbers to the bounds once again, we observe that the general formulae of the sets to which each of A, B, C, and D are being mapped to are

A'(k) = n - (k-1)
B'(k) = n - (k-1)
C'(k) = k
D'(k) = k + 1

where A', B', C', and D' are the respective ranges of the functions A, B, C, and D.

Now is a good time to recall what we're working towards here. We want to be able to map each of the elements of the set of natural numbers to the bounds. Alright, let's get back to doing that. We took bounds apart, forming A, B, C, and D. This made our task of finding the general formulae easier. Now it's time to put them back together to obtain the original bounds array. But that's not all, we also need to encode the natural numbers that are mapped to each element in bounds. To do that, we'll simply replace each element of bounds with a tuple whose first element will be the natural number mapped to the index of the element and second element will be the original element of bounds. We'll not be doing that in the bounds itself, though. We'll be doing it in the broken down arrays - A, B, C, and D. In fact, that is exactly why we broke down bounds, to make the task just mentioned easier to accomplish. Here's how that's going to look like.

[(1,n)  (2,n)  (3,1)  (4,2)  (5,n-1)  (6,n-1)  (7,2)  (8,3)  (9,n-2)  (10,n-2)  (11,3)  (12,4)  (13,n-3)  (14,n-3)  ... ]

Label: We'll call this one `mapped_bounds`.

Here's how to do it in code

# broken down arrays with tuples
a = [(4*k - 3, n - (k-1)) for k in 1:n]
b = [(4*k - 2, n - (k-1)) for k in 1:n]
c = [(4*k - 1, k) for k in 1:n]
d = [(4*k, k+1) for k in 1:n]

# put the array containing 'n' together from its odd and even number subsets
ens = cat(a, b, dims=(1, 1))

# do the same for the array of the constants
nums = cat(c, d, dims=(1, 1))

#= Note: We're keeping 'ens' and 'nums' in variables because
later we'll also need them individually =#

# finally, put bounds together by concatenating ens and nums
bounds = sort(cat(ens, nums, dims=(1, 1)))

#= Note: We're sorting bounds by the first elements of the
tuples (by default) which puts the natural numbers in
progressive order =#

Now that we have a dynamic piece of code (with respect to n, that is) to generate the bounds array, we're finally ready to dynamically generate the linear_map and execute the few lines of code we saw toward the beginning of the article, finally acquiring our ever-desired spiral matrix.

Putting it all together

Alright, let's get the linear_map. Here's what we gotta do - we gotta loop through bounds, check whether the iterant (which is a tuple) belongs to the ens or the nums, check whether the first element of the iterant is even or odd, then do something with i or j on the basis of the previous checks, and finally add (push) the tuple (i,j) to the linear_map.

Here's how the code looks like

#initialize linear_map variable
linear_map = []

#= notice that the first elements of the tuples are A(k), B(k),
C(k), and D(k), while the second elements are A'(k), B'(k), C'(k),
and D'(k) =#

a = [(4*k - 3, n - (k-1)) for k in 1:n]
b = [(4*k - 2, n - (k-1)) for k in 1:n]
c = [(4*k - 1, k) for k in 1:n]
d = [(4*k, k+1) for k in 1:n]

ens = cat(a, b, dims=(1, 1))
nums = cat(c, d, dims=(1, 1))
bounds = sort(cat(ens, nums, dims=(1, 1)))

i = j = 1

for e in bounds[1:2*n - 1]
    # why the slicing? check note 5 in footer
    if e in ens
        if e[1] % 2 == 1
            while j != e[2]
                push!(linear_map, (i, j))
                j += 1
            end
        elseif e[1] % 2 == 0
            while i != e[2]
                push!(linear_map, (i, j))
                i += 1
            end
        end

    elseif e in nums
        if e[1] % 2 == 1
            while j != e[2]
                push!(linear_map, (i, j))
                j -= 1
            end
        elseif e[1] % 2 == 0
            while i != e[2]
                push!(linear_map, (i, j))
                i -= 1
            end
        end        
    end
end

# don't forget to push the final values of i and j after the loops
push!(linear_map, (i,j))

Now that we have linear_map, the rest is as easy as cake. Remember what we did earlier? That's exactly what we're going to do now.

# create a n x n matrix of zeros
spiral_mat = zeroes(n, n)

for k in 1:length(linear_map)
    spiral_mat[linear_map[k][1], linear_map[k][2]] = k
end

display(spiral_mat)

And there you have it, a spiral matrix of n x n dimensions and n^2 elements. Let's put this whole thing in the form of a function now.

function spiral(n::Int)
    n == 0 && return Matrix{Int}(undef,0,0)

    lin_map = [] 
    ens = sort(cat([(4*k - 3, n - (k-1)) for k ∈ 1:n], [(4*k - 2, n - (k-1)) for k ∈ 1:n], dims=(1, 1)))
    nums = sort(cat([(4*k - 1, k) for k ∈ 1:n], [(4*k, k+1) for k ∈ 1:n], dims=(1, 1)))

    i = j = 1

    for e ∈ sort(cat(ens, nums, dims=(1, 1)))[1:2*n - 1]
        if e ∈ ens
            if e[1] % 2 == 1
                while j != e[2]
                    push!(lin_map, (i, j))
                    j += 1
                end
            elseif e[1] % 2 == 0
                while i != e[2]
                    push!(lin_map, (i, j))
                    i += 1
                end
            end

        elseif e ∈ nums
            if e[1] % 2 == 1
                while j != e[2]
                    push!(lin_map, (i, j))
                    j -= 1
                end
            elseif e[1] % 2 == 0
                while i != e[2]
                    push!(lin_map, (i, j))
                    i -= 1
                end
            end        
        end
    end

    push!(lin_map, (i, j))

    spiral_mat = zeros(Int64, n, n)

    for k ∈ 1:length(lin_map)
        spiral_mat[lin_map[k][1], lin_map[k][2]] = k
    end

    return spiral_mat 
end

End

Things you should know about Julia

Julia, unlike most other languages you might be familiar with, is not 0-indexed.

arr = ["a", "b", "c"]
println(arr[0]) # ERROR: BoundsError: attempt to access 3-element Array{Int64,1} at index [0]
println(arr[1]) # a

Julia supports plenty of ASCII characters as part of its syntax. The only one used in this article is ∈, which is the same as in.

back to article

Closing Remarks

Any mistakes pointed out, corrections recommended, and suggestions made, will be highly appreciated. Thank you for taking the time to read this article 🙏

Exercism is a brilliant resource if you're looking to learn new languages or just want to solidify your skills in an existing one. It has plenty of exercises ranged from easy to difficult for you to take on, solve, and improve your efficiency in the language that interests you the most. Although it doesn't teach you the highly advanced stuff, it's still a very good resource to widen your grasp on the basics. ↩
The counter-clockwise implementation of it can also be figured out using a similar approach to this one. The linear map of n=2, for example, would then be [(1,2),(1,1),(2,1),(2,2)] ↩
Note that we don't ever explicitly do the pairing. Instead, since Julia is 1-indexed instead of being 0-indexed, the very indexe of each of the elements in the linear_map is the natural number that the element is paired with. ↩
There's no explicit center when n is odd. To generalize, it can be referred to as the innermost element of the spiral. ↩
The number of iterations over the elements of bounds needed to reach the center of the matrix is equal to 2n-1. That is, when n=2, you'll reach the center after completing the 3rd step; when n=3, the 5th step; when n=7, the 13th step; and so on. ↩

Hamburger Navbar Animation in React

Warisul Imam — Fri, 12 Jun 2020 18:32:32 +0000

Summary: Unlike in jQuery, you can't toggle classes on your HTML elements directly because React uses JSX. You need to use React Refs in order to toggle classes to your JSX elements in order to animate them. That's the process I intend to walk the reader through in this article.
In the first part of the article, I show how it's done in regular HTML and VanillaJS. The second part shows how to do the exact same thing, but in React. And finally I've included a gif of the end product.

Let's face it, imperative animations in React is not intuitive. You can't simply select a HTML tag and add an event listener to it. Or can you? Not really. But there's a work around.

I came across YouTube video by Dev Ed where he shows a sweet and minimal hamburger navbar animation. I wanted to add something like it to a site I was working on. But the problem I faced was that Ed (the YouTube guy) implemented his animation with Javascript but my project was built in React. I could steal his CSS but I couldn't quite steal his Javascript.

I'm not going to bore you with my quest of finding a work around (although I'd love to share the story with you in another post if you're interested in it🙃). Let's get down to the how-tos.

First let me show you how Ed did it. If you want to go straight to the React way of doing it, click here. I've extracted some parts of his HTML, CSS, and Javascript. If you don't want to look through he code, skip down below for a brief description of what he does.

Here's a part of Ed's HTML.

<div class="menu">
  <div class="line"></div>
  <div class="line"></div>
  <div class="line"></div>
</div>

<ul className="nav-links">
  <li>Home</li>
  <li>Projects</li>
  <li>About</li>
</ul>

Here's a part of his CSS.

nav {
  background-color: #469fdf;
  height: 15vh;
  width: 100%;
  display: flex;
  align-items: center;
  padding: 5px;
  position: relative;
}

.nav-links {
  display: flex;
  list-style: none;
  width: 50%;
  height: 100%;
  justify-content: space-around;
  align-items: center;
  margin-left: auto;
}

@media screen and (max-width: 768px) {
  .line {
    width: 30px;
    height: 3px;
    background: white;
    margin: 5px;
  }

  nav {
    position: relative;
  }

  .menu {
    position: absolute;
    cursor: pointer;
    right: 5%;
    top: 50%;
    transform: translate(-5%, -50%);
    z-index: 1;
  }

  .nav-links {
    position: fixed;
    top: 0;
    background: #1484f5;
    height: 100vh;
    width: 100%;
    flex-direction: column;
    clip-path: circle(100px at 90% -30%);
    -webkit-clip-path: circle(100px at 90% -30%);
    transition: all 1s ease-out;
  }

  .nav-links.open {
    clip-path: circle(1000px);
    -webkit-clip-path: circle(1000px);
  }
}

.nav-links li {
  color: white;
}

And finally, here's the magical javascript that Ed used to make the gorgeous animation.

const menu = document.querySelector(".menu");
const navLinks = document.querySelector(".nav-links");
const links = document.querySelector(".nav-links li");

menu.addEventListener("click", () => {
  navLinks.classList.toggle("open");
});

What he did is he created a navbar, created a hamburger menu within it using three divs that made three straight lines, added some nav-links, and then masked them using CSS. And finally, he uses Javascript to unmask it when the hamburger menu is clicked. I'm not much of an expert in CSS and I blindly copy pasted the masking bit for the animation.

The tricky part comes next in the javascript. You'll notice he used an on-click event listener onto the hamburger menu by referencing the nav-links using a queryselector which triggers the animation (which simply toggles a css class to the nav-links). But if you know react basics you'd be able to tell that you can't simply copy paste that bit to your react application. But you can do something very similar using refs.

Without getting too deep as to what refs are, they let you reference the elements in the DOM just as a queryselector or the classic '.getElementBy...()' would. If you want to read more about refs, check out this medium article. Besides using refs, you'd also need to add an onClick prop to the div that wraps the hamburger menu, and would have to define a method that toggles the css class which executes the animation.

Here's how I did it.

First I had to create the refs in the constructor method of my class component (you can also use refs in functional components).

export default class Header extends React.Component {
  constructor() {
    super()
    this.navLinks = React.createRef();
  }
}

Next up, I literally copy pasted the entire nav from Ed's HTML into the render() method, except I had to add classes in jsx rather than actual HTML.

render() {
  return (
    <nav>

      <div ref={this.menu} onClick={this.menuAnimation}>
        <div className="line" />
        <div className="line" />
        <div className="line" />
      </div>

        <ul className="nav-links" ref={this.navLinks}>
            <li onClick={this.menuAnimation}>Home</li>
            <li onClick={this.menuAnimation}>Projects</li>
            <li onClick={this.menuAnimation}>About</li>
        </ul>
      </nav>
    );
  }

So I added an onClick event handler to the nav-links div and added the previously created this.navLinks ref to it. You might be wondering why I added the same event handlers to the nav-links. I'll explain in a bit.
Now we have to define the menuAnimation method. I'll put the entire class in now to avoid confusion.

import React from 'react';

export default class Header extends React.Component {
  constructor() {
    super()
    this.navLinks = React.createRef();
  }

  menuAnimation = () => {
    this.navLinks.current.classList.toggle("open");
  }

  render() {
    return (
      <nav>

        <div className="menu" onClick={this.menuAnimation}>
          <div className="line" />
          <div className="line" />
          <div className="line" />
        </div>

        <ul className="nav-links" ref={this.navLinks}>
          <li onClick={this.menuAnimation}>Home</li>
          <li onClick={this.menuAnimation}>Projects</li>
          <li onClick={this.menuAnimation}>About</li>
        </ul>
      </nav>
    );
  }
}

The code that triggers the animation is pretty much the same. The only difference is how the nav-links div is referenced in Vanilla JS and React.

Here's the end result.

If you followed along by coding you must have realized why I added the menuAnimation method to the nav-linkst too. Because once you toggle the menu and choose one of the nav-links, the menu doesn't close itself (because nothing tells it to!). So you have to add the same toggle method to the nav-links so it closes the hamburger menu before it takes the user to the intended link or page.

P.S. This was my first ever post on Dev. Would really appreciate some support😊. I'd be grateful if anyone pointed out the mistakes in my writings and hopefully I won't make them next time.
You can tweet me at @leadersheir_ and check out some of my projects on github and codepen.
Stay safe, ya'll...
HAPPY CODING!!!