Walk on Matrix using pseudocode

tldr; if you visualize walk in matrix, it looked like playing snake moving inward spiral motion starting at top left and ends somewhere in the middle.

Code implemented in Elixir can be found here

Intro

Walk in Matrix is a coding puzzle in which you are given an input of 2-dimensional list of integers and returns a list of integers.

The input is something like this:

[
  [1, 2, 3],
  [4, 5, 6],
  [7, 8, 9]
]

Then the output:

[1, 2, 3, 6, 9, 8, 7, 4, 5]

Before we start, some caveats:

  • We'll only talk in pseudocode.
  • This walkthrough won't cover about optimizations or anything that has something to do for-the-holy-grail of speed nor efficiency!
  • We won't explain here why recursion exists nor its purpose. Tip: search thru internet "recursion eli5" or "recursion illustration examples" (you get what I mean).

Here's the 6 magical "steps" to walk in the matrix

1) Think, think!

  • Must be a nested list
  • Each row (list) has the same amount of elements.
  • Also, we're gonna add some fancy words: head and tail.

Here's what a nested list, visualized:

[
  [1, 2, 3],
  [4, 5, 6],
  [7, 8, 9]
]

Note: as you may noticed, list contains numbers. We're going to stick with numbers for the sake of convenience. Pay close attention to those square brackets ([ ]).

What do head and tail look like?

head is when you take the first element from a list. In that case the head here is:

[1, 2, 3]

Whoa, I thought "first element" you say? Yes, [1, 2, 3] is the first element. As "first element" means it is either a single one OR lots of it BUT grouped as one. As you see, [1, 2, 3] is a list that contains 3 numbers where it is separated by comma (,). It just so happened that the first element was a list! and the separator for the rest of it is by adding a comma (,).

Now tail, on the other hand, is another way of saying "the rest or what's left after you take out the first element".

What does a tail look like?

[
  [4, 5, 6],
  [7, 8, 9]
]

Aside from head and tail, we should make another group called sorted and unsorted. What this means is that the correct order of numbers are to be put in sorted while the rest is in unsorted. This unsorted group will eventually be moved to sorted.

here's our current state:

[
  [1, 2, 3],
  [4, 5, 6],
  [7, 8, 9]
]

sorted = []
unsorted = []

2) Move, move!

So we're going to start at the head. Move the leftmost element and put it in the rightmost of sorted group

[
  [1, 2, 3], <- this is the head
  [4, 5, 6],
  [7, 8, 9]
]

our head     sorted       unsorted
[1, 2, 3]    []           []
[2, 3]       [1]          []
[3]          [2, 1]       []
[]           [3, 2, 1]    []

Howdy, wait! it looks like we just reversed the order of those numbers!

here's our current state:

head = []
sorted = [3, 2, 1]
unsorted = []

tail = 
[
  [4, 5, 6],
  [7, 8, 9]
]

3) Put it here, put it there

Remember tail? Currenly our tail looks like this

[
  [4, 5, 6],
  [7, 8, 9]
]

We're going to put elements of tail into 2 groups:

  • The last element of each list should go in sorted
  • The rest goes in unsorted

Don't do anything on the very last list, as we'll use that on the next step

The "recursion" part starts here (step #3) inside the unsorted until none is left. So here's step-by-step walkthrough:

[
  [4, 5, 6], <- do this
  [7, 8, 9]  <- don't touch this last list
]

row          sorted         unsorted
[4, 5, 6]    [3, 2, 1]      []
[4, 5]       [6, 3, 2, 1]   []
[4]          [6, 3, 2, 1]   [4]
[]           [6, 3, 2, 1]   [5, 4]

here's our current state:

[
  [7, 8, 9]
]

head = []
sorted = [6, 3, 2, 1]
unsorted = [5, 4]
tail =
[
  [7, 8, 9]
]

4) Put it exactly as it should be

When you reach at the last row of tail, just copy as it is.

[
  [7, 8, 9] <- last row
]

row          sorted                  unsorted
[7, 8, 9]    [6, 3, 2, 1]            [5, 4]
[]           [7, 8, 9, 6, 3, 2, 1]    [5, 4]

here's our current state:

[

]

head = []
sorted = [7, 8, 9, 6, 3, 2, 1]
unsorted = [5, 4]
tail = []

5) Everyday I'm shufflin'

Once you're done with step #4 (aka last row), go back to step #2 and keep doing this until unsorted is empty. Take note, we still have elements in unsorted.

So unsorted elements will be moved to "head":

[
  [4, 5] <- go back to step #2, unsorted is now "head"
]

row       sorted                        unsorted
[4, 5]    [7, 8, 9, 6, 3, 2, 1]         []
[5]       [4, 7, 8, 9, 6, 3, 2, 1]      []
[]        [5, 4, 7, 8, 9, 6, 3, 2, 1]   []

Since unsorted is now empty, we're moving to the final step.

6) Reverse UNO!

Once unsorted is empty, now we reverse the sorted list in order to get the final output.

from:

[5, 4, 7, 8, 9, 6, 3, 2, 1]

to:

[1, 2, 3, 6, 9, 8, 7, 4, 5]

So that's it! I hope you enjoyed this walkthrough. I didn't cramps during the session. But if you're tired, you can see the actual implementation in Elixir here.