DEV Community

Myoungjin Jeon
Myoungjin Jeon

Posted on

Weekly Challenge #088 Task #2 :: (Perl, Raku and More)

TASK #2 › Spiral Matrix

Submitted by: Mohammad S Anwar

You are given m x n matrix of positive integers.

Write a script to print spiral matrix as list.

Example 1:

Input:
    [ 1, 2, 3 ]
    [ 4, 5, 6 ]
    [ 7, 8, 9 ]
Ouput:
    [ 1, 2, 3, 6, 9, 8, 7, 4, 5 ]
Enter fullscreen mode Exit fullscreen mode
Example 2:

Input:
    [  1,  2,  3,  4 ]
    [  5,  6,  7,  8 ]
    [  9, 10, 11, 12 ]
    [ 13, 14, 15, 16 ]
Output:
    [ 1, 2, 3, 4, 8, 12, 16, 15, 14, 13, 9, 5, 6, 7, 11, 10 ]
Enter fullscreen mode Exit fullscreen mode

Imperative approach (Perl, Golang, Common-lisp)

When I finished the common-lisp solution, I think this approach is better because there is no worry about side effect and no more manipulating data during the process.

To do get a spiral array from a matrix, we need to know how to read outside cells around the matrix.
Let's go as if there is no offset to get inside cells by going through spiral way.

North Segment

To be fair, nothing to say much of this one
because it is natural way to read a row(array)
this is a perl code.

push @spiralArray, @mat[0] # reading top(first) of the matrix
Enter fullscreen mode Exit fullscreen mode

East Segment

also has natural way to read column, but the cell rightmost on the top of matrix is already read. so we need to skip the cell.
Firstly let's look into golang code because it is good language for imperative approach.

...
if num_rows > 1 {
    for r := 1; r <= row_end; r++ {
        sarr = append(sarr, mat[r][col_end])
    }
}
...
Enter fullscreen mode Exit fullscreen mode

and common-lisp code might be

...
   (let ((east-side (loop for r from (1+ o) upto row-end
                           collect (aref mat r col-end))))
     (when (not (null east-side))
       (nconc sarray east-side)
...
Enter fullscreen mode Exit fullscreen mode

Common-lisp has nice macro for loop, very impressive every time I discover something more.

But I applied some different method in Perl,

...
    push @spiral_array,
      map { $_->[$col_end] } @mat[ $o + 1 .. $row_end ];
...
Enter fullscreen mode Exit fullscreen mode

Yeah... I know. it look weird. I'm obsessed with map in this period. but in Raku, we can write much better. below code is pseudo code but it seems alright.

 @spiral-array.append( @matrix[ 1 .. $row_end; $col_end] )
Enter fullscreen mode Exit fullscreen mode

I think this is really really cool. handy and straightforward!!

South Segment

south one is little more different, because the cell in the right most at the bottom is already scanned before. we need to omit those again. and also we need to reverse the order of occurrence of the cells

...
    # south
    if ( $num_cols > 1 ) {
        push @spiral_array,
          @{$mat[$row_end]}  # bottom
            [ reverse 1 .. ($col_end -1) ]; # reverse order as well
...
Enter fullscreen mode Exit fullscreen mode

West Segment

last one has shortest member due to other segment are greed so they all get what they could.

...
    # west
      if ( $num_rows > 2 ) {
          push @spiral_array,
            map { $_->[$o] } reverse @mat[ $o + 1 .. $row_end - 1 ];
      }
...
Enter fullscreen mode Exit fullscreen mode

How to go inside Onion 🧅 (matrix)??

I applied offset variable which is grows every time we are done to read one layer of matrix and go inside the matrix. and numbers of rows and numbers of columns also reduced along with offset variable.

...
    for ( my $o = 0; $num_rows > 0 && $num_cols > 0; ++$o ) {
        my ($row_end, $col_end) = map { $o + $_ -1 } $num_rows, $num_cols;
    ... snip ...
       # go inner matrix
        $num_rows -= 2;
        $num_cols -= 2;
    }
...
Enter fullscreen mode Exit fullscreen mode

And also we need to change the code to work with offset variable and num_rows and num_cols! so I leave the full code of the function called "getSpiralArrayFromMatrixRef()"

sub getSpiralArrayFromMatrixRef ($) {
    my @mat = @{$_[0]}; # copy

    my $num_rows = scalar @mat;
    my $num_cols = scalar @{$mat[0]};

    my @spiral_array;
    for ( my $o = 0; $num_rows > 0 && $num_cols > 0; ++$o ) {
        my ($row_end, $col_end) = map { $o + $_ -1 } $num_rows, $num_cols;

        # north
        push @spiral_array, @{$mat[$o]}[$o .. $col_end];
        # east
        if ( $num_rows > 1 ) {
            push @spiral_array,
              map { $_->[$col_end] } @mat[ $o + 1 .. $row_end ];
            # south
            if ( $num_cols > 1 ) {
                push @spiral_array,
                  @{$mat[$row_end]}[ reverse $o .. ($col_end -1) ];
                # west
                if ( $num_rows > 2 ) {
                    push @spiral_array,
                      map { $_->[$o] } reverse @mat[ $o + 1 .. $row_end - 1 ];
                }
            }
        }
        # go inner matrix
        $num_rows -= 2;
        $num_cols -= 2;
    }

    @spiral_array
}
Enter fullscreen mode Exit fullscreen mode

A bit Functional Approach (Raku, Haskell)

In Raku, I made a function called peel-off which read outside of matrix in clockwise and return it with inner matrix

sub peel-off( @a ) {
    my ( $re, $ce ) = @a.end, @a[0].end;

    my @inside  = @a[ 1 .. $re.pred; 1 .. $ce.pred ] // Empty;
    @inside .= rotor($ce.pred).map(*.Array) if @inside; 
    my @outside = @a[ 0; * ];                           # outside of top

    for ( [ 1 .. $re;     $ce         ],                # outside of right
          [ $re;          $ce.pred,
                          $ce.pred.
                           pred ... 0 ],                # outside of bottom
          [ $re.pred,
            $re.pred.
             pred ... 1;   0         ]  )               # outside of left
    -> ( $rr, $cr ) {
        last unless all( $rr.elems.so, $cr.elems.so );  # out of range
        @outside.append: @a[$rr[*]; $cr[*]];
    }

    @inside, @outside
}
Enter fullscreen mode Exit fullscreen mode

Raku works quite well with range in a matrix, so I use a for loop to iterate the row and column range for each segment. and basically this was my first solution. and I need to go inside by using repeat .. while loop

my ( $in, $out );
repeat {
    ( $in, $out ) = peel-off( @mat );
    @spiral.append: |$out;
    @mat = |$in;

} while ( @mat[0] andthen { .elems > 0} );
Enter fullscreen mode Exit fullscreen mode

It works as I expected without many debugging.

In Haskell, I could use more higher order function called unfoldr

getSpiralAarray :: [[String]] -> [String]
getSpiralAarray mat =
  foldr1 (++)
  ( unfoldr (\m ->
                 case m of
                   Nothing -> Nothing
                   Just m' -> case (getInnerMatrix m') of
                                Left  _   -> Just (outOf m', Nothing)
                                Right m'' -> Just (outOf m', Just m''))
      (Just mat) )
  where outOf m = readAroundMatrixCW m
Enter fullscreen mode Exit fullscreen mode

and I make a function for reading outside of matrix and another one for get inner matrix separately

getInnerMatrix :: [[String]] -> Either String [[String]]
getInnerMatrix m
  | length m <= 1 = Left "Too Short In Row"
  | otherwise = mapCutColumns [] getShorterInRows
    where
      mapCutColumns acc [] = Right acc
      mapCutColumns acc (r:rs) =
        case getShorterInCols r of
          Nothing -> Left "Too Short In Column"
          Just r' -> mapCutColumns (acc ++ [r']) rs
      getShorterInRows = (init.tail) m -- cut top and bottom
      getShorterInCols row =
        if (length row) <= 1 then Nothing
        else Just $ (init.tail) row
Enter fullscreen mode Exit fullscreen mode

(init.tail) composition works like @a[1..$#a] in Perl
this code is not efficient probably, but I think it is easier to debug. Debugging in Haskell is not easy, IMHO. Especially it is not when debugging a pure function.

and To reading outside...

readAroundMatrixCW :: [[String]] -> [String]
readAroundMatrixCW [] = []
readAroundMatrixCW m =
  foldr1 (++) $
  getNorth
  : case findEast of
      Nothing -> []
      Just  e -> e
        : case findSouth of
            Nothing -> []
            Just  s -> s
              : case findWest of
                  Nothing -> []
                  Just  w -> [w]
  where
... snip ...
Enter fullscreen mode Exit fullscreen mode

I skipped the where part for blog purpose. main different thing is that I need to specify the every return value in branch. and I'm still happy with that. This kind of practice helps a lot when creating a function in Perl as well.

Elm Solution

After noticing there is some chance to produce unnecessary data, I made another type of solution in Elm(basically function programming language). I confessed that it is hardest to debug. because it is not handy to access the element in the list in Elm. perhaps I need to zip the each row number or column number along with the data but I just use drop, take and "head" composition.
code below is for reading west segment in Elm.

...
        west  = {-if L.isEmpty south then []
                else-} -- already checked previously
                if nr <= 2 then []
                else mat
                    |> L.drop (o+1)
                    |> L.take (nr-2)
                    |> L.reverse
                    |> L.filterMap (L.drop o >> L.head)
...
Enter fullscreen mode Exit fullscreen mode

But I really enjoyed the syntax |> because it makes more readable for most of programmer even if this is a functional programming language!!! we don't need to read from bottom to top anymore!!
>> is an composition operator (which is same as . in Haskell) but applying order is left from right as the arrow direction indicate. so << has the normal composition way as . does.

Okay. That's all for this week.
Please don't forget the visit~~!!
🐪PWC🦋

I'll have my holiday for challenge. I need to do something more important things in my life.
and I'll come back next year!!! 👋
say $_ for "Merry Christmas", "and", "Happy New Year!!";

$Myoungjin_JEON=@@=qw^rekcaH lreP rehtonA tsuJ^;$|++;{$i=$like=pop@@;unshift@@,$i;$~=18-length$i;print"\r[","~"x abs,(scalar reverse$i),"~"x($~-abs),"]"and select$good,$day,$mate,1/$~for 0..$~,-$~+1..-1;redo}
Enter fullscreen mode Exit fullscreen mode

Top comments (0)