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 (`[` `]`).

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.