[erlang-questions] Matrix rotator
Mon Jun 15 04:41:25 CEST 2009
On Sun, Jun 14, 2009 at 4:24 PM, Tony Arcieri<tony@REDACTED> wrote:
> On Sun, Jun 14, 2009 at 2:08 PM, Johnny Billquist <bqt@REDACTED> wrote:
>> The problem is rather trivial in itself. Are you looking for some
>> particularly efficient algorithm, or what?
> Whatever you'd like, but creative or clever solutions are always
Oh, hell - why not? I'll submit:
rotate() -> ;
rotate(Matrix) -> rotate(Matrix, ).
rotate([|_], Acc) -> Acc;
rotate(Matrix, Acc) ->
rotate([ Tail || [_|Tail] <- Matrix],
[[ Head || [Head|_] <- Matrix ]|Acc]).
If I count correctly, the above is 1 intermediate list created (the
"next tails") and 2 list-reversals (each list-comp) for each row of
input. I was also able to come up with a version that made the
tradeoff of 50% more intermediate lists, but a quarter of the
reversals (again, if I count correctly). It also cuts out half the
traversals of the list of rows. That code is below, but is nowhere
near as concise:
rotate() -> ;
rotate(forward, lists:reverse(Matrix), [  || _ <- hd(Matrix) ]).
rotate(forward, , Acc) -> lists:reverse(Acc);
rotate(backward, , Acc) -> Acc;
rotate(forward, [Row|Rest], Acc) ->
rotate(backward, Rest, prepend(Row, Acc));
rotate(backward, [Row|Rest], Acc) ->
rotate(forward, Rest, prepend(lists:reverse(Row), Acc)).
prepend(From, To) -> prepend(From, To, ).
prepend([Hf|Tf], [Ht|Tt], Acc) -> prepend(Tf, Tt, [[Hf|Ht]|Acc]);
prepend(, , Acc) -> Acc.
More information about the erlang-questions