Once in a while, when I do the dsa problems, I try to do them using functional programming. Haskell is really good for some of these problems.They become trivial with it. But input output does have to be handled, and it becomes a pain to do so when you can’t even get the input test case on your standard competitive programming platform. So I tried some Scala once, and I found its ecosystem, at least for such problems, to be good enough.

The problem goes: You are given a matrix, and you must write out its “spiral” form i.e take elements as if you were wrapping a ribbon to the centre of the matrix and lie them out flat.

So this matrix’s ribbon would be [1,2,3,6,9,8,7,4,5]

This seemed to me to be a clear functional programming problem. I suppose an imperative approach would help here, but when I visualised the problem, with a little snake coiling through the matrix, taking it apart piece by piece, I knew it had to be done functionally.

I suppose there is another way to think about it. Combinatorics. Take the size of the matrix, make pairs of (0..number of columns), then (1.. number of rows), then reverse it again, by doing (col-1.. 0) and (row - 1 to 1). This is fine, but it is basically the same ribbon approach expressed in a different way.

The POINT is to think about the underlying structure of the problem. Let's say there is a snake coiling through the box. The snake picking up the first row it can see, turning to the right and then repeating the same process again. How do you express this programmatically? You can get the first row's elements easily, but what about the turning part?

Well, you can flip the remaining matrix (i.e, what is left after the first row is remoed) along it's diagnol. Fancy eighth grade maths term for this is transpose.

Transpose of a matrix - first step

This allows us to have access to the columns of the original matrix as rows now, so we can perform the same operation of just picking up the first row in front of us. But, one more hitch. Picking up the first row when you flip the matrix is not enough. The row we want is actually the last one, so we once again flip it along the middle. Even fancier term for this operation is reverse.

Example of operation sequence - performed once

The sequence is to take the first row, then transpose the remaining matrix, reverse it, and do a repeat rerun until you run out of elements. You can be extra clever about it, and not reverse the matrix each time. Instead, you can take the last element only, and then rinse repeat. But this means that the way in which you do the first operation is different from the way in which you do the remaining operations. And while that is fine, it's not really what I would ideally like to do. Again, snake approach - just consume the first row in front of you.

Initially, I also thought this could be done with a scan or a fold operation. Basically, take the elements and accumulate them somehow. But that didn’t work either, because those approaches iterate through the initial list and consider each element one by one. Here, I had to consider MULTIPLE parts from different elements in the list. And I had to come back to some elements. Unless I transposed the list and passed it to the next element. In which case I was not doing a scan, because I would have to repeat that same process again.

Here is the python code for it:

def ribbon_recursive(matrix):  
    if len(matrix) == 0:  
        return []  
    top_row = matrix[0]  
    if len(matrix[1:]) == 0:   
        return top_row  
    return top_row + ribbon_recursive(transpose(matrix[1: ])[:: -1]) 

This is the basic thing. Find the top, then for the remaining part, transpose and reverse it and continue.

This is the haskell solution:

ribbon matrix = map (head) $ iterate (reverse . transpose . tail) matrix 

One line. Classic.

It’s not perfect. It gives a pesky tail exception I am too bored to calculate. I fixed the problem in Scala by taking the elements only while I actually could.

Iterator.iterate(matrix)(_.tail.transpose.reverse).takeWhile(_.size > 0).map(_.head).flatten

And then after talking to some smarter functional programming people, had to confront my laziness(HA) and then fixed it to this -

ribbon matrix = map (head) $ takeWhile ((> 0) . length) $ iterate (reverse . transpose . tail) matrix       

Alternatively, instead of using "tail method" - we can simply, take the last row of the transposed matrix each time, and then do our transformations with the top part of the matrix remaining. I thought this could be done without using the reverse operation (hence it would be more "effiecient"). But alas, efficiency Gods have betrayed me, since I still needed that operation to maintain the order of the elements picked up. And the first row would have to be dealt with separately. here is a recursive definition of the same -

ribbon' [] = []
ribbon' ((x:xs):[]) = reverse (x:xs)
ribbon' matrix = last matrix ++ (ribbon' $ transpose $ reverse $ init matrix)

ribbon matrix = head matrix ++ (ribbon' $ transpose $ tail matrix)

Again, this approch sidesteps the "reverse" in the first call, but then, the operation must be done to ensure the "turn right" part. Personally, this looks less neat.

Now, I want to be clear, you are not going to win any efficiency points with this. But my goal is not efficiency as an abstract but to approach it from a functional angle. And it is easier, once you start thinking functionally to apply your solution to all functional programming languages. I learnt how to think like this in Haskell first. It’s what I revert to when I have to “think” of the problem, and then it becomes a matter of finding equivalent functions in other languages. Now, there are some language specific things that cannot be translated. They are the features that fundamentally change from one language to another. But still, I find for these trivial problems, some portability is quite easy to achieve.