[erlang-questions] Matrix rotator

[Bryan Fink]

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

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(Matrix) ->
    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.

-Bryan