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 ]
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 ]
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
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])
}
}
...
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)
...
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 ];
...
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] )
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
...
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 ];
}
...
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;
}
...
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
}
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
}
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} );
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
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
(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 ...
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)
...
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}
Oldest comments (0)