# 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.